本文選題：約束優(yōu)化 + 增廣拉格朗日函數(shù)��； 參考：《湖南大學(xué)》2016年博士論文

【摘要】：求解約束最優(yōu)化問題的增廣拉格朗日法,也就是最初的乘子法,以及與之相關(guān)的交替方向乘子法,在最近幾年里受到了較為廣泛的認(rèn)可和重視。這不僅僅是因?yàn)樗鼈冊谇蠼庖恍﹣碜杂诋a(chǎn)業(yè)及工程中的實(shí)際問題時(shí)所表現(xiàn)出來的適用性,也因?yàn)橐运鼈優(yōu)榛A(chǔ)的一些實(shí)用算法具有相當(dāng)高的效率。經(jīng)典的增廣拉格朗日法以及經(jīng)典的交替方向乘子法的產(chǎn)生已經(jīng)過去了40多年,相關(guān)的工作也逐漸地被完善。但即便如此,作為增廣拉格朗日法和交替方向乘子法的核心組成部分的增廣拉格朗日函數(shù)所蘊(yùn)含的創(chuàng)造優(yōu)秀的算法的潛力至今還未被完全的發(fā)掘。因此,本篇博士論文致力于研究一些求解約束最優(yōu)化問題的基于增廣拉格朗日函數(shù)的方法的算法設(shè)計(jì),理論分析以及數(shù)值試驗(yàn)。首先,本文提出一種二階的增廣拉格朗日函數(shù)法,用于求解帶等式和不等式約束的非線性規(guī)劃問題、非線性二階錐規(guī)劃問題以及非線性半定規(guī)劃問題。在該方法中,本文引入一種特殊設(shè)計(jì)的廣義牛頓法來解決問題中約束所導(dǎo)致的非光滑性,從而產(chǎn)生二階的乘子更新步。緊接著,本文給出該方法的相關(guān)理論分析。本文的結(jié)論表明在約束非退化(或線性獨(dú)立約束品性)和強(qiáng)二階充分條件成立的情況下,本文中設(shè)計(jì)的方法對(duì)于本文所考慮的幾類問題是局部收斂的,并具有超線性的收斂速度。此外,這些結(jié)論是在懲罰參數(shù)固定和嚴(yán)格互補(bǔ)條件不一定成立的情況下成立的。其次,本文給出了一種非精確的多塊交替方向乘子法類型的一階算法,用于求解一類高維數(shù)多塊合成的凸錐規(guī)劃問題。該方法的設(shè)計(jì)結(jié)合了一種非精確的兩塊Majorized半鄰近交替方向乘子法以及用來求解多塊的且目標(biāo)函數(shù)中僅關(guān)于第一塊變量的部分包含一個(gè)非光滑函數(shù)的凸合成二次規(guī)劃的非精確對(duì)稱高斯賽德爾迭代的最新進(jìn)展。該方法的最大的特點(diǎn)是它在求解每一個(gè)相關(guān)的子問題的時(shí)候僅僅需要一圈非精確的對(duì)稱高斯賽德爾迭代。在一些簡單而且易行的誤差容許條件下,求解每一個(gè)子問題的時(shí)間將會(huì)大大的縮短。除此以外,對(duì)稱高斯賽德爾迭代中的很多向前迭代經(jīng)�？梢允÷缘�,這更加增強(qiáng)了算法的執(zhí)行效率。本文對(duì)所提出算法的全局收斂性和非遍歷的迭代復(fù)雜度進(jìn)行了分析。接著,本文使用該方法求解了一些大規(guī)模的帶有大量等式和不等式約束線性和二次凸半定規(guī)劃問題。數(shù)值試驗(yàn)的結(jié)果表明該方法在求解大部分測試問題時(shí)候所耗的時(shí)間與步長為1:618的直接推廣的多塊交替方向乘子法相比,能夠節(jié)約百分之五十至百分之七十。所需強(qiáng)調(diào)的是,盡管直接推廣的多塊交替方向乘子法的收斂性是未知的,它在當(dāng)前仍是求解多塊線性和二次凸半定規(guī)劃問題的一階算法的一個(gè)基準(zhǔn)。再次,本文澄清了人們對(duì)交替方向乘子法收斂性質(zhì)的一些誤解。本文中構(gòu)造了一個(gè)反例表明一篇非常有影響力的文章中的關(guān)于交替方向乘子法的收斂性的結(jié)論在沒有預(yù)先假設(shè)子問題的解存在的情況下是不正確的。鑒于這種情況,本文給出了相當(dāng)弱的充分條件來保證每個(gè)子問題的解的存在性。緊接著,本文在一種更廣的算法框架,也就是半鄰近交替方向乘子算法中,通過嚴(yán)格分析給出了一些交替方向乘子法的收斂性質(zhì)。此外,本文還并提出一個(gè)使用起來非常簡單且不增加運(yùn)算量的充分條件,使得在數(shù)值計(jì)算中能夠讓步長大于黃金分割率1:618,進(jìn)而加強(qiáng)算法的數(shù)值表現(xiàn)。最后,本文給出了一種求解兩塊的線性約束凸優(yōu)化問題的廣義半鄰近交替方向乘子法的收斂性分析。該方在一種非常自然的方式下同時(shí)在區(qū)間(0;2)中松弛了原始和對(duì)偶的變量,從而有著提高經(jīng)典交替方向乘子法的計(jì)算效率的可能性。更重要的是,該方法能夠通過對(duì)稱高斯賽德爾迭代等技術(shù)來選取合適的半鄰近項(xiàng),從而可以用來求解多塊的合成凸優(yōu)化問題。通過求解420個(gè)雙非負(fù)半定規(guī)劃問題的數(shù)值結(jié)果表明,本文所提出的該方法是可行的,而且本文引進(jìn)的松弛步能夠提高算法的效率。
[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.

【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O221.2

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 Ya Xiang YUAN;;Analysis on a Superlinearly Convergent Augmented Lagrangian Method[J];Acta Mathematica Sinica;2014年01期

，

本文編號(hào)：1862527