Main Content

一阶最优性测度

什么是一阶最优性测度?

一阶最优性用于测量点 x 与最优点的接近程度。大多数 Optimization Toolbox™ 求解器都使用此测度,尽管它对不同算法有不同定义。一阶最优性是必要条件,但不是充分条件。换言之:

  • 一阶最优性测度必须至少为零。

  • 一阶最优性等于零的点不一定是最小值。

有关一阶最优性的一般信息,请参阅 Nocedal 和 Wright 的合著 [31]。有关 Optimization Toolbox 求解器的一阶最优性测度的详细信息,请参阅无约束最优性受约束的最优性理论求解器形式的约束最优性

与一阶最优性相关的停止规则

OptimalityTolerance 容差与一阶最优性测度相关。通常,如果一阶最优性测度小于 OptimalityTolerance,则求解器迭代结束。

一些求解器或算法使用相对一阶最优性作为停止条件。如果一阶最优性测度小于 μ 乘以 OptimalityTolerance,则求解器迭代结束;其中 μ 为:

  • 目标函数在 x0 处的梯度的无穷范数(最大值)

  • 求解器的输入的无穷范数(最大值),例如 linprog 中的 fb 或者 quadprog 中的 H

相对测度尝试解释问题的规模。如果采用相对停止标准,将目标函数乘以很大或很小的数不会改变停止条件,如果采用未经缩放的标准,则会改变停止条件。

具有增强版退出消息的求解器会在停止标准详细信息中指出它们何时使用相对一阶最优性。

无约束最优性

对于平滑无约束问题

minxf(x),

一阶最优性测度是 ∇f(x) 的无穷范数(意味着最大绝对值),即:

first-order optimality measure = maxi|(f(x))i|=f(x).

此最优性测度基于平滑函数达到最小值的熟悉条件:其梯度必须为零。对于无约束问题,当一阶最优性测度接近于零时,目标函数的梯度接近于零,因此目标函数可能接近最小值。如果一阶最优性测度并不小,则目标函数不是最小值。

受约束的最优性理论

本节简述约束问题的一阶最优性测度定义的理论基础。有关 Optimization Toolbox 函数中使用的定义,请参阅求解器形式的约束最优性

对于平滑约束问题,使 g 和 h 分别是表示所有不等式和等式约束(指边界、线性和非线性约束)的向量函数:

minxf(x) subject to g(x)0, h(x)=0.

在这种情况下,一阶最优性的含义比无约束问题更复杂。该定义基于卡鲁什-库恩-塔克 (KKT) 条件。KKT 条件类似于梯度的最小值必须为零的条件,修正为考虑约束条件。不同之处在于 KKT 条件适用于约束问题。

KKT 条件使用辅助拉格朗日函数:

L(x,λ)=f(x)+λg,igi(x)+λh,ihi(x).(1)
向量 λ(它是 λg 和 λh 的串联)是拉格朗日乘数向量。它的长度是约束的总数。

KKT 条件是:

xL(x,λ)=0,(2)
λg,igi(x)=0 i,(3)
{g(x)0,h(x)=0,λg,i0.(4)
求解器在计算最优性测度时不使用公式 4 中的三个表达式。

公式 2 相关联的最优性测度为

xL(x,λ)=f(x)+λg,igi(x)+λh,ihh,i(x).(5)
公式 3 相关联的最优性测度为
λgg(x),(6)
其中公式 6 中的范数表示向量 λg,igi(x) 的无穷范数(最大值)。

合并的最优性测度是在公式 5公式 6 中计算的最大值。接受非线性约束函数的求解器将约束违反值 g(x) > 0|h(x)| > 0 报告为 ConstraintTolerance 违反。请参阅容差和停止条件

求解器形式的约束最优性

大多数约束工具箱求解器将其一阶最优性测度的计算分为边界、线性函数和非线性函数。该测度是以下两个范数中的最大值,这两个范数对应于公式 5公式 6

xL(x,λ)=f(x)+ATλineqlin+AeqTλeqlin                       +λineqnonlin,ici(x)+λeqnonlin,iceqi(x),(7)
|lixi|λlower,i,|xiui|λupper,i,|(Axb)i|λineqlin,i,|ci(x)|λineqnonlin,i,(8)

其中,公式 7公式 8 中向量的范数是无穷范数(最大值)。拉格朗日乘数上的下标对应于求解器拉格朗日乘数结构体。请参阅拉格朗日乘数结构体公式 7 中的求和范围涵盖所有约束。如果边界是 ±Inf,则该项不受约束,因此它不是求和的一部分。

仅线性等式

对于一些只具有线性等式的大规模问题,一阶最优性测度是投影梯度的无穷范数。换句话说,一阶最优性测度是投影到 Aeq 的零空间上的梯度的大小。

有界最小二乘和信赖域反射求解器

对于最小二乘求解器和信赖域反射算法,在仅具有边界的问题中,一阶最优性测度是最大值除以 |vi*gi| 的 i。此处,gi 是梯度的第 i 个分量,x 是当前点,并且

vi={|xibi|if the negative gradient points toward bound bi1otherwise.

如果 xi 位于边界上,则 vi 为零。如果 xi 不在边界上,则在最小化点上,梯度 gi 应为零。因此,一阶最优性测度在最小化点上应为零。

相关主题