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

Basic Information

• Paper ID: 2503.22551
• Title: Approximate stationarity in disjunctive optimization: concepts, qualification conditions, and application to MPCCs
• Authors: Isabella Käming (TU Dresden), Patrick Mehlitz (Philipps-Universität Marburg)
• Classification: math.OC (Optimization and Control)
• Publication Date: October 14, 2025
• Paper Link: https://arxiv.org/abs/2503.22551

Abstract

This paper investigates stationarity conditions and qualification conditions for disjunctive constraint optimization problems. These problems encompass optimization with complementarity constraints, vanishing constraints, or switching constraints, which are challenging due to their highly combinatorial structure. The research focuses on two main aspects: First, the study of approximate stationarity conditions and associated strict constraint qualification conditions that can be used to infer stationarity of local minima. While such concepts are known in the context of Mordukhovich stationarity, this paper introduces appropriate extensions related to strong stationarity. Second, the paper establishes qualification conditions based on approximate Mordukhovich or strong stationary points that can respectively imply their Mordukhovich or strong stationarity.

Research Background and Motivation

Problem Definition

The core problem studied in this paper is the disjunctive constraint optimization problem (DP):

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

where f: ℝⁿ → ℝ and F: ℝⁿ → ℝˡ are continuously differentiable, and Γ₁,...,Γₜ ⊂ ℝˡ are convex polyhedral sets.

Research Motivation

1. Practical Importance: Disjunctive constraint optimization encompasses multiple important application domains, including:
   • Mathematical Programs with Complementarity Constraints (MPCCs)
   • Vanishing constraint problems
   • Switching constraint problems
   • Cardinality constraint problems
2. Theoretical Challenges: These problems are theoretically challenging due to their combinatorial structure, and traditional constraint qualification conditions are often too restrictive or difficult to verify.
3. Limitations of Existing Approaches:
   • Existing AM-regularity requires controlling infinitely many sequences, which is difficult to verify in practice
   • Necessary conditions for strong stationarity lack systematic study
   • Lack of easily verifiable qualification conditions

Core Contributions

1. Introduction of New Approximate Stationarity Concepts: Proposes the concept of strictly approximate strong stationarity (SAS-stationarity), extending known approximate Mordukhovich stationarity theory.
2. Establishment of New Qualification Conditions: Proposes the subset Mangasarian-Fromovitz condition (subMFC), which is easier to verify compared to traditional AM-regularity.
3. Analysis of Theoretical Relationships: Systematically analyzes relationships among various approximate stationarity concepts and their connections to exact stationarity.
4. MPCC Applications: Applies theoretical results to complementarity constraint optimization problems, extending approximate versions of weak stationarity and Clarke stationarity.
5. Independence Results: Proves that the newly proposed subMFC is independent of AM-regularity and AS-regularity, offering advantages in certain cases.

Methodology Details

Task Definition

Study the stationarity theory of disjunctive constraint optimization problems, specifically:

• Input: feasible point x̄ and objective function f
• Output: determination of stationarity type and corresponding qualification conditions
• Constraints: F(x) ∈ Γ := ⋃_^t Γ_j

Core Theoretical Framework

1. Hierarchy of Stationarity Concepts

The paper establishes the following hierarchy of stationarity concepts:

S-stationary ⟹ M-stationary (exact stationarity)
    ⇑              ⇑
SAS-stationary ⟹ AM-stationary (approximate stationarity)

2. Approximate Stationarity Definitions

Definition 3.6 (Approximate Stationarity):

• AM-stationary: There exists an approximate M-stationary sequence {(xᵏ,λᵏ,δᵏ,εᵏ)} satisfying:
  • εᵏ = ∇f(xᵏ) + F'(xᵏ)ᵀλᵏ
  • λᵏ ∈ N_Γ(F(xᵏ) - δᵏ)
  • (xᵏ,δᵏ,εᵏ) → (x̄,0,0)
• SAS-stationary: There exists a strictly approximate S-stationary sequence {(xᵏ,λᵏ,εᵏ)} satisfying:
  • εᵏ = ∇f(xᵏ) + F'(xᵏ)ᵀλᵏ
  • λᵏ ∈ N̂_Γ(F(x̄))
  • (xᵏ,εᵏ) → (x̄,0)

3. Qualification Condition (ODP-subMFC)

Definition 4.3: For an AM-stationary point x̄, ODP-subMFC holds if and only if there exist I ⊂ I_∃(x̄) and a sequence {(xᵏ,λᵏ,δᵏ,εᵏ)} such that:

(i) Either I = ∅, or for all u ∈ ℝˡ \ {0} satisfying u ≥ 0 and u_{ℓ\I} = 0:

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

(ii) The sequence is approximately M-stationary and I = I_∃(xᵏ,δᵏ)

Technical Innovations

1. Introduction of SAS-stationarity: First systematic study of approximate versions of strong stationarity, filling an important theoretical gap.
2. Practicality of subMFC: Compared to AM-regularity which requires controlling all possible sequences, subMFC only requires verifying linear independence of gradients for specific sequences.
3. Sequence-Dependent Qualification Conditions: While not a qualification condition in the traditional sense, it is better suited for verifying sequences generated by algorithms.

