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

《《最优化方法》课程复习考试.doc.pdf》由会员分享，可在线阅读，更多相关《《最优化方法》课程复习考试.doc.pdf（54页珍藏版）》请在三一文库上搜索。

1、最优化方法复习提要 第一章最优化问题与数学预备知识 1.1模型 无约束最优化问题min /（x）, x =（旺, 兀2,心）w R“? A 约束最优化问题疋简（兀）0,心1,2,?, 加也（兀） =0,丿=1,2,?,“ ）min /（x）; s.t. gQ）nO,i = l,2,，加， hj （x） = 0,j = ,2,?,l ? 其中.f（X）称为目标函数， 西, 兀2, ，暫称为 决策变量，S称为可行域， gQ） no（心1,2, ,加）, 勺（兀） = 0。= 1,2,丿）称为约束条件. 1. 2多元函数的梯度、Hesse矩阵及Tayloi?公式 定义设f:R “TR,JR“?如果维

2、向量，VAre R n, 有 + Ax) -f(x) = p T x + 0(|Ax|)? 则称/（x）在点元处町微，并称df（x） = p Tx 为/（x）在点元处的微分 . 如果/（X）在点元处对丁 =（兀“2，?,）丁的各分量的偏导数 。/( 元) d x i 都存在，则称 / （兀）在点元处一阶可导，并称向量 为/ （兀）在点元处一阶导数或梯度. 定理1设f :R nR,xeRn?如果 / （兀）在点元处可微 , 则/ （兀）在点元处梯度 V/(x)存在，并且有#(x) = W) 7Ar . 定义 设f:R“TR,JR “?d是给定的n维非零向量，e = 2 ?如杲d min /( 兀

