非线性规划中的序列仿射尺度法进阶题 题目描述： 考虑一个非线性规划问题，其中目标函数是凸的，约束为线性等式和不等式。要求使用序列仿射尺度法求解。具体问题如下： 最小化：f(x) = (x₁ - 2)⁴ + (x₁ - 2x₂)² 约束条件： x₁ + x₂ ≤ 3 x₁ - x₂ ≤ 1 x₁, x₂ ≥ 0 我们将通过序列仿射尺度法，从一个内点初始解开始，逐步迭代求解此问题。 解题过程： 问题理解与初始化 目标函数 f(x) 是非线性凸函数。约束是线性的，包括两个不等式和两个变量非负约束。序列仿射尺度法的核心思想是：在当前点构造一个仿射尺度变换，将原问题转化为一个等价形式，然后求解一个线性或二次子问题来得到搜索方向，再沿该方向进行线搜索得到新迭代点，并重复此过程。 首先，将不等式约束转化为标准形式（≤形式）： g₁(x) = x₁ + x₂ - 3 ≤ 0 g₂(x) = x₁ - x₂ - 1 ≤ 0 x₁ ≥ 0, x₂ ≥ 0 可视为 -x₁ ≤ 0, -x₂ ≤ 0。 我们需要一个严格内点作为初始点，即满足所有不等式严格成立的点。例如，选 x⁰ = (1, 0.5)，验证： g₁(1,0.5)=1+0.5-3=-1.5<0, g₂(1,0.5)=1-0.5-1=-0.5 <0, x₁>0, x₂>0 ✅。 构造仿射尺度变换 在序列仿射尺度法中，我们利用当前点 xᵏ 到约束边界的距离来缩放变量，以“拉开”与边界的距离，从而更容易在变换空间内移动。具体来说，定义缩放矩阵 Dᵏ： Dᵏ = diag(d₁, d₂)，其中 dᵢ = 1 / sᵢᵏ，sᵢᵏ 是第 i 个不等式约束的松弛变量（或对变量边界，是 xᵢ 本身）。 首先引入松弛变量将不等式转为等式。对 g₁ 和 g₂，引入松弛变量 s₁, s₂ ≥ 0： x₁ + x₂ + s₁ = 3, s₁ = 3 - x₁ - x₂ x₁ - x₂ + s₂ = 1, s₂ = 1 - x₁ + x₂ 对 x₁ ≥ 0, x₂ ≥ 0，本身是变量边界，无需额外松弛变量，但可视为松弛变量就是 x₁ 和 x₂。 在当前点 xᵏ，计算松弛变量值： s₁ᵏ = 3 - x₁ᵏ - x₂ᵏ s₂ᵏ = 1 - x₁ᵏ + x₂ᵏ 以及变量下界的“松弛”：x₁ᵏ, x₂ᵏ 本身。 定义缩放向量 dᵏ： d₁ˣ = 1 / x₁ᵏ, d₂ˣ = 1 / x₂ᵏ （对应变量下界约束） d₁ˢ = 1 / s₁ᵏ, d₂ˢ = 1 / s₂ᵏ （对应不等式约束 g₁, g₂） 但通常，序列仿射尺度法主要对变量边界（x ≥ 0）进行缩放，对一般不等式约束可能通过障碍函数或将其转为等式处理。这里我们聚焦于对变量非负约束的仿射尺度变换，这是经典方法。 更简单的实现：我们只对 x ≥ 0 进行仿射缩放。定义变换矩阵 Dᵏ = diag(1/x₁ᵏ, 1/x₂ᵏ) 的逆？实际上，常用 Dᵏ = diag(x₁ᵏ, x₂ᵏ) 将 x 变换为 y = (Dᵏ)⁻¹ x，使 y 在当前点对应全1向量。但为了避免混淆，我们按如下步骤： 定义新变量 y，满足 x = Xᵏ y，其中 Xᵏ = diag(x₁ᵏ, x₂ᵏ)。则 yᵢ = xᵢ / xᵢᵏ，所以在当前点 yᵏ = (1,1)ᵀ。此变换将当前点映射到全1向量，且将非负象限映射到自身。 构建线性化子问题 在变换空间（y空间）中，原问题变为： 最小化 f(Xᵏ y) 约束条件：A Xᵏ y ≤ b，其中 A = [ [ 1,1],[ 1,-1]], b = [ 3,1 ]ᵀ，且 y ≥ 0。 但序列仿射尺度法通常在该变换空间求解一个线性近似子问题。常用方法是：在当前点 yᵏ = (1,1)ᵀ，对目标函数进行线性近似： f(Xᵏ y) ≈ f(xᵏ) + ∇f(xᵏ)ᵀ Xᵏ (y - 1) 其中 ∇f(x) 是 f 在 x 处的梯度。 计算 ∇f(x)： ∂f/∂x₁ = 4(x₁-2)³ + 2(x₁-2x₂) ∂f/∂x₂ = -4(x₁-2x₂) 在 x⁰=(1,0.5)： ∇f(x⁰) = [ 4(1-2)³+2(1-1), -4(1-1)] = [ 4* (-1)+0, 0] = [ -4, 0 ]ᵀ。 所以线性化目标为：cᵀ y，其中 c = Xᵏ ∇f(xᵏ) = diag(x₁⁰,x₂⁰) ∇f(x⁰) = diag(1,0.5) * [ -4,0]ᵀ = [ -4, 0 ]ᵀ。 约束在 y 空间为：A Xᵏ y ≤ b，即： [ 1,1 ] diag(1,0.5) y = y₁ + 0.5 y₂ ≤ 3 [ 1,-1 ] diag(1,0.5) y = y₁ - 0.5 y₂ ≤ 1 且 y ≥ 0。 求解线性子问题 线性子问题为： 最小化 cᵀ y = -4 y₁ 约束于： y₁ + 0.5 y₂ ≤ 3 y₁ - 0.5 y₂ ≤ 1 y₁ ≥ 0, y₂ ≥ 0 由于目标函数系数 c₁ = -4（负），c₂=0，所以最小化 -4y₁ 等价于最大化 y₁。但约束限制了 y₁ 的最大值。从约束看： 从第一个约束：y₁ ≤ 3 - 0.5 y₂，y₂ ≥ 0 ⇒ y₁ ≤ 3。 从第二个约束：y₁ ≤ 1 + 0.5 y₂，y₂ ≥ 0 ⇒ y₁ 可大于1，但结合第一个约束，最大 y₁ 出现在 y₂ 尽可能小，即 y₂=0 时，则 y₁ ≤ min(3, 1) = 1。所以线性子问题的最优解为 y* = (1, 0)ᵀ，此时目标值 -4。 但注意，y* 在 y₂=0 处，对应 x₂ = x₂⁰ * y₂ = 0.5 0=0，将触及边界 x₂=0。序列仿射尺度法通常不会让迭代点直接到达边界，而是保持严格内点。所以我们不直接取 y 作为下一步，而是将其作为搜索方向。 计算搜索方向并线搜索 在 y 空间，从当前点 yᵏ=(1,1) 到最优解 y* =(1,0) 的方向是 dʸ = y* - yᵏ = (0, -1)ᵀ。将其变换回 x 空间： dˣ = Xᵏ dʸ = diag(1,0.5) * (0, -1)ᵀ = (0, -0.5)ᵀ。 所以搜索方向是 dˣ = (0, -0.5)ᵀ。沿着此方向，从 x⁰ 出发，新点 x⁺ = x⁰ + α dˣ = (1, 0.5) + α (0, -0.5) = (1, 0.5 - 0.5α)，其中 α 是步长，0 <α≤1。 我们需要选择 α 使得新点仍在严格内点（即所有松弛变量>0）。计算： s₁(α) = 3 - x₁⁺ - x₂⁺ = 3 - 1 - (0.5-0.5α) = 1.5 + 0.5α > 0 恒成立（α>0） s₂(α) = 1 - x₁⁺ + x₂⁺ = 1 - 1 + (0.5-0.5α) = 0.5(1-α) > 0 ⇒ α < 1 x₂⁺ = 0.5(1-α) > 0 ⇒ α < 1 所以 α 最大可取到略小于1，比如 α=0.9。 我们还需要确保目标函数下降。计算 f(x⁺) 在 α=0.9 时： x⁺ = (1, 0.5-0.45) = (1, 0.05) f(x⁺) = (1-2)⁴ + (1-0.1)² = 1 + 0.81 = 1.81 而 f(x⁰)= (1-2)⁴+(1-1)² = 1+0=1，所以 f 反而增加了。这说明纯线性化子问题的方向可能不是下降方向，或我们需要更精确的线搜索。 实际上，序列仿射尺度法通常结合一个势函数或障碍函数来确保内点性和下降。经典的内点法使用对数障碍函数。但序列仿射尺度法也可在子问题中加入一个对变量接近边界的惩罚，比如在目标中加入 -μ ∑ log(yᵢ)，然后线性化。这里我们简化，使用一个更实际的做法：在 y 空间的线性子问题中，我们最小化 cᵀ y - μ ∑ log(yᵢ) 的线性近似？但这会引入非线性。 为避免复杂，我们回到更标准的做法：序列仿射尺度法通常用于线性规划，对于非线性规划，常与障碍函数结合。这里我们采用一个简单修正：由于线性化子问题的解在边界，我们可对其施加一个界限，比如限制 ∥y - yᵏ∥ ≤ Δ 作为信赖域约束，然后求解一个有界线性子问题。但为简化，我们直接取一个较小的步长 α=0.1 试探： x⁺ = (1, 0.5-0.05) = (1, 0.45) f(x⁺) = (-1)⁴ + (1-0.9)² = 1 + 0.01 = 1.01 > f(x⁰)=1 仍上升。这表示方向 dˣ 不是下降方向？计算梯度与方向点积： ∇f(x⁰)ᵀ dˣ = [ -4,0]·[ 0,-0.5 ] = 0，所以方向与梯度正交，理论上沿该方向一阶变化为0。但由于函数非线性，可能上升或下降。我们计算二阶信息：dˣ 是沿 x₂ 减少方向，而 f 对 x₂ 的二阶偏导？∂²f/∂x₂² = 8 >0，所以沿 x₂ 方向是凸的，减少 x₂ 可能增加 f。因此这个方向不好。 修正子问题 经典序列仿射尺度法用于线性规划时，子问题最优解在边界，但通过势函数确保下降。对于非线性规划，更好的做法是求解一个二次近似子问题。例如，在 y 空间用二次近似： f(Xᵏ y) ≈ f(xᵏ) + ∇f(xᵏ)ᵀ Xᵏ (y-1) + ½ (y-1)ᵀ Xᵏ ∇²f(xᵏ) Xᵏ (y-1) 其中 ∇²f 是 Hessian 矩阵。 计算 ∇²f(x)： ∂²f/∂x₁² = 12(x₁-2)² + 2 ∂²f/∂x₁∂x₂ = -4 ∂²f/∂x₂² = 8 在 x⁰=(1,0.5)： ∇²f(x⁰) = [ [ 12(1-2)²+2, -4],[ -4,8]] = [ [ 12* 1+2, -4],[ -4,8]] = [ [ 14, -4],[ -4,8] ]。 在 y 空间，Hessian 的变换为 Hʸ = Xᵏ ∇²f(xᵏ) Xᵏ = diag(1,0.5) [ [ 14,-4],[ -4,8]] diag(1,0.5) = [ [ 14, -4 0.5],[ -4 0.5, 8* 0.5²]] = [ [ 14, -2],[ -2, 2] ]。 二次子问题为： 最小化 cᵀ (y-1) + ½ (y-1)ᵀ Hʸ (y-1)，其中 c = [ -4,0 ]ᵀ（之前计算）。 令 z = y-1，则子问题为： 最小化 cᵀ z + ½ zᵀ Hʸ z 约束于 A Xᵏ (z+1) ≤ b 且 z+1 ≥ 0。 简化：约束等价于： (1) z₁ + 0.5 z₂ ≤ 3 - (y₁⁰+0.5 y₂⁰) = 3 - (1+0.5)=1.5 (2) z₁ - 0.5 z₂ ≤ 1 - (y₁⁰-0.5 y₂⁰) = 1 - (1-0.5)=0.5 (3) z₁ ≥ -1, z₂ ≥ -1。 这是凸二次规划（Hʸ 正定？检查：行列式=14 2-(-2) (-2)=28-4=24>0，且迹>0，所以正定），可用二次规划求解。但为手工进行，我们可忽略约束先求无约束最优解：梯度为 c + Hʸ z = 0 ⇒ Hʸ z = -c = [ 4,0 ]ᵀ。 解方程： [ [ 14, -2],[ -2, 2]] [ z₁,z₂]ᵀ = [ 4,0 ]ᵀ 由第二式：-2 z₁ + 2 z₂ = 0 ⇒ z₁ = z₂ 代入第一式：14 z₁ -2 z₁ = 12 z₁ =4 ⇒ z₁=1/3, z₂=1/3 所以无约束最优 z* =(1/3,1/3)，对应 y* = (4/3,4/3)。 检查约束： (1) 4/3 + 0.5* (4/3) = 4/3+2/3=2 ≤1.5？2>1.5 违反。 (2) 4/3 - 0.5* (4/3)=4/3-2/3=2/3 ≈0.667 >0.5 违反。 (3) y>0 满足。 所以需考虑约束。但求解此二次规划需专门算法，这里我们简化：取有约束的解为约束边界附近。由于约束(2)更紧，我们尝试在约束(2)取等号：z₁-0.5 z₂=0.5，且 z₁=z₂，则 z₁-0.5z₁=0.5⇒0.5z₁=0.5⇒z₁=1,z₂=1，对应 y=(2,2)，但此时约束(1) 2+1=3>1.5违反。考虑在约束(1)取等号：z₁+0.5z₂=1.5，z₁=z₂ ⇒ z₁+0.5z₁=1.5⇒1.5z₁=1.5⇒z₁=1,z₂=1，同样违反(2)。所以我们需在可行域内求二次规划最优，这可能需要数值求解。 为避免复杂，我们采用一个实用策略：序列仿射尺度法在非线性规划中常与障碍函数结合，即求解一个带对数障碍的近似问题。这里由于时间，我们转而采用标准的内点法思想，但保留仿射尺度变换。实际上，序列仿射尺度法可视为内点法的一种，其中缩放矩阵 Dᵏ 随迭代更新。 迭代与收敛 从初始点 x⁰ 开始，我们更新缩放矩阵并求解子问题，逐步逼近最优解。原问题的最优解可通过分析得到：目标函数 f 非负，在 (2,1) 处为0，且满足约束？检查：(2,1)：g₁=2+1-3=0, g₂=2-1-1=0, x≥0，所以 (2,1) 是全局最优解，位于两个约束的交点。 序列仿射尺度法会生成一系列内点，收敛到该点。但上述第一次迭代方向不理想，说明需要结合障碍函数或其他修正。在实际算法中，常使用如下步骤： a) 定义障碍函数 B(x) = f(x) - μ (∑ log(xᵢ) + ∑ log(sᵢ))，其中 sᵢ 是松弛变量。 b) 在当前点，对 B(x) 进行二次近似，并利用仿射尺度变换将问题转化为一个线性约束二次规划。 c) 求解该子问题得到方向。 d) 线搜索更新点，并减小 μ。 由于篇幅，这里不展开完整迭代。但核心思想是：序列仿射尺度法通过变换使当前点位于变换空间中心，从而可更好地探索内部，同时通过障碍函数避免过早触碰边界。 总结： 序列仿射尺度法是一种内点法，通过变量缩放改善问题的条件，并逐步求解近似子问题。对于非线性规划，通常与障碍函数结合，在每次迭代中求解一个二次规划子问题。本问题的最优解为 (2,1)，算法应从内点开始，通过迭代序列逼近该解。