2025-11-10T02:40:59.086485

Approximate stationarity in disjunctive optimization: concepts, qualification conditions, and application to MPCCs

Käming, Mehlitz
In this paper, we are concerned with stationarity conditions and qualification conditions for optimization problems with disjunctive constraints. This class covers, among others, optimization problems with complementarity, vanishing, or switching constraints, which are notoriously challenging due to their highly combinatorial structure. The focus of our study is twofold. First, we investigate approximate stationarity conditions and the associated strict constraint qualifications which can be used to infer stationarity of local minimizers. While such concepts are already known in the context of so-called Mordukhovich-stationarity, we introduce suitable extensions associated with strong stationarity. Second, a qualification condition is established which, based on an approximately Mordukhovich- or strongly stationary point, can be used to infer its Mordukhovich- or strong stationarity, respectively. In contrast to the aforementioned strict constraint qualifications, this condition depends on the involved sequences justifying approximate stationarity and, thus, is not a constraint qualification in the narrower sense. However, it is much easier to verify as it merely requires to check the (positive) linear independence of a certain family of gradients. In order to illustrate the obtained findings, they are applied to optimization problems with complementarity constraints, where they can be naturally extended to the well-known concepts of weak and Clarke-stationarity.
academic

Approximate stationarity in disjunctive optimization: concepts, qualification conditions, and application to MPCCs

基本信息

  • 论文ID: 2503.22551
  • 标题: Approximate stationarity in disjunctive optimization: concepts, qualification conditions, and application to MPCCs
  • 作者: Isabella Käming (TU Dresden), Patrick Mehlitz (Philipps-Universität Marburg)
  • 分类: math.OC (Optimization and Control)
  • 发表时间: October 14, 2025
  • 论文链接: https://arxiv.org/abs/2503.22551

摘要

本文研究了析取约束优化问题的稳定性条件和限定条件。这类问题包括互补约束、消失约束或切换约束的优化问题，由于其高度组合结构而具有挑战性。研究重点有两个方面：首先，研究近似稳定性条件及相关的严格约束限定条件，可用于推断局部最小值的稳定性。虽然在Mordukhovich稳定性背景下已知此类概念，但本文引入了与强稳定性相关的适当扩展。其次，建立了一个限定条件，基于近似Mordukhovich或强稳定点，可分别推断其Mordukhovich或强稳定性。

研究背景与动机

问题定义

本文研究的核心问题是析取约束优化问题(DP)：

min f(x) s.t. F(x) ∈ Γ := ⋃_{j=1}^t Γ_j

其中f: ℝⁿ → ℝ和F: ℝⁿ → ℝˡ是连续可微的，Γ₁,...,Γₜ ⊂ ℝˡ是凸多面体集合。

研究动机

  1. 实际重要性: 析取约束优化涵盖多个重要的应用领域，包括：
    • 互补约束问题(MPCCs)
    • 消失约束问题
    • 切换约束问题
    • 基数约束问题
  2. 理论挑战: 这类问题由于其组合结构而在理论分析上极具挑战性，传统的约束限定条件往往过于严格或难以验证。
  3. 现有方法局限:
    • 现有的AM-regularity需要控制无穷多个序列，实际应用中难以验证
    • 强稳定性的必要条件缺乏系统性研究
    • 缺乏易于验证的限定条件

核心贡献

  1. 引入新的近似稳定性概念: 提出了严格近似强稳定性(SAS-stationarity)的概念，扩展了已知的近似Mordukhovich稳定性理论。
  2. 建立新的限定条件: 提出了子集Mangasarian-Fromovitz条件(subMFC)，相比传统的AM-regularity更容易验证。
  3. 理论关系分析: 系统分析了各种近似稳定性概念之间的关系，以及它们与精确稳定性的联系。
  4. MPCC应用: 将理论结果应用于互补约束优化问题，扩展了弱稳定性和Clarke稳定性的近似版本。
  5. 独立性结果: 证明了新提出的subMFC与AM-regularity和AS-regularity相互独立，在某些情况下更具优势。

方法详解

任务定义

研究析取约束优化问题的稳定性理论，特别是：

  • 输入：可行点x̄和目标函数f
  • 输出：稳定性类型的判定和相应的限定条件
  • 约束：F(x) ∈ Γ := ⋃_^t Γ_j

核心理论框架

1. 稳定性概念层次

论文建立了以下稳定性概念的层次结构：

S-stationary ⟹ M-stationary (精确稳定性)
    ⇑              ⇑
SAS-stationary ⟹ AM-stationary (近似稳定性)

2. 近似稳定性定义

定义3.6 (近似稳定性)：

  • AM-stationary: 存在近似M-稳定序列{(xᵏ,λᵏ,δᵏ,εᵏ)}满足：
    • εᵏ = ∇f(xᵏ) + F'(xᵏ)ᵀλᵏ
    • λᵏ ∈ N_Γ(F(xᵏ) - δᵏ)
    • (xᵏ,δᵏ,εᵏ) → (x̄,0,0)
  • SAS-stationary: 存在严格近似S-稳定序列{(xᵏ,λᵏ,εᵏ)}满足：
    • εᵏ = ∇f(xᵏ) + F'(xᵏ)ᵀλᵏ
    • λᵏ ∈ N̂_Γ(F(x̄))
    • (xᵏ,εᵏ) → (x̄,0)

3. 限定条件(ODP-subMFC)

定义4.3：对于AM-稳定点x̄，ODP-subMFC成立当且仅当存在I ⊂ I_∃(x̄)和序列{(xᵏ,λᵏ,δᵏ,εᵏ)}使得：

