이중성(최적화)

수학적 최적화 이론에서 이중성 또는 이중성 원리는 최적화 문제를 원시적 문제 또는 이중적 문제라는 두 가지 관점 중 하나에서 볼 수 있다는 원칙이다. 이중 문제에 대한 해법은 원시(소형화) 문제의 해법에 대한 하한을 제공한다.^[1] 그러나 일반적으로 원시 문제와 이중 문제의 최적 값은 같을 필요가 없다. 그들의 차이를 이중성격차라고 한다. 볼록 최적화 문제의 경우, 이중성 간격은 제약 조건 조건 하에서는 0이다.

이중 문제

보통 "이중 문제"라는 용어는 라그랑의 이중 문제를 의미하지만, 다른 이중 문제, 예를 들어 울프 이중 문제, 펜첼 이중 문제 등이 사용된다. 라그랑비아 이중문제는 비부정 라그랑지 승수를 사용하여 목표함수에 제약을 가한 다음 원래의 목표함수를 최소화하는 원시 변수 값에 대해 해결함으로써 최소화 문제의 라그랑지안을 형성함으로써 얻는다. 이 솔루션은 원시 변수를 이중 변수라고 하는 라그랑주 승수의 함수로 제공하므로 새로운 문제는 이중 변수에 대해 파생된 제약 조건(최소한 부정성 제약 조건 포함)에 따라 이중 변수에 관한 객관적 함수를 최대화하는 것이다.

