4238:
54:. If the primal is a minimization problem then the dual is a maximization problem (and vice versa). Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal. This fact is called
3890:
3287:
3967:
2624:
3679:
3690:
109:
to add the constraints to the objective function, and then solving for the primal variable values that minimize the original objective function. This solution gives the primal variables as functions of the
Lagrange multipliers, which are called dual variables, so that the new problem is to maximize
1498:
In the dual problem, the dual vector multiplies the constraints that determine the positions of the constraints in the primal. Varying the dual vector in the dual problem is equivalent to revising the upper bounds in the primal problem. The lowest upper bound is sought. That is, the dual vector is
1670:
1382:
In computational optimization, another "duality gap" is often reported, which is the difference in value between any dual solution and the value of a feasible but suboptimal iterate for the primal problem. This alternative "duality gap" quantifies the discrepancy between the value of a current
1499:
minimized in order to remove slack between the candidate positions of the constraints and the actual optimum. An infeasible value of the dual vector is one that is too low. It sets the candidate positions of one or more of the constraints in a position that excludes the actual optimum.
4233:{\displaystyle {\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}}}
3045:
2438:
2925:
3545:
2746:
1526:. They provide necessary conditions for identifying local optima of non-linear programming problems. There are additional conditions (constraint qualifications) that are necessary so that it will be possible to define the direction to an
3885:{\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}
752:
3529:
2420:: (x∗, λ∗) is a saddle point of the Lagrange function L if and only if x∗ is an optimal solution to the primal, λ∗ is an optimal solution to the dual, and the optimal values in the indicated problems are equal to each other.
1551:
1203:
1521:
To ensure that the global maximum of a non-linear problem can be identified easily, the problem formulation often requires that the functions be convex and have compact lower level sets. This is the significance of the
3037:
3282:{\displaystyle g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}{\mathcal {L}}(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\}.}
1901:
5651:
4366:
2619:{\displaystyle {\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}}}
2181:
2113:
1011:
556:
1977:
2666:
924:
2754:
256:
3972:
3695:
3550:
2443:
2401:. But for some classes of functions, it is possible to get an explicit formula for g(). Solving the primal and dual programs together is often easier than solving only one of them. Examples are
2252:
1556:
358:
4518:
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
2308:
830:
3674:{\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\ldots ,m\end{aligned}}}
3415:
2387:
615:
1776:
5644:
1070:
2674:
1383:
feasible but suboptimal iterate for the primal problem and the value of the dual problem; the value of the dual problem is, under regularity conditions, equal to the value of the
207:
164:
3959:
5420:. Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489.
4931:. Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489.
3347:
3296:
is concave, even when the initial problem is not convex, because it is a point-wise infimum of affine functions. The dual function yields lower bounds on the optimal value
425:
953:
1369:
5637:
387:
285:
2948:
4277:
3321:
1329:
1302:
1257:
1233:
3367:
2968:
110:
the objective function with respect to the dual variables under the derived constraints on the dual variables (including at least the nonnegativity constraints).
3913:
850:
635:
476:
449:
1675:
The problem has constraints; we would like to convert it to a program without constraints. Theoretically, it is possible to do it by minimizing the function
1665:{\displaystyle {\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\\end{aligned}}}
640:
5841:
3435:
2318:
principle. If the primal problem is convex and bounded from below, and there exists a point in which all nonlinear constraints are strictly satisfied (
1085:
755:
5741:
1523:
2984:
5833:
5505:
5460:
5327:
5163:
4848:
4702:
4591:
4525:
4500:
4465:
4392:, and conjectured that two person zero sum matrix game was equivalent to linear programming. Rigorous proofs were first published in 1948 by
5348:(2001). "4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem".
5579:
1807:
4282:
5846:
5584:
5479:
5425:
5387:
5357:
5300:
5269:
5234:
5196:
5144:
5125:
5106:
4979:
4936:
4892:
4815:
4778:
4745:
4677:
4652:
4627:
4558:
4247:. This problem may be difficult to deal with computationally, because the objective function is not concave in the joint variables
1483:
In the linear case, in the primal problem, from each sub-optimal point that satisfies all the constraints, there is a direction or
2125:
2057:
961:
2314:
The optimal solution to the dual program is a lower bound for the optimal solution of the original (primal) program; this is the
5866:
5534:
5783:
481:
4388:
immediately after
Dantzig presented the linear programming problem. Von Neumann noted that he was using information from his
1916:
1487:
of directions to move that increases the objective function. Moving in any such direction is said to remove slack between the
2920:{\displaystyle {\mathcal {L}}(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).}
2632:
855:
5372:
Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000
4877:
Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000
212:
2197:
290:
6080:
5489:
2410:
1387:
of the primal problem: The convex relaxation is the problem arising replacing a non-convex feasible set with its closed
1371:. This value is always greater than or equal to 0 (for minimization problems). The duality gap is zero if and only if
98:
5183:. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490.
4732:. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490.
2268:
6085:
5851:
761:
5497:
4431:
1417:
5881:
5042:
Geoffrion, Arthur M. (1971). "Duality in
Nonlinear Programming: A Simplified Applications-Oriented Development".
63:
In general, the optimal values of the primal and dual problems need not be equal. Their difference is called the
31:
5871:
3372:
2340:
561:
5856:
5698:
4368:
is nonlinear in general, so the Wolfe dual problem is typically a nonconvex optimization problem. In any case,
3421:
1425:
72:
5295:. Grundlehren der Mathematischen Wissenschaften . Vol. 306. Berlin: Springer-Verlag. pp. xviii+346.
5264:. Grundlehren der Mathematischen Wissenschaften . Vol. 305. Berlin: Springer-Verlag. pp. xviii+417.
4810:. Grundlehren der Mathematischen Wissenschaften . Vol. 306. Berlin: Springer-Verlag. pp. xviii+346.
4773:. Grundlehren der Mathematischen Wissenschaften . Vol. 305. Berlin: Springer-Verlag. pp. xviii+417.
1689:
2741:{\displaystyle {\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }
5941:
5918:
5812:
5736:
4723:
1016:
5178:
4727:
6059:
5936:
5861:
5788:
5773:
5218:
4405:
1396:
169:
126:
5004:
3918:
1277:
The duality gap is the difference between the values of any primal solutions and any dual solutions. If
5793:
4426:
2429:
2406:
1542:
1515:
1392:
956:
5374:. Lecture Notes in Computer Science (LNCS). Vol. 2241. Berlin: Springer-Verlag. pp. 112–156.
4879:. Lecture Notes in Computer Science (LNCS). Vol. 2241. Berlin: Springer-Verlag. pp. 112–156.
3961:
are continuously differentiable, the infimum occurs where the gradient is equal to zero. The problem
3425:
2319:
5798:
5664:
5367:
5288:
5174:
4872:
4803:
4719:
1444:
variables. The goal is to maximize the value of the objective function subject to the constraints. A
121:
43:
3326:
5731:
5721:
5716:
5413:
5222:
4924:
4550:
1408:
392:
106:
102:
68:
929:
5960:
5678:
5554:
5401:
5090:
5059:
4906:
4611:
4452:
2402:
1530:
solution. An optimal solution is one that is a local optimum, but possibly not a global optimum.
1503:
1488:
1421:
1413:
1334:
94:
5535:"Generalized Lagrange multiplier method for solving problems of optimum allocation of resources"
5025:
4408:(SVMs), the formulating the primal problem of SVMs as the dual problem can be used to implement
363:
261:
5609:
5293:
Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods
4808:
Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods
2397:). In general this may be hard, as we need to solve a different minimization problem for every
5778:
5501:
5475:
5456:
5421:
5383:
5353:
5323:
5296:
5265:
5230:
5192:
5159:
5140:
5121:
5102:
5086:
4975:
4932:
4888:
4844:
4811:
4774:
4741:
4698:
4673:
4648:
4623:
4607:
4587:
4554:
4521:
4496:
4461:
2933:
2393:
Note that, to use either the weak or the strong duality principle, we need a way to compute g(
1518:, the constraints are not necessarily linear. Nonetheless, many of the same principles apply.
4971:
4965:
5931:
5876:
5767:
5762:
5593:
5546:
5375:
5184:
5051:
4880:
4733:
4542:
4393:
4385:
1449:
1236:
5629:
5605:
5566:
5515:
5435:
5397:
5337:
5310:
5279:
5206:
4989:
4946:
4902:
4858:
4825:
4788:
4755:
4568:
4250:
3299:
1307:
1280:
1242:
1211:
5951:
5922:
5896:
5891:
5886:
5817:
5802:
5711:
5683:
5660:
5601:
5562:
5511:
5431:
5393:
5333:
5306:
5275:
5214:
5202:
4985:
4942:
4898:
4854:
4821:
4784:
4751:
4564:
3352:
2953:
2416:
Another condition in which the min-max and max-min are equal is when the
Lagrangian has a
1484:
118:
4543:
3895:
where the objective function is the
Lagrange dual function. Provided that the functions
2330:
principle. In this case, we can solve the primal program by finding an optimal solution
6038:
5946:
5807:
5706:
5449:
5244:
5094:
4615:
4421:
4381:
3898:
3429:
1372:
835:
620:
461:
434:
77:
6074:
6005:
5997:
5993:
5989:
5985:
5981:
5822:
5570:
5345:
5249:
4244:
1782:
754:. The latter condition is trivially, but not always conveniently, satisfied for the
1495:
value of the candidate solution is one that exceeds one or more of the constraints.
6043:
5530:
5405:
4910:
4409:
4369:
2417:
1376:
747:{\displaystyle \inf _{x\in X}{\tilde {f}}(x)=\inf _{x\ \mathrm {constrained} }f(x)}
56:
5578:
Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007).
3524:{\displaystyle d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}}
1793:) is hard to solve as it is not continuous. It is possible to "approximate" I by
1198:{\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,}
6033:
6028:
5912:
4389:
1471:
dual constraints, each of which places a lower bound on a linear combination of
1440:
constraints, each of which places an upper bound on a linear combination of the
1388:
1272:
1076:
64:
5956:
5926:
5688:
5188:
4737:
5623:
17:
5379:
4884:
114:
5597:
5370:(2001). "Lagrangian relaxation". In Jünger, Michael; Naddef, Denis (eds.).
4875:(2001). "Lagrangian relaxation". In Jünger, Michael; Naddef, Denis (eds.).
4549:. River Edge, NJ: World Scientific Publishing Co., Inc. pp.
1459:
In the dual problem, the objective function is a linear combination of the
1432:. In the primal problem, the objective function is a linear combination of
5550:
1399:
that is the closed convex hull of the original primal objective function.
637:
that has a minimum 0 on the constraints, and for which one can prove that
5965:
3032:{\displaystyle g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }
1260:
458:
If there are constraint conditions, these can be built into the function
5262:
Convex analysis and minimization algorithms, Volume I: Fundamentals
4771:
Convex analysis and minimization algorithms, Volume I: Fundamentals
5746:
5063:
1801:
is a positive constant. This yields a function known as the lagrangian:
452:
428:
5558:
4412:, but the latter has higher time complexity in the historical cases.
1429:
1079:
is the difference of the right and left hand sides of the inequality
5055:
1896:{\displaystyle L(x,\lambda )=f_{0}(x)+\sum _{i}\lambda _{i}f_{i}(x)}
1456:
values that achieves the maximum value for the objective function.
5322:. Mineola, New York: Dover Publications, Inc. pp. xiii+523.
4843:. Mineola, New York: Dover Publications, Inc. pp. xiii+523.
4384:, the duality theorem for linear optimization was conjectured by
4361:{\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)}
5633:
4396:
and his group. (Dantzig's foreword to Nering and Tucker, 1993)
3539:
For a convex minimization problem with inequality constraints,
2409:. A better and more general approach to duality is provided by
1331:
is the optimal primal value, then the duality gap is equal to
5116:
Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003).
4643:
Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003).
5470:
Papadimitriou, Christos H.; Steiglitz, Kenneth (July 1998).
3134:
3092:
3083:
2760:
2680:
2638:
2176:{\displaystyle \max _{\lambda \geq 0}\min _{x}L(x,\lambda )}
2108:{\displaystyle \min _{x}\max _{\lambda \geq 0}L(x,\lambda )}
1479:
Relationship between the primal problem and the dual problem
1006:{\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}
5260:
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993).
4769:
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993).
5180:
Numerical optimization: Theoretical and practical aspects
4729:
Numerical optimization: Theoretical and practical aspects
1391:
and with replacing a non-convex function with its convex
551:{\displaystyle {\tilde {f}}=f+I_{\mathrm {constraints} }}
101:. The Lagrangian dual problem is obtained by forming the
5580:"Lagrangian relaxation via ballstep subgradient methods"
5440:
Programmation mathématique : Théorie et algorithmes
4951:
Programmation mathématique : Théorie et algorithmes
2326:
the optimal solution of the primal program; this is the
1972:{\displaystyle \max _{\lambda \geq 0}L(x,\lambda )=J(x)}
4491:
Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai (2009).
3428:
holds and the original problem is convex, then we have
5442:, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. )).
2661:{\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}}
5472:
5173:
Bonnans, J. Frédéric; Gilbert, J. Charles;
4953:, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. ).
4718:
Bonnans, J. Frédéric; Gilbert, J. Charles;
4285:
4253:
3970:
3921:
3901:
3693:
3548:
3438:
3375:
3355:
3329:
3302:
3048:
2987:
2956:
2936:
2757:
2677:
2635:
2441:
2343:
2271:
2200:
2128:
2060:
1919:
1810:
1692:
1554:
1337:
1310:
1283:
1245:
1214:
1088:
1019:
964:
932:
919:{\displaystyle I_{\mathrm {constraints} }(x)=\infty }
858:
838:
764:
643:
623:
564:
484:
464:
437:
395:
366:
293:
264:
215:
172:
129:
455:(greatest lower bound) of the function is attained.
251:{\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}
93:
but other dual problems are used – for example, the
6052:
6019:
5974:
5905:
5831:
5755:
5697:
5671:
4967:
Mathematical programming: Structures and algorithms
2247:{\displaystyle g(\lambda ):=\min _{x}L(x,\lambda )}
1375:holds. Otherwise the gap is strictly positive and
353:{\displaystyle f({\hat {x}})=\inf _{x\in X}f(x).\,}
46:may be viewed from either of two perspectives, the
5448:
5248:
5099:Network Flows: Theory, Algorithms and Applications
4620:Network Flows: Theory, Algorithms and Applications
4360:
4271:
4232:
3953:
3907:
3884:
3673:
3523:
3409:
3361:
3341:
3315:
3281:
3031:
2962:
2942:
2919:
2740:
2660:
2618:
2381:
2302:
2246:
2175:
2107:
1971:
1895:
1770:
1664:
1502:This intuition is made formal by the equations in
1363:
1323:
1296:
1251:
1227:
1197:
1064:
1005:
947:
918:
844:
824:
746:
629:
609:
550:
470:
443:
419:
381:
352:
279:
250:
201:
158:
5350:Combinatorial Optimization: Networks and Matroids
2322:), then the optimal solution to the dual program
2303:{\displaystyle \max _{\lambda \geq 0}g(\lambda )}
2051:Therefore, the original problem is equivalent to:
3715:
3495:
3453:
3122:
3071:
2345:
2273:
2217:
2146:
2130:
2072:
2062:
1921:
1246:
1158:
1090:
685:
645:
319:
5418:Mathematical programming: Theory and algorithms
4929:Mathematical programming: Theory and algorithms
4451:Boyd, Stephen P.; Vandenberghe, Lieven (2004).
1467:constraints from the primal problem. There are
825:{\displaystyle I_{\mathrm {constraints} }(x)=0}
105:of a minimization problem by using nonnegative
2119:By reversing the order of min and max, we get:
258:, we can define the primal problem as finding
89:Usually the term "dual problem" refers to the
5645:
8:
5255:. Princeton, NJ: Princeton University Press.
1000:
991:
245:
236:
5447:Nering, Evar D.; Tucker, Albert W. (1993).
4460:. Cambridge University Press. p. 216.
5652:
5638:
5630:
4970:. New York: Wiley-Interscience . pp.
4089:
3826:
3606:
3410:{\displaystyle g(\lambda ,\nu )\leq p^{*}}
2382:{\displaystyle \min _{x}L(x,\lambda ^{*})}
2191:is the inner problem in the above formula:
610:{\displaystyle I_{\mathrm {constraints} }}
71:problems, the duality gap is zero under a
4343:
4335:
4329:
4319:
4308:
4284:
4252:
4189:
4157:
4149:
4143:
4133:
4122:
4067:
4047:
4037:
4027:
4016:
3976:
3971:
3969:
3945:
3926:
3920:
3900:
3841:
3804:
3779:
3769:
3759:
3748:
3718:
3699:
3694:
3692:
3621:
3584:
3554:
3549:
3547:
3515:
3502:
3456:
3443:
3437:
3401:
3374:
3354:
3328:
3307:
3301:
3256:
3246:
3236:
3225:
3203:
3193:
3183:
3172:
3150:
3133:
3132:
3125:
3091:
3090:
3082:
3081:
3074:
3047:
3025:
3024:
3015:
3011:
3010:
3000:
2996:
2995:
2986:
2955:
2935:
2899:
2889:
2879:
2868:
2846:
2836:
2826:
2815:
2793:
2759:
2758:
2756:
2734:
2733:
2724:
2720:
2719:
2709:
2705:
2704:
2694:
2690:
2689:
2679:
2678:
2676:
2652:
2648:
2647:
2637:
2636:
2634:
2554:
2487:
2476:
2457:
2446:
2442:
2440:
2370:
2348:
2342:
2276:
2270:
2220:
2199:
2149:
2133:
2127:
2075:
2065:
2059:
1924:
1918:
1878:
1868:
1858:
1836:
1809:
1750:
1734:
1712:
1691:
1600:
1589:
1570:
1559:
1555:
1553:
1541:. Suppose we want to solve the following
1355:
1342:
1336:
1315:
1309:
1288:
1282:
1244:
1219:
1213:
1194:
1161:
1145:
1126:
1111:
1098:
1093:
1087:
1042:
1041:
1018:
984:
983:
963:
934:
933:
931:
864:
863:
857:
837:
770:
769:
763:
695:
688:
661:
660:
648:
642:
622:
570:
569:
563:
511:
510:
486:
485:
483:
463:
436:
403:
402:
394:
368:
367:
365:
349:
322:
301:
300:
292:
266:
265:
263:
229:
228:
214:
188:
171:
145:
128:
5291:(1993). "14 Duality for Practitioners".
5177:; Sagastizábal, Claudia A. (2006).
4806:(1993). "14 Duality for Practitioners".
4545:Convex analysis in general vector spaces
2334:* to the dual program, and then solving:
1771:{\displaystyle J(x)=f_{0}(x)+\sum _{i}I}
5742:Locally convex topological vector space
5451:Linear Programming and Related Problems
5229:(1st ed.). John Wiley & Sons.
5026:"Optimization III: Convex Optimization"
4443:
1065:{\displaystyle F(x,0)={\tilde {f}}(x)}
27:Principle in mathematical optimization
5320:Optimization theory for large systems
5019:
5017:
4841:Optimization theory for large systems
4582:Borwein, Jonathan; Zhu, Qiji (2005).
4486:
4484:
1785:: I=0 if u≤0, and I=∞ otherwise. But
7:
1395:, that is the function that has the
202:{\displaystyle \left(Y,Y^{*}\right)}
159:{\displaystyle \left(X,X^{*}\right)}
5139:(2nd ed.). Athena Scientific.
4672:(2nd ed.). Athena Scientific.
3954:{\displaystyle g_{1},\ldots ,g_{m}}
5585:Mathematics of Operations Research
4584:Techniques of Variational Analysis
4336:
4286:
4150:
4100:
4093:
4090:
4086:
4083:
4080:
4077:
4074:
4071:
4068:
3830:
3827:
3823:
3820:
3817:
3814:
3811:
3808:
3805:
3610:
3607:
3603:
3600:
3597:
3594:
3591:
3588:
3585:
2978:associated with the problem. The
1463:values that are the limits in the
997:
913:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
242:
25:
5251:Linear Programming and Extensions
5118:Convex Analysis and Optimization
5005:"Lagrangian Duality for Dummies"
4645:Convex Analysis and Optimization
4279:. Also, the equality constraint
3323:of the initial problem; for any
1491:and one or more constraints. An
5847:Ekeland's variational principle
5438:. (2008 Second ed., in French:
5287:Hiriart-Urruty, Jean-Baptiste;
5024:Nemirovsky and Ben-Tal (2023).
4949:. (2008 Second ed., in French:
4802:Hiriart-Urruty, Jean-Baptiste;
4204:
3856:
3684:the Lagrangian dual problem is
3645:
2668:having non-empty interior, the
2262:is the program of maximizing g:
2013:=0, and its value is then f(x);
1990:If x satisfies all constraints
852:satisfying the constraints and
75:condition. This fact is called
5474:(Unabridged ed.). Dover.
5455:. Boston, MA: Academic Press.
5318:Lasdon, Leon S. (2002) .
5154:Bertsekas, Dimitri P. (2009).
5135:Bertsekas, Dimitri P. (1999).
4839:Lasdon, Leon S. (2002) .
4693:Bertsekas, Dimitri P. (2009).
4668:Bertsekas, Dimitri P. (1999).
4541:Zălinescu, Constantin (2002).
4493:Duality in Vector Optimization
4355:
4349:
4298:
4292:
4266:
4254:
4169:
4163:
4112:
4106:
4059:
4053:
4006:
4000:
3791:
3785:
3738:
3732:
3633:
3627:
3576:
3570:
3489:
3477:
3391:
3379:
3342:{\displaystyle \lambda \geq 0}
3268:
3262:
3215:
3209:
3162:
3156:
3115:
3097:
3064:
3052:
3021:
2911:
2905:
2858:
2852:
2805:
2799:
2783:
2765:
2730:
2566:
2560:
2499:
2493:
2469:
2463:
2376:
2357:
2297:
2291:
2241:
2229:
2210:
2204:
2170:
2158:
2102:
2090:
1966:
1960:
1951:
1939:
1890:
1884:
1848:
1842:
1826:
1814:
1765:
1762:
1756:
1743:
1724:
1718:
1702:
1696:
1612:
1606:
1582:
1576:
1304:is the optimal dual value and
1188:
1176:
1151:
1132:
1059:
1053:
1047:
1035:
1023:
980:
939:
907:
901:
813:
807:
741:
735:
678:
672:
666:
491:
414:
408:
399:
373:
343:
337:
312:
306:
297:
271:
225:
1:
5624:Duality in Linear Programming
4724:Sagastizábal, Claudia A.
4516:Csetnek, Ernö Robert (2010).
2424:The strong Lagrange principle
1524:Karush–Kuhn–Tucker conditions
420:{\displaystyle f({\hat {x}})}
4520:. Logos Verlag Berlin GmbH.
948:{\displaystyle {\tilde {f}}}
5867:Hermite–Hadamard inequality
5352:. Dover. pp. 117–120.
4964:Shapiro, Jeremy F. (1979).
2976:Lagrange multiplier vectors
2009:) is maximized when taking
1504:Linear programming: Duality
1364:{\displaystyle p^{*}-d^{*}}
6102:
5498:Princeton University Press
5227:Combinatorial Optimization
5217:; Cunningham, William H.;
5156:Convex Optimization Theory
4695:Convex Optimization Theory
4432:Relaxation (approximation)
2020:violates some constraint,
1406:
1270:
617:is a suitable function on
382:{\displaystyle {\hat {x}}}
280:{\displaystyle {\hat {x}}}
5189:10.1007/978-3-540-35447-5
4738:10.1007/978-3-540-35447-5
2432:problem in standard form
2411:Fenchel's duality theorem
32:mathematical optimization
6053:Applications and related
5857:Fenchel-Young inequality
3422:constraint qualification
2943:{\displaystyle \lambda }
926:otherwise). Then extend
73:constraint qualification
5813:Legendre transformation
5737:Legendre transformation
5380:10.1007/3-540-45586-8_4
5219:Pulleyblank, William R.
4885:10.1007/3-540-45586-8_4
4406:support vector machines
2260:Lagrangian dual program
1781:where I is an infinite
756:characteristic function
91:Lagrangian dual problem
6060:Convexity in economics
5994:(lower) ideally convex
5852:Fenchel–Moreau theorem
5842:Carathéodory's theorem
5598:10.1287/moor.1070.0261
5494:Nonlinear Optimization
5003:David Knowles (2010).
4362:
4324:
4273:
4234:
4138:
4032:
3955:
3909:
3886:
3764:
3675:
3525:
3411:
3363:
3343:
3317:
3283:
3241:
3188:
3033:
2980:Lagrange dual function
2964:
2944:
2921:
2884:
2831:
2742:
2662:
2620:
2391:
2383:
2312:
2304:
2256:
2248:
2185:
2177:
2117:
2109:
1981:
1973:
1904:
1897:
1779:
1772:
1673:
1666:
1420:problems in which the
1365:
1325:
1298:
1253:
1239:in both variables and
1229:
1199:
1066:
1007:
949:
920:
846:
826:
748:
631:
611:
552:
472:
445:
421:
383:
354:
281:
252:
203:
160:
42:is the principle that
5982:Convex series related
5882:Shapley–Folkman lemma
5551:10.1287/opre.11.3.399
5225:(November 12, 1997).
5158:. Athena Scientific.
5137:Nonlinear Programming
5120:. Athena Scientific.
4697:. Athena Scientific.
4670:Nonlinear Programming
4647:. Athena Scientific.
4363:
4304:
4274:
4272:{\displaystyle (u,x)}
4235:
4118:
4012:
3956:
3910:
3887:
3744:
3676:
3526:
3412:
3364:
3344:
3318:
3316:{\displaystyle p^{*}}
3284:
3221:
3168:
3034:
2965:
2945:
2922:
2864:
2811:
2743:
2663:
2621:
2430:nonlinear programming
2407:quadratic programming
2384:
2336:
2305:
2264:
2249:
2193:
2178:
2121:
2110:
2053:
1974:
1912:
1906:Note that, for every
1898:
1803:
1773:
1685:
1667:
1547:
1543:nonlinear programming
1516:nonlinear programming
1436:variables. There are
1366:
1326:
1324:{\displaystyle p^{*}}
1299:
1297:{\displaystyle d^{*}}
1263:(least upper bound).
1254:
1252:{\displaystyle \sup }
1230:
1228:{\displaystyle F^{*}}
1200:
1067:
1008:
957:perturbation function
950:
921:
847:
827:
749:
632:
612:
553:
473:
446:
422:
384:
355:
282:
253:
204:
161:
122:locally convex spaces
113:In general given two
44:optimization problems
5872:Krein–Milman theorem
5665:variational analysis
5500:. pp. xii+454.
5490:Ruszczyński, Andrzej
5223:Schrijver, Alexander
4283:
4251:
3968:
3919:
3899:
3691:
3546:
3436:
3373:
3362:{\displaystyle \nu }
3353:
3327:
3300:
3046:
2985:
2963:{\displaystyle \nu }
2954:
2934:
2755:
2675:
2633:
2439:
2341:
2269:
2198:
2126:
2058:
1917:
1808:
1690:
1552:
1335:
1308:
1281:
1243:
1212:
1086:
1017:
962:
930:
856:
836:
762:
641:
621:
562:
482:
462:
435:
393:
364:
291:
262:
213:
170:
127:
107:Lagrange multipliers
99:Fenchel dual problem
6081:Convex optimization
5862:Jensen's inequality
5732:Lagrange multiplier
5722:Convex optimization
5717:Convex metric space
5539:Operations Research
5091:Magnanti, Thomas L.
4612:Magnanti, Thomas L.
4454:Convex Optimization
2670:Lagrangian function
1409:Dual linear program
360:In other words, if
69:convex optimization
6086:Linear programming
5990:(cs, bcs)-complete
5961:Algebraic interior
5679:Convex combination
5368:Lemaréchal, Claude
5289:Lemaréchal, Claude
5245:Dantzig, George B.
5175:Lemaréchal, Claude
5087:Ahuja, Ravindra K.
4873:Lemaréchal, Claude
4804:Lemaréchal, Claude
4720:Lemaréchal, Claude
4608:Ahuja, Ravindra K.
4358:
4269:
4245:Wolfe dual problem
4230:
4228:
3992:
3951:
3905:
3882:
3880:
3723:
3707:
3671:
3669:
3562:
3521:
3473:
3426:Slater's condition
3407:
3359:
3339:
3313:
3292:The dual function
3279:
3140:
3089:
3029:
2960:
2940:
2917:
2738:
2658:
2616:
2614:
2403:linear programming
2379:
2353:
2320:Slater's condition
2300:
2287:
2244:
2225:
2173:
2154:
2144:
2105:
2086:
2070:
1969:
1935:
1893:
1863:
1768:
1739:
1662:
1660:
1489:candidate solution
1422:objective function
1414:Linear programming
1361:
1321:
1294:
1249:
1225:
1195:
1172:
1118:
1062:
1003:
945:
916:
842:
822:
744:
731:
659:
627:
607:
548:
468:
441:
417:
379:
350:
333:
277:
248:
199:
156:
95:Wolfe dual problem
6068:
6067:
5531:Everett, Hugh III
5507:978-0-691-11915-1
5496:. Princeton, NJ:
5462:978-0-12-515440-6
5329:978-0-486-41999-2
5165:978-1-886529-31-1
5101:. Prentice Hall.
4850:978-0-486-41999-2
4704:978-1-886529-31-1
4622:. Prentice Hall.
4593:978-1-4419-2026-3
4527:978-3-8325-2503-3
4502:978-3-642-02885-4
4467:978-0-521-83378-3
3977:
3908:{\displaystyle f}
3714:
3700:
3555:
3452:
3121:
3070:
2580:
2513:
2479:
2449:
2344:
2272:
2216:
2145:
2129:
2071:
2061:
1920:
1854:
1730:
1626:
1592:
1562:
1534:Lagrange duality
1385:convex relaxation
1157:
1089:
1050:
942:
845:{\displaystyle x}
694:
684:
669:
644:
630:{\displaystyle X}
494:
471:{\displaystyle f}
444:{\displaystyle f}
411:
376:
318:
309:
274:
209:and the function
40:duality principle
16:(Redirected from
6093:
5986:(cs, lcs)-closed
5932:Effective domain
5887:Robinson–Ursescu
5763:Convex conjugate
5654:
5647:
5640:
5631:
5620:
5618:
5617:
5608:. Archived from
5574:
5569:. Archived from
5519:
5485:
5466:
5454:
5443:
5409:
5363:
5341:
5314:
5283:
5256:
5254:
5240:
5215:Cook, William J.
5210:
5169:
5150:
5131:
5112:
5068:
5067:
5039:
5033:
5032:
5030:
5021:
5012:
5011:
5009:
5000:
4994:
4993:
4961:
4955:
4954:
4921:
4915:
4914:
4869:
4863:
4862:
4836:
4830:
4829:
4799:
4793:
4792:
4766:
4760:
4759:
4715:
4709:
4708:
4690:
4684:
4683:
4665:
4659:
4658:
4640:
4634:
4633:
4604:
4598:
4597:
4579:
4573:
4572:
4548:
4538:
4532:
4531:
4513:
4507:
4506:
4488:
4479:
4478:
4476:
4474:
4459:
4448:
4394:Albert W. Tucker
4386:John von Neumann
4367:
4365:
4364:
4359:
4348:
4347:
4334:
4333:
4323:
4318:
4278:
4276:
4275:
4270:
4239:
4237:
4236:
4231:
4229:
4194:
4193:
4183:
4182:
4181:
4162:
4161:
4148:
4147:
4137:
4132:
4098:
4096:
4065:
4052:
4051:
4042:
4041:
4031:
4026:
3995:
3993:
3991:
3974:
3960:
3958:
3957:
3952:
3950:
3949:
3931:
3930:
3914:
3912:
3911:
3906:
3891:
3889:
3888:
3883:
3881:
3846:
3845:
3835:
3833:
3802:
3798:
3794:
3784:
3783:
3774:
3773:
3763:
3758:
3722:
3710:
3708:
3697:
3680:
3678:
3677:
3672:
3670:
3626:
3625:
3615:
3613:
3582:
3565:
3563:
3552:
3530:
3528:
3527:
3522:
3520:
3519:
3507:
3506:
3472:
3448:
3447:
3416:
3414:
3413:
3408:
3406:
3405:
3368:
3366:
3365:
3360:
3348:
3346:
3345:
3340:
3322:
3320:
3319:
3314:
3312:
3311:
3288:
3286:
3285:
3280:
3275:
3271:
3261:
3260:
3251:
3250:
3240:
3235:
3208:
3207:
3198:
3197:
3187:
3182:
3155:
3154:
3139:
3138:
3137:
3096:
3095:
3088:
3087:
3086:
3038:
3036:
3035:
3030:
3028:
3020:
3019:
3014:
3005:
3004:
2999:
2969:
2967:
2966:
2961:
2949:
2947:
2946:
2941:
2926:
2924:
2923:
2918:
2904:
2903:
2894:
2893:
2883:
2878:
2851:
2850:
2841:
2840:
2830:
2825:
2798:
2797:
2764:
2763:
2747:
2745:
2744:
2739:
2737:
2729:
2728:
2723:
2714:
2713:
2708:
2699:
2698:
2693:
2684:
2683:
2667:
2665:
2664:
2659:
2657:
2656:
2651:
2642:
2641:
2629:with the domain
2625:
2623:
2622:
2617:
2615:
2611:
2607:
2578:
2559:
2558:
2548:
2544:
2540:
2511:
2492:
2491:
2480:
2478:subject to
2477:
2462:
2461:
2450:
2447:
2388:
2386:
2385:
2380:
2375:
2374:
2352:
2309:
2307:
2306:
2301:
2286:
2253:
2251:
2250:
2245:
2224:
2182:
2180:
2179:
2174:
2153:
2143:
2114:
2112:
2111:
2106:
2085:
2069:
2031:)>0 for some
1978:
1976:
1975:
1970:
1934:
1902:
1900:
1899:
1894:
1883:
1882:
1873:
1872:
1862:
1841:
1840:
1777:
1775:
1774:
1769:
1755:
1754:
1738:
1717:
1716:
1671:
1669:
1668:
1663:
1661:
1657:
1653:
1624:
1605:
1604:
1593:
1591:subject to
1590:
1575:
1574:
1563:
1560:
1475:dual variables.
1370:
1368:
1367:
1362:
1360:
1359:
1347:
1346:
1330:
1328:
1327:
1322:
1320:
1319:
1303:
1301:
1300:
1295:
1293:
1292:
1258:
1256:
1255:
1250:
1237:convex conjugate
1234:
1232:
1231:
1226:
1224:
1223:
1204:
1202:
1201:
1196:
1171:
1150:
1149:
1131:
1130:
1117:
1116:
1115:
1103:
1102:
1071:
1069:
1068:
1063:
1052:
1051:
1043:
1012:
1010:
1009:
1004:
987:
954:
952:
951:
946:
944:
943:
935:
925:
923:
922:
917:
900:
899:
898:
851:
849:
848:
843:
831:
829:
828:
823:
806:
805:
804:
753:
751:
750:
745:
730:
729:
692:
671:
670:
662:
658:
636:
634:
633:
628:
616:
614:
613:
608:
606:
605:
604:
557:
555:
554:
549:
547:
546:
545:
496:
495:
487:
477:
475:
474:
469:
450:
448:
447:
442:
431:of the function
426:
424:
423:
418:
413:
412:
404:
388:
386:
385:
380:
378:
377:
369:
359:
357:
356:
351:
332:
311:
310:
302:
286:
284:
283:
278:
276:
275:
267:
257:
255:
254:
249:
232:
208:
206:
205:
200:
198:
194:
193:
192:
165:
163:
162:
157:
155:
151:
150:
149:
21:
6101:
6100:
6096:
6095:
6094:
6092:
6091:
6090:
6071:
6070:
6069:
6064:
6048:
6015:
5970:
5901:
5827:
5818:Semi-continuity
5803:Convex function
5784:Logarithmically
5751:
5712:Convex geometry
5693:
5684:Convex function
5667:
5661:Convex analysis
5658:
5615:
5613:
5577:
5529:
5526:
5508:
5488:
5482:
5469:
5463:
5446:
5428:
5412:
5390:
5366:
5360:
5344:
5330:
5317:
5303:
5286:
5272:
5259:
5243:
5237:
5213:
5199:
5172:
5166:
5153:
5147:
5134:
5128:
5115:
5109:
5095:Orlin, James B.
5085:
5082:
5077:
5072:
5071:
5056:10.1137/1013001
5041:
5040:
5036:
5028:
5023:
5022:
5015:
5007:
5002:
5001:
4997:
4982:
4963:
4962:
4958:
4939:
4923:
4922:
4918:
4895:
4871:
4870:
4866:
4851:
4838:
4837:
4833:
4818:
4801:
4800:
4796:
4781:
4768:
4767:
4763:
4748:
4717:
4716:
4712:
4705:
4692:
4691:
4687:
4680:
4667:
4666:
4662:
4655:
4642:
4641:
4637:
4630:
4616:Orlin, James B.
4606:
4605:
4601:
4594:
4581:
4580:
4576:
4561:
4540:
4539:
4535:
4528:
4515:
4514:
4510:
4503:
4490:
4489:
4482:
4472:
4470:
4468:
4457:
4450:
4449:
4445:
4440:
4418:
4402:
4378:
4339:
4325:
4281:
4280:
4249:
4248:
4227:
4226:
4185:
4179:
4178:
4153:
4139:
4097:
4063:
4062:
4043:
4033:
3994:
3981:
3966:
3965:
3941:
3922:
3917:
3916:
3897:
3896:
3879:
3878:
3837:
3834:
3800:
3799:
3775:
3765:
3728:
3724:
3709:
3689:
3688:
3668:
3667:
3617:
3614:
3580:
3579:
3564:
3544:
3543:
3537:
3535:Convex problems
3511:
3498:
3439:
3434:
3433:
3397:
3371:
3370:
3351:
3350:
3325:
3324:
3303:
3298:
3297:
3252:
3242:
3199:
3189:
3146:
3145:
3141:
3044:
3043:
3009:
2994:
2983:
2982:
2970:are called the
2952:
2951:
2932:
2931:
2895:
2885:
2842:
2832:
2789:
2753:
2752:
2718:
2703:
2688:
2673:
2672:
2646:
2631:
2630:
2613:
2612:
2591:
2587:
2550:
2546:
2545:
2524:
2520:
2483:
2481:
2473:
2472:
2453:
2451:
2437:
2436:
2426:
2366:
2339:
2338:
2267:
2266:
2196:
2195:
2124:
2123:
2056:
2055:
2044:
2025:
1995:
1915:
1914:
1874:
1864:
1832:
1806:
1805:
1746:
1708:
1688:
1687:
1659:
1658:
1637:
1633:
1596:
1594:
1586:
1585:
1566:
1564:
1550:
1549:
1536:
1512:
1481:
1411:
1405:
1351:
1338:
1333:
1332:
1311:
1306:
1305:
1284:
1279:
1278:
1275:
1269:
1241:
1240:
1215:
1210:
1209:
1141:
1122:
1107:
1094:
1084:
1083:
1015:
1014:
960:
959:
928:
927:
859:
854:
853:
834:
833:
765:
760:
759:
639:
638:
619:
618:
565:
560:
559:
506:
480:
479:
460:
459:
433:
432:
391:
390:
362:
361:
289:
288:
260:
259:
211:
210:
184:
177:
173:
168:
167:
141:
134:
130:
125:
124:
87:
28:
23:
22:
15:
12:
11:
5:
6099:
6097:
6089:
6088:
6083:
6073:
6072:
6066:
6065:
6063:
6062:
6056:
6054:
6050:
6049:
6047:
6046:
6041:
6039:Strong duality
6036:
6031:
6025:
6023:
6017:
6016:
6014:
6013:
5978:
5976:
5972:
5971:
5969:
5968:
5963:
5954:
5949:
5947:John ellipsoid
5944:
5939:
5934:
5929:
5915:
5909:
5907:
5903:
5902:
5900:
5899:
5894:
5889:
5884:
5879:
5874:
5869:
5864:
5859:
5854:
5849:
5844:
5838:
5836:
5834:results (list)
5829:
5828:
5826:
5825:
5820:
5815:
5810:
5808:Invex function
5805:
5796:
5791:
5786:
5781:
5776:
5770:
5765:
5759:
5757:
5753:
5752:
5750:
5749:
5744:
5739:
5734:
5729:
5724:
5719:
5714:
5709:
5707:Choquet theory
5703:
5701:
5695:
5694:
5692:
5691:
5686:
5681:
5675:
5673:
5672:Basic concepts
5669:
5668:
5659:
5657:
5656:
5649:
5642:
5634:
5628:
5627:
5621:
5592:(3): 669–686.
5575:
5573:on 2011-07-24.
5545:(3): 399–417.
5525:
5522:
5521:
5520:
5506:
5486:
5480:
5467:
5461:
5444:
5426:
5414:Minoux, Michel
5410:
5388:
5364:
5358:
5346:Lawler, Eugene
5342:
5328:
5315:
5301:
5284:
5270:
5257:
5241:
5235:
5211:
5197:
5170:
5164:
5151:
5145:
5132:
5126:
5113:
5107:
5081:
5078:
5076:
5073:
5070:
5069:
5034:
5013:
4995:
4980:
4956:
4937:
4925:Minoux, Michel
4916:
4893:
4864:
4849:
4831:
4816:
4794:
4779:
4761:
4746:
4710:
4703:
4685:
4678:
4660:
4653:
4635:
4628:
4599:
4592:
4574:
4559:
4533:
4526:
4508:
4501:
4480:
4466:
4442:
4441:
4439:
4436:
4435:
4434:
4429:
4424:
4422:Convex duality
4417:
4414:
4401:
4398:
4382:George Dantzig
4377:
4374:
4357:
4354:
4351:
4346:
4342:
4338:
4332:
4328:
4322:
4317:
4314:
4311:
4307:
4303:
4300:
4297:
4294:
4291:
4288:
4268:
4265:
4262:
4259:
4256:
4243:is called the
4241:
4240:
4225:
4222:
4219:
4216:
4213:
4210:
4207:
4203:
4200:
4197:
4192:
4188:
4184:
4180:
4177:
4174:
4171:
4168:
4165:
4160:
4156:
4152:
4146:
4142:
4136:
4131:
4128:
4125:
4121:
4117:
4114:
4111:
4108:
4105:
4102:
4099:
4095:
4092:
4088:
4085:
4082:
4079:
4076:
4073:
4070:
4066:
4064:
4061:
4058:
4055:
4050:
4046:
4040:
4036:
4030:
4025:
4022:
4019:
4015:
4011:
4008:
4005:
4002:
3999:
3996:
3990:
3987:
3984:
3980:
3975:
3973:
3948:
3944:
3940:
3937:
3934:
3929:
3925:
3904:
3893:
3892:
3877:
3874:
3871:
3868:
3865:
3862:
3859:
3855:
3852:
3849:
3844:
3840:
3836:
3832:
3829:
3825:
3822:
3819:
3816:
3813:
3810:
3807:
3803:
3801:
3797:
3793:
3790:
3787:
3782:
3778:
3772:
3768:
3762:
3757:
3754:
3751:
3747:
3743:
3740:
3737:
3734:
3731:
3727:
3721:
3717:
3713:
3711:
3706:
3703:
3698:
3696:
3682:
3681:
3666:
3663:
3660:
3657:
3654:
3651:
3648:
3644:
3641:
3638:
3635:
3632:
3629:
3624:
3620:
3616:
3612:
3609:
3605:
3602:
3599:
3596:
3593:
3590:
3587:
3583:
3581:
3578:
3575:
3572:
3569:
3566:
3561:
3558:
3553:
3551:
3536:
3533:
3518:
3514:
3510:
3505:
3501:
3497:
3494:
3491:
3488:
3485:
3482:
3479:
3476:
3471:
3468:
3465:
3462:
3459:
3455:
3451:
3446:
3442:
3430:strong duality
3404:
3400:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3358:
3338:
3335:
3332:
3310:
3306:
3290:
3289:
3278:
3274:
3270:
3267:
3264:
3259:
3255:
3249:
3245:
3239:
3234:
3231:
3228:
3224:
3220:
3217:
3214:
3211:
3206:
3202:
3196:
3192:
3186:
3181:
3178:
3175:
3171:
3167:
3164:
3161:
3158:
3153:
3149:
3144:
3136:
3131:
3128:
3124:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3094:
3085:
3080:
3077:
3073:
3069:
3066:
3063:
3060:
3057:
3054:
3051:
3039:is defined as
3027:
3023:
3018:
3013:
3008:
3003:
2998:
2993:
2990:
2972:dual variables
2959:
2939:
2928:
2927:
2916:
2913:
2910:
2907:
2902:
2898:
2892:
2888:
2882:
2877:
2874:
2871:
2867:
2863:
2860:
2857:
2854:
2849:
2845:
2839:
2835:
2829:
2824:
2821:
2818:
2814:
2810:
2807:
2804:
2801:
2796:
2792:
2788:
2785:
2782:
2779:
2776:
2773:
2770:
2767:
2762:
2748:is defined as
2736:
2732:
2727:
2722:
2717:
2712:
2707:
2702:
2697:
2692:
2687:
2682:
2655:
2650:
2645:
2640:
2627:
2626:
2610:
2606:
2603:
2600:
2597:
2594:
2590:
2586:
2583:
2577:
2574:
2571:
2568:
2565:
2562:
2557:
2553:
2549:
2547:
2543:
2539:
2536:
2533:
2530:
2527:
2523:
2519:
2516:
2510:
2507:
2504:
2501:
2498:
2495:
2490:
2486:
2482:
2475:
2474:
2471:
2468:
2465:
2460:
2456:
2452:
2448:minimize
2445:
2444:
2425:
2422:
2378:
2373:
2369:
2365:
2362:
2359:
2356:
2351:
2347:
2328:strong duality
2299:
2296:
2293:
2290:
2285:
2282:
2279:
2275:
2243:
2240:
2237:
2234:
2231:
2228:
2223:
2219:
2215:
2212:
2209:
2206:
2203:
2172:
2169:
2166:
2163:
2160:
2157:
2152:
2148:
2142:
2139:
2136:
2132:
2104:
2101:
2098:
2095:
2092:
2089:
2084:
2081:
2078:
2074:
2068:
2064:
2049:
2048:
2042:
2023:
2014:
1993:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1947:
1944:
1941:
1938:
1933:
1930:
1927:
1923:
1892:
1889:
1886:
1881:
1877:
1871:
1867:
1861:
1857:
1853:
1850:
1847:
1844:
1839:
1835:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1767:
1764:
1761:
1758:
1753:
1749:
1745:
1742:
1737:
1733:
1729:
1726:
1723:
1720:
1715:
1711:
1707:
1704:
1701:
1698:
1695:
1656:
1652:
1649:
1646:
1643:
1640:
1636:
1632:
1629:
1623:
1620:
1617:
1614:
1611:
1608:
1603:
1599:
1595:
1588:
1587:
1584:
1581:
1578:
1573:
1569:
1565:
1561:minimize
1558:
1557:
1535:
1532:
1511:
1510:Nonlinear case
1508:
1480:
1477:
1407:Main article:
1404:
1401:
1373:strong duality
1358:
1354:
1350:
1345:
1341:
1318:
1314:
1291:
1287:
1271:Main article:
1268:
1265:
1248:
1222:
1218:
1206:
1205:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1170:
1167:
1164:
1160:
1156:
1153:
1148:
1144:
1140:
1137:
1134:
1129:
1125:
1121:
1114:
1110:
1106:
1101:
1097:
1092:
1061:
1058:
1055:
1049:
1046:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1002:
999:
996:
993:
990:
986:
982:
979:
976:
973:
970:
967:
941:
938:
915:
912:
909:
906:
903:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
862:
841:
821:
818:
815:
812:
809:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
768:
743:
740:
737:
734:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
691:
687:
683:
680:
677:
674:
668:
665:
657:
654:
651:
647:
626:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
568:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
509:
505:
502:
499:
493:
490:
467:
440:
416:
410:
407:
401:
398:
375:
372:
348:
345:
342:
339:
336:
331:
328:
325:
321:
317:
314:
308:
305:
299:
296:
273:
270:
247:
244:
241:
238:
235:
231:
227:
224:
221:
218:
197:
191:
187:
183:
180:
176:
154:
148:
144:
140:
137:
133:
86:
83:
78:strong duality
48:primal problem
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
6098:
6087:
6084:
6082:
6079:
6078:
6076:
6061:
6058:
6057:
6055:
6051:
6045:
6042:
6040:
6037:
6035:
6032:
6030:
6027:
6026:
6024:
6022:
6018:
6011:
6009:
6003:
6001:
5995:
5991:
5987:
5983:
5980:
5979:
5977:
5973:
5967:
5964:
5962:
5958:
5955:
5953:
5950:
5948:
5945:
5943:
5940:
5938:
5935:
5933:
5930:
5928:
5924:
5920:
5916:
5914:
5911:
5910:
5908:
5904:
5898:
5895:
5893:
5890:
5888:
5885:
5883:
5880:
5878:
5877:Mazur's lemma
5875:
5873:
5870:
5868:
5865:
5863:
5860:
5858:
5855:
5853:
5850:
5848:
5845:
5843:
5840:
5839:
5837:
5835:
5830:
5824:
5823:Subderivative
5821:
5819:
5816:
5814:
5811:
5809:
5806:
5804:
5800:
5797:
5795:
5792:
5790:
5787:
5785:
5782:
5780:
5777:
5775:
5771:
5769:
5766:
5764:
5761:
5760:
5758:
5754:
5748:
5745:
5743:
5740:
5738:
5735:
5733:
5730:
5728:
5725:
5723:
5720:
5718:
5715:
5713:
5710:
5708:
5705:
5704:
5702:
5700:
5699:Topics (list)
5696:
5690:
5687:
5685:
5682:
5680:
5677:
5676:
5674:
5670:
5666:
5662:
5655:
5650:
5648:
5643:
5641:
5636:
5635:
5632:
5626:Gary D. Knott
5625:
5622:
5612:on 2011-07-26
5611:
5607:
5603:
5599:
5595:
5591:
5587:
5586:
5581:
5576:
5572:
5568:
5564:
5560:
5556:
5552:
5548:
5544:
5540:
5536:
5532:
5528:
5527:
5523:
5517:
5513:
5509:
5503:
5499:
5495:
5491:
5487:
5483:
5481:0-486-40258-4
5477:
5473:
5468:
5464:
5458:
5453:
5452:
5445:
5441:
5437:
5433:
5429:
5427:0-471-90170-9
5423:
5419:
5415:
5411:
5407:
5403:
5399:
5395:
5391:
5389:3-540-42877-1
5385:
5381:
5377:
5373:
5369:
5365:
5361:
5359:0-486-41453-1
5355:
5351:
5347:
5343:
5339:
5335:
5331:
5325:
5321:
5316:
5312:
5308:
5304:
5302:3-540-56852-2
5298:
5294:
5290:
5285:
5281:
5277:
5273:
5271:3-540-56850-6
5267:
5263:
5258:
5253:
5252:
5246:
5242:
5238:
5236:0-471-55894-X
5232:
5228:
5224:
5220:
5216:
5212:
5208:
5204:
5200:
5198:3-540-35445-X
5194:
5190:
5186:
5182:
5181:
5176:
5171:
5167:
5161:
5157:
5152:
5148:
5146:1-886529-00-0
5142:
5138:
5133:
5129:
5127:1-886529-45-0
5123:
5119:
5114:
5110:
5108:0-13-617549-X
5104:
5100:
5096:
5092:
5088:
5084:
5083:
5079:
5074:
5065:
5061:
5057:
5053:
5049:
5045:
5038:
5035:
5027:
5020:
5018:
5014:
5006:
4999:
4996:
4991:
4987:
4983:
4981:0-471-77886-9
4977:
4973:
4969:
4968:
4960:
4957:
4952:
4948:
4944:
4940:
4938:0-471-90170-9
4934:
4930:
4926:
4920:
4917:
4912:
4908:
4904:
4900:
4896:
4894:3-540-42877-1
4890:
4886:
4882:
4878:
4874:
4868:
4865:
4860:
4856:
4852:
4846:
4842:
4835:
4832:
4827:
4823:
4819:
4817:3-540-56852-2
4813:
4809:
4805:
4798:
4795:
4790:
4786:
4782:
4780:3-540-56850-6
4776:
4772:
4765:
4762:
4757:
4753:
4749:
4747:3-540-35445-X
4743:
4739:
4735:
4731:
4730:
4725:
4721:
4714:
4711:
4706:
4700:
4696:
4689:
4686:
4681:
4679:1-886529-00-0
4675:
4671:
4664:
4661:
4656:
4654:1-886529-45-0
4650:
4646:
4639:
4636:
4631:
4629:0-13-617549-X
4625:
4621:
4617:
4613:
4609:
4603:
4600:
4595:
4589:
4585:
4578:
4575:
4570:
4566:
4562:
4560:981-238-067-1
4556:
4552:
4547:
4546:
4537:
4534:
4529:
4523:
4519:
4512:
4509:
4504:
4498:
4494:
4487:
4485:
4481:
4469:
4463:
4456:
4455:
4447:
4444:
4437:
4433:
4430:
4428:
4425:
4423:
4420:
4419:
4415:
4413:
4411:
4407:
4399:
4397:
4395:
4391:
4387:
4383:
4380:According to
4375:
4373:
4371:
4352:
4344:
4340:
4330:
4326:
4320:
4315:
4312:
4309:
4305:
4301:
4295:
4289:
4263:
4260:
4257:
4246:
4223:
4220:
4217:
4214:
4211:
4208:
4205:
4201:
4198:
4195:
4190:
4186:
4175:
4172:
4166:
4158:
4154:
4144:
4140:
4134:
4129:
4126:
4123:
4119:
4115:
4109:
4103:
4056:
4048:
4044:
4038:
4034:
4028:
4023:
4020:
4017:
4013:
4009:
4003:
3997:
3988:
3985:
3982:
3978:
3964:
3963:
3962:
3946:
3942:
3938:
3935:
3932:
3927:
3923:
3902:
3875:
3872:
3869:
3866:
3863:
3860:
3857:
3853:
3850:
3847:
3842:
3838:
3795:
3788:
3780:
3776:
3770:
3766:
3760:
3755:
3752:
3749:
3745:
3741:
3735:
3729:
3725:
3719:
3712:
3704:
3701:
3687:
3686:
3685:
3664:
3661:
3658:
3655:
3652:
3649:
3646:
3642:
3639:
3636:
3630:
3622:
3618:
3573:
3567:
3559:
3556:
3542:
3541:
3540:
3534:
3532:
3516:
3512:
3508:
3503:
3499:
3492:
3486:
3483:
3480:
3474:
3469:
3466:
3463:
3460:
3457:
3449:
3444:
3440:
3431:
3427:
3423:
3418:
3402:
3398:
3394:
3388:
3385:
3382:
3376:
3356:
3336:
3333:
3330:
3308:
3304:
3295:
3276:
3272:
3265:
3257:
3253:
3247:
3243:
3237:
3232:
3229:
3226:
3222:
3218:
3212:
3204:
3200:
3194:
3190:
3184:
3179:
3176:
3173:
3169:
3165:
3159:
3151:
3147:
3142:
3129:
3126:
3118:
3112:
3109:
3106:
3103:
3100:
3078:
3075:
3067:
3061:
3058:
3055:
3049:
3042:
3041:
3040:
3016:
3006:
3001:
2991:
2988:
2981:
2977:
2973:
2957:
2937:
2914:
2908:
2900:
2896:
2890:
2886:
2880:
2875:
2872:
2869:
2865:
2861:
2855:
2847:
2843:
2837:
2833:
2827:
2822:
2819:
2816:
2812:
2808:
2802:
2794:
2790:
2786:
2780:
2777:
2774:
2771:
2768:
2751:
2750:
2749:
2725:
2715:
2710:
2700:
2695:
2685:
2671:
2653:
2643:
2608:
2604:
2601:
2598:
2595:
2592:
2588:
2584:
2581:
2575:
2572:
2569:
2563:
2555:
2551:
2541:
2537:
2534:
2531:
2528:
2525:
2521:
2517:
2514:
2508:
2505:
2502:
2496:
2488:
2484:
2466:
2458:
2454:
2435:
2434:
2433:
2431:
2423:
2421:
2419:
2414:
2412:
2408:
2404:
2400:
2396:
2390:
2371:
2367:
2363:
2360:
2354:
2349:
2335:
2333:
2329:
2325:
2321:
2317:
2311:
2294:
2288:
2283:
2280:
2277:
2263:
2261:
2255:
2238:
2235:
2232:
2226:
2221:
2213:
2207:
2201:
2192:
2190:
2189:dual function
2184:
2167:
2164:
2161:
2155:
2150:
2140:
2137:
2134:
2120:
2116:
2099:
2096:
2093:
2087:
2082:
2079:
2076:
2066:
2052:
2046:
2038:
2034:
2030:
2026:
2019:
2015:
2012:
2008:
2004:
2000:
1996:
1989:
1988:
1987:
1985:
1980:
1963:
1957:
1954:
1948:
1945:
1942:
1936:
1931:
1928:
1925:
1911:
1909:
1903:
1887:
1879:
1875:
1869:
1865:
1859:
1855:
1851:
1845:
1837:
1833:
1829:
1823:
1820:
1817:
1811:
1802:
1800:
1796:
1792:
1788:
1784:
1783:step function
1778:
1759:
1751:
1747:
1740:
1735:
1731:
1727:
1721:
1713:
1709:
1705:
1699:
1693:
1684:
1683:), defined as
1682:
1678:
1672:
1654:
1650:
1647:
1644:
1641:
1638:
1634:
1630:
1627:
1621:
1618:
1615:
1609:
1601:
1597:
1579:
1571:
1567:
1546:
1544:
1540:
1533:
1531:
1529:
1525:
1519:
1517:
1509:
1507:
1505:
1500:
1496:
1494:
1490:
1486:
1478:
1476:
1474:
1470:
1466:
1462:
1457:
1455:
1451:
1447:
1443:
1439:
1435:
1431:
1427:
1423:
1419:
1416:problems are
1415:
1410:
1402:
1400:
1398:
1394:
1390:
1386:
1380:
1378:
1374:
1356:
1352:
1348:
1343:
1339:
1316:
1312:
1289:
1285:
1274:
1266:
1264:
1262:
1238:
1220:
1216:
1191:
1185:
1182:
1179:
1173:
1168:
1165:
1162:
1154:
1146:
1142:
1138:
1135:
1127:
1123:
1119:
1112:
1108:
1104:
1099:
1095:
1082:
1081:
1080:
1078:
1073:
1056:
1044:
1038:
1032:
1029:
1026:
1020:
994:
988:
977:
974:
971:
968:
965:
958:
936:
910:
904:
860:
839:
819:
816:
810:
766:
757:
738:
732:
689:
681:
675:
663:
655:
652:
649:
624:
566:
507:
503:
500:
497:
488:
465:
456:
454:
438:
430:
405:
396:
370:
346:
340:
334:
329:
326:
323:
315:
303:
294:
268:
239:
233:
222:
219:
216:
195:
189:
185:
181:
178:
174:
152:
146:
142:
138:
135:
131:
123:
120:
116:
111:
108:
104:
100:
96:
92:
84:
82:
80:
79:
74:
70:
66:
61:
59:
58:
53:
49:
45:
41:
37:
33:
19:
18:Dual function
6044:Weak duality
6020:
6007:
5999:
5919:Orthogonally
5726:
5614:. Retrieved
5610:the original
5589:
5583:
5571:the original
5542:
5538:
5493:
5471:
5450:
5439:
5417:
5371:
5349:
5319:
5292:
5261:
5250:
5226:
5179:
5155:
5136:
5117:
5098:
5047:
5043:
5037:
4998:
4966:
4959:
4950:
4928:
4919:
4876:
4867:
4840:
4834:
4807:
4797:
4770:
4764:
4728:
4713:
4694:
4688:
4669:
4663:
4644:
4638:
4619:
4602:
4586:. Springer.
4583:
4577:
4544:
4536:
4517:
4511:
4495:. Springer.
4492:
4471:. Retrieved
4453:
4446:
4410:Kernel trick
4403:
4400:Applications
4379:
4370:weak duality
4242:
3894:
3683:
3538:
3419:
3293:
3291:
2979:
2975:
2971:
2930:The vectors
2929:
2669:
2628:
2427:
2418:saddle point
2415:
2398:
2394:
2392:
2337:
2331:
2327:
2323:
2316:weak duality
2315:
2313:
2265:
2259:
2257:
2194:
2188:
2186:
2122:
2118:
2054:
2050:
2040:
2036:
2032:
2028:
2021:
2017:
2010:
2006:
2002:
2001:)≤0, then L(
1998:
1991:
1983:
1982:
1913:
1907:
1905:
1804:
1798:
1794:
1790:
1786:
1780:
1686:
1680:
1676:
1674:
1548:
1538:
1537:
1527:
1520:
1513:
1501:
1497:
1492:
1482:
1472:
1468:
1464:
1460:
1458:
1453:
1452:(a list) of
1445:
1441:
1437:
1433:
1418:optimization
1412:
1384:
1381:
1377:weak duality
1276:
1259:denotes the
1207:
1074:
457:
112:
90:
88:
85:Dual problem
76:
62:
57:weak duality
55:
52:dual problem
51:
47:
39:
35:
29:
6034:Duality gap
6029:Dual system
5913:Convex hull
5050:(1): 1–37.
5044:SIAM Review
4473:October 15,
4390:game theory
2035:, then L(x,
1426:constraints
1403:Linear case
1389:convex hull
1273:Duality gap
1267:Duality gap
1077:duality gap
478:by letting
65:duality gap
6075:Categories
5957:Radial set
5927:Convex set
5689:Convex set
5616:2011-05-12
5075:References
1539:Motivation
1493:infeasible
1013:such that
287:such that
115:dual pairs
103:Lagrangian
5942:Hypograph
4337:∇
4306:∑
4287:∇
4218:…
4196:≥
4151:∇
4120:∑
4101:∇
4014:∑
3936:…
3870:…
3848:≥
3746:∑
3659:…
3637:≤
3517:∗
3487:ν
3481:λ
3470:ν
3461:≥
3458:λ
3445:∗
3403:∗
3395:≤
3389:ν
3383:λ
3357:ν
3334:≥
3331:λ
3309:∗
3244:ν
3223:∑
3191:λ
3170:∑
3130:∈
3113:ν
3107:λ
3079:∈
3062:ν
3056:λ
3022:→
3007:×
2958:ν
2938:λ
2887:ν
2866:∑
2834:λ
2813:∑
2781:ν
2775:λ
2731:→
2716:×
2701:×
2644:⊂
2599:…
2585:∈
2532:…
2518:∈
2503:≤
2372:∗
2368:λ
2295:λ
2281:≥
2278:λ
2239:λ
2208:λ
2168:λ
2138:≥
2135:λ
2100:λ
2080:≥
2077:λ
2039:)→∞ when
1949:λ
1929:≥
1926:λ
1866:λ
1856:∑
1824:λ
1732:∑
1645:…
1631:∈
1616:≤
1357:∗
1349:−
1344:∗
1317:∗
1290:∗
1221:∗
1166:∈
1155:≤
1147:∗
1128:∗
1120:−
1113:∗
1105:∈
1100:∗
1048:~
998:∞
989:∪
981:→
975:×
940:~
914:∞
667:~
653:∈
492:~
409:^
374:^
327:∈
307:^
272:^
243:∞
234:∪
226:→
190:∗
147:∗
119:separated
5966:Zonotope
5937:Epigraph
5533:(1963).
5524:Articles
5492:(2006).
5416:(1986).
5247:(1963).
5097:(1993).
4927:(1986).
4726:(2006).
4618:(1993).
4416:See also
3979:maximize
3702:maximize
3557:minimize
3424:such as
3369:we have
3349:and any
2428:Given a
1797:, where
1545:problem:
1485:subspace
1446:solution
1428:are all
1424:and the
1397:epigraph
1261:supremum
451:and the
389:exists,
97:and the
34:theory,
6021:Duality
5923:Pseudo-
5897:Ursescu
5794:Pseudo-
5768:Concave
5747:Simplex
5727:Duality
5606:2348241
5567:0152360
5516:2199043
5436:0868279
5406:9048698
5398:1900016
5338:1888251
5311:1295240
5280:1261420
5207:2265882
5064:2028848
4990:0544669
4972:xvi+388
4947:0868279
4911:9048698
4903:1900016
4859:1888251
4826:1295240
4789:1261420
4756:2265882
4569:1921556
4427:Duality
4376:History
4372:holds.
3432:, i.e.
1528:optimal
1393:closure
1379:holds.
1235:is the
453:infimum
429:minimum
427:is the
50:or the
38:or the
36:duality
6004:, and
5975:Series
5892:Simons
5799:Quasi-
5789:Proper
5774:Closed
5604:
5565:
5559:168028
5557:
5514:
5504:
5478:
5459:
5434:
5424:
5404:
5396:
5386:
5356:
5336:
5326:
5309:
5299:
5278:
5268:
5233:
5205:
5195:
5162:
5143:
5124:
5105:
5062:
4988:
4978:
4945:
4935:
4909:
4901:
4891:
4857:
4847:
4824:
4814:
4787:
4777:
4754:
4744:
4701:
4676:
4651:
4626:
4590:
4567:
4557:
4553:–113.
4524:
4499:
4464:
2579:
2512:
2324:equals
1625:
1450:vector
1430:linear
1208:where
758:(i.e.
693:
558:where
67:. For
5832:Main
5555:JSTOR
5402:S2CID
5080:Books
5060:JSTOR
5029:(PDF)
5008:(PDF)
4907:S2CID
4458:(pdf)
4438:Notes
3420:If a
1984:Proof
1448:is a
955:to a
5952:Lens
5906:Sets
5756:Maps
5663:and
5502:ISBN
5476:ISBN
5457:ISBN
5422:ISBN
5384:ISBN
5354:ISBN
5324:ISBN
5297:ISBN
5266:ISBN
5231:ISBN
5193:ISBN
5160:ISBN
5141:ISBN
5122:ISBN
5103:ISBN
4976:ISBN
4933:ISBN
4889:ISBN
4845:ISBN
4812:ISBN
4775:ISBN
4742:ISBN
4699:ISBN
4674:ISBN
4649:ISBN
4624:ISBN
4588:ISBN
4555:ISBN
4522:ISBN
4497:ISBN
4475:2011
4462:ISBN
3915:and
2950:and
2405:and
2258:The
2187:The
1075:The
832:for
166:and
6006:(Hw
5594:doi
5547:doi
5376:doi
5185:doi
5052:doi
4881:doi
4734:doi
4551:106
4404:In
3716:inf
3496:inf
3454:max
3123:inf
3072:inf
2974:or
2346:min
2274:max
2218:min
2147:min
2131:max
2073:max
2063:min
2016:If
1922:max
1514:In
1247:sup
1159:inf
1091:sup
686:inf
646:inf
320:inf
117:of
30:In
6077::
5998:(H
5996:,
5992:,
5988:,
5925:)
5921:,
5801:)
5779:K-
5602:MR
5600:.
5590:32
5588:.
5582:.
5563:MR
5561:.
5553:.
5543:11
5541:.
5537:.
5512:MR
5510:.
5432:MR
5430:.
5400:.
5394:MR
5392:.
5382:.
5334:MR
5332:.
5307:MR
5305:.
5276:MR
5274:.
5221:;
5203:MR
5201:.
5191:.
5093:;
5089:;
5058:.
5048:13
5046:.
5016:^
4986:MR
4984:.
4974:.
4943:MR
4941:.
4905:.
4899:MR
4897:.
4887:.
4855:MR
4853:.
4822:MR
4820:.
4785:MR
4783:.
4752:MR
4750:.
4740:.
4722:;
4614:;
4610:;
4565:MR
4563:.
4483:^
3531:.
3417:.
2413:.
2214::=
2045:→∞
1986::
1910:,
1795:λu
1506:.
1072:.
81:.
60:.
6012:)
6010:)
6008:x
6002:)
6000:x
5984:(
5959:/
5917:(
5772:(
5653:e
5646:t
5639:v
5619:.
5596::
5549::
5518:.
5484:.
5465:.
5408:.
5378::
5362:.
5340:.
5313:.
5282:.
5239:.
5209:.
5187::
5168:.
5149:.
5130:.
5111:.
5066:.
5054::
5031:.
5010:.
4992:.
4913:.
4883::
4861:.
4828:.
4791:.
4758:.
4736::
4707:.
4682:.
4657:.
4632:.
4596:.
4571:.
4530:.
4505:.
4477:.
4356:)
4353:x
4350:(
4345:j
4341:g
4331:j
4327:u
4321:m
4316:1
4313:=
4310:j
4302:+
4299:)
4296:x
4293:(
4290:f
4267:)
4264:x
4261:,
4258:u
4255:(
4224:m
4221:,
4215:,
4212:1
4209:=
4206:i
4202:,
4199:0
4191:i
4187:u
4176:0
4173:=
4170:)
4167:x
4164:(
4159:j
4155:g
4145:j
4141:u
4135:m
4130:1
4127:=
4124:j
4116:+
4113:)
4110:x
4107:(
4104:f
4094:o
4091:t
4087:t
4084:c
4081:e
4078:j
4075:b
4072:u
4069:s
4060:)
4057:x
4054:(
4049:j
4045:g
4039:j
4035:u
4029:m
4024:1
4021:=
4018:j
4010:+
4007:)
4004:x
4001:(
3998:f
3989:u
3986:,
3983:x
3947:m
3943:g
3939:,
3933:,
3928:1
3924:g
3903:f
3876:m
3873:,
3867:,
3864:1
3861:=
3858:i
3854:,
3851:0
3843:i
3839:u
3831:o
3828:t
3824:t
3821:c
3818:e
3815:j
3812:b
3809:u
3806:s
3796:)
3792:)
3789:x
3786:(
3781:j
3777:g
3771:j
3767:u
3761:m
3756:1
3753:=
3750:j
3742:+
3739:)
3736:x
3733:(
3730:f
3726:(
3720:x
3705:u
3665:m
3662:,
3656:,
3653:1
3650:=
3647:i
3643:,
3640:0
3634:)
3631:x
3628:(
3623:i
3619:g
3611:o
3608:t
3604:t
3601:c
3598:e
3595:j
3592:b
3589:u
3586:s
3577:)
3574:x
3571:(
3568:f
3560:x
3513:p
3509:=
3504:0
3500:f
3493:=
3490:)
3484:,
3478:(
3475:g
3467:,
3464:0
3450:=
3441:d
3399:p
3392:)
3386:,
3380:(
3377:g
3337:0
3305:p
3294:g
3277:.
3273:}
3269:)
3266:x
3263:(
3258:i
3254:h
3248:i
3238:p
3233:1
3230:=
3227:i
3219:+
3216:)
3213:x
3210:(
3205:i
3201:f
3195:i
3185:m
3180:1
3177:=
3174:i
3166:+
3163:)
3160:x
3157:(
3152:0
3148:f
3143:{
3135:D
3127:x
3119:=
3116:)
3110:,
3104:,
3101:x
3098:(
3093:L
3084:D
3076:x
3068:=
3065:)
3059:,
3053:(
3050:g
3026:R
3017:p
3012:R
3002:m
2997:R
2992::
2989:g
2915:.
2912:)
2909:x
2906:(
2901:i
2897:h
2891:i
2881:p
2876:1
2873:=
2870:i
2862:+
2859:)
2856:x
2853:(
2848:i
2844:f
2838:i
2828:m
2823:1
2820:=
2817:i
2809:+
2806:)
2803:x
2800:(
2795:0
2791:f
2787:=
2784:)
2778:,
2772:,
2769:x
2766:(
2761:L
2735:R
2726:p
2721:R
2711:m
2706:R
2696:n
2691:R
2686::
2681:L
2654:n
2649:R
2639:D
2609:}
2605:p
2602:,
2596:,
2593:1
2589:{
2582:i
2576:,
2573:0
2570:=
2567:)
2564:x
2561:(
2556:i
2552:h
2542:}
2538:m
2535:,
2529:,
2526:1
2522:{
2515:i
2509:,
2506:0
2500:)
2497:x
2494:(
2489:i
2485:f
2470:)
2467:x
2464:(
2459:0
2455:f
2399:λ
2395:λ
2389:.
2377:)
2364:,
2361:x
2358:(
2355:L
2350:x
2332:λ
2310:.
2298:)
2292:(
2289:g
2284:0
2254:.
2242:)
2236:,
2233:x
2230:(
2227:L
2222:x
2211:)
2205:(
2202:g
2183:.
2171:)
2165:,
2162:x
2159:(
2156:L
2151:x
2141:0
2115:.
2103:)
2097:,
2094:x
2091:(
2088:L
2083:0
2067:x
2047:.
2043:i
2041:λ
2037:λ
2033:i
2029:x
2027:(
2024:i
2022:f
2018:x
2011:λ
2007:λ
2005:,
2003:x
1999:x
1997:(
1994:i
1992:f
1979:.
1967:)
1964:x
1961:(
1958:J
1955:=
1952:)
1946:,
1943:x
1940:(
1937:L
1932:0
1908:x
1891:)
1888:x
1885:(
1880:i
1876:f
1870:i
1860:i
1852:+
1849:)
1846:x
1843:(
1838:0
1834:f
1830:=
1827:)
1821:,
1818:x
1815:(
1812:L
1799:λ
1791:x
1789:(
1787:J
1766:]
1763:)
1760:x
1757:(
1752:i
1748:f
1744:[
1741:I
1736:i
1728:+
1725:)
1722:x
1719:(
1714:0
1710:f
1706:=
1703:)
1700:x
1697:(
1694:J
1681:x
1679:(
1677:J
1655:}
1651:m
1648:,
1642:,
1639:1
1635:{
1628:i
1622:,
1619:0
1613:)
1610:x
1607:(
1602:i
1598:f
1583:)
1580:x
1577:(
1572:0
1568:f
1473:m
1469:n
1465:m
1461:m
1454:n
1442:n
1438:m
1434:n
1353:d
1340:p
1313:p
1286:d
1217:F
1192:,
1189:)
1186:0
1183:,
1180:x
1177:(
1174:F
1169:X
1163:x
1152:)
1143:y
1139:,
1136:0
1133:(
1124:F
1109:Y
1096:y
1060:)
1057:x
1054:(
1045:f
1039:=
1036:)
1033:0
1030:,
1027:x
1024:(
1021:F
1001:}
995:+
992:{
985:R
978:Y
972:X
969::
966:F
937:f
911:=
908:)
905:x
902:(
896:s
893:t
890:n
887:i
884:a
881:r
878:t
875:s
872:n
869:o
866:c
861:I
840:x
820:0
817:=
814:)
811:x
808:(
802:s
799:t
796:n
793:i
790:a
787:r
784:t
781:s
778:n
775:o
772:c
767:I
742:)
739:x
736:(
733:f
727:d
724:e
721:n
718:i
715:a
712:r
709:t
706:s
703:n
700:o
697:c
690:x
682:=
679:)
676:x
673:(
664:f
656:X
650:x
625:X
602:s
599:t
596:n
593:i
590:a
587:r
584:t
581:s
578:n
575:o
572:c
567:I
543:s
540:t
537:n
534:i
531:a
528:r
525:t
522:s
519:n
516:o
513:c
508:I
504:+
501:f
498:=
489:f
466:f
439:f
415:)
406:x
400:(
397:f
371:x
347:.
344:)
341:x
338:(
335:f
330:X
324:x
316:=
313:)
304:x
298:(
295:f
269:x
246:}
240:+
237:{
230:R
223:X
220::
217:f
196:)
186:Y
182:,
179:Y
175:(
153:)
143:X
139:,
136:X
132:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.