凸优化问题

凸优化问题

小象实战讲义 · 人工智能数学基础

在人工智能模型的训练与求解过程中，优化问题无处不在。然而，并非所有优化问题都易于求解，其关键分水岭在于问题的”凸性”。本节将系统介绍凸优化问题的标准形式、核心性质及其重要性，并探讨其两个重要特例—线性规划与二次规划，帮助大家理解为何”一旦问题被表述为凸优化，就意味着它已在理论上被解决”。

💡 核心导读

• 凸优化为何重要：现实中的许多关键问题（如线性规划、二次规划）都属于凸优化范畴，且凸优化问题具有”局部最优即全局最优”的优良性质，使其求解在理论上和计算上都更为可靠。
• 标准形式与凸性要求：凸优化问题在一般约束优化问题的基础上，增加了目标函数和不等式约束函数为凸函数、等式约束函数为仿射函数的限制。
• 线性规划：目标函数与所有约束函数均为仿射函数的凸优化问题，是凸优化的一个重要子类，常用单纯形法、内点法或对偶理论求解。
• 二次规划：目标函数为凸二次型、约束函数为仿射函数的凸优化问题，最小二乘回归是其典型应用。
• 实践工具：掌握利用编程语言（如 Python）中的优化库求解一般优化问题及凸优化特例的基本方法。

1. 从一般优化问题到凸优化

1.1 有约束优化问题的标准形式

一个有约束的优化问题通常表述为以下标准形式： $$\begin{aligned} \min_{x} \quad & f_0(x) \ \text{s.t.} \quad & f_i(x) \leq 0, \quad i = 1, \ldots, m \ & h_j(x) = 0, \quad j = 1, \ldots, p \end{aligned}$$ 其中：

• $x \in \mathbb{R}^n$ 称为优化变量。
• $f_0: \mathbb{R}^n \to \mathbb{R}$ 称为目标函数或费用函数。
• $f_i(x) \leq 0$ 称为不等式约束，共有 $m$ 个。
• $h_j(x) = 0$ 称为等式约束，共有 $p$ 个。
• $\text{s.t.}$ 是 “subject to” 的缩写，意为”满足于”或”受限于”。

所有函数 $f_0, f_1, \ldots, f_m, h_1, \ldots, h_p$ 有定义的集合 $D$ 称为该优化问题的定义域。而满足所有约束条件的点 $x$ 的集合，称为可行集或约束集，记作 $\mathcal{X}$。优化问题的目标就是在可行集 $\mathcal{X}$ 中找到一个点 $x^*$，使得目标函数 $f_0(x)$ 在该点取得最小值。

注：许多实际问题都可以转化为上述标准形式。例如，若约束为 $f_i(x) \leq a$，可令 $g_i(x) = f_i(x) - a \leq 0$；若约束为 $f_i(x) \geq 0$，可等价为 $-f_i(x) \leq 0$。

1.2 凸优化问题的定义

如果一个优化问题满足以下三个附加条件，则它被称为一个凸优化问题：

1. 目标函数 $f_0(x)$ 是凸函数。
2. 所有不等式约束函数 $f_i(x)$ 是凸函数。
3. 所有等式约束函数 $h_j(x)$ 是仿射函数。

其中，仿射函数是指形如 $h(x) = Ax + b$ 的函数，即一个线性函数与一个常数的和。

因此，凸优化问题的标准形式可明确写为： $$\begin{aligned} \min_{x} \quad & f_0(x) \ \text{s.t.} \quad & f_i(x) \leq 0, \quad i = 1, \ldots, m \ & a_j^T x = b_j, \quad j = 1, \ldots, p \end{aligned}$$ 其中 $f_0, f_1, \ldots, f_m$ 均为凸函数，$a_j \in \mathbb{R}^n, b_j \in \mathbb{R}$。

1.3 凸优化的核心优势：局部最优即全局最优

凸优化问题最重要的性质之一是：任何局部最优解都是全局最优解。

对于一个可微的凸目标函数 $f_0(x)$，如果存在点 $x^$x∗ 满足一阶最优性条件 $\nabla f_0(x^$) = 0，并且 $x^$x∗ 在可行集内，那么 $x^$ 就是该凸优化问题的全局最优解。这一结论直接来自凸函数的一阶特征：对任意可行点 $y$，有 $f_0(y) \geq f_0(x^$) + \nabla f_0(x^)^T (y - x^) = f_0(x^)。这个性质极大地简化了求解过程，因为许多优化算法（如梯度下降法）容易陷入非凸问题的局部最优，但对于凸问题，只要算法能找到满足一阶最优性条件的可行点（无约束时即稳定点 $\nabla f_0(x^*) = 0$，有约束时即满足 KKT 条件的点），我们就找到了全局最优解。

