Proximal Point Method For Linearly Constrained Optimization Problems And Its Convergence

Proximal point algorithm is a type of method widely used in solving optimization problems,fixed point problems,maximum monotone operator problems and so on.By the framework of proximal point method,it is not only closely related to many algorithms,but also can do more interpretation and generalization of some methods.In recent years,combining the idea of proximal point method or the proximal terms with some existing algorithms also shows that it can improve the performance of the original algorithms to a certain extent.Attracted by the research value of proximal point method in the algorithm theory and their many applications,this dissertation aims to study a type of accelerated proximal point algorithm and a generalized alternating direction method of multipliers with semi-proximal terms for solving linear equality constrained convex optimization problem.The full text consists of six chapters.The first chapter is the introduction.It mainly introduces the research background,the preliminary concepts and properties related to this dissertation.At first,we review the main research results and the development of proximal point method in the optimiza-tion fields.Then we introduce some definitions such as optimization conditions,convex functions,subgradient and subdifferentiation,ε-subgradient and ε-subdifferentiation,conjugate function,Moreau envelope,proximal point operator and other concepts,prop-erties and some basic conclusions.In Chapter 2,an algorithm framework of accelerated proximal point method is pre-sented for a class convex constrained optimization problems with linear equalities.The method can be seen as an extension to Guler’s methods for unconstrained optimiza-tion and linear programming problems.For unconstrained convex optimization problem,Guler ever gave the classical convergence rate which based on the objective function val-ue f(xk)-f(x*)for an accelerated proximal point algorithm,but left the convergence problem of the sequence ｛xk｝k∈N generated by the algorithm.Differ from the using of the accelerated proximal point method on the dual problem of linear programming,our algorithm directly uses the accelerating technique both on the proximal point operator and the Lagrange multiplier for the original constrained convex optimization problem in the iteration.It can be proved that the sequence generated by the algorithm converges to a KKT solution of the original problem under appropriate conditions.And also the convergence rate base on the value of the objective function is proved.In Chapter 3,in the case of inexactly solving the proximal point subproblems,the accelerated proximal point algorithm and its convergence are discussed.The updating of xk+1、,vk+1*,yk and the other auxiliary quantities in iteration are updated and calculated by a non-precision but more easily achieved rule.The convergence property of the algorithm is proved under some proper conditions.Our main work of the accelerated proximal point algorithm for linearly constrained convex optimization problems is:1)By using of the Lagrange function,KKT system and the original-dual relation of the optimization problem,we construct appropriate auxiliary sequences with the quadrat-ic convex functions φk(x)and the auxiliary points {yk}k∈N,generate the update of xk and the Lagrange multipliers λx respectively.Then we extend the accelerated proximal point method to the general convex optimization problems with equality constrains and give the convergence properties of the algorithm in the case of the iteration subproblem is solved exactly.2)In the iteration of the original accelerated proximal point method,the update of vk+1 needs the exact value of xk+1 but which in practice is difficult to calculate and the true values often can not be obtained accurately.Then,the convergence rate result,O(1/k2),may not be guaranteed.Hence,in the general accelerated algorithm,we adopt the updating rule which is more convenient for calculation in practice and then discuss its global convergence in the non-precision resolving case.3)In the extended accelerated algorithm,the parameter ak which is related to the convergence rate of the whole algorithm is updated by an introduced constant c.The update of ak in Guler’s algorithm can be seem as a special case with c=1.In Chapter 4,for a type of 2-block separable convex optimization problems,we discuss the convergence of a generalized alternating direction method of multipliers with semi-proximal terms.With the connection between ADMM method,splitting algorithm and the proximal point algorithm,a discussion similar to chapter 2 is used and the global convergence property of the algorithm is proved under some simple conditions.In Chapter 5,based on the previously discussed accelerated proximal point method,some other proximal-type algorithms are shown.Also the algorithms are tested on solving quadratic programming and total variation regularized image denoising problem.The efficiency of the algorithms is demonstrated by numerical comparison to some existing accelerated methods.In Chapter 6,we summarize the dissertation and give some further research direction in the future.