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

विच्छेदक अनुकूलन में अनुमानित स्थिरता: अवधारणाएं, योग्यता शर्तें, और 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 (अनुकूलन और नियंत्रण)
प्रकाशन तिथि: 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: ℝⁿ → ℝˡ सतत अवकलनीय हैं, और Γ₁,...,Γₜ ⊂ ℝˡ उत्तल बहुफलकीय समुच्चय हैं।

अनुसंधान प्रेरणा

व्यावहारिक महत्व: विच्छेदक बाध्यता अनुकूलन कई महत्वपूर्ण अनुप्रयोग क्षेत्रों को शामिल करता है:
- पूरक बाध्यता समस्याएं (MPCCs)
- लुप्त होने वाली बाध्यता समस्याएं
- स्विचिंग बाध्यता समस्याएं
- कार्डिनैलिटी बाध्यता समस्याएं
सैद्धांतिक चुनौतियां: इस प्रकार की समस्याएं उनकी संयोजक संरचना के कारण सैद्धांतिक विश्लेषण में अत्यंत चुनौतीपूर्ण हैं, और पारंपरिक बाध्यता योग्यता शर्तें अक्सर बहुत सख्त या सत्यापित करने में कठिन होती हैं।
मौजूदा विधियों की सीमाएं:
- मौजूदा AM-नियमितता को अनंत अनुक्रमों को नियंत्रित करने की आवश्यकता है, जो व्यावहारिक अनुप्रयोगों में सत्यापित करना कठिन है
- मजबूत स्थिरता की आवश्यक शर्तों का व्यवस्थित अध्ययन अभाव है
- आसानी से सत्यापित योग्यता शर्तों का अभाव है

मुख्य योगदान

नई अनुमानित स्थिरता अवधारणाओं का परिचय: सख्त अनुमानित मजबूत स्थिरता (SAS-stationarity) की अवधारणा प्रस्तुत की, जो ज्ञात अनुमानित Mordukhovich स्थिरता सिद्धांत को विस्तारित करती है।
नई योग्यता शर्तें स्थापित करना: उपसमुच्चय Mangasarian-Fromovitz शर्त (subMFC) प्रस्तावित की, जो पारंपरिक AM-नियमितता की तुलना में सत्यापित करने में आसान है।
सैद्धांतिक संबंधों का विश्लेषण: विभिन्न अनुमानित स्थिरता अवधारणाओं के बीच संबंधों का व्यवस्थित विश्लेषण, और उनके सटीक स्थिरता से संबंध।
MPCC अनुप्रयोग: सिद्धांत परिणामों को पूरक बाध्यता अनुकूलन समस्याओं पर लागू करना, कमजोर स्थिरता और Clarke स्थिरता के अनुमानित संस्करणों को विस्तारित करना।
स्वतंत्रता परिणाम: यह साबित करना कि नई प्रस्तावित subMFC AM-नियमितता और AS-नियमितता से पारस्परिक रूप से स्वतंत्र है, कुछ मामलों में अधिक लाभकारी है।

विधि विवरण

कार्य परिभाषा

विच्छेदक बाध्यता अनुकूलन समस्याओं के स्थिरता सिद्धांत का अध्ययन, विशेष रूप से:

इनपुट: व्यवहार्य बिंदु 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ᵏ,δᵏ)

तकनीकी नवाचार बिंदु

SAS-stationarity का परिचय: पहली बार मजबूत स्थिरता के अनुमानित संस्करण का व्यवस्थित अध्ययन, जो सैद्धांतिक अंतराल को भरता है।
subMFC की व्यावहारिकता: सभी संभावित अनुक्रमों को नियंत्रित करने की आवश्यकता वाली AM-नियमितता की तुलना में, subMFC को केवल विशिष्ट अनुक्रमों की प्रवणता रैखिक स्वतंत्रता सत्यापित करने की आवश्यकता है।
अनुक्रम-निर्भर योग्यता शर्तें: हालांकि पारंपरिक अर्थ में बाध्यता योग्यता नहीं है, लेकिन एल्गोरिथम-उत्पन्न अनुक्रमों के सत्यापन के लिए अधिक उपयुक्त है।

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन विधि

पेपर मुख्य रूप से सैद्धांतिक विश्लेषण और विशिष्ट उदाहरणों के माध्यम से परिणामों को सत्यापित करता है:

उदाहरण 3.10: AM-स्थिर लेकिन SAS-स्थिर न होने वाले बिंदु को प्रदर्शित करता है
उदाहरण 3.13: AM-नियमितता और AS-नियमितता की स्वतंत्रता को दर्शाता है
उदाहरण 4.8: साबित करता है कि M-स्थिरता हमेशा ODP-subMFC का अर्थ नहीं देती है
उदाहरण 4.11: एल्गोरिथम अनुक्रम सत्यापन में subMFC के अनुप्रयोग को प्रदर्शित करता है

