《最优化方法》课程复习考试

《最优化方法》复习提要 第一章 最优化问题与数学预备知识

§1. 1 模型

无约束最优化问题 minf(x),x(x1,x2,,xn)TRn．

约束最优化问题〔S{x|xRn,gi(x)0,i1,2,,m;hj(x)0,j1,2,,l}〕

minf(x);minf(x); 即 s..tgi(x)0,i1,2,,m, txS.s..h(x)0,j1,2,,l.j其中f(x)称为目标函数，x1,x2,gi(x)0(i1,2,,xn称为决策变量，S称为可行域，

,l)称为约束条件．

,m),hj(x)0(j1,2,§1. 2 多元函数的梯度、Hesse矩阵与Taylor公式

定义 设f:RnR,xRn．如果n维向量p，xRn，有

f(xx)f(x)pTxo(x)．

那么称f(x)在点x处可微，并称df(x)pTx为f(x)在点x处的微分．

如果f(x)在点x处对于x(x1,x2,,xn)T的各分量的偏导数

f(x),i1,2,xi,n

都存在，那么称f(x)在点x处一阶可导，并称向量

f(x)(f(x)f(x),,x1x2,f(x)T) xn为f(x)在点x处一阶导数或梯度．

定理1 设f:RnR,xRn．如果f(x)在点x处可微，那么f(x)在点x处梯度

f(x)存在，并且有df(x)f(x)Tx．

1 / 44

定义 设f:RnR,xRn．d是给定的n维非零向量，ed．如果 dlim0f(xe)f(x)(R)

f(x)． d存在，那么称此极限为f(x)在点x沿方向d的方向导数，记作

定理2 设f:RnR,xRn．如果f(x)在点x处可微，那么f(x)在点x处沿任何非零方向d的方向导数存在，且

f(x)df(x)Te，其中e． dd定义 设f(x)是Rn上的连续函数，xRn．d是n维非零向量．如果0，使得(0,)，有f(xd)〔>〕f(x)．那么称d为f(x)在点x处的下降〔上升〕方向．

定理3 设f:RnR,xRn，且f(x)在点x处可微，如果非零向量dRn，使得f(x)Td〔>〕0，那么d是f(x)在点x处的下降〔上升〕方向． 定义 设f:RnR,xRn．如果f(x)在点x处对于自变量x(x1,x2,,xn)T的

2f(x)各分量的二阶偏导数(i,j1,2,xixj阶可导，并称矩阵

2f(x)2x12f(x)2f(x)x2x12f(x)xnx1那么称函数f(x)在点x处二,n)都存在，

2f(x)x1x22f(x)2x22f(x)xnx22f(x)x1xn2f(x)x2xn

2f(x)2xn为f(x)在点x处的二阶导数矩阵或Hesse矩阵． 定义 设h:RnRm,xRn，记h(x)(h1(x),h2(x),hi(x)(i1,2,,m)在点x处对于自变量x(x1,x2,,hm(x))T，如果 ,xn)T的各分量的偏导数

2 / 44

hi(x)(i1,2,xj,m;j1,2,,n)

都存在，那么称向量函数h(x)在点x处是一阶可导的，并且称矩阵

h1(x)x1h2(x)mnh(x)x1hm(x)x1h1(x)x2h2(x)x2hm(x)x2h1(x)xnh2(x)xn

hm(x)xn为h(x)在点x处的一阶导数矩阵或Jacobi矩阵，简记为h(x)．

例2 设aRn,xRn,bR，求f(x)aTxb在任意点x处的梯度和Hesse矩阵．

解 设a(a1,a2,f(x)ak(k1,2,xk,an),x(x1,x2,T,xn)，那么f(x)akxkb，

Tnk1因,n)，故得f(x)a．

2f(x)又因0(i,j1,2,xixj,n)，那么2f(x)O．

1TxQxbTxc为二2例3 设QRnn是对称矩阵，bRn,cR，称f(x)次函数，求f(x)在任意点x处的梯度和Hesse矩阵．

解 设Q(qij)nn,x(x1,x2,f(x1,x2,,xn)T,b(b1,b2,,bn)T，那么

n1nn,xn)qijxixjbkxkc，

2i1j1k1nf(x)nqxbqxx1jj11jjb1j1j11Qxb． 从而f(x)nnf(x)qxbqxbnxnjjnnjjnj1j13 / 44

f(x)nqijxjbi(i1,2,再对

xij12f(x),n)求偏导得到qij(i,j1,2,xixj,n)，于

是

q11q12q21q222f(x)qn1qn2q1nq2nQ． qnn例4 设(t)f(xtd)，其中f:RnR二阶可导，xRn,dRn,tR，试求(t),(t)．

解 由多元复合函数微分法知 (t)f(xtd)Td,(t)dT2f(xtd)d． 定理4 设f:RnR,xRn，且f(x)在点x的某邻域具有二阶连续偏导数，那么f(x)在点x处有Taylor展式

1f(xx)f(x)f(x)TxxT2f(xx)x,(01)．

2证明 设(t)f(xtx),t[0,1]，那么(0)f(x),(1)f(xx)．按一元函数Taylor公式(t)在t0处展开，有

(t)(0)(0)t()t2,(0t)．

从例4得知(0)f(x)Tx,()(x)T2f(xx)x．

121令t1，有f(xx)f(x)f(x)TxxT2f(xx)x,(01)．

2根据定理1和定理4，我们有如下两个公式

f(x)f(x)f(x)T(xx)o(xx)，

12f(x)f(x)f(x)T(xx)(xx)T2f(x)(xx)o(xx)．

2§1. 3 最优化的根本术语

定义 设f:RnR为目标函数，SRn为可行域，xS．

〔1〕 假设xS，都有f(x)f(x)，那么称x为f(x)在S上的全局〔或整体〕极小点，或者说，x是约束最优化问题minf(x)的全局〔或整体〕最优解，并称

xS4 / 44

f(x)为其最优值．

〔2〕 假设xS,xx，都有f(x)f(x)，那么称x为f(x)在S上的严格全局〔或整体〕极小点．

〔3〕 假设x的邻域N(x){xRnxx}(0)使得xN(x)S，都有f(x)f(x)，那么称x为f(x)在S上的局部极小点，或者说，x是约束最优化问题minf(x)的局部最优解．

xS〔4〕 假设x的邻域N(x)(0)使得xN(x)S,xx，都有

f(x)f(x)，那么称x为f(x)在S上的严格局部极小点．

第二章 最优性条件

§2.1 无约束最优化问题的最优性条件

定理1 设f:RnR在点x处可微，假设x是问题minf(x)的局部极小点，那么f(x)0．

定义 设f:S(Rn)R在xintS处可微，假设f(x)0，那么称x为f(x)的平稳点．

定理2 设f:RnR在点x处具有二阶连续偏导数，假设x是问题minf(x)的局部极小点，那么f(x)0，且2f(x)半正定．

定理3 设f:RnR在点x处具有二阶连续偏导数，假设f(x)0，且2f(x)正定，那么x是问题minf(x)的严格局部极小点． 注：定理2不是充分条件，定理3不是必要条件．

3例1 对于无约束最优化问题minf(x)x12x2，其中x(x1,x2)TR2，显然 2Tf(x)(2x1,3x2),xR2，令f(x)0，得f(x)的平稳点x(0,0)T，而且

022202f(x),f(x)． 0006x25 / 44

易见2f(x)为半正定矩阵．

但是，在x的任意邻域xx，总可以取到x(0,)T，使f(x)f(x)，

2即x不是局部极小点．

24x2例2 对于无约束最优化问题minf(x)x142x12x2，其中x(x1,x2)TR2， 23T,4x12x24x2)，从而得平稳点x(0,0)T，并且 易知f(x)(4x134x1x2212x124x2f(x)8x1x228x1x2200,f(x)． 22004x112x222)在x处取最小值，即x为严显然2f(x)不是正定矩阵．但是，f(x)(x12x2格局部极小点．

1132例3 求解下面无约束最优化问题minf(x)x13x2x2x1，

33其中x(x1,x2)TR2， 解 因为

0x12122x1f(x)2,f(x)，

02x22x22x22x110,所以令f(x)0，有2

x22x20.1111解此方程组得到f(x)的平稳点x(1),x(2),x(3),x(4)．

0202从而

20220(2)2f(x(1)),f(x)，

020220220(4)2f(x(3)),f(x)．

0202由于2f(x(1))和2f(x(4))是不定的，因此x(1)和x(4)不是极值点．2f(x(3))是负定的，故x(3)不是极值点，实际上它是极大点．2f(x(2))是正定的，从而x(2)是严格局部极小点．

6 / 44

定理4 设f:RnR是凸函数，且f(x)在点xRn处可微，假设f(x)0，那么x为minf(x)的全局极小点．

推论5 设f:RnR是凸函数，且f(x)在点xRn处可微．那么x为minf(x)的全局极小点的充分必要条件是f(x)0． 例4 试证正定二次函数f(x)1TxQxbTxc有唯一的严格全局极小点2xQ1b，其中Q为n阶正定矩阵．

证明 因为Q为正定矩阵，且f(x)Qxb,xRn，所以得f(x)的唯一平稳点xQ1b．又由于f(x)是严格凸函数，因此由定理4知，x是f(x)的严格全局极小点．

§2.2 等式约束最优化问题的最优性条件

定理1 设f:RnR在点x处可微，hj:RnR(j1,2,连续偏导数，向量组h1(x),h2(x),,l)在点x处具有一阶

,hl(x)线性无关．假设x是问题

minf(x);thj(x)0,j1,2,s..的局部极小点，那么vjR,j1,2,l,l

,l，使得

f(x)vjhj(x)0．

j1称L(x,v)f(x)vTh(x)为Lagrange函数，其中h(x)(h1(x),h2(x),称v(v1,v2,,vl)T为Lagrange乘子向量．

,hl(x))T．

lxL易见L(x,v)，这里xL(x,v)f(x)vjhj(x),vL(x,v)h(x)．

Lj1v定理2 设f:RnR和hj:RnR(j1,2,,l)在点xRn处具有二阶连续偏

导数，假设vRl，使得xL(x,v)0，并且，zRn,z0，只要

7 / 44

zThj(x)0,j1,2,,l，便有zT2xxL(x,v)z0，那么x是问题

minf(x);thj(x)0,j1,2,s..,l

的严格局部极小点．

2minf(x)x12x2;例1 试用最优性条件求解 

th(x)x1x280.s..2x1vx22v(x1x28)，那么L(x,v)2x2vx1， 解 Lagrange函数为L(x,v)x12x2(xx8)12从而得L(x,v)的平稳点(8,8,2)T和(8,8,2)T，对应有

x(8,8)T,v2和x(8,8)T,v2．

2由于L(x,v)v2xxv22x2,h(x)x． 2221因此

M(x){(z1,z2)T|(z1,z2)h(x)0}

{(z1,z2)T|z1x2z2x10} {(z1,z2)T|z1z2}．

T2222并且zM(x),z0，有zxxL(x,v)z2z14z1z22z28z10．

利用定理2，所得的两个可行点x(8,8)T和x(8,8)T都是问题的严格局部极小点．

§2.3 不等式约束最优化问题的最优性条件

xdS,(0,)，定义 设SRn,xclS,dRn,d0，假设0，使得，

那么称d为集合S在点x处的可行方向． 这里clS{x|xRn,SN(x),0}．

令 D{d|d0,0,使xdS,(0,)}，

8 / 44

F0{d|f(x)Td0}．

定理1 设SRn是非空集合，f:SR,xS,f(x)在点x处可微．假设x是问题minf(x)的局部极小点，那么 F0xSD．

对于

minf(x);tgi(x)0,i1,2,s..其中f:RnR,gi:RnR(i1,2,令I(x){i|gi(x)0,i1,2,,m, 〔1〕

,m)．

,m}，其中x是上述问题〔1〕的可行点．

定理2 设x是问题〔1〕的可行点，f(x)和gi(x)(iI(x))在点x处可微，

gi(x)(iI(x))在点x处连续，如果x是问题〔1〕的局部极小点，那么 F0G0，

其中G0{d|gi(x)Td0,iI(x)}．

定理3 设x是问题〔1〕的可行点，f(x)和gi(x)(iI(x))在点x处可微，

gi(x)(iI(x))在点x处连续，假设x是问题〔1〕的局部极小点，那么存在不全

为0的非负数u0,ui(iI(x))，使

u0f(x)iI(x)ug(x)0． 〔x称为Fritz John点〕

ii如果gi(x)(iI(x))在点x处也可微，那么存在不全为0的非负数u0,u1,使

mu0f(x)uigi(x)0,〔x称为Fritz John点〕 i1ug(x)0,i1,2,,m.ii,um，

minf(x)x1;tg1(x)(1x1)3x20, 试判断x(1,0)T是否为Fritz John点． 例1 设s..g2(x)x20.100解 因为f(x),g1(x),g2(x)，且I(x){1,2}，

0119 / 44

1000所以为使Fritz John条件u0u1u2成立，只有u00才行．取

0110u00,u1u20即可，因此x是Fritz John点．

定理4 设x是问题〔1〕的可行点，f(x)和gi(x)(iI(x))在点x处可微，

gi(x)(iI(x))在点x处连续，并且gi(x)(iI(x))线性无关．假设x是问题〔1〕

的局部极小点，那么存在ui0(iI(x))，使得

f(x)iI(x)ug(x)0． 〔x称为K-T点〕

ii如果gi(x)(iI(x))在点x处也可微，那么存在ui0(i1,2,mf(x)uigi(x)0,〔x称为K-T点〕 i1ug(x)0,i1,2,,m.ii,m)，使得

minf(x)(x11)2x2;例2 求最优化问题s..tg1(x)x1x220, 的K-T点．

g2(x)x202(x1)10解 因为f(x)1,g(x),g(x)12，所以K-T条件为

1112(x11)u10,1uu0,12u1(x1x22)0, ux0,22u10,u20.假设u20，那么u11，这与u10矛盾．故u20，从而x20；

假设x120，那么u12，这与u10矛盾．故u10，从而u21,x11； 由于u10,u20，且x(1,0)T为问题的可行点，因此x是K-T点． 定理5 设在问题〔1〕中，f(x)和gi(x)(i1,2,,m)是凸函数，x是可行点，

并且f(x)和gi(x)(iI(x))在点x处可微．假设x是问题〔1〕的K-T点，那么x是问题〔1〕的全局极小点．

10 / 44

§2.4 一般约束最优化问题的最优性条件 考虑等式和不等式约束最优化问题

minf(x);tgi(x)0,i1,2,,m, 〔1〕 s..hj(x)0,j1,2,,l,其中f:RnR,gi:RnR(i1,2,,m),hj:RnR(j1,2,,l)．

,m}．

