A Penalty Method For Matrix Rank Minimization Problems

This thesis studies the matrix rank minimization problem(LCRMP)with linear constraints.LCRMP is widely used in many fields.Because its objective function is non-convex,LCRMP has always been considered to be computationally challenging,and as the matrix order increases,the problem will become NP-hard.The current methods for solving matrix rank minimization problems include non-convex optimization algorithms and heuristics algorithm.This thesis constructs complementary constraint variables and transforms LCRMP into a mathematical programming problem with semidefinite cone complementary constraints(SD-CMPCC).Different from the general MPCC problem,by constructing special complementary variables,the transformed SDCMPCC problem satisfies Clarke stationary at the local minimum point.Under this constraint qualification,the transformed SDCMPCC problem can ensure that the classic KKT condition is established at the local minimum.In this thesis,the non-smooth penalty model of SDCMPCC is given,and the objective function is expressed as the difference between two convex functions to construct the DC pro-gramming problem.In this thesis,generalized Slater constraint qualifications are added to the feasible region of the SDCMPCC non-smooth penalty model,which proves that Clarke station-ary holds at its local minimum point,and it is concluded that the classic KKT condition holds at the local minimum point of the SDCMPCC penalty problem.This thesis introduces the matrix completion rank minimization problem and conducts a numerical experiment,transforming the matrix completion rank minimization problem into a DC programming problem.A sequence linear semidefinite programming algorithm for solving DC programming problems is given,And compared with the solution obtained by the singular value threshold algorithm,The effectiveness of sequential linear semidefinite programming algorithm is proved.