一阶最优性度量

什么是一阶最优性度量？

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

一阶最优性度量必须至少为零。
一阶最优性等于零的点不一定是最小值。

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

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

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

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

目标函数在 x0 处的梯度的无穷范数（最大值）
求解器的输入的无穷范数（最大值），例如 linprog 中的 f 或 b 或者 quadprog 中的 H

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

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

无约束最优性

对于平滑无约束问题

$\min_{x} f (x),$

一阶最优性度量是 ∇f(x) 的无穷范数（意味着最大绝对值），即：

$first-order optimality measure = \max_{i} | {(\nabla f (x))}_{i} | = {‖ \nabla f (x) ‖}_{\infty} .$

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

受约束的最优性理论

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

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

$\min_{x} f (x) subject to g (x) \leq 0, h (x) = 0.$

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

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

L (x, λ) = f (x) + \sum λ_{g, i} g_{i} (x) + \sum λ_{h, i} h_{i} (x) .

(1)

向量 λ（它是 λ_g 和 λ_h 的串联）是拉格朗日乘数向量。它的长度是约束的总数。

KKT 条件是：

\nabla_{x} L (x, λ) = 0,

(2)

λ_{g, i} g_{i} (x) = 0 \forall i,

(3)

{\begin{matrix} g (x) \leq 0, \\ h (x) = 0, \\ λ_{g, i} \geq 0. \end{matrix}

(4)

求解器在计算最优性度量时不使用公式 4 中的三个表达式。

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

‖ \nabla_{x} L (x, λ) ‖ = ‖ \nabla f (x) + \sum λ_{g, i} \nabla g_{i} (x) + \sum λ_{h, i} \nabla h_{h, i} (x) ‖ .

(5)

与公式 3 相关联的最优性度量为

‖ \vec{λ_{g} g} (x) ‖,

(6)

其中公式 6 中的范数表示向量

\vec{λ_{g, i} g_{i}} (x)

的无穷范数（最大值）。

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

求解器形式的约束最优性

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

\begin{array}{l} ‖ \nabla_{x} L (x, λ) ‖ = ‖ \nabla f (x) + A^{T} λ_{i n e q l i n} + A e q^{T} λ_{e q l i n} \\ + \sum λ_{i n e q n o n l i n, i} \nabla c_{i} (x) + \sum λ_{e q n o n l i n, i} \nabla c e q_{i} (x) ‖, \end{array}

(7)

‖ \vec{| l_{i} - x_{i} | λ_{l o w e r, i}}, \vec{| x_{i} - u_{i} | λ_{u p p e r, i}}, \vec{| {(A x - b)}_{i} | λ_{i n e q l i n, i}}, \vec{| c_{i} (x) | λ_{i n e q n o n l i n, i}} ‖,

(8)

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

仅线性等式

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

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

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

$v_{i} = {\begin{array}{l} | x_{i} - b_{i} | & if the negative gradient points toward bound b_{i} \\ 1 & otherwise . \end{array}$

如果 x_i 位于边界上，则 v_i 为零。如果 x_i 不在边界上，则在最小化点上，梯度 g_i 应为零。因此，一阶最优性度量在最小化点上应为零。