1. 凸集优化问题的安全区域第一次接触凸集概念时我把它想象成一个没有凹陷的橡皮泥球——无论怎么捏连接球内任意两点的线段都不会跑到球外面。这种几何直观后来成了我理解凸优化的重要基础。在欧氏空间中凸集的数学定义是对于集合内任意两点x₁和x₂它们的凸组合θx₁ (1-θ)x₂其中0≤θ≤1仍然属于该集合。常见的凸集包括超平面{x | aᵀx b}就像用刀均匀切开空间半空间{x | aᵀx ≤ b}超平面的一侧区域球体{x | ||x-x₀|| ≤ r}所有到中心点距离不超过r的点多面体有限个半空间的交集比如二维空间中的三角形# 判断集合S是否为凸集的Python示例 import numpy as np def is_convex(S, test_points1000): for _ in range(test_points): x1, x2 S[np.random.choice(len(S), 2, replaceFalse)] theta np.random.rand() if theta*x1 (1-theta)*x2 not in S: return False return True凸集有个重要特性多个凸集的交集仍是凸集。这个性质在实际建模中非常有用比如当我们需要同时满足多个线性不等式约束时可行解空间就是这些半空间的交集自然形成凸集。2. 凸函数优化问题的理想地形凸函数就像碗状曲面任意两点连线都在曲面之上。数学上函数f: ℝⁿ → ℝ在凸集S上是凸函数当且仅当 f(θx (1-θ)y) ≤ θf(x) (1-θ)f(y) ∀x,y∈S, θ∈[0,1]判断凸函数的实用方法一阶条件可微函数f是凸函数当且仅当f(y) ≥ f(x) ∇f(x)ᵀ(y-x)二阶条件二阶连续可微函数f是凸函数当且仅当Hessian矩阵∇²f(x)半正定常见凸函数示例线性函数f(x) aᵀx b二次函数f(x) xᵀQx cᵀxQ半正定指数函数f(x) eᵃˣ负对数f(x) -log(x)# 用Hessian矩阵判断函数凸性 from scipy.linalg import eigvalsh def is_convex_func(f, hessian, domain): samples [np.random.uniform(*domain) for _ in range(100)] for x in samples: if np.any(eigvalsh(hessian(x)) -1e-8): # 存在负特征值 return False return True在机器学习中很多损失函数如均方误差、交叉熵都是凸函数这保证了我们可以找到全局最优解。记得第一次实现逻辑回归时我惊讶于无论怎么初始化参数算法总能收敛到相同结果——这正是凸函数的神奇之处。3. 凸规划局部最优即全局最优凸优化问题标准形式 minimize f₀(x) subject to fᵢ(x) ≤ 0, i1,...,m Ax b 其中f₀和fᵢ都是凸函数等式约束是线性的。凸规划的关键性质局部最优解就是全局最优解最优解集是凸集对于严格凸函数最优解唯一我在供应链优化项目中遇到过典型的凸规划问题某公司需要最小化运输成本二次成本函数同时满足各仓库的供需平衡线性等式约束和运输能力限制线性不等式约束。使用CVXPY建模只需几行代码import cvxpy as cp # 定义变量和参数 x cp.Variable(n) # 运输量 A np.random.randn(m,n) # 约束矩阵 b np.random.randn(m) # 需求向量 # 构建问题 objective cp.Minimize(cp.quad_form(x, Q) c.T x) constraints [A x b, x 0] prob cp.Problem(objective, constraints) # 求解 result prob.solve()4. 线性规划凸规划的特例线性规划(LP)是目标函数和约束都是线性的凸规划标准形式为 minimize cᵀx subject to Ax b x ≥ 0单纯形法是求解LP的经典算法虽然最坏情况下是指数复杂度但在实际应用中表现优异。我曾在生产排程问题中对比过单纯形法和内点法单纯形法在稀疏约束矩阵下速度更快内点法更适合大规模稠密问题from scipy.optimize import linprog # 生产利润最大化案例 c [-3, -2] # 目标系数(求最大转为求最小) A [[1, 1], [2, 1]] # 约束系数 b [4, 5] # 约束上限 res linprog(c, A_ubA, b_ubb, bounds(0, None)) print(f最优生产计划产品A {res.x[0]:.1f}单位产品B {res.x[1]:.1f}单位)5. 二次规划带平方项的优化二次规划(QP)的目标函数是二次型约束为线性 minimize (1/2)xᵀQx cᵀx subject to Ax ≤ b在投资组合优化中我们最小化风险方差同时要求预期收益import cvxpy as cp Sigma np.cov(returns) # 资产收益协方差矩阵 mu np.mean(returns, axis1) # 预期收益 target_return 0.1 x cp.Variable(n) prob cp.Problem( cp.Minimize(cp.quad_form(x, Sigma)), [mu.T x target_return, cp.sum(x) 1, x 0]) prob.solve()支持向量机(SVM)的优化问题也是典型的QP。记得第一次推导SVM对偶问题时发现最终要解决的竟是一个凸二次规划顿时理解了为什么SVM总能找到全局最优解。6. 求解算法从理论到实现梯度下降法虽然简单但在非强凸函数上可能收敛缓慢。我曾在神经网络训练中观察到梯度下降的之字形下降路径def gradient_descent(f, grad, x0, lr0.01, max_iter1000): x x0.copy() path [x0] for _ in range(max_iter): x x - lr * grad(x) path.append(x) if np.linalg.norm(grad(x)) 1e-6: break return x, np.array(path)牛顿法利用二阶信息收敛更快但需要计算Hessian矩阵。在逻辑回归中比较两种方法梯度下降需要1000次迭代达到1e-4精度牛顿法只需不到10次迭代def newton_method(f, grad, hess, x0, max_iter100): x x0.copy() for _ in range(max_iter): delta np.linalg.solve(hess(x), -grad(x)) x delta if np.linalg.norm(delta) 1e-8: break return x实际应用中拟牛顿法如BFGS往往更实用它通过近似Hessian矩阵避免了直接计算二阶导数。在Scipy中可以直接调用from scipy.optimize import minimize result minimize(funobjective, x0x0, methodBFGS, jacgradient)7. 工程实践中的凸优化在计算机视觉项目中我们曾用凸优化解决相机位姿估计问题。将重投影误差最小化表述为二阶锥规划(SOCP)# 使用cvxpy建立SOCP模型 poses cp.Variable((n_cameras, 6)) # 位姿参数 points_3d cp.Variable((n_points, 3)) # 三维点 constraints [] for i, j in zip(camera_indices, point_indices): # 构建重投影误差约束 error reprojection_error(poses[i], points_3d[j], observations[i,j]) constraints.append(cp.SOC(1.0, error)) # 二阶锥约束 prob cp.Problem(cp.Minimize(0), constraints) prob.solve(solvercp.SCS, verboseTrue)另一个有趣应用是用凸优化进行图像修复。将损坏像素的修复建模为优化问题目标是最小化图像梯度的L1范数总变分同时保持已知像素值不变# 创建mask矩阵1表示已知像素0表示待修复 U cp.Variable(shapeimage.shape) objective cp.Minimize(cp.tv(U)) constraints [cp.multiply(mask, U) cp.multiply(mask, image)] prob cp.Problem(objective, constraints) prob.solve(solvercp.SCS)8. 凸优化的局限与扩展虽然凸优化有诸多优点但现实问题往往是非凸的。这时可以尝试凸松弛将非凸问题放宽为凸问题分支定界用于混合整数规划序列凸近似迭代求解局部凸近似例如在三维重建中将非凸的Bundle Adjustment问题线性化后迭代求解for iteration in range(max_iterations): # 在当前估计点附近线性化 A, b linearize_reprojection_errors(current_estimate) # 解线性最小二乘问题 delta cp.Variable(n_params) prob cp.Problem(cp.Minimize(cp.norm(A delta - b, 2))) prob.solve() # 更新估计 current_estimate delta.value随着问题规模增大还需要考虑分布式优化算法。ADMM交替方向乘子法就是适合分布式计算的框架它将问题分解为多个可并行求解的子问题。