【《一种仿射内点信赖域算法来求解带界约束的非线性优化问题分析》3100字】

一种仿射内点信赖域算法来求解带界约束的非线性优化问题分析目录TOC\o"1-3"\h\u28643一种仿射内点信赖域算法来求解带界约束的非线性优化问题分析 1121931.1预备知识 1261851.2界约束优化问题的仿射内点信赖域算法 2314541.3算法收敛性分析 612541.4数值实验 131.1预备知识界约束优化问题在约束优化问题中是比较容易处理的一类问题，在现实的生产生活中有着极其广泛的应用。如此说来，研究非线性界约束优化问题对于科学技术的发展具有重要影响。对于非线性界约束优化问题，国内外已经发展了许多理论和方法。仿射内点信赖域方法基于优化问题的KKT条件，经过选取合理的仿射变换矩阵，并由此构造信赖域子问题模型，通过解出信赖域子问题来求得非线性约束优化问题的试探步。仿射矩阵方法是由Dikin提出的，经常借此解决线性规划问题。在后来仿射矩阵方法又由Barnes和Vanderber等进行了深入研究。在二十世纪末期，Dikin引入了用来解决二阶凸问题的仿射矩阵方法，构造出了一个椭球，此椭球以当前迭代点为中心,轴长与包含在可行域里最大的椭球的轴长成常数比例，在椭球上求目标函数的最小来求解下一个迭代点。通常情况下，仿射变换内点算法考虑以下界约束问题.若是以上问题的最优解，那么3-(1)内点仿射变换算法的一阶必要条件在满足某种条件下可写作如下非线性系统.其中，是仿射尺度矩阵。定理1.1满足一阶最优性条件3-(1)当且仅当是非线性系统.的一个解。其中，许多文献研究了凸规划仿射变换内点算法的收敛性。在仿射变换矩阵的构造过程中，我们让变量和边界的距离作为矩阵选取的参考因素，另外还取决当前迭代点信赖域半径。对于为何要加入信赖域半径的影响，是因为信赖域可以自适应变化，在算法收敛性以及处理效果方面有一定的帮助。Fletcher和Leyffer为了保证算法的全局收敛性，引入了滤子方法。滤子方法是一种代替价值函数的方法，可以作为保证非线性规划算法收敛的工具。LiandZhu提出了在线搜索滤子技术基础上的仿射内点信赖域方法来求带界约束的非线性优化问题。Andreas和Lorenz给出了一种基于线搜索的过滤方法框架，该框架既可以应用于障碍函数方法，也可以应用于SQP方法。1.2界约束优化问题的仿射内点信赖域算法带有等式约束的界约束优化问题是我们在这一章要研究的内容3-(2)其中是连续可微实值函数，向量，，且。另外是可行集，其内点可行集可以表示为.问题3-(2)的拉格朗日函数为.假设为问题3-(2)的极小点，则肯定存在满足KKT条件上式等价于.3-(3)其中，是对角仿射矩阵，它的对角元素被定义为.3-(4)其中，其中是一个常量。假设第次迭代时，用牛顿法求解问题3-(3)，则迭代步满足3-(5)其中3-(6)且变换其形式可以写作3-(7)定义二次模型其中，。定义信赖域子问题为3-(8)我们令考虑一个回代线搜索过程，在这个过程中尝试步长递减的序列，直到满足某个接受条件，对应的迭代点为其中是当前迭代点，是搜索方向。为了避免经典的价值函数的使用，我们用滤子方法来代替，我们令使用的约束违反度函数为。定义1.1称点支配点，当且仅当且。定义1.2滤子就是具有形式的列表，记为，使得或对所有成立。接下来我们就确定迭代点是否合适的标准。实际来说，若点的对应函数对的值和对应的值很近似，那它则会被过滤掉。也就是说在平面上，对那些不被滤子接受的点所处在的地方建造了边界。所以被滤子接受试探点，当且仅当满足3-(9)或3-(10)成立。其中，。此外，滤子集合是逐渐变化的，假设第次迭代时的滤子集合用来表示。迭代过程在不断进行，需要把点对放进滤子里，若可以被当前滤子所接受，则记，并且3-(11)相似于文献中的滤子更新方式，我们定义3-(12)下面我们给出我们的仿射内点信赖域算法。算法1.1（仿射内点信赖域算法）步0选取初始点，信赖域半径，最大信赖域半径，常量。步1初始化滤子集合，定义。步2如果，则停止迭代。步3计算内点信赖域子问题3-(8)，得到搜索方向。步4回代线搜索4.1设，。4.2计算。4.3测试迭代点是否被滤子接受，如果不被接受，则拒绝这个迭代步长，转步4.5。4.4如果3-(9)和3-(10)成立，接受这个迭代步，转步5，否则转步4.5。4.5选择新的迭代步长，，令。返回步4.2.步5保证内点，设，则。步6如果3-(9)和3-(10)都不被满足，则更新滤子；否则令。步7更新信赖域半径，计算,,.令步8令，转步2.备注1在3-(10)和3-(11)中被给出，其中.3-(13)其中，，和是向量，，和的第个分量。1.3算法收敛性分析在滤子迭代过程中，我们定义集合，给定，算法产生的序列，在收敛性分析中，我们定义水平集通过.为了证明收敛性，我们需要做以下假设A1算法产生的序列包含在紧集中；A2是一致有界的，另外存在一个常量使得；A3迭代序列在上是有界闭集。引理1.1是子问题3-(8)解的充分必要条件是存在，使得3-(14)成立，且半正定。证明若是问题3-(8)的解，则根据一阶必要条件可以得到：存在，使得3-(14)成立。接下来只需证半正定。假定，因为是子问题的解，也就是.的解。这样对所有满足和的，均有,3-(15)因为和，可得把以上两式代入3-(14)并整理可得3-(16)由于，可得半正定。设，，满足3-(14)，并且半正定，则对于所有的使得成立，我们有进而即证明了是子问题的解。为了估计目标函数的充分下降性，考虑子问题3-(17)其中，我们把问题3-(17)的解叫做cauchy点，然后得到以下性质引理1.2如果是子问题的解，则存在常数使得3-(18)3-(19)证明设，则有3-(20)由假设A2，存在，使得，对所有成立。因为，所以当时，有又根据我们有3-(21)因为，当有3-(21)成立，令3-(22)设，有所以cauchy点为3-(23)如果，则3-(24)如果，当，3-(25)当，有因为3-(26)和3-(27)所以其中如果和有如果，有所以引理1.3假设A1，A2，A3成立，过滤集经过有限次扩充，优化问题3-(2)的严格互补性成立，则有3-(28)证明：因为，所以存在使得对所有的，在第次迭代中过滤集不扩充，所以当时，我们有3-(9)和3-(10)成立。如果对于足够大的有3-(9)成立，我们有使得对于，这意味着3-(28)成立。同样，如果对于足够大的有3-(10)成立3-(29)如果，我们有和。通过3-(13)，对所有的有所以我们知道当且单调递减有下界时，3-(28)成立。引理1.4假定A1，A2，A3成立，滤子集合扩充了无限次，在的极限点处成立，问题3-(2)的严格互补性成立，则3-(30)证明：反证法。假设有的无限序列和正指标使对所有对某一个。假设保证对所有的，和其中，，和是常数。所以，和过滤集相关的包含在如下区域内：非常明显，是有限的。在第次迭代后，被添加进滤子集合中，即在区域里，此后就没有别的添加进滤子集合中。每一个区域面积至少是。下面分情况讨论。若有无限序列使当时，，则当时，至多被有限个这样的区域所覆盖，这与是无限序列矛盾。否则，当时，，我们已知。类似于文献的引理1.8的证明，我们可以知道趋于零。故，因此，存在正指标使得对所有这与矛盾。所以3-(30)成立。由以上收敛性证明可以得到下面定理。定理1.1假设A1，A2，A3成立，问题3-(2)的严格互补性在的每一个极限点出成立，有1.4数值实验在这一节中，我们应用所提出的仿射内点信赖域方法来解决带界约束的等式约束优化问题。我们的程序代码是运行在Matlab2014a中。算法1.1中的所有参数在代码中选取如下:，，，，，算例的数值结果如下表所示。表中标准测试问题引用自文章中。例如，HS6表示Hock和Schittkowski中的第6个，S112表示Schittkowski中的第112个。文章中提出了一种无惩罚型非单调信赖域算法，在下表中，我们称之为算法1。我们将该算法与我们的算法进行了比较。实验结果表明，我们的算法迭代次数比其算法少。表1.1算例算法2.1算法1变量个数迭代次数误差迭代次数2883731329388351027927193816245接下来，我们对Rockbrock函数进行测试，算例的数值结果如下表所示。例目标函数为