第 六 章 约束最优化方法.

Presentation on theme: "第 六 章 约束最优化方法."— Presentation transcript:

1 第 六 章 约束最优化方法

2 第六章 约束最优化方法 问题 min f(x) s.t. g(x) ≤0 分量形式略 h(x)=0 (fgh)
第六章 约束最优化方法 问题 min f(x) s.t. g(x) ≤ 分量形式略 h(x)=0 约束集 S={x|g(x) ≤0 , h(x)=0} 6.1 Kuhn-Tucker 条件 一、等式约束性问题的最优性条件： 考虑 min f(x) s.t h(x)=0 回顾高等数学中所学的条件极值： 问题 求z=f(x,y)极值 min f(x,y) 在ф(x,y)=0的条件下。 S.t. ф(x,y)=0 引入Lagrange乘子：λ Lagrange函数 L(x,y;λ)= f(x,y)+ λ ф(x,y) (fgh) (fh) 即

3 第六章 6.1 Kuhn-Tucker 条件 一、等式约束性问题的最优性条件： (续) 若(x*,y*)是条件极值，则存在λ* ，使
fx(x*,y*)+ λ* фx (x*,y*) =0 fy(x*,y*)+ λ* фy(x*,y*) =0 Ф (x*,y*)=0 推广到多元情况，可得到对于(fh)的情况： min f(x) s.t hj(x)= j=1,2, …,l 若x*是(fh)的l.opt. ,则存在υ*∈ Rl使 矩阵形式： 分量形式：

4 第六章 6.1 Kuhn-Tucker 条件 一、等式约束性问题的最优性条件： (续) 几何意义是明显的：考虑一个约束的情况：
最优性条件即： -▽f(ㄡ ) ㄡ ▽h(ㄡ ) h(x) -▽f(x*) ▽h(x*) 这里 x* ---l.opt. ▽f(x*)与 ▽h(x*) 共线，而ㄡ非l.opt. ▽f(ㄡ )与▽h(ㄡ )不共线。

5 第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： 考虑问题 min f(x)
s.t gi(x) ≤0 i=1,2, …,m 设 x*∈S={x|gi(x) ≤0 i=1,2, …,m} 令 I={i| gi(x*) =0 i=1,2, …,m} 称I为 x*点处的起作用集（紧约束集）。 如果x*是l.opt. ,对每一个约束函数来说，只有当它是起作用约束时，才产生影响，如： (fg) g2(x)=0 x* g1(x)=0 g1(x*)=0, g1为起作用约束

6 第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续） 特别 有如下特征：如图
特别 有如下特征：如图 在x* ： ▽f(x*)+u* ▽g(x*)= u*>0 要使函数值下降，必须使g(x)值变大，则 在ㄡ 点使f(x)下降的方向（- ▽f(ㄡ ) 方向）指向约束集合内部，因此ㄡ不是l.opt. 。 -▽f(ㄡ ) X* -▽f(x*) ▽g(x*) ▽g(ㄡ )

7 第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续）
定理（最优性必要条件）： （K-T条件） 问题(fg), 设S={x|gi(x) ≤0},x*∈S,I为x*点处的起作用集，设f, gi(x) ,i ∈I在x*点可微， gi(x) ,i I在x*点连续。 向量组{▽gi(x*), i ∈I}线性无关。 如果x*----l.opt. 那么， u*i≥0, i ∈I使

8 第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续） 3 1 2 4 g1=0 g2=0
x1 g3=0 x2 x* ▽g2(x*) ▽g1(x*) -▽f(x*) (3,2)T

9 第六章 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续） 用K-T条件求解：

10 第六章 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续）

11 第六章 6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续） 可能的K-T点出现在下列情况：
①两约束曲线的交点：g1与g2,g1与g3,g1与g4,g2与g3,g2与g4,g3与g4。 ②目标函数与一条曲线相交的情况： g1，g2, g3, g4 对每一个情况求得满足(1)~(6)的点(x1,x2)T及乘子u1,u2,u3,u4,验证当满足可得，且ui≥ 0时，即为一个K-T点。 下面举几个情况： ● g1与g2交点：x=(2,1)T∈S ,I={1,2} 则u3=u4=0 解