并把问题〔1〕的可行域记为S．xS,I(x){i|gi(x)0,i1,2,定理1 设x为问题〔1〕的可行点，f(x)和gi(x)(iI(x))在点x处可微，

hj(x)(j1,2,,l)在点x处具有一阶连续偏导数，gi(x)(iI(x))在点x处连续，

并且向量组h1(x),h2(x),点，那么 F0G0,hl(x)线性无关．假设x是问题〔1〕的局部极小

H0，

这里F0{d|f(x)Td0}，G0{d|gi(x)Td0,iI(x)}，

H0{d|hj(x)Td0,j1,2,,l}．

定理2 设x为问题〔1〕的可行点，f(x)和gi(x)(iI(x))在点x处可微，

hj(x)(j1,2,,l)在点x处具有一阶连续偏导数，gi(x)(iI(x))在点x处连

续．假设x为问题〔1〕的局部极小点，那么存在不全为0的数u0,ui(iI(x))和

vj(j1,2,,l)，且u0,ui0(iI(x))，使

u0f(x)iI(x) ug(x)vh(x)0． 〔x称为Fritz John点〕

iijjj1l假设gi(x)(iI(x))在点x处也可微，那么存在不全为0的数u0,ui(i1,2,vj(j1,2,,l)，且u0,ui0(i1,2,,m)和

,m)，使

mlu0f(x)uigi(x)vjhj(x)0,〔x称为Fritz John点〕 i1j1ug(x)0,i1,2,,m.ii11 / 44

2minf(x)x12x2;tg1(x)x13x20,s..例1 设 试判断x(1,0)T是否为Fritz John点．

g2(x)x20,h(x)(x11)2x20.200解 I(x){2}，且f(x),g2(x),h(x)，且I(x){1,2}，

0112000因此为使Fritz John条件u0u2v成立，只有u00才行．所

0110以取u00,u21,v1，即知x是Fritz John点．

定理3 设x为问题〔1〕的可行点，f(x)和gi(x)(iI(x))在点x处可微，

hj(x)(j1,2,,l)在点x处具有一阶连续偏导数，gi(x)(iI(x))在点x处连续，

,l)线性无关．假设x是问题〔1〕的

