经典优化（可解的核心）

上级: optimization

你已经掌握的数学，加上"可解"这条边界画在哪里。

无约束情形

• 一阶条件： ∇f(x)=0（驻点）；
• 二阶条件： Hessian 矩阵 ∇²f ⪰ 0（局部极小）；处处半正定 ⟺ 凸。
• 凸性是关键性质——凸函数没有坏的局部极小（每个驻点都是全局最优）。

约束情形——你已经会的（"取 μ"）

在等式约束 hᵢ(x)=0 和不等式约束 gⱼ(x)≤0 下最小化 f(x)。用乘子把约束定价进lagrangian（拉格朗日函数）L；最优性条件就是 kkt 条件；对偶问题恒为凹（对凸问题而言，在 Slater 条件下强对偶成立）。完整处理见 → lagrangian、kkt。

具名的凸问题族（层层嵌套）

LP ⊂ QP ⊂ SOCP ⊂ SDP——线性规划、二次规划、二阶锥规划、半正定规划。

• LP：单纯形法（Dantzig）/ 内点法；LP 的对偶性。
• 凸优化（Boyd–Vandenberghe）：现代的综合理论——只要能把问题写成凸锥规划，就能用内点法在多项式时间内求解。

唯一要紧的想法

凸性是分界线。 凸——全局可解，对偶紧，理论透彻。非凸——困难（一般情形下 NP-难），存在局部极小，收敛没有免费保证——而这正是本篇之后所有内容的去处。