A Relaxed Interior Point Method for Low-Rank Semidefinite Programming Problems with Applications to Matrix...

Area of Science:

• Optimization
• Numerical Analysis
• Computer Science

Background:

• Semidefinite programming (SDP) is a powerful tool for solving complex optimization problems.
• Low-rank solutions are often desired in practical SDP applications, but standard methods struggle to find them efficiently.
• Existing interior point methods may not inherently enforce low-rank structures during iteration.

Purpose of the Study:

• To propose a new relaxed interior point method specifically designed for low-rank semidefinite programming problems.
• To develop a framework that anticipates and enforces a low-rank structure in primal iterates.
• To explore novel ways of computing primal and dual search directions within this relaxed framework.

Main Methods:

• A relaxed interior point framework is introduced, deviating from the standard approach.
• A nearly low-rank form is imposed on all primal iterates to guide convergence towards a low-rank solution.
• First-order optimality conditions are relaxed and approximated by solving an auxiliary least-squares problem.
• Both first- and second-order methods are admitted for computing approximated Newton directions.

Main Results:

• The convergence of the proposed relaxed interior point method is theoretically established.
• A prototype implementation of the method has been developed.
• Encouraging preliminary computational results were obtained for SDP-reformulations of matrix completion problems.

Conclusions:

• The new relaxed interior point method offers a promising alternative for solving low-rank semidefinite programming problems.
• The imposed nearly low-rank structure and relaxed optimality conditions are effective in achieving desired solutions.
• The method shows potential for practical applications, particularly in matrix completion.