Research On Approximate Projection Algorithms For Constrained Optimization Problems

In recent years,constrained optimization problem have become widespread in many fields and gained much attention.Such as image and signal pro-cessing,data analysis and artificial intelligence,computational physics and chemistry.In order to solve this type of problem in a better way,we propose a new random relaxation ap-proximation projection algorithm,a new moving balls approximation projection method.If the objective function is the sum of multiple convex functions,the constraint set is the intersection of a finite number of general closed convex sets and the constraint function is a subdifferentiable convex function,we propose a variance reduced random relaxation projection method（VR³PM）and analyze its convergence rate in Chapter 3.This method combines the advantages of the random projection method and the variance reduced method.And it is easy to implement.This chapter gives easy-to-judge general sufficient conditions for the key linear regularity assumption in the random projection-type method.In addition,existing random relaxation projection methods require the assump-tion that the subgradient of the constraint function is bounded,while VR³PM given in this chapter does not require this assumption.Chapter 3 establishes the convergence rates of O(1/k^1/2)and O（1/k）when the objective function is convex and strongly convex,respec-tively.In the numerical experimental section,the experimental reports of this method for solving LCQP,QCQP,convex regression problems,and distributed robust optimization problems are given to illustrate the practicality of our method.If the objective function is the sum of multiple convex functions,the constraint functions are differentiable,and the gradients of the constraint functions are Lipschitz-continuous,a more efficient variance reduced moving balls approximation method（VR-MBAM）is proposed in Chapter 4.This method combines the advantages of the SVRG method and the moving balls approximation method.Compared with existing convergence rates of moving balls approximation-type methods that require the strong convexity of the objective function,a notable advantage of the proposed method is that the linear and sub-linear convergence rates can be guaranteed under the quasi-strong convexity and convexity conditions,respectively.This method has a convergence rate of O（1/k）when the objec-tive function is a general convex function.In summary,our variance reduced moving balls approximate method has the same convergence rate as the classical gradient projection algorithm and is easy to implement.In the numerical experimental section,we give the experimental results of the algorithm in solving the regular logistic regression problem and Neyman-Person classification problem,to verify the efficiency of the proposed method.By combining the FISTA accelerated algorithm with the moving balls approxi-mate method,an accelerated version of the moving balls approximate projection method（FISTA-MBAM）is proposed in Chapter 5.The existing convergence rates of moving balls approximation-type methods require the strong convexity of the objective function.While in this chapter,the accelerated version of the moving balls approximation projection method can achieve a convergence rate of O（1/k²）when the objective function is con-vex.In the numerical experimental section,the experimental reports for solving QCQP are given to illustrate the practicality of this method.