课件-最优化3.有约束非线性

自动化学约束优化约束非线minfs.t.gi(x)hj(x)

j1,...,不等式约束优化问题线性约束优化问题，…定义1设， ,则称是处的一个可行方向。在处的所有可行方向的集合记为 2在定理1:设是 中非空集合,若是(NLP)问题局部最优解，则

在处可微即:局部最优解，则处的可行方向一定不是下降方向证明：反证，设存在向量h0,hF0V，即hF0hVhFf(x)Th00,当0,时 f(xhf(xhV20,当0,2时，有xh令min1,2,当0,f(xhf(x)，且xhD即xh比x更优，与x是局部最优 最优点可能出现的情况在可行域内在约束边界 约束最优解minf(x1,x2) s.tx2

2x22x212x22x21不难看出，可行域是弧AB，最优点是B点x*二．不等式约束的一阶最优性条 ， 表示处全部起作约束的标号在讨论可行方向时，希望只考虑在处起作用的约束条g1g1(x)x1dx0dddg2(x)例设g1(x)x2 2x

0,g(x)1x

g(x)x0 ,2T极约 点的 指标集(xg2(x)g(x)1g3(x)Ox重新定用替代定理1中的可行方向锥

最优性定理2：设，在可微，在续，如果是（NLP）问题局部最F0VV0VhV0h0当0,xh即只需证gi(xh0i1hV，由V定义iI(x有g(x)Th0 gi(xgi(x则有gi(x

h010当0,1时，gi(xh)gi(x),iI(x)gi(xh)gi(x)0,iI(x（1）而当iI(xgi(x0，已知iI(xgi(x)x处连续2 0当0,2时，gi(xh)0iI(x（2）由（12min1,2,当0,时，对igi(xh)0xhDh为可行方向hVV0凸集的进一凸 4SRn，若xxS， x1(1)x2

凸5S的凸包：由S中元素所有可能的凸组合构它是所有包含集合S的凸集的交，即它是包含集合S的最小凸6KRn，若xK0，有xK则称K为锥；若锥K还是凸集，则称之为定义7SRn是非空凸xSx不在S中任何线段的内部，则x是凸集S的极点。显然，多边形顶点、圆周上的点均为S中的某方向d不能表示为该集合的两个不同方向的正的线性组dS的极方向。凸集的分十分关键的作用。集合的分离是指对于两个集合S1S2，存在一个超平面H有pTx那么H一边的xpTx 9SSRn中两个非空集合HpTx 1为超平面，如果xS,都有pTx对于1分离集S13SRn是非空yS，则存在唯一的点xS，它y的距离最短。进一步，xy距离最短的充要条件(xx)T(xy)0，x凸集的4（凸集的分离定理）设SRnyRnyS，则存p0和实数，使得pTxxS，并且同时满足pTy即超平pTx严格分离y和闭凸S。证明：由于S是闭凸集yS。故定理3存在唯一的一xS，使(xx)T(xy)0，x p(yx)，则 pT(xx)0， pTxpTx。再 pTx则xS， pTx。pTypTypTxpT(yxx(yx)T(yx) y 2x故 pTy定理证5（Farkas）ARmncRn，Ax cTxATy y也可表示Ax0cTx0有解的充要条件ATycy0例AmnB是ln矩阵cRn应用Farkas引理证明下列两个系统恰有一个有解：1Ax0Bx0cTx0对于某xRn2ATyBTzcy0，对某yRnz然后利Farkas可以把该等式转化为不等式描述：Bx0Bx0,BxA这样，系统1的不等式系统可以描 为

x0,cTxB 利用Farkas引理，系统1描述的不等式系A ABx0,cTx0有解系统B c,0无解 yzyRmzzRl，即 1 z z 2yATyBTzBT cz0 1z z2zz1z2z是自由变量，无非负限制，2ATyBTzcy0：Gordan：有解的充要解释 夹角都为钝Gordan1 2A 2

使得1,2,3X夹角都为钝角，则存在非零向yj0,j123使yTyTyT 因为不存X，使得1,2,3X夹角都为钝角，所1y22y331y22y33x13x2 17x 3x 3x 17x

x13x22 217x 3 Ax0无解，其中,A 1 Gordan理，只需证明存ATy0y0有解即可也就是证明

y1

17y30有非零解，且解非负即可。由13y12

11y3y13y217y331y211y3y13y217y3,3(3y217y3)y211y3y24y3,y15可见，当任y30时，均y15y30,y24y30，由Gordan理，命题得证最优性的代数条件(FritzJohn条件定理7： 在可微在连续，如果是（NLP）问题的局部最优解，存在不全为零的非负 ,使:理2,在,,量.得,即由Gordan,数成 得,知,T题的最优minf(x)1

7)22

g(x)10x2x2 g2(x)4x1x2g3(x)x2g1(xxfg1(xxf(x)g2(x在点,Tf(x)8,g(x)6,g(x) 设86104 12 2 此方程有分量不全为的非负解，如于是在处满足FJ条件 f(x) g1(x)g2(x)x1

(2x2)2(f(x)0,g(x)2,g(x) 0 设0210 10 20 此方程有解=（02k任何正于是在处满足FJ条件 在可微在连续 证明：由定理7，存在不全iiI0f(x)igi(x)0，而不i(x)=0

i,iI gi(x)iI(x)线性相关与题

,iI则f(xigi(x)例验 1计算f(xgi

f(x)

2),g(x)

,g(x)

2x

1 2 0 （2）x(1)0g(x(1)0g0 I(x(1))f(x(1))4,g(x(1))1,g(x(1))0

1 K-T条件f(x(1g(x(1g(x 4110 10 21 41

04, 得2 14x(1不是K-T（3）对x(2)1点g(x(20g(x(21 1I(x(2))f(x(2))2,g(x(2))1,g(x(2))2

1 K-T条件f(x(2g(x(2g(x 2112 12 21 212

0,得22

ix(2K-TK-T条件的另一种形K-T条件等价由条件,当时而当时 例minf(x)x11)2s.tg1(x)x1x22g(x)x 求满足K-T条件f(x)

1),g(x)

1,g(x)0 f(x)1g1(x)2g2(x)由K-T条件g(x)0, (x) 0, 2(x11)1 112 1(x1x22) 2x2 10,2 由（4）2x2020，由）1

0,由（）(1) 0，由（3）(x20

1,1,

0,

0, x20x2,由

12舍x= 0 0x1K-T 设域的

线性无关,则存 ,满罚函数自动化学小化方法(SUMT---SequentialUnconstrainedMinimizationTechnique) minf( s.t.g(x) j h(x)j

i1,2,,j构成一个新的目标函数，称为惩罚 (x,r(k),r(k))f(x)r(k)G[g(x)]r(k)H[h( (x,r(k),r(k))f(x)r(k G[g(x)]r(k H[h( 惩罚项必须具有以下极限性质mlimr(k)G[g(x)]m

llimr(k)H[h(x)]k

k

(x,r(k),r(k))f(x(k))惩罚函数

外点子算目标函数—-价格，约束条件---规 采购代价=商品价格+罚惩罚函数的导例1考虑单变量问 minf(x) 的图s.tx1显然该问题最优解是x*不考虑约束条件，最优解x0距离x*1较远，如何才能使其 近如果保持曲线位于可行域(-,-的最优点的横坐标就会逐渐向*1这一过程可用数学式

x1(x,r)

r(x x1当从逐0渐增大时，函数就(,)上面k拉起的曲线，当充分大时，函数(xr)的无约束极小点*充分接近x*1.k(x2r(x1)2)2x2r(x1)0x 1r,x1)。例 minF(X)g(X)x1构造如下(x,r(k))

(x10)(可行域内xr(k)(x

(x10)(可行域外d 1

(k

(x1)

x1

2r(k0.1x0.1

2r(k (k (x,r(k)) (k x (x

(x10)(可行域内(x10)(可行域外(x,r(k)) xr(k)(x束边界越远，曲线被抬0.1(x,r(k0.1 xr(k)(xx1

2r(k基本原 去近原约束问题的最优解。minf

minf 0,i1~ s.tgi(x)0,i1~2不等式约

等式约外点法惩罚函数的构对于具有不等式约束的优化问题minf(x)s.tgi(x) i1外点法的形((x,r)f(x)rmin[0,g jjr0r1r2fj(x,rk)f(x)rk[g(x)]2j

r0r1r2惩罚项的作用:迫使可行域外的函数f

可行域(x,rk)

f(x)r

[g

可行域j j0012罚因子的(( fP(x合力使得迭代点向() 1）给出，， 若使得（第个约束不满足，转否则停初始点x(0)的选初始罚因子r(0)递增系数c

4)终止条[x*[x*(rk),rk][x*(rk1),rk[x*(rk1),rk1x*(rk)x*(rk1)323krkk

)程序框例4

minf(X)x1 g(X)xx2 g2(X)x1解：首先构造惩罚函(X,rk)

x1 xxrk x2)2 14r x2)x12r 12r

x21 x(rk)x2 rx*2f*1---2---3---4---∞000g(Xg(X)xx2 112f(X)x1g2(X)x1 0.125 Xk f(Xk)minf(x)1( 1)3 例5s.t g1(x)1x1g2(x)x2

用外点法(x,r)1(x1)3xrmax0,1xrmax0,

(x1)22rmax0,1x 12rmax0,x 为解上面第一个方程，讨论两种情形 （1）1x0max0,1x00 (x1)20x1，此点不满足1x0，即不在可行 （2）1x0max0,1x1x0 (x1)22r(1x)0

r2kkx1r2kk

，由于只考虑

1的情r2kkx1r2kk

0（舍去r2kkx1r2kk同理由0得 2 2k即x1(rk)1rk

rk4rk4k

rkrk4kr24 r

r2 rrkrkkk

rkrkkk

1, x2(rk)

2

0, 所以，x*1x* xx(x,k)f()1---10无约束问题min(xrkf(xrk的最优解为*k limx* k k证明：因为k

无约束问题的xk

kkk(x*,rk) ,rkkk ,rk+1)(x*,rk+1)k f(x*)rkP(x*)f(x* )rkP(x*

k kf(x* )rk1P(x* )f(x*)rk1P(x*

k k 因为1式(x*,rk) ,rk+1

端用k

rk以得 kk由）x*rk)krkP(x*)rk1P(x* k

)rkP(x* )+rk1P(x*k （rk

rk)(P(x*

)P(x*

0kkP(x* )P(x*kkk 结合）和（）4式f(x*)f(x* kk由（5）可知(*k

P(x)f(x*)f(x*)rkP(x* k(x*,rk)(x,rkkf(x) 式和（）5

(*kf(x* 所以，极限和(*,rk limf(x*k 存

k (xk,r)=f(xk)rP(xk所以极限存在k(*

rk k 以limP(x*0，再由的P(xk 有P(x*)=P(limx*)=limP(x*k k 这说明x*由）式x,ff(x*)=f(limx*)=limf(x*)fk k 所以*原约束问题的最优k外点法的不足：为了让无约束问题的最优解*k约束问题的最优解*,满足允许的误差精无法预料k竟要大到什么程度。显然，太大的 计算机在数值计算上 。另外，外点k在迭代过程中*某个充分大的处迭代rk对于某些实际问题，这样的近似最优解是不能被接内点内点法将增广目标函数定义于可行域内，序列迭代点在可行域内逐步近约束边界上的最优点。内点法只能用来求解具有不等式约束的优化对于只具有不等式约束的优化问题 f(s.t.g(x)

(j 一.惩罚函数形(x,r)f(x)

mm(k)m

gi(

ixr)fxrk)ln[g im(x,r)f(x)+r(k) mii1[g(i例1minFXg(X)1x先构造惩罚函数min(X,r(k))F(X)r(k xr(k g(X 1d1r(k (1x)2

解得r(kx(r(k))r(k=＝01r(k cr(k

k r=0.01,﹍﹍ x*→二.内点法构造惩罚函数应遵循原惩罚项min(X,r(k))F(X)r(k g(X当x由可行域内靠近任一约束边界时1g(X

三三min(X,r(k))F(X)r(k1g(X由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽管惩罚函数的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩罚项已是很例2用内点法 f(x)x2 1s.t.gx)x1 的最优解1解:首先构造内点惩罚函数(x,r)x2x2rkln(x rk2x x 2x22联立求解

12rkx(r12rk 2x(rk)2考虑约束

g(x)1x11x(r)111 最优点迭代

x(r0) x(r1) x(r2) x(rk) 四.算法步在可行域内部D0选择一个初始内点选取初始罚因子r(0)与罚因子降低系数c，并置求minφ(x(K),r(K))解出最优点K←K+1，r(K)←cr(K-1)，xK0←xK-1*，并转步骤按终止准则判别，若满足转步骤6），否则转步骤输出最优解（X*，F*），停止计算五.收敛条[x*[x*(rk),rk][x*(rk1),rk[x*(rk1),rk1x*(rk)x*(rk1)例3用内点法求下列问题的最优解：n(X)x1

g(X)x2x0 g2(X)x10解:构造惩罚函2(X,rk)F(X)rk j1gj(XXrFXrln(gX jj2或(X,rk)F(X)rk jj1g2(Xj(X,rk)

rkln(x2x2)rkln(x 2rk 1 x2

rkx2 x1

114

18r 18r rkx r01

X0X0 X1

F(X0)1当r0.52

X2

F(X)2当 0.25

F(

)当r30.125当rk0

X3Xk

F(X3)F(Xk)六.选取初始内点的算法步 （1）x0Rn,0c1k令

g(xk)0,1i

g(xk)0,1i i若 ,则x0D，迭代停止，否则转 i xg(x)0,iT 使minV )V(xk

k k其中V(x,k1gi(xk1

g 令k1

k1 (c1kk1转算法流

求内点混合罚函minf(x),x s.t.g(x) j h(x)j

i1,2,,jD0

g(x0i1~m若imi

1 i(x,r(k))f(x)r(k)lg[g(x)]i

r(k

[hj( minf(x)lgx1h(x)x2x24 g(x)x11构造混合罚函(x,r(k))(lgxx)1(x2x24)2r(k)lg(x r(k 01.553 11.334 3乘子算LgnLagraneLgage乘子的迭代进,乘子算法是对内点法,外点法,混合法的改明,乘子算法优于若是无约束极小化问题的最优解， 注意到可行 出是不可能的。

求 但当非常大时，罚函数问题Hesse矩阵呈现 外点法2(x,r)(x2

minf(x)s.tx21x2r(x

1)2 (x,r)

2(x1 2x2r(x 2(x,r)

2 k k

22r 子令是子问

p再看Lagrange乘子函数L(xf(xjhj(x)pj的驻h(x) L(x*,*)f(x*) k为了使x(kk比较上面两

jx*令------修正Lagrange乘子向量的迭代公然后再进行 次迭代， 继续迭代，直 ，从而如果不收敛或收敛很慢，可增大罚因子 再进行迭代。收敛快慢的一般标准是：，解处的Lagrange，广LagrangeLagrange而 o ，得到点> ，转否则进入 转乘子法求解下列问(x,,M)(2x2xxx2)(1)(xx2)M

(x,M)(2x

xxx2) x2)

x 6xx50,x4x5 x(1)

x(1)

,h(x(1))

(k(x,k）,M)(2x2xxx2)(k) x2)

x

3(k

12

x(k) 0x(k)

x(k)

5(k)20 由(k+1)=(k

Mh(x(k))(k

2(x(k

x(k

2)7(k

3(2)12 17

23

1

) 5(2)20 28 h(xh(x(2)h(x(1)

23**=1.75，此时仍

2

3*12 原问题最优解x*

,f(x*)5 5*5 该问题有唯一极小点* 0取为x 0h(x*)9.5107,

Mk1

x* 五．不等式约束的乘子算 出

于入上面了乘子法

2 11

12x2xxx2

max(0,M(xx

1

当1M(x1x22

xxx2+1M(xx2)22 1

4xxM(xx2)

x2xM(xx2)

6M x(1)8M

110M518M 当

2)0x,,M)=2x

2x2 214x 0,x 1 x(1)

g(x(120,

1 251设,

x(1) 2323修正

(k

max[0,(k

2(x(k)x(k

2)]111

1同理可得() (3) x(3)11最后可得原约束问题的最优解 x(3)1

7f(x*)7增广目标函矩阵范数、条件数与矩阵例考虑下面的两个线性方程2x1 6x2 与2x1 6x2 2x 2 x 其解分别为：xx1x 2

xx110x x 向量范XRn,若X的实值函数N(X)=‖X‖,满足条件非负性:‖X‖0,且‖X‖=0的充要条件为齐次性kX‖=|k|‖X:‖则称N(X)=‖X‖为Rn上的向量X的范定义：设X=(x1,x2,…,xn)TRn,则定义x21x2x21x2x2 X2向量的－范数

max{xi1i向量的1－范数

X1

xi1x矩阵范定义:设矩阵ARn×n,若A的实值函数N(A)=‖A‖,满足条件非负A‖0且‖A‖=0当且齐次A‖=||‖A三角不等柯西－施瓦茨不等则称‖A‖为矩阵A的范数定义：设向量XRn,矩阵ARn×n,且给定一种向量范数‖X‖p,则p p X

pmaxXp

,p1,2,为由向量范数派生的矩阵算子范数定理：设A=(aij)n×n,则对应于3种常见的向量范数，有3种矩阵范nA1max

列和的1

Amax

行和的 2

j

max是ATA的最大特征值，也称为谱范矩阵范数的一些 A0,&,A0A②AA, ABA A,B ABA A,B Ax

A

,x条件数 矩Axbb0A(x*x)bb cond(A) condA

AA定义：称条件数很大的矩阵 矩阵， 矩阵对应方程组 方程组，反之，则称A为良态矩阵常用的条件 (A) cond1(A)cond2(A)

A AAA

(AT (AT ATA代表矩阵ATA的最大特征判断矩阵是 ，有时并不计算A1，而由以下经验判行列式很大或很小（如某些行、列近似相关元素间相差大数量级，且无规主元消去过程中特征值相差大数 A

0.99

b1.990.99

0.

1.97计算cond(A)2精确解 1x精确解 1

9800 9900 = 9900 10000解：A是对称矩阵，其特征det(IA)

120.cond(A)22

39206>>向自动化学第一Frank-Wolfe自动化学 其中 记 一阶连续可微 近原问题，这是一个线性规划问设(2)最有形形1):若，则线划的时可证为问题的K-T：形1）现 则也 满足（2）的K-T条件而原问题(1)K-T ，，同时满足K-T条件故是原问题（1）的K-T点。情形2): ， 因为:若情形2)出现:显然,当然不是线性规划问题（2）的最优解，由是（2）的最优解，必有从而 在处的下降方向为为 设最佳步长因子 ，用取代，重复以上计算过程二、算法迭代步 ，

，Stop,；否则转4)进行一维搜索，得最优步长因子 ，，转2)

若迭代到某步，有则为原问题的K-T点若情形1）总不发生，则算法产生一有界无穷 ，其任意极限点都是原问题的K-T点。2(x 2(x f(x)2(x14f2(x 2(x

x

第一次迭minTf(x0)xmin20x1x1x2s.tx1x2 x, 用单纯形法求出此线性规划的最引入松驰变量x3x4

min20x1x1x2x3s.tx1x2x4

001110014820400f0 02101101182400f08x* 0T为该（LP）y08 8 2）Tf(x0)(y0x0) 4061448 60y0x0660 minf(x0(y0x0))minf(66,20 0f(66,26)664226 12(106)12(62)144144d0

x0(y0x0)

6T0880第二次迭代x1代替x0，重复以上步0 x f(x1)2x1 x 2x

x2 minTf(x1)xx1x2s.tx1x2 001110014800f000Tf(x1)(y1x1)

80064000 y1x10为搜索方向，对原目标函数作一维搜索求其最优步长 minf(x1(y1x1))minf(0,80 0d 01d 2

0令x2x1(y1x1) 1第三次迭代

4f(x2)2x18 8

0

x2 求解线性规minTf(x2)xx1x2s.tx1x2用单纯形法求出此线性规划的最 0011100148000f00Tf(x2)(y2x2) 000 x*x20即性自动化学一．线性近似规划的

是可行解，将，（3）求解由（2）和（3）

点,制 ,,题若满足可行性,则 转4),否则令,返2),重新解缩小步若,且满足则点为近似最优解,否则,近似规划法求解：第一次g(x(1))9.75,g(x(1)) 2x1 2x1g1(x)

2x,g2(x)

2 2x(1g(xg(x) g(x)g(x(1))g(x(1))T(xx(1)g1(x)g1 )(x (1) g(x)9.75

x1

40.25

x xg(x)4.25

x1

9.25

x x步长x

(1)

x1

x2

12x132,1x22.511x15,1.5x2又有约0x15,0x2101x11.5x2minf(x)2x140.256x15x29.756x 1x1把（1）（1）x1x2有上下界，如 ,即x 0,令

x

j

0j

x即可 x

tjx

t

0,x"t

xjx"0j

x"x即可 这里y1x11,y2x21x150y11.5x23.50y2minf(x)2y1y26y15y26y5 到 s.ty1yy用单纯形法解（2）式，可得

41 6 31对于g(x(2))1.6626g1 )1.0586 不满足原非线性规划的约束条第二次迭0.5减少步长限制为(2)(1) 返回修正上述近得到新的近似线性规划问题minf(x)2x140.256x15x29.756x 2x 2x2用单纯形法解（3）x(3)4,f(x(3g(x(3))0,g(x(3)) ) 第一次迭代近似(LP)可行域为凸集ABCDE,最优点A(463)第二次迭代:近似(LP)可行域为凸集FGHIJ,最优点F(440.256x15x2迭代点:x(1)A9.756x15x2f(X)第三

Rosen梯度投自动化学一、算法若当前迭代点位于约束域内部，此时负梯度 二、投影矩阵的基本 是线性空间的子空间，如果和中每个向量的分解式是唯一的，这个和被称为直投影矩阵：设 矩阵若 ，则称为投影矩设 2为投影矩

3若为投影矩阵 P设P为投影矩(IP)TIPTIIPIPIPPP2I2PPI3）PxL,Qx (Px)T(Qx)xTPT xTP(I xT(P xT(P 0,L 又xRnxIxPQ)xPxQxpqpLq显然这种表示是唯一的，若不然xpqp'q',p,p'L,q,q'ppq'q,ppLq'q而LL正交，则pp')T(q'q0即ppq'q,pp')Tpppp'20pp'0ppqqRnLL的直LL投影矩阵特定理： 是任一投影矩阵， 在处的一个下降方证明：欲证hf(xxTf(x)h0Pf(x0PPTPPPTf(x)hTf(x)Pf(x)Tf(x)PTPfPf(x)TPf(x)Pf(x)2考虑问题 ，一阶连续可微作分解，使

，是矩阵的若是的内点，

则为投影矩阵证明ATAAT)1A为投影 AT(AAT)1

AAT)1

(AAT

AT(AAT)1

AT(AAT)1AAT(AAT)1A AT(AAT)1AA AT(AAT ATAAT)1A为投影矩 PIATAAT)1 为投影矩 四．算法收敛 的可行解,在处则非零向量为处的可行方证明要性非零向量hx处的可行方向0,使得对(0,xh即A(xh) C(xh) 由（1）A1(xh)A1xA1hb1 b1A

AxAh AxA

b 2 20,A1h由（2）C(xh)dCxChCxd,Ch0ChA1h0Ch0h为可行方向00,A(xhbC(xh)A2xb200,A2(xh(0,),A(xh)又Ch0Cxd0C(xh)CxChCx故0当0,A(xhbC(xhxhDh为处的可行方如果同时满足， 应该是处的可行下降方向 令,（1）h0hf(xx处的可行下降方向证明：先证h为可行方 APA[IAT(AAT)1 AAAT(AAT) AhAPf(x)A1h0Ah0ChC C 再由条件hPf(x)0P为投影矩阵知hf(xx处的一个下降方向hPf(xf(xx处的可行下降方向(2h0若满足u0x为原（NLP）的K-T证明：hPf(x)0，即[IAT(AAT)1A]f(x) f(x)AT(AAT)1Af(x) 令AAT)1Af(xw，上式可以表示为 f(x)ATw0f(x)

u f(x)( CT)u v v 1f(x)ATuCTv1已知u0上式恰Kuhn-Tucher条件x满足K-Tx为原（NLP）的K-T（3）当若不满 ，则 中 的行，得到新

，并 替代， ，则

在处的一与（1）类似可以证明ˆ0为可行下降方向）由（1）结论，只须证明ˆPˆf(x)0即可。ˆ只须证A中有线性相关的行向量，与A行满秩 Pˆf(x)[IˆAAT)1A] f(x)(AAT)1Af(x ˆˆˆAT ˆTˆ

另一方Pf(x)[IAT(AAT)1A]f(x f(x)AT[(AAT)1Af(x f(x)AT 即Pf(x)f(x)ˆTwu

i其中ww中除去u后得到的1维向i0riA中对应ui

的行向 (1)-ˆTˆ) i0

r组成i0i 0,说明原A的行向量线0与A是行满 ˆˆˆAT)1Af(x w直接由uˆ构成，ˆ为u中直接划去 行所v v五、算法迭代步选取初始可行点，计算精度，作分 ，使 ,行满秩,其行秩2） , 3 若则停 为原（NLP）的K-T点 则 中划 对应的行向量，得到新 2）一维搜索，确定步 转 kminf(xkhkA(xkh) k必须满 ks.tC(xkh)k

分析约束条件h为可行方向，由引理， 0而xk为可行点，Cxk 显然约束条件（2）对任意0自然成立对于约束条件（1）A(xkhbA(xkh hk为可行方向，A1hkAxkb，所以只须0 minf(xkhk故问

A

A

2 而由AxkA bAh

A Axkb

Axk Ah0

2A2hk02max确定满

Axkminxk

h0,iI(xk i

Ah不满足

i

A2hk梯度投影算法求解：f(x)4x12x24x10 0 2x 0 第一 1）f(x14x10仅由3 I(x1)3,4A 0,b0,A

1, 2 1 0

5 A1A 0 （约束条件中没有等式约束2）PIAT(AAT)1 II 0 hPf(x1)00 0 i计算w，判定ui0w(AAT)1Af(x1

0 0T 04 uuu2uiminuimin4,66u2 故在A中划去对应于u26的行向量 ˆˆ 1ˆ1 ˆIˆAAT 0 1 1 10 00

1 1 ˆPˆf(x1) 040 求最大可行步长Aˆ

106 2 56

22

min

A 222 10 5 min

10 56 0 2 5 0 min 6 min 1 6

求x2

00

0 0 6 6 x10x26f(xf

)

1令 01,011d 故

1,

0

10

01 1 第一次迭代第二次迭 x20，I(x22,3,f(x2 AA

5 5 ,b , 0 ,b ,

1 , 1 , A1

0 PIAT(AAT)1 0 5T 5 5T 1 0 0 0 0 0

hPf(x2) 060 w(AAT)1Af(x2

5 5T 56

0 0 02 28

5 5 uuu 2 minumin2,2828 5 得ˆˆ,

28所对应的第二5 ˆIˆAAT 0 15 55

5 26 26

5

70

266

13h2Pf(x)

1

2 14

26 13 24计算

,

,x3

31第二次迭代第三 24

3对 31，f3

)

,I

) AA1 PIAT(AAT)1

526 26

532hPf(x3

1

w32u

26 3132

此时f(xug2x

31

故x3 为原（NLP)的全局最优 算法迭代过

Zoutendijk可行方自动化学一.线性约minf(x)(NLP)s.t.Ax CxAmnCpnbRmCRpx(NLP)xAA1,bb1,Axb,Ax 2 2

I(xiixbi,1i由上一节梯度投影算法我们知道向量hx处的下降可行方向的条Ah0,Ch0,f()Th 1于是通过解线性minf(x)T(LP)

Chxh显然，如h满足下降可行方向条件则对任意0,，向量h也必满足增加关于h的约束条件，比如minf(x)T Ah(LP)

Chjh ,j1j

定理(Farkas定理）设A ,cRn,则Ax0,cTx0有解充要条件是ATyc,y0无 minf 定理x(NLPs.t.Axb的一个可 CxAA1,bb1,Axb,Axb 2 2minf(x)T Ah

(LP)

Chjh 1,j1j

的最优解为(LP)的最优目标函数值小于h*必为原(NLP)在x处的一个下降可行方向(LP)的最优目标函数值h0显然是(LP)的可行解，故(LP)（1)(LP)0，即最优解h*1f(x)Th*0Ah*0,Ch*1h*x1不等式组f(x)Th Ah0,Ch0无解11Ah0Ch0Ch0f(x)Th01ATuCT v)f(x vv2v1，上式说明存在向量uv(u01f(x)ATuCTv1取初始可行x1kxk，作分AA1bb1AxbAxb 2 2

处的线性规划问题

minf(xk)T Ah Chj 1,j1j得最优解k

f(xk)Tk

0则停xkK-T，否则I(xk)xk处对应于不等式约束的主动约束标号集minixk

h0,iI(xk

Ah不满足max

2 A2hk求, f(xkh)f(xkh) 0 xk1

khkkk112.1.1用Zoutendijk可行方向法解下minf(x)x2x22x 2x1x21 xx2 x

0)T第一1）f(x(1)) 4)T，对x(1) 仅有34）约束起作用I(x1)3,4x(1)处，作分解A 0,b0,A

1,b 1 0

2 x(1处求可行下降方向h(1，minF(h)f(x(1))T(LP)

A1h

1,jminF(h)2h11 h1即(LP) h2 1h1 1h2用单纯形法解得：h(1) 2）确定Ah(1)

111

2bAx(1)min 2 A 21 10 min 1 11 1

2 10 0 0min

2min 2 2

一维搜索求步长(1x(20 1 x(1)h(1)00 1 x1x2f(xf(x(1)h(1))226令 03,0 d

故(1)1x(2)x(1)(1)h(1)F(h(160第二次迭 4）x(2)1，I(x(21,2,f(x A 1,b1,A 0,b0 1 0 在点x(2)处求可行下降方向h(2)，minf(x(2))T(LP)

A1h

1,jmin 2hh 即(LP) hh 1h1 1h2 5）确定Ah(2) 01 bAx(1)

(2)2 min ,A2

A 1 0 1 2A2

0,

16）一维搜索求步长(2),x(3) 1 1x(2)h(2)1 1 1 x11x21f(x中f(x(2)h(2))222令 01,0 d

1(2)1x(3)2

(2)

2 23 2第二次迭代结F(h(220，继续迭 3

7）对x(3) ，I(x(3))2,f(x(3)) 2

1 A 1,b2,A 0,b0 x(3)处求可行下降方向h(3)解线性规划问minF(h)f(x(3))T(LP)

1,jminF(h)h1 hh(LP

1h11h2 3F(h(3))0,由定理知，x(3) 是K- 2)

3为原（NLP)的全局最优

2二.非线性约 考虑不等式约束 f(x) gi(x)0,i其中n,f(xg(x)i

选择下降可行是在处起作用约束下标集又,

gi(x)f(x)gi(x)(iI(x))在处可微函,数在gi(x)(iI(x))连续,如果f(x)Th g(x)Thi则

iI f(x)Th gi(x)T

h (iI gi(x) gi(x)(iI(x))gi(xh) iI(x) 当(x)在可微(x gi(xh)gi(x)gi(x)Th+o(hgi(xh)gi

g(x)Th+o(h

i()Th,右端i0端由.gi(x)0(igi(xh)由上分析知,对充分小的gi(xh)0,i( 因此h为x处的下

minfs.t.gi(x)0,i1 x点处的可行下降方向d满足g(x)Td0,iI(x zzdf(x)Tdg(x)Tdz,iI(x) z下降最多的方向d由方向导数f(x)f(x)Th

f

hcosf(x),可知，以上问题可以转化为求使z最小的线性规划问minf(x)Tdz(LP)s.tg()Tdz0,iI(x dd

1,j1假如(LP)的最优解(z*d*z*0ii

有解d可行下降z*0ii

Gordan理可证此时x为原规划的FritzJohnit

,I(x){i|gi(x)证明:问题(7)的目标函数最优值为0的充要条是不等式f(x)Th无

Th0,(iI f(x)Th0,gi(x)T无解

h0,(iI 存在不全为0的数使w00wi0,i (

w0f(x)

wg(x)T 为求步长,求解一维搜索问题minf(x(k)h(k) 0 SUP{g(x(k

h(k))0,i1,...,m} 计算步给定初始可行点(1) k令(){i|gi(x(k)) LP) s.t.f(x)Thzgi(x)Thz

iI(x)hj1,j1,...,得最优解z,h(k),z;,,转,x(k Fritz 求解一维搜索minf(x(k)h(k)

0

得最优解 中由给kk

x

x(k

h(k)

k:k 3.Topkis-Veinott修 f(x)Thzgi(x)Thzgi

ihj1,jTopkis-Veinott算给定初始可行点(1)

k f(x)Thzgi(x)Thzgi

ihj1,j得最优解(zh(kk若 止 点;,xk),

Fritz求解一维搜索minf(x(k)h(k) 0其中由ax

5)x置k,(11(k x5)x置k

h(k) k:k 定理：考虑问题函 f(x),gi(x)(i连续可微又设是{(k) Topkis的序列则的{x(k)一聚点都是 第五节约梯度自动化学1963年，Wo1fe(ReducedGradientMethod).考虑具有线性约束的非线性规划问minf Ax x基本原用既约梯度构造假设问题(1)的约束是 的，且xA N),xxBx）可以表示

Nminf(xB,xNs.t.BxBNxNxB,xN B1bB1Nx，用非基变量 代入目标函数，得到即F(xNf(xB(xNminF(xNs.t.B

B1bB1N

xN当xB0时，称之为非 的情形，xB0表示xB的所有分量都大于0.xN0不带其它约束条件因此问题(2)是比原来问题（1）较低维的简单问 度r(xN)F(xNxBN f(xB(xN),xN)-(B1N)T f(xB(xN),xN)xBN由于（3）式中(N简后的个变量n(xN的梯度xN，所以称为的既约梯f(x，记为r(xN现在有了r(xN，我们要找f(x)的极小值，显然就可以沿负既约梯度方向(r(xN))搜索移xN，使得目标函数值下降。(k关键是如何确定在点xN处的可行下降方向 ？以及如何定步长

？以保x(k1)xk

h(k)是可行点，且目标k值下降kh(k)记h(k) h(k h(k)h(k)h(k)分别对应基变量和非基变量的分 为使目标函数值下降，h(k)应取负既约梯度方向h(k) N但是，当某个分量 0且rj(xN)0时j沿负既约梯度方向将导致决策变量非负性不满 rj(xN)0,j因此，定x(k)r(x(k)

r(x(k))h(khN

N

N N

rj(x(k))由前面引理知，为保证h(k)为可行方向，h(k)需要满Ah(k)0h(k) N

0Bh(k

Nh(k) h(k h(k)B1Nh(k

x(k)0因此h(k)x(k)也一定是可行方向，故 h(k)B1Nh(k)Nh(khN

下面确定步长k x(k1)x(k

h(k)k x(k1)x(kk

h(k

0,j1njh(k)0时，对任意的0（7）jjh(k)0时，应取j

(kxh(k)xhh(k)

min

(kxjx

h(k

其

(k h h定理：设x是问题（1）的可行解，A N mn矩阵B为m阶可逆矩

xT, 函数f(x在点x处可微，又设h是（4）和（5）式定义的方向，如果h0，则h是下降可行方向，而且h0的充要条xK-T既约梯度法的迭代步骤给出初始可行点x(1，容许误差0k从x(k)中选择m个大分量，它们的下标集记为 kAj列记为PjB是由PjjJk构成的mN是由PjjJk构成的mnm(3)求出 )，并由式（4）和式（5）求出h(k)和h(k) 从而得到搜索方向h(k

h(k

，则停止计算，得到点x(k)作为的最优解，停止迭代；否则，转由（8）式求 ，从x(k)出发，沿h(k)搜索minf(x(k)h(k)s.t.0得到最优解kx(k1)x(kk

h(kkk1 f(x)4x1, f(x)2x2 f(x(1))4, f(x(1)) r(x(1)) N

f(x(1))(B1N)TxBx

r(x(1))160,d(1)x(1)r(x(1)) N1 r(x(1))60,d(1)r(x(1)) r(x(1))50,d(2)x(2)r(x(2))

N1 r(x(1))50,d(2)r(x(2)) 第十次规划Quadratic自动化学第一节接消去自动化学什么是二次规划等式约束二次规划问题的解法直接消去法(DirectEliminationLagrange直接消去法(DirectElimination第二节Lagrange自动化学考虑二次规

min1xTHxcT2 Ax

Rank(A)m,xRn,bLagrange函L(x,)1xTHxcTxT(Ax 2令xL(x)0L(x)Axb ATx

c即

Lagrange矩阵可 AT

RT

，由 AT

In HQATRnHRTATSAQARTm

假设H1存在，由上述关系得到矩阵QR,S的表达QH1H1AT(AH1AT)1AH S(AH1AT 由（3）式等号两端乘以Lagrange矩阵的逆，则得到问题xQcRTRc

xx(k是（1）x(kAx(k)b，gkf(x(k))Hx(k)x(k)k

，可将（7）和（8）改xx(k

例用Lagrange minx22x2x2

x1x2x32x1x2x3解 H 0,c0,A

1,122

b4,H1

2 02

2 12

3

14 4

4 4Q 3,R

3

5

S4 2 11 3 代入得到问题的最优

3x

22第三节作用集方自动化学对于不等minf(x)1xTHxCT2s.tAx

Lagrange起作用集方法是利用起作用为起点，把在该点起作用的约束作为等式约束kx(k)指标集I(k)表示，求解等式约束问minfi aixi

iI(k

aiA的第ix(k处起作用约束函数x(k，令xx(k，则f(x)1(x(k))TH(x(k))cT(x(k))1THTHx(k)1x(k)THx(k)cTcTx(k 1THf(x(k))Tf(x