25-26-2-最优化理论与算法-期末（A卷）

一、（30分）

考虑下述线性规划

min⁡3x1−2x2+x3\min \quad 3x_1 - 2x_2 + x_3 s.t.3x1+x2+x3≤6x1−x2+2x3≥1−2≤x1≤2x2≥0, x3≥0\begin{aligned} \text{s.t.} \quad &3x_1 + x_2 + x_3 \leq 6 \\ &x_1 - x_2 + 2x_3 \geq 1 \\ &-2 \leq x_1 \leq 2 \\ &x_2 \geq 0,\ x_3 \geq 0 \end{aligned}
  1. 用单纯形方法对其进行求解；
  2. 写出该问题的对偶规划，写出互补松弛条件。
  3. 若目标函数中 x1x_1 的系数由 c1=3c_1 = 3 改为 11，原来的最优解还是新问题的最优解吗？

二、（10分）

下述线性规划问题是以极小化为目标，其初始和最优的单纯形表如下所示：

初始单纯形表：

基 Bx1x_1x2x_2x3x_3x4x_4x5x_5b
x4x_4111122110066
x5x_51144−1-1001144
zi−ciz_i - c_i22−1-111000000

最优单纯形表：

基 Bx1x_1x2x_2x3x_3x4x_4x5x_5b
x3x_300−1-1111/31/3−1/3-1/32/32/3
x1x_11133001/31/32/32/314/314/3
zi−ciz_i - c_i00−6-600−1/3-1/3−5/3-5/3−26/3-26/3

现向该线性规划加入新的约束 x1−x2+x3≤1x_1 - x_2 + x_3 \leq 1，原来的最优解还是最优解吗？如不是，请给出新的最优解。

三、（10分）

证明：若线性规划

min⁡cTxAx=bx≥0\begin{aligned} \min \quad &c^T x \\ &Ax = b \\ &x \geq 0 \end{aligned}

无界，则存在向量 yy，使得 （1） cTy<0c^T y < 0，（2） 如果 xx 是可行解，则对任意的正数 kk，x+kyx+ky 也是可行解。

四、（20分）

用共轭梯度法求解下述无约束优化。

min⁡f(x)=x12+2x22+x32−x1x2+x2+x3\min \quad f(x) = x_1^2 + 2x_2^2 + x_3^2 - x_1x_2 + x_2 + x_3

取初始点 x(0)=(2,1,0)Tx^{(0)} = (2,1,0)^T。

五、（15分）

考虑等式约束优化问题

min⁡f(x)=−x1x2x3s.t.x1+2x2+3x3=60\begin{aligned} \min \quad &f(x) = -x_1x_2x_3 \\ \text{s.t.} \quad &x_1 + 2x_2 + 3x_3 = 60 \end{aligned}

使用二次罚函数求解该问题，当固定罚因子 μk\mu_k 时，写出二次罚函数 F(x,μk)F(x, \mu_k) 的最优解 xk+1x^{k+1}，当 μk→+∞\mu_k \to +\infty 时，写出该优化问题的解。当罚因子 μ\mu 满足什么条件时，二次罚函数的海瑟矩阵 ∇xx2F(x,μ)\nabla^2_{xx} F(x, \mu) 是正定的？

六、（15分）

考虑非线性规划问题

min⁡(x1−3)2+(x2−3)2s.t.2−2x1−x2≥0x1≥0x2≥0\begin{aligned} \min \quad &(x_1 - 3)^2 + (x_2 - 3)^2 \\ \text{s.t.} \quad &2 - 2x_1 - x_2 \geq 0 \\ &x_1 \geq 0 \\ &x_2 \geq 0 \end{aligned}
  1. 找出所有满足 KKT 条件的可行点，判定该点是否为局部极小点，全局极小点；
  2. 写出上述非线性规划的对偶规划，满足强对偶吗？