2025年大学《数理基础科学》专业题库- 最优化问题及解法

2025年大学《数理基础科学》专业题库——最优化问题及解法考试时间：______分钟总分：______分姓名：______一、选择题（每题2分，共10分。请将正确选项的字母填在题后的括号内）1.函数f(x,y)=x²-y²在点(1,1)处的梯度∇f(1,1)等于？(A)(2,-2)(B)(2,2)(C)(-2,2)(D)(-2,-2)2.对于二次函数f(x)=xᵀQx+cᵀx（其中Q对称正定），牛顿法通常能？(A)一次迭代即找到全局最优解(B)在有限次迭代内找到全局最优解(C)可能陷入局部最优解(D)保证找到鞍点3.对于约束优化问题minf(x)s.t.h(x)=0，下列说法正确的是？(A)拉格朗日乘子法只能处理不等式约束(B)KKT条件是必要最优性条件(C)函数f(x)在最优解x*处的梯度必垂直于可行方向(D)只要满足KKT条件，x*必为全局最优解4.在解决不等式约束优化问题时，罚函数法通过引入惩罚项，使得原始问题的最优解与转化后无约束问题的最优解？(A)总是相同(B)总是不同(C)对于可行初始点相同，对于不可行初始点不同(D)对于可行初始点不同，对于不可行初始点相同5.共轭梯度法主要用于求解？(A)任何线性方程组(B)非对称正定矩阵的线性方程组(C)对称正定矩阵的线性方程组(D)特殊稀疏矩阵的线性方程组二、填空题（每空3分，共15分。请将答案填在题中的横线上）1.梯度方向是函数f(x)在点x处沿该点处变化率______的方向。2.对于无约束优化问题，如果H(x)（Hessian矩阵）在点x*处正定，则x*是函数f(x)的______点。3.KKT条件包含三个组成部分：可行性条件、Stationarity条件和______条件。4.对于不等式约束minf(x)s.t.gi(x)≤0(i=1,...,m)，增广拉格朗日函数通常包含项______λᵢ(r)，其中r>0，λᵢ为拉格朗日乘子。5.在共轭梯度法中，搜索方向{p^k}满足______关系，其中A是对称正定矩阵。三、解答题（共75分）1.（15分）用梯度下降法求解函数f(x)=x₁²+x₂²-4x₁-4x₂的最小值，初始点为x^(0)=(3,3)，学习率α=0.1。要求计算前两次迭代点的坐标，并说明每次迭代的方向向量。2.（15分）考虑约束优化问题：minf(x)=x₁²+4x₂²s.t.g(x)=x₁+x₂-5=0。（1）写出该问题的拉格朗日函数L(x,λ)。（2）求解KKT条件，找出可能的最优解。（3）验证该最优解是否为全局最优解。3.（15分）设函数f(x)=x₁²+2x₁x₂+x₂²，定义域为D={x|x₁²+x₂²≤1}。（1）求解f(x)在可行域D上的最优解（包括全局最小值点和值）。（2）使用罚函数法（选择合适的惩罚参数λ和障碍参数r），将此约束优化问题转化为无约束优化问题，并说明转化思路。4.（15分）设A是n×n对称正定矩阵，b是n维向量。证明：共轭梯度法求解Ax=b的迭代过程中，相邻两个迭代向量x^(k)和x^(k+1)是A-共轭的。5.（15分）比较梯度法、牛顿法和共轭梯度法在求解无约束优化问题时的优缺点，并说明在什么情况下选择哪种方法可能更合适。试卷答案一、选择题1.(A)2.(B)3.(C)4.(C)5.(C)二、填空题1.最大2.局部最小3.Primalfeasibility4.-μ/25.{p^k}ᵀAp^{k+1}=0三、解答题1.解析思路：*梯度下降法更新公式：x^(k+1)=x^(k)-α∇f(x^(k))。*计算目标函数f(x)=x₁²+x₂²-4x₁-4x₂的梯度：∇f(x)=(2x₁-4,2x₂-4)。*初始点x^(0)=(3,3)，梯度∇f(x^(0))=(2*3-4,2*3-4)=(2,2)。*第一次迭代：*更新点：x^(1)=x^(0)-α∇f(x^(0))=(3,3)-0.1*(2,2)=(3-0.2,3-0.2)=(2.8,2.8)。*当前梯度：∇f(x^(1))=(2*2.8-4,2*2.8-4)=(5.6-4,5.6-4)=(1.6,1.6)。*迭代方向：-α∇f(x^(0))=-0.1*(2,2)=(-0.2,-0.2)。*第二次迭代：*更新点：x^(2)=x^(1)-α∇f(x^(1))=(2.8,2.8)-0.1*(1.6,1.6)=(2.8-0.16,2.8-0.16)=(2.64,2.64)。*当前梯度：∇f(x^(2))=(2*2.64-4,2*2.64-4)=(5.28-4,5.28-4)=(1.28,1.28)。*迭代方向：-α∇f(x^(1))=-0.1*(1.6,1.6)=(-0.16,-0.16)。*结果：前两次迭代点分别为(2.8,2.8)和(2.64,2.64)，每次迭代的方向向量为(-0.2,-0.2)和(-0.16,-0.16)。2.解析思路：*（1）拉格朗日函数：L(x,λ)=f(x)+λg(x)=x₁²+4x₂²+λ(x₁+x₂-5)。*（2）求解KKT条件：*∇_xL(x,λ)=(2x₁+λ,8x₂+λ)=0。得到2x₁+λ=0和8x₂+λ=0。*∇_λL(x,λ)=x₁+x₂-5=0。*可行性条件：g(x)=x₁+x₂-5≤0。*从∇_xL=0得到λ=-2x₁和λ=-8x₂。因此-2x₁=-8x₂，即x₁=4x₂。*代入∇_λL=0：x₁+x₂-5=4x₂+x₂-5=5x₂-5=0。解得x₂=1。*再由x₁=4x₂得x₁=4。*可能的最优解为x*=(4,1)。*代入可行性条件：g(x*)=4+1-5=0。解满足可行性条件。*（3）验证最优性：*函数f(x)=x₁²+4x₂²是一个严格凸函数（因为其Hessian矩阵A=[[2,0],[0,8]]正定）。*约束g(x)=x₁+x₂-5定义了一个通过点(4,1)的直线，且点(4,1)是该直线上满足x₁²+4x₂²最小的点（在可行域边界上）。*因此，该问题在x*=(4,1)处存在唯一的局部最优解，且由于目标函数和约束均为凸，该局部最优解即为全局最优解。3.解析思路：*（1）分析函数和可行域：*函数f(x)=x₁²+2x₁x₂+x₂²可写为f(x)=(x₁+x₂)²-x₂²。*函数在原点(0,0)处取得值为0，这是函数的一个驻点（梯度为0）。检查Hessian矩阵[[2,2],[2,2]]，其行列式为4-4=0，不是正定矩阵，因此(0,0)不是严格局部最小值点。*可行域D={x|x₁²+x₂²≤1}是以原点为中心，半径为1的圆盘。*在可行域内部(x₁²+x₂²<1)，函数f(x)=(x₁+x₂)²-x₂²在原点取得最小值0。*在可行域边界(x₁²+x₂²=1)上，考虑拉格朗日函数L(x,λ)=(x₁+x₂)²-x₂²+λ(x₁²+x₂²-1)。*令∇_xL=(2(x₁+x₂),2(x₁+x₂)-2x₂)+(2λx₁,2λx₂)=0。*得到方程组：2(x₁+x₂)+2λx₁=0和2(x₁+x₂)-2x₂+2λx₂=0。*整理得：(1+λ)x₁+(1+λ)x₂=0和(1-λ)x₁+(1+λ)x₂=0。*若x₁+x₂=0，则x₂=-x₁。代入约束x₁²+x₂²=1，得x₁²+(-x₁)²=1，即2x₁²=1，x₁=±√(1/2)，x₂=∓√(1/2)。对应点为(√(1/2),-√(1/2))和(-√(1/2),√(1/2))。函数值为f(√(1/2),-√(1/2))=(√(1/2)-√(1/2))^2-(√(1/2))^2=-1/2。f(-√(1/2),√(1/2))也为-1/2。*若λ≠-1，则x₁+x₂=0和x₁-λx₂=0联立，得x₁=λx₂。代入约束x₁²+x₂²=1，得(λx₂)²+x₂²=1，即(λ²+1)x₂²=1，x₂²=1/(λ²+1)，x₂=±1/√(λ²+1)。x₁=λx₂=±λ/√(λ²+1)。需要满足x₁²+x₂²=1，即(λ/√(λ²+1))²+(1/√(λ²+1))²=λ²/(λ²+1)+1/(λ²+1)=(λ²+1)/(λ²+1)=1。此解满足约束，但代入f(x)=(x₁+x₂)²-x₂²=0-x₂²=-x₂²=-(1/(λ²+1))<0。这比边界上的-1/2更小，不在可行域边界上，因此无解。*综上，全局最小值为-1/2，在边界点(√(1/2),-√(1/2))和(-√(1/2),√(1/2))处取得。*（2）罚函数法转化：*考虑不等式约束minf(x)s.t.g(x)=x₁²+x₂²-1≤0。*使用外部罚函数法，构造罚函数Φ(x,r)=f(x)+ρ(x₁²+x₂²-1)²，其中ρ>0为惩罚参数。*该罚函数在原问题可行域内（x₁²+x₂²<1）与原目标函数等价，在边界上（x₁²+x₂²=1）目标函数值会显著增大。*问题转化为求解一系列无约束优化问题：min_Φ(x,r)Φ(x,r)=x₁²+x₂²-4x₁-4x₂+ρ(x₁²+x₂²-1)²，对不同的r>0进行求解。*当r足够大时，罚项ρ(x₁²+x₂²-1)²的值会非常大（除非x₁²+x₂²≈1），使得函数Φ(x,r)在x₁²+x₂²<1的区域无最小值或最小值远离最优解。随着r增大，最优解会逐渐逼近原问题的边界约束x₁²+x₂²=1。*转化思路：通过引入对不满足约束的惩罚，使得无约束问题的最优解序列在r增大的过程中，逐渐收敛到原约束优化问题的最优解。4.解析思路：*证明：设x^(k)和x^(k+1)是共轭梯度法求解Ax=b的相邻两个迭代向量。*根据共轭梯度法的定义，搜索方向p^(k)=-∇f(x^(k))+β^kp^(k-1)，其中β^k=(∇f(x^(k))ᵀ∇f(x^(k+1)))/(∇f(x^(k-1))ᵀ∇f(x^(k-1)))。*对于二次函数f(x)=xᵀQx+cᵀx，梯度为∇f(x)=2Qx+c。因为A是对称正定矩阵，所以Q=A。*因此，∇f(x^(k))=2Ax^(k)+b，∇f(x^(k+1))=2Ax^(k+1)+b。*要证明x^(k)和x^(k+1)是A-共轭的，即要证明A(x^(k+1))ᵀx^(k)=0。*计算：(A(x^(k+1))ᵀx^(k))=A((x^(k)+p^(k))ᵀx^(k))（因为x^(k+1)=x^(k)+p^(k)）*=A(x^(k)ᵀx^(k)+p^(k)ᵀx^(k))（向量转置的分配律）*=A(x^(k)ᵀx^(k))+A(p^(k)ᵀx^(k))（矩阵与向量的结合律）*因为A是对称矩阵，A(x^(k)ᵀx^(k))=(x^(k)ᵀx^(k))A=x^(k)ᵀAx^(k)。*计算A(p^(k)ᵀx^(k))：*p^(k)=-∇f(x^(k))+β^kp^(k-1)=-2Ax^(k)-b+β^kp^(k-1)。*p^(k)ᵀx^(k)=(-2Ax^(k)-b+β^kp^(k-1))ᵀx^(k)=-2(x^(k)ᵀAx^(k))-(bᵀx^(k))+β^k(p^(k-1)ᵀx^(k))。*代入A(p^(k)ᵀx^(k))：*A(p^(k)ᵀx^(k))=A[-2(x^(k)ᵀAx^(k))-(bᵀx^(k))+β^k(p^(k-1)ᵀx^(k))]=-2A(x^(k)ᵀAx^(k))-A(bᵀx^(k))+β^kA(p^(k-1)ᵀx^(k))。*=-2x^(k)ᵀAx^(k)-A(bᵀx^(k))+β^kA(p^(k-1)ᵀx^(k))。*整理(A(x^(k+1))ᵀx^(k))：*A(x^(k+1))ᵀx^(k)=x^(k)ᵀAx^(k)-2x^(k)ᵀAx^(k)-A(bᵀx^(k))+β^kA(p^(k-1)ᵀx^(k))*=-x^(k)ᵀAx^(k)-A(bᵀx^(k))+β^kA(p^(k-1)ᵀx^(k))。*因为x^(k)是Ax=b的解，所以Ax^(k)=b，即bᵀx^(k)=(Ax^(k))ᵀx^(k)=x^(k)ᵀAx^(k)。*代入上式：A(x^(k+1))ᵀx^(k)=-x^(k)ᵀAx^(k)-A(x^(k)ᵀAx^(k))+β^kA(p^(k-1)ᵀx^(k))=-2x^(k)ᵀAx^(k)+β^kA(p^(k-1)ᵀx^(k))。*现在利用β^k的定义：β^k=(∇f(x^(k))ᵀ∇f(x^(k+1)))/(∇f(x^(k-1))ᵀ∇f(x^(k-1)))=(2Ax^(k)+b)ᵀ(2Ax^(k+1)+b)/(2Ax^(k-1)+b)ᵀ(2Ax^(k-1)+b)。*=[(2Ax^(k)+b)ᵀ(2Ax^(k)+2p^(k))]/[(2Ax^(k-1)+b)ᵀ(2Ax^(k-1)+b)]*=[4(Ax^(k))ᵀx^(k)+2(Ax^(k))ᵀp^(k)+2bᵀx^(k)+bᵀp^(k)]/[4(Ax^(k-1))ᵀx^(k-1)+2(Ax^(k-1))ᵀp^(k-1)+2bᵀx^(k-1)+bᵀp^(k-1)]*因为Ax^(k)=b,Ax^(k-1)=b-p^(k-1)，所以bᵀx^(k)=x^(k)ᵀAx^(k)=x^(k)ᵀb。*代入并简化β^k：*β^k=[4x^(k)ᵀb+2(Ax^(k))ᵀp^(k)+2x^(k)ᵀb+bᵀp^(k)]/[4x^(k-1)ᵀb+2(Ax^(k-1))ᵀp^(k-1)+2x^(k-1)ᵀb+bᵀp^(k-1)]*=[6x^(k)ᵀb+2(Ax^(k))ᵀp^(k)+bᵀp^(k)]/[6x^(k-1)ᵀb+2(Ax^(k-1))ᵀp^(k-1)+bᵀp^(k-1)]*再看A(p^(k-1)ᵀx^(k))：*A(p^(k-1)ᵀx^(k))=A(p^(k-1)ᵀ(x^(k)+p^(k)))=A(p^(k-1)ᵀx^(k))+A(p^(k-1)ᵀp^(k))。*所以β^kA(p^(k-1)ᵀx^(k))=β^k[A(p^(k-1)ᵀx^(k))-A(p^(k-1)ᵀp^(k))]。*将β^k和A(p^(k-1)ᵀx^(k))代入A(x^(k+1))ᵀx^(k)的表达式：*A(x^(k+1))ᵀx^(k)=-2x^(k)ᵀAx^(k)+β^k[A(p^(k-1)ᵀx^(k))-A(p^(k-1)ᵀp^(k))]*=-2x^(k)ᵀAx^(k)+β^kA(p^(k-1)ᵀx^(k))-β^kA(p^(k-1)ᵀp^(k))。*利用x^(k)ᵀAx^(k)=x^(k)ᵀb和Ax^(k)=b，得-2x^(k)ᵀAx^(k)=-2x^(k)ᵀb。*再利用bᵀp^(k)=(Ax^(k)+p^(k))ᵀp^(k)=x^(k)ᵀb+p^(k)ᵀp^(k)，所以bᵀp^(k)=x^(k)ᵀb+p^(k)ᵀp^(k)。*代入β^k的分子表达式：6x^(k)ᵀb+2(Ax^(k))ᵀp^(k)+bᵀp^(k)=6x^(k)ᵀb+2bᵀp^(k)+bᵀp^(k)=6x^(k)ᵀb+3bᵀp^(k)。*β^k=[6x^(k)ᵀb+3bᵀp^(k)]/[6x^(k-1)ᵀb+3bᵀp^(k-1)]。*再看分母中的6x^(k-1)ᵀb+3bᵀp^(k-1)：因为x^(k-1)=x^(k)-p^(k)，所以x^(k-1)ᵀb=(x^(k)-p^(k))ᵀb=x^(k)ᵀb-p^(k)ᵀb=x^(k)ᵀb-(Ax^(k)+p^(k))ᵀp^(k)=x^(k)ᵀb-x^(k)ᵀb-p^(k)ᵀp^(k)=-p^(k)ᵀp^(k)。*所以分母=-6p^(k)ᵀp^(k)+3bᵀp^(k-1)。*现在计算β^kA(p^(k-1)ᵀx^(k))：*β^kA(p^(k-1)ᵀx^(k))=β^kA(p^(k-1)ᵀ(x^(k)+p^(k)))=β^k[A(p^(k-1)ᵀx^(k))-A(p^(k-1)ᵀp^(k))]*β^kA(p^(k-1)ᵀx^(k))=β^k[A(p^(k-1)ᵀx^(k))]（假设A(p^(k-1)ᵀp^(k))=0，需要证明）*要证明A(p^(k-1)ᵀp^(k))=0，即A(p^(k-1))ᵀp^(k)=0。根据共轭梯度法定义，p^(k)与p^(k-1)是A-共轭的。*因此，β^kA(p^(k-1)ᵀx^(k))=0。*最终A(x^(k+1))ᵀx^(k)=-2x^(k)ᵀAx^(k)-β^kA(p^(k-1)ᵀp^(k))=-2x^(k)ᵀAx^(k)-0=-2x^(k)ᵀAx^(k)=-2x^(k)ᵀb。*注意到A(p^(k-1)ᵀx^(k))=A(p^(k-1)ᵀ(x^(k)+p^(k)))=A(p^(k-1)ᵀx^(k))+A(p^(k-1)ᵀp^(k))。如果A(p^(k-1)ᵀp^(k))=0，则A(p^(k-1)ᵀx^(k))=A(p^(k-1)ᵀx^(k))。要证明A(p^(k-1)ᵀp^(k))=0，即p^(k-1)ᵀ(Ax^(k))=0。Ax^(k)=b，所以需要p^(k-1)ᵀb=0。这与β^k的定义中的分子6x^(k-1)ᵀb+3bᵀp^(k-1)的形式有关。*回到A(x^(k+1))ᵀx^(k)=-2x^(k)ᵀAx^(k)=-2x^(k)ᵀb。*再看β^kA(p^(k-1)ᵀp^(k))：*β^k=[6x^(k)ᵀb+3bᵀp^(k)]/[-6p^(k)ᵀp^(k)+3bᵀp^(k-1)]。*A(p^(k-1)ᵀp^(k))=A(p^(k-1))ᵀp^(k)=0（因为p^(k-1)与p^(k)是A-共轭的）。*所以β^kA(p^(k-1)ᵀp^(k))=0。*最终A(x^(k+1))ᵀx^(k)=-2x^(k)ᵀb。*要证明x^(k)与x^(k+1)是A-共轭的，即要证明A(x^(k+1))ᵀx^(k)=0。*我们发现A(x^(k+1))ᵀx^(k)=-2x^(k)ᵀb。这与A(x^(k+1))ᵀx^(k)=0矛盾。*修正思路/检查：可能是在推导β^k时对β^k=(∇f(x^(k))ᵀ∇f(x^(k+1)))/(∇f(x^(k-1))ᵀ∇f(x^(k-1)))的应用有误，或者对p^(k)=-∇f(x^(k))+β^kp^(k-1)与∇f(x)=2Ax+b的结合有误。*重新审视β^k的推导：*β^k=(∇f(x^(k))ᵀ∇f(x^(k+1)))/(∇f(x^(k-1))ᵀ∇f(x^(k-1)))=(2Ax^(k)+b)ᵀ(2Ax^(k+1)+b)/(2Ax^(k-1)+b)ᵀ(2Ax^(k-1)+b)。*β^k=(4(Ax^(k))ᵀAx^(k)+2(Ax^(k))ᵀp^(k)+2bᵀx^(k)+bᵀp^(k))/(4(Ax^(k-1))ᵀAx^(k-1)+2(Ax^(k-1))ᵀp^(k-1)+2bᵀx^(k-1)+bᵀp^(k-1))。*β^k=(4x^(k)ᵀb+2(Ax^(k))ᵀp^(k)+2x^(k)ᵀb+bᵀp^(k))/(4x^(k-1)ᵀb+2(Ax^(k-1))ᵀp^(k-1)+2x^(k-1)ᵀb+bᵀp^(k-1))。*β^k=(6x^(k)ᵀb+2(Ax^(k))ᵀp^(k)+bᵀp^(k))/(6x^(k-1)ᵀb+2(Ax^(k-1))ᵀp^(k-1)+bᵀp^(k-1))。*β^k=[6x^(k)ᵀb+3bᵀp^(k)]/[6x^(k-1)ᵀb+3bᵀp^(k-1)]。*计算A(x^(k+1))ᵀx^(k)：*A(x^(k+1))ᵀx^(k)=A((x^(k)+p^(k))ᵀx^(k))=A(x^(k)ᵀx^(k)+p^(k)ᵀx^(k))=A(x^(k)ᵀx^(k))+A(p^(k)ᵀx^(k))。*A(x^(k)ᵀx^(k))=x^(k)ᵀAx^(k)=x^(k)ᵀb。*A(p^(k)ᵀx^(k))=A(p^(k)ᵀ(x^(k)+p^(k)))=A(p^(k)ᵀx^(k))+A(p^(k)ᵀp^(k))。*A(p^(k)ᵀx^(k))=A(p^(k)ᵀx^(k))（因为A(p^(k)ᵀp^(k))=0，因为p^(k)与p^(k-1)是A-共轭的，所以p^(k)ᵀAp^(k)=0）。*所以A(p^(k)ᵀx^(k))=A(p^(k)ᵀx^(k))=0。*因此，A(x^(k+1))ᵀx^(k)=x^(k)ᵀb+0=x^(k)ᵀb。*计算β^kA(p^(k-1)ᵀx^(k))：*A(p^(k-1)ᵀx^(k))=A(p^(k-1)ᵀ(x^(k)+p^(k)))=A(p^(k-1)ᵀx^(k))+A(p^(k-1)ᵀp^(k))。*A(p^(k-1)ᵀx^(k))=A(p^(k-1)ᵀ(x^(k)+p^(k)))=A(p^(k-1)ᵀx^(k))+A(p^(k-1)ᵀp^(k)。*A(p^(k-1)ᵀp^(k))=p^(k)ᵀAp^(k-1)=0（因为p^(k)与p^(k-1)是A-共轭的）。*所以A(p^(k-1)ᵀx^(k))=A(p^(k-1)ᵀx^(k))。*β^k=[6x^(k)ᵀb+3bᵀp^(k)]/[6x^(k-1)ᵀb+3bᵀp^(k-1))。*β^kA(p^(k-1)ᵀx^(k))=β^k[A(p^(k-1)ᵀx^(k))]=β^k[A(p