2025-11-25T03:19:17.246550

Generalized Reduced Jacobian Method

Maghri, Elboulqe

In a recent work, we presented the reduced Jacobian method (RJM) as an extension of Wolfe's reduced gradient method to multicriteria (multiobjective) optimization problems dealing with linear constraints. This approach reveals that using a reduction technique of the Jacobian matrix of the objective avoids scalarization. In the present work, we intend to generalize RJM to handle nonlinear constraints too. In fact, we propose a generalized reduced Jacobian (GRJ) method that extends Abadie-Carpentier's approach for single-objective programs. To this end, we adopt a global reduction strategy based on the fundamental theorem of implicit functions. In this perspective, only a reduced descent direction common to all the criteria is computed by solving a simple convex program. After establishing an Armijo-type line search condition that ensures feasibility, the resulting algorithm is shown to be globally convergent, under mild assumptions, to a Pareto critical (KKT-stationary) point. Finally, experimental results are presented, including comparisons with other deterministic and evolutionary approaches.

academic

सामान्यीकृत न्यूनीकृत जैकोबियन विधि

मूल जानकारी

पेपर ID: 2510.14785
शीर्षक: सामान्यीकृत न्यूनीकृत जैकोबियन विधि
लेखक: M. El Maghri, Y. Elboulqe
वर्गीकरण: math.OC (अनुकूलन और नियंत्रण)
प्रकाशन तिथि: 17 अक्टूबर, 2025
पेपर लिंक: https://arxiv.org/abs/2510.14785

सारांश

यह पेपर सामान्यीकृत न्यूनीकृत जैकोबियन विधि (GRJ) प्रस्तुत करता है, जो लेखकों की पूर्ववर्ती रैखिक बाधा बहु-उद्देश्य अनुकूलन समस्याओं के लिए न्यूनीकृत जैकोबियन विधि (RJM) को अरैखिक बाधाओं को संभालने के लिए विस्तारित करता है। यह विधि निहित फलन प्रमेय के आधार पर वैश्विक न्यूनीकरण रणनीति का उपयोग करती है, सरल उत्तल प्रोग्रामिंग समस्या को हल करके सभी मानदंडों के लिए सामान्य न्यूनीकृत अवरोही दिशा की गणना करती है। व्यवहार्यता की गारंटी देने वाली आर्मिजो-प्रकार की रेखा खोज शर्तें स्थापित करने के बाद, एल्गोरिथ्म के पेरेटो-महत्वपूर्ण (KKT-स्थिर) बिंदुओं में वैश्विक अभिसरण को सिद्ध किया गया है। प्रायोगिक परिणामों में अन्य नियतात्मक और विकासवादी विधियों के साथ तुलना शामिल है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या विवरण

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

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

पारंपरिक विधियों की सीमाएं: मौजूदा बहु-उद्देश्य अनुकूलन विधियों को अक्सर अदिश रूपांतरण की आवश्यकता होती है, कृत्रिम पैरामीटर पेश करते हैं, जो मूल समस्या के प्रति संवेदनशील हो सकते हैं
रैखिक बाधाओं की सीमा: लेखकों की पूर्ववर्ती RJM विधि केवल रैखिक बाधा समस्याओं पर लागू होती है
व्यावहारिक अनुप्रयोग की आवश्यकता: वास्तविक दुनिया की बहु-उद्देश्य अनुकूलन समस्याओं में आमतौर पर अरैखिक बाधाएं होती हैं

तकनीकी चुनौतियां

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

मुख्य योगदान

