最优性条件
等式约束问题
不等式约束问题
定义:起作用约束标号集 ,将容许点带入s等于零的s的序号集合,比如{1,2},容许点带入s等于零的s被称作起作用约束
不等式的FJ条件
不等式的KT条件
KT条件在FJ条件的前提下要求 起作用约束条件的梯度即 非线性相关
例题:
一般约束问题
同时具有等式约束和不等式约束
与不等式约束相似,一般约束问题的FJ和KT条件在不等式约束的基础上添加了等式部分,即h和,不同的是等式部分一定为起作用约束
FJ条件
KT条件
例题:
Zoutendijk 容许方向法
容许方向法是求解约束最优化问题的一类基本方法。这类方法一般先从线性约束问题开始讨论,然后再推广到非线性约束问题。它的基本迭代格式是
下降容许方向的确定
非零向量 为点的容许方向向量的充要条件是满足
是等式约束的系数矩阵, 是不等式约束的起作用约束部分系数矩阵
若p还满足,那么p是下降容许方向向量
确认p是否为下降容许向量,即求下式最优值,其中e为分量全为1的n维向量,即
该式最优值非正, 若最优值<0,则p是下降容许方向向量, 若最优值=0,则容许点x是KT点
直线搜索
是不等式约束的不起作用约束部分系数矩阵
终止条件
算法
例题见书p245
外部罚函数法
其中是阶跃函数
若无约束问题(4.79)的极小点x 是约束问题(4.67)的容许点(即),则x也是约束问题(4.67)的极小点,表明约束不起作用,这时只解一次无约束问题(4.80)就能求到约束问题(4.67)的极小点
若不是容许点(即),则x不是约束问题(4.67)的极小点,表明约束对极小点的求解有影响,这时就要解一系列无约束问题(4.80),得到的极小点序列{ }向容许集靠近,向(4.67)的极小点逼近
算法
例子
乘子法
乘子法解决了外部罚函数法因罚因子增大导致的数值计算不稳定问题,是外部罚函数法的一种改进方法.
乘子法是在约束问题的 Lagrange 函数上加入惩罚,罚因子因此不必趋于无穷大,数值计算稳定性有保证.
等式约束问题
如果无约束问题(4.121)的最优解x 是(4.109)的容许点,那么x 是(4.109)的最优解,且参数$\lambda =\lambda^, μ=μ^ $
终止准则
算法:
例子
不等式约束问题
例子
一般约束问题
算法