最优化理论约束PPT学习教案

1、会计学1 最优化理论约束最优化理论约束 (fgh) (fh) 即 第1页/共42页 分量形式： l j jj xhxf 1 * 0)()( 0 )( )( * * * x xh xf 第2页/共42页 -f( ) h( ) h(x) -f(x*) h(x*) 这里 x* -l.opt. f(x*)与 h(x*) 共线，而非l.opt. f( )与h( )不共线。 h j jj xhxf 1 * *)(*)( 第3页/共42页 (fg) g2(x)=0 x* g1(x)=0 g1(x*)=0, g1为起作用约束 第4页/共42页 g( ) -f( ) X* -f(x*) g(x*) 第5页/共4

2、2页 点。称条件的点满足 互补松弛条件 。那么，可微，如果在 TKxTK mixgu miu xguxf ixgx xguxf ii i m i ii i Ii ii * * 1 * )(,2, 10)( ,2, 10 0)()( )(, 0)()( 第6页/共42页 0),( 0),( 042),( 05),(. )2()3(),(min 2214 1213 21212 2 2 2 1211 2 2 2 121 xxxg xxxg xxxxg xxxxgts xxxxf 例 1 234 1 2 g1=0 g2=0 g4=0 x1 g3=0 x2 x* g2(x*) g1(x*) -f(x*)

3、 (3,2)T 第7页/共42页 0)()()( )2,2()2(2),3(2()( )2, 1()( )2,4()2,2()( 2, 112 0),( 0),( 23 2 13 1 * 3 2 * 23 1 * 1 * 2 * 1 * 2 211 212 211 * xgxgxf uu xxxf xg xxxg I xxg xxg x TT T TT T 使计算可得 起作用集），交点（ 点在 1 0 , 0 1 )( 2 1 )2(, 2 2 )(, )2(2 )3(2 )( 43 2 2 1 1 2 1 gxg g x x xg x x xf 第8页/共42页 0)( ,2,1,0 0)(

4、)( xgu miu xguxf ii i m i ii 个未知量个方程66 )6(0 )5(0 )4(0)42( )3(0)5( 0, )2(022)2(2 )1(02)3(2 24 13 212 2 2 2 11 4321 42212 32111 xu xu xxu xxu uuuu uuxux uuxux 第9页/共42页 点。是故 得 TKx uu uxux uxux T )1 , 2( 0 3 2 , 3 1 022)2(2 02)3(2 21 2212 2111 第10页/共42页 点。故不是不满足 点；故不是 得交点：与 TKgS TKS x x xx gg T T T ,0,)

5、5,0( ,)5,0( )5,0( 0 05 2 1 2 2 2 1 31 . 04, 06 0)20(2 0)30(2 04, 3)0 , 0(:, 43 4 3 2143 点故非 得解 故交点 TK uu u u uuISxgg T 第11页/共42页 034. 04742),( ),( 05 02)2(2 02)3(2 0,1 0)()( 13 5 13 20 13 45 212 13 20 13 45 2 2 2 1 122 111 432 1 xxgTK S xx uxx uxx uuuI xgxf 点故均不是 得解 则 相切的情况：与目标函数 第12页/共42页 线性无关。，向量组

6、 约束规格）。（的某邻域内连续可微。在 ）（，连续，在可微在设 为起作用集。，问题定理： )(,),(,),)( , , 2 , 1)(,)( ,0)(, 0)(|)( , 2 , 10)( , 2 , 10)(. . )(min )( 1 xhxhIixg CQx ljhxIixgxIixg IxhxgxSxfgh ljxh mixgts xf fgh li jii j i 第13页/共42页 点。是则 及为凸规划，满足可微性若 亦可微，那么在如果还有 那么如果 TKxoptlx CQfgh mi xgu u xhvxguxf xIixg xhvxguxf ljRv Iiuoptlx ii

7、i l j jj m i ii i l j jj Ii ii j i . )( ,2, 1 0)( 0 0)()()( )( 0)()()( ,2, 1, ,0. 11 1 第14页/共42页 为既约梯度称相应 非基变量基变量，使 非奇异，存在分解 ：、既约梯度及搜索方向 ）个正分量。（的每个极点都有 列线性无关；的任意 、非退化假设： 的多面体同可行集： 秩 ）、问题：（ NBxfxfr xf xf xf xxxx x x x BNBASx bBmS mA SLPxbAxxS RbmAA x bAxts xf P T B T N T N N B NBNB N B mm m nm 1 1 )(

8、)(, )( )( )( 0, 0 , 3 02 1 2 .)(0,| , 0 . . )(min 1 第15页/共42页 为可行方向。故即有 ）时，（则取 由 故 又 ）时，（当为可行方向，即 时当 为可行方向 寻找下降可行方向： dSdxdx d d x bAxdxAAd ddx AdbAxbAdAxdxA dproof xd Ad d d j j j jjj jj .0 00|min .)(,0,0 .0,0 0,0,)( 0,0:. .0,0 0 )1( 第16页/共42页 0 )()( )()( )()()( 0)(:)2( 0, 0 0 . 1 1 1 1 N T N N T B

9、T N N T NN T B N T NB T B T T NBjjN NB NB N B N B dr dNBxfxf dxfNdBxf dxfdxfdxf dxfd NdBddxdd NdBd NdBd d d NBAd d d d 分解： 要求下降方向 及中，对应可行，可取在故要使 得到 根据 考虑分解 第17页/共42页 点。若 的下降可行方向；为若 那么方向定理：按上述方案产生 的分量。为其中： 时当 时当 的方案向的一种产生下降可行方、结合 TKxd Pdd d NdBd rr rrx rr dd d NB Nj jjj jj jN 02 )(, 01 , 0 0 : :)2()