Experimental Setup

Theoretical Verification Methods

The paper primarily employs theoretical analysis and concrete examples to verify results:

1. Example 3.10: Demonstrates a point that is AM-stationary but not SAS-stationary
2. Example 3.13: Illustrates the independence of AM-regularity and AS-regularity
3. Example 4.8: Proves that M-stationarity does not always imply ODP-subMFC
4. Example 4.11: Demonstrates the application of subMFC in verifying algorithmic sequences

Comparative Analysis

The paper systematically compares:

• Relationships between new concepts and existing AM-stationarity
• Relative strength of subMFC versus traditional LICQ and AM-regularity
• Performance of different stationarity concepts in MPCCs

Experimental Results

Main Theoretical Results

1. Necessity Results

Theorem 3.9: If x̄ is a local minimum of (DP), then x̄ is AM-stationary.

Corollary 3.8: If x̄ is SAS-stationary, then it is AM-stationary. The converse holds when t=1.

2. Sufficiency Results

Theorem 4.5: Let x̄ be an AM-stationary point and ODP-subMFC hold. Then:

• x̄ is M-stationary
• If the relevant sequence is strictly approximately S-stationary, then x̄ is S-stationary

3. Independence Results

Proposition 4.10: ODP-subMFC is independent of both AM-regularity and AS-regularity.

MPCC Application Results

1. Concept Equivalence

Lemmas 5.3-5.5: Prove equivalence between approximate stationarity concepts defined in this paper and known concepts in the literature:

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

2. Effectiveness of MPCC-subMFC

Theorem 5.11: MPCC-subMFC can derive corresponding exact stationarity from different types of approximate stationarity.

Case Study

Example 4.11 (Algorithmic Sequence Verification): Consider the problem:

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

where Γ₁ = ℝ₊ × ℝ, Γ₂ = ℝ × ℝ₊

For the algorithmically generated sequence xᵏ = -1/k, λᵏ = (-1,0), although AM-regularity does not hold, M-stationarity can be verified through subMFC.

Related Work

Main Research Directions

1. Disjunctive Optimization Theory: Pioneering work by Flegel, Kanzow, Outrata (2007)
2. Approximate Stationarity: AM-regularity theory by Mehlitz (2020)
3. MPCC Theory: Research on sequential optimality conditions by Andreani et al.
4. Constraint Qualification Conditions: Development from LICQ to various weakened versions

Advantages of This Paper

1. Systematicity: First systematic study of approximate theory of strong stationarity
2. Practicality: Proposes more easily verifiable qualification conditions
3. Generality: Unified treatment of multiple constraint types
4. Completeness: Complete framework from theory to applications

Conclusions and Discussion

Main Conclusions

1. Theoretical Completeness: Establishes a complete theoretical framework for approximate stationarity in disjunctive optimization
2. Practical Value: subMFC provides new tools for algorithm analysis
3. Broad Applicability: Theory applicable to multiple constraint types

Limitations

1. Necessity of SAS-stationarity: Not all local minima satisfy SAS-stationarity
2. Sequence-Dependence of subMFC: Not a qualification condition in the traditional sense
3. Computational Complexity: Verification of certain qualification conditions remains complex

Future Directions

1. Algorithm Design: Develop algorithms that guarantee SAS-stationarity
2. Nonsmooth Extensions: Extend to Lipschitz function cases
3. Computational Methods: Develop efficient algorithms for verifying qualification conditions

In-Depth Evaluation

Strengths

1. Theoretical Innovation: SAS-stationarity concept fills an important theoretical gap
2. Practical Value: subMFC is easier to verify than traditional methods
3. Strong Systematicity: Complete theoretical framework with clear hierarchy
4. Broad Applicability: Unified treatment of multiple important constraint types
5. Rigor: Rigorous mathematical proofs with abundant examples

Weaknesses

1. Computational Complexity: Practical computation of certain concepts remains difficult
2. Algorithm Guidance: Lacks concrete algorithmic implementation guidance
3. Numerical Experiments: Primarily theoretical analysis with limited large-scale numerical verification

Impact

1. Theoretical Contribution: Provides important advancement to disjunctive optimization theory
2. Practical Value: Provides new tools for algorithm analysis
3. Disciplinary Impact: May influence development of related optimization subfields

Applicable Scenarios

1. Algorithm Analysis: Verification of convergence properties of optimization algorithms
2. Theoretical Research: Foundation for further theoretical development
3. Applied Problems: Handling practical optimization problems with complex constraint structures

References

The paper cites 41 related references, primarily including:

• Flegel, Kanzow, Outrata (2007): Pioneering work on disjunctive optimization
• Mehlitz (2020): AM-regularity theory
• MPCC-related research by Andreani et al.
• Foundational variational analysis theory by Mordukhovich, Rockafellar & Wets

This paper makes important contributions to disjunctive constraint optimization theory, particularly providing new theoretical tools and practical methods in approximate stationarity and qualification conditions. While primarily theoretical, it provides a valuable framework for algorithm design and analysis.