第十章 约束条件下多变量函数
的寻优方法
● 将非线性规划→线性规划
● 将约束问题→无约束问题
● 将复杂问题→较简单问题
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)点的微小摄动有某种限制作用。 等式约束对所有可行点都是起作用约束。
2．正则点
对问题(10.1.1)，若可行点X (1)处，各起作用约束的梯度线性无关，则X (1)是约束条件的一个正则点。
3．可行方向（对约束函数而言）
用R 表示问题(10.1.1)的可行域。设X (1)是一个可行点。对某方向D 来说，若存在实数λ1>0，使对于任意λ(0
▽g j (X(1)) T D>0 (j∈J ) (10.1.3)
即可保证它是点X (1)的可行方向。J 是X (1)点起作用约束下标的集合。
在X (1)点，可行方向D 与各起作用约束的梯度方向的夹角为锐角 ⋅ = ab cos θ 。
4．下降方向（对目标函数而言）
设X (1)是问题(10.1.1)的一个可行点。对X (1)的任一方向D 来说，若存在实数λ1>0，使对于任意λ(0
▽f(X(1)) T D
即可保证它为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*, „, λ*T m ) 及Γ*=(γ***T , γ, „, γ12l ) ，使得下述条件成立：
*∇f X -∑λ∇h i X -∑γ*∇g X =0j j **i *
i =1j =1()
j
j **m ()l ()(10. 1. 6) γ γg j (X*)=0 (j=1,2,„,l) (10.1.7) ≥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)的广义拉格朗日函数：
m ⎡⎢f (X )-∑λi h i X
i =1⎣()⎤-∑γj g j X ⎥
j =1⎦l ()
广义拉格朗日乘子：
λ
1*, λ2*, „, λ****m 及γ1, γ2, „, γl
2．求满足库恩—塔克条件的点（K-T 点）
例：求下列非线性规划问题的K-T 点
min f(X)=2x12+2x1x 2+x22-10x 1-10x 2
g 1(X)=5-x12-x 22≥0 (1)
g 2(X)=6-3x1-x 2≥0 (2)
解：设K-T 点为 X * = 1 ，
共有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 ⎡x ⎤⎢x ⎥⎣2⎦
三、 关于凸规划的全局最优解定理
对非线性规划(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*, „, λ*T m ) 及Γ*=(γ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)的严格局部极小点。 ⎧Z T ∇g j X *=0⎪T *Z ∇g X ≥0⎨j ⎪Z T ∇h X *=0i ⎩
Z T ()()()*j ∈J 且γ*j >0j J 且γ*j =0i =1, 2, , m *
i (10. 1. 9)(10. 1. 10)(10. 1. 11)[∇f (X )-∑λ2
i =1
m m ∇h i X -∑γ*j ∇2g j X *2*j =1()*l ()]Z 〉0(10. 1. 12) 其中，J 是点X *处起作用的不等式约束的下标j 的集合。 * 是广义拉格朗日函数 ∇ f ( X )- ∑ λ ∇ h i ( - ∑ γ *
j ()X )∇ 2g X j 2**i 2l
i =1j =1在点X 处的海赛矩阵。 *
令满足(10.1.9) 、(10.1.10) 、(10.1.11)三条件的非零向量Z 构成的子空间为M ，则(10.1.12)式表明，广义拉格朗日函数在点X *处的海赛矩阵在子空间M 上是正定的。
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)
X ∈R ⊂E n
其中，R 是可行域，E n 是n 维欧氏空间。f(X)、 h i (X) (i=1,2,„,m) 和g j (X) (j=1,2,„,l) 均存在一阶连续偏导数。
一. 基本原理和算法步骤
1．给定初始可行点X (1)，初始步长限制δ(1) j (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)
3．在上述近似线性规划的基础上，增加一组限制步长的线性约束后，求解之，得到最优解X (K+1)。由于线性近似通常只在展开点附近近似程度较高，故需限制变量取值范围： |xj -x j (k)|≤δ(k)j (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 (k)则所增约束的可行域
为矩形ABCD
x 1
4．检验X (k+1)点对原始约束是否可行？
若不可行，则缩小步长限制，令δ
返回步骤3
若可行，则转步骤5
5．判断精度
若|f(X(k+1))-f(X(k))|
或者|δ(k)j |
k=k+1，返回步骤2。 否则，令δ
δ(k)(k)(k) =δ置j j (j=1,2,„,n) ，的大小对算法影响很大，须根据初始点、函数性
态等进行选择。
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)
X ∈R ⊂E n
其中，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
定义罚函数 p 1(X , M )=f (X )+M ∑[h i (X )]
m 2i =1[h i (X )]为罚项。 其中，M 为罚因子（很大的正数）， M ∑ i =1
罚函数只对不满足约束条件的点进行惩罚。
2
(2) 对只有不等式约束的问题 min f(X)
g j (X)≥0 (j=1,2,„,l) 定义罚函数 p (X , M )=f (X )+M 2 (3) 对原问题(10.4.1) 定义罚函数
p (X , M )=f (X )+M {
l
j
j =1
∑[min (0, g (X ))]
2
2
∑[h i (X )]
i =1
m
2
+∑min (0, g j (X ))
j =1
l
[]}
罚函数还可以取其它形式。 2．算法步骤
(1) 任意给定初始点X (0)，初始罚因子M 1>0（例M 1=1）。放大系数C>1（例C=5或10），允许误差ε>0，令k=1。 (2) 求解罚函数p(X, Mk ) 的无约束极小。
以X (k-1)为初始点（或另给初始点），求解min p(X, Mk ) ，得其极小点X (k)。 (3) 判断精度
在X (k)点，若罚项
3. 外点法小结
(1) 适于求解各种一般的非线性规则问题 (2) 可任意给定初始点（不可行点也行）
(3) 求解时，必须先去掉罚函数中的“min ”（分多种情况讨论）
(4) Mk 表示惩罚力度，选得过大、过小都不好 (5) 序列无约束最小化方法与一般的迭代有区别 (6) 各次迭代得到的极小点X (k)组成的点列从可行域外部趋于原问题的极小点
二、内点法
非线性规划：min f(X)
g j (X)≥0 (j=1,2,„,l) R 1={X|gj (X)>0, j=1,2,„,l}
其中，f(X)和g j (X)都是连续函数，R 1是可行域中所有严格内点（即不包括可行域边界上的点）的集合。 ● 内点法适用于只含有不等式约束的问题 ● 初始点必须是严格内点
● 内点法在可行域边界上设置了一道“障碍”，阻止搜索点到可行域边界上去
1. 构造障碍函数（罚函数） 或
p (X , r k )=f (X )+r k ∑
j =1l l
1g j X p (X , r k )=f (X )-r k ∑lg (g j (X ))
j =1
l
1
r k ∑其中，r k 为障碍因子（很小的正数）， g X 或 j =1j l
X ) )为障碍项。 - r k ∑ lg ( g j (
j =1
2. 算法步骤
(1) 给定严格内点X (0)为初始点，初始障碍因子r 1>0，（例r 1=1），缩小系数β∈(0, 1)，（例β=0.1或0.2），允许误差 ε>0，令k=1
(2) 求解障碍函数p(X，r k ) 的无约束极小
以X (k-1)为初始点，或任意给定一个严格内点做初始点，
( X )（R 1是可行域中所有严格内点的集合） p , r k
求解 min X ∈ R
1
得其极小点X (k)。 (3) 判断精度
在X (k)点，若障碍项
否则，令r k+1=βr k ，k =k+1，返回步骤(2)。
3. 初始内点的求法（采用“内点法”）
(1) 任意给定初始点X (1)∈E n ，初始障碍因子r 1>0（例r 1=1），缩小系数β∈(0, 1)（例β=0.1或0.2），令k=1 (2) 对X (k)点，确定不等式约束的下标集合T k 、S k 及可行域R 1、R k
T k ={j| gj (X(k))>0 1≤j ≤l} S k ={j| gj (X(k)) ≤0 1≤j ≤l} R k ={X| gj (X)>0 j ∈T k } R 1={X| gj (X)>0 j=1,2,„,l}
(3) 若S k =Ф（空集），则X (k)∈R 1 ，X (k)即为初始内点，停止搜索。否则，转步骤(4)。 (4) 构造障碍函数
Q (X , r k )=-∑g j (X )+r k ∑
j ∈S k
1
j ∈T k g j X (r k >0)
对照前述内点法中的障碍函数，这里Q(X, r k ) 的第一项可看作虚拟目标函数，它由g j (X)≤0的那些约束函数之和的相反数组成，其最小值为0。Q(X, rk ) 的第二项可看作虚拟约束条件，它由满足g j (X)>0的那些约束条件组成，即在R k 域的边界上设置了一道“障碍”，它阻止已得到满足的约束条件再变为不满足。
(5) 以X (k)为初始点，在R K 域内，求障碍函数Q(X, rk ) 的无约束极小，得其极小点X (k+1)∈R k 。
(6) 减小r k ，令r k+1=βr k ，置k=k+1，返回步骤(2)。 其实，求初始内点的过程，就是在R k 域内，反复使用内点法的过程。随着得到满足的约束条件个数的增加，R k 域逐渐缩小以趋近于R 1域。
三、 混合法
1. 混合法，即外点法与内点法结合使用。
对等式约束和当前不被满足的不等式约束，使用外点法（构造罚函数）；对已满足的那些不等式约束，使用内点法（构造障碍函数）。 2. 构造罚函数
1⎧m 22⎫
p (X , r k )=f (X )+⎨∑[h i (X )]+∑min (0, g j (X ))⎬-r k ∑ln (g j (X ))r k ⎩i =1j ∈S k j ∈T k ⎭
[]
(r k >0)
其中 T k ={j | gj (X(k))>0 1≤j ≤l}
S k ={j | gj (X(k)) ≤0 1≤j ≤l}
作业：P.190/4.10 , 4.12(求出一个新的下降的可行点即可) 补充题:试用SUMT 的外点法求解下列问题 min f(x ) = x12 + x 22 x 1 ≤ 2 x 2 = 1
第十章 约束条件下多变量函数
的寻优方法
● 将非线性规划→线性规划
● 将约束问题→无约束问题
● 将复杂问题→较简单问题
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)点的微小摄动有某种限制作用。 等式约束对所有可行点都是起作用约束。
2．正则点
对问题(10.1.1)，若可行点X (1)处，各起作用约束的梯度线性无关，则X (1)是约束条件的一个正则点。
3．可行方向（对约束函数而言）
用R 表示问题(10.1.1)的可行域。设X (1)是一个可行点。对某方向D 来说，若存在实数λ1>0，使对于任意λ(0
▽g j (X(1)) T D>0 (j∈J ) (10.1.3)
即可保证它是点X (1)的可行方向。J 是X (1)点起作用约束下标的集合。
在X (1)点，可行方向D 与各起作用约束的梯度方向的夹角为锐角 ⋅ = ab cos θ 。
4．下降方向（对目标函数而言）
设X (1)是问题(10.1.1)的一个可行点。对X (1)的任一方向D 来说，若存在实数λ1>0，使对于任意λ(0
▽f(X(1)) T D
即可保证它为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*, „, λ*T m ) 及Γ*=(γ***T , γ, „, γ12l ) ，使得下述条件成立：
*∇f X -∑λ∇h i X -∑γ*∇g X =0j j **i *
i =1j =1()
j
j **m ()l ()(10. 1. 6) γ γg j (X*)=0 (j=1,2,„,l) (10.1.7) ≥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)的广义拉格朗日函数：
m ⎡⎢f (X )-∑λi h i X
i =1⎣()⎤-∑γj g j X ⎥
j =1⎦l ()
广义拉格朗日乘子：
λ
1*, λ2*, „, λ****m 及γ1, γ2, „, γl
2．求满足库恩—塔克条件的点（K-T 点）
例：求下列非线性规划问题的K-T 点
min f(X)=2x12+2x1x 2+x22-10x 1-10x 2
g 1(X)=5-x12-x 22≥0 (1)
g 2(X)=6-3x1-x 2≥0 (2)
解：设K-T 点为 X * = 1 ，
共有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 ⎡x ⎤⎢x ⎥⎣2⎦
三、 关于凸规划的全局最优解定理
对非线性规划(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*, „, λ*T m ) 及Γ*=(γ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)的严格局部极小点。 ⎧Z T ∇g j X *=0⎪T *Z ∇g X ≥0⎨j ⎪Z T ∇h X *=0i ⎩
Z T ()()()*j ∈J 且γ*j >0j J 且γ*j =0i =1, 2, , m *
i (10. 1. 9)(10. 1. 10)(10. 1. 11)[∇f (X )-∑λ2
i =1
m m ∇h i X -∑γ*j ∇2g j X *2*j =1()*l ()]Z 〉0(10. 1. 12) 其中，J 是点X *处起作用的不等式约束的下标j 的集合。 * 是广义拉格朗日函数 ∇ f ( X )- ∑ λ ∇ h i ( - ∑ γ *
j ()X )∇ 2g X j 2**i 2l
i =1j =1在点X 处的海赛矩阵。 *
令满足(10.1.9) 、(10.1.10) 、(10.1.11)三条件的非零向量Z 构成的子空间为M ，则(10.1.12)式表明，广义拉格朗日函数在点X *处的海赛矩阵在子空间M 上是正定的。
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)
X ∈R ⊂E n
其中，R 是可行域，E n 是n 维欧氏空间。f(X)、 h i (X) (i=1,2,„,m) 和g j (X) (j=1,2,„,l) 均存在一阶连续偏导数。
一. 基本原理和算法步骤
1．给定初始可行点X (1)，初始步长限制δ(1) j (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)
3．在上述近似线性规划的基础上，增加一组限制步长的线性约束后，求解之，得到最优解X (K+1)。由于线性近似通常只在展开点附近近似程度较高，故需限制变量取值范围： |xj -x j (k)|≤δ(k)j (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 (k)则所增约束的可行域
为矩形ABCD
x 1
4．检验X (k+1)点对原始约束是否可行？
若不可行，则缩小步长限制，令δ
返回步骤3
若可行，则转步骤5
5．判断精度
若|f(X(k+1))-f(X(k))|
或者|δ(k)j |
k=k+1，返回步骤2。 否则，令δ
δ(k)(k)(k) =δ置j j (j=1,2,„,n) ，的大小对算法影响很大，须根据初始点、函数性
态等进行选择。
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)
X ∈R ⊂E n
其中，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
定义罚函数 p 1(X , M )=f (X )+M ∑[h i (X )]
m 2i =1[h i (X )]为罚项。 其中，M 为罚因子（很大的正数）， M ∑ i =1
罚函数只对不满足约束条件的点进行惩罚。
2
(2) 对只有不等式约束的问题 min f(X)
g j (X)≥0 (j=1,2,„,l) 定义罚函数 p (X , M )=f (X )+M 2 (3) 对原问题(10.4.1) 定义罚函数
p (X , M )=f (X )+M {
l
j
j =1
∑[min (0, g (X ))]
2
2
∑[h i (X )]
i =1
m
2
+∑min (0, g j (X ))
j =1
l
[]}
罚函数还可以取其它形式。 2．算法步骤
(1) 任意给定初始点X (0)，初始罚因子M 1>0（例M 1=1）。放大系数C>1（例C=5或10），允许误差ε>0，令k=1。 (2) 求解罚函数p(X, Mk ) 的无约束极小。
以X (k-1)为初始点（或另给初始点），求解min p(X, Mk ) ，得其极小点X (k)。 (3) 判断精度
在X (k)点，若罚项
3. 外点法小结
(1) 适于求解各种一般的非线性规则问题 (2) 可任意给定初始点（不可行点也行）
(3) 求解时，必须先去掉罚函数中的“min ”（分多种情况讨论）
(4) Mk 表示惩罚力度，选得过大、过小都不好 (5) 序列无约束最小化方法与一般的迭代有区别 (6) 各次迭代得到的极小点X (k)组成的点列从可行域外部趋于原问题的极小点
二、内点法
非线性规划：min f(X)
g j (X)≥0 (j=1,2,„,l) R 1={X|gj (X)>0, j=1,2,„,l}
其中，f(X)和g j (X)都是连续函数，R 1是可行域中所有严格内点（即不包括可行域边界上的点）的集合。 ● 内点法适用于只含有不等式约束的问题 ● 初始点必须是严格内点
● 内点法在可行域边界上设置了一道“障碍”，阻止搜索点到可行域边界上去
1. 构造障碍函数（罚函数） 或
p (X , r k )=f (X )+r k ∑
j =1l l
1g j X p (X , r k )=f (X )-r k ∑lg (g j (X ))
j =1
l
1
r k ∑其中，r k 为障碍因子（很小的正数）， g X 或 j =1j l
X ) )为障碍项。 - r k ∑ lg ( g j (
j =1
2. 算法步骤
(1) 给定严格内点X (0)为初始点，初始障碍因子r 1>0，（例r 1=1），缩小系数β∈(0, 1)，（例β=0.1或0.2），允许误差 ε>0，令k=1
(2) 求解障碍函数p(X，r k ) 的无约束极小
以X (k-1)为初始点，或任意给定一个严格内点做初始点，
( X )（R 1是可行域中所有严格内点的集合） p , r k
求解 min X ∈ R
1
得其极小点X (k)。 (3) 判断精度
在X (k)点，若障碍项
否则，令r k+1=βr k ，k =k+1，返回步骤(2)。
3. 初始内点的求法（采用“内点法”）
(1) 任意给定初始点X (1)∈E n ，初始障碍因子r 1>0（例r 1=1），缩小系数β∈(0, 1)（例β=0.1或0.2），令k=1 (2) 对X (k)点，确定不等式约束的下标集合T k 、S k 及可行域R 1、R k
T k ={j| gj (X(k))>0 1≤j ≤l} S k ={j| gj (X(k)) ≤0 1≤j ≤l} R k ={X| gj (X)>0 j ∈T k } R 1={X| gj (X)>0 j=1,2,„,l}
(3) 若S k =Ф（空集），则X (k)∈R 1 ，X (k)即为初始内点，停止搜索。否则，转步骤(4)。 (4) 构造障碍函数
Q (X , r k )=-∑g j (X )+r k ∑
j ∈S k
1
j ∈T k g j X (r k >0)
对照前述内点法中的障碍函数，这里Q(X, r k ) 的第一项可看作虚拟目标函数，它由g j (X)≤0的那些约束函数之和的相反数组成，其最小值为0。Q(X, rk ) 的第二项可看作虚拟约束条件，它由满足g j (X)>0的那些约束条件组成，即在R k 域的边界上设置了一道“障碍”，它阻止已得到满足的约束条件再变为不满足。
(5) 以X (k)为初始点，在R K 域内，求障碍函数Q(X, rk ) 的无约束极小，得其极小点X (k+1)∈R k 。
(6) 减小r k ，令r k+1=βr k ，置k=k+1，返回步骤(2)。 其实，求初始内点的过程，就是在R k 域内，反复使用内点法的过程。随着得到满足的约束条件个数的增加，R k 域逐渐缩小以趋近于R 1域。
三、 混合法
1. 混合法，即外点法与内点法结合使用。
对等式约束和当前不被满足的不等式约束，使用外点法（构造罚函数）；对已满足的那些不等式约束，使用内点法（构造障碍函数）。 2. 构造罚函数
1⎧m 22⎫
p (X , r k )=f (X )+⎨∑[h i (X )]+∑min (0, g j (X ))⎬-r k ∑ln (g j (X ))r k ⎩i =1j ∈S k j ∈T k ⎭
[]
(r k >0)
其中 T k ={j | gj (X(k))>0 1≤j ≤l}
S k ={j | gj (X(k)) ≤0 1≤j ≤l}
作业：P.190/4.10 , 4.12(求出一个新的下降的可行点即可) 补充题:试用SUMT 的外点法求解下列问题 min f(x ) = x12 + x 22 x 1 ≤ 2 x 2 = 1