047-方法-实用SQP方法

知识点概述

实用的SQP方法在局部SQP算法的基础上，引入了全局化策略，以保证从任意初始点都能收敛到解。主要的全局化策略是线搜索和信赖域。这两种策略都需要一个机制来平衡“目标函数下降”和“约束满足”这两个冲突的目标，这通常通过价值函数（Merit Function）或过滤器（Filter）来实现。此外，实用算法还需要处理QP子问题可能不可行或无界的情况。

教材原文

The SQP methods of the previous section are local: They require a starting point $(x_0,{\lambda }_0)$ that is close to a solution $(x^{\ast },{\lambda }^{\ast })$. To be practical, they must be embedded in a framework that promotes convergence from any starting point. The two main types of globalization strategies, line search and trust region, have both been applied successfully to SQP.

详细解释

1. 线搜索SQP (Line Search SQP)

   • 思想: 将QP子问题求出的解$p_k$作为搜索方向，然后沿着该方向进行线搜索，寻找一个合适的步长${\alpha }_k$。
   • 价值函数: 线搜索需要一个价值函数来评估步长的好坏。最常用的是**${\ell }_1$精确罚函数**： ${\varphi }_1(x;\mu )=f(x)+\mu \Vert c(x){\Vert }_1$ 其中$\mu$是罚参数。搜索方向$p_k$必须是${\varphi }_1$的一个下降方向。
   • 步长接受: 步长${\alpha }_k$需要满足Armijo条件，即保证${\varphi }_1$有充分的下降。
   • 挑战:
     1. Maratos效应: 在解附近，即使是单位步长${\alpha }_k=1$（这是实现超线性收敛所需要的）也可能被价值函数拒绝，因为它可能暂时增加了约束违反度。解决方法包括二阶校正步 (second-order correction) 或使用watchdog策略。
     2. Hessian近似: 必须保证QP子问题中的Hessian近似$B_k$是正定的，以确保QP子问题有解且解是下降方向。这通常通过BFGS更新并配合修正策略来实现。

2. 信赖域SQP (Trust-Region SQP)

   • 思想: 在每次迭代中，在一个信赖域内求解QP子问题。但这里存在一个根本困难：QP子问题可能因为约束的线性化而变得不可行，即使原始问题是可行的。
   • 处理不可行子问题:
     • 方法一：罚函数法 (Penalty Approach): 将QP子问题中的硬约束软化为${\ell }_1$罚函数形式，转化为一个有界约束的二次规划问题。这种方法在实践中很成功，但理论分析复杂。
     • 方法二：可行性恢复 (Feasibility Restoration): 设计一个两阶段的方法。首先尝试求解标准的QP子问题。如果不可行，则进入一个“可行性恢复”阶段，该阶段的目标是专门最小化约束违反度。
     • 方法三：S${\ell }_1$QP (Sequential ${\ell }_1$ Quadratic Programming): 这是目前最流行的方法之一。它直接将${\ell }_1$罚函数作为模型，构造一个包含${\ell }_1$罚项的QP子问题。这个子问题总是可行的。
   • 信赖域管理: 与无约束信赖域方法类似，根据模型（QP子问题的目标函数）的预测下降量与实际价值函数的下降量的比值来更新信赖域半径。

3. 过滤器SQP (Filter SQP)

   • 思想: 采用过滤器机制代替价值函数来决定是否接受一个步长。一个试探点$(x_k+p_k)$被接受，只要它的$(h,f)$值对（$h$是约束违反度，$f$是目标函数值）不被过滤器中的任何历史点所支配。
   • 优点: 避免了选择罚参数$\mu$的困难，并且在实践中表现出很好的性能。
   • 应用: 过滤器可以与信赖域框架或线搜索框架结合。

学习要点

• 全局化核心: 理解实用SQP方法必须解决的核心问题：(1) 平衡目标下降与约束满足；(2) 处理QP子问题可能遇到的困难（如Hessian非正定、子问题不可行）。
• 线搜索 vs. 信赖域: 掌握两种全局化策略在SQP背景下的具体实现和挑战。
  • 线搜索SQP：依赖价值函数，面临Maratos效应。
  • 信赖域SQP：面临QP子问题不可行的挑战，需要专门的策略（如S${\ell }_1$QP）来应对。
• 价值函数 vs. 过滤器: 了解这两种评估步长机制的优缺点。
• S${\ell }_1$QP: 记住S${\ell }_1$QP是解决信赖域SQP中子问题不可行性的一种流行且有效的方法。

实践应用

• SQP方法是求解中小型、稠密非线性规划问题的标准算法，被广泛认为是最高效的算法之一。
• SNOPT: 一个著名的、广泛使用的求解器，它是一个线搜索SQP的实现，具有处理大规模稀疏问题的能力。
• KNITRO: 一个功能强大的求解器，提供了多种算法选项，包括两种SQP算法（一种基于信赖域，一种基于线搜索）。
• FILTERSQP: 一个基于过滤器机制的SQP实现。

关联知识点

• 前置知识: 046-方法-局部SQP方法, 041-概念-罚函数与过滤器
• 后续知识: 048-方法-非线性规划的内点法 (作为另一大类主流算法)