第六章 约束优化方法

惩罚项 p x gi x ，当然也可以使用其他的方法来定义惩罚项，只要保证满 i 1 L




足前面所述的三个条件即可。 上述迭代算法的终止准则为 ，也可以改为 M k p x ( k )
外点罚函数法
收敛性分析
设 x x M k 为无约束优化问题 min F x, M k f x M k gi x 的最优解，那么： L
g 2 x x1 4 x2 2 0
首先需要引入松弛变量 x3 , x4 ，为了保证加入的数值为非负，则在不等式的左 边分别加上 x3 , x4 ，将不等式约束变为等式约束后问题变为：
min s.t.
2 f x 2 x12 2 x1 x2 2 x2 6 x1 2 g1 x 3x1 4 x2 x3 6 0 2 g 2 x x1 4 x2 x4 2 0
2
然后利用无约束的多变量函数寻优方法对 s 求极小值，即可得到原问题的最优 解。
拉格朗日乘子法
min 例2 用拉格朗日乘子法求解非线性规划问题 s.t. g1 x 3x1 4 x2 6 0
2 f x 2 x12 2 x1 x2 2 x2 6 x1
min F x, M k f x M k gi x
i 1 L
设其最优解为 x
(k )
xMk
(3) 计算 1 max hi x( k ) , 2 max gi x( k ) , max 1, 2 1i p 1i m (4) 若 ，输出 x* x( k ) ，算法终止；否则令 M k 1 cM k ， k k 1 ，转(2)

要构成初始复合形，实际上就是确定k个可行点作为
复合形的顶点，顶点数目一般在n+1≤k≤2n范围内。对于 维数较低的优化问题，因顶点数目较少，可以由设计者 自行凑出可行点作为复合形顶点。但对于维数较高的优 化问题，这种方法常常很困难。
为此，提出构成复合形的随机方法。该方法是先产
生k个随机点，然后再把那些非可行随机点调入可行域
x2
g4(X )≥0
X (2)
X (3)
X (R)
g1(X )≥0
o
X (s)
X (1) X (4)
g2(X )≥0
g3(X )≥0
x1
x2
X (R) X (2)
BACK
g4(X )≥0
X (R)
X (3)
X (R)
g1(X )≥0
o
X (s)
X (1) X (4)
g2(X )≥0
g3(X )≥0
我们设法将不在可行域内的随机点逐一调入可行域。 首先依次检查X ( 2 )、X ( 3 )、……X ( k )是否在可行域
内。在检查过程中，依次将可行点定义为X ( 2 )、X ( 3 )、 ……X ( q )，将不可行点定义为X ( q＋1)、X ( q＋2 )、……X ( K )。 首先将X ( q＋1)调入可行域。
这种方法可保证移动后的点一定会在可行域内，且 不会与原来的可行点重合。
∑ X (D)＝1
3
X (j)
3j=1
将非可行点调入可行域的几何表示
X(2)
X (3)
X(D)
X ′(4)
X (4)
D
X (1)
完全适用于可行域是凸集的情况，如为非凸 集，中心点可能不在可行域内，可以通过改变设计 变量的上限和下限值，重新产生各顶点来解决。经 过多次计算，有可能在可行域内生成初始复合形。

第六章
6.1 Kuhn-Tucker 条件
二、不等式约束问题的Khun-Tucker条件： （续） ●
目标函数f ( x)与g 1( x) 0相切的情况： I {1}, 则u 2 u 3 u 4 0 2( x1 3) 2 x1u1 0 解2( x 2 2) 2 x 2 u1 0 x2 x2 5 0 1 2 故均不是K T点 得(
若( fgh)为凸规划，满足可微性及CQ 则x l.opt. x 是K T点。
第六章
min f ( x) 1、问题：（P） s.t. Ax b x0 可行集：S {x | Ax b, x 0} 2、非退化假设： 1 A的任意m列线性无关；
g3=0 x2
▽g2(x*)
第六章
例
2 1
-▽f(x*) (3,2)T
x*
▽g1(x*)
1
2 3 g1=0
4
g4=0 x1 g2=0
6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续）
在x *点 g 1 ( x1 , x 2 ) 0 g 2 ( x1 , x 2 ) 0
计算可得 f ( x * )
1 3
* u1
1 3
* u2 2 3
2 3
使
g 1 ( x )
g 2 ( x ) 0
用K-T条件求解：
2( x1 3) 2 x1 f ( x ) , g ( x ) 1 2( x 2) 2x 2 2 1 0 g 3 ( x ) , g 4 0 1 1 , g ( 2 ) 2 2

混合法是综合外点法和内点法的优点建立的一种算法，对不等式约束条件按内 点法建立惩罚项，对等式约束条件按外点法建立惩罚项，由此得到惩罚函数：
m 1 2 X , rk1 , rk 2 f X rk1 rk 2 hv X u 1 g u X v 1 p
解：① 构造惩罚函数，转化为无约束最优化问题：
x1 x2 (可行域内) min X , rk 2 2 2 x x r x x r x 2 k 1 1 2 k 1


(可行域外)
② 求解无约束最优化问题，因为惩罚函数构造简单，可以直接用极值条件求解， 即令惩罚函数的一阶导数等于零：
李实cselisujneducn1教1007室济南大学控制科学与工程学院最优化方法61惩罚函数法63序列二次规划法64多目标最优化方法65matlab求解约束最优化问题66约束最优化问题应用实例济南大学控制科学与工程学院最优化方法33约束最优化方法是用来求解如下非线性约束最优化问题的数值迭代算法
第六章 约束最优化方法
f X 1 1.09
r2 0.25, rk 0,
f X 2 0.466
f X* 0

济南大学控制科学与工程学院
最优化方法
16
外点法的迭代路线如下图所示，向约束问题的最优点[0, 0]T逐步逼近 虚线②所示。
济南大学控制科学与工程学院
最优化方法
17
6.1.3 混合法
解，如惩罚函数法、乘子法、序列二次规划法。
济南大学控制科学与工程学院
最优化方法
2
6.1 惩罚函数法
惩罚函数法是一种将约束最优化问题转化为无约束最优化问题求解的算法。 对于约束最优化问题：