,l)，使

且向量组gi(x)(iI(x)),hj(x)(j1,2,局部极小点，那么存在数ui0(iI(x))和vj(j1,2,lf(x)iI(x)ug(x)vh(x)0． 〔x称为K-T点〕

iijjj1如果gi(x)(iI(x))在点x处也可微，那么存在数ui0(i1,2,vj(j1,2,,l)，使

,m)和

mlf(x)uigi(x)vjhj(x)0,〔x称为K-T点〕 i1j1ug(x)0,i1,2,,m.ii令 g(x)(g1(x),g2(x),u(u1,u2,,gm(x))T,h(x)(h1(x),h2(x),,vl)T，

,hl(x))T，

,um)T,v(v1,v2,称u与v为广义Lagrange乘子向量或K-T乘子向量．

f(x)g(x)Tuh(x)Tv0,T ug(x)0,u0.令L(x,u,v)f(x)uTg(x)vTh(x)为广义Lagrange函数．称L(x,u,v)为广

12 / 44

义Lagrange函数．那么K-T条件为

xL(x,u,v)0,T ug(x)0,u0.定理4 设在问题〔1〕中，f(x)和gi(x)(i1,2,hj(x)(j1,2,,m)是凸函数，

,l)是线性函数，并且f(x)和gi(x)(iI(x))在点x处x是可行点，

可微．假设x是问题〔1〕的K-T点，那么x是问题〔1〕的全局极小点．

minf(x)(x13)2(x21)2;tg(x)x12x20,例2 求解最优化问题s.. h(x)2x1x230.解 广义Lagrange函数为

L(x,u,v)f(x)ug(x)vh(x)(x13)2(x21)2u(x12x2)v(2x1x23)．

因为

L(x,u,v)L(x,u,v)2(x13)2ux12v，2(x21)uv．

x1x2所以K-T条件与约束条件为

2(x13)2ux12v0,2(x1)uv0,22u(x1x2)0, 2x1x20,2xx30,12u0.下面分两种情况讨论． （1） 设u0，那么有

2(x13)2v0,2(x21)v0, 2xx30.1271871由此可解得x1,x2,v，但x(,)T不是可行点，因而不是K-T点．

55555（2） 设u0，那么有

13 / 44

2(x13)2ux12v0,2(x1)uv0,2 2x1x20,2xx30.12由此可得x122x130，解得x11或x13。从而x21或x29．于是u1或u11〔这与u0矛盾〕．v1或v27．由此可知x(1,1)T是问题的K-T点，但x(3,9)T不是问题的K-T点．

易见，f(x)是R2上的凸函数，g(x)是R2上的凹函数，h(x)是线性函数，因此由定理4知，x(1,1)T是问题的全局最优解．

定理5 设x为问题〔1〕的可行点，f(x),gi(x)(iI(x))和hj(x)(j1,2,点x处具有二阶连续偏导数，并且存在乘子向量u(u1,u2,v(v1,v2,,vm)T0使K-T条件成立，即

,l)在

,um)T0和

xL(x,u,v)0, Tug(x)0.假设对于任何满足

zTgi(x)0,iI(x)且ui0,Tzgi(x)0,iI(x)且ui0, Tzhj(x)0,j1,2,,l的向量z0，都有zT2 xxL(x,u,v)z0，那么x是问题〔1〕的严格局部极小点．

nciminf(x);i1xitgi(x)xi0,i1,2,例3 求解最优化问题s..nh(x)aixib0,i1,n,

其中常数ai0,ci0,i1,2,,n;b0．

解 该问题的广义Lagrange函数为

nnciL(x,u,v)uixiv(aixib)．

i1xii1i1n14 / 44

因为

cL(x,u,v)i2uiaiv,i1,2,xixi,n．

所以问题的K-T条件与约束条件为

cix2uiaiv0,i1,2,iuixi0,i1,2,,n,xi0,i1,2,,n,naixib0,i1u0,i1,2,,n.i,n,

由第1式、第3式知xi0(i1,2,,n)，从而由第二式解得ui0,i1,2,,n，

,n．于

是再由第1式知v0，且aivxi2ci0,i1,2,ci即得xi,i1,2,aiv于是xi,n，从而aii1ncib0，解得vaiv(aici)2i1nb2，

bi1naicici,i1,2,ai,n．

所以x(x1,x2,,xn)T是问题的K-T点．

又由于L(x,u,v)在点(xT,uT,v)T处关于x的Hesse矩阵2xxL(x,u,v)是一个n阶对角矩阵，其对角线上第i个元素为

2ci0,i1,2,3xi,n，

因此2xxL(x,u,v)是正定矩阵．根据定理5，x为问题的严格局部极小点．

第三章 常用优化算法介绍

§3.1 一维搜索

给定xk,dkRn，令()f(xkdk),0．

15 / 44

定义 如果求得步长k，使得

f(xkkdk)minf(xkdk)或(k)min()

00那么称这样的一维搜索为最优一维搜索或准确一维搜索．k叫做最优步长．

minf(x);xk1是从xk出发沿方向dk作定理1 对于问题，设f:SR是可微函数，

txSs..T最优一维搜索得到的，那么有 f(xk1)dk0．

定义 如果选取k，使目标函数f沿方向dk取得适当的可承受的下降量，即使得下降量f(xk)f(xk1)0是我们可承受的，那么称这样的一维搜索为可承受一维搜索或非准确一维搜索．

定义 设:RR,[0,]，并且()min()．如果对于[a,b][0,]有

0[a,b]，那么称[a,b]是问题min()的搜索区间．

0定义 设:RR,[a,b]R，假设存在[a,b]，使得()在[a,]上严格单调减少，在[,b]上严格单调增加，那么称[a,b]是()的单谷区间，()是[a,b]上的单谷函数或单峰函数．

定理2 设:RR,[a,b]为()的单谷区间，1,2[a,b]，且12，那么 〔1〕假设(1)(2)，那么[a,2]是()的单谷区间； 〔2〕假设(1)(2)，那么[1,b]是()的单谷区间． 算法3-1〔进退法〕

Step1 选取初始数据。给定初始点0，初始步长h00，加倍系数1〔一般取2〕，计算0(0)，置k0．

Step2 试探．令k1khk，计算k1(k1)．

Step3 比拟目标函数值．假设k1k，转Step4，否那么，转Step5．

Step4 加步探索．令hk1hk,k,k:k1,k:k1,k:k1，转Step2．

16 / 44

Step5 反向搜索．假设k0，转换搜索方向，hk:hk,k1，转Step2；否那么，停止迭代．令 amin{,k1},bmax{,k1}．输出搜索区间[a,b]．

§3.2 0.618法与Fibonacci法

考虑min(t),tR．假定(t)的一个搜索区间[a1,b1]已确定，并设(t)在[a1,b1]上

为单谷函数．

算法3-2〔0.618法〕

Step1 选取初始数据．确定初始搜索区间[a1,b1]和允许误差0,0.618． Step2 计算最初两个试探点：1a1(1)(b1a1),1a1(b1a1)，求出

(1),(1)，并置k1．

Step3 检查

kk？是，停止计算，输出tkk2；否那么，转Step4．

Step4 比拟函数值．假设(k)(k)，转Step5；假设(k)(k)，转Step6． Step5 向左搜索．令ak1:ak,bk1k,k1k,(k1)(k)． 并计算k1ak1(1)(bk1ak1),(k1)，转Step7．

Step6 向右搜索．令ak1k,bk1:bk,k1k,(k1)(k)． 并计算k1ak1(bk1ak1),(k1)，转Step7．

Step7 置k:k1，转Step3．

定义 Fibonacci数是指满足下述条件的数列Fk：

F0F11,Fk1FkFk1,k1,2,.

用数学归纳法可以证明，Fibonacci数可由下式表示：

n1n111515,n0,1,2,Fn522． 〔3.2. 2〕

算法3-3〔Fibonacci法〕

Step1 选取初始数据．给定初始搜索区间[a1,b1]和允许误差0，区分系数0，

17 / 44

求搜索次数n，使

Fnb1a1．

Step2 计算最初两个试探点：1a1值(1)和(1)，并置k1．

Fn2F(b1a1),1a1n1(b1a1)，求函数FnFnStep3 检查(k)(k)？是，转Step4；否，转Step5．

Step4 向左搜索．令ak1:ak,bk1k,k1k,(k1)(k)． 并计算k1ak1Fnk2(bk1ak1)和(k1)，转Step6． FnkStep5 向右搜索．令ak1k,bk1:bk,k1k,(k1)(k)． 并计算k1ak1Fnk1(bk1ak1)和(k1)，转Step6． FnkStep6 置k:k1，假设kn1，转Step3；假设kn1，转Step7．

Step7 令nn1,nn1，计算(n)和(n)。假设(n)(n)，那么令

an:an1,bnn；否那么，令ann,bn:bn1，停止计算，极小点含于区间[an,bn]．

§3.3 Newton法

考虑min(t),tR．假定(t)具有三阶连续导数．

算法3-4〔Newton法〕

Step1 给定初始点t0，允许误差0，置k0．

Step2 检查(tk)？是，输出tk，停止计算；否，转Step3． Step3 计算点 tk1tk(tk)，置k:k1，转Step2． (tk)§3.4 最速下降法

考虑无约束最优化问题

18 / 44

minf(x)

其中f:RnR具有一阶连续偏导数．

算法3-5〔最速下降法〕

Step1 选取初始数据．选取初始点x0，给定允许误差0，令k0．

Step2 检查是否满足终止准那么．计算f(xk)，假设f(xk)，迭代终止，xk Step3 进展一维搜索．取dkf(xk)，求k和xk1，使得

f(xkkdk)minf(xkdk)，

0xk1xkkdk．

令k:k1，返回Step2．

特别地，考虑

minf(x)n1TxQxbTxc 2nn其中xR,QR为正定矩阵，bR,cR．

n设第k次迭代点为xk，从点xk出发沿f(xk)作一维搜索，得

xk1xkkf(xk)，

Tn其中kf(xk1)f(xk)0．而f(x)Qxb,xR，

T所以f(xk1)f(xk)kQf(xk)，从而(f(xk)kQf(xk))f(xk)0，而Q正T定，即f(xk)Qf(xk)0，故由上式解出

f(xk)Tf(xk) kf(xk)TQf(xk)于是

f(xk)Tf(xk)xk1xkf(xk)

f(xk)TQf(xk)

例1 用最速下降法求解问题

minf(x)4x12x22

19 / 44

其中x(x1,x2)．取初始点xT(0)(1,1)T，允许误差0.1．

f是正定二次函数，且

800Q,b,c0．

020f在点x(x1,x2)T处的梯度f(x)(8x1,2x2)T．

第一次迭代： 令搜索方向d(0)f(x(0))(8,2)T，

d(0)644217，

从点x(0)出发沿d(0)

(0)680.130769， 520x(1)(1,1)T0.130769(8,2)T(0.046152,0.738462)T．

第二次迭代： 令d(1)f(x(1))(0.369216,1.476924)T，

d(1)2.183051.522375，

从点x出发沿d(1)(1)

x(2)(0.101537,0.147682)T．

第三次迭代： 令d(2)f(x(2))(0.812296,0.295364)T，

d(2)0.7470560.864329，

x(3)(0.009747,0.107217)T．

第四次迭代： 令d(3)f(x(3))(0.077976,0.214434)T，

d(3)0.0520620.228171，

20 / 44

x(4)(0.019126,0.027816)T．

第五次迭代： 令d(4)f(x(4))(0.153008,0.055632)T，

d(4)0.0265060.162807，

x(5)(0.001835,0.020195)T．

此时，f(x(5))0.001847

x(5)(0.001835,0.020195)T．

x(0,0)T．

§3.5 Newton法

算法3-6〔Newton法〕

Step1 选取初始数据．选取初始点x0，给定允许误差0，令k0．

Step2 检查是否满足终止准那么．计算f(xk)，假设f(xk)，迭代终止，xk

2121Step3 构造Newton方向．计算[f(xk)]，取dk[f(xk)]f(xk)．

Step4 求下一个迭代点．令xk1xkdk，k:k1，返回Step2． 例2

x(0)(1,1)T，允许误差0.1．

(0)解 f(x80)(8,2)T，2f(x(0))，故

021/801(0)2(0)1(0)，d[f(x)]f(x)[2f(x(0))]1， 101/2x(1)x(0)d(0)(1,1)T(1,1)T(0,0)T．

由于 f(x)00.1，迭代完毕，得x

算法3-7〔阻尼Newton法〕

21 / 44

(1)(1)

Step1 选取初始数据．选取初始点x0，给定允许误差0，令k0．

Step2 检查是否满足终止准那么．计算f(xk)，假设f(xk)，迭代终止，xk

2121Step3 构造Newton方向．计算[f(xk)]，取dk[f(xk)]f(xk)．

Step4 进展一维搜索．求k和xk1，使得

f(xkkdk)minf(xkdk)，

0xk1xkkdk．

令k:k1，返回Step2．

例3 用阻尼Newton法求解下面问题：

minf(x)(1x1)22(x2x12)2

其中x(x1,x2)．取初始点x解 第一次迭代：

T(0)(0,0)T，允许误差0.1．

2(1x1)8(x2x12)x1f(x)， 24(x2x1)16x128(x2x12)28x1f(x)，

8x142故 f(x(0))(2,0)T,f(x(0))2，

2021/20(0)12f(x(0)),[f(x)]．

0401/4于是，Newton方向 d即求minf(x0(0)(0)(0)(0)[2f(x(0))]1f(x(0))(1,0)T，从x出发沿d作一维搜索，

d(0))min(1)224的最优解，得到(0)01．令 2x(1)x(0)(0)d(0)(1/2,0)T．

f(x(1))(0,1)T,f(x(1))1．

第二次迭代：

842111(1)12f(x(1)),[f(x)]，

4124822 / 44

d(1)[2f(x(1))]1f(x(1))(1/4,1/2)T．

从x出发沿d(1)(1)作一维搜索，即求

minf(x(1)d(1))min001[8(2)2(2)4] 128的最优解，得到(1)2．令

x(2)x(1)(1)d(1)(1,1)T．

f(x(1))(0,1)T,f(x(1))1．

此时，f(x(2))(0,0)T,f(x(2))0x

(2)(1,1)T，这是惟一的最优解．

§3.6 共轭梯度法

定义 设QRnn为正定矩阵．假设R中的向量组d0,d1,n,dm1满足

diTQdj0,i,j0,1,那么称d0,d1,,m1,ij，

,dm1是Q共轭的．

算法3-8〔共轭方向法〕 给定一个正定矩阵QRnn．

Step1 选取初始数据．选取初始点x0，给定允许误差0．

TStep2 选取初始搜索方向．计算f(x0)，求出d0，使f(x0)d00，令k0．

Step3 检查是否满足终止准那么．假设f(xk)，迭代终止；否那么，转Step4． Step4 进展一维搜索．求k和xk1，使得

f(xkkdk)minf(xkdk)，

0xk1xkkdk．

Tep5 选取搜索方向．求dk1使

dk1TQdj0,j0,1,令k:k1，返回Step3．

,k，

23 / 44

如果用共轭方向法求解正定二次函数的无约束最优化问题

minf(x)其中QRnn1TxQxbTxc 2n为正定矩阵，bR,cR〔此时算法中的正定矩阵应与二次函数的正定矩

阵一致〕，那么容易推出迭代公式为

f(xk)Tdkxk1xkdk TdkQdk

Fletcher-Reeves〔FR〕公式：kf(xk1)f(xk)22；

f(xk1)Tf(xk1)Dixon-Myers〔DM〕公式：k； Tdkf(xk)f(xk1)T[f(xk1)f(xk)]Polak-Ribiere-Polyak〔PRP〕公式：k．

f(xk)Tf(xk)算法3-9〔FR共轭梯度法〕

Step1 选取初始数据．选取初始点x0，给定允许误差0．

Step2 检查是否满足终止准那么．计算f(x0)，假设f(x0)，迭代终止，x0 Step3 构造初始搜索方向．计算d0f(x0),k0． Step4 进展一维搜索．求k和xk1，使得

f(xkkdk)minf(xkdk)，

0xk1xkkdk．

令k:k1，返回Step2．

Tep5 检查是否满足终止准那么．计算f(xk1)，假设f(xk1)，迭代终止，xk1 Step6 检查迭代次数．假设k1n，令x0:xn，返回Step3；否那么，转Step7． Step7 构造共轭方向．用FR公式取

dk1f(xk1)kdk，kf(xk1)f(xk)22，

24 / 44

令k:k1，返回Step4．

注意，如果算法3-9的Step7中k的形式改为DM公式或PRP公式，那么分别得到DM共轭梯度法和PRP共轭梯度法．

x(0)(0,0)T，允许误差0.1．

解 因为

2(1x1)8(x2x12)x1f(x)， 24(x2x1)所以

f(x(0))(2,0)T,f(x(0))2．

令d(0)f(x(0))(2,0)T，从x(0)出发，沿d(0)进展一维搜索，得

(0)1/4,x(1)x(0)(0)d(0)(1/2,0)T．

从而

f(x(1))(0,1)T,f(x(1))1．

由FR公式有

0f(x(1))f(x(0))221， 4因此，新的搜索方向为

d(1)f(x(1))0d(0)(1/2,1)T．

从x出发，沿d(1)(1)进展一维搜索，得

(1)1,x(2)x(1)(1)d(1)(1,1)T．

此时

f(x(2))(0,0)T,f(x(2))0．

x(2)(1,1)T．

§3.7 坐标轮换法

考虑无约束最优化问题

25 / 44

minf(x)

其中xRn,f:RnR．

算法3-10〔坐标轮换法〕

Step1 选取初始数据．选取初始点x0，给定允许误差0，令k0．

Step2 进展一维搜索．从xk1出发，沿坐标轴方向ek进展一维搜索，求k1和xk，使得

f(xk1k1ek)minf(xk1ek)，

xkxk1k1ek．

Step3 检查迭代次数．假设kn，转Step4；否那么，令k:k1，返回Step2． Step4 检查是否满足终止准那么．假设xnx0，迭代终止，得xnx0:xn,k:1，返回Step2．

例4 用坐标轮换法求解问题

minf(x)x12x223x1x1x2

其中x(x1,x2)．取初始点x解 从点x(0)T(0)(1,1)T，允许误差0.1．

出发沿e1进展一维搜索，易得

0,x(1)x(0)0e1(,0)T；

从点x出发沿e2进展一维搜索，得

(1)32321,x(2)x(1)1e2(,)T；

x(2)x(0)．

再从点x(2)343324出发沿e1进展一维搜索，得

2,x(3)x(2)2e1(从点x(3)38153T,)； 84出发沿e2进展一维搜索，得

3,x(4)x(3)3e2(341515T,)； 81626 / 44

x(4)x(2)．

再从点x(4)出发沿e1进展一维搜索，得

4从点x(5)3(5)6315,xx(4)4e1(,)T； 323216出发沿e2进展一维搜索，得

53(6)6363,xx(5)5e2(,)T； 643264x(6)x(4)．

再从点x(6)出发沿e1进展一维搜索，得

6从点x(7)3(7)25563T,xx(6)6e1(,)； 12812864出发沿e2进展一维搜索，得

73255255T,x(8)x(7)7e2(,)； 256128256x(8)x(6)．

x(8)((2,1)T．

255255T,)． 128256§3.8 Powell法

算法3-11〔Powell法〕

Step1 选取初始数据．选取初始点x0，n个线性无关的初始搜索方向d0,d1,给定允许误差0，令k0．

Step2 进展根本搜索．令y0xk，依次沿d0,d1,,dn1，

,dn1进展一维搜索．对一切

j1,2,,n，记

f(yj1j1dj1)minf(yj1dj1)，

yjyj1j1dj1．

27 / 44

Step3 检查是否满足终止准那么．取加速方向dnyny0，假设dn，迭代终止，得yn为问题的近似最优解；否那么，转Step4．

Step4 确定搜索方向．按

f(ym)f(ym1)max{f(yj)f(yj1)}

0jn1确定m，假设

f(y0)2f(yn)f(2yny0)2[f(ym)f(ym1)]

成立，转Step5；否那么，转Step6．

Step5 调整搜索方向．从点yn出发沿方向dn作一维搜索．求出n，使得

f(ynndn)minf(yndn)．

令xk1ynndn，再令dj:dj1,jm,m1,,n1，k:k1，返回Step2．

Step6 不调整搜索方向．令xk1yn，k:k1，返回Step2． 例5

x(0)(0,0)T，初始搜索方向组

d0(0,1)T,d1(1,0)T，

给定允许误差0.1． 解 第一次迭代： 同例1一样，得

3y(1)(0,0)T,y(2)(,0)T，

23d2y(2)y(0)(,0)T。

2因为d23/2，所以要确定调整方向．由于

9f(y(0))0,f(y(1))0,f(y(2))，

4

f(y(1))f(y(2))max{f(y(j))f(y(j1))|j0,1}，

因此m1，并且

f(y(m))f(y(m1))f(y(1))f(y(2))9． 428 / 44

又因f(2y(2)3y(0))0x(1)y(2)(,0)T．

2第二次迭代： 取y(0)3x(1)(,0)T，从点y(0)出发沿d0作一维搜索，得

23330,y(1)y(0)0d0(,)T．

424(1)接着从点y出发沿方向d1作一维搜索，得

1,y(2)y(1)1d1(由此有加速方向

38153T,)． 8433d2y(2)y(0)(,)T．

84因为d235/8，所以要确定调整方向．因

945189， f(y(0)),f(y(1)),f(y(2))41664m0，并且

f(y(m))f(y(m1))f(y(0))f(y(1))由于

9． 16f(2y(2)y(0))y(2)出发沿d2作一维搜索，得

45， 162,x(2)y(2)2d2(2,1)T。

同时，以d2替换d0，即下一次迭代的搜索方向组取为

1333d0(1,0)T,d1(,)T．

84第三次迭代： 取y(0)x(2)(2,1)T，类似地可求得

y(1)(2,1)T,y(2)(2,1)T，

d2y(2)y(0)(0,0)T．

因为 d20x(3)y(2)(2,1)T．

29 / 44

§3.9罚函数法 一、外法函数法

考虑约束非线性最优化问题

minf(x);tgi(x)0,i1,2,,m, s..hj(x)0,j1,2,,l,（i1,2,其中f(x),gi(x),m）和hj(x)（j1,2,,l）都是定义在RnS．

对于等式约束问题

minf(x);thj(x)0,j1,2,s..定义罚函数

,l,

F1(x,)f(x)hj2(x)，

j1l其中参数

minF1(x,) nxR对于不等式约束问题

minf(x);tgi(x)0,i1,2,s..定义罚函数

,m,

F2(x,)f(x)[max{0,gi(x)}]2，

i1m其中

minF2(x,) nxR

F(x,)f(x)P(x)，

其中是很大的正数，P(x)具有以下形式：

P(x)[gi(x)][hj(x)]．

i1j1ml30 / 44

和是满足以下条件的实值连续函数：

(y)0,当y0时， (y)0,当y0时,(y)0,当y0时， (y)0,当y0时.函数和的典型取法为

(y)[max{0,y}]， (y)|y|，

其中1和1是给定的常数，通常取作1或2．

minF(x,)f(x)P(x) nxR其中是很大的正数，P(x)是连续函数．

算法3-12〔外罚函数法〕

Step1 选取初始数据．给定初始点x0，初始罚因子10，放大系数1，允许误差0，令k1．

Step2 求解无约束问题．以xk1为初始点，求解无约束问题

minF(x,)f(x)P(x) nxR设其最优解为xk．

Step3 检查是否满足终止准那么．假设kP(xk)，那么迭代终止，

xkk1k,k:k1，返回Step2．

二、罚函数法

S的部

intS{x|xRn,gi(x)0,i1,2,,m}．

为了保持迭代点始终含于intS，我们引入另一种罚函数

G(x,r)f(x)rB(x)，

31 / 44

其中r是很小的正数，B(x)是intS上的非负实值连续函数，当点x趋向可行域S的边界时，B(x)．

显然，罚函数G(x,r)的作用是对企图脱离可行域的点给予惩罚，相当于在可行域的边界设置了障碍，不让迭代点穿越到可行域之外，因此也称为障碍函数．

G(x,r)的两种常用的形式为

G(x,r)f(x)ri1m1， gi(x)与

G(x,r)f(x)rlngi(x)

i1m分别称为倒数障碍函数和对数障碍函数．

算法3-13〔罚函数法或SUMT点法〕

Step1 选取初始数据．给定初始点x0intS，初始参数r10，缩小系数(0,1)，允许误差0，令k1．

Step2 求解无约束问题．以xk1为初始点，求解无约束问题

minG(x,rk)f(x)rkB(x); s..txintS,设其最优解为xk．

Step3 检查是否满足终止准那么．假设rkB(xk)，那么迭代终止，

xkrk1rk,k:k1，返回Step2．

附录5 《最优化方法》复习题

1、设ARnn是对称矩阵，bRn,cR，求f(x)的梯度和Hesse矩阵．

解 f(x)Axb,2f(x)A．

1TxAxbTxc在任意点x处232 / 44

2、设(t)f(xtd)，其中f:RnR二阶可导，xRn,dRn,tR，试求(t)． 解 (t)f(xtd)Td,(t)dT2f(xtd)d． 3、设方向dRn是函数f(x)在点x处的下降方向，令

ddTf(x)f(x)THIT，

df(x)f(x)Tf(x)其中I为单位矩阵，证明方向pHf(x)也是函数f(x)在点x处的下降方向． 证明 由于方向d是函数f(x)在点x处的下降方向，因此f(x)Td0，从而

f(x)Tpf(x)THf(x)

ddTf(x)f(x)Tf(x)(IT)f(x) Tdf(x)f(x)f(x)Tf(x)Tf(x)f(x)Td0，

所以，方向p是函数f(x)在点x处的下降方向． 4、SRn是凸集的充分必要条件是m2,x1,x2,,xmS,x1,x2,,xm的一切

凸组合都属于S．

证明 充分性显然．下证必要性．设S是凸集，对m用归纳法证明．当m2时，由凸集的定义知结论成立，下面考虑mk1时的情形．令xixi，

i1k1其中xiS,i0,i1,2,结论成立〕，记yk,k1，且i1．不妨设k11〔不然xxk1S，

i1k1ixi，有x(1k1)yk1xk1，

i11k1,k,i0,i1,2,又

1k1i1，

1i1k1k那么由归纳假设知，yS，而xk1S，且S是凸集，故xS．

5、设SRn为非空开凸集，f:SR在S上可微，证明：f为S上的凸函数的充要条件是f(x2)f(x1)f(x1)T(x2x1),x1,x2S．

33 / 44

证明 必要性．设f是S上的凸函数，那么x1,x2S与(0,1)，有

f(x2(1)x1)f(x2)(1)f(x1)，

于是

f(x1(x2x1))f(x1)f(x2)f(x1)，

因S为开集，f在S上可微，故令0，得

f(x1)T(x2x1)f(x2)f(x1)，即f(x2)f(x1)f(x1)T(x2x1),x1,x2S．

充分性．假设有f(x2)f(x1)f(x1)T(x2x1),x1,x2S， 那么[0,1]，取xx1(1)x2S，从而

f(x1)f(x)f(x)T(x1x)，f(x2)f(x)f(x)T(x2x)，

将上述两式分别乘以和1后，相加得

f(x1)(1)f(x2)f(x)f(x)T(x1(1)x2x)

f(x)f(x1(1)x2)，

所以f为凸函数．

6、证明：凸规划minf(x)的任意局部最优解必是全局最优解．

xS证明 用反证法．设xS为凸规划问题minf(x)的局部最优解，即存在x的某

xS个邻域N(x)，使f(x)f(x),xN(x)S．假设x不是全局最优解，那么存在xS，使f(x)f(x)．由于f(x)为S上的凸函数，因此

(0,1)，有

f(x(1)x)f(x)(1)f(x)f(x)．

当充分接近1时，可使x(1)xN(x)S，于是f(x)f(x(1)x)，矛盾．从而x是全局最优解．

7、设SRn为非空凸集，f:SR是具有一阶连续偏导数的凸函数，证明：x是问题minf(x)的最优解的充要条件是：f(x)T(xx)0,xS．

xS证明 必要性．假设x为问题minf(x)的最优解．反设存在xS，使得

xS34 / 44

f(x)T(xx)0，那么dxx是函数f(x)在点x处的下降方向，这与x为问

题minf(x)的最优解矛盾．故f(x)T(xx)0,xS．

xS充分性．假设f(x)T(xx)0,xS．反设存在xS，使得f(x)f(x)．

f(x(xx))f(x)f(x(1)x)f(x)

f(x)(1)f(x)f(x)f(x)f(x)0((0,1)，

因S为凸集，f在S上可微，故令0，得

f(x)T(xx)f(x)f(x)0，这与条件矛盾，故x是问题minf(x)的最优解．

xS8、设函数f(x)具有二阶连续偏导数，xk是f(x)的极小点的第k次近似，利用

f(x)在点xk处的二阶Taylor展开式推导Newton法的迭代公式为 xk1xk[2f(xk)]1f(xk)．

证明 由于f(x)具有二阶连续偏导数，故

1f(x)(x)f(xk)f(xk)T(xxk)(xxk)T2f(xk)(xxk)．

2且2f(xk)是对称矩阵，因此(x)是二次函数．为求(x)的极小点，可令

(x)0，即f(xk)2f(xk)(xxk)0，假设2f(xk)正定，那么上式解出的

(x)的平稳点就是(x)的极小点，以它作为f(x)的极小点的第k1次近似，记为xk1，即xk1xk[2f(xk)]1f(xk)，这就得到了Newton法的迭代公式. 9、表达常用优化算法的迭代公式．

kak(1)(bkak),〔1〕0.618法的迭代公式：

kak(bkak).Fnk1a(bkak),kkFnk1(k1,2,〔2〕Fibonacci法的迭代公式：Fank(ba)kkkkFnk1,n1)．

〔3〕Newton一维搜索法的迭代公式： tk1tk(tk)． (tk)35 / 44

〔4〕最速下降法用于问题minf(x)1TxQxbTxc的迭代公式： 2f(xk)Tf(xk)xk1xkf(xk) Tf(xk)Qf(xk)〔5〕Newton法的迭代公式：xk1xk[2f(xk)]1f(xk)． 〔6〕共轭方向法用于问题minf(x)1TxQxbTxc的迭代公式： 2f(xk)Tdkxk1xkdk． TdkQdk10、线性规划：

minf(x)2x1x2x3;s..t3x1x2x360,x12x22x310, x1x2x320,x1,x2,x30.〔1〕用单纯形法求解该线性规划问题的最优解和最优值； 〔2〕写出线性规划的对偶问题； 〔3〕求解对偶问题的最优解和最优值．

解 〔1〕引进变量x4,x5,x6，将给定的线性规划问题化为标准形式：

minf(x)2x1x2x3;s..t3x1x2x3x460,x12x22x3x510, x1x2x3x620,x1,x2,,x60.

x4 x5 x6 x1 x2 x3 x4 x5 x6 3 1 1 -2 1 -2 1* 1 1 2 -1 -1 1 0 0 0 0 1 0 0 0 0 1 0 60 10 20 0 f 36 / 44

x4 2 0 2 1 0 -1 40 x5 3 0 0 0 1 2 50 x2 1 1 -1 0 0 1 20 f -3 0 0 0 0 -1 -20 所给问题的最优解为x(0,20,0)T，最优值为f20． 〔2〕所给问题的对偶问题为：

maxg(y)60y110y220y3;s..t3y1y2y32,y12y2y31, y12y2y31,y1,y2,y30.〔3〕将上述问题化成如下等价问题：

minh(y)60y110y220y3;s..t3y1y2y32,y12y2y31, y12y2y31,y1,y2,y30.引进变量y4,y5,y6，将上述问题化为标准形式：

minh(y)60y110y220y3;s..t3y1y2y3y42,y12y2y3y51,〔2〕 y12y2y3y61,y1,y2,,y60. y1 y2 y3 y4 y5 y6 y4 -3 -1 -1 1 0 0 2 y5 -1 2 -1* 0 1 0 -1 37 / 44

1〕 〔

y6 -1 -2 1 0 0 0 -1 1 1 1 0 0 0 1 1 0 3 1 0 20 h y4 y3 y6 -60 -10 -20 0 -2 1 -2 -3 -2 0 0 1 0 1 0 0 0 h -40 -50 0 -20 0 问题〔2〕的最优解为y(0,0,1)T，最优值为h20〔最小值〕． 问题〔1〕的最优解为y(0,0,1)T，最优值为g20〔最大值〕．

11、用0.618法求解 min(t)(t3)2，要求缩短后的区间长度不超过0.2，初始区间取[0,10]． 解 第一次迭代： 取[a1,b1][0,10],0.2． 确定最初试探点1,1分别为

1a10.382(b1a1)3.82，1a10.618(b1a1)6.18．

求目标函数值：(1)(3.823)20.67，(1)(6.183)210.11． 比拟目标函数值：(1)(1)． 比拟1a16.1800.2． 第二次迭代：

a2a10,b216.18,213.82,(2)(1)0.67．

2a20.382(b2a2)0.382(6.180)2.36,(2)(2.363)20.4．

(2)(2),2a23.82． 第三次迭代：

a3a20,b323.82,322.36,(3)(2)0.4．

38 / 44

3a30.382(b3a3)0.382(3.820)1.46,(3)(1.463)22.37．

(3)(3),b333.821.46． 第四次迭代：

a431.46,b4b33.82,432.36,(4)(3)0.4．

4a40.618(b4a4)1.460.0.618(3.821.46)2.918,(4)0.0067． (4)(4),b443.822.36． 第五次迭代：

a542.36,b5b43.82,542.918,(5)(4)0.0067．

5a50.618(b5a5)3.262,(5)0.0686． (5)(5),5a53.2622.36． 第六次迭代：

a6a52.36,b653.262,652.918,(6)(5)0.0067．

6a60.382(b6a6)2.7045,(6)0.087．

(6)(6),b663.2622.7045． 第七次迭代：

a762.7045,b7b63.262,762.918,(7)(6)0.0067．

7a70.618(b7a7)3.049,(7)0.002． (7)(7),b77． 第八次迭代：

a872.918,b8b73.262,873.049,(8)(7)0.002．

8a80.618(b8a8)3.131,(8)0.017．

(8)(8),8a8． 第九次迭代：

a9a82.918,b983.131,993.049,(9)(8)0.002．

39 / 44

9a90.382(b9a9)2.999,(9)0.000001． (9)(9),9a93.0492.918． 故x9923.024．

24x13x2，取x(0)(1,1)T，迭12、用最速下降法求解 minf(x)x122x1x22x2代两次．

解 f(x)(2x12x24,2x14x23)T，

2241TT将f(x)写成f(x)xQxbx的形式，那么Q,b．

2243第一次迭代：

x(1)x(0)f(x(0))Tf(x(0))(0)f(x) (0)T(0)f(x)Qf(x)0(0,3)1013． 1(0,3)22031/4243第二次迭代：

x(2)f(x(1))Tf(x(1))xf(x(1)) (1)T(1)f(x)Qf(x)(1)3/2(3/2,0)013/27/4． 223/21/401/4(3/2,0)24013、用FR共轭梯度法求解

11minf(x)(x1x2x3)2(x1x2x3)2(x1x2x3)2，取x(0)(,1,)T，迭代

22两次．假设给定0.01,判定是否还需进展迭代计算． 解 f(x)3(x12x22x32)2(x1x2x1x3x2x3)，

40 / 44

6221再写成f(x)xTGx，G262，f(x)Gx．

2226第一次迭代：

f(x(0))(0,4,0)T，令d0f(x(0))(0,4,0)T，

从x(0)出发，沿d0进展一维搜索，即求minf(x(0)d0)216482的最优解，

0得

01/6,x(1)x(0)0d0(1/2,1/3,1/2)T．

第一次迭代：

f(x(1))(4/3,0,4/3)T．0f(x(1))f(x(0))222， 9d1f(x(1))0d0(4/3,8/9,4/3)T．

从x(1)出发，沿d1进展一维搜索，即求

142362214181418minf(x(1)d1)(,,)262

3902339232261423的最优解，得

1,x(2)此时

381/24/33x(1)1d11/38/9(0,0,0)T．

1/284/3f(x(2))(0,0,0)T,f(x(2))00.01．

得问题的最优解为x(0,0,0)T，无需再进展迭代计算．

24x12x1x2，取x(0)(1,1)T，迭代一14、用坐标轮换法求解 minf(x)x122x2步．

41 / 44

解 从点x(0)(1,1)T出发，沿e1(1,0)T进展一维搜索， 即求minf(x(0)e1)243的最优解，得

002,x(1)x(0)0e1(3,1)T．

再从点x(1)出发，沿e2(0,1)T进展一维搜索， 即求minf(x(1)e2)2227的最优解，得

011/2,x(2)x(1)1e2(3,3/2)T．

23x1x1x2，取x(0)(0,0)T，初始搜索方15、用Powell法求解minf(x)x12x2向组d0(0,1)T,d1(1,0)T，给定允许误差0.1〔迭代两次〕． 解 第一次迭代：

令y(0)x(0)(0,0)T，从点y(0)出发沿d0进展一维搜索，易得

00,y(1)y(0)0d0(0,0)T；

接着从点y(1)出发沿d1进展一维搜索，得

1,y(2)y(1)1d1(,0)T

3由此有加速方向 d2y(2)y(0)(,0)T．

2因为d23/2，所以要确定调整方向．

32329由于 f(y(0))0,f(y(1))0,f(y(2))

4f(y(1))f(y(2))max{f(y(j))f(y(j1))|j0,1}，

因此m1，并且

f(y(m))f(y(m1))f(y(1))f(y(2))3又因f(2y(2)y(0))0x(1)y(2)(,0)T．

2第二次迭代：

9． 43取y(0)x(1)(,0)T，从点y(0)出发沿d0作一维搜索，得

23330,y(1)y(0)0d0(,)T．

42442 / 44

接着从点y(1)出发沿方向d1作一维搜索，得

1,y(2)y(1)1d1(由此有加速方向

38153T,)． 8433d2y(2)y(0)(,)T．

84因为d235/8，所以要确定调整方向．因

945189， f(y(0)),f(y(1)),f(y(2))41664m0，并且

f(y(m))f(y(m1))f(y(0))f(y(1))由于

f(2y(2)y(0))y(2)出发沿d2作一维搜索，得

9． 1645， 162,x(2)y(2)2d2(2,1)T。

同时，以d2替换d0，即下一次迭代的搜索方向组取为

1333d0(1,0)T,d1(,)T．

84minf(x)(x1)2;16、用外罚函数法求解 

tx20.s..取10.5,2,104． 解 引入罚函数

F(x,k)(x1)2k(max{0,(x2)})2(x1)2k2[(x2)2(2x)|2x|]

那么原约束最优化问题相应的一系列无约束最优化问题为：minF(x,k)， 其中10.5,k12k,k1,2,解上述无约束问题，得xk依次对k1,2,．

12kk，同时kP(xk)． 21k(1k)用上述公式计算xk和kP(xk)，结果如下表所示．

43 / 44

k 1 2 3 4 5 6 7 8 xk kP(xk) k xk kP(xk) 7.692103 3.876103 1.946103 9.747104 4.878104 2.440104 1.220104 6.103105 1.3333 1.5 1.6667 1.8 1.8889 1.9412 1.9697 1.9846 2.222101 9 2.5101 1.9922 10 1.9961 2.222101 11 1.9981 1.6101 12 1.9990 9.877102 13 1.9995 5.536102 14 1.9998 2.938102 15 1.9999 1.515102 16 1.9999 由迭代终止条件kP(xk)k410可得原约束问题的近似最优解〔保存42(1k)位有效数字〕x161.9999．

44 / 44