最优化试题及答案

最优化理论、方法及应用试题一、（30分）1、针对二次函数1()2TTfxxQxbxc，其中Q是正定矩阵，试写出最速下降算法的详细步骤，并简要说明其优缺点？答：求解目标函数的梯度为()gxQxb，()kkkggxQxb，搜索方向：从kx出发，沿kg作直线搜索以确定1kx。Step1:选定0x,计算00,fgStep2:做一维搜索,1minkkktffxtg,1kkkxxtg.Step3：判别，若满足精度要求，则停止；否则，置k=k+1,转步2。优缺点：最速下降法在初始点收敛快，算法简单，在最优点附近有锯齿现象，收敛速度慢。2、有约束优化问题min()()0,1,2,,..()0,1,2,,ijfxgximsthxjl最优解的必要条件是什么？答：假设*x是极小值点。必要条件是f，g，h函数连续可微，而且极小值点的所有起作用约束的梯度(*)(1,2,,)ihxil和(*)(1,2,,)jgxjm线性无关，则存在******1212,,,,,,,,lm使得11******1212**(*)*(*)*(*)0*(*)0,1,2,,,,,,,,,00,0lmiijjiijjlmijfxhxgxgxjm3、什么是起作用约束？什么是可行方向？什么是下降方向？什么是可行下降方向？针对上述有约束优化问题，如果应用可行方向法，其可行的下降方向怎样确定？答：起作用约束：若0()0jgx，这时点0x处于该约束条件形成的可行域边界上，它对0x的摄动起到某种限制作用。可行方向：0x是可行点，某方向p，若存在实数00，使得它对任意00,，均有0xp可行点集合，则称方向p是点0x的可行方向。下降方向：某一可行点0x，对该点的任一方向p来说，若存在实数0'0，使对任意00,'均有00fxpfx，就称方向p为0x点的一个下降方向。可行下降方向：既是可行方向，又是下降方向。可行方向的确定：可行方向法就是沿下降容许方向搜索并保持迭代点为可行点的一种迭代方法。二、（25分）1、回答出n维空间中非零向量系12,,nppp相互共轭的定义。答：设Q是n×n对称正定矩阵。若n维空间中非零向量系12,,nppp满足,,1,2,,,,ijpQpijnij则称12,,nppp是Q共轭的，或称12,,nppp的方向是Q共轭方向。2、应用共轭梯度方法求解无约束优化问题2212min8xx，初始点为011Tx。答：假设误差范围是0.001。12220,()16016xQfxx，初始搜索方向002()16Pfx步长：00000()()2600.06344104TTfxfxtPQP，1000120.87320.06341160.0144xxtP第二步迭代：11.7464()0.2304fx，1()1.7615fx,10000()51.99680.01274104TTfxQPPQP，11001.7718()0.0272PfxP，步长：11111()()3.10300.49336.2904TTfxfxtPQP21110.87321.77180.00080.49330.01440.02720.001xxtP3、对于无约束优化问题2212min8xx，写出其下降的牛顿方向，并应用牛顿算法迭代两步，初始点仍取为011Tx。答：102200,16016gG，求解方程111GPg，111/21/16G，11111/2211/16161PGg。于是211110110xxP。三、（20分）1、针对有约束优化问题()0,1,2,,min(),..()0,1,2,,ijgximfxsthxjl试构造出两种外部惩罚函数(,)Fx。答：(,)()()Fxfxx，其中2211()()()(())lmjiijixhxgxugx，0,()0,xDxxD。其它选择2211()()min(0,())lmjijixhxgx2、最小二乘问题2min()()()()TJxfxfxfx用台劳公式进行一阶线性化得()()()()kkkfxfxAxxx，将问题转化为如下的问题2minkkfAP，其中,(),()kkkkkPxxffxAAx是函数在kx处的Jacobi矩阵。证明算法11TTkkkkkkxxAAAf（1）当TkkAA非奇异时，方向P是下降的（2）当TkkAA接近奇异时，方向1()TTkkkkkkPAAIAf也是下降的。其中k是一个适当的常数。证明：（1）即证明()0TkkJxP，()22()2()()TTTkkkkkkkJxAfAxxAxfx，A（x）是f(x)的Jacobi矩阵，TkkkgAf，故()2()()2TkkkkJxAxfxg，1()2()()0TkkkkkkJxPgAxAxg。（2）当TkkAA接近奇异时，若ks是一个适当的常数，则1()TkkkAAI存在，从而1()2()0TkkkkkkkJxPgAAIg，因此方向1()TTkkkkkkPAAIAf也是下降的。四、（15分）求解如下的约束优化问题221221212()(2)(1)0..20fxxxxxstxx答：先求满足K-T条件的点1222()21xfxx，11221(),()11xgxgx，1112212211221221212122(2)202(2)0020020,0xxxxxxxxxxx，解得：1212112/32/3xx五、（10分）将Zoutendijk可行方向法应用于优化问题min()xfx，其中|,xAxbCxd中，其中A，b,C,d是响应的矩阵。试给出可行下降方向和最优步长的确定方法。答：假设x是题中的某个容许点。适当调换A的行向量和b的响应分量，然后分解'''AAA，相应的分解'''bbb，使得'',''''AxbAxb。则非零向量P为从点x出发的容许方向向量的充要条件是'0,0APCP。min().'0..011,1,2,,TjfxPApstCPPjn由此可得到的有限的最优解，设为P*，P*为点x处的一个下降容许方向向量。为了确定一个新的迭代点x，可以从点x出发沿下降容许方向P*直线搜索，即(**)min(*),**fxtPfxtPxxtP最优步长t*的确定(*)min(*),..(*)()0AxtPbfxtPstCxtPdt多余(*)AxtPb分解成'(*)'''(*)''AxtPbAxtPb，简化成''(*)''min(*),..0AxtPbfxtPstt。求可行区间：''''''*AxbtAPutv，u，v的维数与''b相同，0u，当0v时，对0t，utv总成立。从而''''''*AxbtAP成立，此时t，当0v时，为使utv成立，即(1,2,,)iiutvi成立，只需考虑0iv的不等式若取1min{0}iiiiutvv，则对0,tt，都有(1,2,,)iiutvi成立，从而1,0min{0},0iiiiiivtuvvv。