下面的代码演示了一个非凸函数存在多个局部极小值的情况，以对比凸函数的优良性质。

import numpy as np
import matplotlib.pyplot as plt

# 定义一个非凸函数（Rastrigin函数的一维简化版）
def non_convex_func(x):
    return x**4 - 4*x**2 + 0.5*x

# 定义一个凸函数（简单的二次函数）
def convex_func(x):
    return (x - 2)**2 + 1

# 生成数据点
x = np.linspace(-3, 3, 400)
y_nonconvex = non_convex_func(x)
y_convex = convex_func(x)

# 绘制对比图
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))

ax1.plot(x, y_nonconvex, 'b-', linewidth=2)
ax1.set_title('非凸函数示例')
ax1.set_xlabel('x')
ax1.set_ylabel('f(x)')
ax1.grid(True, alpha=0.3)
# 标记局部极小值点（通过观察近似位置）
ax1.scatter([-1.5, 1.6], [non_convex_func(-1.5), non_convex_func(1.6)], color='red', s=80, zorder=5, label='局部极小值')
ax1.legend()

ax2.plot(x, y_convex, 'g-', linewidth=2)
ax2.set_title('凸函数示例')
ax2.set_xlabel('x')
ax2.set_ylabel('f(x)')
ax2.grid(True, alpha=0.3)
# 标记全局最小值点
ax2.scatter([2], [convex_func(2)], color='red', s=80, zorder=5, label='全局最小值')
ax2.legend()

plt.tight_layout()
plt.show()

# 使用数值方法寻找非凸函数的局部极小值（演示梯度下降可能陷入局部最优）
from scipy.optimize import minimize

# 从不同初始点出发
initial_points = [-2.5, 0, 2.5]
print("非凸函数从不同初始点优化的结果：")
for x0 in initial_points:
    res = minimize(non_convex_func, x0, method='BFGS')
    print(f"  初始点 x0 = {x0:4.1f} -> 收敛到 x* = {res.x[0]:6.3f}, f(x*) = {res.fun:6.3f}")

print("\n凸函数从不同初始点优化的结果（总是收敛到全局最优）：")
for x0 in initial_points:
    res = minimize(convex_func, x0, method='BFGS')
    print(f"  初始点 x0 = {x0:4.1f} -> 收敛到 x* = {res.x[0]:6.3f}, f(x*) = {res.fun:6.3f}")

2. 线性规划：凸优化的特例

2.1 定义与标准形式

线性规划是凸优化问题的一个子类，它要求目标函数和所有约束函数都是仿射函数。其标准形式通常写作： $$\begin{aligned} \min_{x} \quad & c^T x \ \text{s.t.} \quad & G x \preceq h \ & A x = b \end{aligned}$$ 其中，$c \in \mathbb{R}^n$, $G \in \mathbb{R}^{m \times n}$, $h \in \mathbb{R}^m$, $A \in \mathbb{R}^{p \times n}$, $b \in \mathbb{R}^p$。符号 $\preceq$ 表示向量的逐分量小于等于。

由于仿射函数既是凸函数也是凹函数，线性规划显然满足凸优化的所有条件。

2.2 求解方法简介

线性规划有成熟的求解理论和算法：

• 单纯形法：通过在多面体可行域的顶点间迭代，寻找最优解。对于大多数实际问题非常有效。
• 内点法：从可行域内部出发，沿着中心路径逼近边界上的最优解。具有多项式时间复杂性。
• 对偶理论：每个线性规划问题都有一个对应的对偶问题。有时求解对偶问题更为方便，且对偶变量具有重要的经济或物理意义（如影子价格）。

下面我们用 Python 的 SciPy 库来求解一个简单的线性规划问题。

import numpy as np
from scipy.optimize import linprog

# 定义线性规划问题：
# 目标: min c^T * x
# 约束: G * x <= h
#        A * x = b
#        x >= 0 (边界约束可通过 G, h 设置)

# 例题： min 2x1 + 4x2 + 3x3
#        s.t. 3x1 + 4x2 + 2x3 >= 10
#             2x1 +  x2 + 3x3 >= 8
#             x1, x2, x3 >= 0

# 由于 linprog 默认求解 min c^T x, s.t. A_ub * x <= b_ub, A_eq * x = b_eq
# 我们需要将“>=”约束转换为“<=”约束

