凸优化第2讲：凸优化建模

目录

第1讲：凸优化基础

• 理论：凸集/凸函数定义、凸优化问题标准形式、全局最优性。
• 案例：线性回归的凸性证明。
• 代码：MATLAB fmincon 验证凸函数最小值。

第2讲：凸优化建模

• 理论：常见凸问题类（LP、QP、SOCP、SDP）、建模技巧（松弛法）。
• 案例：投资组合优化（QP）、机器学习损失函数凸性分析。
• 代码：Python CVXPY 建模投资组合问题。

第3讲：对偶理论

• 理论：拉格朗日对偶、强弱对偶性、KKT条件。
• 案例：支持向量机（SVM）对偶问题推导。
• 代码：MATLAB 求解对偶间隙。

第4讲：梯度下降法

• 理论：收敛性分析、步长选择（精确/回溯线搜索）。
• 案例：逻辑回归参数优化。
• 代码：Python 实现梯度下降（NumPy）。

第5讲：牛顿法与内点法

• 理论：牛顿方向、障碍函数、路径跟踪算法。
• 案例：不等式约束优化（如路径规划）。
• 代码：MATLAB quadprog 实现内点法。

第6讲：次梯度与近端方法

• 理论：次梯度定义、近端算子、Lasso回归。
• 案例：稀疏信号恢复（压缩感知）。
• 代码：Python scikit-learn 对比次梯度与近端梯度下降。

第7讲：分布式凸优化

• 理论：ADMM算法、一致性优化。
• 案例：多智能体协同控制。
• 代码：MATLAB 并行计算工具箱实现ADMM。

第8讲：鲁棒优化

• 理论：不确定集建模、鲁棒对偶。
• 案例：电力系统调度中的不确定性处理。
• 代码：Python ROME 工具箱示例。

第9讲：凸优化在AI中的应用

• 理论：深度学习中的凸松弛（如低秩矩阵补全）。
• 案例：神经网络训练中的凸代理损失。
• 代码：PyTorch 自定义凸损失函数。

第10讲：前沿与总结

• 理论：非凸优化中的凸启发式方法（如凸包络）。
• 案例：学员自选课题报告（如医学图像重建）。
• 代码：综合项目答辩（MATLAB/Python实现）。

---

第2讲：凸优化建模

**理论s

1. 凸优化问题的标准分类

凸优化问题按目标函数和约束类型可分为以下四类核心问题：

问题类型	标准形式	特点	应用场景
线性规划 (LP)	$\min c^{T}x$s.t. $Ax\le b$$x\ge 0$	目标/约束均为线性	资源分配、生产计划
二次规划 (QP)	$\min \frac{1}{2}{x}^{T}Qx+c^{T}x$s.t. $Ax\le b$$Q⪰0$	目标为二次凸函数	投资组合优化、控制问题
二阶锥规划 (SOCP)	$\min f^{T}x$s.t. $	A_ix + b_i	_2 \leq c_i^Tx + d_i$
半定规划 (SDP)	$\min \text{tr}(CX)$s.t. $\text{tr}(A_{i}X)=b_i$$X⪰0$	矩阵变量半正定约束	系统控制、组合优化

凸性验证要点：

• QP中$Q$必须半正定
• SOCP的锥约束需满足$|\cdot {|}_2\le \text{线性项}$
• SDP的可行域是矩阵的凸锥

2. 建模技巧

(1) 松弛法

将非凸约束放宽为凸约束：

$\begin{cases} \text{原约束} & x \in {0,1} \ \text{凸松弛} & 0 \leq x \leq 1 \end{cases} $

应用：整数规划中的LP松弛

(2) 等价转换

例：将分式目标转换为SOCP：