तुलनात्मक विश्लेषण

पेपर व्यवस्थित रूप से तुलना करता है:

नई अवधारणाओं और मौजूदा AM-stationarity के बीच संबंध
subMFC और पारंपरिक LICQ, AM-नियमितता की शक्ति-कमजोरी संबंध
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-नियमितता और AS-नियमितता से पारस्परिक रूप से स्वतंत्र है।

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-नियमितता सत्य नहीं है, लेकिन subMFC के माध्यम से M-स्थिरता को सत्यापित किया जा सकता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

सैद्धांतिक पूर्णता: विच्छेदक अनुकूलन में अनुमानित स्थिरता का संपूर्ण सैद्धांतिक ढांचा स्थापित किया
व्यावहारिक मूल्य: subMFC एल्गोरिथम विश्लेषण के लिए नए उपकरण प्रदान करता है
व्यापक अनुप्रयोग: सिद्धांत कई बाध्यता प्रकारों पर लागू किया जा सकता है

सीमाएं

SAS-stationarity की आवश्यकता: सभी स्थानीय न्यूनतम SAS-स्थिरता को संतुष्ट नहीं करते हैं
subMFC की अनुक्रम-निर्भरता: पारंपरिक अर्थ में बाध्यता योग्यता शर्त नहीं है
कम्प्यूटेशनल जटिलता: कुछ योग्यता शर्तों का सत्यापन अभी भी जटिल है

भविष्य की दिशाएं

एल्गोरिथम डिजाइन: SAS-स्थिरता की गारंटी देने वाले एल्गोरिथम विकसित करना
गैर-चिकनी विस्तार: Lipschitz फलनों के मामले में विस्तार करना
कम्प्यूटेशनल विधियां: योग्यता शर्तों के सत्यापन के लिए कुशल एल्गोरिथम विकसित करना

गहन मूल्यांकन

शक्तियां

सैद्धांतिक नवाचार: SAS-stationarity अवधारणा महत्वपूर्ण सैद्धांतिक अंतराल को भरती है
व्यावहारिक मूल्य: subMFC पारंपरिक विधियों की तुलना में अधिक आसानी से सत्यापित है
व्यवस्थितता: संपूर्ण सैद्धांतिक ढांचा और पदानुक्रम संरचना
व्यापक अनुप्रयोग: कई महत्वपूर्ण बाध्यता प्रकारों को एकीकृत तरीके से संभालता है
कठोरता: गणितीय प्रमाण कठोर हैं, उदाहरण समृद्ध हैं

कमियां

कम्प्यूटेशनल जटिलता: कुछ अवधारणाओं की वास्तविक गणना अभी भी कठिन है
एल्गोरिथम मार्गदर्शन: ठोस एल्गोरिथम कार्यान्वयन मार्गदर्शन का अभाव
संख्यात्मक प्रयोग: मुख्य रूप से सैद्धांतिक विश्लेषण, बड़े पैमाने पर संख्यात्मक सत्यापन का अभाव

प्रभाव

सैद्धांतिक योगदान: विच्छेदक अनुकूलन सिद्धांत के विकास में महत्वपूर्ण प्रगति
व्यावहारिक मूल्य: एल्गोरिथम विश्लेषण के लिए नए उपकरण
अनुशासन प्रभाव: संबंधित अनुकूलन उप-क्षेत्रों के विकास को प्रभावित कर सकता है

प्रयोज्य परिदृश्य

एल्गोरिथम विश्लेषण: अनुकूलन एल्गोरिथम के अभिसरण गुणों को सत्यापित करना
सैद्धांतिक अनुसंधान: आगे के सैद्धांतिक विकास के लिए आधार के रूप में कार्य करना
अनुप्रयुक्त समस्याएं: जटिल बाध्यता संरचना वाली वास्तविक अनुकूलन समस्याओं को संभालना

संदर्भ

पेपर 41 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से:

Flegel, Kanzow, Outrata (2007): विच्छेदक अनुकूलन का अग्रणी कार्य
Mehlitz (2020): AM-नियमितता सिद्धांत
Andreani आदि द्वारा MPCC संबंधित अनुसंधान
Mordukhovich, Rockafellar & Wets का भिन्नात्मक विश्लेषण मौलिक सिद्धांत

यह पेपर विच्छेदक बाध्यता अनुकूलन सिद्धांत में महत्वपूर्ण योगदान देता है, विशेष रूप से अनुमानित स्थिरता और योग्यता शर्तों के क्षेत्र में नए सैद्धांतिक उपकरण और व्यावहारिक विधियां प्रदान करता है। हालांकि मुख्य रूप से सैद्धांतिक कार्य है, लेकिन एल्गोरिथम डिजाइन और विश्लेषण के लिए मूल्यवान ढांचा प्रदान करता है।