【《一种内点信赖域方法用于求解可分离约束问题分析》2500字】

一种内点信赖域方法用于求解可分离约束问题分析目录TOC\o"1-3"\h\u29871一种内点信赖域方法用于求解可分离约束问题分析 1128061.1预备知识 1323531.2交替结构的内点信赖域算法 2245411.3算法收敛性证明 71.1预备知识本章考虑的可分离优化问题如下：2-(1)其中和是二次连续可微实值光滑函数，是一般约束，集合为闭集。问题2-(1)在图像处理，机器学习，交通规划等领域有着极其广泛的应用，为解决该类问题算法的研究提供了广阔的应用空间，也激起了广大最优化研究者对问题2-(1)设计算法的浓厚兴趣。当是凸函数时，已经有了比较成熟的理论分析。在这些方法中，交替方向法是解决非线性可分离约束优化问题的有效算法。交替方向法在机器学习和图像制作等诸多方面有着广泛的应用。实际上,交替方向法在这些领域具有良好的数值性能,是因为交替方向法的子问题有其自身的特点。交替方向法的起源最早是由Gabay、Mercher和Glowinski在20世纪70年代提出的，类似的思想起源于20世纪50年代。很多文章对这种方法进行了深入的研究，但之前交替方向法主要用来处理偏微分方程问题，目前交替方向法则主要用于求解变量可分离的凸优化问题2-(2)优化问题中，为凸函数，，。模型问题2-(2)的增广Lagrange函数为，2-(3)其中Lagrange乘子，罚参数。增广Lagrange算法极小化问题2-(3)的迭代公式满足经典增广Lagrange算法将问题2-(2)看作是一般的极小化问题，没有考虑它的变量可分离形式。经典增广Lagrange算法同时极小化增广Lagrange函数2-(3)中的变量和，而交替方向法则不同，它从目标函数的变量可分离形式出发，对变量和求极小，迭代过程为其中初始变量和可随意选取。新的信号采样理论—压缩感知在二十一世纪初期由Candes等人提出，交替方向法重新焕发了活力。然而交替方向法目前主要用于解决凸问题，对于非凸问题的研究较少，所以本章打算对模型问题2-(1)中当目标函数对凸性没有要求时进行研究。1.2交替结构的内点信赖域算法目标函数定义为，函数的第次迭代，定义模型为，假设是可行域，。这个模型既包含在可行域中，又包含在信赖域里。其中，，，，是信赖域半径。我们考虑如下二次模型其中，是试探步，，，是的海塞阵或其近似，所以可以看作。类似于经典的内点法，我们考虑了对数障碍问题2-(4)其中是障碍参数，为松弛变量。下面我们就可以导出松弛变量的表达式。首先，我们定义对数障碍问题的拉格朗日函数2-(5)其中是正纯量，是向量。通过的最优性条件，可以导出松弛变量的表达式2-(6)如果我们令，我们有2-(7)接下来，对数障碍问题的等价系统被提出，这个等价系统的解近似于原优化问题的KKT解，对数障碍问题的等价系统可以写成以下形式2-(8)交替方向法被用来处理拉格朗日函数模型中的迭代变量和，然后内点信赖域子问题被提出，可以用来求解迭代步。通过求解以下两个内点信赖域子问题，我们可以得到迭代步和。子问题形式如下2-(9)2-(10)其中是Fritz-john函数关于和的海塞阵，是关于和的梯度。因此2-(11)2-(12)2-(13)2-(14)为了保证下降性，需满足以下条件2-(15)2-(16)其中，，，。以上条件在柯西点成立，然后我们有2-(17)其中，。为了检验模型函数与目标函数之间的误差，我们设然后并且内点信赖域算法在算法1.1中给出算法1.1(交替结构的内点信赖域算法)步0给出原始迭代点，选取合适的信赖域半径和，参数，和。计算，，令，，。步1若，则停止。步2通过2-(9)和2-(10)，计算迭代步，则步3如果2-(18)则令，，，。步4我们考虑以下两种情况情况12-(19)如果2-(20)且2-(18)不成立，则如果2-(18)和2-(20)都成立，则如果2-(20)不成立但2-(21)成立，则如果2-(21)不成立，则情况22-(22)如果2-(23)且2-(18)不成立，则如果2-(18)和2-(23)都成立，则如果2-(23)不成立，则令，转步1.另外，对于常数我们有以下限制，，.特别的，我们令1.3算法收敛性证明在这一章节中，我们需要证明算法1.1生成的迭代序列是收敛的。为了证明收敛性，我们需要做出以下假设。A1目标函数在开集上连续可微；A2迭代序列为有界开集；A3存在一个常量，对所有的，有A4序列是有界的，对所有的，有2-(24)引理3.1假设A1，A2和A4成立，对给定的和，序列满足等价系统2-(8)。证明对于2-(8)，我们使用牛顿等式有2-(25)信赖域内点子问题的KKT条件可以写成如下形式2-(26)2-(27)其中是乘子，，由等式2-(27)，我们可以得到，将代入等式2-(26)可以得到一阶等式系统2-(25)，根据文献的定理3.1，我们知道信赖域子问题有唯一解，这个解也是等价系统2-(25)的解。因为两个变量的证明几乎是一样的，所以我们只证明变量。引理3.2假设A1-A4成立，对于算法的迭代序列，存在一个正常数，使得2-(28)2-(29)证明因为对于两个变量的证明方式是相同的，所以我们仅证明首个不等式。由泰勒展开，我们有2-(30)又因为，和的定义，我们有2-(31)其中。因为，令，则不等式成立。引理3.3假设A1-A4都成立，若存在一个常数，使，存在一个常数，使得证明此项引理的证明和文章中引理3.3证明类似。引理3.4假设A1-A4都成立，则，对于，有2-(32)且2-(33)证明通过2-(17)我们有因此，我们能得到不等式和2-(33)。引理3.5假设A1-A4都成立，2-(34)然后有2-(35)证明由引理3.2,3.3和3.4，以及如果2-(17)式成立，我们有如果我们得到。通过上述引理证明，我们可以得到以下结果定理1.1假设A1-A4都成立，对于算法产生的所有迭代序列，我们有（1）和收敛，极限满足问题的约束条件；（2）收敛到目标函数的最优值；定理1.2假设A1-A4和2-(17)都成立，是由算法产生的迭代序列，我们令并且满足以下条件2-(36)其中，存在一个子序列使得，且是原优化问题2-(1)的最优解。证明由定理1.1可知，对于子序列，我们有2-(37)通过2-(36)可知因此所以结论可由和的连续性得出。1.4数值实验在这一部分中，我们应用所提出的信赖域内点算法来解决凸、非凸问题和随机优化问题。我们的程序代码是运行在Matlab2014a。在算法中，初始点的选取是可行域内的任意点。算法1.1中的所有参数在代码中选取如下:，，，，，，，，，，.例1第一个是凸优化问题，目标函数为多项式函数和.约束函数为.表1.1初始点时间（s）迭代次数误差0.07750.10860.05340.0845例2第二个是线性约束可分问题，这个问题参考于，目标函数为和.约束函数为.表1.2初始点时间(s)迭代次数误差,0.1432,0.1002,0.59260.17440.4834例3第三个是线性约束可分问题，目标函数为和约束函数为.表1.3初始点时间(s)迭代次数误差0.08730.12150.09630.0833例4第四个是非线性约束的可分问题，目标函数为和约束