|
|
| Line 1: |
Line 1: |
| − | Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101701.png" /> be a complete finite-dimensional [[Riemannian manifold|Riemannian manifold]], let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101702.png" /> be a convex [[Objective function|objective function]] and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101703.png" /> be a totally convex subset described by a system of inequalities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101704.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101705.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101706.png" /> are concave functions (cf. [[Concave function|Concave function]]). The solution of the [[Convex programming|convex programming]] problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101707.png" /> is completely characterized by a saddle-point theorem initially stated on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101708.png" /> [[#References|[a2]]] by H.W. Kuhn and A.W. Tucker.
| + | #REDIRECT [[Karush-Kuhn-Tucker conditions]] |
| − | | |
| − | Suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k1101709.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017010.png" /> are of class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017011.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017012.png" />. Introduce the Lagrange function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017015.png" />. A point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017016.png" /> is the optimal solution of the convex programming problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017017.png" /> if and only if there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017018.png" /> such that the so-called Kuhn–Tucker conditions hold:
| |
| − | | |
| − | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017019.png" /></td> </tr></table>
| |
| − | | |
| − | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k110/k110170/k11017020.png" /></td> </tr></table>
| |
| − | | |
| − | These equations provide a criterion for testing whether a solution which has been found by other methods is in fact an optimal solution.
| |
| − | | |
| − | The Kuhn–Tucker theorem has been generalized in various directions:
| |
| − | | |
| − | to necessary or sufficient conditions, or both types, for an extremum of a function subject to equality or inequality constraints [[#References|[a1]]];
| |
| − | | |
| − | to changing the geometrical structure of the underlying manifold [[#References|[a1]]], [[#References|[a3]]].
| |
| − | | |
| − | ====References====
| |
| − | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> K.J. Arrow, L. Hurwicz, H. Uzawa, "Studies in linear and nonlinear programming" , Stanford Univ. Press (1958)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> H.W. Kuhn, A.W. Tucker, "Nonlinear programming" , ''Proc. Second Berkeley Symp. Math. Stat. Probab.'' , California Univ. Press (1951) pp. 481–492</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> C. Udrişte, "Convex functions and optimization methods on Riemannian manifolds" , Kluwer Acad. Publ. (1994)</TD></TR></table>
| |
Latest revision as of 11:42, 2 May 2016
How to Cite This Entry:
Kuhn-Tucker conditions. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kuhn-Tucker_conditions&oldid=22679
This article was adapted from an original article by C. UdriÅŸte (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098.
See original article