Anar al contingut

Condicions de Karush-Kuhn-Tucker

De L'Enciclopèdia, la wikipedia en valencià

Les condicions de Karush-Kuhn-Tucker (també conegudes com les condicions KKT o Kuhn-Tucker) són requeriments necessaris i suficients per a que la solució d'un problema de programació matemàtica siga òptima. És una generalisació del método dels multiplicadors de Lagrange.

Problema general d'optimisació

Considerem el següent problema general:

min f(x)
sujeto a  
 gi(x)≤0 ,  i=1,…,m
 hj(x)=0 ,  j=1,…,l

a on f(x) és la funció objectiu a minimisar, gi(x) són les restriccions de desigualtat i hj(x) són les restriccions d'igualtat, en m i l el número de restriccions de desigualtat i igualtat, respectivament.

Les condicions necessàries per a problemes en restriccions de desigualtat varen ser publicades per primera volta en la tesis de màster de W. Karush,[1] encara que varen ser renombradas despuix d'un artícul en una conferència d'Harold W. Kuhn i Albert W. Tucker.[2]

Condicions necessàries de primer orde

Supongam que la funció objectiu, per eixemple, a minimisar, és f:ℝn→ℝ i les funcions de restricció són gi:ℝn→ℝ i hj:ℝn→ℝ. Llavors, supongam que són contínuament diferenciables en el punt x*. Si x* és un mínim local, llavors existixen constants λ≥0, μi≥0 (i=1,…,m) i νj (j=1,...,l) no totes nules tals que:

λ+∑i=1mμi+∑j=1l|νj|>0,
λ∇f(x*)+∑i=1mμi∇gi(x*)+∑j=1lνj∇hj(x*)=0,
μigi(x*)=0para todoi=1,…,m.

Referències

  1. ↑ W. Karush(1939).«Minima of Functions of Several Variables with Inequalities as Side Constraints».Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois.
  2. ↑ H. W. Kuhn,Tucker, A. W., Proceedings of 2nd Berkeley Symposium, Nonlinear programming, University of Califòrnia Press, 1951, Berkeley
Bibliografia
  • Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
  • R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, pp. 473-485 (2005).

Vore també


Referències