最优化试题及答案

最优化理论、方法及应用试题

一、

（30分）

12xQx?bx?c，其中

TT1、针对二次函数f(x)?Q是正定矩阵，试写出最速下降

算法的详细步骤，并简要说明其优缺点？

答：求解目标函数的梯度为g(x)?Qx?b，gk?g(xk)?Qxk?b，搜索方向：从xk出发，沿?gk作直线搜索以确定xk?1。

Step1: 选定x0,计算f0,g0

Step2: 做一维搜索, fk?1?minf?xk?tgk?,xk?1?xk?tgk.

tStep3：判别，若满足精度要求，则停止；否则，置k=k+1,转步2。

优缺点：最速下降法在初始点收敛快，算法简单，在最优点附近有锯齿现象，收敛速度慢。

2、有约束优化问题

minf(x)s.t.??gi(x)?0,i?1,2,?,m ???hj(x)?0,j?1,2,?,l最优解的必要条件是什么？

答：假设x*是极小值点。必要条件是f，g，h函数连续可微，而且极小值点的所有起作用约束的梯度?hi(x*)(i?1,2,?,l)和?gj(x*)(j?1,2,?,m)线性无关，则

*****,?,?l,?1,?2,?,?m,使得 存在?1*,?2lmi?f(x*)???i?1**?hi(x*)???i?1*j*?gj(x*)?0?j*gj(x*)?0,j?1,2,?,m

??**1,?2,?,?l,?1,?2,?,?m??0****?i?0,?j?03、什么是起作用约束？什么是可行方向？什么是下降方向？什么是可行下降方向？针对上述有约束优化问题，如果应用可行方向法，其可行的下降方向怎样确定？ 答：起作用约束：若gj(x0)?0，这时点x0处于该约束条件形成的可行域边界上，它对x0的摄动起到某种限制作用。

可行方向：x0是可行点，某方向p，若存在实数?0?0，使得它对任意

???0,?0?，均有x0??p?可行点集合，则称方向p是点x0的可行方向。

下降方向：某一可行点x0，对该点的任一方向p来说，若存在实数?0'?0，

使对任意???0,?0'?均有f?x0??p??f?x0?，就称方向p为x0点的一个下降方向。 可行下降方向：既是可行方向，又是下降方向。

可行方向的确定：可行方向法就是沿下降容许方向搜索并保持迭代点为可行点的一种迭代方法。

二、 （25分）

1、回答出n维空间中非零向量系p1,p2,?pn相互共轭的定义。 答：设Q是n×n对称正定矩阵。若n维空间中非零向量系p1,p2,?pn满足

piQpj,i,j?1,2,?,n,i?j,则称p1,p2,?pn是Q共轭的，或称p1,p2,?pn的方向是Q

共轭方向。

2、应用共轭梯度方法求解无约束优化问题min?x12?8x22?，初始点为x0??11?。

?2??0.001答： 假设误差范围是。Q???0??2?P0???f(x0)?????16?TT0??2x1??，初始搜索方向?,?f(x)??16x16??2?

2604104步长：t0??f0(x)?f0(x)P0QP0T??0.0634，

?1???2??0.8732?x1?x0?t0P0????0.0634?????1?16??????0.0144??1.7464?

第二步迭代：?f(x1)???，?f(x1)?1.7615,

??0.2304??0??f(x1)QP0P0QP0TTT?51.99684104??1.7718??0.0127，P1???f(x1)??0P0????0.0272?3.10306.2904?0.4933，

步长：t1??f(x1)?f(x1)P1QP1T?

?0.8732???1.7718???0.0008?x2?x1?t1P1???0.4933??????

??0.0144??0.0272???0.001?3、对于无约束优化问题min?x12?8x22?，写出其下降的牛顿方向，并应用牛顿算法迭代两步，初始点仍取为x0??11?。

?1答：g1????0,G0??，求解方程，G??GP??g1111??16??016??T?2??20??1/2??， 1/16??1/2?1P1??G1g1?????1???2???1???????。 1/16??16???1??1??0?于是x2?x1?P1?????????。

?1??1??0?三、

（20分）

