Approximate Bundle Methods And Applications

Bundle methods are at the moment considered as one of the most efficient and promising methods for solving nonsmooth optimization problems. They have already been applied to many practical areas, for example, economy, mechanics, engineering, optimal control and so on. Researches on bundle methods touch upon such mathematical branches as convex analysis, nonlinear programming and nonsmooth analysis. This dissertation is devoted to the study of approximate bundle methods for solving nonsmooth optimization problems and the applications of approximate bundle methods to MPECs problems and generalized variational inequalities.The main results obtained in this dissertation are summarized as follows:1. Based on the fact that some function values are not easy to compute, Chapter 2 establishes a piecewise linear model by utilizing approximate objective function values and subgradients. By comparing with the ones appeared in other references, our model is much closer to objective function. A possible descent direction is obtained by using the piecewise linear model, and the problem of searching descent direction can be converted into a quadratic programming, which decreases the difficulty of the problem. Chapter 3, 4, 5, 6 are written based on the construction of this model.2. Chapter 3 proposes a proximal bundle method with inexact data for nonsmooth convex unconstrained optimization. Firstly, a possible descent direction is obtained by minimizing the piecewise linear model, then some conditions for serious steps and null steps are given. Convergence analysis followed the proposed algorithm shows that even we only use the inexact values of objective function and subgradients, the algorithm converges to the optimal solution. Based on the same assumption mentioned above, an infeasible bundle method is also presented for solving nonsmooth convex constrained optimization problem. The original problem changes into the unconstrained minimization of the improved function. But with the generation of new serious step, the improved function must be defined again. The method ensures the convergence of the algorithm even though the first original point and the serious points generated in iteration process are infeasible.3. Chapter 4 gives an implementable algorithm for nonsmooth unconstrained optimization by combining the regularization of Moreau-Yosida, bundle idea and quasi-Newton method. This method focuses on the study of the minimization problem of Moreau-Yosida regularization, the bundle idea is adopted to approximate the nonsmooth function. Quasi-Newton...