SQP-Type Methods For Rank-Constrained Nonlinear Semidefinite Programming

Rank-constrained optimization is a kind of optimization problems with matrix rank constraint,which is widely used in machine learning,system control and finance,etc.The existing theories and lgorithms have solved the rank-constrained optimization problem in which the objective function is quadratic and other constraint functions are linear.The purpose of this paper is to use SQP-type method in nonlinear semidefinite programming to construct two kinds of models for solving rank-constrained nonlinear optimization problems.Based on the equivalent model,we equivalently transform the rank-constrained nonlinear semidefinite programming problem into the usual nonlinear semidefinite programming problem.Because the number of additional variables is O(m2).it is not wise to solve it directly when matrix dimension m is larger.A two-stage algorithm,combining multiplier prediction and l1 penalty method.is proposed to solve the equivalent problem.Then we analyze the well-definedness and global convergence of the algorithm and prove that the algorithm has linear convergence rate.The results of numerical experiment verify the feasibility of the theory and the effectiveness of the algorithm.Based on the approximation model,considering the difficulty of dealing with the rank constraint is that the rank function is non-convex and non-continuous.we replace the rank function with a continuously differentiable approximation function.transform the rank-constrained semidefinite programming into a sequence of nonlinear semidefinite programs,and then use the l1 penalty method to solve them.We prove the well-definedness and global convergence of the algorithm.and discuss the similarities and differences with other similar methods.In the numerical experiment part,the method of obtaining Lagrangian multipliers at KKT points is given,which is consistent with the theoretical part,and the numerical results are compared with those of the equivalent model.