विधि विस्तार: RJM विधि को अरैखिक बाधाओं वाली बहु-उद्देश्य अनुकूलन समस्याओं को संभालने के लिए सफलतापूर्वक विस्तारित किया
सैद्धांतिक आधार: निहित फलन प्रमेय के आधार पर एक संपूर्ण सैद्धांतिक ढांचा स्थापित किया
एल्गोरिथ्म डिजाइन: व्यवहार्य आर्मिजो रेखा खोज वाली संपूर्ण GRJ एल्गोरिथ्म प्रस्तावित की
अभिसरण प्रमाण: सौम्य मान्यताओं के तहत एल्गोरिथ्म के वैश्विक अभिसरण को सिद्ध किया
प्रायोगिक सत्यापन: 30 परीक्षण समस्याओं के माध्यम से विधि की प्रभावशीलता को सत्यापित किया, अन्य विधियों के साथ तुलना सहित

विधि विवरण

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

निम्नलिखित अरैखिक बाधा बहु-उद्देश्य अनुकूलन समस्या पर विचार करें:

(MOP) Min F(x) subject to G(x) = 0, a ≤ x ≤ b

जहां:

$F: \mathbb{R}^n \to \mathbb{R}^r$ उद्देश्य फलन सदिश है
$G: \mathbb{R}^n \to \mathbb{R}^m$ बाधा फलन सदिश है
$a, b \in \mathbb{R}^n$ चर सीमाएं हैं

मुख्य अवधारणाएं

दक्षता परिभाषा

पेपर तीन दक्षता अवधारणाओं को परिभाषित करता है:

कमजोर दक्षता: कोई $x \in S$ नहीं है जो $F(x) < F(x^*)$ को संतुष्ट करता है
दक्षता (पेरेटो इष्टतमता): कोई $x \in S$ नहीं है जो $F(x) \preceq F(x^*)$ को संतुष्ट करता है
उचित दक्षता: हेनिग अर्थ में उचित दक्षता

बहु-उद्देश्य अवरोही दिशा

सदिश $d \in \mathbb{R}^n$ को बहु-उद्देश्य अवरोही दिशा कहा जाता है, यदि यह संतुष्ट करता है: $J_F(x)d < 0$

GRJ रणनीति

न्यूनीकरण तकनीक

$A(x) = J_G(x) \in \mathbb{R}^{m \times n}$ को बाधा जैकोबियन मैट्रिक्स मानें, मान लें कि यह पूर्ण रैंक है। आधार $B$ चुनें ताकि उप-मैट्रिक्स $A_B(x)$ व्युत्क्रमणीय हो, चर को आधार चर $x_B$ और गैर-आधार चर $x_N$ में विभाजित करें।

निहित फलन प्रमेय द्वारा, एक फलन $\psi: W \to V$ मौजूद है जो संतुष्ट करता है: $G(\psi(x_N), x_N) = 0$ $\frac{\partial \psi}{\partial x_N}(x_N) = -A_B^{-1}(x')A_N(x')$

सामान्यीकृत न्यूनीकृत जैकोबियन मैट्रिक्स

सामान्यीकृत न्यूनीकृत जैकोबियन मैट्रिक्स को परिभाषित करें: $U_N(x) := J_{F_N}(x) - J_{F_B}(x)A_B^{-1}(x)A_N(x)$

बहु-उद्देश्य न्यूनीकृत अवरोही दिशा

गैर-आधार सदिश $d_N \in \mathbb{R}^{n-m}$ को बहु-उद्देश्य न्यूनीकृत अवरोही दिशा कहा जाता है, यदि यह संतुष्ट करता है: $U_N(x)d_N < 0, \quad \forall i \in I_a(x) \cap N, d_i \geq 0, \quad \forall i \in I_b(x) \cap N, d_i \leq 0$

दिशा खोज उप-समस्या

न्यूनीकृत अवरोही दिशा की गणना के लिए, निम्नलिखित उत्तल अनुकूलन उप-समस्या पेश की जाती है: $(P_x) \quad \min_{\lambda \in \Lambda} f(\lambda, x) := \frac{1}{2}\sum_{i \in N}\left(\varphi(b_i - x_i)\lfloor(U_N(x)^T\lambda)_i\rfloor_-^2 + \varphi(x_i - a_i)\lfloor(U_N(x)^T\lambda)_i\rfloor_+^2\right)$