In general given two dual pairs of separated locally convex spaces $\left(X,X^{*}\right)$ and $\left(Y,Y^{*}\right)$ and the function $f:X\to \mathbb {R} \cup \{+\infty \}$ , we can define the primal problem as finding ${\hat {x}}$ ${\hat {x}}$ $f({\hat {x}})=\inf _{x\in X}f(x).\,$ ${\hat {x}}$ ${\$ f $f({\hat {x}})=\inf _{x\in X}f(x).\,$ ( $f({\hat {x}})=\inf _{x\in X}f(x).\,$ ) $f({\hat {x}})=\inf _{x\in X}f(x).\,$ = $f({\hat {x}})=\inf _{x\in X}f(x).\,$ $f({\hat {x}})=\inf _{x\in X}f(x).\,$ ∈ $f({\hat {x}})=\inf _{x\in X}f(x).\,$ $f({\hat {x}})=\inf _{x\in X}f(x).\,$ ( x $f({\hat {x}})=\inf _{x\in X}f(x).\,$ ) $f({\hat {x}})=\inf _{x\in X}f(x).\,$ . ${\$ $\,}$ 다시 $f({\hat {x}})=\inf _{x\in X}f(x).\,$ 말해 ${\hat {x}}$ ^ ${\$ 이 ${\hat {x}}$ (가) 있는 경우 $f$ ( $f({\hat {x}})$ ) $f({\hat {x}})$ {\ $displaystyle$ $f$ $({\hat$ { $x})$ 는 함수 f ${\displaystyf}$ 의 최소값이며 $f({\hat {x}})$ $f$ 함수의 최소값(가장 큰 하한값)을 얻는다.

제약조건 조건이 있는 ${\tilde {f}}=f+I_{\mathrm {constraints} }$ f ${\tilde {f}}=f+I_{\mathrm {constraints} }$ ~ = ${\tilde {f}}=f+I_{\mathrm {constraints} }$ + ${\tilde {f}}=f+I_{\mathrm {constraints} }$ c ${\tilde {f}}=f+I_{\mathrm {constraints} }$ ${\tilde {f}}=f+I_{\mathrm {constraints} }$ r a ${\tilde {f}}=f+I_{\mathrm {constraints} }$ r a ${\tilde {f}}=f+I_{\mathrm {constraints} }$ t ${\tilde {f}}=f+I_{\mathrm {constraints} }$ ${\$ 로 설정하여 $f$ $f$ $f$ 기능에 내장할 수 있다. $I_{\mathrm {constraints} }}$ where $I_{\mathrm {constraints} }$ is a suitable function on $X$ that has a minimum 0 on the constraints, and for which one can prove that ${\displaystyle \inf _{x$ $\in X}{\tilde{f}}(x)=\inf _{x\\mathrm {constrained} }f(x)}$ . The latter condition is trivially, but not always conveniently, satisfied for the characteristic function (i.e. $I_{\mathrm {constraints} }(x)=0$ for $x$ satisfying the constraints and ${\displaystyle I_{\mathrm {cons$ $traints} }(x$ )=\ $fully$ }그렇지 $I_{\mathrm {constraints} }(x)=\infty$ 않으면. Then extend ${\tilde {f}}$ to a perturbation function $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ such that $F(x,0)={\tilde {f}}(x)$ .^[2]

이중성격차는 불평등의 좌우의 차이다.

\sup _{y^{*}\in Y^{*}-F^{}}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,

여기서 $∗{\$ F $^{*}$ 는 $F^{*}$ 두 변수 모두에서 볼록한 결합이며, $\sup$ {\ $displaystyle \sup}$ 은 우월(최소 상한)을 나타낸다 $\sup$ .^[2]^[3]^[4]

이중성격차

이중성 간격은 모든 원시 용액과 이중 용액의 값 사이의 차이다. $∗{\$ 이 최적의 $d^{*}$ 이중값이고 $p^{*}$ $p^{*}$ ${\$ 이 최적의 원시 값이라면 $p^{*}$ , 이중성 $p^{*}-d^{*}$ 은 p $p^{*}-d^{*}$ - $p^{*}-d^{*}$ ∗ ${\$ 이 값은 항상 0보다 크거나 같다 $p^{*}-d^{*}$ 강한 이중성이 유지될 경우에만 이중성 격차가 0이다. 그렇지 않으면 격차가 엄격히 긍정적이고 이중성이 약하다.^[5]

계산 최적화에서, 또 다른 "이중성 격차"가 종종 보고되는데, 이것은 어떤 이중성 솔루션과 실현 가능하지만 차선의 원시 문제에 대해 반복하는 값 사이의 차이다. 이 대안 "이중성 격차"는 원시 문제에 대해 실현 가능하지만 차선책인 현재의 값과 이중 문제의 값 사이의 차이를 정량화한다. 이중 문제의 값은 규칙성 조건에서 원시 문제의 볼록한 이완 값과 같다. 볼록 이완은 비콘벡스 가능 세트를 닫힌 볼록 선체로 교체하고 비콘벡스 기능을 볼록 폐쇄로 교체하는 문제로, 원래 원초 목적 기능의 닫힌 볼록 선체에 대한 경첩이 있는 기능이다.^[6]^[7]^[8]^[9]^[10]^[11]^[12]^[13]^[14]^[15]^[16]

선형대소문자

선형 프로그래밍 문제는 목표함수와 제약조건이 모두 선형인 최적화 문제다. 원시적 문제에서 객관적 함수는 n개의 변수의 선형 결합이다. m 제약조건이 있으며, 각 제약조건은 n 변수의 선형 조합에 상한을 둔다. 제약을 받는 목표함수의 가치를 최대화하는 것이 목표다. 솔루션은 목표함수에 대한 최대값을 달성하는 n개의 값의 벡터(목록)이다.

이중 문제에서, 목적 함수는 원시 문제로부터 m 제약 조건의 한계인 m 값의 선형 결합이다. n개의 이중 제약조건이 있으며, 각각 m 이중 변수의 선형 조합에 하한을 둔다.

원시 문제와 이중 문제 사이의 관계

선형의 경우, 원시 문제의 경우, 모든 제약을 만족하는 각 하위 최적점으로부터, 목적 함수를 증가시키는 방향 또는 방향의 하위 공간이 있다. 그런 방향으로 움직이면 후보 해법과 하나 이상의 제약 사이에 느슨한 부분이 제거된다고 한다. 후보 솔루션의 실현 불가능한 가치는 제약 조건 중 하나 이상을 초과하는 값이다.

이중 문제에서 이중 벡터는 원시에서 제약조건의 위치를 결정하는 제약조건을 곱한다. 이중 문제에서 이중 벡터를 변화시키는 것은 원시 문제에서 상한을 수정하는 것과 같다. 가장 낮은 상한선을 찾는다. 즉, 제약조건의 후보 위치와 실제 최적 사이의 느슨함을 제거하기 위해 이중 벡터를 최소화한다. 이중 벡터의 실현 불가능한 값은 너무 낮은 값이다. 그것은 실제 최적점을 배제한 위치에서 하나 이상의 제약조건의 후보 위치를 설정한다.

이 직관은 선형 프로그래밍: 이중성의 방정식에 의해 공식화된다.

비선형 케이스

비선형 프로그래밍에서 제약조건이 반드시 선형인 것은 아니다. 그럼에도 불구하고, 많은 같은 원칙들이 적용된다.

비선형 문제의 전지구적 최대치를 쉽게 식별할 수 있도록 하기 위해, 문제 제형은 종종 기능이 볼록하고 소형 하위 수준 집합이 있어야 한다.

이것이 카루시-쿤-터커 조건의 의의다. 그들은 비선형 프로그래밍 문제의 국부적 최적성을 식별하기 위해 필요한 조건을 제공한다. 최적의 솔루션으로의 방향을 정의할 수 있도록 필요한 추가 조건(기존 자격)이 있다. 최적 솔루션은 국소 최적 솔루션이지만 글로벌 최적 솔루션은 아닐 수 있다.

강한 라그랑주 원리: 라그랑주 이중성

비선형 프로그래밍 문제가 표준 형태로 제시됨

{\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\ldots ,p\right\}\end{aligned}}

with the domain ${\mathcal {D}}\subset \mathbb {R} ^{n}$ having non-empty interior, the Lagrangian function $\Lambda :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ is defined as

\Lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}+\sum _{i=1}^{p}\nu _{i}h_{i}}(x).

벡터 $\lambda$ $\lambda$ 및 $\lambda$ $\nu$ ${\displaystyle$ \nu $}$ 을(를) 문제와 연관된 이중 변수 또는 라그랑주 곱셈 벡터라고 한다 $\nu$ . 라그랑주 이중 함수 $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ : R $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ p $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ → R ${\$ g $:\mathb {R}^{m}\time \mathb {R}^{p}\to \mathb$ { $R}}}}은($ 으)로 정의된다 $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ .

g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\Lambda (x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left(f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right).

이중 함수 g는 점으로 볼 때 아핀 함수의 최소치이기 때문에 초기 문제가 볼록하지 않을 때에도 오목하다. 이중 함수는 초기 문제의 최적 $p^{*}$ 값 $p^{*}$ $∗{\$ 에 대한 하한을 산출한다. $\lambda \geq 0$ 0 ${\displaystyle \lambda \geq$ 0 $}$ 및 $\lambda \geq 0$ $\nu$ ${\displaystyle \$ $nu$ $}$ 에 $\nu$ 대해 $g(\lambda ,\nu )\leq p^{*}$ ( $g(\lambda ,\nu )\leq p^{*}$ λ $g(\lambda ,\nu )\leq p^{*}$ $)\displaystyleq p$ 이 있다.

If a constraint qualification such as Slater's condition holds and the original problem is convex, then we have strong duality, i.e. $d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$ .

볼록 문제

불평등 구속조건에 따른 볼록 최소화 문제의 경우,

{\det{aigned}&#{x}{\dataname {x}}}}}}}}}}}{{no}\&g_{to}\nowleq 0,\data.1,\ldots,m\end{aigned}}}}}}

라그랑의 이중 문제는

{\displaystyle{j}&{\putet {u}{\inf _{x}\{x(x)+\inf _{x}\ft(f(x)+\nf _{j=1}^{j}g_{j}(x)\rig)\rig)\rig)\\&\datablename {bask\;to} &&u_{i}\geq 0,\data i=1,\ldots,m\ended}}

여기서 목표 기능은 Lagrange 이중 기능이다. $함수$ f{\ $displaystyle f}$ $g_{1},\ldots ,g_{m}$ g $g_{1},\ldots ,g_{m}$ 1 $g_{1},\ldots ,g_{m}$ , $g_{1},\ldots ,g_{m}$ m $g_{1},\ldots ,g_{m}$ {\ $displaystyle g_{1},\ldots, g_{m}$ 이(가) 연속적으로 다를 경우 $g_{1},\ldots ,g_{m}$ , 그라데이션이 0인 경우 최소값이 발생한다. 문제

{\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}

'울프 이중 문제'라고 불린다. This problem may be difficult to deal with computationally, because the objective function is not concave in the joint variables $(u,x)$ . Also, the equality constraint $\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)$ is nonlinear in genera따라서 Wolfe 이중 문제는 일반적으로 비컨벡스 최적화 문제다. 어쨌든 약한 이중성이 버티고 있다.^[17]

역사

조지 단치히에 따르면, 선형 최적화를 위한 이중성 정리는 단치히가 선형 프로그래밍 문제를 제시한 직후 존 폰 노이만(John von Neumann)에 의해 추측되었다. 폰 노이만은 자신의 게임 이론에서 얻은 정보를 이용하고 있다고 지적하고, 2인칭 제로섬 매트릭스 게임이 선형 프로그래밍에 해당한다고 추측했다. 엄격한 증거는 1948년 알버트 W에 의해 처음 출판되었다. 터커와 그의 일행. (네링과 터커에게 보내는 단치히의 서문, 1993년)

참고 항목

메모들

^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. p. 216. ISBN 978-0-521-83378-3. Retrieved October 15, 2011.
^ ^a ^b Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai (2009). Duality in Vector Optimization. Springer. ISBN 978-3-642-02885-4.
^ Csetnek, Ernö Robert (2010). Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
^ Zălinescu, Constantin (2002). Convex analysis in general vector spaces. River Edge, NJ: World Scientific Publishing Co., Inc. pp. 106–113. ISBN 981-238-067-1. MR 1921556.
^ Borwein, Jonathan; Zhu, Qiji (2005). Techniques of Variational Analysis. Springer. ISBN 978-1-4419-2026-3.
^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.
^ Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization. Athena Scientific. ISBN 1-886529-45-0.
^ Bertsekas, Dimitri P. (1999). Nonlinear Programming (2nd ed.). Athena Scientific. ISBN 1-886529-00-0.
^ Bertsekas, Dimitri P. (2009). Convex Optimization Theory. Athena Scientific. ISBN 978-1-886529-31-1.
^ Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
^ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. MR 1261420.
^ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Duality for Practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR 1295240.
^ Lasdon, Leon S. (2002) [Reprint of the 1970 Macmillan]. Optimization theory for large systems. Mineola, New York: Dover Publications, Inc. pp. xiii+523. ISBN 978-0-486-41999-2. MR 1888251.
^ Lemaréchal, Claude (2001). "Lagrangian relaxation". In Jünger, Michael; Naddef, Denis (eds.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science (LNCS). 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.
^ Minoux, Michel (1986). Mathematical programming: Theory and algorithms. Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. ).
^ Shapiro, Jeremy F. (1979). Mathematical programming: Structures and algorithms. New York: Wiley-Interscience [John Wiley & Sons]. pp. xvi+388. ISBN 0-471-77886-9. MR 0544669.
^ Geoffrion, Arthur M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848.

참조

책들

Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.
Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization. Athena Scientific. ISBN 1-886529-45-0.
Bertsekas, Dimitri P. (1999). Nonlinear Programming (2nd ed.). Athena Scientific. ISBN 1-886529-00-0.
Bertsekas, Dimitri P. (2009). Convex Optimization Theory. Athena Scientific. ISBN 978-1-886529-31-1.
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (November 12, 1997). Combinatorial Optimization (1st ed.). John Wiley & Sons. ISBN 0-471-55894-X.
Dantzig, George B. (1963). Linear Programming and Extensions. Princeton, NJ: Princeton University Press.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. MR 1261420.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Duality for Practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR 1295240.
Lasdon, Leon S. (2002) [Reprint of the 1970 Macmillan]. Optimization theory for large systems. Mineola, New York: Dover Publications, Inc. pp. xiii+523. ISBN 978-0-486-41999-2. MR 1888251.
Lawler, Eugene (2001). "4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem". Combinatorial Optimization: Networks and Matroids. Dover. pp. 117–120. ISBN 0-486-41453-1.
Lemaréchal, Claude (2001). "Lagrangian relaxation". In Jünger, Michael; Naddef, Denis (eds.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science (LNCS). 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.
Minoux, Michel (1986). Mathematical programming: Theory and algorithms. Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. )).
Nering, Evar D.; Tucker, Albert W. (1993). Linear Programming and Related Problems. Boston, MA: Academic Press. ISBN 978-0-12-515440-6.
Papadimitriou, Christos H.; Steiglitz, Kenneth (July 1998). Combinatorial Optimization : Algorithms and Complexity (Unabridged ed.). Dover. ISBN 0-486-40258-4.
Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0691119151. MR 2199043.

기사들

Everett, Hugh, III (1963). "Generalized Lagrange multiplier method for solving problems of optimum allocation of resources". Operations Research. 11 (3): 399–417. doi:10.1287/opre.11.3.399. JSTOR 168028. MR 0152360. Archived from the original on 2011-07-24.
Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). "Lagrangian relaxation via ballstep subgradient methods". Mathematics of Operations Research. 32 (3): 669–686. doi:10.1287/moor.1070.0261. MR 2348241.
선형 프로그래밍의 이중성 Gary D. 너트

[Boyd-1] Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. p. 216. ISBN 978-0-521-83378-3. Retrieved October 15, 2011.

[BWG-2] Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai (2009). Duality in Vector Optimization. Springer. ISBN 978-3-642-02885-4.

[3] Csetnek, Ernö Robert (2010). Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.

[Zalinescu-4] Zălinescu, Constantin (2002). Convex analysis in general vector spaces. River Edge, NJ: World Scientific Publishing Co., Inc. pp. 106–113. ISBN 981-238-067-1. MR 1921556.

[5] Borwein, Jonathan; Zhu, Qiji (2005). Techniques of Variational Analysis. Springer. ISBN 978-1-4419-2026-3.

[6] Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.

[7] Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization. Athena Scientific. ISBN 1-886529-45-0.

[8] Bertsekas, Dimitri P. (1999). Nonlinear Programming (2nd ed.). Athena Scientific. ISBN 1-886529-00-0.

[9] Bertsekas, Dimitri P. (2009). Convex Optimization Theory. Athena Scientific. ISBN 978-1-886529-31-1.

[10] Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.

[11] Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. MR 1261420.

[12] Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Duality for Practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR 1295240.

[13] Lasdon, Leon S. (2002) [Reprint of the 1970 Macmillan]. Optimization theory for large systems. Mineola, New York: Dover Publications, Inc. pp. xiii+523. ISBN 978-0-486-41999-2. MR 1888251.

[14] Lemaréchal, Claude (2001). "Lagrangian relaxation". In Jünger, Michael; Naddef, Denis (eds.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science (LNCS). 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.

[15] Minoux, Michel (1986). Mathematical programming: Theory and algorithms. Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. ).

[16] Shapiro, Jeremy F. (1979). Mathematical programming: Structures and algorithms. New York: Wiley-Interscience [John Wiley & Sons]. pp. xvi+388. ISBN 0-471-77886-9. MR 0544669.

[17] Geoffrion, Arthur M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Search