The DC Algorithm For Nonconvex Optimization And Its Applications

Nonconvex optimization has been widely used in deep learning,simulation and financial analysis and forecasting,such as nonlinear least squares problem,quadratically constrained quadratic problems,rank minimization problems.This thesis aims to study two kinds of the nonconvex problems:quadratic assignment problems(QAP)and sparse Envelope regression problems.However,most nonconvex problems are hard to solve directly,some even are NP-hard.Therefore,this thesis tries to solve nonconvex problems by using the techniques of convex relaxation and the proximal point theory.The framework for DC relaxation problems are designed based on the mathematical characteristics and the structural feature of QAP and sparse envelope model respectively.Firstly,this paper studies the classical mathematical model of facility location problem–quadratic assignment problem,which aims to build a mathematical model of separating9)facilities on9)locations so as to minimize the distance between facilities and the flow between locations.Such problem has important applications in chip design,equipment manufacturing,computer graphics and vision.In this paper,we propose a new double nonnegative conic model with a rank constraint,and prove that it is equivalent to the original QAP,even it is still NP-hard.However,this paper constructs the corresponding DC programming relaxation model,and designs a semi-proximal DC Algorithm(DCA)to solve that relaxed problem.By using SDPNAL+software package,the improved semismooth Newton-CG augmented Lagrange method is used to solve the subproblems of DCA.For a large amount of numerical examples in the QAPLIB database,numerical results show that the proposed algorithm can effectively find the global optimal integer solutions of most QAP problems.Secondly,this thesis studies the application of DC method in multivariate statistical regression.In order to reduce the redundancy of the large scale regression model,Cook et al.^[1]proposed a sparse envelope model to improve the efficiency of estimation.By use of the structure characteristics of the objective function of the sparse envelope model(SEM),this paper presents the DC decomposition form of the sparse Envelope problem.Furthermore,an accelerate proximal gradient method is proposed to solve the convex subproblems of the DC algorithms based on the Lipschitz property of the gradient of the objective function.Numerical experiments are implemented in Matlab for solving the SEM.By randomly generating samples and coordinate matrices of sparse Envelope model,numerical results show that the proposed algorithm is more effective than the block coordinate descent(BCD)algorithm^[2]for solving the SEM.Based on the above research about two kinds of non-convex optimization problems,we can see that the DC program can solve the quadratic assignment problem and the sparse Envelope problem efficiently and quickly after constructing the appropriate convex relaxation problems.