Namespaces
Variants
Actions

Difference between revisions of "Kuhn-Tucker conditions"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Merge with Karush-Kuhn-Tucker conditions.)
 
(One intermediate revision by one other user not shown)
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=12541
This article was adapted from an original article by C. UdriÅŸte (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article