Skip to content

一阶最优性条件

First-order optimality condition · Variational inequality optimality condition

以梯度和所有可行方向的非负内积充要刻画可微凸问题的全局极小点。

条目类型
定理

形式陈述

CRn 为非空凸集,凸函数 f 在包含 C 的开集上可微。点 xCfC 上的全局极小点,当且仅当

f(x),xx0,对所有 xC.

这称为变分不等式形式的一阶最优性条件。充分性来自凸函数的一阶下界

f(x)f(x)+f(x),xxf(x).

必要性则对任意 xC 考察 ϕ(t)=f(x+t(xx)):凸性保证 t[0,1] 可行,而 t=0 为单边极小点,故 ϕ(0+)0。若 C=Rn,可分别取 x=x±v,条件化为梯度 f(x)=0。在边界上梯度一般不为零;正确陈述是 f(x) 属于 Cx 处的法锥。

直觉

从候选点朝任意可行点走一小步,方向导数都不能为负;否则就存在立刻降低目标的可行方向。凸性把这一局部方向信息升级为全局证书,因为整条可行线段都留在 C 内,且切平面是全局下界。这里检验的不是有限个坐标方向,而是整个可行方向锥;在光滑边界上,目标的负梯度必须由边界法向力抵住。

无约束时可以朝梯度的正反两个方向试探,唯一可能是梯度为零。约束会破坏这种对称性:若某方向被集合挡住,即使梯度非零也可能已经无法下降。一阶条件说明“优化停止”是几何命题,而不是某个算法的退出代码。实际程序用小梯度或小投影梯度作为近似证书时,还要把容差、尺度和求值误差写清楚。

例子与边界

考虑

minx1,x2012((x12)2+(x2+1)2).

无约束极小点 (2,1) 不可行;候选 x=(2,0) 的梯度是 (0,1)。对任意可行 x

(0,1),x(2,0)=x20,

所以 x 是全局极小点,且目标值为 1/2。此处 f(x)0 并非失败,而是第二坐标的非负约束提供了相反法向。把同一问题误用无约束判据会错误地断言“尚未最优”。

凸性不能删除。f(x)=x3x=0 满足 f(0)=0,但任意负 x 都给更小函数值;一般非凸问题中零梯度只是局部极小的必要条件之一,还可能对应极大点或鞍点。不可微凸函数也不能硬写梯度,例如 |x| 在零点应使用 0f(0)。最后,这一条件刻画解,不保证解存在,也不保证任何迭代会到达它;开集上的下确界可能不取到。

推论与应用

对闭凸集 C 和步长 α>0,投影不动点

x=PC(xαf(x))

与变分不等式等价,因此投影梯度可以用固定点残差衡量近似最优。复合目标 g+h 则把条件改为 0g(x)+h(x);近端梯度映射为零正好见证这条包含关系。拟 Newton 方法解的也是 f(x)=0,但其矩阵近似和线搜索只是在寻找证书,不属于证书的定义。

误差结论必须注明指标。若强凸性成立,函数值误差能够控制 xx;只有普通凸性时,可能存在整片最优解,算法的函数值收敛并不自动指定迭代点收敛到哪一个。若程序报告梯度范数趋零,还需结合凸性、约束处理及解存在性,才可解释为全局最优逼近。

参考资料
  • 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。
关系图谱19 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系