HUST-SE最优化作业

HUST-SE数学建模与最优化-最优化作业-选题F（外点法，内点法，乘子法求解约束最优化问题）

外点法

原理

外点法将约束优化问题转化为一系列的无约束优化问题，通过构造带有惩罚项的目标函数逐步逼近最优解。

• 目标函数构造： 对于目标函数 $f(x)$ 和约束条件 $g_i(x)≤0,h_j(x)=0$，构造惩罚函数：

$$
F(x,μ)= f(x) + \mu \left( \sum_{i=1}^{l} \max(0, g_i(x))^2 + \sum_{j=1}^{m} h_j(x)^2 \right)
$$

其中，$\mu>0$ 是惩罚因子。

• 惩罚项的作用：
  • 当 $x$ 满足约束条件时，惩罚项为 0。
  • 当 $x$ 不满足约束条件时，惩罚项随 $\mu$ 增大加剧目标函数的值，逼迫 $x$ 回到可行域。
• 迭代步骤：
  1. 初始化 $\mu$ 和 $x$。
  2. 求解无约束问题 $\min F(x, \mu)$。
  3. 若约束条件近似满足（误差 $\epsilon$ 内），停止迭代；否则增大 $\mu$，重复步骤 2。

优缺点：

• 优点：通用性强，可解决一般约束问题。
• 缺点：惩罚因子的增大可能导致数值不稳定，Hesse 矩阵病态。

算例描述

$$
min f(x) = \frac {x_1^2} 2 + \frac{x_2^2}6
$$

$$
s.t. x_1+x_2−1=0
$$

解答

import numpy as np
from scipy.optimize import minimize

# 目标函数
def objective(x):
    return x[0]**2 / 2 + x[1]**2 / 6

# 惩罚函数
def penalty_function(x, mu):
    constraint = x[0] + x[1] - 1
    return objective(x) + mu * constraint**2

mu = 1  
tolerance = 1e-6
x_init = [0.0, 0.0] 
x = x_init

while True:
    result = minimize(lambda x: penalty_function(x, mu), x)
    x_new = result.x
    
    # 检查是否满足约束条件
    constraint_value = x_new[0] + x_new[1] - 1
    if abs(constraint_value) < tolerance:
        break
    
    # 增大惩罚因子
    mu *= 10
    x = x_new

print("Optimal solution:", x_new)
print("Objective value:", objective(x_new))

求解得到

Optimal solution: [0.25001243 0.74998744]
Objective value: 0.12499996699040285

内点法

原理

内点法从可行域的内部出发，通过构造障碍函数（Barrier Function）避免迭代点越出可行域。

• 目标函数构造： 对于目标函数 $f(x)$ 和约束$g_i(x) \leq 0$，构造障碍函数：
  $$
  B(x, r) = f(x) - r \sum_{i=1}^{l} \ln(-g_i(x))
  $$
  其中，$r > 0$ 为障碍因子。

• 障碍项的作用：

  • 当 $x$ 接近约束边界 $g_i(x) = 0$ 时，障碍项趋于无穷大，阻止迭代点越界。
  • 当 $x$ 远离约束边界时，障碍项的影响较小。

• 迭代步骤：

  1. 初始化 $r$ 和 $x$。
  2. 求解无约束问题 $\min B(x, r)$。
  3. 若解的精度满足要求，停止迭代；否则减小 $r$，重复步骤 2。

优缺点：

• 优点：始终在可行域内迭代，适用于非线性不等式约束问题。
• 缺点：只适用于不等式约束，且初始点必须在可行域内。

算例描述

$$
min f(x) = {x_1} + {x_2}
$$

$$
s.t. x_1^2+x_2^2−4 \le 0
$$

解答

import numpy as np
from scipy.optimize import minimize

def barrier_function(x, r):
    if x[0]**2 + x[1]**2 >= 4:
        return np.inf
    return x[0] + x[1] - r * np.log(4 - (x[0]**2 + x[1]**2))

r = 1.0  
tolerance = 1e-6
x_init = [0.5, 0.5] 
x = x_init

