“对 $k$ 求和并利用函数值单调即可。第二式由单步下降与强凸推出的 $ \nabla f(x) ^2\ge2\mu(f(x) f^ )$ 相乘得到。极小点的梯度为零来自一阶最优性条件。”
形式陈述 ​
设
这称为变分不等式形式的一阶最优性条件。充分性来自凸函数的一阶下界
必要性则对任意
直觉
从候选点朝任意可行点走一小步,方向导数都不能为负;否则就存在立刻降低目标的可行方向。凸性把这一局部方向信息升级为全局证书,因为整条可行线段都留在
无约束时可以朝梯度的正反两个方向试探,唯一可能是梯度为零。约束会破坏这种对称性:若某方向被集合挡住,即使梯度非零也可能已经无法下降。一阶条件说明“优化停止”是几何命题,而不是某个算法的退出代码。实际程序用小梯度或小投影梯度作为近似证书时,还要把容差、尺度和求值误差写清楚。
例子与边界
考虑
无约束极小点
所以
凸性不能删除。
推论与应用
对闭凸集
与变分不等式等价,因此投影梯度可以用固定点残差衡量近似最优。复合目标
误差结论必须注明指标。若强凸性成立,函数值误差能够控制
参考资料
- Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004,§4.2.3,optimality criterion for differentiable convex problems。
- Amir Beck, First-Order Methods in Optimization, SIAM, 2017,Theorem 3.14 and §9.1,first-order conditions and variational inequalities。
- Dimitri P. Bertsekas, Nonlinear Programming, 3rd ed., Athena Scientific, 2016,§2.1,feasible directions and first-order necessary conditions。