3、) ；即 v S.t. XG S. V/(x)=( df(x) T 。/（可。/（元） Um/a + 2e）-V（x） 久 TO 2 存在，则称此极限为/（x）在点元沿方向d的方向导数，记作冬学. da 定理2设f :R nR,xeRn. 如果/ （兀）在点元处可微 , 则/ （兀）在点元处沿任何 非零方向d的方向导数存在，且= VA元）。 , 其中丘 =厶? da a 定义 设/ （兀）是 /?“ 上的连续函数，xeR n. d是维非零向量 . 如果30, 使得V2w（O0）,有/（x + 2J）（）/（x）.则称d为f（兀）在点元处的下降 （上 升） 方向. 定理3设f:R nR.xeRn

4、 ,且/（兀）在点元处可微 , 如果日非零向量de R n 9 使得Vf（x） T d（） 0,则d是/ （兀）在点元处的下降（上升）方向. 定义 设f:R ”TR,HeR ”?如果/ （兀）在点元处对丁自变量x = （xpx2,-,x/J） 7的 各分量的二阶偏导数単匕丿?=1,2, , ）都存在，则称函数 / （兀）在点元处二阶U Xj 可导，并称矩阵 为/（x）在点元处的二阶导数矩阵或Hesse矩阵. 定义 设h:R“记/1（兀）=（肉（兀） , 爲（兀） , ?, 饥（兀） 7, 如果 勺? （x） （i = 1,2, ，加）在点元处对于自变量x =（兀 , 吃, ）丁的各分量的偏导

5、数 d 2x 扌/ （元） dxdx2 巧 ( 元) d 2f(x) 3 x2d ? d 2x 2 ? d xd x n L n ? ? d 2f(x) 97() ? ? d 2f(x) d x nd X d x nd x2 d 2f(x) V 2/(x) 丿 号(i = 1,2, ，加;J = 1,2,加dxf 都存在，则称向量函数加对在点元处是一阶可导的，并且称矩阵 为/?（%）在点x处的一阶导数矩阵或Jacobi矩阵, 例2 设aw R“,xw R“,bw R ,求f （x） = a Tx-h 在任意点兀处的梯度和Hesse 矩阵. 解 设 0 =（绚卫2，?, ）/, 兀=（旺, 兀2

6、，?,），则/ （兀） =工绞母+b , k= 因。 =畋伙=1,2,? ，川），故得V/（x）二a? 无 乂因理半=0（门=1,2,加，则V 2/W = 0? d xfl x j 例3 设Qe R ,xt, 是对称矩阵，heRceR,称fM = x TQxhT x-c为二 次函数，求 / （劝在 任意点兀处的梯度和Hesse矩阵. 解 设Q = （qJwX =（呂,兀2, ，xjT,b = （b,b2, ，b$ ,贝lj 、J、J、 / （西, 尢 2，?,）二牙工工如巧+工仪母 +0, 匕 /=1 ;=1 *=1 再对￥(兀 )x +q (/= 1,2,?,?)求偏导得到?弓 X)=q(i

7、,j = ,2,加, 于 dxt肯dX/dXj d h (x) a h(元) 曲（元） dXdx2 dX n d人(x)独（元）沁（元） dx 乙 ? ? ? ? 巩（元） dhm(x) ? ? dh m(x) 9% dx2 dX n ) % 肿（元） = 简记为V/7（X）. 从而V/*(x)= /(x) 工 qZj WjXj ;=1 =Qx + b ? 是 q 、 务 v7(x)= % 】 %2 Qin ? ? ? =Q 41 绻 2 Clnn ) 例4 设 （/ ）= /（兀 + 力），其屮/:/? t/? 二阶可导，xwR“,dwR “，TwR, 试求0（/）, （pt ）? 解 由多

8、元复合函数微分法知（pt ） = V/（+d,（pt ） = d T2fx + td ）d?定理4 设f:RJR, XG R n, 且/（x）在点x的某邻域内具有二阶连续偏导数，则/（%）在点元处冇 Taylor展式 fix + Ar） = /（%） + V/（x/Ar + - Ax TV2f （x + 如）心 ，（0 v s,t. h.(x) = 0, / = 1,2,，/ 解Lagrange 函数为L(x, v) = 4- x； - v(x lx2 - 8),则VLx, v) = 2x2 - vx, 一( 西兀2 一 ?丿 从而得厶 ( 兀,v)的| 人稳点(V8,A/8,2)7和(- 旋

9、2) ,对应有 x = (V8,V8) r,v = 2 和元=(-V8,-V8) r, v = 2 . 因此 M(X) = (Z1,Z2) / |(Z1,Z2)V/?(X) = 0 = (zI,z2)rz x2 + z2xl =0 = (z1,z2)r|z1=-z2. 并且fze M(元),zH0,有zrV(元,V)z = 2z； 4z】z? + 2z； = 8zj 0 . 利用定理2,所得的两个可行点X = (V8,A/8/和“(- 忌，- 旋r都是问题的严格局部极小点 . 2.3不等式约束最优化问题的最优性条件 定义SRxeclS,de RdQ,若曰力 0,使得，元 + S,X/Qw (0

10、,5), 则称为集合S在点元处的可行方向?这里c/5 = x|xe /?“,SnNd(QH0,/O? 令 “ |“0,财0,使 + 庇S,VAG(0,), 的严格局部极小点 . 例1试用最优性条件求解 min /(x)=彳 + 兀； s.t. /?(x) = x yx2 - 8 = 0. 由于V;X(x,v)= _ 一2 2 丿1-2 2 2 ,V/i(x) = (-1、ux 了 0、 11 了 0、 厂 0、 、。, 一 1 0, ie / （% ） ? 眾理3设元是问题（1）的可行点， / （劝和gQ）（iw/（元）在点元处可微， g心）（询 / （功在点元处连续，若元是问题（1）的局部极

11、小点，则存在不全为0 的非负数如 “?（沱/ （元），使 u（yf（x）- 为M/Vg,（元） =0 ?（元称为Fritz John 点） fe/ （T） 如果g/（Q（注/ （无）在点元处也可微，则存在不全为0的非负数如，岡，心，使 0. /A （ Q、（0、 解 因为W）= n ,Vg,（x）= ,v2（x）=, 且/（元）= 1,2, 、。丿 丿 (1) 成立，只有如=0才行. 取 uQ=O,ui=u 2=a 0 即可，因此无是 Fritz John 点. 定理4设元是问题（1）的可行点， / 和g,.（x）（ZG /（%）在点元处可微， g? ）（注/（元）在点元处连续，并且Vgz.（

12、x） （zeZ（J）线性无关 . 若元是问题 （1） 的局部极小点，则存在WZ0（ZG/（X）,使得 V/(x)-工乞Vg,( 元)=0 ? feZ(x) m Yf （元） -工均（元） = 0, /=! 色g（元） =，= 1，2,?，加. min /(x) = (x, 一I) 2 + x2; 例2 求最优化问题s.t. g1(x) = -xI-x2+20,的K?T点. g2(x) = x 20 2(x - in ( 解 因为V/(x)= 1 ,Vg(x)= , Vg9(x)= , 所以K?T条件为 I1丿1一1丿“U丿 2(X| -1) + W = 0, 1 + Wj _ “2 = 0，

13、v 比(X 兀？ + 2) = 0, u2x2 = 0, u 0, u2 0. 则=-1 ,这与U 矛盾?故弘2 0，从而兀2 = ； 若-%, +2 = 0,贝ij 比=-2 ,这与Wj 0 矛盾 . ?故u = 0 ,从而w2 = 1, Xj = 1 ； 由于玛 no,血no,且元=（1,0）丁为问题的可行点 , 因此元是K?T点. 定理5设在问题（1）中，/（兀）和 -g,（兀）（心1,2,?, 加）是凸函数，元是可行点, 并且/和 0,ZG I(X), Wo = rf|V/?7(x) TJ = O,j = l,2,.,Z ? 定理2设元为问题(1)的可行点，/( 劝和g,.(%) (Z

14、GZ(X)在点无处可微， 包(兀)(./? = 1,2, 在点元处具有一阶连续偏导数，g?)(注/( 元) 在点元处连 续. 若元为问题(1)的局部极小点， 则存在不全为0的数如“ (沱/( 元) 和 vy(j = l,2,.,/),且Wo,W/O(ze/(x),使 w0V/(x) - 工色 ?( )- 工v7V/?.(x) = 0 ? /e/(T) ；=1 Vj (j = 1,2,?,/) ,?, 使 / “oVA 元)- X 坷Vgj (元)-X YjPhj ( 元)=0, /=1 j=l uigi(x) = 0,i = l,2, ，九 ( 元称为Fritz John点) 若gf(x) (

15、zV /(元) 在点x处也可微 , 则存在不全为0的数如必Q = 1,2, ,加) 和 ( 元称为Fritz John点) min f(x) = %,2 +x；; 例1 设M 51(%)= X,3 “ X2 “ 0, 试判断x = (l,O) r 是否为Fritz John . g2(x) = x2 0, h(x) = -(x, -1) 2 + x2 = 0. 取w0 =0,?2 =1, v = -l,即知元是Fritz John 点. 定理3设元为问题(1)的可行点， /( 劝和gz.(%) (ZGZ(X)在点无处可微，hj(Q (./ = 1,2,?,/) 在点x处具有一阶连续偏导数，g,

16、(x)( 氓/( 元) 在点% 处连续 , 且向量组Vgz(x) (/G Z(x), V/7.(x) (j = 1,2, ? ? ? ,/)线性无关 . 若元是问题(1)的局 部极小点，贝I存在数W/ 0(/?/(%) 和? (.) = 1,2, J),使 Y/(元) 一工ug( 元)一2 吓叫(x) = 0. ( 元称为K?T点) iel(x)y=l 如果g,( 兀)( 渥/( 元) 在点元处也可微，则存在数u. no(j = i,2, ，加) 和 vy. (； = 1,2,.,/),使 “ JI I V/X) - 工乞 ( 元)- 工v$hj (x) = 0, S /=! ；=1 乞 例2

17、 求解最优化问题0, /?(%) = 2x( 4- x2 - 3 0. 解 广义Lagrange函数为 r co L(x.u.v) = f(x)-ug(x) - vhx) = (x, -3)“ +(x2 -1) -u(-x +x2)-1(2 + x2 - 3). MyldL(x,u.v)_ dL(x,u,v)_ 内为 - =2(%| 3) + 2uX 2v , - = 2(X9 U V . 3x, dx2 所以K?T条件及约束条件为 2(兀 一3) + 2ux - 2v = 0, 2(兀2 1)比一u = 0, w(-% 2 + x 2) = 0, V + 卷0? 2壬 + 工2 - 3 二0

18、, w 0. 下而分两种情况讨论. (1)设弘=0,则有 2(壬3) 2v 0, 0,则有 2(兀一3) + 2ux - 2v = 0, 2( x2 1) 一况一u = 0, 一石+花=0， 2xj + 兀2 - 3 = 0? 由止匕可得一兀；一2兀+3 = 0 ,需军得兀 | = 1或兀| = 3。从血兀2=1或兀2=9?1? 是= 1 或u = -ll ( 这与” 0矛盾 ).v = -l或v = 27?由此可知元 = (1,1)丁是问题的K? T 点，但元 =(-3,9卩不是问题的K?T点. 易见，畑是F上的凸函数，g(兀) 是F上的凹函数，力 ( 兀) 是线性函数，因此由定理 4知，x

19、 = (l,l) r 是问题的全局最优解. 従理5设元为问题(1)的可行点，/G),gO)(iw/() 和勺(x)(J = l,2,?,/) 在 点元处具有 二阶连续偏导数，并且存在乘子向量历=(可, 历2, ,瓦y?0和 =(耳, ，,n 0使K?T 条件成立 , 即 fVxL(x,w,v) = 0, u Tg(x) = 0. 若对于任何满足 z T V gi.(x)0jG /(X)且瓦=0, 0, zW勺(元) = 0, ) = 1,2,?J 的向量ZH0,都有z TVl，L(x 9u,v)z09贝吹是问题 (1)的严格局部极小点 . ?c min/(x) =工丄； Z=1 xi 例3 求

20、解最优化问题 0, z = 1,2,?,/?, hx)=工axt _ b = 0, z=i 其中常数坷0,q 0,i = 1,2,?，；b 0. 解 该问题的广义Lagrange函数为 Lg w,v)=y- L-y -v (y一方). /=! 兀 /=1 Z=1 所以问题的K-T条件及约束条件为 -av = O, i = 1,2，?，仏兀. uixi = 0 J = 1，2, 0J = 12，仏 n 工比_b = 0, i=l ut 0, z = 1,2,?,“. 由第1式、第3式知兀? 0(i = 1,2, ,M), 从而由第二式解得爲=0, z = 1,2,?,/?.于 是再曲第1式知*

21、v0 , Ji+ c. =0,心1,2, , n , 所以元 =(石，禺，,KJ?是问题的K?T点. 又由丁L(x,n, v)在点(x T,uT,V)T 处关于x的Hesse矩阵 (元，历，可是一个阶对角 矩阵，其对角线上第，个元素为 0,/ = 1,2,?,/!, 因此V：厶 (元, 兀可是止定矩阵 . 根据定理5,元为问题的严格局部极小点. 第三章常用优化算法介绍 3.1 一维搜索 给定xk.d kG R n, 令 0(2) = /( 丑+碣),2?0? 因为 解得V = 1=1 h 2 dxf ? ? ?, n ? ,i = ，从而X /=1 即得兀 = 定义如果求得步长心，使得 f （

22、xk +AA） = rnm f （xk + Ad k）或 0（ （2）若俠人沧久入），则 入上 是卩仇）的单谷区间. 算法3-1 （进退法） Stepl选取初始数据。给定初始点入，初始步长/? 0 0 ,加倍系数 a 1 （一般取0 = 2）, 计 算0（）=0（人），置比 =0? Step2 试探. 令- + h k，计算探 +=0（ 兀一兀 再从点兀出发沿弓进行一维搜索，得 恥討 +如辱討 从点兀出发沿匕进行一维搜索，得 入=丄, 严=尢+“=（竺邑八 64 于 2 32 64 再从点兀出发沿弓进行一维搜索，得 03 （7）（6）0,255 63 r 入= ， = X + 入q =（ ,）

23、 6 128 6 1 128 64 从点兀出发沿匕进行一维搜索，得 . 3 （7）. 启 55 255 r 256 “ 128 256 严）一兀 迭代终止，得问题（3.7.2）的近似最优解为 其实问题（3.7.2）的最优解为（2） ? 3.8 Powell 法 算法3?11 （Powell法） Stepl选取初始数据?选取初始点x（）, AT个线性无关的初始搜索方向（）, , ? ?, 盗_, 宀兀 . 0,令 =0? Step2进行基本搜索 . 令儿=忑，依次沿进行一维搜索. 对一切 丿=12宀记 /（yz-i + “d-J = min / （y + 加, yJ = y J_l+j.ldJ_

24、l ? Step3检查是否满足终止准则. 取加速方向dn = y n-yQt若阀|vw, 迭代终止，得儿为问题 的近似最优解；否则，转Step4. Step4确定搜索方向 . 按 / （儿） -/ （九+J =max/（yp - / （） . ） （3.8.1） 确定加 , 若 / （儿） -2/（几）+ /（2 儿- 几）2/（儿）-/ （; ”+） （3.8.2） 成立，转Step5；否则，转Step6. Step5调整搜索方向 . 从点儿出发沿方向盗作一维搜索. 求出人，使得 /（儿+人4）=映/ （儿+处）? 令兀R+严几+ “ sj. g(x)no,i = l,2,? ?,“ /z7

25、(x) = 0, j = 1,2,?,/, (3.9.1) 其屮/(x),g?)( 心1,2,?, 加) 和hj(x)(j = ,2,?,D都是定义在川上的实值连续 函数?记问题(3.9.1)的可行域为S. 对于等式约朿问题 min /(%)； s.t. hj(x) = 0,j = 1,2,?,/, (3.9.2) 定义罚函数 耳(x,cr) = /(兀)+ er工h； (x), J=I 其中参数7是很大的正常数 . 这样，可将问题(3.9.2)转化为无约束问题 min FAx.(7) ? xeR n 对于不等式约束问题 (3.9.3) 定义罚函数 min /(%)； s.t. g：( 兀)n

26、O,Z = l,2,? ?,/n, (3.9.4) 传( 兀 Q) = /(x) + b工max 0, ( 兀) 2 , /=1 其中7是很大的正数 . 这样，可将问题(3.9.4)传化为无约束问题 min R (x, 0,当，v0时， j0(y) = O,当y = OB 寸， 0(y)o,当歹工0时. 函数0和0的典型取法为 0(刃= max0,- y “, 0(y)卅卩， 其中) = /(x) + r k 5.r. xe int S, 设其最优解为无? Step3检查是否满足终止准则. 若贝U迭代终止，嫌为约束问题(3.9.4) 的近似最优解；否则，令g=%k ；=k + ,返回Step2

27、. （3.9.8） 附录5最优化方法复习题 1、设AG R nxn 是对称矩阵 ,bwRJcwR,求f(x) = -x r Axb T x-c在任意点兀处 2 的梯度和Hesse矩阵. 解V/*(x) = Ax + b, 2f(x) = A ? 2、设0(/) = /(x + /d)，其中/:/?” t /? 二阶可导，xeRdeRteR9试求? 解0(/) = 丫/( 兀+ / ) T d, 0= cTV f(X+tel) cl ? 3、设方向de R n 是函数 /( 兀) 在点兀处的下降方向, 令 H = / del 1 V/EYfW 其屮/ 为单位矩阵，证明方向p = -Hf(x)也是

28、函数 /( 兀) 在点兀处的下降方向. 证明 由于方向d是函数 /( 兀)在点无处的下降方向，因此Vf(x) Td2, G S的一切 凸组合都属于S? 证明 充分性显然 . 下证必要性 . 设S是凸集，对加用归纳法证明. 当m = 2吋， ?+1 由凸集的定义知结论成立，下面考虑时的情形 . 令“工心， Z = 1 k+ 其中兀w S, 4 no, i = l, 2,?，R + 1,且工 （2）写出线性规划的对偶问题; （3）求解对偶问题的最优解和最优值. 解（1）引进变量x4,x5,x6,将给定的线性规划问题化为标准形式: min /(x) = 2x -x 2 +x3; s.t. 3兀+ 吃

29、 + 兀3 + 兀4 = 60, X 2兀 + 2 兀3 + 忑=1， x, + x2 - x3 + x6 = 20, X X2 兀 4兀5 兀6 兀 4 31110060 1-2201010 兀 6 11*-100120 f -21-10000 X 4 20210-140 X 530001250 x211-100120 f-30000-1-20 所给问题的最优解为X = (0,20,0)7 ,最优值为7 = -20. (2)所给问题的对偶问题为： max g(y) = -60 j,-10% - 20儿； s? t ?一3y -y 2-y30. (3)将上述问题化成如下等价问题： min h(

30、y) = 60 +10% +20%；s? t ?一3y -y 2-y30. 引进变量， % ，% ，将上述问题化为标准形式： min h(y) = 60 y, +10y2 + 20%; s? t?一3” _ % _% + 4 = 2, “ _ 必+2旳一儿 +必=T，_牙_2旳+儿+几=1， (1) 儿 y5% -3-1-11002 % -12T*010-1 %-1-210011 h-60-10-20 0000 4-2-301-103 1-210101 %-2000110 h-40-5000-20020 问题(2)的最优解为y = (0,0,1/,最优值为万=20 ( 最小值 ). 问题(1)

31、的最优解为7 = (0,0,1/,最优值为 = -20 ( 最大值 ). 11用0. 618法求解min 0(0 = (/-3)2,要求缩短后的区间长度不超过0.2,初 始区间取0,10. 解第一次迭代： 取q,bJ = 0,10, = 0.2 ? 确定最初试探点人，“分别为 人=坷 + 0.382(勺一q) = 3.82 , “ = q + 0.61_q) = 6.18 . 求目标函数值 :0(入)=(3.82-3)2=0.67, ?(“J = (6.18-3)2=10.11. 比较目标函数值：0(人)V(“|)? 比较 / a】=6.18 0 0.2 ? 第二次迭代 : 入=色 + 0?3

32、822 _ a? ） = 0.382（6.18-0） = 2.36, 0（石）=（2.36 一3） 2 = 0.4. 0（入）v 仅“?），“2 一色=3.82 ? 第三次迭代： a3=a 2= 0, h3 = 角=3.82, “3 = 易=2.36, = 0（入）=0.4. 入=色 + 0.382（伏一如）=0.382（3.82-0） = 1.46,（p（） = （1.46-3） 2 = 2.37 ? 0（入） 0（“3），伏一心 =3.82一1.46 ? 第四次迭代： a4 .46, /?4=h.= 3.82,入=角=2.36, （兄斗）=次角） =0.4 ? “4 =為 + 0.618（

33、勺 _ 偽） T?46 + 0.0.618（3.82-1.46） = 2.918,俠角）=0.0067 . 0（入） 久儿），乞一入 =3.82 2.36 ? 第五次迭代： a5= A4 = 2.36, Q = b4 3.82,入=角=2.918,入） =仅角）0.0067 . “5 = as +0.618（2 - ） = 3.262,0（5）= 0.0686 ? 0（入）? 第六次迭代： a6 = a 5= 2.36,人= 3.262,佻=入=2.918, （/6） = （人）=0.0067 ? 几6 = % +0.382（/?6 务） =2.7045, 0（人）=0.087 . 0（入）

34、0（“6），4 一入=3.262-2.7045 ? 第七次迭代： = A6 = 2.7045, $ = b（、= 3.262,入=儿、=2.91& （入）=。（他） =0.0067 ? 角= +0.618&7 均） =3.049, （p（肉）=0.002 ? （P（人） 帙禺）,虬一入? 第八次迭代： = 心=2.918,2 = $ = 3.262,心=“7 = 3.049,)=呎厲)=0.002 ? “8 =兔+0.618(2 色)=331,0(忽)0.017 ? 0（入）V0（“），血一娥 ? 第九次迭代： ciq =遍=2.918, /?9 =从=3.131,角=入=3.049, 0（角

35、）=0（心）=0.002 ? A)=。9 +0?382(/?9 - 兔)=2.999,卩(入)= 0.000001 ? （入） 7/4、 = x + 人 8 再写成f(x) = x T Gx V/(x) = Gx ? V/(x (2) = (O,O,O) 7/( 兀)=0 ,所以耍确定调整方向. 由于/(J ( O) = O,/(/) = O,/(y )=：，按(8.4. 17)式有 4 /(y (1) )-/(y (2) = rnaxfAy)-/ (y +,) | j = 0,1, 因此m = l,并且 Q /(/ M) )-/(/ M+1) ) = /(y (,)-/ (y 2) =- ?

36、 4 乂因/（2y-y（） = 0, 故（8?4.18）式不成立 . 于 是，不调整搜索方向组，并 令兀=严=弓 3. 第二次迭代： 取/?=兀 = d,oj，从点屮）出发沿d作一维搜索，得 2 A）= / +入0 =（| ，扌） 7 . 接着从点y出发沿方向作一维搜索，得 由此冇加速方向 2 =严-严=（右討? d2=3A/5/8 ,所以要确定调整方向. 因 / （宀专心新（宀罟 （8?4?17）式易知m = 0,并且 o f(y (m)-f(ym+) ) = /(y (o) )-/(y (1)=- 16 由于 /（2严一严）=巻， 1O （8. 4.18）式成立。于是，从点y出发沿作一维搜

37、索，得 召=，兀=y (2 + = (2,1)卩 o 同吋，以2替换心，即下一次迭代的搜索方向组取为 3 3 - ()=(1,0),%= (, )7? o 4 16、用外罚函数法求解| min/(A)=(X_1)2； s.t. x-20. 取(T, =0.5,6T = 2, = 10_4? 解引入罚函数 F(x, q)=( 兀 _ 1)_ + (max0,( 兀2) = (x 1) + -(x 2) + (2 x) 12 x | 因为 故按 因此 则原约朿最优化问题相应的一系列无约朿最优化问题为：min F（x, q）, 其中0 =0.5, S+i = 2ak, k = 1,2,? 解上述无约

38、束问题，得*牆，同时吋（小希 ? 依次对k = l,2,用上述公式计算无和qPg , 结果如下表所示 . k乐叫）k卅（母） 11. 33332. 222x10“91.99227. 692x10 -3 21.52. 5xl0 _l 101.99613. 876xIO -3 31. 66672. 222x10“111.99811.946x10 41.81. 6xl0 _, 121.99909. 747XW 4 51.88899. 877xIO -2 131.99954. 878xIO -4 61.94125. 536x10-2141.99982. 440X10-4 71. 96972. 938xIO -2 151.99991.220x10“ 81. 98461.515X10 -2 161.99996. 103X10-5 由迭代终止条件馬占可得原约束问题的近似最优解（保留4 位有效数字）西6 =1.9999.