जहां $\Lambda = \{(\lambda_1, \ldots, \lambda_r) \in \mathbb{R}_+^r : \sum_{j=1}^r \lambda_j = 1\}$ ।

व्यवहार्यता और अवरोही गुण

प्रस्ताव 3.1 न्यूनीकृत अवरोही दिशा के साथ व्यवहार्यता को सिद्ध करता है:

चरण आकार की ऊपरी सीमा $t_N > 0$
गैर-अपभ्रंश बिंदुओं पर व्यवहार्य चरण आकार $t_f$ का अस्तित्व
आर्मिजो-प्रकार की असमानता को संतुष्ट करने वाले चरण आकार का अस्तित्व

GRJ एल्गोरिथ्म

एल्गोरिथ्म प्रवाह

चरण 0: प्रारंभिकीकरण
चरण 1: गैर-अपभ्रंश आधार चयन
चरण 2: सामान्यीकृत न्यूनीकृत जैकोबियन मैट्रिक्स की गणना
चरण 3: दिशा खोज उप-समस्या को हल करें
चरण 4: रोकने की कसौटी की जांच
चरण 5: व्यवहार्य आर्मिजो रेखा खोज
चरण 6: पुनरावृत्ति बिंदु को अपडेट करें
चरण 7: अपभ्रंश परीक्षण

अभिसरण विश्लेषण

प्रमेय 5.1 निम्नलिखित मान्यताओं के तहत:

व्यवहार्य समुच्चय गैर-अपभ्रंश है
फलन $\varphi$ सतत है और 0 पर अवकलनीय है
आधार गुण मान्यता (H) सत्य है

एल्गोरिथ्म द्वारा उत्पन्न अनुक्रम संतुष्ट करता है:

प्रत्येक पुनरावृत्ति व्यवहार्यता को बनाए रखती है और उद्देश्य फलन सख्ती से घटता है
कोई भी संचय बिंदु पेरेटो KKT-स्थिर बिंदु है

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

डेटासेट

साहित्य से 30 बाधित बहु-उद्देश्य अनुकूलन परीक्षण समस्याएं चुनी गईं, जिनमें शामिल हैं:

रैखिक और अरैखिक बाधा समस्याएं
2-3 उद्देश्य फलन
2-30 चर
व्यावहारिक इंजीनियरिंग डिजाइन समस्याएं (डिस्क ब्रेक, वेल्डेड बीम डिजाइन)

मूल्यांकन मेट्रिक्स

शुद्धता (Purity, P): अनुमानित पेरेटो सीमांत में वास्तविक गैर-प्रभुत्व समाधानों के अनुपात को मापता है
*वितरण (Spread, Δ)**: समाधानों की विविधता और बिखराव को मापता है
पीढ़ी दूरी (GD): अभिसरण को मापता है, अर्थात अनुमानित सीमांत से वास्तविक सीमांत की दूरी

तुलना विधियां

ZMO: Zoutendijk-प्रकार विधि
MOSQP: SQP-प्रकार विधि
NSGA-II: शास्त्रीय विकासवादी एल्गोरिथ्म

कार्यान्वयन विवरण

आर्मिजो स्थिरांक: β = 0.25
रोकने की कसौटी: min(P_x) < 10^{-6}
प्रारंभिक जनसंख्या: 200 व्यक्ति
व्यवहार्य आर्मिजो रेखा खोज को हल करने के लिए न्यूटन विधि का उपयोग

प्रायोगिक परिणाम

मुख्य परिणाम

कार्यक्षमता प्रोफाइल विश्लेषण

कार्यक्षमता प्रोफाइल (Performance Profile) विश्लेषण दिखाता है:

