有约束极值问题

1、1 最优性条件第八章第八章 有约束极值问题有约束极值问题一、基本概念一、基本概念1 起作用约束min(). .()01,.,()()01,.,jif xstgxjliihximm in ( ).( ) 01,.,( )jf xstg xjli 是(i)的可行解，若 则称 为 处的起作用约束。记 处 起作用约束的下标集(0)x()0jgx (0)x(0)()0jgx2 可行方向(0)(0)()01,jjjgxjlx=()01,.,jrx gxjl=()01,., ;()0,1,.,jirx gxjl h xim记或(0)00,0,xr 时有(0)xdr称 为 处的可行方向d(0)x为（i）或（i

2、i）的可行域若 是 的任一可行方向，则有(0)xd(0)()0,(1)tjgxdjj3 下降方向(0)00,0,xr (0)(0)()()f xdf x时有称 为 处的下降方向d(0)x若 是 的任一下降方向，则有d(0)x(0)()0(2)tfxd若d既满足（1）式又满足（2）式则称 为 的下 降可行方向 d(0)x定理1 为（i）的局部极小值点， 在 处可微，(0)x()f x(0)x()()jgxjj(0)x在处可微()()jgxjj在(0)x处连续则在 处不存在可行下降方向。即不存在向量(0)xd(0)()0,(1)tjgxdjj(0)()0(2)tfxd同时成立二、最优性条件二、最优

3、性条件1、gordan引理引理设1,.,laaln为 个 维向量，不存在向量p 使得0,1,.,jta pjl成立的充要条件是存在不全为零的非负数，使得10ljjja成立2、fritze john定理定理(i)010010jjjljjjljxgxgxf,.,)()()(*(3)1(4)jjpxgpxftjt, 0)(0)(*)( , 0, 00jjjjjjjxgxf0)()(*0(5)ljjjxgxf1*00)()(6)00jjjxg,)(*该定理给出了非线性规划 的(局部)最优点应满足的必要条件。该条件称为 fritz john条件，满足这个条件的点称为fritz john点。3kuhn-t

4、ucker条件条件 设x*是非线性规划（i）的局部极小点)(),(xgxfj有一阶连续偏导而且x*处的所有起作用约束梯度线性无关， 则存在数使得（6）成立),.,( ,.,)()()(*ljljxgxgxfjjjljjj101001010010jjjljjjljxgxgxf,.,)()()(*成立（3）（3）中各式的两边，中各式的两边，（6）),.,( ,.,)()()(*ljljxgxgxfjjjljjj101001 若x*是非线性规划(ii)的局部极小点， 且x*点的所有起作用约束的梯度)(*jjxgjmixhi,.,),(*1和线性无关。则存在向量),.,(),.,(mlm11 使得),

