运筹学教案（Word版）--§4-5约束最优化方法.doc

§
(MP)
其中,
1、约束问题的最优性条件
令则对任意,有
称使的约束为点的一个积极约束。点的所有积极约束的下标集记为

比如
显然是该问题的一个可行点。所以
设和在点处可微,在点处连续,在点处连续可微,并且各线性无关。若是(MP)的局部最优解,则存在两组实数和,使得
()
()称为(MP)的 Kuhn-Tucker条件,简称为 K-T条件。凡是满足K-T条件()的点可行叫做(MP)的K-T点。
注:很多约束最优化方法就是寻找(MP)的K-T点。
若进一步要求每个在点处都可微,则(MP)的K-T条件可写为更简便的形式
()
其中称为互补松紧条件。
注:对没限制。
引进(MP)的Lagrange函数
其中,叫做Lagrange乘子。
则(MP)的K-T条件()可写
()
定理 对于(MP)问题,若在点处连续可微,可行点满足(MP)的K-T条件,且是凸函数,是线性函数,则是(MP)的整体最优解。
用K-T条件解下列问题
()
解:问题()的Lagrange函数为
所以

因此,问题()的K-T条件是
作为K-T点还应满足可行性条件
利用互补松紧条件进行讨论
(I)若,则由互补松紧条件知
再加上可行性条件中的一个方程

可解得。再由互补松紧条件知。将这些值代入K-T条件的前两个方程有
解得。经检验,均满足()的K-T条件和可行性条件,因而为其K-T点
(II)若此时第一个互补松紧条件失效,需利用其它互补松紧条件。
(1)若则由互补松紧条件知由可行性条件知。再由互补松紧条件知。将这些值代入K-T条件的前两个方程有
解得与矛盾。
(2)若此时前两个互补松紧条件失效,需利用第三个互补松紧条件。
<1> 若则由互补松紧条件知由可行性条件知。与矛盾。
<2> 若将这些值代入K-T条件的前两个方程有
再加上可行性条件中的一个方程

可解得与矛盾。
综上分析,问题()只有一个K-T点。易验证均为凸函数,而为线性函数,()的整体最优解。
注:(该问题可以对进行分类)要充分利用互补松紧条件进行分类讨论。若是寻找问题的K-T点,则需要将所有可能的分类都进行讨论;若是求问题的最优解,则找到第一个K-T点时就可以结束了。
3、惩罚函数法
(MP)
思想:利用问题中的约束函数做出适当的带有参数的惩罚函数,然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数,把(MP)问题的求解转换为求解一系列无约束非线性规划问题。
类型:罚函数法(外部惩罚法)
障碍函数法(内部惩罚法)
(1)罚函数法
原始想法:设法适当加大不可行点的目标函数值,使不可行点不能成为相应无约束极小化问题的最优解。具体地说,是预先选定一个很大的正数,构造如下的罚函数

利用罚函数构造一个增广的目标函数。则在可行点处与的值相同,而在不可行点处的值很大。所以,以增广目标函数为目标函数的无约束极小化问题

的最优解,必定是(MP)问题的最优解。
修改