第1章：优化问题与凸性

几何、最优性与求解方法

凸集描述哪些选择可以同时成立，凸函数描述目标如何随选择变化。支撑超平面、次梯度和共轭把几何结构转成可运算的关系；最优性条件用这些关系判断一个候选解是否已经最好；对偶问题提供可以和候选值比较的下界。

数值算法则负责产生候选解。梯度法使用一阶信息，牛顿法使用局部曲率，投影和近端操作处理约束或非光滑项，内点法通过障碍函数处理不等式。它们与最优性理论相互配合，但不是同一个问题：证明某点最优，不代表已经找到计算它的低成本方法；算法停止，也不代表它已经给出了可靠的最优性证书。

一般优化问题写为

\min_x f_0(x)\quad\text{s.t. }f_i(x)\le0,\ i=1,\ldots,m,\quad Ax=b.

可行集由约束给出，目标函数比较可行点的优劣。最优值是目标的下确界；最优解是达到该值的可行点，二者不能混同。

例如在 $x>0$ 上最小化 $x$ ，最优值为 0 却没有最优解。在紧的非空可行集上，连续目标能取到最小值；在无界域上常需下半连续性与强制性等条件保证水平集紧。

若目标与不等式约束函数均凸，等式约束为仿射，则可行集凸，构成标准凸优化问题。某个非凸表达式也可能等价改写为凸问题，所以要区分函数形式与实际可行集合。

最小二乘 $\min_x\|Ax-b\|_2^2$ 是凸问题；再加 $\lambda\|x\|_1$ 仍凸，但不再处处可微。约束 $\|x\|_2=1$ 一般非凸，而 $\|x\|_2\le1$ 是凸的。

设 $x$ 为凸可行集中的局部极小点，若另有可行 $y$ 满足 $f(y)<f(x)$ ，则对任意 $0<t<1$ ，点 $x_t=(1-t)x+ty$ 可行，且

f(x_t)\le(1-t)f(x)+tf(y)<f(x).

取足够小的 $t$ ， $x_t$ 任意接近 $x$ ，与局部极小矛盾。因此不存在更优可行点。

证明没有保证解存在，也没有保证唯一。严格凸目标在凸集上至多有一个最优解；强凸还提供定量曲率，但仍需其他条件讨论存在性。

拟合 $Ax\approx b$ 时，平方损失偏重较大残差， $\ell_1$ 损失降低异常值影响， $\ell_\infty$ 损失最小化最大偏差。这些目标表达不同需求，不是求解器的任意选项。

将 $\min_x\|Ax-b\|_\infty$ 引入变量 $t$ ，可写为 $\min t$ ，约束 $-t\mathbf1\le Ax-b\le t\mathbf1$ ，得到线性规划。辅助变量把一个凸但非光滑的目标转换成线性目标与约束。