模式搜索算法采用增广拉格朗日模式搜索(ALPS)算法求解非线性约束问题。阿尔卑斯算法求解的优化问题为
这样
在哪里c(x)表示非线性不等式约束,量表信(x)表示等式约束,米是非线性不等式约束的个数,和太为非线性约束的总数。
阿尔卑斯算法试图解决非线性优化问题与非线性约束,线性约束,和界限。在这种方法中,边界和线性约束与非线性约束分开处理。利用拉格朗日函数和罚参数,将目标函数和非线性约束函数结合,形成子问题。利用模式搜索算法对这类优化问题序列进行近似最小化,使其满足线性约束和边界。
每个子问题解代表一次迭代。因此,使用非线性约束时,每次迭代的函数求值次数要比不使用非线性约束时高得多。
子问题公式定义为
在哪里
的组件λ我向量的λ是非负的,被称为拉格朗日乘数估计
的元素年代我向量的年代都是非负的转变
ρ为正惩罚参数。
算法首先使用惩罚参数的初始值(InitialPenalty
).
模式搜索使子问题序列最小化,每个子问题都是原始问题的近似。每个子问题都有一个固定的值λ,年代,ρ.当子问题最小化到要求的精度并满足可行性条件时,修正拉格朗日估计。否则,惩罚参数将增加一个惩罚因子(PenaltyFactor
).这导致了一个新的子问题的公式化和极小化问题。重复这些步骤,直到满足停止条件。
每个子问题解代表一次迭代。因此,使用非线性约束时,每次迭代的函数求值次数要比不使用非线性约束时高得多。
关于算法的完整描述,请参见以下参考文献:
科尔达,塔玛拉·G,罗伯特·迈克尔·刘易斯和弗吉尼亚·托尔松。一种集直接搜索增广拉格朗日算法,用于结合一般约束和线性约束进行优化。SAND2006-5315技术报告,桑迪亚国家实验室,2006年8月。
康,A. R., N. i.m. Gould,和博士L. Toint。具有一般约束和简单边界的全局收敛增广拉格朗日优化算法数值分析学报, 1991年第28卷第2期545-572页。
康,A. R., N. i.m. Gould,和博士L. Toint。具有一般不等式约束和简单边界的全局收敛增广拉格朗日势垒优化算法数学的计算, 1997年第66卷,第217号,261-288页。