12 第六章 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续） ●

13 第六章 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续） ●

14 第六章 Kuhn-Tucker 条件 三、一般约束问题的Kuhn-Tucker 条件

15 第六章 Kuhn-Tucker 条件 三、一般约束问题的Kuhn-Tucker 条件 (续)

16 第六章 既约梯度法 一、解线性约束问题的既约梯度法

17 第六章 既约梯度法 一、解线性约束问题的既约梯度法 （续）

18 第六章 既约梯度法 一、解线性约束问题的既约梯度法 （续）

19 第六章 既约梯度法 一、解线性约束问题的既约梯度法 （续）

20 第六章 既约梯度法 一、解线性约束问题的既约梯度法 （续）

21 第六章 解线性约束问题的既约梯度法 （续）

22 第六章 既约梯度法 一、解线性约束问题的既约梯度法 （续）

23 第六章 6.2 既约梯度法 算法： x(1)∈S, k=1 k=k+1 Jk={j|xj为x(k)中最大m个正分量之一}
第六章 既约梯度法 算法： x(1)∈S, k=1 k=k+1 Jk={j|xj为x(k)中最大m个正分量之一} B=[…,aj(j∈Jk),…] N=[…,aj(jŒJk),…] YNT=▽NfT(x(k))- ▽BfT(x(k))B-1N dB=-B-1NdN 解 得 x(k+1)=x(k)+λkd Y Stop; x(k)~K-T点 d=0? N

24 第六章 既约梯度法 一、解线性约束问题的既约梯度法 （续）

25 第六章 既约梯度法 二、广义既约梯度法 （续）

26 第六章 既约梯度法 二、广义既约梯度法 （续）

27 第六章 6.3罚函数法

28 第六章 6.3罚函数法 1.罚函数概念 （续）

29 第六章 罚函数法 1.罚函数概念 （续）

30 图示

31 第六章 6.3罚函数法 2.罚函数法： （fgh）

32 第六章 6.3罚函数法 2.罚函数法： （续）

33 第六章 6.3 罚函数法 2.罚函数法： （续） 算法： 初始x(1), μ1>0, β>1, ε >0,k=1
第六章 罚函数法 2.罚函数法： （续） 算法： 初始x(1), μ1>0, β>1, ε >0,k=1 以x(k)为初始点，解 min f(x)+ μα(x) 得到，x(k+1) μk α(x(k+1))< ε yes 停；x(k+1)—l.opt. No μk+1 = β μk k=k+1

34 第六章 罚函数法 3.闸函数法： （内点罚函数法）

35 第六章 罚函数法 3.闸函数法： （续）

36 第六章 罚函数法 3.闸函数法： （续）

37 第六章 罚函数法 3.闸函数法： （续）

38 第六章 6.3 罚函数法 3.闸函数法： （续） 算法： x(1) ∈ S0, μ1>0, β∈ [0,1], ε >0,k=1
第六章 罚函数法 3.闸函数法： （续） 算法： x(1) ∈ S0, μ1>0, β∈ [0,1], ε >0,k=1 min f(x)+ μk B(x) s.t. x∈ S0 从x(k）出发， 求得，x(k+1) μk B(x(k+1))< ε yes 停；x(k+1)—解 No μk+1 = β μk k=k+1

39 第六章 罚函数法 3.闸函数法： （续）

40 第六章 6.3 罚函数法 4.罚函数法与闸函数法的缺点： 1°当罚函数法（闸函数法）的μ →∞ （ μ → 0+）时，惩罚项
第六章 罚函数法 4.罚函数法与闸函数法的缺点： 1°当罚函数法（闸函数法）的μ →∞ （ μ → 0+）时，惩罚项 →+ ∞• 0或0• + ∞形式，在计算上有困难； 2°计算一系列无约束问题，故计算量大。 5.乘子法：

41 第六章 罚函数法 5.乘子法： （续）

42 第六章 罚函数法 5.乘子法： （续）