最优化习题答案及复习资料

最优化习题答案

第给一早辽

一、考虑二次函数/(乂)=£|+2工井2+3%；一孔+工2

1)写出它的矩阵一向量形式：”X)=；jQx+//x

2)矩阵Q是不是奇异的？

3)证明：f(x)是正定的

4)f(x)是凸的吗？

5)写出f(x)在点1=(2,1)'处的支撑超平面(即切平面)方程

解：l)f(x)=X；+2H+3%；-%|+

1TxV22M、(

111X|I+HI

dL(21

(22、-1

其中x=l'I，Q=!26!,b=l

{X2J

2、22

2)因为Q=，所以IQI==8>0即可知Q是非奇异的

、26>26

22

3)因为|2|>0,=8>0,所以Q是正定的，故f(x)是正定的

26

因为V2/(X)=1：2

4)，所以lyz2/(x)|=8>0,故推出▽是正定的,

6

即是凸的

所以可⑸=(5,ii)

5)因为wa)=(2x+2x-1,2X+6x+1)’,

212

所以/(x)在点X处的切线方程为5(无-2)+11(此-1)=0

二、求下列函数的梯度问题和Hesse矩阵

22

+9+3

1)f(x)=2Xi+XX2X1X3X2+128+2%2

2)/a)=/„(x+工2)

1122

解：1)守(》)=(4乂+%2+9%3，X+6X2+X3+2，9为+12)

(419、

V2/U)=161

、910)

2)V/(x)=(2。%十%,,—产212-)

++++

XIX|X2X1XIX%2X1

/222

2

工~-2纭-21工2-X-^XX_v2

益处+x；X2+蚪(X；W+X2)

V-/(x)

22

_2-2x

-Jf-4xx_2x-JC

l'(x2+xx+j^)(x"+XX+A：2f

I11221122

三、设f（X）=1；+工；+2］；+2%%-12-工3，取点%明（uU.验证

min

7⑴=(1,0,-1)是f(x)在点⑴处的一个下降方向，并计算

ax

