15非线性约束最优化算法

本文框架最优化算法分类不等式约束组合变量消除优化函数和滤波马洛托斯现象二次校正和非单调方法15.1最优化算法分类非线性最优化算法没有分类标准；对后面章节各种逼近做了分组，如下所述：I.第16章，讨论二次线性规划（quadraticprogramming）求解问题的算法，它具有独特的性能。对有效集(activeset)，内点法(interior-point)和梯度投影法(gradientprojectionmethods)进行讨论。II.第17章,讨论罚函数(penalty)和增广拉格朗日(augmentedLagrangianmethods)方法，把目标函数和条件都结合归到罚函数里边，这样可以通过求解一系列非约束条件处理15.1问题。15.11罚函数和增广朗格朗日方法假如(15.1)中只有等式约束条件存在，那么二次罚函数定义：)(21)(2xCxfii等式约束问题，定义：iixxfc)()(结合拉格朗日函数性质和二次罚函数（15.2）函数增广拉格朗日函数:iiiiiAxcxcxfxL)(2)()();,(215.12连续二次规划方法第18章，讨论序列二次规划方法（sequentialquadraticprogramming）简称SQP.基本的SQP方法中定义Pk在(xk，λk)迭代的方向，从而得到解约束条件：pkPkkxfxLPTxxTp)(),(221minIikTkiikTkixcpxcxcpxcii,0,0)()()()(15.13非线性规划内点法第19章，讨论非线性规划内点法（interior-point）相对在14章讨论的线性规划来说，这种方法可以看做是原始对偶内点法（primal-dualinterior-point）的拓展，也可以看做是障碍法。约束条件：miisxsxflog)(min.Iisxcixciii,0)(,0)(15.2不等式约束组合求解非线性规划最主要的难题是处理不等式约束，特别是在解中确定哪些约束条件是有效的。估测一个最优有效集A*，这是一组约束条件，在解处满足等式。这估测值叫做作用集，用w表示。在作用域约束条件强制为等式，约束条件在w处忽略，然后求解。最后验证是否有一个拉格朗日乘数，得到近似解X*，且W满足KKT条件（12.34）。这样把这X*看做（15.1）的局部解。例子：即使小数量的不等式约束，确定最优化有效集不是一个简单的任务。问题：约束条件：22,)2(21)2(21),(minyxyxfdefyx00041)1(1yxyx15.21W的八种可能选择用在下面的描述的作用作用域：按指数1到3有序标记，图15.1阐述了目标函数的形态，可行域是两轴和曲线包围的区域。可以看出在解中只有第一个约束条件有效，（x*，y*）=(1.953，0.089)τ即使对这个小的例子，考虑所有w可能的值很麻烦，图15.1表明，可以利用定义这个问题和他们的派生的函数知识消除，事实上在16章描述的有效集方法利用这种信息来进行一系列有根据的猜测作用域，避免w选择的明显偏离15.1的解。既内点法（障碍法）之后，一种不同的方法在19章考虑，这种方法生成的迭代远离通过不等式约束条件定义的可行定义域的边界，作为非线性规划的解释近似的阻碍作用被消弱，允许精度增加解的估计，在这种方法中避免了非线性规划组合的难题。第一种可能：求解方案中任何约束条件无效，也就是说w=Φ，由于▽f=(x-2，y-1/2)T，可以看到无约束f最小值在可行域外边，所以最优化有效集不能为空。有7种另外可能，其中三个约束条件是有效的，w={1，2，3}，图（15.1）对这个问题这样的情况没有发生，三个约束条件不共享一个相同的交叉点。通过单一的有效约束条件，得到三个更进一步的可能，那就是是{w=1}，{w=2}，{w=3}{W=2}，只有x=0的约束条件有效，如果在这种条件下使f执行最小化，得到（0，1、2）T这个点，检查（12.34）KKT条件，表明无论选择什么拉格朗日乘数，都不能满足在0，1、2）T的条件。（因为必须要λ1=λ3=0满足（13.34e）），通过这表明，设λ2=-2满足（12.34a），但是λ2的值不满足(12.34d)。{W=1，3}，得到单一的可行点（3，0）T，由于约束条件2在这个点无效，令λ2=0，解决（12.34a）用其他朗格朗日乘数，得到λ1=-16，λ3=16.5。，这些值是负数，不满足（12.34）所以（3，0）T不是（15.1）的解。{W=1}，求解等式约束条件问题，这问题中第一个约束条件是有效的，得到点（x，y）T=(1.953，0.089)T和拉格朗日乘数λ1=0.411。通过设定λ2=λ3=0，很容易得到，（12.34）的KKT其他条件是满足。于是得结论这个点是KKT点，由于拉格朗日的Hessian正定，很容易得到二阶充分条件满足。15.3变量消除处理约束最优化问题，用边界条件消除问题中的变量是正常的，用更少的自由度得到一个简单问题。然而由于消除法可能改变问题或者引入病态条件必须小心使用I.目标函数：I.约束条件：I.得到两个变量的函数：),,,()(min4321xxxxfxf00234234231xxxxxxx234223341,xxxxxxx),(),(234233443xxxxxfxxh15.31非线性消除的缺点22minyx23)1(yx问题思考：约束条件：通过消除y求解，得到下面等式：32)1()(xxxh很明显，随着x趋近负无穷时，h(x)趋近负无穷。盲目应用这个转换，得到这个问题无线，但是这个问题不能忽略约束条件（x-1）3=y2，这个含蓄的表明x≧1界值，这个解是有效的。因此，如果希望消除y，必须加入x≧1这个界值。这个问题说明了用非线性消去变量，可能导致很难追踪错误的结果。基于这个原因，大多数最优化算法中不用非线性消去法。相反，许多约束条件的线性的算法会用到消去法去解一些简单问题。现在就系统的概述下用线性约束去得到变量消除的目的。15.32用线性约束简单消去思考线性函数的约束条件的最小化问题，约束条件是线性等式约束：约束条件：)(minxfbAxA是一个m×n的矩阵，m≦n。简单起见假设A是满秩（假如情况不是这种情况，得到这个问题要么矛盾，要么约束条件多余的，能删除而不影响问题的解)在这种假定下，我们可以找到线性独立矩阵Ａ的m列的一个子集。如果将这些列向量组合到一个的B矩阵，定义一个的P置换矩阵。Ｐ矩阵是将这些列与Ａ的第一个列进行交换的矩阵，表达式:NBAPN表示Ａ矩阵n-m剩余列。(这里的注释和第13章一致，讨论线性规划背景的相似概念)定义下面形式下的子向量：(15.8)xB为基变量，B为基矩阵。注意PPT=I可以将约束条件Ax=b改写如下：重排这个式子，通过下面的表达式可以减少所给的基变量：(15.9)从而，通过选择任意xN值，计算约束条件Ax=b的可行点，然后可以通过(15.9)设置xB。因此，(15.4)问题和非约束问题等价。(15.10)NBTxxPxNBTNxBxxApAxbp.11xBBxNBNb).(min11xxBBxNNdefNNbPfhxN上述讨论说明了线性等式的约束条件的非线性最优化问题是从数学观点来的，非约束问题同样，下面就讨论非约束问题15.34线性等式的非约束问题的非线性最优化思考：（15.11a）约束条件：(15.10)定义转置矩阵P得的组成从新排列，xT=(x3，x6，x1，x2，x4，x5)T，得到AP矩阵的系数:基矩阵B是对角阵，因此，很容易求取转置(15.12))2(31)sin(min64542321xxxxxx44623649686542154321xxxxxxxxxx1624243134968163xx612340496801AP替换(15.11a)中的x3，x6，问题变成如下：).4381418321(315421)sin(min5421454221,,,)64968(5421xxxxxxxxxxxxxxxx(15.13)从Ａ系数矩阵(不含有X3和X6两个变量)中选择其它两列作(15.11b)系统中消除的基础。然而，这些选择，B-1N将会变得更复杂。用高斯消元法选择一组m非独立列，在线性代数中的用语，能计算出这个矩阵的行阶梯型，选择中心轴列做为基矩阵的列。理想情况下，希望B矩阵很好分解和适定性。为了这个目的，用稀疏高斯消去算法去，保持稀疏、控制舍入误差。从(15.8)和(15.9)中可以看出在线性约束条件(15.6)中任意可行点可以被写成：(15.14)(15.15)xZYbxN.,011INZYBB　注意z有n-m线性非独立列(由于在低维中存在单位矩阵的存在)满足AZ=0因此，Z是空矩阵A的基础矩阵。加上Y和Z的列组成是一个线性非独立集。我们也可以看到是线性约束条件一个特解.换句话说，这个简单消去法说明了可行点可以作为Ax=b(15.14的第一项)的特解加上沿着约束条件(15.14的第二项)的空集(或者相切)总的概括。这(15.13)，(15.14)的关系表明特解Yb是从控制x的n-m个在０点的组成，别的部分是松弛的，直到它们满足约束条件；Yb的特解有时称作坐标松弛步长。见图15.3坐标松弛步长Yb通过选择不基矩阵B去成为A矩阵的第一列，若果选择B作为A的第二列，那么坐标松弛步长将沿着X2轴。简单消去法不费时，但是数值不稳定会产生。如果图15.3中这个可行集是由几乎平行与X1轴的一条线组成的话，沿着这个坐标轴的坐标松弛是一个比较大的数量级。计算x作为不同的大矢量，给出数值取消。在这种情况下选择沿着x2轴的特解会比较好，也就是说选择不同的基。因此，一般情况下，选择最好的基底并不是一个简单的任务。当这个基矩阵约束条件很少时，在定义过程中会引起数值错误。为了克服过分协调松弛步长的危险。我们可以定义这个特解Yb作为约束条件的最小基准步长。这种方法是现在所描述的纵多消去法中的特殊情况。15.35线性约束条件的一般消减法对(15.14)和（15.15）归类，选择矩阵Y∈Rn×m和Z∈Rn×(n-m)，具有以下性质：(15.16)这些属性表明，正如（15.15）Z的列是空矩阵A的基底。因为A有满秩，所以A[YIZ]=[AYI0]，所以AY矩阵也是非奇异矩阵，现在表示线性约束Ax=b任何形式的解，如下：(15.17)对向量XY∈Rm和xZ∈Rn-m，通过15.17的取代到约束条件Ax=b得到：因此通过非奇异矩阵，可以直接被写成下式：(15.18)通过代替表达式(15.17)，得到任意一个向量的形式:(15.19)0AZ非线性，mnRZYxYzYxxbAYAxxY)(xAYzZbYx)(1.)(1bxAYYxz∈Rn-m的任意选择满足约束条件Ax=b。因此，这个问题(15-6)可以被重新当做如下的非约束问题：(15.20)理想的，选择Y使AY尽可能的满足Ax=b条件，因为它需要对这个因式分解给出特解Y（AY）-1b。用一个AT的QR因式分解来计算Y和Z，AT有如下形式为：(15.21)[Q1Q2]是正交矩阵。子矩阵Q1和Q2有正交列，它们分别为n×m和n×(n-m)，而R是n×m的上三角矩阵和非奇异矩阵，是一个m×m矩阵。（在附录(A.54)详细的讨论。）做如下定义：(15.22)因此，Y和Z的形式是Rn的一个正交基矩阵。假如我们将(15.20)展开并做一部分从排列，我们可以得到:).(min1xAYzZbYfxz,021