2025年大学《数理基础科学》专业题库- 数学最优化理论与方法

2025年大学《数理基础科学》专业题库——数学最优化理论与方法考试时间：______分钟总分：______分姓名：______一、1.设非线性规划问题minf(x)=x₁²+2x₂²-4x₁-4x₁x₂+2x₂s.t.g₁(x)=x₁+x₂-3≤0g₂(x)=-x₁+x₂-1≤0g₃(x)=x₁≥0g₄(x)=x₂≥0其中x∈ℝ²。写出该问题的KKT条件。2.某无约束优化问题使用牛顿法进行求解，其Hessian矩阵为正定。若在某次迭代中，搜索方向p_k满足B_kp_k=-∇f(x_k)，其中B_k是Hessian矩阵在x_k处的近似。请写出该近似所对应的牛顿方向q_k的表达式，并简述该近似方法可能的理论依据。二、1.考虑线性规划问题maxz=3x₁+5x₂s.t.x₁+x₂≤42x₁+x₂≤5x₁,x₂≥0使用单纯形法求解该问题。请完整写出迭代过程，包括初始表格、每一步的基变量选择、旋转运算以及最终结果（最优解、最优值）。在表格运算中，仅要求列出关键步骤和最终结果，无需展示所有中间计算。2.已知线性规划问题maxz=cᵀxs.t.Ax≤bx≥0的最优解为x*，最优单纯形基为B。其对偶问题是minw=bᵀys.t.Aᵀy≥cy≥0请写出对偶问题的最优解y*，并说明理由（依据对偶理论）。三、1.设函数f(x)=x³-3x+1在区间[-2,2]上定义。请找出f(x)在该区间上的所有局部最优解（包括局部最小值点和局部最大值点），并判断其是最小值点还是最大值点。仅要求列出求解过程的关键步骤和结论。2.在使用梯度法求解无约束优化问题时，如何确定步长参数α_k？请简述两种常用的线搜索策略（如精确线搜索、黄金分割法或Armijo条件）的基本思想。3.考虑约束优化问题minf(x)=x₁²+x₂²s.t.h(x)=x₁+x₂-1=0使用拉格朗日乘子法求解。请写出拉格朗日函数，并推导最优性条件（KKT条件的一个特例）。若进一步假设f和h在所考虑的区域上都是二阶连续可微的，请补充推导二阶最优性条件。四、1.简述整数规划与线性规划的主要区别，并举例说明为什么某些优化问题需要引入整数约束。2.动态规划适用于求解哪些类型的最优化问题？请简述动态规划的基本思想（包括状态定义、状态转移方程、基本方程和边界条件）。3.在实际应用中，如何判断一个无约束优化问题的目标函数可能存在多个局部最优解？当算法陷入局部最优解时，可以采取哪些策略来尝试寻找更好的全局最优解？请简述其中两种策略的基本思想。试卷答案一、1.KKT条件：(i)∇f(x)+∑ᵢλᵢ∇gᵢ(x)=0(ii)λᵢ≥0,gᵢ(x)≤0(对于所有i)(iii)λᵢ*gᵢ(x)=0(对于所有i)其中，∇f(x)=[2-4-2x₂,4-4x₁]ᵀ,∇g₁(x)=[1,1]ᵀ,∇g₂(x)=[-1,1]ᵀ,∇g₃(x)=[1,0]ᵀ,∇g₄(x)=[0,1]ᵀ。2.由B_kp_k=-∇f(x_k)和牛顿法方向定义q_k=-[∇f(x_k)+∇²f(x_k)δ_k]，其中δ_k是沿方向p_k的步长。若令δ_k=1，则q_k=-[∇f(x_k)+B_kp_k]。代入B_kp_k=-∇f(x_k)，得q_k=0。这表明该近似导致牛顿法方向为零，通常是因为B_k不再是对Hessian矩阵的良好近似。该近似可能的理论依据是认为在牛顿法迭代的当前点x_k附近，函数f(x)可以较好地用其二次部分近似，即f(x_k+δ_kp_k)≈f(x_k)+∇f(x_k)ᵀδ_kp_k+1/2δ_kᵀB_kδ_k。如果B_k是Hessian矩阵的某个近似（如B_k=∇²f(x_k)+E_k，E_k为误差），则q_k=-[∇f(x_k)+(∇²f(x_k)+E_k)p_k]=-(∇²f(x_k)p_k+E_kp_k)。若B_kp_k=-∇f(x_k)，则q_k=-E_kp_k。选择B_k使得q_k具有有利的收敛性性质，例如下降性或线搜索步长容易确定。二、1.单纯形法求解过程：初始基本可行解：x=(0,0)ᵀ,z=0。基变量x₁,x₂=0。初始表格：|基变量|x₁|x₂|s₁|s₂|RHS||-------|----|----|----|----|-----||z|-3|-5|0|0|0||s₁|1|1|1|0|4||s₂|2|1|0|1|5|检验行：z-row=[-3,-5,0,0]ᵀ。检验数-5<-3，选择x₂入基。最小比：4/1=4,5/1=5。选择s₁出基。旋转运算（以x₂行和z-row为主元）：新x₂行：[1,1,1,0,4]→[1,1,1,0,4](除主元外不变)新z-row：[-3,-5,0,0,0]+5*(新x₂行)=[-3,0,5,0,20]新s₁行：[1,1,1,0,4]→[0,0,1,-1,0](新s₁=s₁-x₂)新s₂行：[2,1,0,1,5]→[0,-1,0,1,1](新s₂=s₂-x₂)新表格：|基变量|x₁|x₂|s₁|s₂|RHS||-------|----|----|----|----|-----||z|-3|0|5|0|20||x₂|0|1|1|0|4||s₁|0|0|1|-1|0||s₂|0|-1|0|1|1|检验行：z-row=[-3,0,5,0]ᵀ。检验数-3<0。所有检验数≤0，达到最优。最优解：x₁=0,x₂=4。最优值：z=20。2.对偶问题的最优解y*为原问题最优解x*在其对偶变量处的值。即y*ᵢ=cᵢ*x*ᵢ(对于所有i)。依据强对偶定理，若原问题有最优解x*，则其对偶问题也有最优解y*，且二者目标函数值相等。若原问题的最优单纯形基为B，则对偶问题的最优解y*=(c_BᵀB⁻¹b,c_NᵀB⁻¹A_N)ᵀ，其中c_B,c_N分别是对应基变量和非基变量的系数向量，A_B,A_N是矩阵A按B和非基变量分块得到的子矩阵。当原问题采用单纯形法迭代到最终阶段，最优解为x*，最优基为B时，此时x*_B=B⁻¹b(基变量取值为B⁻¹乘以右侧向量)，x*_N=0(非基变量取值为0)。将x*代入KKT条件∇f(x*)ᵀ+∑ᵢλᵢ∇gᵢ(x*)ᵀ=0，即cᵀ+Aᵀy*=0。若原问题最终形式为z=c_Bx*_B+c_Nx*_N=c_B(B⁻¹b)+0=c_BᵀB⁻¹b，则c_BᵀB⁻¹b=z*。结合c_B=cᵀ，得z*=cᵀB⁻¹b=c_BᵀB⁻¹b。由强对偶定理z*=w*，其中w*=bᵀy*。因此bᵀy*=c_BᵀB⁻¹b。若原问题最优解为x*，且x*的基变量部分为x*_B=B⁻¹b，则对偶问题的最优解y*应满足y*_B=c_BᵀB⁻¹。即y*=(c_BᵀB⁻¹,c_NᵀB⁻¹A_N)ᵀ。当原问题最终解为x*，最优基为B时，x*_B=B⁻¹b，所以y*_B=c_BᵀB⁻¹=c_Bᵀ(B⁻¹b)=c_Bᵀx*_B=cᵀx*_B=cᵢ*x*ᵢ(仅对基变量i成立)。对于非基变量i∈N，gᵢ(x*)=0，λᵢ=0，KKT条件自动满足。所以y*ᵢ=cᵢ*x*ᵢ(对所有i)。三、1.求局部最优解：求导：f'(x)=3x²-3。令f'(x)=0，得x=±1。求二阶导：f''(x)=6x。在x=1处，f''(1)=6>0，为局部最小值点。在x=-1处，f''(-1)=-6<0，为局部最大值点。检查边界：f(-2)=-5,f(2)=5。结论：局部最小值点为x=1，最小值f(1)=-1；局部最大值点为x=-1，最大值f(-1)=3。全局最小值为f(1)=-1，全局最大值为f(2)=5。2.线搜索策略：(a)精确线搜索：寻找步长α_k使得f(x_k+α_kp_k)达到在方向p_k上f(x_k)的最小值，即α_k=argmin_αf(x_k+αp_k)。这通常需要解决一个一维优化问题，计算量可能较大。(b)黄金分割法（或Armijo条件）：不直接寻找精确步长，而是采用一种启发式方法。黄金分割法保持两个搜索区间，在每步迭代中根据黄金比例缩减其中一个区间，直到区间足够小，认为其内点即为步长α_k的近似值。Armijo条件（或称为精确线搜索的弱形式）则通过选择步长α_k满足f(x_k+α_kp_k)≤f(x_k)+c*α_k*∇f(x_k)ᵀp_k(其中0<c<1)，即保证搜索方向是下降的，且下降量至少为某个固定比例。这种策略计算量相对较小。3.拉格朗日乘子法：拉格朗日函数：L(x,λ)=f(x)+λ(h(x))其中x∈ℝⁿ,λ∈ℝ(或λ∈ℝₘ,若h(x)是向量)。最优性条件：∇L(x_k,λ_k)=∇f(x_k)+λ_k∇h(x_k)=0对应KKT条件中的∇f(x)+∑ᵢλᵢ∇gᵢ(x)=0，这里∇h(x_k)=∇g₁(x_k)。对于等式约束h(x)=0，KKT条件还包括互补松弛条件gᵢ(x)≤0,λᵢ*gᵢ(x)=0，这里变为h(x)=0(总是成立)和λ*h(x)=0。后者在最优解处自动满足（因为h(x)=0），故KKT条件简化为∇f(x)+λ∇h(x)=0和h(x)=0。若f和h在所考虑区域上二阶连续可微，则二阶最优性条件要求Hessian矩阵∇²L(x_k,λ_k)在x_k处正定（对于无约束部分，或在该点沿可行方向的正定性分析），且满足∇²f(x_k)+λ_k∇²h(x_k)是半负定的。这通常需要更复杂的条件。四、1.整数规划与线性规划的区别：主要区别在于对变量的取值限制。线性规划(LP)要求所有变量取连续值（通常在实数域内），而整数规划(IP)要求至少部分或全部变量取整数值（通常是0或1，或某个整数范围）。LP求解后得到的解可能是非整数，而IP求解得到的最优解（对于整数规划）必须是整数。由于整数约束的引入，IP通常比LP更难求解，其可行域更小，可能存在多个最优解（整数最优解可能不同于LP最优解）。例子：LP问题maxz=x₁+5x₂s.t.2x₁+x₂≤10,x₁+3x₂≤15,x₁,x₂≥0。最优解可能为x₁=4.8,x₂=2.4,z=28.8。若增加x₁,x₂必须为整数，则最优整数解可能为x₁=5,x₂=2,z=25，或x₁=4,x₂=3,z=23。2.动态规划适用类型与思想：动态规划适用于具有“最优子结构”和“重叠子问题”特征的最优化问题，通常用于解决多阶段决策问题或序列决策问题。基本思想：(a)状态定义：将复杂问题分解为一系列关联的子问题，定义合适的状态变量（S）来表示在某个阶段（或决策点）所达到的状态。(b)状态转移方程：描述从一个状态到下一个状态的过程，即如何根据当前状态和决策选择来得到下一个状态。形式为：S(k+1)=T(S(k),a(k))，其中k是阶段索引，a(k)是第k阶段的决策。(c)基本方程（递归关系）：基于最优子结构性质，将问题的最优解值表示为其子问题的最优解值（通常是递归地）的组合。对于最短路径或最小成本问题，形式常为：Opt(S_k)=min/min/max{a(k)*Cost(S_k,a(k))+Opt(S_{k+1})}，其中O