用于模式搜索的非线性约束求解算法
模式搜索算法采用增广拉格朗日模式搜索 (ALPS) 算法来解决非线性约束问题。ALPS 算法求解的优化问题是
使得
其中 c(x) 表示非线性不等式约束,ceq(x) 表示等式约束,m 为非线性不等式约束的数量,mt 为非线性约束的总数。
ALPS 算法尝试解决具有非线性约束、线性约束和边界的非线性优化问题。在这种方法中,边界和线性约束与非线性约束分开处理。利用拉格朗日函数和惩罚参数,将目标函数和非线性约束函数结合起来,形成一个子问题。使用模式搜索算法近似最小化一系列此类优化问题,以满足线性约束和边界。
每个子问题的解代表一次迭代。因此,使用非线性约束时,每次迭代的函数计算次数要比其他情况高得多。
子问题公式定义为
其中
向量 λi 的分量 λ 是非负的,称为拉格朗日乘数估计
向量 si 的元素 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.