VU-Decomposition Theory Based On Several Classes Of Bundle Methods

Over the past decade, several independent researches studying nonsmooth optimization have developed classes of functions and sets that, though nonsmooth themselves, have underly-ing smooth substructure. These substructures are exploited for algorithmic purposes, to create calculus rules, and develop sensitivity analysis. Basing on this substructure, Lemarechal, Mif-flin, Sagastizabal and Oustry introduced Vu-theory in 2000. The basic idea is to decompose Rn into two orthogonal subspaces u and V so that f's nonsmoothness is concentrated essentially in V. It is possible to find smooth trajectories, via the intermediate function, called u-Lagrangian, yielding a second-order expansion for f. In 2004, Mifflin and Sagastizabal presented the VU-smoothness and proximal point results for some nonconvex functions. However, the study on constraint problem and the application of vu-decomposition method is not enough. The main results of this dissertation can be summarized as follows:1. Chapter 2 studies a superlinear space-decomposition algorithm for constrained nonsmooth convex programs. We consider the constrained nonsmooth convex optimization problems, that is, piecewise C2 convex objectives with smooth convex inequality constraints. With the help of exact penalty function, these programs are transformed into unconstrained nonsmooth convex programs. The objective functions of these unconstrained programs are particular cases of functions with primal-dual gradient structure which has connection with Vu-space decomposition. Based on this special structure, a smooth trajectory can be computed and the second-order expansion of f can be obtained. A Vu-space decomposi-tion method for solving these constrained programs is given. This method is proved to be convergent with local superlinear rate under certain assumptions. An illustrative example is given to show how this method works.2. Chapter 3 discusses an approximate decomposition algorithm for convex minimization. For nonsmooth convex optimization, Mifflin and Sagastizabal introduced a Vu-space decom-position algorithm. However, a drawback is that it needs the exact subgradient of the objective function, which is expensive to compute. To solve this problem, this chapter in-troduces a conception of approximate u-Lagrangian and gives its corresponding results. An approximate decomposition algorithm frame that is capable to deal with approximate subgradients is given. This method can implement with the theory of proximal point sequence follows the primal track. Numerical tests emphasize the theoretical findings.3. In Chapter 4, we apply the Vu-theory to the second-order cone programming problem. The Vu-space decomposition method and primal-dual function are given. A Vu-algorithm is presented to solve the second-order cone programming problem. The algorithm is proved to converge with superlinear rate of convergence under certain assumptions. An illustrative example is given to show how the method works.