凸优化问题

这里的关键不是目标函数“看起来像碗”，而是目标的上图与可行域都没有离散裂缝或内凹结构。于是两个可行方案的插值仍可行，且目标值不会高于端点值的相同加权平均。任何严格改进方向都能沿线段持续推进，这正是局部极小点无法伪装成非全局解的原因。

线性规划、最小二乘、二次规划（半正定 Hessian）、范数正则化和半定规划都是凸优化。约束 $g(x)=0$ 即使 $g$ 凸也通常产生非凸集合，例如 $x^2=1$；所以等式必须仿射。把最大化凹函数改写为最小化其负值仍属凸优化。问题的某种代数写法看似非凸，不代表其本质不可凸化；反之，只有目标凸而可行域非凸也不属于标准凸问题。全局最优性质不自动保证最优解存在，仍需闭性、紧性或强制性等条件。

最小二乘

是无约束凸问题；加入 $Cx\le d$ 仍保持凸性。相反，约束 $\Vert x{\Vert }_2=1$ 把可行域限制在球面，两个对径可行点的中点不再可行，所以即使目标凸，整体问题也非凸。最优值有限不保证被取得，例如在开区间 $(0,1)$ 上最小化 $x$ 的下确界为零却无最优点。

线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。是目标与约束均仿射的基本特例，凸函数公理库凸函数Convex function函数在任意凸组合处不超过相同权重下函数值的凸组合。和凸集公理库凸集Convex set任意两点间线段全部包含在集合中的向量空间子集。则给出一般模型。可微情形可用梯度公理库梯度Gradient标量函数微分在内积下对应的向量。描述一阶条件；存在性还要借助闭性、紧性公理库紧空间Compact space每个开覆盖都能缩减为有限子覆盖的拓扑空间。或强制增长，而不仅是凸性。统计估计、控制和资源配置之所以偏爱凸建模，正因为最优性证书和数值算法可以相互校验。

机器学习训练把样本确定后，ERM公理库经验风险最小化Empirical risk minimization · ERM在假设类中选择训练样本平均损失最小的规则。可能形成一个静态凸问题；正则化 ERM公理库正则化经验风险最小化regularized ERM · RERM在经验拟合项上加入结构惩罚，以显式控制解的复杂度与统计—优化权衡。再把惩罚写入目标。求得训练目标的全局最优只证明优化命题，不证明该解接近未知分布下的总体风险最优，后者还需泛化分析。在线凸优化公理库在线凸优化Online convex optimization · OCO每轮先在凸域选点、再承受未知凸损失，并与最好固定点比较。的损失则逐轮揭示，评价累计 regret，而不是把它视为同一个静态问题反复求解。这些页面以凸优化作数学工具，本页的定义不反向依赖学习协议。

对偶问题公理库拉格朗日对偶Lagrange duality通过拉格朗日函数构造原问题下界的对偶问题，并研究弱对偶、强对偶与最优性条件。能在尚未求得原问题最优解时先给出全局下界，并在适当约束资格下与原最优值相等。非光滑目标可先通过近端算子公理库近端算子Proximal operator · Proximity operator在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。把“降低函数值”与“保持靠近当前点”合成一个单值映射，再由近端点方法公理库近端点方法Proximal point method · Proximal point algorithm反复精确求解带二次稳定项的子问题以逼近闭凸函数最小点的方法。迭代整个目标的 prox。它不同于只对复合目标一部分取 prox 的 proximal gradient；梯度法、近端法和内点法利用的结构并不相同。