下载文档原格式
满足约束条件的优化问题优化问题是指在一定的约束条件下，寻找最优解的过程。
满足约束条件的优化问题是指除了要求最优解外，还需要满足额外的约束条件。
下面我们来看一些常见的满足约束条件的优化问题。
1. 线性规划线性规划是一种常见的优化问题，它的约束条件和目标函数都是线性关系。
线性规划常常被用来解决资源分配和生产优化等问题。
例如，一个公司需要在不同的工厂生产不同的产品，而每个工厂的产能和资源有限，需要通过线性规划来确定最优的生产方案。
2. 整数规划整数规划是一种特殊的线性规划问题，其中所有变量必须是整数。
整数规划通常被用来解决分配问题、调度问题和路线规划等问题。
例如，在运输物品时，一些物品只能装载整数个，需要通过整数规划算法来确定最优的装载方案。
3. 二次规划二次规划是一种约束条件下目标函数为二次函数的优化问题。
二次规划通常被用来解决加工优化和精度控制等问题。
例如，在加工零件时，需要通过二次规划来确定加工参数，以达到最优的加工效果和精度要求。
4. 非线性规划非线性规划是一种约束条件下目标函数为非线性函数的优化问题。
非线性规划通常被用来解决生产调度、经济模型和工业设计等问题。
例如，制造企业需要通过非线性规划来确定最优的生产调度方案，以便在产品需求高峰期满足市场需求。
总之，满足约束条件的优化问题广泛应用于各个领域，它们可以通过各种算法和技术来求解，例如线性规划算法、整数规划算法、二次规划算法和非线性规划算法等。
在解决实际问题时，需要结合具体的情况和需求，选择最合适的优化算法和技术，来求解满足约束条件的最优解。
第十五章序列二次规划法第十五章序列二次规划法考察一般非线性约束最优化问题m in ( )( ) 0 , { 1 , 2 , , }s . t.( ) 0 , { 1 , 2 , , }i eei efxc x i mc x i m mEI m(15.0.1)其中 )( )), ((i xfc i E Ix ??都二阶连续可微 .序列二次规划法(Sequential Quadratic Programming，简称SQP)的基本思想是在当前迭代点 kx 处，以问题 (15.1.1)的 Lagrange 函数 ( , )Lx? 在 ( ),kkx ? 处关于变量 x 的 Taylor 二阶展开式作为目标函数，以约束条件 ( )( )i x i E Ic ??在 kx 处的 Taylor 一阶展开式作为约束条件，构造一个二次规划子问题来获得搜索方向 kd ，它可以看作是求解无约束优化问题的牛顿法(或拟牛顿法 )在约束情形下的推广 . 由于 2 ( , )kkxxLx?? 的计算量比较大且不一定正定，因此，我们一般采用拟牛顿法思想构造正定矩阵序列{}kB ，并以kB 代替 2 ( , )kkxxLx?? ，即由二次规划子问题m i n ( ) ( ) 0 ,s .t . 12() ((,) )0T k Tkk k Tik k Tiiid B d dc xd Ecxfxc x icx dIi(15.0.2)来确定下降方向 kd .在序列二次规划法中，一般采用某种精确罚函数来作为评价算法产生的迭代点 kx 趋近原问题 (15.1.1)最优解 x 的程度的价值函数 .§15.1 Lagrange-Newton 法本节考察仅有等式约束的情形m i n ( )s .t . ( ) 0 , {1 , 2 , , }i Efxc x i m??? ? (15.1.1)第十五章序列二次规划法272 最优化理论与方法 [乌力吉 ]其中 (( )), )(i xfc ix E? 均二阶连续可微 . 其 Lagrange 函数为1(( ), ) ) (miiif x cLx x????? ?. (15.1.2)由第九章可知，在一定条件下， x 是问题 (15.1.1)的局部解的必要条件是存在 m满足 K-K-T 条件1( , ) ( ) ( ) ,(, ),) ( mx i iiL x f x c cx xxL?(15.1.3)这里 12( ) , ( ) ,( ) ( , ( ) ) Tmxcc xcx xc ? ?.Lagrange-Newton 法的基本思想是利用牛顿法求解非线性方程组 (15.1.3)来得到原问题(15.1.1)的 K-K-T 点及其乘子 .§15.1.1 非线性方程组的阻尼 Newton 法我们先来讨论求解一般非线性方程组()Gx?0 (15.1.4)的 Newton 法，其中 : nnG 连续可微 .在当前迭代点 kx 处，将向量值函数 ()Gx 以其在 kx 处的 T aylor 一阶展开式近似代替，求解线性方程组) ( )( ()k k k TG x dd G x G x? ? ? ? ? 0， (15.1.5)其中 12( ) ( ( ) ( ) ( ) )k k k knG x G x G x G x? ? ? ? ??，这个方程组又称为 Newton 方程，当()Gx 的 Jacobi 矩阵 ()kTGx? 可逆时，可解得 Newton 方向1( ) )( ()k k T kG x G xd ??? ? . (15.1.6)Newton 方向 kd 是价值函数21211|| ( ) |() |22 ()imixGx G x? ?? ??(15.1.7)在点 kx 处的下降方向，这是因为§ 15.1 Lagrange-Newton 法最优化理论与方法 [乌力吉 ] 2731( ) ( ) ( ) ( ) ( )k k kmikkiix x G x G x G xG?， (15.1.8)由此得( ) ) ( ) ) ( )(( ()2k T k k T k T k k T k kx d G x d G xG x G x x??? ? ?? ? ? ?， (15.1.9)因此，当 kx 不是非线性方程组 (15.1.4)的解时，必有 ( ) 0k T kx d.求解非线性方程组的经典 Newton 法迭代格式为1k k kxx d? ??. (15.1.10)设 x 为 ()Gx?0 的解， ( )Gx? 可逆，则由 ()Gx 连续可微可知，当kx 充分靠近 x 时，)( kGx? 也可逆，且由 Von-Neumann 引理知，存在 0M? ，使得1|| ( ) ||kG x M，于是11 | | | | | | | | ( ) ) ( ) | || | (k k k k k T kx x d x x G x xx Gx??? ? ? ? ? ? ??1| | ( ) ) | | ( )( | | (( | |))k T k k T kG x G x G x x x?? ? ? ???| | ( ) | | ( | | | | | ) | | ( | | )|kkM G x o x x o x x? ? ? ??， (15.1.11)这表明非线性方程组的牛顿法具有局部超线性收敛速率，特别地，当 ()Gx? 在点 x 处局部Lipschitz 连续时，由定理 1.2.1，有1 | | | | (| | ( ) ) ( ) ( ) | |k k k T kx G x GxM x G x x x? ? ? ? ? ??2(|| || )kO x x??， (15.1.12)这时，非线性方程组的 Newton 法具有局部二阶收敛速率 .算法 15.1（非线性方程组的阻尼 Newton 法）步 1：给定初始点 0 nx?? ，参数 (0,1)?? 和 (0,1)?? ，容许误差0?? ，置 0k? ；步 2：如果 ()kx ，则算法结束，输出近似解 kx ；步 3：确定牛顿方向，从牛顿方程( ) ( )k k TG x G x d?? ? 0 (15.1.13)解出 kd ，并令 1?? ；步 4：沿 kd 进行简单后退线搜索，如果第十五章序列二次规划法274 最优化理论与方法 [乌力吉 ]( ) (1 ) ( )k k kx d x? ? ? ? ?? ? ?， (15.1.14)则令 ? ??? ，转步 4，否则令 k ；步 5：令 1k k kkx x d?? ?? ，置 1kk??，转步 2.定理 15.1.1 设 : n nG 连续可微，如果 ()kGx? 对每个 k 都可逆，且存在 0M? ，使得 1()|| ||kG x M总成立，则算法 15.1 产生的点列 {}kx 的任何聚点都是 ()Gx?0 的解 .证设x 是点列{}kx 的一个聚点，则存在无穷指标集1 {1,2, }K ? ? ，满足1limkkKk xx??? ?， (15.1.15)由于算法 15.1 是下降算法，故由数列 {( )}kx? 单调减少可知( ) ( )limk kxx???? ? . (15.1.16)由于 1()|| ||kG x M，故对每个 1k K? ，都有1 0| | | | | | | | | | | | | |( ) ) ||( ( )k k kG x G x GdM x?? ?? ?，(15.1.17)即1{}k kKd ?有界，从而存在无穷指标集 21K K? ，使得2limkkKk dd??? ?，且由 ()Gx 连续可微，有2( ) ( ) | || | l i m | | 0( ) ( ) | |T k T k kkKkddG x G x G x G x???? ? ? ???，即( ) ( )T dG x G x? ? ?. (15.1.18)再由算法 15.1 步 4 可知，1 )( ) ( ) (1 ( )k k k kkkdx x x? ? ? ? ? ?? ??? ?， (15.1.19)( ) (1 ( ))k k kkkdxx? ? ? ? ?? ??， (15.1.20)其中 ? /kk? ? ?? .下面用反证法来证明定理的结论成立 . 假设 x 不是 ()Gx?0 的解，这时 ( ) 0x? ? ，由不等式 (15.1.19)和极限 (15.1.16)，有 lim 0k k??? ?，因此，§ 15.1 Lagrange-Newton 法最优化理论与方法 [乌力吉 ] 275lim? 0kk ??? ? ， (15.1.21)由此得2( ) ( l im 2) ( ) ( ) ( ) ( )? T T Tk kK kkxx x d G x G x xd d? ? ? ???，从而对充分大的 2k K? ，都有3 (1? ?( )2 ) ( )kkdxx? ? ? ???? . (15.1.22) 由于对任意 (0,1)?? ，有22l i m ( ) l i m ? )? (kkkkk K k Kkkx d x x d? ? ? ???? ? ? ?? ? ? ?，故由 ( ) ( ) ( )Tx G x G x?? ? ? 连续以及2limkkKk dd??? ?，有)? ?| ( ) ( ( ) ( |)k k kkkdx x x xd? ? ? ? ? ?? ? ???|? ?| ( ) ( )k k k T k k Tk k k kddx dx d? ? ? ? ? ? ? ?? ? ? ???( ) ? ? ?|( ( ) )k k k k T kk k kdxx dd? ? ? ? ? ? ?? ? ?? ? ?) (|( ? )?k T kkk d d dx? ? ? ?????( || ) ( ( ) || || ||k k k k kk k kdx x dd? ? ? ? ? ? ?? ??????|| ( ) || || || )kkk ddx d? ? ?? ? ? ??2? )( )( ,kok K k? ?? ??， (15.1.23)其中 (0 ,1), (0 ,1)kk对任意 2k K? 成立，故对充分大的 2k K? ，由不等式 (15.1.20) ,(15.1.23)和 (15.1.22)，有( ) ( ) ( )k k k kkk dx x x? ? ? ? ? ?? ? ??( ) ( ) ( )kkxod x? ? ? ?? ? ??1? ? ? ?( ) ( ) ( ) ( )2k k k kx x o x? ? ? ? ? ? ?? ? ??? ?， (15.1.24)即有 ( ) ( )kxx?? ?? ，对不等式两边取极限，得第十五章序列二次规划法276 最优化理论与方法 [乌力吉 ]1) ( ) 0( x，由于 (0,1)?? ，故 ( ) 0x? ? ，但这与假设矛盾，矛盾表明假设不成立 .§15.1.2 等式约束优化问题的 Lagrange-Newton 法在本节，我们回过头来考察非线性方程组 (15.1.3)1()),(().miiif x c xcx(15.1.25)以 () mnAx 来表示约束函数 ()cx的 Jacobi 矩阵，即12 mA x c x c x c x? ? ? ? ??， (15.1.26)并记1(, ()()( ) ( ) ( , )) m ii xifGxcxcxx c x Lx? ??， (15.1.27)则 (,)Gx? 的 Jacobi 矩阵为2 ( ) ( ))( ,(, )Txx Lx AxxxG A ?? ?????? ?????O . (15.1.28)假设 A (A1) 约束函数 ()cx的 Jacobi 矩阵 ()Ax 是行满秩的；(A2) Lagrange 函数的 Hesse 矩阵 2 ( ),xxLx?? 在切平面 { | }nd Ad? ? 0? 上正定，即有2 ( |, ) 0 },{Tnxx L x dd d dd A?? ? ? ?? ? ?0 0?. (15.1.29)定理 15.1.2 如果问题 (15.1.25)满足假设 A，则 ( , )Gx?? 是可逆矩阵 .证设存在向量 nmd 满足2 ) ( )) (,,()(T xxx dAxddAxLxGx ??? ??? ? ? ? ??? ? ??? ?? ??? ?????? 00O，则由2 (), )( Txx xLx d A x d ??? ? ? 0， (15.1.30)§ 15.1 Lagrange-Newton 法最优化理论与方法 [乌力吉 ] 277()xA x d??0 ， (15.1.31)有2 (, ) ( ) ( ) xT T T Tx x x x xd d d A x d ALx xdd??? ??? ? 0，(15.1.32)这样，由等式 (15.1.31)和 (15.1.32)以及假设 (A2)可知 xd?0 ，将其代入方程等式 (15.1.30)，得()TA x d? ?0 ，而由假设 (A1)可知 ()TAx 是列满秩的，故 d??0 ，从而 ( , )Gx?? 是可逆矩阵 .记1( , ) ( , ) ( , )2 Tx G x G x? ? ? ?? .等式约束优化问题的Lagrange-Newton 法就是通过算法15.1 来求解非线性方程组(15.1.14)来得到约束问题(15.1.3)的K-K-T 点及其乘子，具体算法如下：算法 15.2（等式约束优化问题的 Lagrange-Newton 法）步 1：给定初始点 00)(, nmx ? ??? ，参数 (0,1)?? 和 (0,1)?? ，容许误差 0?? ，置 0k? ；步2：如果(),kkx? ? ?? ，则算法结束，输出近似K-K-T 点对( ),kkx ? ；步 3：确定牛顿方向，从牛顿方程2 ( , () ( ) ( )( )())k k k T k k T kxxxkkdAfdAL x x x A xx c xO 0(15.1.33)解出 , )( kkxd d? ，并令 1?? ；步 4：沿 , )( kkxd d? 进行简单后退线搜索，如果( ) ( 1 ) (,, )k k k k k kxx d d x?? ? ? ? ? ? ? ?? ? ? ?，则令 ? ??? ，转步 4，否则令 k ；步 5：令 1kkk kxx x d?? ?? ， 1kkk kd????? ?? ，置 1kk??，转步 2.这个算法的全局收敛性和局部收敛速率可由§15.1.1 中相应结论得到 .注对于包含不等式约束的优化问题第十五章序列二次规划法278 最优化理论与方法 [乌力吉 ]m in ( )( ) 0 , { 1 , 2 , , }s . t.( ) 0 , { 1 , 2 , , }i eei efxc x i mc x i m mI m我们可以考虑引入松弛变量，使其成为仅具有等式约束的优化问题2m in ( )( ) 0 , { 1 , 2 , , }s. t.( ) 0 , { 1 , 2 , , }eii eiefxc x i mc x y i m m m EI具体讨论读者自己完成 .当我们恒取 1k?? 时，算法 15.2 就变成经典 Newton 法，这时有迭代格式11,.kkkxkx x dd从而，牛顿方程 (15.1.33)可以写成2 ) ( )(,()()()k k k T kxxkkL x x xxc dAA xf? ?? ? ? ?? ? ??? ?? ? ? ???? ??O 0， (15.1.34)由此解出 kkxdd? 和 1 kkkd???? ??.另一方面，我们注意到非线性方程组 (15.1.34) 完全可以看成是二次规划问题21m in ( ) (2s . t., ) ()))( (T k k k Txxkkd f xq d d L x ddx cxA(15.1.35)的一阶必要条件，即为问题 (15.1.20)的 K-K-T 条件 .当假设 A 满足时，非线性方程组 (15.1.34)的唯一解 1)(,kkd ?? 就是凸二次规划问题(15.1.35)的最优解及其乘子 .因此，等式约束优化问题的 Lagrange-Newton 法可以理解为每次求解一个二次规划子问题来得到在当前迭代点 kx 处关于变量 x 的下降方向 kkxdd? 以及1k k kx x d? ??的乘子1k?? .这给了我们一个启示，对于约束优化问题可以通过解一系列这样的二次规划子问题来产生收敛于原问题 K-K-T 点及其 Lagrange 乘子的迭代序列 {}kx 和{}k? ，这就是序列二次规划法的思想来源 .§ 15.2 序列二次规划法最优化理论与方法 [乌力吉 ] 279§15.2 序列二次规划法本节考察一般非线性约束最优化问题m in ( )( ) 0 , { 1 , 2 , , }s . t.( ) 0 , { 1 , 2 , , }i eei ec x i mc x i m mEI m(15.2.1)其中 )( )), ((i xfc i E Ix ??都二阶连续可微 .类似于二次规划子问题(15.1.35)，我们构造一般约束问题(15.2.1)的二次规划子问题()) ( )1m in ( 0 , ,) ( ) 0 , ) 2 (s.t . (T k T kk T k iik T k d f x cdq d d Bc x i Ec d c x i Idxx(15.2.2)其中 kB 是 Lagrange 函数的 Hesse 矩阵 2 ,)( kkxxLx?? 的近似 . 二次规划问题 (15.2.2)的 K-K-T 条件为1( ) ( ) ,( ) ( ) 0 , ,( ) ( ) 0 , 0 , ( ) ( ) .( ) 0 , mkkk i iik T kiik T k k T ki i i i i if x c xx x i Ex x x x IBdc d cc d c c d c i 0(15.2.3)定理 15.2.1 如果 kd 是二次规划问题 (15.2.2)的 K-K-T 点， k? 是相应的乘子，则对于 1l?罚函数() 1|( ) ( ) | ( ) ||kcxP x f x? ? ??? ， (15.2.4)有() 110) | | ( ) | | (( () )kk mk T k k k kk i iid cxd P x d B d xd c?， (15.2.5)其中() 1| | ( ) | | | ( ) | | m i n{ 0 , ( ) } |k iii E i Ic x c x c x| ( ) | m a x{ 0 , ( ) }iii E i Ic x c x????? ?? . (15.2.6) 证对任意 , nyz?? ， [0,1]?? ，有第十五章序列二次规划法280 最优化理论与方法 [乌力吉 ]() 11| | [ ( 1 | m i n{ 0 , ( 1 } |) ] | | )nii iy z y z? ? ? ??? ? ???? ?1 )m a x{ 0 , (1 }ini iyz??? ?? ? ??1 [ ( 1 m a x{ 0 , } m a x{ 0 ,) }]niii yz???? ? ? ? ??11) m i n{ 0 , m i n{ 0}} ,(1nniiiiyz??????? ??( ) ( )11) | || ||(| ||1 yz.因此，由函数 ()1| || |y? 的凸性和 K-K-T 条件知， ()Px? 在 kx 处沿方向 kd 的方向导数( ) ( )1100) ( ) | | ( ) | |()( | | | |l i mkk k k kk T kd P x cd x d xfx cd d?( ) ( )11((|| [ ) ) ] || ( ) |) || |l im() k k T k kk T k c x A x d xf x d c( ) ( )11( ) ( | ( ( ) ) ] || ( ) ||| ) || )[k T k k k T k kf x d x Accx d x? ???????11 ()( ) ( ) | |||miTk k k k kk i iBd c x xcd?? ????? ? ? ???????() 11|() | ( ) | | ( )mk T k k k kk i iicxd B d cx??? ?? ? ? ? ?，其中矩阵 1 2) ( ( ) ( ) ( ) )( kk mkkc x c x xx cA ? ? ? ??，从而定理得证 .定理 15.2.2 如果 kd 是二次规划问题 (15.2.2)的 K-K-T 点， k? 是相应的乘子，则当( ) 0k T kkd B d ? 且 || ||k 时， kd 是 1l? 罚函数 (15.2.4)在kx 处的下降方向 .证由于1 ( ) ( ) ) ( ))( (m k k k k k ki i i i i ii E Iiic x c x c x? ? ?? ? ??? ? ? ??? ?() 1| ( ) || | | | | | |m a x{ 0 , ( ) } ( ) | ||k k k k k ki i i ii EI ic x c x c x? ? ?，故当 ( ) 0k T kkd B d ? 且 || ||k 时，由 (15.2.5)知 ()Px? 在 kx处沿方向 kd 的方向导数§ 15.2 序列二次规划法最优化理论与方法 [乌力吉 ] 281)( 0kkP d ddx?，这表明 kd 是 1l? 罚函数 (15.2.4)在 kx 处的下降方向 .下面给出序列二次规划法的具体算法，这个算法是韩世平于 1976 年提出来的， Powell在 1977 年给出修改方案 . 由于 Wilson 早在 1963 年就讨论过Lagrange-Newton 法，因此，下面的算法也称作 Wilson-Han-Powell 算法 .算法 15.3（序列二次规划法）步 1：给定初始点 0 nx?? ，罚因子 0?? ，步长上限 0?? ，初始矩阵 0 nnB ，初始参数 0 0?? ，容许误差 0?? ，置 0k? ；步 2：求解二次规划子问题 (15.2.2)得到下降方向 kd ，如果|| ||kd ?? ，则算法结束，输出近似 K-K-T 点 kx ；步 3：求出步长 [0, ]k ，使得0) m i(( n)k k k kkkP d P x dx?? ??? ? ???? ? ? ?； (15.2.7)步 4：令 1kk kkx x d?? ?? ；步 5：产生矩阵 1kB? 和参数 1 0k?? ? ；步 6：置 1kk??，转步 2.注（ 1）在算法 15.3 中，价值函数 ()Px? 是 1l? 罚函数 (15.2.4)，正数列 {}k? 满足0k k??. (15.2.8)（2）矩阵1kB? 的计算一般是用拟牛顿迭代公式产生，我们希望它是 2 1 1( , )kkxxLx 的近似，因此可取1 1 11( ) ( ) ( ), )( ()mk k k k k k k k ki i iix x f x f x cs xy cx?? ? ??? ? ? ? ? ? ? ? ? ??， (15.2.9)然后利用拟牛顿公式计算1kB? . 由于上述线搜索过程不能保证( )0k T kys ? ，从而不能直接利用 BFGS 方法 . Powell 在 1978 年给出了一种修正策略，即取) 0 . 2 ( )( 1 ), ( ,, ) 0 . 2(,()k k T k k T kk kk k k T k k T kk k k ky s B sBysy y s y s B ss?? ????? ? ?第十五章序列二次规划法282 最优化理论与方法 [乌力吉 ]其中(0 .8 ()( ) )k T kkk k T k k T kks B ssysBs? ? ?，经过这样的修正，我们就可以用 BFGS 方法 .还有一种修正策略是以1 ( ) ( )? 2mk k k kiii c x c xyy ? ?? ?? ?来取代 ky . 这种做法一般能保证 ?( )0k T ks y ? ，如果 ?( )0k T ks y ? ，则可以通过增大 ? 来实现其反号 .定理 15.2.3 设 ()fx和 ( )( )i x i E Ic ??都连续可微，且存在两个常数 0 mM?? ，使得不等式22|| |||| || T km d Bd M dd?? (15.2.10)对一切 k 和 nd?? 都成立 . 如果不等式 || ||k 对一切 k 都成立，则由算法 15.3 产生的点列 {}kx 的任何聚点都是约束优化问题 (15.2.1)的 K-K-T 点 .证设x 是点列{}kx 的任意一个聚点，且存在无穷指标集0 {1, }2,K ? ? ，使得0limkkkK x x?.由定理的条件可知， {}k? 和 {}kB 都有界从而0{}k kK? ?和0{}k k KB ?都有收敛子列，不妨就设00,lim limkkk kKKBB? ???.由于 kd 是二次规划子问题 (15.2.2)的最优解，从而 kd 满足 K-K-T 条件 (15.2.3). 注意到()fx和 ( )( )i x i E Ic ??都连续可微， kB 满足不等式 (15.2.10)，由线性方程组的扰动理论，我们在 (15.2.3)式中令 k?? ，不难得出lim kkKk dd??? ? ， (15.2.11)且 d 满足 K-K-T 条件§ 15.2 序列二次规划法最优化理论与方法 [乌力吉 ] 2831( ) ( ) ,( ) ( ) 0 , , ( ) ( ) 0 , 0 , ( ) ( ) .( ) 0 , miiiTiiTi i iTi i if x c xx x i ExxBdc d cc d c cdx x Ici(15.2.12)如果 d?0 ，则由 K-K-T 条件 (15.2.12)易见，这时 x 是约束优化问题 (15.2.1)的 K-K-T点，定理得证 .下面讨论 d?0 的情形，这时取 [0, ]? ?? ，满足0) m i((n)P x P xdd????????? ? ?.由于 d 满足 K-K-T 条件 (15.2.12)，其中 ? 是 x 的乘子， 0Td Bd? ，|| ||? ??? ，由定理 15.2.2 可知， d 是目标函数 ()Px? 在 x 处的下降方向，从而有)(()P x P xd.记 ) )0((P x P x d??? ??? ?? ，由于kkd x dx ??? ? ? 0,)( kKk ?? ? ，故对充分大的 0k K? ，有() 2 ()kkPPx d x??? ??? ?. (15.2.13)另一方面，由于1 0) m in(( )( )k k k kkkxxP P d P x? ? ??? ? ? ?? ??? ? ? ? ? 对每个 k 成立，故对任意自然数 k 和 m ， 1mk??，有111( ) )(mmkiikPxxP?? ?. (15.2.14)再注意到不等式 (15.2.8)蕴含对充分大的 k 有2iki ???? ??，因此，对充分大的 k ，我们在不等式 (15.2.14)中令 m?? ，得第十五章序列二次规划法284 最优化理论与方法 [乌力吉 ]11( ) )(k iikP xP x?? ?0 (m i n )kk iikPdx??? ??。
约束优化算法的关键技术研究及应用约束优化算法是一种解决带有约束条件的优化问题的方法。
在许多实际应用中，我们需要在满足一定约束条件的情况下找到最优的解决方案。
本文将介绍约束优化算法的关键技术研究和应用，并且将详细阐述其中几个重要的算法。
约束优化问题更具有挑战性，因为既要在满足约束条件的范围内解空间，又要找到全局最优解。
以下是约束优化算法的关键技术研究和应用：1.约束处理技术：在约束优化问题中，对约束条件的处理是非常关键的。
一种常用的方法是将约束条件转化为罚函数，将违反约束的解惩罚，而不使其进入空间。
另一种常用的方法是采用预处理技术，通过削减解空间来减少约束条件的考虑。
2.高效的策略：在寻找最优解时，需要采用高效的策略。
常见的策略包括遗传算法、禁忌、蚁群算法等。
这些算法通过引入随机性和启发式信息，能够有效地在解空间中到较优的解。
3.优化算法融合技术：将不同的优化算法进行融合，能够提高求解效率和精度。
例如，遗传算法和模拟退火算法的融合可以在全局和局部之间进行切换，以充分利用两种算法的优点。
4.约束满足技术：约束满足技术是约束优化算法中的重要要素之一、它通过检查每个生成的解是否满足约束条件，从而筛选掉不满足约束的解。
常见的约束满足技术包括约束传播和剪枝等。
5.多目标优化技术：在一些实际问题中，存在多个目标需要优化。
多目标优化技术能够同时考虑多个目标，出一组最优解的集合，形成一个帕累托前沿。
常见的多目标优化技术包括遗传算法和多目标粒子群优化算法等。
1.工程设计：在工程设计中，约束优化算法可以帮助工程师找到满足各种约束条件的最优设计方案。
例如，在飞机设计中，需要同时考虑飞行性能、结构强度和燃料消耗等多个方面。
2.网络优化：在网络优化中，约束优化算法可以帮助优化网络拓扑、资源分配和流量控制等问题。
例如，在无线通信网络中，需要优化传输速率、信号质量和功耗等多个指标。
3.金融风险管理：在金融风险管理中，约束优化算法可以用于优化投资组合、风险控制和资产配置等问题。
第7章约束问题的优化方法第三节二次规划第四节序列二次规划第三节二次规划一、二次规划的基本概念二次规划（Quadratic Programming, QP）是一种特殊的非线性规划问题，目标函数是二次函数，约束是线性函数，如果只含等式约束，则形如（1）为阶对称矩阵，为矩阵，秩为。
如果半正定/正定，则其KKT点就是全局最优。
许多现实问题本身可建模为二次规划，而一些一般规划问题也能近似归结为求解二次规划问题，因此二次规划具有重要的地位。
求解二次规划（QP）问题的算法较多，如：（1）Lagrange方法（2）起作用集方法（3）Lemke方法（4）路径跟踪法二、求解等式约束QP问题的Lagrange方法考虑QP问题（1），其Lagrange函数为KKT条件：将此方程组写成（2）系数矩阵称为Lagrange矩阵。
设Lagrange矩阵可逆，其逆矩阵可表示为由式，得假设逆矩阵存在，由上述关系可解得：（3）（4）（5）于是Lagrange矩阵的逆可知。
（2）式两端乘以Lagrange矩阵的逆，就得到KKT点（6）（7）的迭代形式：设是问题（1）的任一可行解，即满足，在此点，目标函数的梯度利用和，可将（6）、（7）式改写为（8）（9）如果目标函数凸，则上述点就是一个全局极小。
例1，用Lagrange方法求解可计算出。
由（3）、（4）、（5）式得到再根据（6）式，计算问题的最优解（KKT点）为：三、起作用集方法（具有不等式约束的QP问题）考虑具有不等式约束的QP问题（10）为阶对称正定矩阵，为矩阵，秩为。
因为不是等式约束，因此该问题不能直接用Lagrange方法求解*，求解的策略之一，是用起作用集方法将它转化为求解等式约束问题。
*使用剩余变量也能化为等式约束：；但这种方法是不可取的，因为又增加了不等式约束：，结果问题还是没有完全转化为等式约束。
（一）起作用集方法的基本思路在每次迭代中，以已知的可行点为起点，把在该点的起作用约束作为等式约束，在此约束下极小化目标函数，而其余的约束暂且不管，求得新的比较好的可行点后，再重复以上做法。
关于序列二次规划（SQP）算法求解非线性规划问题研究兰州大学硕士学位论文关于序列二次规划（SQP）算法求解非线性规划问题的研究姓名：石国春申请学位级别：硕士专业：数学、运筹学与控制论指导教师：王海明20090602兰州大学2009届硕士学位论文摘要非线性约束优化问题是最一般形式的非线性规划NLP问题，近年来，人们通过对它的研究，提出了解决此类问题的许多方法，如罚函数法，可行方向法，Quadratic及序列二次规划SequentialProgramming简写为SOP方法。
本文主要研究用序列二次规划SOP算法求解不等式约束的非线性规划问题。
SOP算法求解非线性约束优化问题主要通过求解一系列二次规划子问题来实现。
本文基于对大规模约束优化问题的讨论，研究了积极约束集上的SOP 算法。
我们在约束优化问题的s一积极约束集上构造一个二次规划子问题，通过对该二次规划子问题求解，获得一个搜索方向。
利用一般的价值罚函数进行线搜索，得到改进的迭代点。
本文证明了这个算法在一定的条件下是全局收敛的。
关键字：非线性规划，序列二次规划，积极约束集Hl兰州人学2009届硕二t学位论文AbstractNonlinearconstrainedarethemostinoptimizationproblemsgenericsubjectsmathematicalnewmethodsareachievedtosolveprogramming．Recently,Manyasdirectionit，suchfunction，feasiblemethod，sequentialquadraticpenaltyprogramming??forconstrainedInthisthemethodspaper,westudysolvinginequalityabyprogrammingalgorithm．optimizationproblemssequentialquadraticmethodaofSQPgeneratesquadraticprogrammingQPsequencemotivationforthisworkisfromtheofsubproblems．OuroriginatedapplicationsinanactivesetSQPandSQPsolvinglarge-scaleproblems．wepresentstudyforconstrainedestablishontheQPalgorithminequalityoptimization．wesubproblemsactivesetofthesearchdirectionisachievedQPoriginalproblem．AbysolvingandExactfunctionsaslinesearchfunctionsubproblems．wepresentgeneralpenaltyunderobtainabetteriterate．theofourisestablishedglobalconvergencealgorithmsuitableconditions．Keywords：nonlinearprogramming，sequentialquadraticprogrammingalgorithm，activesetlv兰州大学2009届硕士学位论文原创性声明本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所取得的成果。
等式约束优化问题的求解方法等式约束优化问题是一类重要的数学问题。
它的求解方法在多个领域中得到广泛应用，如机器学习、运筹学、经济学等。
本文将介绍几种常见的求解等式约束优化问题的方法。
一、拉格朗日乘数法拉格朗日乘数法是求解等式约束优化问题的经典方法之一。
设等式约束为f(x)=0，目标函数为g(x)，则拉格朗日函数为：L(x,λ)=g(x)+λf(x)其中，λ称为拉格朗日乘子。
根据最优化问题的求解原理，若x*为最优解，则存在一个λ*使得L(x*,λ*)取最小值。
我们可以通过对L(x,λ)求偏导数，然后令它们等于0，得到x*和λ*的值。
具体来说，求解过程如下：1. 求g(x)的梯度，令其等于λf(x)的梯度，即：∇g(x*)=λ*∇f(x*)2. 求f(x)的值，令其等于0，即：f(x*)=03. 代入公式，解出λ*。
4. 代入公式，解出x*。
值得注意的是，拉格朗日乘数法求解等式约束优化问题的前提是强可行性条件成立，即在f(x)=0的前提下，g(x)的最小值存在。
二、牛顿法牛顿法也是一种常用的求解等式约束优化问题的方法。
它的思路是利用二阶导数信息迭代地逼近最优解。
具体来说，求解过程如下：1. 初始化x0。
2. 计算g(x)和f(x)的一阶和二阶导数。
3. 利用二阶导数信息，优化一个二次模型，即：min{g(x)+∇g(x0)(x-x0)+1/2(x-x0)^TH(x-x0)} s.t. f(x)=0其中H是目标函数g(x)的海塞矩阵。
4. 求解约束最小二乘问题的解x*，即为下一轮的迭代结果。
5. 判断是否满足终止条件。
若满足，则停止迭代，输出结果。
否则，返回第2步。
牛顿法比拉格朗日乘数法更加高效，但是它不保证每次迭代都能收敛到最优解。
三、序列二次规划算法序列二次规划算法是一种求解等式约束优化问题的黑箱算法。
其主要思路是将目标函数g(x)的二次型模型转化为约束最小二乘问题。
这个约束最小二乘问题可以通过牛顿法来求解。
《互补约束优化问题若干算法研究》篇一一、引言互补约束优化问题（Complementary Constraint Optimization Problem, CCOP）是运筹学和优化理论中一类重要的数学问题。
这类问题在工程、经济、管理等多个领域有着广泛的应用。
互补约束优化问题的核心在于处理变量间的互补关系和约束条件，使得在满足所有约束的条件下，寻找最优解。
本文将就互补约束优化问题的若干算法进行研究，探讨其理论和应用。
二、互补约束优化问题概述互补约束优化问题通常涉及一组决策变量，这些变量之间存在互补关系，且受到一系列线性或非线性约束的限制。
问题的目标是寻找一组决策变量，使得在满足所有约束的条件下，某个或某些目标函数达到最优值。
这类问题具有非线性、非凸性、不连续性等特点，求解难度较大。
三、算法研究1. 线性互补问题算法线性互补问题是互补约束优化问题的一个特例，其决策变量和约束条件均为线性。
针对这类问题，常用的算法包括基于内点法的算法、投影算法等。
内点法通过迭代求解一系列线性方程组，逐步逼近最优解。
投影算法则通过投影操作将决策变量投影到满足互补约束的可行域内，从而得到最优解。
2. 非线性互补问题算法对于非线性互补问题，由于问题的非凸性和不连续性，求解难度更大。
常用的算法包括基于迭代搜索的算法、神经网络算法等。
迭代搜索算法通过不断调整决策变量的值，使得目标函数逐步逼近最优值。
神经网络算法则通过构建神经网络模型，将互补约束优化问题转化为神经网络的训练问题，通过训练得到最优解。
3. 混合整数规划算法混合整数规划是处理具有整数和连续决策变量的优化问题的一类方法。
在互补约束优化问题中，如果部分决策变量为整数，可以采用混合整数规划算法进行求解。
常用的算法包括分支定界法、割平面法等。
这些算法通过不断缩小搜索空间，逐步逼近最优解。
四、应用研究互补约束优化问题的应用非常广泛，如工程优化、经济调度、资源分配等问题。
以工程优化为例，互补约束优化问题可以用于结构优化、控制系统设计等领域。
广西科学 Gua n g x i Sciences 2〇16,23(5):385〜391网络优先数字出版时间：2016-11_21 【DOI】10. 13656/ki.gxkx. 20161121. 006网络优先数字出版地址：http://www. cnki. net/kcms/detail/45. 1206. G3. 20161121. 1520. 012. html约束优化问题稳定序列二次规划方法研究综述4An Overview of the Researches on Stabilized Sequential Quadratic Programming Methods for Constrained Optimization Problems刘美杏，简金宝〃LIU Meixing，JIAN Jinbao(玉林师范学院，复杂系统优化与大数据处理广西高校重点实验室，广西玉林537000)(Guangxi Colleges and Universities K e y L a b of C o m p l e x S y s t e m Optimization and Big Data Processing,Yulin N o r m a l University,Yul i n,G u a n g x i,537000, China)摘要：稳定序列二次规划（sSQP)方法由于在求解病态或退化约束优化问题获得理论与数值的突破性进展而备 受关注，重要成果频繁问世.本文对近期国际上若干重要sS Q P方法及其思想进行概述，包括罚函数型sS Q P方法，滤子型sS Q P方法和非精确恢复（IR)型sS Q P方法等，并对约束优化问题sS Q P方法的进一步研究进行探索 性思考.关键词：约束优化问题稳定序列二次规划收敛速度中图分类号：0221. 2 文献标识码：A 文章编号：1005-9164(2016)05-0385-07Abstract：T h e stabilized sequential quadratic p r o g r a m m i n g (s S Q P) m e t h o d s attract great attention with respect to the theoretical and numerical breakthrough for solving ill-posed or degenerate constrained optimization p r o b l e m s，and m a n y important references about s S Q P m e t h o d s we r e published. This paper gives an overview on s o m e important s S Q P m e t h o d s,which mainly include penalty function type s S Q P m e t h o d s?filter type s S Q P m e t h o d s and inexact restoration (IR) type s S Q P m e t h o d s，and a fe w exploratory considerations for further study on s S Q P m e t h o d s are given.Key words：constrained optimization p r o b l e m s，stabilized sequential quadratic p r o g r a m m i n g, convergence rate0引言收稿日期=2016-07-01修回日期=2016-08-27作者简介：刘美杏（1987 —），女，硕士，主要从事最优化理论与算 法研究。
*国家自然科学基金项目（11271086)，广西自然科学基金项目 (2014GXNSFFA118001)，广西高校科研项目（ZD201407)和复杂系统优化与大数据重点实验室开放基金项目(2015CSOBDP0203)资助。
通信作者：简金宝（1964 —），男，教授，博士，博士生导师，主要从事最优化理论与算法及应用研究，E-mail: jian;jb@gxu. edu.稳定序列二次规划（sSQP)方法作为序列二次规 划（SQP)方法的重要扩展，致力于考虑芽问题模盡、假设条件、技术构造、收敛性质（全局收敛或收敛速度)与数值效果等方面的研究..尤其是对相对弱条件下的收敛速度与数值效果,值掲注意的是，对1*退化 约束优化问题.当对应原始解的拉格朗日乘子不唯一 时，快速收敛性的实现难度极大.19 M年，Wrigh#]首次提出求解退化不等式约束优化的s S Q P方法以来，以W r i g h t，H a g e r，Izmailov，广西科学2016年10月第23卷第5期385Ferndnde2，.S〇lod〇Y，Gill 及 Robi.n so.n.等为代羞的sSQP方法及理论研究发展迅速，取得系列成果.文 献的方法在每次迭代时需求解一个属标函数二次 的极大极小问题，可等价转化为原始对偶空间i的稳 定二次规划（QP)问题。
该作者在二阶充分最优性条 件C SO SC^.sMang.a sari.a n-Fi.〇R T Q v it;z 约率规.格（MF-CQ)和严格互补等条件下，怔明了 sSQP方法的局部 二次收敛性.文献[1:〕:謙一步改进文献0Q的sSQP方'法，在SOSC和MFCQ等较弱的条件下，证明算法具 备局部二次收敛性.Hage^I对收敛性假设条件进行 研究.仅在SOSC.条件下获得文献[U;中算法的局部 收敛性.并提出用一对不等式约束来表示等式约束. 从而可将方法推广到一般约束优化问题.相比较，传 统SQP方法对乘子唯一性有着较苛刻的要求，只能 依靠严格MFC.Q条件来保证.特别地，在等式约束情 形下，迫使线性无关约束规格（LICQ)成立w.文献 这〕将sSQP方法推广到求解含等式;与不等式约束的 变分问题，当初始点充分靠近原始对偁稳定点时•仅 需SOSC假设条件，实现了算法的超线性收敛性.对于等式约束优化问题*文献[$]在非临界乘子的条件下建食了超线性收敛的必Q P方法> 文献#讓孑线 性方程组，在无需LICQ和严格苴补等较强的假设条 伴下,提出一个二次收敛的牛顿塾sSQP方法，并:给出了该方法超线性收敛的重要定理.文献[S〕将拟牛 顿型sSQP方法拓广到变分不等式问题，通过对Bregman距离极小化来更新矩阵償息，这祥仪需:要SOSC便可证明算法的超线性收敛性，上述文献主要聚焦在最优解的局部范围内构造有效算法，并研究不同假设条件对其收敛速度的影响.建京了一批局部超线性收敛或二次收敛的sSQP 方法.这些文献都侧重于局部收敛速度的分析，对算 法全局优化策略（全局收敛性质）未做深入研究.而此 问题正是实际应用和优化学者们希冀解决的问题.也 是衡鸶萆优化算法有效性的重要指标之一_近年来，尽管国内外不少李者对全局化sSQP方法潜心研究，但成果有限.本文主要介绍如下几类的全局sSQP算 法：罚函数型sSQP方法滤子型sSQP方法[13]和IR M sSQP方法_[14]，弁:对约束优化向题sSQP方 法的进一步研究进行探索性思考.1 函数型sSQP方法当前，对sSQP方法全局化策略的研究仍是一项 极其具看挑战性的作，其中约東优化sSQP方法全 局化时罚函数的选取极其困难，这对于蕞优性或下降 性影响甚大.Gill等W引人原始对偶广义增广拉格朗3§@日（A U函数.提出t个求解等式约束加简单界约 束优化问题的全局收敛sSQP方法.Izm aU〇V.Dl3充 分利用A L方法的鲁棒性，在没有任何积极约束识别 策略下构造了一个$〇?方法，并证明了算法的全局 收敛性和麓部收敛連度，随后，他们又在文献〇(2]中 以原始对偶精确罚函数^]为效益函数•提出了一个 求解等式约束优化问题的sSQP方法，并分析了算法 的全局收敛性和超线性收敛速度.下面参考文献D幻I•介绍一个具体的罚函数型sSQP算法.考虑等式约束优化问题：m in f i x)s.t.h(x) =0 ?(1)其中 /(x):i?n— _R，/i(：r)= (/ii(x)，…，/iz(x))T: w —兒至少是二阶可微函数.令问题a)的Lagrange函数为L(x，A) =/X x)+〈A，/i(x)〉，(2)其中，符号〈•，•〉表亦向量内积运算.则问题（1)对 应的一阶最优性条件为，A) =0，/i(x) =0•(3)〇x进而，定义函数少:尺”X_RZ — W X_R Z，少（x，A) =，A)，/i(x)). (4)〇x对一个给定的原始对偶迭代点（x，A) 6P X P Z及稳 定参数^>0,考虑如下原始对偶空间上的sSQP子问 题，并产生sSQP方向（6,7)，m in<(x)?~，A)«f，《f〉+吾 ||A+(f,r j)L ax乙v I I 2s.t./i(x)+/i7—arj=0 ^(5)其中 /i’(x) =(V/i!(x)，…，V/iz(x))T.基于上述sSQP方向（搜索方向），文献[12]采用 如下原始对偶效益函数[15]^胃^”—仏=L(x,A) +I I h{x~) || 2 +警 i i心A) r_(6) z 〇X此处选取适当罚参数>0,Q >0,可以保证由于问 題产:生的sSQP方向是&A)的下降方向.由文献和文献0?；]知,_愿始对偶效益函数(6> :暴:一个精确罚函数.即如果c2>:©充分小,以>0充分大，则於,t，A,)任:意稳定点部痛问题.(1)的稳定•点；反之，如果最:优_性系统(3j_.的_原.始对偶解X^s..，A) 满足U C Q和S O S C等条件，则它必是罚猜数炉-广-:(x，A)的严格痛部极小解■为便于分析和陈述算法的收敛性条件•卞面复Guangxi Sciences，Vol. 23 No. 5, O ctober 2016速二阶充分条件（SOSC):(文献[|2,以及临# Lagra.n gian乘爹灌I非临.养 La.g.ratigian乘子[6.l h—19] ■等食龙.记萬;）是南同题⑴翁稳定点；处对应的 _L.a gr3n.g ia.n乘子构成的集合.记号k e;r A，im A分.别表示矩阵A的零空::间和列金间、即ker A== 0},im A = {d-.d=Ay}.定义1 称I J满足二阶充分条件(SOSC:)，如果it.> >• ©, V6 6ker/i/ (.r)\ {>〇}.d"<7)定义2称x e是临界乘子，如存在e ek e r // (x.)\ f .9}，使得 D L (x，X.)f €i t n(./!.’(a'.).)T，否 则.称[是非临界乘誓，嚴然，如I €J(5)满足s o s c，则其是.非临界 乘乎•故非临界乘子条件弱于SOSC.算法1 (文献〔11]中sSQP算法）初始步选取参数> 0 : >0 s e2 > 0，Cj.:> 0'，.Q e：>0，.:8?i〇>.0..，g.> 1:,沒€ [〇,1]..固..定连续嚴数(:除_丁 ,〇点外函数值几乎处处为办，，•：尺+4选取原始对偶初始.点.(？，A a)__e i?":x兒（置 k ：=D,步骤1由（4:>:式计箕屯A中(，若也= Q，..终止，步骤 2 .令|| 氣 || }，c r=c^.,Cr，A)=■d):，求解乎问题(5)的K K T系统得到稳定矣，),若该系统无解，则进人步骤4_步骤3 _:(i)如果物"丨1,|| 5f(8)则进人步骤5.(ID如果||h(x k)I^ifiiiat)(9)息(h(j;>i),h，(x1'}^1)tpi(I/iC a'*,)I.1■(2Q)则令q =<T i…i.+l，.其.中.e iw =(!.((〇丨|,I卜)•如果.1?! <，进入歩骤_5 i:W则，令fi.=C；js进人 步骤4,.f iii.)如果I I>^(心)，（11)则.令Q =f2.4 +|v其中 f2.4 =C.g(p||(i l VP*.»A4_|fS 7*，.f i:)_■如果 f2 <G,进人步.骤 5:,;..'苔则f2 =C2•步骤《选取(h+D阶对称正隹:矩阵f t，计弇 方向,=—Q冷、:(x's A*).步骤5 计算&，此处j为满足不等式Vli((#4,A a> +ffd*) <：fsi…2C^k：. A4)Ht''(x H d k、(12)的最小非负整数.步骤 6 令 d；i*+1) =(y.A*).A :=細歩骤1.在算法i的迭代过程中，常量值匕.e:的设置对 该算法的执行有着重要的防御作用，一般地，这两个 数值应该取足够大，方能保证罚参数^_的更新法 则不受影响.为T増强算法设计的有效性，当f问题 (5)K K T系统无解或步骤3的任一情形都不被执行 时，算法1执行步骤4的拟牛顿步防御措施，以修正 sSQP方向使之具有下降性，从而算法具有良好的适 定性和全爲收敛性质.当初始点充分靠近稳定点时，仅臂要非临择L a g_r a h gian■乘争假设，即可证明算株1的超线性收敛.对退化测试问题，算法1表现出了良 好的数值效果.2滤子型sSQP方法滤子法是近20年提出的求解非线性约束优化的 —种有效方法.该方法的提出是为了避免在实际问题 中设置魏参数.阜期滤子法的研究妇功于Fletchei•和Leyf f e#M]，随后该方法因良好的数值效果而备受关近期代表成臬见文献[21-2S].,文献n:i3]对稳棄 Q P子问题进行修正，并结合双滤子技术[:1]提出了求 解一般约束优化问题的滤子型sSQP方法，下面文献〔13]中的算法进行分析.考虑如下一般非线性规划问题：m i n f i x)s. t./i e(x) =0，/ij〇) < 0，（13)其中，(尤）=(/i f(尤）6 e)=("!(尤）€ ■0，e = {l,2, •59/}?I={Z+1?Z+2, * s <>m} •>f \Rn ^ R ^ &—尺“ e e U I为连续可微函数.定义问题（13)的 Lagrangian 函数 L(x，/_0 为L(x,fx) =f(x) +2fj.i hi(x). (14)ie e lil这里y=(/^i，内，• 5，//m)T 是 Lagrangian 乘子向量.对于当前给定的原始对偶估计迭代点对（^，/，0，求解如下修正的稳定Q P子问题：m i n f r(xk)Td+—dTBkd+^―— ||+id,A X') L LA A ||^s. t.h£(xk) h；e(xk)Td— aL,kA A e =0 ?hT(xk) +h/I(xk)Td-a LfkAXI < 0. (15)387广西科学2016年10月第23卷第5期其中，，*是稳定参数^是V L L Q-*，，'4〉的近似 对称正定矩阵.当应=▽!;(.人//)，/』=/：/= (r C P，/)时，萁中^ V j, L (；ps >f xA) 、a ixk y[Jtk) = h e {xk ) t(16.)in {—hi ix k),f2j }-J：问题(15)是一个传统的稳定Q P子问题模型.源于算 法良好的收敛性质，设计了两种乘子更新方式，其中 保证全局收敛•//则满足鳥部收敛的需求.类似 地•考虑妒和(7〃的更新准则.翁宁问题(15)的解岽义原始对偶搜索方.向W4，A.//:>(此处=ZU4十:/-*'—户4>,此方 向对算法收敛性理论分析有着重要的作用，其等价于求解如下相容的稳定Q P子问题:m i n f'(.xkr d+\d yBk^ 4^ I I i^k +{d,^ (a~)乙Z is.t.he(xk) h；e(xk)Td— aL,k (fxk£Afx£ —W，”=0，/ij(x^) +/i/J(x^)T^ — aL,k (/ui +A fxi — fx\,k) ^ 0.(17)在设计非线性规划问题（13)的有效算法时，除 需要对目标函数进行极小化，同时要不断降低约束违 反度函数：h(x)= S hi(x)|+2 max{/if(x) ,0}. (18)i=\f=m然而，搜索方向W S A/Z)难以直接达到这样的要求.因此，引入如下辅助目标函数少(x，^)和松她约束违 反度函数户(x，"）：= fix') +I I I I S(19)p{x,fx) =|hi(x) — aL,k (fxt — fXiL,k)|+i=1S^J max{/if(x) — aL,k (/ut — fxtL,k),〇}. (20) j =z+i进而引进双滤子技术（基于文献£Sl],但有所改进），包括“全局滤子”和“局部滤子前者致力于算法收斂于:KKT点或稳:定点:s爵者以实现其暴部收敛速度,对于第是次迭代，“全局滤子”和“屈部滤子”分别记m.定义3购称点对(.；•">被全局滤爭”元W,)或中(#^>)_接麗,;如果'=它满足如__下两个 不等式之一掌p ix1 ,p!) — p(x,/j) 7i [/>(a：,/-«)]" »(21)(/H.r ./<')—(pLr.y.；•^i.(22)此处}^ 6 (〇，l>.定义4[1〇!称点对为“全局滤子”元•如果 它被“全局滤子”所有元素（Ma"，//)，中(7，//))接受.定义5M称点对(■〖•/〕）被“局部滤子”元.y)或（m w)，/(^))接受，如果它满足下面两个不等式 之一：it('xf’) —h(j：)^max{yi A(.r?min{y3.c r(a：;•(23)f i x') — f(x) ；Ss (x )%rnin：f ys,，）”•(24)此处y3 >〇是一个常数.定义6[1®»称点对G./l)为“局部滤子”元•如果 它被“局部滤子”所有元素a(x%/(;r〇)接受.财于问题(13:)及当前笾代点对％、,求解稳 定Q P子问题（17)得到搜素方向（^3//：)，并沿着 此方向和步长《，分别定义函数®的实际下降量和线性预测下降量*A(a) =^{x k,j j,k)—^>{xk-l r adi ,fik+,A lU a)=-r^C-r*}T^令：r =J十(OcT*，" =//十M/•；—，当该探歩长:a = 1时，定义K K T误藏下降条件：t?ai,3；,jx) ^r ahJl,t 6f0 .t?> 0.(25)此外.文献[1幻结合“全烏滤子”接受条件，进一步利 用回溯技术选择了恰国•的步长《、判断条件和步长下界.开关条件^>sip<xk …/)j rS e(2-6)充分卞降条件：A^i a1)>rzi l%{ak) ,(27) ='.r y m i n{72p(xk ,fck) ,d\^p(xk ,/uk)y} x/(^y^+a^C f/y A^u<若 /+(j U(//)T A// < 0;心否则.(28)其中，常数$ 6(〇，l).对于原始对偶迭代点对(i^)，如果它被局部滤 子接受，或者满足K K T误差下降条件(25)，或者满足如下近似松弛一阶条件：ipix jfx) ^4?其中，中i x，fx) ••=/^Vx L{x 9/u)he(x) — aL,k i/x£ — /u eL,k)^m i n(— hi(x) +aL,k (/u：-(29)，(30)L,k入f^I/Guangxi Sciences，Vol. 23 No. 5, October 2016388则序列；4丨下降趋于0•构造Lagrange乘子，^和稳定参数一'4的更新准则：.,n?右T I I I I/^max，a k：=；丨//，S否则.aL,k+l = mm{p aL,k <>d a{x tfx)} t其中，/^max>〇，/?6 (〇，l)是两个常数.(31)(32)下面给出求解问题（13)的滤子型s S Q P算法.算法2 (文献[13]中s S Q P算法之外循环)初始步选取初始点x G参数4>〇，叫> 0，〉0，沒〉0，〉0，"m a x〉0，竺G (〇，1)，7i 6 (〇，i) ；r2€(〇a),e(〇,i>：,r €c o,y>,j? e(〇*i, fjL'0 ^0, f/ =0. &i> :91 o*L'0 > 0» = \ ( U i i ^%} < < ={(%，一n.U iF la g=GLOBAXs置..是：=.0.步骤.1 如顰问题(13 J的K K T歲或 不可行稳定点，则终止.步骤2 求解穩倉Q P子问题(17)_，产生原翁对偶解 ，A/』:i〉，令 a=1，本.=界*+一*，户=/7 +d_/*..*•步骤3 如果（&./〕）被局部滤子接受或满足(25)式，则由准则（3U和(32)更新乘子，和稳定 :参数f f L.*+1?鸞Flag=LOCAU g+1 ={.(:心，—■):')}•否则，进人步骤4,步骤S 启动算法■3:(.算:法12之内循环）,.翁得赢对(x，/丄)和:步长a.如果:众<«.l.a*则令//+1 =//'*，进人 可行性恢复阶段弁找到新的迭代点y+1，使得(乂+1,广1)被全局滤管■汽接受./Z*1 .(^U+1，甘+1保持 .不变■如果汐(乂，//:)..:> 〇，则令系：=是+1，将(户(a-4? //:),◎(，,//>)加人如粜森对(i：，;:）满足(烈> 式，则_准则(31)和 (32)更新，'“1和,令《+1 = ;(^，一_):|)}. 4*=#?*r f^+1 =##*步骤5 如果(i#)被局部滤子接受•则将(/iCr K/C x：))加人束，更新局部滤乎.否贝I]•进人步H 6.步骤 6令:r*+1 =#..，//+1=/•<=a■々.：=是 +1，县FIag=GLOBAL.利用拟牛顿公式更新矩阵甘+1 •返回步骤1.算法3(算法2之内循环）.步骤 1令;r=:r* +..Q^=//+..<f e i^•如果.« ，则进人歩骤2;否则•终止.步骤2如果.(:x，./j)被金:局，滤子攘受.，则进人歩 骤3*:'否_则令〇:=r a，返國步骤L步骤3 如果开关条件(26)不成立或充分下降 条件（27)成立，则终止.否则令a=r a，返回步骤1.能被滤子接受(全烏滤子或局部滤子 >.这对整个算法 的收敛性质分析起到至关重要的作用.在理论上.不需要任何约束规格，即可证明：滤子型sSQP算法2 不仅具有全局收敛性（存在收敛子列或收敛于KKT 点，或收敛于不可行稳定点），而且在SOSC下.算法 达到超线性收敛速度..3 IR型sSQP方法sSQP方法的研究最早可以追溯到20世纪末，虽然在适绿的假设条件或技术下單.斯的研究成果实 现了算法快速的收敛速度 <但在理论上能实现全局收 敛的成果较少，滤子型sSQP方法需储存滤爭信息, 会造成存储量大.而且当迭代点远离可行域，或者在 迭代过程中当试探步长比既定下界粟小时，为寻找一 个能被全局滤子接受的新迭代点，需要执行可行性恢 复阶段，这无疑増加算法计算成本，从而影响数值效 果.然而，IR技术_可以减少可行性恢复阶段的复 杂性，对sSQP算法的理论分析有着重要的作用.文献■出了求解含等式且金量有界约束优化的IR 型sSQP方法，下面详细介绍此算法，考虑问题(1)，且满足约束条件x e d=u e及" a<-r<ft}，此处<2,6e _R"•定义间题a)的自然残 差X R1 M r R，a(x-X)=9L{x,X)JXh i x)(33)其中，P a表示在fl J l的1£交投影，L:俨:X i?f4i?是 Lagran.gian函数（2).对y原餘对偶迭代点，对W，A4)，罚參褻> 0 及Q«，其中Q*是间题Cl)L:a grang丨a n Hesse的近似，考虑如下拟牛顿型sSQP子问题：m in+士.一)—5>+2pt I I As.t,h(x k)+h'(x ky('专一x k.)----(A—A4)=0spkf e a(34)为构造全局收敛算法，引人下面的辅助函数&(.^ A)«Ht(ic-A)：i?f t ><R l—R：||A || °5(35)AptH t(x-A) =/?(.r) ——(A—A*).(36)pt选取点n r) =(a：...A*(a：.))，易.知(T* (x.))=利用取雄子技术，由鼻祛2产生的所有迭代点均0, V尤e对于Y4 :=浐:=(X，A h s S Q P 广西科■學—1=«:年10月_笫.23卷第.S期389子问题(34)等价于如下Q F子问题: m i nY<F；(y〇,y-y^> +y<Qk〇0 —/P k](Y-.).y—y*>s,t.(Y—Y*) =0 e D X记.，（37).在意到讯（Y*)=0.不难发现上述Q F子问题(37)对 应于优化问题：min F4(Y)ys.t.Hk(Y) =0,Y e Q X R1c m 的Q P近似子问题.通过近似求解问题(.37)可获得 sS Q P方法的局部收敛性质，气对i f次迭代•IR方法包括恢复阶段和极小化阶段.在恢复阶段•给定迭代点A'计算恢复点Y S避免 T目标函数值以及可行性恶化.在极小化阶段，塞于 可行性和最优性构造言^个含罚参数的效益函数，并 沿着一阶可行方向进行线搜索.下面给出I R型sS Q P算法的具体步骤.算法4(文献[14]中5SQP算法）初始步选取参数r芒<0»1)e(:〇，1)>〇?#列仏丨_滴_足％^|〇，《^焉>〇、选取任_意近似初始 X0=Q M11-A0)^D X R' ,p〇〇!^-i =a(X a)i 是：对当前参数内，定义11；,(x,A) =(,：x>tn,ax{—ah -Jp^e,min;{A.aw Vpte}})•(3 9}步骤1计算:ffCX4),奢) <e v则终止.步骤 2(t)令 x*.°=(乂.Q a4.。