10、1 ()3( 1 第18页/共42页 证毕。非零，于是或至少一个由于 又 保证故总有 对 .0,0 0 0, 0, 0.0 00 00 01 . 2 2 1 N T Njjj jjj jj jj Nj jjN T N NBj jjjj jjj j drrxrd rrx rr drdrdr AdNdBdd rxdr rdr x proof 第19页/共42页 得证。 即 条件： 可得取 故时，当原因： 则取 矛盾；与那么， 反证。若存在可得 0 0 0)()( 0)()( 0)( ,)() ; 000 0, 0, 0) 00 )(0:0) 02 1 1 1 xu u uNBxfxf uBBxfx

11、f uAvxf TK RBxfviii xrxdrru xuxuruuii drd Njrri d T T N T B T N T B T B T BTTT nT B T jjjjjNN N T N T NNB jjj jN 第20页/共42页 证毕。也就是 即故恒有 时当 时当 ，即 由第三式得： 由第一式得： 点即 .0 0, 0, 0 00 00 00 00, 0 )()(0)( )(0)( 0 0 0)( 1 1 1 d NdBddd rxdr dr rxuxxu uxxu rNBxfxfuuNvxf BxfvuBvxf xu u uAvxf TKx NBNj jjjj jj jjjj

12、N T N BBB T B T N T B T N T N T N TT N T B TT B TT B T TTT 第21页/共42页 x(1)S, k=1 k=k+1 Jk=j|xj为x(k)中最大m个正分量之一 B=,aj(jJk), N=,aj(jJk), YNT=NfT(x(k)- BfT(x(k)B-1N dB=-B-1NdN 解 得 x(k+1)=x(k)+kd d=0? Y N Stop; x(k)K-T点 0, 0, jjj jj j rrx rr d 当 当 0. . )(min )( t s dxf k 0, 0,0|/min )( d dddx jj k j 否则 当

13、第22页/共42页 ., :,: 0)(. . )(min 0, 55 2. . 32min . 21 21 21 2121 2 2 2 1 babaRba RRhRRf bxa xhts xf P GRG xx xx xxts xxxxxx Ex n lnn ，且的分量允许 连续可微。其中： ）（标准形式 ）二、广义既约梯度法（ 见书（略） 第23页/共42页 T T T y T z T z yy z y z yln l z xh y xh xfxfr y xh bya b b b a a aRz Ry z y xSx bxaxhxS )()( )()( )( 2 , ,1 ,0)(| 1

14、广义既约梯度： 非奇异 使 记 使分解 非退化假设： 记 第24页/共42页 点。 时为下降可行方向；当 同样有结论： 或 且或且令 取方向： TKxd d d z xh y xh d Jir Ji d rbzraziJ z TT y iz iz iziiizii 02 01 )()( 0)( 0 )( 0)(|0)(| 1 第25页/共42页 0)( 0)( )()()( :0)( :0)(. :)(min )( .1 ) ( 11 xx xx xhxgx RRhxh RRgxgts RRfxf fgh TechniqueonMinimizati nedUnconstraiSequentia

15、lSUMT l j j m i i ln mn n 有不满足约束的 有目的：使满足约束的 构造罚函数： 罚函数概念： 序列无约束最优化方法 第26页/共42页 )2.(22 |)(, 0max)( )(),( )()(min )()( 0 )( , 0 00 0,0 )( 00 0,0 )( 次是最低次的光滑函数常用：因次罚函数时，称当 为正整数。 的典型取法： 辅助问题 辅助函数 不可行 可行 惩罚项 可构造取 时当 时当 时当 时当 其中： p ptttt tt xxf xxf x t t t t t t pp 第27页/共42页 .2 2 ),(,2 2 2 14 ),(,2 2, 2,

16、4) 14()2( )()(),( : 2)()()(min, 2, 0 2,)2( 2, 0max)(: 02. . min . 22 2 2 optx xxgx xxgx xx xxxxx xxfxg xxfxxf x xx xx xts x Ex 故 的最小值点时当 的驻点时当 辅助函数解析解 时当 如图 二次罚函数 第28页/共42页 第29页/共42页 的单调非增函数关于 的单调非降函数；关于 ）（则 ）（使：，再设 为罚函数，连续。连续，引理：设 下确界）（定义： 0)( 0)(),(2 0|sup| )(inf1 )()(,0 )(, )()(inf x xf Sxxf xxfD

17、x xhgf xxf x x 第30页/共42页 . ,0)(0 0)(.2 )(lim0| )(sup| )(inf1 .0 ,0)(,0)(|),( )( 21 optx x optx Sxxf xx xhxgxSfgh x k k k k 则 使若推论：在定理条件下， 且 那么， 有即 单调增加的正数列在引理假设下，设存在 定理： 第31页/共42页 初始x(1), 10, 1, 0,k=1 以x(k)为初始点，解 min f(x)+ (x) 得到，x(k+1) k (x(k+1)0, 0,1, 0,k=1 min f(x)+ k B(x) s.t. x S0 从x(k）出发， 求得，x

18、(k+1) k B(x(k+1) yes 停；x(k+1)解 No k+1 = k k=k+1 第37页/共42页 。转置否则 停，说明若 ；转为初始内点，得到解以 用闸函数法求解： ；转 使否则，取 为初始内点。则若 令 ；转 求初始内点： 2, 1 .,0)( 4 4 ,0)(. )(min 3 3 |)(max)( , 0)(|2 2, 1,1 0 )1( )1()( )()( )( )( )1( kk Sxg xx Iixgts xg Iixgxgj xI xgiI kx k j kk ki j k k i k j k k k ik 第38页/共42页 : )( :0)(. . :)(min )( xfLagrange RDDx RRhxhts RRfxf fhD n ln n 函数代替用 约束构成。是一个集合，常由简单 第39页/共42页 。及调整否则 及乘子得到解若 得到求解 为罚因子。为乘子，其中： 乘子罚函数