$\min \frac{\Vert Ax-b{\Vert }_2^2}{c^{T}x+d}\Rightarrow \{\begin{array}{l}\min t\\ \text{s.t.}\Vert Ax-b{\Vert }_2^2\le t(c^{T}x+d)\end{array}$

---

案例部分

案例1：投资组合优化（QP）

问题描述

在给定$n$种资产的期望收益$\mu$和协方差矩阵$\Sigma$下，求解最优投资权重$w$：

$\begin{array}{rl}\underset{w}{\max }& {\mu }^{T}w-\gamma w^T\Sigma w\\ \text{s.t.}& \sum w_i=1\\ & w\ge 0\end{array}$

• $\gamma$：风险厌恶系数
• 目标函数为凹函数（最大化问题）

凸性分析

• 目标函数可写为$-\min (-{\mu }^{T}w+\gamma w^T\Sigma w)$
• 因$\Sigma ⪰0$，问题为凸QP

---

案例2：机器学习损失函数凸性分析

常见损失函数验证

1. 平方损失：$L(w)=|y-Xw{|}_2^2$
   • Hessian矩阵：${\nabla }^{2}L(w)=2X^{T}X⪰0$
2. Logistic损失：$L(w)=\sum \log (1+e^{-y_i{w}^T{x}_i})$
   • Hessian矩阵：${\nabla }^{2}L(w)=\sum \sigma (z_i)(1-\sigma (z_i))x_i{x}_i^T⪰0$
     （其中$\sigma (z)=1/(1+e^{-z})$）
3. Hinge损失（非凸）：$L(w)=\sum \max (0,1-y_i{w}^T{x}_i)$
   • 在$y_i{w}^T{x}_i=1$处不可微，整体非凸

---

代码实现

1. 投资组合优化（Python + CVXPY）

import cvxpy as cp
import numpy as np
import pandas as pd# 生成模拟数据
np.random.seed(42)
n_assets = 10
returns = np.random.randn(100, n_assets) * 0.01  # 日收益率
mu = np.mean(returns, axis=0)
Sigma = np.cov(returns.T)# 构建优化问题
gamma = cp.Parameter(nonneg=True, value=0.5)  # 风险参数
w = cp.Variable(n_assets)
prob = cp.Problem(cp.Maximize(mu.T @ w - gamma * cp.quad_form(w, Sigma)),[cp.sum(w) == 1, w >= 0]
)
prob.solve()# 结果分析
print("最优权重:", w.value.round(4))
print("预期收益:", (mu @ w.value).round(4))
print("风险:", np.sqrt(w.value @ Sigma @ w.value).round(4))# 有效前沿计算
risks = []
returns = []
gammas = np.logspace(-2, 2, 20)
for g in gammas:gamma.value = gprob.solve()risks.append(np.sqrt(w.value @ Sigma @ w.value))returns.append(mu @ w.value)# 可视化
import matplotlib.pyplot as plt
plt.plot(risks, returns, 'bo-')
plt.xlabel('Risk (Std Dev)')
plt.ylabel('Expected Return')
plt.title('Efficient Frontier')
plt.show()

代码解析

1. gamma作为参数实现快速重优化
2. cp.quad_form(w, Sigma)精确表达二次项
3. 通过参数扫描绘制有效前沿

---

2. 鲁棒投资组合（SOCP扩展）

考虑收益不确定性$\mu \in \mathcal{U}$：

# 定义不确定集半径
delta = 0.1  # 鲁棒优化模型
prob_robust = cp.Problem(cp.Maximize(cp.min(mu.T @ w - delta * cp.norm(w, 1)) - gamma * cp.quad_form(w, Sigma)),[cp.sum(w) == 1, w >= 0]
)
prob_robust.solve(solver=cp.ECOS)

**1. 线性规划 (LP) **

理论扩展

• 对偶理论：推导LP对偶问题，证明强对偶定理
• 灵敏度分析：计算影子价格（Shadow Price）和可行域变化影响
• 单纯形法：实现表格形式的单纯形算法

应用场景

• 供应链优化：多仓库配送路径成本最小化
• 广告投放：预算约束下的曝光量最大化

Python代码实现（PuLP库）

from pulp import *
import numpy as np
import matplotlib.pyplot as plt# 生产计划问题
model = LpProblem("Production_Planning", LpMinimize)
x1 = LpVariable("Product_A", lowBound=0)
x2 = LpVariable("Product_B", lowBound=0)# 目标函数：最小化成本
model += 3*x1 + 5*x2, "Total Cost"# 约束条件
model += 2*x1 + 4*x2 >= 8, "Material Constraint"
model += 3*x1 + 2*x2 >= 6, "Labor Constraint"# 求解与可视化
model.solve()
print(f"Optimal Plan: A={x1.varValue}, B={x2.varValue}")# 绘制可行域
x = np.linspace(0, 5, 100)
y1 = (8 - 2*x)/4
y2 = (6 - 3*x)/2
plt.plot(x, y1, label='Material Constraint')
plt.plot(x, y2, label='Labor Constraint')
plt.fill_between(x, np.maximum(y1,y2), 3, alpha=0.2)
plt.scatter(x1.varValue, x2.varValue, c='r', label='Optimal Point')
plt.legend(); plt.grid(); plt.show()

MATLAB实现

% 使用linprog求解
f = [3; 5];
A = [-2 -4; -3 -2];  % 注意MATLAB默认是Ax <= b
b = [-8; -6];
lb = [0; 0];
[x, fval] = linprog(f, A, b, [], [], lb);
disp(['最优解: x1=', num2str(x(1)), ', x2=', num2str(x(2))]);

---

**2. 二次规划 (QP) **

理论扩展

• KKT条件：推导QP问题的KKT系统
• 积极集方法：实现迭代求解策略
• 鲁棒QP：椭球不确定集下的鲁棒对偶形式

应用场景

• 机器人控制：轨迹规划中的最小能量优化
• 金融工程：带交易成本的组合再平衡

Python代码实现（CVXPY）

import cvxpy as cp
import numpy as np# 投资组合优化
np.random.seed(42)
n = 10  # 资产数量
mu = np.abs(np.random.randn(n))  # 期望收益
Sigma = np.random.randn(n, n)
Sigma = Sigma.T @ Sigma  # 协方差矩阵w = cp.Variable(n)
gamma = cp.Parameter(nonneg=True)
gamma.value = 0.5prob = cp.Problem(cp.Maximize(mu.T @ w - gamma * cp.quad_form(w, Sigma)),[cp.sum(w) == 1, w >= 0]
)
prob.solve()# 有效前沿计算
gammas = np.logspace(-2, 2, 20)
returns = []; risks = []
for g in gammas:gamma.value = gprob.solve()returns.append(mu @ w.value)risks.append(np.sqrt(w.value @ Sigma @ w.value))# 可视化
plt.plot(risks, returns, 'bo-')
plt.xlabel('Risk'); plt.ylabel('Return')
plt.title('Efficient Frontier')
plt.show()

MATLAB实现

% 使用quadprog求解
H = [1 -1; -1 2];
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];
[x, fval] = quadprog(H, f, A, b, [], [], zeros(2,1));
disp(['最优解: x1=', num2str(x(1)), ', x2=', num2str(x(2))]);

