Optimality Theory For Low-rank Constrained Matrix Optimization

Low-rank matrix optimization is a class of matrix optimization problems with rank constraint.With wide applications ranging from statistics and machine learning,signal and image processing,communication and quantum computing,system identification and control,to economics and finance.Low-rank matrix optimization is currently a key research direction in optimization and related fields.Due to the combinatorial features caused by the discontinuous and nonconvex rank function,however,low-rank matrix optimizations are computationally NP-hard in gen-eral.Traditional convex optimization theory is difficult to apply to the nonsmooth and nonconvex problems.Hence,literature on optimality conditions for this problem need to be explored.In this thesis,we mainly aim to study the optimality conditions of the low-rank constrained matrix optimization by making use of the tangent cones and normal cones to the feasible set.We study the optimality theory from only low-rank constrained matrix optimization to the low-rank constrained matrix optimization over spectral sets,and then to the low-rank matrix optimization with affine set.All these results enrich the theory of low-rank matrix optimization and give potential clues to designing efficient numerical algorithms for seeking low rank solutions.For the low-rank constrained matrix optimization,by calculating the Clarke tan-gent and normal cones to low-rank set,along with the given Frechet,Mordukhovich normal cones,we investigate four kinds of stationary points,and analyze the relations between each stationary point and a local/global minimizer.Furthermore,the second-order optimality condition is also achieved with the help of Clarke tangent cone.Finally,some applications are discussed to illustrate our proposed optimality conditions.For the low-rank constrained matrix optimization over spectral sets,we consid-er three typical spectral sets,yielding three low-rank spectral sets.For each low-rank spectral set,we first calculate the projection of a given point onto this set and the for-mula of its Frechet normal cone,based on which the induced stationary points of matrix optimization over low-rank spectral sets are then investigated.Finally,we reveal the re-lationship between each stationary point and each local/global minimizer and establish the first-order and the second-order optimality conditions.Meanwhile,we illustrate our proposed optimality analysis for several applications including the low-rank approxi-mation of graph similarity matrices and the quantum tomography problem.For the low-rank matrix optimization with affine set,under some suitable assump-tions,we establish the intersection rule of the Frechet normal cone to the feasible set.This allows us to propose the first-order optimality conditions in terms of the so-called F-stationary point and the ?-stationary point.Furthermore,the second-order optimality analysis,including the necessary condition and the sufficient one,is proposed as well.Finally,several specific applications are discussed to illustrate our proposed optimality analysis.