शुद्धता मेट्रिक: GRJ विधि शुद्धता में सर्वश्रेष्ठ प्रदर्शन करती है, अपेक्षाकृत छोटी सीमा α पर ρ(α)=1 तक पहुंच सकती है, जबकि अन्य विधियां इस मान तक नहीं पहुंच सकीं
वितरण मेट्रिक: चारों विधियां वितरण में समान प्रदर्शन करती हैं, GRJ और NSGA-II को हल्का लाभ है
अभिसरण मेट्रिक: पीढ़ी दूरी में, तीन नियतात्मक विधियों को NSGA-II की तुलना में हल्का लाभ है
गणना समय: अन्य तीन विधियां GRJ से गति में थोड़ी बेहतर हैं, यह मुख्य रूप से GRJ की आधार चयन और रेखा खोज प्रक्रिया के अधिक समय लेने के कारण है

व्यावहारिक इंजीनियरिंग समस्या विश्लेषण

डिस्क ब्रेक डिजाइन समस्या

उद्देश्य: ब्रेक का द्रव्यमान और रुकने का समय दोनों को न्यूनतम करना
परिणाम: GRJ और NSGA-II पेरेटो सीमांत की खोज में उत्कृष्ट प्रदर्शन करते हैं, जबकि ZMO और MOSQP को गंभीर चुनौतियों का सामना करना पड़ता है

वेल्डेड बीम डिजाइन समस्या

उद्देश्य: विनिर्माण लागत और बीम के विक्षेपण को न्यूनतम करना
परिणाम: सभी विधियां पेरेटो सीमांत के महत्वपूर्ण क्षेत्र को सफलतापूर्वक अनुमानित करती हैं, लेकिन बिखराव की डिग्री अलग है, GRJ अच्छी दृढ़ता प्रदर्शित करता है

संख्यात्मक परिणाम सारांश

30 परीक्षण समस्याओं में, GRJ विधि अधिकांश समस्याओं पर शुद्धता मेट्रिक में सर्वश्रेष्ठ प्रदर्शन करती है, विशेष रूप से जटिल अरैखिक बाधा समस्याओं पर लाभ दिखाती है।

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

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

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

सीमाएं

गणना जटिलता: आधार चयन और रेखा खोज प्रक्रिया अपेक्षाकृत समय लेने वाली है
मान्यता शर्तें: बाधा योग्यता शर्त (ACQ) और आधार गुण मान्यता को संतुष्ट करने की आवश्यकता है
अपभ्रंश प्रबंधन: अपभ्रंश मामलों का प्रबंधन एल्गोरिथ्म दक्षता को प्रभावित कर सकता है
पैरामीटर संवेदनशीलता: आर्मिजो पैरामीटर और फलन φ की पसंद प्रदर्शन को प्रभावित कर सकती है

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

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

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

शक्तियां

सैद्धांतिक कठोरता: निहित फलन प्रमेय पर आधारित ठोस सैद्धांतिक आधार
विधि नवीनता: अरैखिक बाधा बहु-उद्देश्य अनुकूलन में न्यूनीकरण तकनीक को सफलतापूर्वक विस्तारित करने वाली पहली विधि
अभिसरण गारंटी: कठोर वैश्विक अभिसरण प्रमाण प्रदान करता है
प्रायोगिक पूर्णता: 30 परीक्षण समस्याओं का व्यापक सत्यापन
व्यावहारिक मूल्य: व्यावहारिक इंजीनियरिंग डिजाइन समस्याओं में उत्कृष्ट प्रदर्शन

कमियां

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

प्रभाव

शैक्षणिक योगदान: बहु-उद्देश्य अनुकूलन सिद्धांत के लिए नई अनुसंधान दिशा प्रदान करता है
पद्धति महत्व: शास्त्रीय एकल-उद्देश्य विधियों को बहु-उद्देश्य तक विस्तारित करने की संभावना प्रदर्शित करता है
व्यावहारिक मूल्य: इंजीनियरिंग डिजाइन आदि व्यावहारिक अनुप्रयोगों के लिए प्रभावी उपकरण प्रदान करता है
पुनरुत्पादनीयता: एल्गोरिथ्म विवरण विस्तृत है, कार्यान्वयन और पुनरुत्पादन में आसान

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

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

संदर्भ

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

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

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