---

**3. 二阶锥规划 (SOCP) **

理论扩展

• 锥对偶：推导SOCP的锥对偶形式
• 欧几里得Jordan代数：分析锥约束的数学结构
• 鲁棒优化：将不确定约束转化为SOCP

应用场景

• 天线阵列设计：波束成形优化
• 结构设计：桁架结构的最小重量设计

Python代码实现（CVXPY）

# 鲁棒回归问题
m, n = 30, 10
A = np.random.randn(m, n)
b = np.random.randn(m)# 传统最小二乘
x_ls = cp.Variable(n)
prob_ls = cp.Problem(cp.Minimize(cp.norm(A @ x_ls - b, 2)))
prob_ls.solve()# 鲁棒SOCP形式
rho = 0.1  # 扰动半径
x_socp = cp.Variable(n)
t = cp.Variable()
constraints = [cp.norm(A @ x_socp - b, 2) + rho * cp.norm(x_socp, 2) <= t]
prob_socp = cp.Problem(cp.Minimize(t), constraints)
prob_socp.solve()# 结果比较
print(f"LS误差: {prob_ls.value:.3f}, SOCP误差: {prob_socp.value:.3f}")

MATLAB实现

% 使用coneprog求解
prob = optimproblem;
x = optimvar('x', 3);
t = optimvar('t');
prob.Objective = t;
prob.Constraints.c1 = norm([2*x(1); x(2)-1]) <= x(3) + t;
prob.Constraints.c2 = x(3) + t <= 5;
[sol, fval] = solve(prob);
disp(['最优解: x=', num2str(sol.x')]);

---

**4. 半定规划 (SDP) **

理论扩展

• 矩阵对偶：推导SDP的Lagrange对偶
• 组合优化应用：最大割问题的SDP松弛
• 多项式优化：Lasserre松弛的SDP实现

应用场景

• 量子信息：量子态层析优化
• 传感器网络：节点定位问题

Python代码实现（CVXPY）

# 最大割问题的SDP松弛
n = 5
W = np.random.randn(n, n)
W = (W + W.T)/2  # 对称权重矩阵X = cp.Variable((n,n), symmetric=True)
constraints = [X >> 0, cp.diag(X) == 1]
prob = cp.Problem(cp.Maximize(cp.trace(W @ X)/4), constraints)
prob.solve()# 随机舍入法获取离散解
v = np.random.randn(n)
x_round = np.sign(np.linalg.cholesky(X.value + 1e-6*np.eye(n)) @ v)
print(f"SDP目标值: {prob.value:.3f}, 舍后目标: {x_round.T @ W @ x_round/4:.3f}")

MATLAB实现

% 使用sdpt3求解
n = 4;
C = randn(n); C = (C + C')/2;
A = cell(1,n);
for i = 1:nA{i} = sparse(i,i,1,n,n);
end
b = ones(n,1);
[X, y, info] = sedumi(A, b, C, [n]);
disp(['最大特征值: ', num2str(eigs(X,1))]);

---

综合对比实验设计

性能对比表

问题类型	求解器	100变量耗时	收敛迭代次数	内存占用
LP	Gurobi	0.12s	15	45MB
QP	MOSEK	0.35s	22	78MB
SOCP	ECOS	0.28s	30	62MB
SDP	SDPT3	2.1s	45	210MB

可视化分析

# 绘制不同规模问题的求解时间
sizes = [10, 50, 100, 200]
times = {'LP': [0.01, 0.05, 0.12, 0.25],'QP': [0.03, 0.15, 0.35, 0.8],'SOCP': [0.05, 0.2, 0.5, 1.2],'SDP': [0.3, 1.2, 2.5, 6.0]}for typ in times:plt.plot(sizes, times[typ], 'o-', label=typ)
plt.xlabel('Problem Size'); plt.ylabel('Time (s)')
plt.legend(); plt.grid(); plt.show()

---