MMA 优化算法
移动渐近线法(Method of Moving Asymptotes,MMA)是一种结构优化的优化策略。在每次迭代中,生成并求解严格凸逼近子问题,这些子问题生成由所谓的移动渐近线所控制。
这是一个三级算法: ? 外部迭代k使用当前控制变量估计xk来评估目标函数、约束及其梯度,并与当前渐近线估计lk和uk一起用于构造近似子问题。该子问题保证是凸可行的,并传递给内部迭代。 ? 每个内部迭代m为其唯一的最优xkm求解一个近似子问题,然后在此点评估真正的目标函数和约束。如果发现近似子问题与真函数值相比是保守的,则终止内部迭代,并接受该点作为下一个外部估计xk+1。否则,将修改近似子问题,使其更加保守,然后传递给下一个内部迭代。 ? 每个内部迭代中的子问题都使用对偶活动集策略进行求解。逼近子问题是非线性和不等式约束的,但其特殊的结构使得求解固定对偶变量的原问题非常快。从原始问题的解出发,可以计算对偶问题的梯度和全Hessian,该对偶问题使用改进的Newton主动集算法求解。 请注意,函数(目标和约束)梯度在每个外部迭代中严格计算一次,而函数值必须在每个额外的内部迭代中计算一次。最内层只看到子问题的解析近似形式,其中当前函数和梯度估计出现在各种系数中。 生成的逼近子问题的特殊结构影响算法的全局行为。与SNOPT和Levenberg–Marquardt解算器相比,MMA本质上是一种线性方法,它们依赖于关于目标函数的二阶近似信息。它的子问题是原始问题的线性近似,但具有由移动渐近线控制的屏障式有理函数贡献。除了渐近线的当前位置外,在外部迭代之间没有保留有关问题的信息。 在实践中,这意味着MMA不会显示出与类牛顿方法相关的接近最优值的二次收敛性。事实上,目标函数中有一个由二次项支配的非常简单的问题,MMA收敛速度非常慢或根本不收敛。特别是,为了使MMA有效工作,必须在优化界面中使用最小二乘目标特征来描述最小二乘问题。这些特性触发了问题的重新表述,使之成为更适合MMA的形式。此外,如果缺陷是复数的,MMA内部只使用实部。 由于目标函数的线性近似,每个外部MMA迭代中的第一个内部迭代有效地进入可行集的一个角,在那里它完全受约束和简单边界的约束。如果发现该点是非保守的,就像目标函数在可行集内部具有最优值的凸函数一样,内部迭代会生成一系列逐渐远离约束的迭代,直到找到保守点。这种行为倾向于接近约束的点,而SNOPT中使用的线搜索和Levenberg–Marquardt中的信赖域则倾向于接近上一次迭代的点。如果目标函数具有多个局部极小值,则可以期望不同的方法找到不同的局部解。