第十章约束条件下多变量函数的寻优方法●将非线性规划→线性规划●将约束问题→无约束问题●将复杂问题→较简单问题10．1约束极值问题的最优性条件非线性规划：min f(X)h i(X)=0 (i=1,2,…,m) (10.1.1)g j(X)≥0 (j=1,2,…,l)一、基本概念1．起作用约束设X(1)是问题(10.1.1)的可行点。

对某g j(X)≥0而言：或g j(X(1))=0：X(1)在该约束形成的可行域边界上。

该约束称为X(1)点的起作用约束。

或g j(X(1))＞0：X(1)不在该约束形成的可行域边界上。

该约束称为X(1)点的不起作用约束。

X(1)点的起作用约束对X(1)点的微小摄动有某种限制作用。

等式约束对所有可行点都是起作用约束。

()θcos ab b a =⋅ 2．正则点对问题(10.1.1)，若可行点X (1)处，各起作用约束的梯度线性无关，则X (1)是约束条件的一个正则点。

3．可行方向（对约束函数而言）用R 表示问题(10.1.1)的可行域。

设X (1)是一个可行点。

对某方向D 来说，若存在实数λ1>0，使对于任意λ(0<λ<λ1)均有X (1)+λD ∈R ，则称D 是点X (1)处的一个可行方向。

经推导可知，只要方向D 满足：▽g j (X (1))T D>0 (j ∈J ) (10.1.3)即可保证它是点X (1)的可行方向。

J 是X (1)点起作用约束下标的集合。

在X (1)点，可行方向D 与各起作用约束的梯度方向的夹角为锐角 。

4．下降方向（对目标函数而言）设X (1)是问题(10.1.1)的一个可行点。

对X (1)的任一方向D 来说，若存在实数λ1>0，使对于任意λ(0<λ<λ1)均有f(X (1)+λD)<f(X (1))，就称D 为X (1)点的一个下降方向。

经推导可知，只要方向D 满足：▽f(X (1))T D<0 (10.1.5)即可保证它为X (1)点的下降方向。

在X (1)点，下降方向D 与该点处目标函数的负梯度方向的夹角为锐角。

5．可行下降方向在可行点X(1)处，若方向D同时满足(10.1.3)和(10.1.5)，则它是X(1)点的可行下降方向。

若X(1)点不是极小点，继续搜索的方向应该从该点的可行下降方向中去找。

若某点存在可行下降方向，则它不会是极小点。

若某点是极小点，则该点不存在可行下降方向。

二、库恩—塔克条件（一阶必要条件）●它是非线性规划最重要的理论成果之一。

●只要是最优点（且为正则点）就必然满足它。

●满足它的点不一定是最优点（不是充分条件）。

●对凸规划而言，它是最优点的充要条件。

1．库恩—塔克条件对非线性规划(10.1.1)而言，若X*是局部（或全局）极小点且为上述约束条件的正则点，则一定存在向量∧*=(λ1*,λ2*,…,λm *)T 及Γ*=(γ1*,γ2*,…,γl *)T ，使得下述条件成立：γj*g j (X *)=0 (j=1,2,…,l) (10.1.7) γj *≥0 (j=1,2,…,l) (10.1.8)● 共有n+m+l 个未知量（X ，∧*，Γ*）● 可列n+m+l 个方程（其中有m 个等式约束方程）● 由(10.1.7)知，在X *点不起作用约束g j (X *)>0 ,相应的γj *=0● “正则点”是K-T 条件所必须的,但不是最优点所必须的。

