A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion
From MaRDI portal
Publication:2236545
Abstract: A new relaxed variant of interior point method for low-rank semidefinite programming problems is proposed in this paper. The method is a step outside of the usual interior point framework. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) structure, the first order optimality conditions have to be relaxed and are therefore approximated by solving an auxiliary least-squares problem. The relaxed interior point framework opens numerous possibilities how primal and dual approximated Newton directions can be computed. In particular, it admits the application of both the first- and the second-order methods in this context. The convergence of the method is established. A prototype implementation is discussed and encouraging preliminary computational results are reported for solving the SDP-reformulation of matrix-completion problems.
Recommendations
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Matrix completion via an alternating direction method
- Semidefinite programming for discrete optimization and matrix completion problems
- Low-rank matrix completion using nuclear norm minimization and facial reduction
Cites work
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A scaled Gauss--Newton primal-dual search direction for semidefinite optimization
- A Singular Value Thresholding Algorithm for Matrix Completion
- ADMiRA: Atomic Decomposition for Minimum Rank Approximation
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- An alternating direction algorithm for matrix completion with nonnegative factors
- An inexact dual logarithmic barrier method for solving sparse semidefinite programs
- An interior-point method for large-scale l₁-regularized logistic regression
- Aspects of semidefinite programming. Interior point algorithms and selected applications
- Convergence behavior of interior-point algorithms
- Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
- Exact matrix completion via convex optimization
- Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
- Fixed point and Bregman iterative methods for matrix rank minimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Handbook on semidefinite, conic and polynomial optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Interior-point method for nuclear norm approximation with application to system identification
- Local minima and convergence in low-rank semidefinite programming
- Low-rank matrix completion using nuclear norm minimization and facial reduction
- Matrix Completion From a Few Entries
- Matrix completion via an alternating direction method
- On the solution of large-scale SDP problems by the modified barrier method using iterative solvers
- On the steplength selection in gradient methods for unconstrained optimization
- On the worst-case evaluation complexity of non-monotone line search algorithms
- Pseudoinversus and conjugate gradients
- Semidefinite optimization
- Semidefinite Programming
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Solving some large scale semidefinite programs via the conjugate residual method
- The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem
- The Gauss-Newton direction in semidefinite programming
- Two-Point Step Size Gradient Methods
Cited in
(12)- Bregman primal-dual first-order method and application to sparse semidefinite programming
- An interior point-proximal method of multipliers for linear positive semi-definite programming
- A semidefinite programming approach for the projection onto the cone of negative semidefinite symmetric tensors with applications to solid mechanics
- A feasible method for general convex low-rank SDP problems
- Provably faster gradient descent via long steps
- Multichannel frequency estimation with constant amplitude via convex structured low-rank approximation
- Loraine – an interior-point solver for low-rank semidefinite programming
- A novel nonconvex rank approximation with application to the matrix completion
- Solving low-rank semidefinite programs via manifold optimization
- Truncated LSQR for matrix least squares problems
- Proximal-stabilized semidefinite programming
- An inexact alternating projection method with application to matrix completion
This page was built for publication: A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2236545)
