【作者】 陆媛；

【导师】 夏尊铨；

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

【摘要】 在过去的十年里,许多从事非光滑优化研究的学者们构造了一类函数和集合,尽管它们本身是非光滑的,然而存在某种光滑的子结构.这种结构可以被用于设计快速收敛的算法,给出计算准则,展开灵敏性分析.2000年,Lemarechal, Mifflin, Sagastizabal和Oustry对这类特殊的函数提出了vu-分解理论.其基本思想是将Rn空间分解为两个正交的子空间u和v的直和,使得原函数在u空间上的一阶近似是线性的,而其不光滑特征集中于v空间中,借助一个中间函数,u-拉格朗日函数,得到原函数在切于u的某个光滑轨道上的二阶展式.2004年,Mifflin和Sagastizabal给出了非凸函数的vu-分解理论.但是在约束问题的vu-分解方法以及vu-分解方法应用方面的研究还很初步.本文围绕上述问题展开研究,主要工作如下：1.第二章主要研究一类约束非光滑凸规划问题的超线性空间分解方法.我们假设该规划问题的目标函数是分片二阶连续可微的凸函数,约束是由光滑凸函数组成的不等式约束.运用精确罚函数,此规划问题被转化为一个无约束问题,利用无约束问题目标函数具有与vu-空间分解相关的原始对偶结构这一性质,计算出一条光滑轨道,并得到函数在其上的二阶展式.提出解决约束规划问题的vu-空间分解算法.在一定条件下证明了算法的收敛性.最后通过数值实验验证算法有效性.2.第三章主要研究非光滑凸规划问题的近似vu-分解方法.对于凸的非光滑优化问题,文献[1]给出了一个vu-空间分解算法.算法的不足之处在于每次迭代都需要计算目标函数的精确次梯度.这在实际计算中是很困难的.针对这一问题,本章引入近似u-拉格朗日函数概念并给出相关性质.提出只需要计算函数近似次梯度的近似分解算法框架.根据迫近点落在原始轨道上的理论,将近似分解算法可执行化.最后给出数值实验说明算法的有效性.3.第四章将vu-分解理论应用到二阶锥规划问题上.给出相应的vu-空间分解和原始对偶函数,并得到相应结论.提出解决二阶锥规划问题的vu-分解算法,证明了算法收敛性.最后给出数值算例说明算法的有效性.更多还原

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