凸优化

凸优化研究在凸可行集上最小化凸函数的问题。它把“某处再也降不下去”与“整个可行域中没有更好的点”连在一起。凸集保证任意两个可行点之间的线段仍可行；凸函数保证线段上的函数值不高于端点函数值的线性插值。这两项条件要同时检查，不能仅凭函数图像像一只碗就认定模型是凸优化。

一个有边界的最近点问题

设要在第一象限且 $x+y\le 2$ 的区域中，寻找最靠近 $a=(2,1)$ 的点。距离的平方与距离有相同的最小点，问题写成 $$minf(x,y)=(x-2{)}^2+(y-1{)}^2,x\ge 0,y\ge 0,x+y\le 2.$$ 如果没有约束，答案是 $(2,1)$；但它的坐标和为三，超出了允许的二。沿边界 $x+y=2$，令 $y=2-x$，有 $$f(x,2-x)=(x-2{)}^2+(1-x{)}^2=2{(x-\frac{3}{2})}^2+\frac{1}{2}.$$ 所以边界上最好的候选点是 $p=(3/2,1/2)$，目标值 $1/2$。代入约束可确认它确实可行。

配方只找到了边界上的最小值，还要排除区域内部的更好点。对任一可行点 $z=(x,y)$，把 $z-a=(z-p)+(p-a)$ 展开： $$\Vert z-a{\Vert }^2-\Vert p-a{\Vert }^2=\Vert z-p{\Vert }^2+2(p-a)\cdot (z-p)=\Vert z-p{\Vert }^2+2-x-y\ge 0.$$ 最后一步用 $x+y\le 2$。等号仅在 $z=p$ 成立，因此这是唯一的全局最优解。这段计算同时解释了几何意义：把目标点投向可行三角形，投影点到目标点的连线垂直于阻挡它的边界。

可微问题的一阶最优条件

若 $C$ 是凸集、$f$ 在其邻域可微且凸，点 $x^{\ast }\in C$ 最优的充要条件是 $$\mathrm{\nabla }f(x^{\ast })\cdot (y-x^{\ast })\ge 0\text{对每个 }y\in C.$$ 必要性可从可行线段 $x^{\ast }+t(y-x^{\ast })$ 看出：沿这条线段从最优点出发，右导数不能为负。充分性来自凸函数的切平面下界 $f(y)\ge f(x^{\ast })+\mathrm{\nabla }f(x^{\ast })\cdot (y-x^{\ast })$；若一阶内积对所有可行 $y$ 非负，右边就不小于 $f(x^{\ast })$。

在刚才的最近点问题，$\mathrm{\nabla }f(p)=2(p-a)=(-1,-1)$。对任何可行 $y=(u,v)$， $$\mathrm{\nabla }f(p)\cdot (y-p)=-(u-3/2)-(v-1/2)=2-u-v\ge 0.$$ 这个式子正是前面展开平方时出现的非负交叉项；计算与一阶条件在同一个例子里相互核验。若没有边界、且最优点在开集内部，任意方向都能取，才可化成 $\mathrm{\nabla }f(x^{\ast })=0$。

凸性使局部最小也是全局最小：若另有更优可行点，连接它们的短线段会在局部给出更小函数值。若 $f$ 严格凸，两个不同点不可能同时最优，因为其中点会比两端更好。严格凸只保证“至多一个”；还要另证最小值能取得。例如非空紧致可行集上的连续函数一定达到最小值。

建模时检查的三个位置

常见标准形式是 $\underset{x}{min}{f}_0(x)$，满足 $f_i(x)\le 0$ 与 $Ax=b$；其中目标 $f_0$ 和各不等式函数 $f_i$ 都应凸，等式必须是仿射的。上述例子里目标是平方和，三个约束都是仿射不等式。$min(x-1{)}^2$ 若附加 $x\in \{-1,1\}$，目标仍凸，但可行集不凸；孤立点 $x=-1$ 是局部最小，却不如 $x=1$，不能套用刚才的结论。

凸性说明最优解的结构，并不自动替我们完成计算。可微无约束问题可看梯度下降；有边界时可用投影梯度法；乘子、强对偶和约束资格由拉格朗日对偶与KKT条件继续讨论。

“至多一个”与“恰好一个”也不能混淆。例如在开集合 $C=(0,\mathrm{\infty })$ 上最小化严格凸函数 $f(x)=x^2$，可以取越来越小的正数，使函数值逼近零，但零不在 $C$ 内，因此根本没有最小点。若模型把正数的下界改成 $x\ge \epsilon >0$，答案才是 $x=\epsilon$。实际建模时，闭性、界限与是否有可行点同样属于题目的数学条件。

参考资料

• Boyd、Vandenberghe《Convex Optimization》，第2—4章讨论凸集、凸函数及凸优化问题。
• MIT 6.079 凸优化课程讲义，含凸模型与最优性条件。