ch9 最优性条件与二次规划.ppt

《ch9 最优性条件与二次规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、约束极值问题-1内容概要1最优性条件1.1不起作用约束与起作用约束1.2可行下降方向1.3K-T条件2二次规划1.1基本思想1.2基本原理1.3算法步骤1.4例子1.5算法特点约束极值问题求解策略约束问题化为无约束问题非线性规划问题化为线性规划问题复杂问题化为简单问题1最优性条件设X(0)是线性规划的一个可行解，现考虑某一不等式约束条件gi(X)≥0，当满足gi(X(0))>0，称该约束条件是点X(0)的不起作用约束;当gi(X(0))=0，此时该约束条件对X(0)的摄动起到了某种限制作用，称该约束是点X(0)

2、的起作用约束。1.1不起作用约束与起作用约束可行方向假定X(0)是非线性规划的一个可行点，现考虑此点的某一方向D，若存在实数，使对任意λ∈[0，λ0]均有，称方向D是点X(0)的一个可行方向。（分起作用约束和不起作用约束讨论）1.2可行下降方向g1(X)=0g2(X)=0g2(X(0))g1(X(0))X(0)D起作用约束可行方向图示下降方向考虑是非线性规划的一个可行点X(0)，对该点的任一方向D来说，若存在实数，是对任意λ∈[0，λ’0]均有，就称方向D为点X(0)的一个下降方向。如果方向D既是点X(0)的可

3、行方向，又是这个点的下降方向，就称它是该点的可行下降方向。定理设X*是非线性规划的一个局部极小点，目标函数f(X)在X*处可微，而且gi(x)在X*处可微，当j∈Jgi(x)在X*处连续，当jJ则在X*点不存在可行下降方向，从而不存在向量D同时满足：几何意义：满足该条件的方向D，与点X*处目标函数负梯度方向的夹角为锐角，与点X*处起作用约束梯度方向的夹角也为锐角。1.3库恩-塔克条件(K-T条件)等式约束，极值存在的条件：g1(X)-f(X)g1(X*)-f(X*)有一个起作用约束，极值点存在的条件：g1(X*

4、)-f(X*)g2(X*)有两个起作用约束，极值点存在的条件：g1(X*)-f(X*)g2(X*)gn(X*)有t个起作用约束，极值点存在的条件：对于不起作用约束，相当于无约束问题，极值点存在的条件：有l-t-1个不起作用约束，则极值点存在的条件：设X*是非线性规划的极小点，而且与X*点的各起点作用约束的梯度线性无关，则存在向量，使下述条件成立：不等式约束（起作用与不起作用约束），极值点存在的条件：上述条件常简称为K-T条件。满足这个条件的点称为库恩-塔克点（或K-T点）既有等式约束，又有不等式约束，极值点存在

5、的条件：例子也可以讨论变量等于或不等于零，如二维变量，两个以上乘子。2二次规划若某非线性规划的目标函数为自变量X的二次函数，约束条件全是线性的，就称这种规划为二次规划。二次型二次规划的数学模型：例子且该线性规划应满足如果二次型正定（或半正定），则目标函数为严格凸函数（或凸函数），且二次规划的可行域为凸集，则此二次规划属于凸规划。凸规划的局部极值即为全局极值。对于凸规划，K-T条件为极值点存在的充要条件。