Search

We propose Riemannian preconditioned algorithms for the tensor completion problem via tensor ring decomposition. A new Riemannian metric is developed on the product space of the mode-2 unfolding matrices of the core tensors in tensor ring decomposition. The construction of this metric aims to approximate the Hessian of the cost function by its diagonal blocks, paving the way for various Riemannian optimization methods. Specifically, we propose the Riemannian gradient descent and Riemannian conjugate gradient algorithms. We prove that both algorithms globally converge to a stationary point. In the implementation, we exploit the tensor structure and adopt an economical procedure to avoid large matrix formulation and computation in gradients, which significantly reduces the computational cost. Numerical experiments on various synthetic and real-world datasets—movie ratings, hyperspectral images, and high-dimensional functions—suggest that the proposed algorithms have better or favorably comparable performance to other candidates. [ABSTRACT FROM AUTHOR]

The speeding-up and slowing-down (SUSD) direction is a novel direction, which is proved to converge to the gradient descent direction under some conditions. The authors propose the derivative-free optimization algorithm SUSD-TR, which combines the SUSD direction based on the covariance matrix of interpolation points and the solution of the trust-region subproblem of the interpolation model function at the current iteration step. They analyze the optimization dynamics and convergence of the algorithm SUSD-TR. Details of the trial step and structure step are given. Numerical results show their algorithm's efficiency, and the comparison indicates that SUSD-TR greatly improves the method's performance based on the method that only goes along the SUSD direction. Their algorithm is competitive with state-of-the-art mathematical derivative-free optimization algorithms. [ABSTRACT FROM AUTHOR]

Quadratically constrained quadratic programming (QCQP) appears widely in engineering applications such as wireless communications and networking and multiuser detection with examples like the MAXCUT problem and boolean optimization. A general QCQP problem is NP-hard. We propose a penalty formulation for the QCQP problem based on semidefinite relaxation. Under suitable assumptions we show that the optimal solutions of the penalty problem are the same as those of the original QCQP problem if the penalty parameter is sufficiently large. Then, to solve the penalty problem, we present a proximal point algorithm and an update rule for the penalty parameter. Numerically, we test our algorithm on two well-studied QCQP problems. The results show that our proposed algorithm is very effective in finding high-quality solutions. [ABSTRACT FROM AUTHOR]

In this paper we study the worst-case complexity of an inexact augmented Lagrangian method for nonconvex constrained problems. Assuming that the penalty parameters are bounded we prove a complexity bound of |$\mathcal{O}(|\log (\epsilon)|)$| outer iterations for the referred algorithm to generate an |$\epsilon$| -approximate KKT point for |$\epsilon \in (0,1)$|⁠. When the penalty parameters are unbounded we prove an outer iteration complexity bound of |$\mathcal{O}(\epsilon ^{-2/(\alpha -1)})$|⁠ , where |$\alpha>1$| controls the rate of increase of the penalty parameters. For linearly constrained problems these bounds yield to evaluation complexity bounds of |$\mathcal{O}(|\log (\epsilon)|^{2}\epsilon ^{-2})$| and |$\mathcal{O}(\epsilon ^{- (\frac{2(2+\alpha)}{\alpha -1}+2)})$|⁠ , respectively, when appropriate first-order methods (⁠|$p=1$|⁠) are used to approximately solve the unconstrained subproblems at each iteration. In the case of problems having only linear equality constraints the latter bounds are improved to |$\mathcal{O}(|\log (\epsilon)|^{2}\epsilon ^{-(p+1)/p})$| and |$\mathcal{O}(\epsilon ^{-(\frac{4}{\alpha -1}+\frac{p+1}{p})})$|⁠ , respectively, when appropriate |$p$| -order methods (⁠|$p\geq 2$|⁠) are used as inner solvers. [ABSTRACT FROM AUTHOR]

We present a partial first-order affine-scaling method for solving smooth optimization with linear inequality constraints. At each iteration, the algorithm considers a subset of the constraints to reduce the complexity. We prove the global convergence of the algorithm for general smooth objective functions, and show it converges at sublinear rate when the objective function is quadratic. Numerical experiments indicate that our algorithm is efficient. [ABSTRACT FROM AUTHOR]

Trust region methods are a class of numerical methods for optimization. Unlike line search type methods where a line search is carried out in each iteration, trust region methods compute a trial step by solving a trust region subproblem where a model function is minimized within a trust region. Due to the trust region constraint, nonconvex models can be used in trust region subproblems, and trust region algorithms can be applied to nonconvex and ill-conditioned problems. Normally it is easier to establish the global convergence of a trust region algorithm than that of its line search counterpart. In the paper, we review recent results on trust region methods for unconstrained optimization, constrained optimization, nonlinear equations and nonlinear least squares, nonsmooth optimization and optimization without derivatives. Results on trust region subproblems and regularization methods are also discussed. [ABSTRACT FROM AUTHOR]

We present a decomposition method for training Crammer and Singer's multiclass kernel-based vector machine model. A new working set selection rule is proposed. Global convergence of the algorithm based on this selection rule is established. Projected gradient method is chosen to solve the resulting quadratic subproblem at each iteration. An efficient projection algorithm is designed by exploiting the structure of the constraints. Parallel strategies are given to utilize the storage and computational resources available on the multiprocessor system. Numerical experiment on benchmark problems demonstrates that the good classification accuracy and remarkable time saving can be achieved. [ABSTRACT FROM AUTHOR]

An interior-point trust-region algorithm is proposed for minimization of a convex quadratic objective function over a general convex set. The algorithm uses a trust-region model to ensure descent on a suitable merit function. The complexity of our algorithm is proved to be as good as the interior-point polynomial algorithm. [ABSTRACT FROM AUTHOR]