证明：v/(x)=(2x,3X2+2X-1,4工+2x

12332-0

T

v/(x)=(2,4,5)

dW(X1)=(l,0,-D||4|=-3<0

所以d“）是f（x）在X⑴处的一个下降方向

f(%⑴+td“)=f((l+t，l，l-t))

=(l+r)2+l+2(l-ry+2(l-O-l-(l-/)=3f-3r+4

(I，<l)

Vf(x+t<7)=6t-3=0所以t=0.5>0

(1)(l)

所以mmf(x+tz/)=3*0.25-3*0.5+4=3.25

/>0

四、设〃,，,•，c(j=l,2,....,n)考虑问题

Minf(x)=£".

i='x)

2

stZj皿Xj=b

X20（j=l,2,....,n）

1）写出其KuhnTuker条件

i2

2）证明问题最优值是工〃/、！

疝Zj=l（Q/C/）2]

解：1）因[（_/=1,为目标函数的分母故Xj>0

所以九；（j=l,…,n）都为0

所以KuhnTuker条件为V/(x)+|jV//(x)=0

2)

得

故有

所以最优解是

叫向I]

五、使用KuhnTuker条J牛，求问题？

minf（x）=（x-1）+（X—2）

12

3

电一为=1

st乂+乂=2

^,>0，x2^0

的KuhnTuker点，并验证此点为问题的最优解

解：x=（l/2,3/2）NO故储，九;=0

则W)+|1V//,(X)+|L12/Z2(X)=0

=内=0，凡一

(20、，/

而寸/&)=(02jv2gi(x*)=0V2g2(x*)=。

V2Mx*)=。V2/z,(x*)=0，

"(X*)=V2/(X*)+儿*(x*)+&*V2g2(炉)+日”2/叱*)+%*内式工*)=V2/(x*)

T(x*)={y|VAry=OV/jry=0)={y|-y+y-1=0y+y-2=0}=

12,212[1221

故W/(x)x=8>o,

即其为最优解.

第二章

一、设f（x）为定义在区间［a,b］上的实值函数，x*是问题min{f（x）|a«x«^}

的最优解。证明：f（x）是［a,b］上的单谷函数的充要条件是对任意

eb

XrX2^^Xi^x2

满足f（九Xi+（1-九）M）〈max{f（无），f（H）}，e（0,1）

证明：不妨设则Xi〈入无+（1-九）％2<%2

"必要性"若九”+（1-九）工2<x

则由单谷函数定义知/（九为+（1-入）无）</（X）

故有/（九月+（1-九）域<max{/（x）,/（x2）J

4

“充分性”由④，%的任意性取•时，

则12＞九九1+（1一人）%＞11=、且f（入兀+（1-入）羽）＜乳”）

若取％=X时，f（a＞f（%2）

尤〈入XI+（l-九）％2＜工2=£且fS%十（1一人）％2）＜f（X1）

满足单谷函数的定义

二、设为〈乐，"无）＜0/%）＞0

1）证明：满足条件

＜P（X）=/（刘）,6a）=/,aw%）=/（12）的二次函数则X）是（严格）

凸函数

2）证明：由二次插值所得f（x）的近似极小值点（即（p（x）的驻点）是

__（x2-x）/W

x=H-/'（X）—/'（］）

21

或者

%-无

“一¥一尸（♦）-/'（%）

2I

证明：1）设中（幻=。12+云+。（a*0）

则（p'（x）=lax+b

由联（X）=2a为+匕=八煤

中'（工2）=24.2+.=/（%2）

得a=-（%）-八％＞＞Qb=f'（）_-（/'（♦2）一广（无））

、（、''（V—y）

2（9一X1）应Ar

或b=〃（）乂（尸（乂）一广（无））

w—oFx）一

故i）得证

2）（p（x）的驻点为工=—互一上叱纪

2a1r（x）-r（x）

21

_p.一（无一无）/（12）

或%=%2一

/'（*）—/'（¥）

5

三、设人*）=1公0、+/7，+。，0'=。＞0试证：共轨梯度法的线性搜索

2

min/（%⑹+1d⑹）=f（/+乙d"'）中，有

g'd，

（屋少。/

其中&=▽"?'）

证明：由已知，得V/（x）=0X+"

令中（。=+为t的凸二次函数。要使乙是（P⑺的极小点即

为驻点，故满足（P'（套）=0

而年,名）=▽f（-d（i））（T

=[Q(x(k)+td(k))+b]dw

=[Qxw+b+tQd(k)]da>

故有g，+。(屋町Q，=o

得t=~

k(d*))'Qd{k}

四、用共粗梯度法求解：

min3)=3/+]工2―工X―2%xeR

2,22121

取初始点x(，)=(-2,4)r

解：易知

(31-21

A=b=

I-11J10)

第一次迭代：r

v/(x)=(3%-%—2,x-x)g=守(九)=(-12,6)'

1221I1

*=-可(/)=(12,—6)，

6

线性搜索得步长

（d（D）Ad',（12,-6）［_3-l'Y-26

1-1人,

从而无*/+a小岛闿

第二次迭代：

W（x'"）=（6%g=（612）

T7‘T7217’17

B=_g"J

P，（即））"=；98

90

289

210

289,

线性搜索得步长：a?=L7

户(2)+a2d⑵/口

人人d

&=▽/(/)=(0,0)，

所以最优解为X*=(1,1)'

五、用拟Newton法求解：

min/(》)=1；+2］；一2羽工2-4苞/€/

取初始点x'=(1,1)7

解：1)DFC法

取初始对称矩阵

