凸优化问题

这里的关键不是目标函数“看起来像碗”，而是目标的上图与可行域都没有离散裂缝或内凹结构。于是两个可行方案的插值仍可行，且目标值不会高于端点值的相同加权平均。若某个可行点 $y$ 比局部最优点 $x$ 更好，则 $x_{\theta }=(1-\theta )x+\theta y$ 对 $0<\theta <1$ 可行，且

让 $\theta$ 足够小，就在 $x$ 的任意小邻域中找到更好的可行点，与局部最优矛盾。这条线段论证说明凸性为何排除了非全局的局部最优点。

线性规划、无约束最小二乘、带凸约束的半正定二次规划、凸范数正则化与半定规划都属于这一模型。最大化凹函数也可通过目标取负号写成凸最小化。

标准形式用仿射等式保证等式可行集为凸集。凸函数的零水平集则可能非凸，例如 $x^2=1$ 只留下 $-1,1$ 两点；也可能为凸集，例如 $x^2=0$ 只留下原点，此时可等价改写为仿射约束 $x=0$。因此判断问题时，要同时看函数与约束形成的实际集合。

边界最优性由可行方向决定。例如在 $x\ge 0$ 上最小化 $(x+1{)}^2$，解为 $x^{\ast }=0$，梯度为 $2$，负梯度却指向可行域外。可微凸目标在凸可行集上的一阶最优条件是：对每个可行点 $y$，都有 $\mathrm{\nabla }{f}_0(x^{\ast }{)}^{\mathrm{\top }}(y-x^{\ast })\ge 0$。它表示沿任何可行线段出发，一阶目标变化都非负。

最小二乘

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

线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。是目标与约束均仿射的特例，凸函数公理库凸函数Convex function函数在任意凸组合处不超过相同权重下函数值的凸组合。与凸集公理库凸集Convex set任意两点间线段全部包含在集合中的向量空间子集。则提供一般结构。梯度公理库梯度Gradient标量函数微分在内积下对应的向量。或次梯度给出最优性证书。解的存在性可以用另一组条件保证：例如极值定理公理库极值定理Extreme value theorem连续实值函数在非空紧空间上取得最大值和最小值。保证连续目标在非空紧可行集公理库紧空间Compact space每个开覆盖都能缩减为有限子覆盖的拓扑空间。上达到最小值；在有限维空间中，非空闭可行集上的下半连续强制增长目标，若在某个可行点取有限值，也能通过紧水平集取得最小值。

固定训练样本后，经验风险最小化公理库经验风险最小化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反复精确求解带二次稳定项的子问题以逼近闭凸函数最小点的方法。反复执行这一更新。对光滑项与非光滑项之和，近端梯度法则先对光滑项作梯度步，再对非光滑项取近端更新。