??gi(x)?0,i?1,2,?,m1、针对有约束优化问题minf(x),s.t.???hj(x)?0,j?1,2,?,l试构造出两种外部惩罚函数F(x,?)。

l2jm2i答：F(x,??)?0,x?D?(x)????0,x?Df(?x)??，(x其中?(x)????hj?1(x)?????gi?1(x)?u(gi(x))，

。

l2jm2i其它选择?(x)????hj?1(x)?????min(0,gi?1(x))?

2、最小二乘问题

minJ(x)?f(x)f(x)?f(x)T2

用台劳公式进行一阶线性化得f(x)?f(xk)?A(xk)(x?xk)，将问题转化为如下的问题

minfk?AkP2，

其中P?x?xk,fk?f(xk),Ak?A(xk)是函数在xk处的Jacobi矩阵。证明算法

xk?1?xk??AkAkT??1AkfkT

（1） 当AkTAk非奇异时，方向P是下降的

（2） 当AkTAk接近奇异时，方向Pk??(AkTAk??kI)?1AkTfk也是下降的。其中

?k是一个适当的常数。

证明：（1）即证明?JT(xk)Pk?0，?J(xk)?2AkTfk?2AkT(x?xk)?2AT(xk)f(xk)，A（x）是f(x)的Jacobi矩阵，gk?AkTfk，故?J(xk)?2AT(xk)f(xk)?2gk，

?J(xk)Pk??2gk?A(xk)A(xk)?T?1gk?0。

（2）当AkTAk接近奇异时，若?ks是一个适当的常数，则(AkTAk??kI)?1存在，从而?J(xk)Pk??2gk(AkTAk??kI)?1gk?0，因此方向Pk??(AkTAk??kI)?1AkTfk也是下降的。

四、 （15分）

求解如下的约束优化问题

f(x)?(x1?2)?(x2?1)s.t.??x12?x2?0???x1?x2?2?022

答：先求满足K-T条件的点?f(x)???2?x1?2????2x1???1??g(x)?,?g(x)?， ?12????，

1?12x?1????????2?2(x1?2)?2?1x1??2?0?2(x2?2)??1??2?0??x1?1????x2?x??0112???x2?1?，解得： ???2??x1?x2?2??0??1?2/3?2???2/3??x1?x2?0?2??x?x?2?012????1,?2?0五、 （10分）

x??将Zoutendijk可行方向法应用于优化问题minf(x)，其中???x|Ax?b,Cx?d?中，其中A，b,C,d是响应的矩阵。试给出可行下降方向和最优步长的确定方法。 答：假设x是题中的某个容许点。适当调换A的行向量和b的响应分量，然后分解

?A'?A????A''??b'?b?，相应的分解??，使得A'x?b',A''x?b''。则非零向量

?b''?P为

从点x出发的容许方向向量的充要条件是A'P?0,CP?0。

min?f(x)P.?A'p?0 ?s.t.?CP?0??1?P?1,j?1,2,?,nj?T由此可得到的有限的最优解，设为P*，P*为点x处的一个下降容许方向向量。

?，可以从点x出发沿下降容许方向P*直线搜索，为了确定一个新的迭代点x即f(x?t*P*)?minf(x?tP*),x?x?t*P* 最优步长t*的确定

?A(x?tP*)?b?minf(x?tP*),s.t.?C(x?tP*)?d(多余)

?t?0?A(x?tP*)?b分解成

A'(x?tP*)?b'A''(x?tP*)?b''，简化成minf(x?tP*),s.t.??A''(x?tP*)?b''?t?0。

求可行区间：A''x?b''?tA''P*?u??tv，u，v的维数与b''相同，u?0，当v?0时，对?t?0，u??tv总成立。从而A''x?b''?tA''P*成立，此时t???，当v?0时，为使u??tv成立，即ui??tvi(i?1,2,?,?)成立，只需考虑vi?0的不等式 若取t?min{?1?i??uivivi?0}，则对t??0,t?，都有ui??tvi(i?1,2,?,?)成立，从而

??,vi?0??。 t??uimin{?v?0},v?0ii?1?i??vi?

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库最优化试题及答案在线全文阅读。