(\0、

"小〔。b

第一次迭代：

计算得4=(-4,2)'，

7

T

-=-Hig「(4,一2)

经一维线性搜索得：a『025

.=Xi+ad=(2,0.25)'

8,=(1-0.5/

Z=(V4)r

r

g2=(-l-2)

r=§1Y=0.2

y

「0.20)

置正田1。(J

rr〃八HyyHr0.728—0.204、

+浮一i"=_0,7040.472I

第二次迭代

d2=—/Lgu(032,0.24)'经一维线性搜索得：a।=6.25

%3=%2+。2〃2=(4,2)7

g.r(0,0)7

故最优解为：x=Xy=(4,2)

2)BFGS法

fl0、

取定初始对称矩阵Hl=

(U1J

第一次迭代：

计算得&=(-4,2)，

T

-=—"g=(4,—2)

经一维线性搜索得：a尸0.25

8

T

羽二无+a.=(2,0.25)

(0.20]

同DFP法，初始修正矩阵=I八

I。0.2；

T

(1+y"一16-HybyH

乩=乩+/y"；「I「T^

5.y,iJ

第二次迭代：

T

%=一“2&=(°403

经一维线性搜索得：a2=5

%=羽+0124=(4,2)'

r

g3=(0,0)

*T

故最优解为：％=X：=(4,2)

辽

第AMe二--早

一、给定问题

22

min/(》)=］；+%%2+2工2—6乂一14工2

%+总+羽=2

s.t.-尤+212<3

^,>0,^2>0,^3>0

取初始点f"=(1,1,0)'，用简约梯度法求其最优解

++2

xix2x3=

解：约束条件为J+2N3

X>0，x2^0，x,^0

⑴TC110、

则％=(1,1,0)，A=s201J

V〃x)=(2x+%-6x+4x-1400)

1212

g「(-3-900/

9

10、

1T

.g,.v=v/押-(一1N)vfM

3,r44,

d.*jdB=-BNd『~

EI33j

—4A40-4)丁

33

(pz(a)=尸(1⑴+a

43。

93

得aJ

82I,

a=min{--}=-}=

max_421max

15T

x——。0)

(11-700V

g=~

2I3J

，inno]

r-/10)B=IN=I

/2-“02；101J

21愫1

1V

U—

M

3」1

H-

11

gN--3H

Q——

1

-7J

33-7/

九/

[o

d=-1Nd

NB-N=

l0

\7

d⑵=°

10

157

故X⑵=(——。。)为问题的K-T点

33

二、用梯度投影法求解问题，，

min/(%)=(x+2)~+(x-3)

12

2%「312-3=0

s.t.L

取初始点了⑴=(31/

解：v/(x)=(2x+4,2%-6)

12

迭代(1)8=(10,-4)'/,={i}

投影矩阵尸=/-4：(445’A=岁4

F-I

T11313；

6644

3442

①(a)=〃/+a/)=(3——a+2)+(1-a-3)

1313

13288.,

(p(a)=-_a+10二a-4=0

1313

39

a=—

110

39_13

a=minL

max664444

故。=血11{01,。}=—

1maxJ44

3T

x(=x2)+o(h1)d,=(j(i)，u/))

2

乩=(7,-6)'九={1,3}

rA20、TT-ir00、

故A=1_3J投影矩阵P=/-A(A2A2)4=[oo/

—=-尸4=(°，0)7

11

令〃⑵=(A2*)Ag2=(2'5)

37一一

故］⑵=(一，°)为其K-T点

2

三、用可行方向法求解问题，，

min/(%)=(x一2)+(x-1)

12

2天+4*7

s.t.2为-*2

X(>0，x2^0

取初始点3"=(0,0)'

解：VW=(2x—4,2%—2)

12

迭代一：=(-4,-2)

有效约束/1={3,4}确定下降方向

min-44-2%

de。

s.t.d/0i=l，2

-\<d^

解得&=由小且其最优值为-6,即处的搜索方向

/=(□)「

线性搜索(P(a)=/(x'"+ad"')=2a2-6a+5

3

(p'(a)=4a-6=0na=_

2

77

而f-

amijlr=

-6

a=min{4}11

1266r

77

(2)(1),j(0/\

x=x+a/=(：，：)

66

12

T

迭代2：V/a⑵)=(_5L)

33

有效约束/尸{i}确定下降方向

51

m1n-一4+；力

JJ

s.t.2di+：d2»°i=i,2

-l<d,《i

得d⑵=(1,_D'且其最优值为-2

线性搜索(p(a)=f(x⑵+ad°')=2a2-2a+)

1o

1

(pf(a)=4a-2=0=>a=-

而a=min{5-

mL18618

(X=min{l,_5}=5

121818138r

(3)(2))⑵/\

x=x+a2d=(§5)

in?T

迭代3：守a⑶)=(一「一n

99

有效约束A={2}确定下降方向

102

min

一一9八利2

s.t.2q一,2之。i=i2

-\<d^

得d⑶=（L1,i）7，其最优值为n

线性搜索（p（a）=/（d）+ad（"）=：a2-Za+为

57

」⑺-Oa

--45一

2-

a-914

77

而ml-

a-r-

n(2}6

a

3

13

37

(

+d/

一

=3)一

Xa一

2k2

迭代4：守（/）=（—1,0）'

有效约束/尸｛1,2｝确定下降方向

min-dy

2，+4仆。

s-t.匕1,2

-\<d^

得d'4）=（0,0）'，其最优值为o

3T

X,=/=（「l）为KT点

2

四、设（P）

min/（x）

s.t.Ax=Z?,x>0

其中，AwR""",bwR"',/为连续可微函数，D为问题的可行域，设

工“屋尤为下述线性规划问题的最优解：

min▽/（”）了

s.t.Ay=b,y>Q

1）若▽/（x（&））7匕一f）=0，则%"）是问题（P）的Kuhn-Tucker点/

2）若v（x（Q）'（y则y/x0是x0处的下降可行方向/

3）若v（x（Q）'（y-/'b-o,且f为凸函数，则%伏）是最优解

证明：1）因为minV/（x（"））'y的最优解

s.t.Ay=b,y>Q

T

故有v/（x⑻）（匕--）«0

14

假设不")不是(P)的Kuhn-Tucker点

^f(Xy)d<0

则\d>0有解

令1='一3",则y-兀")20,y20,月.Ay==b

故v/G⑹)"叮CM匕(叮CMy

即有叮(斓)'(匕-/巨0与叮(产)3--)<。

矛盾

2)因叮(幺町(乂--)/0故有2/(%(町(匕--)<。

故％-3"是1出的下降方向

w

又A(/一/))=0且若看=0(ze£(x))

故是可行方向

3)Vxe。/(x)N/(/)+▽/(”)%-/)

TT

=5+v-f)+叮(”)(乂--)

T

=5+▽/(”)f)

>W)

故x(“)为最优解.

第四章

一、用罚函数K[g(x)l求解问题

77

min/(x)=x；+2x；

15

s-t.x+x，-1-0

解:问题的增广目标函数为，

T(x，3)=d+2x，3(min{O,x-1})

I212

因此T=氏1ni4--1>0

+2%；X,X2

+2纭+3(%+%—1)X+X-1<0

21212

由旦=”。得

8d

XtX2

X|+X,TN0时x=(0,0)‘

288

为+距-1＜。时得X§)=()

2+382+33

21

当Bf+oo有*6)=(一,白

21,

满足条件,故x=limx(s)=(,)

8r33

用罚函数K』g,(x)]求解问题

minf(x)=(x—D+(X-2)

12

X2-Xi=i

2

s.t.X+X2

X,^0，x2>0

解：l)为+为<2，时

222

T(X,3)=G—1)+(X—2)+8(%—X—1)

1221

由@=或=0得2X]-2-2(%2-X1-l)8=0

dd2_1

X\X2[X2-4+2(X2-x)8=o

解得X(B)=(1+31+33)

1+2851+28

/.13,

故得limx(5)=(-9

8->oo22

16

2)%+%42，X^0，x2<0时

T(x,3)=(x—1)+(X—2)+8(x—X—1)+5X

12212

由包=位=°得!2兄一2-2(无一X-1)3=0

55

XX212工2_4+2(%2-x「l)3+25%2=0

解得x(8

limM3)=(-1,0)，

6—>8

3)Xi+X2-2，x<0，X2-°时

T(x，b)=(x-1)+(X—2)+8(X—X—1)+3%一

1221i

由包=包=0得12%-2-2(乂-X-师+23无=0

e2

X,°无1X2-4+2(%2-X-1)5=0

28+132+63+2，

解得45)=(°1，°)

82+38+b2+36+1

limx(8)=(0,lJ

8->8

4)无+为>2，时

T(x,8)=(x-1)+(%-2)+8(%-x-1)+S(2-x-x)2

122112

由0=包=0得f2X|-2-2(x2-X1-l)8-25(2-^,-X2)=0

a2

X1lX-4+2(X2-X-l)5-28(2-X,-%2)=0

解得x(b)=(l+62+33)

1+26'1+23

131

故得limx®)=(,0

6f822

+2

5)xtx2^,Xi<°，X2<。时

17

”)山「1)+(12-2)+3(%-々-1)2+31+母

由JI=垃=0得12无-2-2(x「x「l)5+23左=0

dd

X\X22工2-4+2(%2-为-1)3+25工2=0

-62+38+1狷噫

解得x(8)=(1,3

k382+45-1，J1

11T

故得limMB)=(-,)

j33

2

6)Xi+X2>，%?°，12<°时

222o

T(x,5)=(x—1)+(X—2)+8(%-x—1)+3V+3(2—x__x)2

1221212

由

ST=AT=0得/24-2—2(%,-%=1)5-23(2-④-乂)=0

d

X2上电―4+2(趋—1)3+25趋―23(2—/-8)=0

解得x(g=(l+b2+36

1+2891+38

1T

故得limMb)=(』)

6Too9

7)无+%>2，尤<。，％20时

T(x,b)=(x—1)+(X-2)+8(x-X—1)+5Z+5(2—%~X)2

1221i12

由

STdT„

------=------=0

dd

X\x2

1382Xy•Xo

-X7-28(-2/I=

X-1一1+-22)-o

得2丫-4+2(工-1)3-x-

I2728T

1+8+3K

)

解得X。)=(+28z

1+383

故得limx(s)=(L

2

i3

时

>2

8)X+X2，Xi

18

z8z

+u+uX+6X+8X

22)22

3忆

由o

3a

X2

22第+28o

--X一X=

—

得1(2

4+D52S22X)=o

2+28(--

2

解得X（B）=（1+62+33）

1+3851+38

1T

故得limM3）=（』）

8->oo3

.I3T

综上所述，有X=（

22

三、用罚函数hig（x）求解问题1

解：目标函数为

22

F（x,r）=x'+2x'+r\n（x+X-0

I212

d

x2

2X+~=0

（1X3X2-1

rt

得x&）=I-Vl-3r1占/1-3r、

1，6

21,T

于是有lim无⑺=（，2或（0,0）

F33

21'

故有％*=（一,—.

33

19

简答题

min-5必+9y2,

s.t.4yi+3y2N3,

1.-2yi+y2>-2,

3yl-4y2=8,

必，叫40；

15

2.-x+-x>0,(以xi为源行生成的割平面方程)

636A

注意：在再为整数的情况下，因为X3，920,该方程自然满足，这是割平面的退化情形

1工1、1

-X.+^4(以X2为源行生成的割平面方程)

4342

3.

a］=0,4=3

九1=%+0.382(，一《)=0+0.382*3=1.146

内=%+0.618(仇一4)=0+0.618*3=1.854

(p(X,)=(1.146)3-2*1.146+1=0.2131

①(内)=(1.854)3—2*1.854+1=3.6648

事实上，不经计算也可以看出(p(A，i)<(p(gi),所以生=0，历=1.854。

即：初始的保留区间为［0,1.854］。

近似的最优解：x*=21曾=0.927.

2

/(x)=x-2.7=x*-2.7

11I

f(x)=xe-x^0>-l=x-1

4人211

4-堂/(x)=xeT2*a)_O.4=xeF_0.4

f(x)=xe-&*⑵-0.1=xe-24一o.l

1I1

4

拟合问题等价于求解下列最小二乘问题：min£(/(x))2

j=l

计算题

1.分别用最速下降方法和修正的牛顿法求解无约束问题min/(x)=x2+4x2„

12

20

取初始点x⑴=（2,2）',£=0」.

（1）T/4）

解：W=l8xI，在初始点x=（2,2）,V/=|16|

I2）I）

从而最速下降法的搜索方向为：J164\

=.,I.

最优步长〃满足/(尤⑴+九*加)=min/(%⑴+M/1)

其中/(x⑴+M)=/(2—4九,2—162)=(2-软>+4(2—16)>.

求解得到：X=17/130,从而

”)=(2,2)7+17/130*(-4,-16)?=(96/65,-6/65),

在X。）=（96/65,—6/65），，收092/65）

=-48/65：

从而最速下降法的搜索方向为：/J-192/6平

、48/65/

继续迭代，直至满足精度。

在初始点%。）=（2,2）「，

（20、

G=,C

108J

从而修正的牛顿法的搜索方向为：

d'=-G-|V/-_Jl/2叫

=一0

1/8人⑹{-2J

最优步长X满足/("1)+寸/)=叫n“X⑴+M/1)

/(—)+入/)=/(2-2X,2-2X)=5(2-2九)2.

易见：九=1,从而

尤。）=（2—2九,2—2入）,=（0,0）r

在X。）=（0,0）。Vf（0^

=d，显然满足精度。

(1分)

2

V/,厂仅〔0801正定，x（2）即为所求的极小点。

21

min/(x)=x2+x2-6x-+8

1212

fxi+X2<4

x—x<0j

2

2.讨论约束极值问题s.t.I>x0的Kuhn-Tucker点。

j1-

x2>0

W(x)=[2xi-6,2尤2-6]T

g(x)=x+x—4,Vg(九)=

1121