第章 约束最优化方法
第 六 章 约束最优化方法
第六章约束最优化方法 问题 mIn feh)s.t.g(x)≤0 分量形式略 h(x)=0 约束集S={xg(x)≤0,h(x)=0 61Kuhn- Tucker条件 等式约束性问题的最优性条件: 考虑 (fh) min f(x) t.h(x)=0 回顾高等数学中所学的条件极值: 问题求(xy极值 即 min f(x, y) 在p(x,y)=0的条件下。 St.φ(x,y)=0 引入 Lagrange乘子: Lagrange函数L(xy:)=f(xy)+(x,y
第六章 约束最优化方法 问题 min f(x) s.t. g(x) ≤0 分量形式略 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) 即
第六章61 Kuhn-Tucker条件 等式约束性问题的最优性条件:(续) 若(xxy-)是条件极值,则存在x,使 f(xy)+中x(xx)=0 ∫xy)+中x)=0 Φ(xxy)=0 推广到多元情况,可得到对于(h)的情况: min f(x) 分量形式: s.b(④)=0j=1,2,…, 若x是ih)的0pt.,则存在o∈R使 了(x")+∑oVh,(x")=O 矩阵形式: VfO)+ Oh(
第六章 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)=0 j=1,2, …,l 若x *是(fh)的l.opt. ,则存在υ *∈Rl使 矩阵形式： 分量形式： = + = l j f x j hj x 1 * * * ( ) ( ) 0 0 ( ) ( ) * * * = + x h x f x
第六章61Kuhn- Tucker条件 等式约束性问题的最优性条件:(续) 几何意义是明显的:考虑一个约束的情况: Vf(x* h(x) 这里 opt.Vfx*与 又) Vh为共线,而又非opt 又 h(xx Vf又)与Vh(又)不共线 Vh(又) 最优性条件即: Vf(x*)=∑UVh(x
一、等式约束性问题的最优性条件： (续) 几何意义是明显的：考虑一个约束的情况： 最优性条件即： 第六章 6.1 Kuhn-Tucker 条件 -▽f(ㄡ ) ㄡ ▽h(ㄡ ) h(x) -▽f(x*) ▽h(x*) 这里 x* ---l.opt. ▽f(x*)与 ▽h(x*) 共线，而ㄡ非l.opt. ▽f(ㄡ )与▽h(ㄡ )不共线。 = = − h j f x j hj x 1 * ( *) ( *)
第六章61 Kuhn-Tucker条件 、不等式约束问题的Khun- Tucker条件: 考虑问题 min f(c) t 8A(x)≤0 ,2 9·.· 设xx∈S={gAx)≤0i=1,2,…,m} F={g(x3)=0÷=1,2,…,m 称/为x点处的起作用集(紧约束集)。 如果x*是.opt.,对每一个约束函数来说,只有当它是起作用约 束时,才产生影响,如: g2(x)=0 g1(x米)=0,8为起作用约束 gIr
第六章 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为起作用约束