最优第五章

最优化
学科专业：控制理论与控制工程 授课教师：徐宝昌 院 系：自动化
第一部分 最优化理论与应用
1 2 3 4 5
引论 线性规划 最优性条件 无约束最优化方法 有约束优化方法
第五章 有约束优化方法
惩罚函数法 碰壁函数法 乘子法 二次规划方法
§5.1惩罚函数法
约束优化问题： ⎧
min f ( x) ⎪ s.t. g ( x) ≤ 0(i = 1,2,L m) ⎪ i ⎨ h j ( x) = 0( j = 1,2, L p) ⎪ ⎪ x = ( x1 , x2 ,L xn )T ⎩
(k ) j =1 j =1
p
p
即：
∇f ( x
(k )
) + ∑ (u j
j =1
p
(k )
+ ch j ( x ( k ) ))∇h j ( x ( k ) ) = 0
（5-10）
§5.3 乘子法
§5.3 乘子法
§5.3 乘子法
§5.3 乘子法
二、Rockafellar的乘子法（对不等式约束）
f ( x) ⎧min （5-13） ⎨ ⎩ s.t. g j ( x) ≥ 0, i = 1,2,L, p 引入松弛变量 z i (i = 1,L, p)，将不等式约束化为等式约束
⎧min ⎪ ⎨ ⎪s.t. ⎩ f ( x) g j ( x) − z j = 0, j = 1,2,L, p
2
再利用前面的针对等式约束的乘子法构造lagrange函数
§5.2 碰壁函数法
四、混合罚函数法：
对于缺点（3），可利用混合惩罚函数法进行解决，即用 内点法与外点法相结合，当 x( 0)给定后，对 x( 0)满足的那些 不等式约束，按内点法构造碰壁函数B(x)，对 x( 0)不满足 的不等式约束和等式约束，按外点法构造惩罚函数p(x),即 混合惩罚函数为： 1 F ( x, γ k ) = f ( x ) + γ k B ( x ) + p Nhomakorabea x) γk
若 G > 0 ，则（8-1）为正定凸QP问题，只要存在全局最优 解，则它是唯一的，若G不定，则（8-1）为一个一般的QP 问题。 有效约束（起作用约束）：设 X 是（8-1）的可行解，若 某个 i ∈ {1,2, L p}，使得 aiT X = bi 成立，则称它为点 X处的 有效约束。 有效约束指标集：在点 X 处所有有效约束的指标组成的集 合J = J ( X ) = {i | aiT X = bi }；
x<2
利用无约束优化方法求解 F (x) 的极小点
dF ⎧1 =⎨ dx ⎩1 − 2M (2 − x) x≥2 x<2
dF 1 ∗ = 0 ⇒ xM = 2 − dx 2M
∗ M越大，则 xM 越接近问题的最优解，当M → +∞时 ∗ xM → x ∗ = 2
§5.1惩罚函数法
∗ M > 0 − ⇒ x M < 2 ，即 xM 在可行集外
§5.1惩罚函数法
p(x)需满足：(1)连续的;
( 2)对∀x ∈ R n , p ( x ) ≥ 0; (3)当且仅当 x ∈ S时， p ( x ) = 0;
n
S为可行集。S = {x g i ( x) ≤ 0, h j ( x) = 0, x ∈ R 对等式约束定义：
g j ( x) = (h j ( x)) 2 , j = 1,2,L p
+ i =1 L
(5-5)
§5.1惩罚函数法
§5.1惩罚函数法
min x 例： s.t. − x + 2 ≤ 0
可行集 x ≥ 2
x≥2
令
x<2 则 x≥2 ⎧x F ( x) = x + M • p( x) = ⎨ x + M (2 − x) 2 ⎩
⎧0 p( x) = ⎨ (2 − x) 2 ⎩
c p φ ( x, z , μ ) = f ( x ) + ∑ μ j ( g j ( x ) − z ) + ∑ ( g j ( x ) − z 2 ) 2 j 2 j =1 j =1
2 j − p
（5-14）
将φ对z求极小，由此解出z，代入（5-14）中，从而将z消 去。 − min φ ( x, z , μ )
min f ( x) + M k p( x), M 1 < M 2 < L M k , lim M k = +∞
n→∞
从而得到极小点的序列 {xM 计算步骤：
∗
k
}
x(0)，初始惩罚因子 M 1, 放大系数 c > 1, ε > 0, k = 1 (1) 给定初始点
(2)以 x ( k −1) 为初始点，求解无约束问题
(5-1)
基本思想：把约束问题(5-1)转换为一个或一系列无约束优化 问题来求解，序列无约束极小化技术(SUMT)。惩罚函数 法叫做SUMT外点法，碰壁函数法叫做SUMT内点法。
一、惩罚函数的性质和构造：
F 惩罚函数： ( x, M ) = f ( x ) + Mp ( x ) (5-2) M>0,惩罚因子。M是一个很大的正数 p(x)惩罚项
2
§5.3 乘子法
§5.3 乘子法
§5.4 二次逼近法
利用二次规划逐步逼近非线性规划问题-序列二次规划方法
§5.4.1 二次规划
一、基本概念
1、问题描述
⎧ ⎪min ⎪ ⎪ ⎨s.t. ⎪ ⎪ ⎪ ⎩ 1 T X GX + g T X 2 aiT X = bi , i = 1,2, L m Q( X ) = aiT X ≤ bi i = m + 1,L p
s.t. x ∈ IntS 设求得的极小点为 x(k ) (k ) γ 3) 若 γ k B( x ) < ε ，则 stop.得到点x(k ) ，否则， k +1 = βγ k ， k=k+1，返回 step 2
§5.2 碰壁函数法
例：
min s.t. 1 ( x1 + 1) 3 + x2 12 − x1 + 1 ≤ 0 − x2 ≤ 0
一、Hestenes的乘子法：
min s.t. f ( x) h j ( x) = 0, j = 1,2,L, p
n
(5-8)
f , h j是二次连续可微函数，x ∈ R
§5.3 乘子法
§5.3 乘子法
§5.3 乘子法
3、如何确定最优乘子 μ
*
首先给定一个足够大的c，然后在迭代中逐步调整 μ (k )，使之 μ* 。
f ( x) + γ k B ( x) IntS
求解： ⎧min
⎨ ⎩x ∈
k →∞
lim γ k = 0
x (0) ∈ IntS , ε > 0, γ 1 ,缩小系数β ∈ (0,1) ，k=1。 1)给定初始内点
( k −1) 2)以 x 为初始点，求解如下问题：
min
f ( x) + γ k B( x)
F ( x, γ k ) = 1 1 1 ( x1 + 1)3 + x2 + γ k ( + ) 12 x1 − 1 x2
解：定义碰壁函数 用解析法求 F ( x, γ k ) 的极小点
γk ∂F =1− 2 = 0 ∂x2 x2
γk ∂F 1 = ( x1 + 1)2 − =0 2 ∂x1 4 ( x1 − 1)
⎧min ⎨ ⎩s.t. f ( x) g i ( x ) ≤ 0. i = 1,2, L m
(5-6)
一、碰壁函数的性质及构造
碰壁函数： F ( x , γ ) = f ( x ) + γ • B ( x ) （5-7） F-碰壁函数,B(x)-碰壁项, γ − 障碍因子, γ > 0 是一个很小的 数。
lim B(x),p(x)分别按内点法和外点法构造，k → ∞ γ k = 0
§5.3 乘子法
Powell和Hestenes于1969年首先针对具有等式约束的优化 问题提出的。Rockafellar于1973 年将其推广到不等式约束 的优化问题，主要解决惩罚因子M ∞时，无约束优化问 题无法进行下去的缺点。
min f ( x) + M k p ( x)
设其极小点为 x(k )
x(k ) ，否则令 (3)若 M k p ( x ) < ε ，则停止计算，得到点
(k )
M k=k+1， k +1 = cM k ,返回到 2）。
§5.2 碰壁函数法
基本思想：从内点出发，并保持在可行域内部进行搜索， 为了保证迭代点在可行域内，在可行集边界上建一道“围 墙”，以阻止可行点离开可行集。 适用于只有不等式约束的问题：
(k ) 设在第k次迭代中，lagrange乘子向量为μ (k ) ，c，得 φ ( x, μ , c) 的极小点 x (k ) ，此时有
∇ xφ ( x ( k ) , μ ( k ) ) = ∇f ( x ( k ) ) + ∑ μ j ∇h j ( x ( k ) ) + c ∑ h j ( x ( k ) )∇h j ( x ( k ) ) = 0
则类似的有：
c m 1 p 2 φ ( x, λ , μ ) = f ( x) + ∑ λ j h j ( x) + ∑ (h j ( x)) + ∑ {[min(0, μ j + cg j ( x))]2 − μ j 2 } 2 j =1 2c j =1 j =1
m
λ(jk +1) = λ(jk ) + ch j ( x ( k ) ) 迭代公式：