Research On The Dual Problems Of Several Bundle Methods For Convex Optimization Problems

For unconstrained optimization problems, on the basis of proximal bundle methods, the relevant literature gives the expression of the approximate solution of the original problem and its important corresponding properties related to approximate solutions by solving the equivalent quadratic punishment sub-problem from the point of view of the dual problem. These important results become the theoretical basis of our further study on bundle methods. In this paper, based on the idea of proximal bundle method we continue to solve the unconstrained optimization problem which is equivalent to quadratic programming sub-problems with special norm standards, from the viewpoint of dual space we transform the original problem into its dual problem by employing dual theorem. We not only study the expression form of the solution, but also obtain some important corresponding properties. Because many constrained optimization problems can be transformed into unconstrained optimization problems, this paper also aims at solving the non-smooth optimization problem with constraints, and we simply use the proximal bundle method to solve it from the view of dual problem. Furthermore, we try to solve this kind of problems by combining the proximal bundle method with the level bundle method, and this creates a new way to solve this constrained optimization problem, namely doubly stabilized bundle method. We study the expression of the solution and its properties and find that the forms of the solution are not similar to the existing results, but we come to the conclusion that the solution is still related to the convex combination of the subgradients of the previous iteration. Furthermore, we find that the subgradients and the prediction descent have similar properties to the existing results.In this thesis, we mainly research on a non-smooth optimization problems with constraints from the point of view of dual space by using different bundle methods in which we take the important results obtained in unconstrained optimization problems as theory basis. The full text is divided into three parts, the main contents are as follows:The first chapter, combining with the historical background and current status of the non-smooth optimization problems, we introduce the importance and developing history of bundles method. Because of the non-smoothness of objective function, optimization problems are difficult to solve, to overcome the obstacles on the calculation and theoretical analysis, many methods have emerged and bundle method is among the others. We will introduce the basic ideas of the steepest descent method, the black box method and general bundle method for solving unconstrained optimization problems, which lays a theoretical foundation for the further study of the second and third chapter.The second chapter, we firstly introduce the generation and the basic idea of the proximal bundle method. We mainly use of the idea of the proximal bundle method and solve the unconstrained original problem by transforming it into a series of quadratic programming problems. From the viewpoint of dual space we explore the penalized sub-problems and prove some interrelated properties by adopting dual space theory. We also verify that the relationship between the original problem and dual problem and the specific forms of the optimal solution of the sub-problem can be obtained,the expression of the solution is similar to that in the previous articles. We sum up the relationship between the optimal solution of sub-problem and the convex combination of subgradients of previous iterate points, obtain the corresponding properties of subgradients and the prediction descent. Secondly, the idea of the proximal bundle method is applied again, and the optimization problem with constraints is transformed into an unconstrained problem by using indicator functions. Similar important conclusions are obtained at the same time.The third chapter, the doubly stabilized bundle method is proposed and its basic idea is described. In this chapter, with the help of the ideas of proximal and level bundle method, we covert the original problem with a non-smooth convex objective function and a non-empty closed convex constraint set to a series of quadratic programming problems with level constraints. And furthermore we covert the constrained optimization problem into an unconstrained optimization problems by using the indicator function method. Next, similarly we continue to focus on the doubly stabilized bundle method, from the viewpoint of the dual problem, we find the dual problem of the penalized sub-problem, explore some relevant properties in its dual space and verify whether the specific forms of the optimal solution of the sub-problem can be obtained,whether the relationship between the original problem and dual problem can be described like in chapter two. Finally,we sum up the relationship between the optimal solution and the convex combination of subgradients of previous iteration and obtain the properties of subgradients and the prediction descent.