Sequential Convex Approximation Approach For A Class Of Matrix Variable Quadratic Function Minimization Problems With Rank Constraint

Matrix variable quadratic function minimization problems, especially a class of rank con-strained matrix variable quadratic function minimization problems, have drawn a lot of interest in recent years. They arise in various applications, e.g., quantitative economy, statistics, machine learning, image and video processing, etc.This thesis mainly focus on numerical methods for rank constrained quadratic function mini-mization problems with symmetric semidefinite matrix variables and with non-symmetric matrix variables. Outline of this thesis is as follows:1. In Chapter 3 and 4, rank constrained quadratic function minimization problems with semidefinite matrix variables are discussed. This kind of problems is first reformulated to a DC constrained problem via the equivalence between rank constraint and difference of two ma-trix norms. Theoretical difficulties are embedded in the new reformulation for the violation of Slater's condition, which condition guarantees convergence of the classical sequential convex ap-proximation (SCA) approach. To overcome above difficulty, in Chapter 3 a relaxation variable ? is introduced to establish an ?-relaxation SCA approach. Convergence is proved, and numer-ical experiments demonstrate its efficiency. In Chapter 4 a different SCA-based non-smooth equation method is proposed. This approach considers three non-smooth equations equivalent to optimality conditions for the DC constrained model. Its basic idea can be described as follows: firstly fix a variable and solve two of the three equations to update the rest two variables itera-tively, secondly at a proper time update the fixed variable with the rest equation, finally repeat above procedure until convergence. This approach is guaranteed to converge under proper con-ditions. One should also note that this approach can be applied to some more complex problems involving H-type weight. Numerical experiments illustrate that it is very efficient.2. In Chapter 5, to find a substitution of rank function is considered as an alternative way to solve the problems. A non-smooth approximation of rank function is proposed for symmetric matrices, and the characteristic of its subdifferential is also discussed. Notice that the newly pro-posed approximation can be generalized to non-symmetric case via symmetrization operator. To verify its applicability, the approximation function is applied to the calibrating correlation matrix model and the matrix completion model. Numerical experiments suggest that it is applicable.3. In Chapter 6, a rank constrained quadratic function minimization problem with non-symmetric matrix variables is considered via its Lagrange dual. For this non-convex hard prob-lem, its convex Lagrange dual problem is simplified, and the weak dual property is proved to hold. Furthermore, with some stronger (with respect to convex dual theory) conditions, strong dual property also holds, i.e., in such conditions, solving a non-convex rank constrained quadratic function minimization problem is equivalent to solving a convex problem.