用于模式搜索的非线性约束求解算法

模式搜索算法采用增广拉格朗日模式搜索 (ALPS) 算法来解决非线性约束问题。ALPS 算法求解的优化问题是

$\min_{x} f (x)$

使得

$\begin{matrix} c_{i} (x) \leq 0, i = 1 \dots m \\ c e q_{i} (x) = 0, i = m + 1 \dots m t \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b, \end{matrix}$

其中 c(x) 表示非线性不等式约束，ceq(x) 表示等式约束，m 为非线性不等式约束的数量，mt 为非线性约束的总数。

ALPS 算法尝试解决具有非线性约束、线性约束和边界的非线性优化问题。在这种方法中，边界和线性约束与非线性约束分开处理。利用拉格朗日函数和惩罚参数，将目标函数和非线性约束函数结合起来，形成一个子问题。使用模式搜索算法近似最小化一系列此类优化问题，以满足线性约束和边界。

每个子问题的解代表一次迭代。因此，使用非线性约束时，每次迭代的函数计算次数要比其他情况高得多。

子问题公式定义为

$Θ (x, λ, s, ρ) = f (x) - \sum_{i = 1}^{m} λ_{i} s_{i} \log (s_{i} - c_{i} (x)) + \sum_{i = m + 1}^{m t} λ_{i} c e q_{i} (x) + \frac{ρ}{2} \sum_{i = m + 1}^{m t} c e q_{i} {(x)}^{2},$

其中

向量 λ_i 的分量 λ 是非负的，称为拉格朗日乘数估计
向量 s_i 的元素 s 是非负移位
ρ 是正惩罚参数。

该算法首先使用惩罚参数 (InitialPenalty) 的初始值。

模式搜索最小化一系列子问题，每个子问题都是原始问题的近似值。每个子问题都有一个固定的值 λ、s 和 ρ。当子问题最小化到所需的精度并满足可行性条件时，拉格朗日估计会更新。否则，惩罚参数将增加一个惩罚因子 (PenaltyFactor)。这导致了一个新的子问题表述和最小化问题。重复这些步骤直到满足停止条件。

每个子问题的解代表一次迭代。因此，使用非线性约束时，每次迭代的函数计算次数要比其他情况高得多。

有关该算法的完整描述，请参阅以下参考资料：

参考

[1] Kolda, Tamara G., Robert Michael Lewis, and Virginia Torczon. “A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints.” Technical Report SAND2006-5315, Sandia National Laboratories, August 2006.

[2] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. “A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds,” SIAM Journal on Numerical Analysis, Volume 28, Number 2, pages 545–572, 1991.

[3] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. “A Globally Convergent Augmented Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds,” Mathematics of Computation, Volume 66, Number 217, pages 261–288, 1997.

用于模式搜索的非线性约束求解算法

参考

另请参阅

主题