5、.,( ,),.,( ,.,)()()()(*ljmiljxgxgxgxfjijjljjjmiji10110011（7）其中*,.,;,.,ml11称为广义拉格朗日(lagrange)乘子。库恩塔克条件是确定某点为最优点的必要条件，只要是最优点且此处起作用约束的梯度线性无关。就必须满足这个条件。但一般说来它并不是充分条件，因而，满足这个条件的点不一定就是最优点。可是，对于凸规划，库恩塔克条件不但是最优点存在的必要条件，它同时也是充分条件。某非线性规划的可行解x*，假定此处有两个起作用约束，若x（k）是极小点，则必处于)()(kxf的夹角之间不然，x（k）点处必存在可行下降方向，它就不会是极小点

6、。)(),()()(kkxgxg21举例：例求131212max(). . (1)0,0f xxstxxx x312(1)xx的极大值点。并验证其是否为k-t点。说明理由。解：1如上图所示，阴影部分为可行域r，红色直线为目标函数的等值线。显然最大值点为（1，0）。r1131122132min()(). .()(1)0()0()0f xf xxstg xxxgxxgxx 将原问题标准化211231103(1)(),(),(),()0011xf xg xgxgx *112233*11*22*33*123()()()()0()0()0()0,0f xg xgxgxg xgxgxk-t条件* 2*11

7、23* 3*112*21*32*12311003(1)00101(1)000,0 xxxxx *(1,0)tx* 2*1123*131 3(1)00 x （1）（2）（3）（5）（4）（1）式为代入上式，得：*210 故*(1,0)tx不是k-t点。311222()(1)0()0g xxxgxx*(1,0)tx *1300(),()11g xgx 的起作用约束为线性相关*(1,0)tx 不是k-t点。自己验证*(1,0)tx 是f-j点。例2 用k-t条件，求解非线性规划21222112212min(). .()90()10f xxxst g xxxgxxx 212221212min(). .

8、91f xxxstxxxx22020()20,00000f x解：1 验证该问题为凸规划原问题标准化为212020(), 20,200202g x 半正定，负定()f x2()f x是凸函数21()g x1()g x是凹函数故该问题为凸规划。所以2 求k-t点该问题的k-t条件为111222()121()()21xf xxg xgxx111211221 1222 (1)0210212011xxxxx1121 1222112212122 (1)0120(9)0(1)0,0 xxxxxx （1）(2)1220,010, （2）（3）（4）(1)121111(3)221122(2)210,0(1)0

9、,0009313,6xxxxxx (0, 3)tx是k-t点(i)(ii)（5）22(3),(4)12121290,01117117117117,2222ttxxxxxx1121(1)(2)2()1 2(6)xxx 117117117117,2222ttxx(iii)将求出的 带入（6）式都不满足故该问题有唯一的k-t点 即为极小值点，(0, 3)tx 三、三、wolfe对偶问题对偶问题1 定义min()(1)()0,1,.,jf xgxjl11(,)(),(,.,) ,(),.,()tttlll xf xggg xg x1111(,)(),(,.,) ,(),.,()(,.,) ,( (),

10、.,()ttttllttlll xf xghgg xg xhh xh xmin()()0,1,.,(2)()0,1,.,jif xgxjlh xim令设或为凸规划或则wolfe对偶问题为：max (, )(3)(, )0,0xl xl xmin (, , )(, , )0(4)0xl xl x 2 线性规划的线性规划的wolfe对偶问题对偶问题min(1),0tc xaxb xwolfe对偶问题对偶问题max(2)ttbac2 二次规划1 二次规划模型（目标函数第二项为正定二次型）11111min()2,1,2,.,(1)0,1,2,.,0,1,2,.,nnnjjjkjkjjkjkkjnijj

11、ijjf xc xc x xcckna xbimxjn1111110.(),(),()1.0nkkkinjkkjjn iijkinnnkknkc xcaf xc xcgxgxajac xc11111min()2()0,1,2,.,(2)()0,1,2,.,nnnjjjkjkjjkjjnn iijjijf xc xc x xgxxjngxa xbim11,1,2,.,(2)nmjkkijn ijjkic xa yycjn1111110.(),(),()1.0nkkkinjkkjjniijkinnnkknkc xcafxcxcgxgxajacxc10,1,2,.,(3)nijjn iija xxb

12、imk-t 条件中第一个条件为1(),1,2,.,nn in iijjijgxxa xb im约束条件化为等式 故()1,2,.,jjgxx jnk-t 条件中第二个条件为0,1,2,.,(4)jjx yjnm0,0,1,2,.,(5)jjxyjnm11,1,2,.,(2)nmjkkijn ijjkic xa yycjn10,1,2,.,(3)nijjn iija xxbim显然。 （2）-（4）的解即为二次规划的解。为了求解（2）-（4），在（2）式中引入人工变量将其转化为线性规划问题。1111,min ( )sgn(),1,2,.,(*)0,1,2,.,0,1,2,.,0,1,2,.,nj

13、jmnijn ijjkkjjjiknijjn iijjjjzza yyc xczcjna xxbimx yjnmzjn, jjx y, jx在求解上述线性规划时，要求至少有一个为零。当（*）的最优解中 时，其中 即为二次规划（1）的最优解。0,1,.jzjn例1求解二次规划2212121212max()810326,0f xxxxxxxx x22112121212min()810632000fxxxxxxxxx 解：将上述二次规划改写为可知目标函数为严格凸函数。1211221221111128,10,2,0,6,3,2ccccccbaa 1231113222123123123123min()3

14、2822103260,0zzzyyxzyyxzxxxxxxyyyzzz 1211312232123123123123min ( )2382210326,0zzzxyyzxyyzxxxx x xy yy z zz或且0,1,2,3jjx yj3 可行方向法 可行方向法可看作无约束下降算法的自然推广，其典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点算法的主要步骤是选择搜索方向和确定沿此方向移动的步长搜索方向的选择方式不同就形成各种可行方向法下面给出zoutendijk可行方向法.设( )kx( )kx点的起作用约束集非空，为求点的可行下降方向d，d应满足下述不

15、等式：( )( )()0()0,(1)ktktjf xdgxdjj( )( )()(),(1)0ktktjf xdgxdjj( )( )()(2)(),111,2,.,ktktjiminf xdgxdjjdin ( )(,)kkd解线性规划问题（2）得最优解( )kd0k若则( )kx即为f-j点。若0k则即为可行下降方向。以该可行下降方向进行一维搜索迭代出新点。1 罚函数法（外点法）罚函数法（外点法） 考虑约束问题其中en是上的连续函数。(),(),()jif xgxh xm in(). .()0,1,.,()0,1,.,jifxs t gxjlhxim2211min()()min(0,()

16、()lmjijip xf xmgxmhx利用目标函数和约束函数组成辅助函数，称为罚函数p（x）。0m 为罚因子。随着罚因子的增加，p（x）的最优解越靠近可行域，最终趋于所求非线性规划的最优解*x4 制约函数法在实际中，罚因子的选择为一个趋向无穷大的严格递增正数列 ，从非可行点出发，逐个求解km2211min()()(min(0,()()lmkjijip xf xmgxhx得到一个极小点的序列 ，在一定条件下，这个序列将收敛于原约束问题的最优解。*kx这种通过一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法，简称sumt方法。（sequential unconstrained

17、minimization technique)例题：求解非线性规划11221221min()()()0f xxxg xxxgxx 12221221(,)min(0,()min(0,)p x mxxmxxx解：构造法函数解析法求解112211122212min(0,()(2 )2min(0,)0(1)12min(0,()0(2)pmxxxmxxpmxxx 取不满足约束条件的点12210,0 xxx则（*）式变为11122111222(4)22(5),(3)111(6),(5)22*212()( 2 )20(3)12()0(4)1(5)211220(6)22114(1)2111(,)(0,0)22

18、4(1)2mttpmxxxmxxpmxxxxxmxmxxmxmmxmmm 取不满足约束条件的点12210,0 xxx111222(4)2210(3)12()0(4)12pxpmxxxxxm 则（*）式变为无法求出*mx由此可看出罚函数法的缺陷。2 障碍函数法（内点法）障碍函数法（内点法）考虑约束问题min(). .()0,1,.,jf xst gxjl111(,)(),(0)(1)()(,)()log(),(0)(2)lkkkjjlkkjkjp x rf xrrgxorp x rf xrgxr kr利用目标函数和约束函数组成辅助函数，称为障碍函数p（x）。对于障碍因子 ，选择为一个趋向无穷大的严格减小