Alternating Linearization Algorithms For Several Kinds Of Nonsmooth Optimizations

Recently many researchers focus on exploiting substructure of the objective function as a way to design or improve numerical algorithms in nonsmooth optimization fields. Alternating linearization algorithm for nonsmooth optimization is presented based on this idea for minimiz-ing the structured optimization problem which the objective function is the sum of two functions and it can be viewed as a class of approximate proximal point method. Many practical problems in applications such as optimal control, image processing, signal recovery, web recommenda-tion system, computer vision, system identification, bioinformatics and statistics and so on can be formulated as the summation of two functions. Therefore the algorithm research on solving these programs possesses theoretical significance and practical value.There are operator splitting methods and alternating linearization methods for minimizing the sum of two functions. When the proximal operators of the objective functions are analyt-ical, these methods are suited. Specially, alternating direction methods are fast and efficient methods in image processing, signal recovery and so on. However, these methods may be im-possible when the proximal operator is not available. The subject of this dissertation is study on alternating linearization algorithm for solving these nonsmooth optimizations including that the analytic proximal operator of each objective function is not existed. The main results may be summarized as follows:1. Chapter2presents an inexact approximate alternating linearization numerical algo-rithms for solving the sum of two convex functions. Alternating linearization algorithm for nonsmooth optimization involves solving two strongly convex subprograms and when the opti-mal solution can’t be obtained the algorithm fails. We take approximate solutions instead and prove that the approximate algorithm converge to a solution of the original problem.2. In Chapter3we construct an alternating linearization algorithm for nonsmooth convex optimization to solve a class of bilevel programming problem. Firstly with the help of penalty function the bilevel programming is converted to a general one level optimization problem which the objective function is the sum of two convex functions. Convergence analysis and numerical experiments validate the efficiency of the algorithm.3. Chapter4consider a nonsmooth optimization problem with smooth substructure whose objective is the sum of a convex function and a continuously differentiable function. We design a new algorithm for solving this class of optimization problem. We make convergence analysis and carry out some numerical tests to verify the implementation of the algorithm.4. Chapter5consider minimizing a summation of two nonconvex nonsmooth functions. Based on the structure of the objective function, the original problem is exploded into an alter-nate generation of two models, each one being characterized by the linearization of one of the convexified functions. We also discuss the convergence properties of the method to a stationary point and carry out some numerical results of its implementation.