Study On A Class Of Matrix Nonconvex Relaxation Methods For Binary Optimization Problems

Binary polynomial optimization problems have wide applications in a host of fields such as information technology,finance,transportation,communication network and so on.In this dissertation,based on the equivalent rank one constrained semidefinite program of this kind of combinatorial optimization problems,we study the global exact penalty induced by the rank one constraint,and propose a matrix nonconvex relaxation method,which greatly enriches the continuous relaxation methods of binary polynomial optimization.Firstly,we study the calmness of partial perturbation to composite rank constraint systems which is shown to be equivalent to a local Lipschitz-type error bound and also a global Lipschitz-type error bound under a certain compactness.Based on its lifted formulation,we derive two criteria for identifying those closed sets such that the associated partial perturbation possesses the calmness,and provide a collection of examples to demonstrate that the criteria are satisfied by common nonnegative and positive semidefinite rank constraint sets.In particular,the calmness of this composite rank constraint system implies the partial calmness of the rank constrained semidefinite program and its BM factorization.Based on the calmness of this perturbation,we obtain several global exact penalties for rank constrained optimization problems,a family of equivalent DC surrogates for rank regularized problems,and several global exact penalties for the factorized form of rank constrained optimization problems.Furthermore,we study the relation between the local optimal solutions and stationary points of these equivalent models.Then,we develop in Chapter 4 a matrix nonconvex relaxation method for a class of binary polynomial programs based on the global exact penalty of its DC constrained SDP reformulation by seeking a finite number of approximate stationary points for the factorized form of the global exact penalty with increasing penalty parameters.A globally convergent majorization-minimization(MM)method with extrapolation is developed to capture such stationary points.Under a mild condition,we show that the rank-one projection of the output for the relaxation approach is an approximate feasible solution of the UBPP and quantify the lower bound of its minus objective value from the optimal value.Numerical comparisons with the SDP relaxation method armed with a special random rounding technique and the DC relaxation approaches armed with the solvers for linear and quadratic SDPs show that the proposed relaxation approach has an advantage in offering solutions of better objective function value within less time.Finally,in Chapter 5 we prove the calmness of the composite rank constraint system associated to the DC constrained doubly nonnegative program of quadratic assignment problem,and show that the penalty problems of the DC constrained doubly nonnegative program and its factorized form are both global exact penalties.Then,we propose a matrix nonconvex method for the quadratic assignment problem by seeking a finite number of approximate stationary points for the factorized form of the global exact penalty with increasing penalty parameters,and develop an augmented Lagrange function method for solving each penalty problem which is shown that every cluster point is a stationary point of the penalty problem.Numerical experiments on QAPLIB confirm the efficiency of the proposed relaxation approach.