1、第五章 约束优化常见算法定义5.1设 为一可行点, ，若存在 0, 使对 0, 均有 + x , 则称是可行域在可行解处的可行方向 , 可行域在可行解处的所有可行方向记为FD(, ), 简记为FD()定理5.1设是问题(5.1)的可行解，在点 处有 = , ，其中1 1 2 2，=12 =12则非零向量为处的可行方向的充要条件是 0, = 0 。1Zoutendijk方法：如果非零向量同时满足 ，其中1 1 2 2，=12 =12则为Kuhn-Tucker点的充要条件是问题(5.2)的最优目标值为零。Rosen投影梯度法定义5.2设为 阶矩阵，若 = 且 = ，则称 为投影矩阵。 2定理5.3
2、设是问题(5.1)的可行解，在点 处，有1 = 1,2 2，其中，=12 =12又设=1为行满秩矩阵，则 = 是一个投影矩阵, 且若()1() 0，则 = ()是下降可行方向.定理5.4设是问题(5.1)的一个可行解 , , ,的定义同定理5.3, 且 为行满1 2秩矩阵，令 = () =()1 其中 和 分别对应于 和. 若() = 0，则11 如果 0，那么是K-T点；2 如果 中含有负分量，不妨设 .2 23.令=1如果是空的，令 = （单位矩阵）, 否则令 = .()14.令 = ( ). 若() 0, 则转步6; 若() = 0，则进行步() () 5.若 是空的，则停止计算，得到
3、；否则，令() = () =()1 如果 0，则停止计算， 为K-T点；如果 中包含负分量，则选()择一个负分量，比如 ，修正 ，去掉 中对应 的行，返回步3。 1 1 根据式(5.4)计算 , 然后解下列问题,min ( + )() (). 0 得步长 ，令= + ,(+1) () ()置 := + 1，返回步2Du 若 0定义: ()=(,)|引理5.1设 , 均是 的非空子集 , (), 和()均在 ()(=1,)上连续, 并存在 , 当 时, 存在 ,使00 0 ，则：()=(,)()+() ()|0()是的增函数( ), () 是 ()和 ()(,) 0的减函数证明：, 可推出 ()
4、=()+()(), 所以 120 (1)+1(1)(1)+1(2)(2)+2(2)(1)+2(1)(12)(1)(12)(2)(1)(2)(2)=(2)+2(2)(1)+2(1)(1)定理5.6假设同上述引理，则：1 若存在 使( ) = 0, 则 是() 在 上的全局最优0 点。2 设 ，若 时，集合 | 包含在的某个有界0 0闭子集中，且x是集合 | 某个子序列的极限点， 0则是()在 上的全局最优点，且lim+(0)=0罚函数的数值实现一般策略是取一个趋向无穷大严格递增正数列 ，从某个 开始， 0对每个k，数值计算min () + (),其中() 是罚函数, 常取,()=12()+=+1
5、0,()2从而得到一个极小点的序列 算法5.7 外点法计算步骤（SUMT）步1. 给定初始点 ，初始罚因子 0，内精度序列 0 | = 0, 0 0 1, ，且 ( +) ，外精度 0，置 0。 0步2. 以 为初始点，计算无约束优化问题min () + ()得 ， 使() 且( , ) ( , )。 步3. 若 ( ) (当 +时，应有 + )和新的 +1使 +1( +1, +1) ( , +1)(通常令 +1 = )，置 + 1 ， 返回步2。定理5.8在上述算法中，取() = + , =12() =+10,()2并设(), ( = 1, ,)均一阶连续可微， , () 0，*是算法产生的
6、序列 的一个聚点，+(+) =1 (*)( (*) )线性无关，则* 是KKT 点，且 ;lim+()=/2,lim+(),0=2,()其中 ( (*) )是对应的Lagrange乘子。内点法也称为障碍函数法，在迭代中总是从内点出发，并保持在可行域内搜索，只适合于不等式约束问题：min ()s.t. () 0, = 1, ., (5.14)其可行域为： = | () 0, = 1, , 其内点集合为： = | () 0, = 1, , 非空.算法5.9 内点法计算步骤步1. 给定初始内点(0) ，初始参数 ，缩小系数 1 ，允许1误差 0，置 := 1。步2. 以(1)为初始点，求解问题min (,) () + ()s.t. 设其极小点为 。()步3. 若 ( ) 0 使得 2 2对一切和 都成立,如果 对一切均成立,则上述SQP算 法产生的点列 之任何聚点都是问题(5.26) 的KT 点.
