最优化理论测试题及参考答案

最优化理论测试题及参考答案考试时间：______分钟总分：______分姓名：______一、单项选择题（每题3分，共30分。下列每小题的选项中，只有一项是符合题目要求的。）1.在最优化问题的数学模型中，目标函数表示的是（）。A.决策变量B.约束条件C.优化求解的对象D.变量的取值范围2.若函数f(x)在点x₀处的一阶导数为零且二阶导数大于零，则点x₀是函数f(x)的（）。A.局部最优解B.全局最优解C.非极值点D.拐点3.下列说法中，正确的是（）。A.所有的无约束优化问题都存在全局最优解B.如果一个无约束优化问题是凸的，那么其任何局部最优解都是全局最优解C.所有最优化方法都能保证在有限步内找到最优解D.拉格朗日乘子法只能用于处理线性约束优化问题4.梯度法在每一步搜索方向沿着（）。A.目标函数的等值线B.目标函数梯度的反方向C.目标函数梯度的方向D.目标函数海森矩阵的特征向量方向5.牛顿法利用了函数的二阶导数信息，其收敛速度通常比梯度法（）。A.更慢B.相同C.更快D.不确定，取决于具体问题6.对于非线性约束优化问题，KKT条件是（）。A.最优解的必要条件B.最优解的充分条件C.最优解的必要且充分条件D.初始点的可行性条件7.在处理不等式约束x≥0时，罚函数法通常引入的惩罚项形式为（）。A.max(0,x)B.-min(0,x)C.(x-x*)²D.xln(x)8.凸优化问题的优点之一是（）。A.可能存在多个不相容的最优解B.任何局部最优解都是全局最优解C.最优解一定是整数D.必须使用复杂的数值方法求解9.共轭梯度法主要适用于（）。A.线性规划问题B.约束优化问题C.求解大型稀疏线性方程组D.具有对称正定海森矩阵的二次凸规划问题10.若一个优化算法在有限步内就能保证达到最优解，则称该算法是（）。A.局部收敛B.全局收敛C.终止性算法D.无约束算法二、填空题（每空2分，共20分）1.最优化问题的解x*称为________解，如果对于所有满足约束条件的点x，都有f(x*)≤f(x)。2.对于无约束优化问题，函数f(x)在点x₀处取得局部最优解的一阶必要条件是∇f(x₀)=________。3.牛顿法中，搜索方向是________的逆矩阵与梯度向量的乘积。4.拉格朗日乘子λ*是________的比值。5.KKT条件中的互补松弛条件要求，对于每个不等式约束gᵢ(x)≤0，要么满足gᵢ(x*)=0，要么满足________。6.如果一个优化算法的收敛速度以二次方速度收敛，那么其每一步迭代产生的近似解的误差大约是前一步误差的________倍。7.函数f(x,y)=x²+y²在全域R²上的全局最小值是________，在约束x+y=1下的最优解是________。8.在最优化理论中，函数f(x)的Hessian矩阵Hf(x)判断无约束优化问题局部凸性的依据是________。三、计算题（每题10分，共30分）1.考虑无约束优化问题：f(x,y)=x²+2xy+3y²。求函数f(x,y)在点(1,1)处的梯度∇f(1,1)和海森矩阵Hf(1,1)。并判断点(1,1)是否为局部最优解。2.使用梯度法求解函数f(x)=x₁²+2x₂²的最小值，初始点取x^(0)=(1,1)，迭代步长为0.5。3.考虑约束优化问题：minf(x,y)=x²+y²，s.t.x+y=1。写出该问题的拉格朗日函数，并利用KKT条件求解最优解x*和y*。四、证明题（每题15分，共30分）1.证明：如果一个无约束优化问题的目标函数是严格凸函数，那么该问题一定存在唯一的全局最优解。2.证明：对于二次凸规划问题min½xᵀQx+cᵀx，其中Q为对称正定矩阵，其牛顿方向d=-Hf(x)=-Q⁻¹c是下降方向，即∇f(x)ᵀd<0。试卷答案一、单项选择题1.C2.A3.B4.C5.C6.A7.A8.B9.D10.C二、填空题1.全局2.03.海森矩阵4.目标函数在最优解处的梯度与拉格朗日函数在最优解处对对应乘子的偏导数5.λᵢ(x*)>06.一7.0；(0.5,0.5)8.Hf(x)在该点正定三、计算题1.解：梯度：∇f(x,y)=(2x+2y,2x+6y)ᵀ∇f(1,1)=(4,8)ᵀ海森矩阵：Hf(x,y)=[[2,2],[2,6]]Hf(1,1)=[[2,2],[2,6]]判断：Hf(1,1)的特征值分别为8和0。由于存在零特征值，Hf(1,1)不可逆，不满足二阶最优性条件，因此(1,1)不是局部最优解。（或通过判断特征值正负性判断非正定）2.解：梯度：∇f(x)=(2x₁,4x₂)ᵀx^(0)=(1,1),∇f(x^(0))=(2,4)ᵀ迭代步长α=0.5下一个点：x^(1)=x^(0)-α∇f(x^(0))=(1,1)-0.5*(2,4)=(0,-1)x^(1)=(0,-1),∇f(x^(1))=(0,-4)ᵀ下一个点：x^(2)=x^(1)-α∇f(x^(1))=(0,-1)-0.5*(0,-4)=(0,1)此时∇f(x^(2))=(0,0)ᵀ，梯度为零，迭代停止。最优解近似为x=(0,1)，最优值f(0,1)=2。3.解：拉格朗日函数：L(x,y,λ)=x²+y²+λ(x+y-1)KKT条件：∇_xL=(2x+λ,2y+λ)ᵀ=0=>2x+λ=0,2y+λ=0∇_yL=λ=0约束条件：x+y=1由∇_yL=λ=0代入∇_xL得2x=0,2y=0，即x=0,y=0。但(0,0)不满足约束x+y=1。因此λ≠0。由2x+λ=0和2y+λ=0得2x=2y，即x=y。代入约束x+y=1得x+x=1，即2x=1，解得x=0.5，y=0.5。此时λ=-2x=-1。最优解x*=(0.5,0.5)，λ*=-1。四、证明题1.证明：假设目标函数f(x)是严格凸函数，最优解x*存在。设x₁和x₂是任意两个不同的可行解，即x₁≠x₂。根据严格凸函数的定义，对于任何λ∈(0,1)，有f(λx₁+(1-λ)x₂)<λf(x₁)+(1-λ)f(x₂)。由于f(x)是凸优化问题的目标函数，λx₁+(1-λ)x₂也是可行解。由x*是最优解，有f(x*)≤f(λx₁+(1-λ)x₂)。结合以上不等式，得到f(x*)≤f(λx₁+(1-λ)x₂)<λf(x₁)+(1-λ)f(x₂)。由于λ∈(0,1)，上述不等式可变形为f(x*)<λf(x₁)+(1-λ)f(x₂)≤max{f(x₁),f(x₂)}。这表明f(x*)是所有可行解中的最小值，即x*是全局最优解。此外，严格凸函数的局部最优解也是唯一的，因此x*是唯一的全局最优解。2.证明：对于二次凸规划问题，目标函数的梯度为∇f(x)=2Qx+c。牛顿方向d=-Hf(x)=-Q⁻¹c。计算∇f(x)ᵀd：∇f(x)ᵀd=(2Qx+c)ᵀ(-Q⁻¹c)=-(2Qx+c)ᵀQ⁻¹c=-[Qx+½c]ᵀQ⁻¹c（因为Qxᵀ=xᵀQ，cᵀQ⁻¹c=cᵀQ⁻¹c）=-(Qx+½c)ᵀQ⁻¹(Qx+½c)=-(Qx+½c)ᵀ(Q⁻¹Q)x-(Qx+½c)ᵀQ⁻¹(½c)=-(Qx+½c)ᵀx-(Qx+½c)ᵀ(½Q⁻¹c)=-(xᵀQx+½xᵀc)-(½xᵀQ⁻¹c+½cᵀQ⁻¹c)=-xᵀQx-xᵀc-½xᵀQ⁻¹c-½cᵀQ⁻¹c=-xᵀQx-xᵀc-½cᵀQ⁻¹c-½cᵀQ⁻¹c（注意cᵀQ⁻¹c是标量，等于cᵀ(Q⁻¹)ᵀc）=-xᵀQx-xᵀc-cᵀQ⁻¹c=-[½