(i) 要么I = ∅，要么对所有u ∈ ℝˡ \ {0}满足u ≥ 0且u_{ℓ\I} = 0时：

0 ≠ ∑_{i∈I} sgn(λᵢᵏ)uᵢ∇Fᵢ(x̄)

(ii) 序列是近似M-稳定的且I = I_∃(xᵏ,δᵏ)

技术创新点

  1. SAS-stationarity的引入: 首次系统性地研究了强稳定性的近似版本，填补了理论空白。
  2. subMFC的实用性: 相比需要控制所有可能序列的AM-regularity，subMFC只需验证特定序列的梯度线性无关性。
  3. 序列依赖的限定条件: 虽然不是传统意义的约束限定，但更适合算法生成的序列验证。

实验设置

理论验证方法

论文主要通过理论分析和具体例子来验证结果：

  1. 例子3.10: 展示AM-稳定但不SAS-稳定的点
  2. 例子3.13: 说明AM-regularity和AS-regularity的独立性
  3. 例子4.8: 证明M-稳定性不总是蕴含ODP-subMFC
  4. 例子4.11: 演示subMFC在算法序列验证中的应用

对比分析

论文系统比较了：

  • 新概念与现有AM-stationarity的关系
  • subMFC与传统LICQ、AM-regularity的强弱关系
  • 不同稳定性概念在MPCC中的表现

实验结果

主要理论结果

1. 必要性结果

定理3.9: 如果x̄是(DP)的局部最小值，则x̄是AM-稳定的。

推论3.8: 如果x̄是SAS-稳定的，则它是AM-稳定的。当t=1时，反之亦然。

2. 充分性结果

定理4.5: 设x̄是AM-稳定点且ODP-subMFC成立，则：

  • x̄是M-稳定的
  • 如果相关序列是严格近似S-稳定的，则x̄是S-稳定的

3. 独立性结果

命题4.10: ODP-subMFC与AM-regularity和AS-regularity相互独立。

MPCC应用结果

1. 概念等价性

引理5.3-5.5: 证明了论文定义的近似稳定性概念与文献中已知概念的等价性：

  • AW-stationarity ⟺ 7, Definition 3.2
  • AC-stationarity ⟺ 7, Definition 3.3
  • AM-stationarity ⟺ 7, Definition 3.3

2. MPCC-subMFC的有效性

定理5.11: MPCC-subMFC可以从不同类型的近似稳定性推导出相应的精确稳定性。

案例分析

例子4.11 (算法序列验证): 考虑问题：

min x s.t. (x, -x²) ∈ Γ₁ ∪ Γ₂

其中Γ₁ = ℝ₊ × ℝ, Γ₂ = ℝ × ℝ₊

对于算法生成的序列xᵏ = -1/k, λᵏ = (-1,0)，虽然AM-regularity不成立，但通过subMFC可以验证M-稳定性。

相关工作

主要研究方向

  1. 析取优化理论: Flegel, Kanzow, Outrata (2007)的开创性工作
  2. 近似稳定性: Mehlitz (2020)的AM-regularity理论
  3. MPCC理论: Andreani等人关于sequential optimality conditions的研究
  4. 约束限定条件: 从LICQ到各种弱化版本的发展

本文优势

  1. 系统性: 首次系统研究强稳定性的近似理论
  2. 实用性: 提出更易验证的限定条件
  3. 一般性: 统一处理多种约束类型
  4. 完整性: 从理论到应用的完整框架

结论与讨论

主要结论

  1. 理论完整性: 建立了析取优化中近似稳定性的完整理论框架
  2. 实用价值: subMFC为算法分析提供了新工具
  3. 应用广泛: 理论可应用于多种约束类型

局限性

  1. SAS-stationarity的必要性: 不是所有局部最小值都满足SAS-稳定性
  2. subMFC的序列依赖性: 不是传统意义的约束限定条件
  3. 计算复杂性: 某些限定条件的验证仍然复杂

未来方向

  1. 算法设计: 开发保证SAS-稳定性的算法
  2. 非光滑推广: 扩展到Lipschitz函数情况
  3. 计算方法: 开发高效的限定条件验证算法

深度评价

优点

  1. 理论创新: SAS-stationarity概念填补了重要理论空白
  2. 实用价值: subMFC比传统方法更易验证
  3. 系统性强: 完整的理论框架和层次结构
  4. 应用广泛: 统一处理多种重要的约束类型
  5. 严谨性: 数学证明严密，例子丰富

不足

  1. 计算复杂性: 某些概念的实际计算仍然困难
  2. 算法指导: 缺乏具体的算法实现指导
  3. 数值实验: 主要是理论分析，缺乏大规模数值验证

影响力

  1. 理论贡献: 为析取优化理论发展提供重要推进
  2. 实用价值: 为算法分析提供新工具
  3. 学科影响: 可能影响相关优化子领域的发展

适用场景

  1. 算法分析: 验证优化算法的收敛性质
  2. 理论研究: 作为进一步理论发展的基础
  3. 应用问题: 处理具有复杂约束结构的实际优化问题

参考文献

论文引用了41篇相关文献，主要包括：

  • Flegel, Kanzow, Outrata (2007): 析取优化的开创性工作
  • Mehlitz (2020): AM-regularity理论
  • Andreani等人的MPCC相关研究
  • Mordukhovich, Rockafellar & Wets的变分分析基础理论

这篇论文在析取约束优化理论方面做出了重要贡献，特别是在近似稳定性和限定条件方面提供了新的理论工具和实用方法。虽然主要是理论性工作，但为算法设计和分析提供了有价值的框架。