c = np.array([2, 4, 3])  # 目标函数系数

# 不等式约束: 原约束为 >=，两边乘以 -1 变为 <=
G = np.array([[-3, -4, -2],  # -1 * (3x1+4x2+2x3) <= -10
              [-2, -1, -3]]) # -1 * (2x1+ x2+3x3) <= -8
h = np.array([-10, -8])      # 右边的常数项也乘以 -1

# 变量非负约束，通过指定 bounds 参数实现
bounds = [(0, None), (0, None), (0, None)]

# 调用线性规划求解器
res = linprog(c, A_ub=G, b_ub=h, bounds=bounds, method='highs')

print("线性规划求解结果：")
print(f"   是否成功: {res.success}")
print(f"   最优解: x1 = {res.x[0]:.4f}, x2 = {res.x[1]:.4f}, x3 = {res.x[2]:.4f}")
print(f"   最优目标函数值: {res.fun:.4f}")
print(f"   迭代次数: {res.nit}")

3. 二次规划：另一类重要的凸优化问题

3.1 定义与标准形式

二次规划是目标函数为凸二次型，约束函数为仿射函数的凸优化问题。其标准形式为： $$\begin{aligned} \min_{x} \quad & \frac{1}{2} x^T P x + q^T x + r \ \text{s.t.} \quad & G x \preceq h \ & A x = b \end{aligned}$$ 其中，$P \in \mathbb{S}^n_+$ 是一个 $n \times n$ 的对称半正定矩阵（保证目标函数是凸函数），$q \in \mathbb{R}^n$, $r \in \mathbb{R}$。$G, h, A, b$ 的定义与线性规划中类似。

3.2 典型应用：最小二乘回归

最小二乘线性回归是二次规划的一个经典例子。给定数据 $(X, y)$，我们希望找到参数 $\beta$ 以最小化残差平方和： $$\min_{\beta} \quad | y - X\beta |^2_2$$ 将其展开： $$| y - X\beta |^2_2 = (y - X\beta)^T (y - X\beta) = \beta^T (X^T X) \beta - 2 y^T X \beta + y^T y$$ 这正好是二次规划的形式，其中 $P = 2X^TX$（半正定），$q = -2X^Ty$，$r = y^Ty$。如果没有额外约束，该问题的最优解即为熟知的正规方程解 $\beta^* = (X^TX)^{-1}X^Ty$。

下面的代码演示了如何使用二次规划求解器求解一个带简单约束的最小二乘问题。

import numpy as np
from scipy.optimize import minimize

# 生成模拟数据
np.random.seed(42)
n_samples = 100
n_features = 3

# 生成特征矩阵 X 和真实系数 beta_true
X = np.random.randn(n_samples, n_features)
beta_true = np.array([1.5, -2.0, 0.5])
# 生成响应变量 y，加入一些噪声
y = X @ beta_true + np.random.randn(n_samples) * 0.5

# 方法1：使用正规方程求解无约束最小二乘
beta_ols = np.linalg.inv(X.T @ X) @ (X.T @ y)
print("无约束最小二乘解 (正规方程):")
print(f"   beta = {beta_ols}")

# 方法2：将其构造成二次规划问题，并使用通用优化器求解
# 定义二次规划的目标函数: 1/2 * beta^T * P * beta + q^T * beta
P = 2 * (X.T @ X)  # 注意：1/2 * beta^T * P * beta = beta^T * (X^T X) * beta
q = -2 * (X.T @ y)

def objective(beta):
    return 0.5 * beta @ P @ beta + q @ beta

# 添加一个简单的线性约束：例如，要求所有系数之和等于 0
# 约束条件: sum(beta) = 0  ->  A_eq * beta = b_eq
A_eq = np.ones((1, n_features))
b_eq = np.array([0.0])

# 初始猜测值
beta0 = np.zeros(n_features)

# 使用序列最小二乘规划（SLSQP）方法求解带等式约束的二次规划
cons = ({'type': 'eq', 'fun': lambda b: A_eq @ b - b_eq})
res_qp = minimize(objective, beta0, constraints=cons, method='SLSQP')

print("\n带约束的二次规划解 (sum(beta)=0):")
print(f"   beta = {res_qp.x}")
print(f"   约束检查: sum(beta) = {np.sum(res_qp.x):.6f}")
print(f"   目标函数值: {res_qp.fun:.6f}")