while True:
    result = minimize(lambda x: barrier_function(x, r), x, method="BFGS")
    x_new = result.x
    
    # 检查终止条件
    if r * (4 - (x_new[0]**2 + x_new[1]**2)) < tolerance:
        break
    
    # 减小障碍因子
    r *= 0.1
    x = x_new

print("Optimal solution:", x_new)
print("Objective value:", x_new[0] + x_new[1])

求解得到

Optimal solution: [-1.41416357 -1.41416357]
Objective value: -2.8283271340951304

乘子法

原理

乘子法结合拉格朗日乘子法和惩罚函数法的优点，通过引入拉格朗日乘子修正惩罚函数，避免惩罚因子过大导致的数值问题。

• 目标函数构造： 对于目标函数 $f(x)$ 和约束 $h_j(x) = 0$，构造增广拉格朗日函数：

  $$
  F(x, \lambda, \mu) = f(x) + \sum_{j=1}^{m} \lambda_j h_j(x) + \frac{\mu}{2} \sum_{j=1}^{m} h_j^2(x)
  $$
  其中，$\lambda$ 为拉格朗日乘子，$\mu > 0$ 为惩罚因子。

• 思想：

  • $\lambda$ 的更新调整约束的权重，逐步逼近精确的拉格朗日乘子。
  • $\mu$ 保持适度即可，不必趋向无穷大。

• 迭代步骤：

  1. 初始化 $\lambda$、$\mu$ 和 $x$。
  2. 求解无约束问题 $\min F(x, \lambda, \mu)$。
  3. 更新拉格朗日乘子$\lambda_{k+1} = \lambda_k + \mu h(x_k)$。
  4. 若约束条件满足精度要求，停止迭代；否则重复步骤 2。

优缺点：

• 优点：避免了外点法中过大的惩罚因子带来的病态问题，数值稳定性好。
• 缺点：实现较为复杂，需联合优化目标变量和拉格朗日乘子。

算例描述

$$
min f(x) = \frac {x_1^2} 2 + \frac{x_2^2}6
$$

$$
s.t. x_1+x_2−1=0
$$

解答

from scipy.optimize import minimize

def augmented_lagrangian(x, lmbda, mu):
    constraint = x[0] + x[1] - 1
    lagrangian = x[0]**2 / 2 + x[1]**2 / 6 + lmbda * constraint + (mu / 2) * constraint**2
    return lagrangian

lmbda = 0  # 拉格朗日乘子
mu = 1     # 惩罚因子
tolerance = 1e-6
x_init = [0.0, 0.0]
x = x_init

while True:
    result = minimize(lambda x: augmented_lagrangian(x, lmbda, mu), x)
    x_new = result.x
    
    # 更新拉格朗日乘子
    constraint_value = x_new[0] + x_new[1] - 1
    if abs(constraint_value) < tolerance:
        break
    lmbda += mu * constraint_value
    x = x_new

print("Optimal solution:", x_new)
print("Objective value:", x_new[0]**2 / 2 + x_new[1]**2 / 6)

求解得到

Optimal solution: [0.25000199 0.749998  ]
Objective value: 0.12499999758157486

这里求解出来的结果与外点法求解出的结果误差很小。可以验证两种方法求解结果的正确性。

总结

在本次最优化作业中，我探讨了三种最优化方法：外点法、内点法和乘子法，并通过对特定算例的应用，深入理解了每种方法的原理和实现过程。

外点法通过引入惩罚项将约束问题转化为无约束问题，其通用性强，但需注意惩罚因子的选择以避免数值不稳定。内点法则通过障碍函数保持迭代点在可行域内，适用于不等式约束问题，但要求初始点必须在可行域内。乘子法结合了拉格朗日乘子法和惩罚函数法，通过引入拉格朗日乘子修正惩罚函数，提高了数值稳定性，但实现相对复杂。

通过编程求解，我得到了每种方法的最优解，验证了理论的正确性。这些方法各有优势和局限，选择时需根据具体问题的性质和要求来定。通过本次作业，我不仅掌握了最优化算法的理论知识，也提升了解决实际最优化问题的能力。