问题(10.1.1)的广义拉格朗日函数：广义拉格朗日乘子：λ1*,λ2*,…,λm *及γ1*,γ2*,…,γl *()()())6.1.10(01**1***=∇-∇-∇∑∑==l j j j m i i i X g X h X f γλ()()()⎥⎦⎤⎢⎣⎡--∑∑==l j j j m i i i X g Xh X f 11γλ⎥⎦⎤⎢⎣⎡=21*x x X2．求满足库恩—塔克条件的点（K-T 点）例：求下列非线性规划问题的K-T 点min f(X)=2x 12+2x 1x 2+x 22-10x 1-10x 2g 1(X)=5-x 12-x 22≥0 (1)g 2(X)=6-3x 1-x 2≥0 (2)解：设K-T 点为 ，共有4个未知数x 1，x 2，γ1，γ2由(10.1.6)及(10.1.7)各列出2个方程。

因只有2个不等式约束，可分4种情况讨论：(1) 两约束均不起作用：有γ1=γ2=0(2) 约束(1)起作用，约束(2)不起作用：有γ2=0(3) 约束(1)不起作用，约束(2)起作用：有γ1=0(4) 两约束均起作用：有γ1>0，γ2>0 三、 关于凸规划的全局最优解定理对非线性规划(10.1.1)而言，若f(X)是凸函数，g j (X)（j=1,2,…,l ）是凹函数，h i (X) (i=1,2,…,m)是线性函数，可行域为R ，X *∈R,且在X *处有库恩—塔克条件(10.1.6)、(10.1.7)、(10.1.8)成立，则X *是全局最优解。

● 上述R 是凸集，f(X)是凸函数，故为凸规划问题。

● 对凸规划而言，K-T 条件是局部极小点的充要条件，且局部极小点即全局极小点。

四、 二阶充分条件1．二阶充分条件对非线性规则(10.1.1)而言，若f(X)、g j (X) (j=1,2,…,l)、h i (X)(i=1,2,…,m)二次连续可微，X *是可行点，又存在向量 ∧*=(λ1*,λ2*,…,λm *)T 及Γ*=(γ1*,γ2*,…,γl *)T ，使库恩—塔克条件(10.1.6)、(10.1.7)、(10.1.8)成立，且对满足下述(10.1.9) 、(10.1.10)、 (10.1.11)三条件的任意非零向量Z 有(10.1.12)成立， 则X *是问题(10.1.1)的严格局部极小点。

其中，J 是点X *处起作用的不等式约束的下标j 的集合。

是广义拉格朗日函数在点X *处的海赛矩阵。

令满足(10.1.9) 、(10.1.10) 、(10.1.11)三条件的非零向量Z 构成的子空间为M ，则(10.1.12)式表明，广义拉格朗日函数在点X *处的海赛矩阵在子空间M 上是正定的。

()()()()()()[()()()])12.1.10(011.1.10,,2,1010.1.10009.1.10001*2*1*2**2*****〉∇-∇-∇⎪⎩⎪⎨⎧==∇=∈≥∇>∈=∇∑∑==Z X g X h X f Z m i X h Z J j X g Z J j X g Z l j j j m i i i T i T j j T j j T γλγγ 且且()()()∑∑==∇-∇-∇lj j j m i i i X g X h X f 1*2*1*2**2γλ2．利用K-T条件和二阶充分条件求约束极小(1) 第一种情况若能用其它方法先求出一个点X*，这个点是约束极小的可能性很大。

不妨先假设其为约束极小，再逐一证明之。

①证明X*是可行点②证明X*是正则点③把X*代入K-T条件(10.1.6) 、(10.1.7)、(10.1.8)式中，应能求出符合条件的向量∧*和Γ*。

④证明广义拉格朗日函数在点X*处的海赛矩阵正定（在子空间M上）若能证明上述四点，则X*是一个严格局部极小点。

(2)第二种情况若不能先求出一个可能极小点的具体值，就先求出满足K-T条件的点X*，再证明④，则X*是一个严格局部极小点。

10．2近似规划法近似规划法（MAP ），亦称小步梯度法，它把非线性规划的求解变为一系列近似线性规划的求解。

非线性规则：min f(X)h i (X)=0 (i=1,2 ,…,m) (10.2.1)g j (X)≥0(j=1,2,…,l)其中，R 是可行域，E n 是n 维欧氏空间。

f(X)、 h i (X) (i=1,2,…,m)和g j (X) (j=1,2,…,l)均存在一阶连续偏导数。

一. 基本原理和算法步骤1．给定初始可行点X (1)，初始步长限制δj (1) (j=1,2,…,n)，步长缩小系数β∈(0,1)，允许误差ε1，ε2，令k=1。

2．在点X (K)处，将f(X)、h i (X)、g j (X)按泰勒级数展开并取一阶近似，得到近似线性规划问题：min f(X)≈f(X (k))+▽f(X (k))T (X-X (k))h i (X)≈h i (X (k))+▽h i (X (k))T (X-X (K))=0 (i=1,2,…,m) g j (X)≈g j (X (k))+▽g j (X (K))T (X-X (k))≥0 (j=1,2,…,l)nE R X ⊂∈(k) 3．在上述近似线性规划的基础上，增加一组限制步长的线性约束后，求解之，得到最优解X (K+1)。

由于线性近似通常只在展开点附近近似程度较高，故需限制变量取值范围： |x j -x j (k)|≤δj (k) (j=1,2,…,n)即 -δ1(k)≤x 1-x 1(k)≤δ1(k)-δ2(k)≤x 2-x 2(k)≤δ2(k). . . . . .例如二维问题：已知X (k)=(3,1.5)T ，δ(k)=(2,0.5)T 则所增约束的可行域为矩形ABCD4．检验X (k+1)点对原始约束是否可行？若不可行，则缩小步长限制，令δj (k)=βδj (k) (j=1,2,…,n)， 返回步骤3若可行，则转步骤55．判断精度若|f(X (k+1))-f(X (k))|<ε1，且|| X (k+1) -X (k)||<ε2，或者|δj (k)| <ε2 (j=1,2,…,n)，则X (k+1)为近似最优解；否则，令δj (k)=δj (k) (j=1,2,…,n)，置k=k+1，返回步骤2。

δ(k)的大小对算法影响很大，须根据初始点、函数性态等进行选择。

x 1()()()[]211,∑=+=mi i X h M X f M X p ()[]21∑=m i i X h M 10．4罚函数法● 通过构造罚函数，把约束问题转化为一系列无约束问题去求解。

● 该方法也叫序列无约束最小化方法（SUMT ）● 不必计算导数● 罚函数法分为外点法、内点法、混和法一、 外点法非线性规则：min f(X)h i (X)=0 (i=1,2,…,m) (10.4.1) g j (X)≥0 (j=1,2,…,l)其中，f(X)、h i (X)和g j (X)是E n 上的连续函数，R 是可行域。

1．构造罚函数罚函数由目标函数和约束函数组成，求罚函数极小（无约束寻优）即可。

(1) 对只有等式约束的问题min f(X)h i (X)=0 (i=1,2,…,m)定义罚函数 其中，M 为罚因子（很大的正数）， 为罚项。