# 对比两种解对应的残差平方和
rss_ols = np.sum((y - X @ beta_ols)**2)
rss_qp = np.sum((y - X @ res_qp.x)**2)
print(f"\n残差平方和对比:")
print(f"   无约束解 RSS: {rss_ols:.6f}")
print(f"   带约束解 RSS: {rss_qp:.6f}")

📝 动手练一练

1. 凸集判断：判断下列集合是否为凸集，并简述理由。 a) $S_1 = { x \in \mathbb{R}^2 \mid x_1^2 + x_2^2 \leq 1 }$（单位圆盘） b) $S_2 = { x \in \mathbb{R}^2 \mid x_1 x_2 \geq 1, x_1 > 0, x_2 > 0 }$ c) $S_3 = { x \in \mathbb{R}^n \mid |x|_\infty \leq 1 }$（无穷范数单位球）

   参考答案： a) 是凸集。因为函数 $f(x) = x_1^2 + x_2^2$ 是凸函数，其水平集 ${x \mid f(x) \leq 1}$ 是凸集。 b) 是凸集。理由：函数 $f(x_1, x_2) = -\ln x_1 - \ln x_2$ 在第一象限（$x_1 > 0, x_2 > 0$）是凸函数（其 Hessian 矩阵为 $\text{diag}(1/x_1^2, 1/x_2^2)$，正定），而集合 $S_2$ 恰好是该凸函数的下水平集 ${ (x_1, x_2) \mid f(x_1, x_2) \leq 0, x_1 > 0, x_2 > 0 }$，根据”凸函数的下水平集是凸集”的性质，可知 $S_2$ 是凸集。 c) 是凸集。无穷范数球 $|x|_\infty \leq 1$ 等价于 $\max_i |x_i| \leq 1$，即 $2n$ 个线性不等式 $x_i \leq 1$ 与 $-x_i \leq 1$（$i = 1, \ldots, n$）的交集。每个不等式都定义了一个半空间，半空间是凸集，而凸集的交集仍是凸集。

   易错提醒：注意区分 $S_2$（不等式约束 $\geq$，凸集）与双曲线 ${ x \mid x_1 x_2 = 1 }$（等式约束，非凸）。后者上任取两点（如 $(2, 0.5)$ 与 $(0.5, 2)$），其中点 $(1.25, 1.25)$ 的乘积为 $1.5625 \neq 1$，不在集合内。这说明”约束方向”（不等式 vs 等式）对凸性有决定性影响。

2. 线性规划建模：某工厂生产两种产品 A 和 B。生产每件 A 产品需要 2 小时人工和 1 公斤原料，利润为 30 元。生产每件 B 产品需要 1 小时人工和 3 公斤原料，利润为 40 元。工厂每天可用人工工时为 100 小时，原料为 120 公斤。请建立使每日总利润最大的线性规划模型（不需求解）。

   参考答案： 设 $x_1$ 为产品 A 的日产量，$x_2$ 为产品 B 的日产量。 目标函数（最大化利润）：$\max , z = 30x_1 + 40x_2$ 约束条件：

   • 人工工时约束：$2x_1 + x_2 \leq 100$
   • 原料约束：$x_1 + 3x_2 \leq 120$
   • 非负约束：$x_1 \geq 0, x_2 \geq 0$ 将其转化为标准最小化形式：$\min , -z = -30x_1 - 40x_2$，约束不变。

本章小结

本节系统介绍了凸优化问题的理论框架及其在人工智能数学基础中的核心地位。

要点回顾：

1. 凸优化定义：在标准约束优化问题基础上，要求目标函数和不等式约束函数为凸函数，等式约束函数为仿射函数。
2. 核心性质：凸优化问题的任何局部最优解都是全局最优解，这一性质使其求解在理论上非常可靠。
3. 线性规划：目标与约束均为仿射的凸优化问题，是许多资源分配、调度问题的数学模型，可通过单纯形法、内点法等高效求解。
4. 二次规划：目标为凸二次型、约束为仿射的凸优化问题，最小二乘回归、支持向量机等都与之密切相关。
5. 计算实践：掌握利用优化库（如 SciPy）求解线性规划、二次规划等凸优化问题的基本方法，是将理论应用于实际的关键一步。

行动清单：

• 概念辨析：回顾凸函数、凸集的定义，确保能判断一个简单函数或集合的凸性。
• 模型转化：尝试将一个小型实际决策问题（如上面的工厂生产问题）抽象为线性规划模型。
• 代码验证：在 Python 环境中运行本节提供的代码示例，并尝试修改问题参数（如目标函数系数、约束条件），观察最优解的变化。

— 小象教研组