几类基于增广拉格朗日函数的求解约束优化问题的方法

发布时间：2018-05-08 18:30

本文选题：约束优化 + 增广拉格朗日函数　；参考：《湖南大学》2016年博士论文

【摘要】：求解约束最优化问题的增广拉格朗日法,也就是最初的乘子法,以及与之相关的交替方向乘子法,在最近几年里受到了较为广泛的认可和重视。这不仅仅是因为它们在求解一些来自于产业及工程中的实际问题时所表现出来的适用性,也因为以它们为基础的一些实用算法具有相当高的效率。经典的增广拉格朗日法以及经典的交替方向乘子法的产生已经过去了40多年,相关的工作也逐渐地被完善。但即便如此,作为增广拉格朗日法和交替方向乘子法的核心组成部分的增广拉格朗日函数所蕴含的创造优秀的算法的潜力至今还未被完全的发掘。因此,本篇博士论文致力于研究一些求解约束最优化问题的基于增广拉格朗日函数的方法的算法设计,理论分析以及数值试验。首先,本文提出一种二阶的增广拉格朗日函数法,用于求解带等式和不等式约束的非线性规划问题、非线性二阶锥规划问题以及非线性半定规划问题。在该方法中,本文引入一种特殊设计的广义牛顿法来解决问题中约束所导致的非光滑性,从而产生二阶的乘子更新步。紧接着,本文给出该方法的相关理论分析。本文的结论表明在约束非退化(或线性独立约束品性)和强二阶充分条件成立的情况下,本文中设计的方法对于本文所考虑的几类问题是局部收敛的,并具有超线性的收敛速度。此外,这些结论是在惩罚参数固定和严格互补条件不一定成立的情况下成立的。其次,本文给出了一种非精确的多块交替方向乘子法类型的一阶算法,用于求解一类高维数多块合成的凸锥规划问题。该方法的设计结合了一种非精确的两块Majorized半邻近交替方向乘子法以及用来求解多块的且目标函数中仅关于第一块变量的部分包含一个非光滑函数的凸合成二次规划的非精确对称高斯赛德尔迭代的最新进展。该方法的最大的特点是它在求解每一个相关的子问题的时候仅仅需要一圈非精确的对称高斯赛德尔迭代。在一些简单而且易行的误差容许条件下,求解每一个子问题的时间将会大大的缩短。除此以外,对称高斯赛德尔迭代中的很多向前迭代经常可以省略掉,这更加增强了算法的执行效率。本文对所提出算法的全局收敛性和非遍历的迭代复杂度进行了分析。接着,本文使用该方法求解了一些大规模的带有大量等式和不等式约束线性和二次凸半定规划问题。数值试验的结果表明该方法在求解大部分测试问题时候所耗的时间与步长为1:618的直接推广的多块交替方向乘子法相比,能够节约百分之五十至百分之七十。所需强调的是,尽管直接推广的多块交替方向乘子法的收敛性是未知的,它在当前仍是求解多块线性和二次凸半定规划问题的一阶算法的一个基准。再次,本文澄清了人们对交替方向乘子法收敛性质的一些误解。本文中构造了一个反例表明一篇非常有影响力的文章中的关于交替方向乘子法的收敛性的结论在没有预先假设子问题的解存在的情况下是不正确的。鉴于这种情况,本文给出了相当弱的充分条件来保证每个子问题的解的存在性。紧接着,本文在一种更广的算法框架,也就是半邻近交替方向乘子算法中,通过严格分析给出了一些交替方向乘子法的收敛性质。此外,本文还并提出一个使用起来非常简单且不增加运算量的充分条件,使得在数值计算中能够让步长大于黄金分割率1:618,进而加强算法的数值表现。最后,本文给出了一种求解两块的线性约束凸优化问题的广义半邻近交替方向乘子法的收敛性分析。该方在一种非常自然的方式下同时在区间(0;2)中松弛了原始和对偶的变量,从而有着提高经典交替方向乘子法的计算效率的可能性。更重要的是,该方法能够通过对称高斯赛德尔迭代等技术来选取合适的半邻近项,从而可以用来求解多块的合成凸优化问题。通过求解420个双非负半定规划问题的数值结果表明,本文所提出的该方法是可行的,而且本文引进的松弛步能够提高算法的效率。
[Abstract]:The augmented Lagrange method for solving constrained optimization problems, that is, the initial multiplier method and the alternating direction multiplier, has been widely recognized and valued in the last few years, not only because of their applicability in solving practical problems from industry and engineering. Because some of the practical algorithms based on them are quite efficient. The classical augmented Lagrange method and the classical alternating direction multiplier have been produced for more than 40 years, and the related work has been gradually improved. Even so, it is the core component of the augmented Lagrange and alternating direction multiplier method. The potential of the augmented Lagrange function to create an excellent algorithm has not yet been fully explored. Therefore, this thesis is devoted to the study of the algorithm design, theoretical analysis and number test of the method based on the augmented Lagrange function for solving constrained optimization problems. First, a two order augmentation is proposed. The Lagrange function method is used to solve nonlinear programming problems with equality and inequality constraints, nonlinear two order cone programming and nonlinear semidefinite programming problems. In this method, a specially designed generalized Newton method is introduced to solve the non smoothness caused by the constraints in the problem, thus generating the two order multiplier update step. Then, this paper gives a theoretical analysis of the method. The conclusion of this paper shows that the methods designed in this paper are locally convergent and have a superlinear convergence rate in the case of the constraint non degenerate (or linear independent constraint character) and strong two order sufficient conditions. It is established under the condition that the penalty parameter is fixed and the strict complementarity condition is not necessarily established. Secondly, this paper gives a first order algorithm of the non exact multi block alternating direction multiplier type, which is used to solve a class of convex cone programming problem with high dimensional multiblock synthesis. The design of this method combines a kind of inexact two block Majorized half neighbor. The latest progress in the near alternating direction multiplier method and the inexact symmetric Gauss Seidel iteration of a convex synthetic two programming with a non smooth function in the target function which is only about the first block of variables in the objective function is the latest progress. The greatest feature of this method is that it only needs to solve every related subproblem. A circle of inexact symmetric Gauss Seidel iteration. Under some simple and easy error admissible conditions, the time to solve each subproblem will be greatly shortened. In addition, many forward iterations in the symmetric Gauss Seidel iteration can often be omitted, which enhances the efficiency of the algorithm. The global convergence and the non ergodic iterative complexity of the algorithm are analyzed. Then, this method is used to solve a number of large-scale linear and two convex semidefinite programming problems with a large number of equality and inequality constraints. The results of numerical experiments show that the time and step of the method are 1: when solving most of the test problems. Compared with the multi block alternating direction multiplier method of 618 direct extension, it can save fifty percent to seventy percent. It should be emphasized that, although the convergence of the multiple alternating direction multiplier method is unknown, it is still a benchmark for the first order algorithm for solving multiple linear and two convex semidefinite programming problems. This paper clarifies some misunderstanding of the convergent properties of the alternating direction multiplier method. In this paper, a counter example is constructed to show that the conclusion on the convergence of the alternating direction multiplier method in a very influential article is not correct without the existence of a presupposed subproblem. A fairly weak sufficient condition is used to guarantee the existence of the solution of each subproblem. Then, in this paper, the convergence properties of some alternate directional multipliers are given in a more extensive algorithm framework, that is, semi adjacent alternating direction multiplier algorithm. The sufficient condition of the amount of operation makes it possible to make the step size larger than the golden rate 1:618 in the numerical calculation, and then strengthen the numerical performance of the algorithm. Finally, this paper gives a convergence analysis of the generalized semi adjacent alternating direction multiplier method for solving two block linear constrained convex optimization problems. In the interval (0; 2), the original and dual variables are relaxed, thus the probability of improving the computational efficiency of the classical alternating direction multiplier method is improved. More importantly, the method can be used to select the appropriate semi adjacent terms by the symmetric Gauss Seidel iteration and so on, which can be used to solve the multi block synthetic convex optimization problem. By solving 4, the method can be used to solve the problem. The numerical results of 20 double nonnegative semidefinite programming problems show that the proposed method is feasible, and the relaxation step introduced in this paper can improve the efficiency of the algorithm.

【学位授予单位】：湖南大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O221.2

【参考文献】