【作者】 李丹；

【导师】 夏尊铨； 庞丽萍；

【作者基本信息】 大连理工大学 ， 运筹学与控制论， 2013， 博士

【摘要】 近年来,非光滑优化领域中的很多学者专注于通过探索目标函数的具体结构来设计或者改进算法.交替线性化算法就是基于这种思想根据目标函数为两个函数和的结构所设计的一种近似迫近点算法.在现实中很多实际问题都可以转化为极小化两个函数和的优化问题,例如最优控制、图像处理、信号恢复、网络推荐系统、计算机视觉、系统辨识、生物信息统计等等.因此,研究这类求解两个函数和问题的算法,同时具有理论意义与实用价值.目前,求解两个函数和的非光滑优化方法主要有算子分裂法与交替方向法.这两类算法非常适于求解当目标函数中的非光滑函数的迫近算子具有解析形式时.特别地,交替方向法成为求解图像处理、压缩感知等实际问题的快速高效算法.然而,当非光滑函数的迫近算子不具备解析形式时,这些算法在实际计算中很难实现.本文所研究的求解这类非光滑问题的交替线性化算法,同时考虑了求解这种形式的非光滑问题.论文所阐述的主要结果可概括如下：1.第二章研究求解两个非光滑凸函数和的非精确交替线性化数值算法.交替线性化算法每次迭代都需要精确求解两个强凸子问题,由于某些情况下不能精确求解,故算法不能执行.我们采用近似最优解代替,并能证明在某些条件下,通过交替求解的近似解收敛到原问题的最优解.2.第三章考虑求解一类双层凸规划问题的交替线性化算法.基于精确罚函数的思想将双层规划问题转化为一般的单层优化问题,转化后的优化问题的目标函数为两个凸函数的和,可以直接构造交替线性化算法求解,通过收敛性分析和数值试验可以验证算法的有效性.3.第四章求解一类具有光滑结构的凸函数和的交替线性化算法,本章针对问题的具体结构基于交替线性化算法的基本思想通过构造新的子问题的模型改进算法,并进行收敛性分析与数值试验,验证了算法的可执行性.4.第五章求解极小化两个非凸非光滑函数和的交替线性化算法.根据目标函数的性质和结构,将原问题转化为两个子问题,每个子问题的形式是将其中一个凸化后的函数线性化,然后交替求解.我们同时讨论了算法收敛到原问题的一个稳定点并进行了基本的数值试验.更多还原

【Abstract】 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.更多还原