Nelineární programování
 
Marie Tomšová 
Ústav matematiky, Fakulta elektrotechniky a komunikačních technologií, 
Vysoké učení technické v Brně  
e-mail: tomsova@feec.vutbr.cz 

Abstrakt 

V navazujícím magisterském studiu na Fakultě elektrotechniky a komunikačních technologií VUT v Brně se v předmětu MPSO (Magisterské studium, Pravděpodobnost, Statistika, Operační výzkum) nebudou učit jen vybrané statistické metody, ale i elementy operační analýzy. Příspěvek je věnován jedné její části – nelineárnímu programování.

1.	Úvod 

Jak plyne z názvu, jde o případ, kdy jsou omezení nebo účelová funkce (nebo obojí) nelineární.
Praktický problém, vedoucí na nelineární programování:
Výnos zemědělské plodiny je závislý v prvé řadě na množství srážek (včetně závlah) a na množství dodaných živin. Závislosti nejsou lineární. Na příklad s rostoucím množstvím srážek výnos nejdříve roste, pak však klesá (na příklad obilí polehne, sníží se kvalita zrna díky plísním apod.). Podobně při přehnojení umělými hnojivy přestává úměrně růst výnos.
Pokud jde o vlastní účelovou funkci, není samozřejmě k dispozici žádný exaktní vzorec. Je třeba vycházet jednak z odborných studií, jednak z dat zjištěných mnohaletým pozorováním pro danou oblast, z bonity a vododržnosti půdy atd. Je přitom třeba se omezit na nejvýše kvadratické závislosti, neboť jen pro tento případ je k dispozici rozumná početní metoda. V našem případě bude kvadratický vztah jistě stačit a může se k němu dospět na příklad aproximací reálných dat parabolou pomocí metody nejmenších čtverců. 

2.	Matematické pojmy
Extrémy. Stacionární body.
Značení: symbolem  (apod.) budeme značit sloupcový vektor,  k němu transponovaný vektor řádkový: 
Definice 1: Funkce f(x,y) má v bodě [x0,y0] (lokální) minimum, existuje-li takové okolí tohoto  bodu, že pro všechny jeho body [x,y]  platí  .
Jestliže platí taková podmínka pro (nějakou) oblast M (to znamená: existuje takový bod [x0,y0]M, že pro všechny jeho body [x,y]M  platí    ), říkáme, že funkce f nabývá v bodě   [x0,y0]  absolutního minima na oblasti M.
Podobně se definuje maximum.
Ostré extrémy: místo neostrých nerovností ostré.
Volný extrém:  lokální extrém, který není vázán dalšími podmínkami (zejména se přitom uvažuje celý definiční obor funkce). Může jich být víc – např. sin(x) má nekonečně mnoho maxim v bodech  /2+2k, k=0,1,2, …

Konvexní (a konkávní) množiny a funkce:
Lze-li každé dva body A,B dané množiny M spojit úsečkou ležící v M, potom nazýváme takovou množinu konvexní.  Libovolný bod  X  úsečky AB lze vyjádřit na příklad takovouto konvexní lineární kombinací      X=A+(1-)B,  0,1.
Příklad:                     

	Konvexní bodová množina		Nekonvexní

Definice 2: Funkce f se nazývá konvexní na oblasti M, platí-li pro libovolné dva body A,B této oblasti:     f(A+(1-)B)f(A)+(1-)f(B).

     f(A)+(1-)f(B)
	f(A)				f(B)	
		   f(..)				
  
	       A	  A+(1-)B		    B	

Příklad konvexní funkce 1 proměnné; funkce je nad tečnou (pod sečnou)
Konkávní funkce: opačná nerovnost (funkce 1 proměnné je pod tečnou)

Stacionární body, vztah k extrému:
Uvažme spojitě diferencovatelnou funkci f. Z matematické analýzy víme, že nutnou podmínkou pro volný extrém je nulová derivace (u funkcí více proměnných nulovost všech parciálních derivací). Bod, ve kterém jsou všechny (první) parciální derivace nulové se nazývá stacionární. Platí tedy
Lemma 1:  Buď f spojitě diferencovatelná funkce (jedné nebo více proměnných). Nabývá-li v bodě A volného extrému, je A stacionárním bodem, tj. všechny první parciální derivace jsou zde nulové.
Příklad: f(x)=(x-3)2 , f’=2(x-3); v bodě x=3 je skutečně minimum.
      g(x)= x3 ; g’=3x2 ; v bodě x=0 však není extrém, ale inflexe.
Gradient
Představme si jednoparametrický systém funkcí (nadploch)  , kde  c  je volitelná konstanta . Pro jisté konkrétní  c  jde o geometrické místo bodů, v nichž funkce f  nabývá stejné hodnoty c . 
Typickým příkladem jsou vrstevnice – čáry (v základně, řekněme rovině dané hladinou moře), nad nimiž má terén stejnou výšku. U potenciálových polí (např. elektrických) se užívá zase pojem hladina (ekvipotenciální hladina). Všechny tyto pojmy znamenají matematicky totéž a nebudeme mezi nimi rozlišovat. 
Gradient (gradientní vektor) funkce v bodě    je vektor parciálních derivací podle 
jednotlivých proměnných : ,
 		   	        .    			
Tento vektor je kolmý na nadplochu  v bodě   a  má směr maximálního růstu funkční hodnoty v soustavě nadploch .
Situaci nejlépe ozřejmí příklad. 
Uvažme   z = f(x1,x2) = (x1-2)2 + (x2-2)2
gradient  je vektor   ( 2(x1-2), 2(x2-2) ).  Tento vektor je kolmý na vlnoplochu 
    v libovolném bodě roviny. Má tedy směr poloměru příslušné vlnoplochy a směřuje ven z kružnice. Na příklad v bodě [2,1] je gradient (0,-2), 
v bodě [0,0] je gradient (-4,-4), v bodě [3,3] je to (2,2) a ve středu [2,2] je gradient (0,0). Poslední fakt je připomenutím známé a již citované věty z matematické analýzy: má-li diferencovatelná funkce v jistém bodě extrém, pak jsou zde všechny parciální derivace nulové (jde o tzv. stacionární bod).	
Závěrem: gradient funkce f v daném bodě je vektor parciálních derivací funkce f v tomto bodě. Je zde kolmý na vrstevnici (hladinu) a má směr největšího růstu funkce f .

3.	Hledání stacionárního bodu

Omezíme se na diferencovatelné funkce jedné a dvou proměnných. Případ více proměnných si čtenář snadno rozváží zobecněním úvah pro dvě proměnné.

Funkce jedné proměnné

Hledáme bod  x, ve kterém je . Označíme-li si, je třeba řešit obecnou rovnici .
Z řady metod, které nabízí numerická matematika, je patrně nejlepší metoda Newtonova. Postupuje se takto:  zvolíme výchozí iteraci  x0. V bodě x0 vedeme k funkci  tečnu (tj. aproximujeme  tečnou). Průsečík této tečny s osou x je další iterací kořene; označme x1. Postup opakujeme, až se po sobě jdoucí iterace téměř neliší.
Prakticky: 
Rovnice tečny v bodě x0  je       
Její průsečík s osou x 		
Dosadíme z druhé rovnice do první: 
a odtud				      
Newtonova metoda je metoda iterační: další přiblížení řešení se počítá z předchozího podle stále stejného předpisu. Tedy:
1.	Zvolíme nultou iteraci  x0.
2.	Vypočteme další iteraci z předešlé podle vzorce  .
3.	Jestliže  končíme, a za hledaný kořen prohlásíme ; když ne, opakujeme bod 2.

Místo geometrického odvození můžeme tentýž výsledek dostat z Taylorovy řady. Je totiž
 
Omezíme se na lineární část rozvoje, tedy  a položíme jej roven 0 (tj. spočteme průsečík této lineární části s osou x), což samozřejmě vede ke stejnému výsledku jako výše.

Funkce dvou a více proměnných

Hledejme stacionární bod funkce  , tj. bod, ve kterém je 
Označme pro přehlednost  
Máme tedy řešit soustavu (nelineárních) rovnic            

Vyjdeme opět z počáteční iterace . Taylorovy řady se středem  pro   f, g  jsou

( podobně pro g(x,y) )
Označme přírůstky  , omezme se na lineární části Taylorových řad a položme je rovny nule:

Stručně označeno:   ,   vše v bodě   
Jde o soustavu dvou lineárních rovnic pro přírůstky  h, k. Vyřešíme a dostaneme další iteraci

a celý postup opakujeme, až se po sobě jdoucí iterace liší o méně, než zvolená přesnost.
(Geometricky: nahradíme obě funkce tečnými rovinami. Ty protnou rovinu xy ve dvou přímkách a tyto přímky se protínají v další iteraci.)

Pro 3 a více proměnných je úvaha analogická.	
Newtonova metoda je pro obecnou soustavu nelineárních rovnic s diferencovatelnými funkcemi nejpoužívanější. Její slabinou je, že někdy začne iterační proces oscilovat mezi dvěma body blízko kořene a kořen se pak v případě potřeby musí upřesnit ručně (na příklad níže popsanou gradientní metodou).   	

Gradientní metoda

Využívá toho, že vektor gradientu udává směr největšího růstu funkce. Řekněme, že hledáme lokální minimum funkce dvou proměnných  F(x,y). Vyjdeme tedy opět z nějakého výchozího bodu . Vypočteme v něm gradient a postupujeme v opačném směru (hledáme minimum,  při hledání maxima postupujeme ve směru gradientu) o jistý násobek gradientu. Právě volba tohoto tzv. kroku je slabinou metody. Empiricky zjištěný vhodný krok je někde mezi 0,05 až 0,25 gradientu. Na počítači je pomoc snadná: zvolíme několik různých kroků a zvolíme ten, pro který poklesne gradient (jeho absolutní hodnota) co nejvíce. Postup s novou iterací opakujeme, až se dostaneme do bodu, kde je gradient (až na zvolenou přesnost) nulový. 
Gradientní metodu si lze snadno představit na výstupu na horu. Gradient udává směr nejprudšího stoupání k vrcholu, minus gradient naopak nejprudší klesání (= směr spádnice). Nejkratší cesta na vrchol sleduje stále směr gradientu (pokud je kopec hladká plocha, šli bychom po hladké křivce). Gradientní metodou bychom tuto křivku aproximovali takto: postoupíme vždy kousek přímo, tam změníme směr podle aktuálního gradientu a zase postoupíme kousek přímo atd. Místo hladké čáry postupu k vrcholu bychom tedy postupovali po lomené čáře, jejíž průmět do roviny by se skládal z úseček.  

4.	Obecná úloha NLP (nelineárního programování):

Nalézt globální extrém účelové funkce  v oblasti, určené soustavou omezení  .
Některé třídy úloh se označují speciálními názvy:
•	kvadratické programování: kvadratická účelová funkce, lineární omezení
•	konvexní programování: účelová funkce i omezení jsou konvexní funkce
•	separabilní programování: bez smíšených členů ( na př. pro f:   )
•	lomené programování: účelová funkce a omezení jsou podíly lineárních funkcí.

Příklad 2 :         při omezeních
a)	0  x1 4 ,  0  x2  1 
b)	0  x1 1 ,  0  x2  1
c)	0  x1 4,5 ,  0  x2  3,5
	
Čtenář snadno nahlédne, že účelová funkce má absolutní minimum 0 v bodě [2,2]. Toto minimum není vázáno žádnými omezujícími podmínkami; jde tedy o minimum volné. 
Vázaný extrém je extrém v oblasti přípustných řešení M, jež je určena omezeními. V našich případech jde o body:
a)	bod (2,1)  - leží na hranici M
b)	bod (1,1)  - jde o vrchol oblasti M
c)	bod (2,2)  - vnitřní bod M

Již z této poměrně jednoduché úlohy kvadratického programování je vidět, že metodika řešení bude podstatně jiná (a daleko složitější) než u úloh lineárního programování.

5.	Hledání vázaného extrému (=řešení úlohy NLP) pro konvexní problém:

Úloha: minimalizujte      
za podmínek             0  ( i=1,2,..m )
			      	
kde účelová funkce f i veškerá omezení jsou konvexní, spojitě diferencovatelné funkce.
Uveďme základní fakta o konvexních funkcích a konvexních množinách:
Průnik konvexních množin je konvexní množina.
Věta 1: Buď  množina bodů v En, splňující omezení   ,  0 , i=1,2,..,m. Jsou-li všechny funkce konvexní, je  konvexní množina (není-li prázdná).
Důkaz: Buďte  dva body z . Je třeba dokázat, že jejich konvexní kombinace  patří do , to jest, že splňuje daná omezení:
a)	 evidentně
b)	, neboť 
Věta 2: Funkce konvexní na konvexní množině  zde má nejvýše jedno lokální minimum. Existuje-li, pak je minimem globálním a dosahuje se na konvexní množině.
Důkaz: Předpokládejme, že minimum nastává v bodě . Buď . Pro velmi malé  leží  bod  v  -okolí (tj. ve vzdálenosti menší než ) bodu  a funkční hodnota v tomto bodě je větší nebo rovna hodnotě v minimu, tj.  
Tím je dokázána existence jediné minimální hodnoty (pokud existuje). Zbývá dokázat, že když je této minimální hodnoty dosaženo ve dvou různých bodech, je jí dosaženo i v libovolném bodu úsečky, těmito body určené, tj. v konvexní kombinaci těchto bodů: 
Nechť funkce nabývá minimální hodnoty z0 ve dvou bodech . Je
 , což jsme dokazovali
Příklady – vesměs funkce jedné proměnné:
a)	=(0, 10) (otevřený interval) ,  . Funkce nemá  na  minimum (ani maximum)
b)	=<0, 10> (uzavřený interval) , . Minimum=0 v bodě [0], maximum=20 v [10]
c)	=(0, 10) (nebo =[0, 10) apod.)  , . Minimum (maximum)=7, v lib. bodě 
d)	=(0, 10),  . Minimum=0  v bodě [3]
Intuitivně je zřejmé, a dá se to i dokázat, že pokud je konvexní oblast  uzavřená, bude minimum (konvexní funkce) existovat. To je také případ úlohy konvexního programování, jak jsme ji formulovali. Všechna omezení jsou totiž neostré nerovnosti, oblast přípustných řešení  je tudíž uzavřená. 
Pro důkaz klíčové věty celé teorie konvexního programování budeme potřebovat ještě dvě pomocná tvrzení:
Věta 3: Funkce , definovaná a diferencovatelná na otevřené konvexní množině   je zde konvexní právě když   pro všechna .
Důkaz:  : Buď  konvexní kombinace bodů 
Je  ( je konvexní) a   Utvořme konvexní kombinaci levých a také pravých stran, tzn. první nerovnost násobme , druhou  (1-) a sečtěme:
Po úpravě: , q.e.d. : Konvexnost f znamená   . Uspořádejme členy: . Podělme obě strany   (0):
          	(*)
Derivace ve směru  funkce  f v bodě   je 
 .   Je tedy

Tento výraz ovšem dostaneme, když rozšíříme pravou stranu (*) zlomkem  a provedeme limitní přechod. Tvrzení tedy platí.
Význam: Věta říká, že přírůstek konvexní funkce v libovolném směru je větší, než přírůstek tečny (tečné roviny, nadroviny) v tomto směru, že tedy konvexní funkce je nad tečnou (nad tečnou nadrovinou) v libovolném směru.
	
Následující věta rovněž zobecňuje fakt známý z diferenciálního počtu jedné proměnné a znamená toto: konvexní funkce nabývá v jistém bodě minima, jestliže ve všech směrech od tohoto bodu roste.
Věta 4: Konvexní, spojitě diferencovatelná funkce na konvexní množině  nabývá globálního minima v bodě  právě když   pro všechna  .
Důkaz: : Nechť f nabývá minima v . Je-li bod  vnitřní, je zde  - jasné. Jestliže je to bod krajní (leží na hranici), uvážíme, že platí , tudíž  a stejným obratem jako ve druhé části důkazu předchozí věty dostaneme .
: Podle předchozí věty je    a dále  0 (předpoklad), tedy  , což jsme dokazovali.

Věty 1 a 2 ukazují, že úloha konvexního programování má smysl, že účelová funkce bude nabývat jediného minima, a to buď v jediném bodě, nebo v nekonečné konvexní množině (podobně jak je tomu u lineárního programování).  
Základní myšlenka řešení: úloha se převede na hledání speciálního volného extrému,
tzv. sedlového bodu Lagrangeovy funkce. Ta je definována takto:
								(N1)
li (často se značí i)  jsou tzv. Lagrangeovy multiplikátory (Lagrangeovy neurčité koeficienty).  (J. L. Lagrange (1736-1813), fenomenální matematik a fyzik, nadaný výjimečnou představivostí. Zabýval se problematikou vázaných extrémů ve variačním počtu, pohybem těles v silových polích aj. Zformuloval pohybové rovnice (tzv. Lagrangeovy rovnice), na nichž se dá vybudovat prakticky celá klasická mechanika. Na jeho práce navázal W. Hamilton, který ve svých 20 letech (1825) objevil princip minimálního účinku (Hamiltonův princip), patrně nejhlubší a nejzávažnější fyzikální zákon vůbec, jímž se řídí veškerý volný i vázaný pohyb těles a elektrických a magnetických nábojů při působení sil, jakož i pohyb světelného paprsku.)

Úloha o sedlovém bodě: Pro Lagrangeovu funkci  najděte nezáporné vektory  tak, že    . 		(N2)
Hledá se tedy maximum vzhledem k  a minimum vzhledem k    (oba výsledné vektory jsou přitom ve všech složkách nezáporné).

Věta 5:  Sedlový bod  Lagrangeovy  funkce je řešením úlohy konvexního programování.
Důkaz: Rozepišme (N2):
 . Z levé nerovnosti
     plyne, že  pro všechna i. Pokud by některé, řekněme  , stačí volit  li=0 pro ik,  lk dostatečně velké, abychom vlevo dostali velké číslo a nerovnost byla porušena. 
Další důležitý důsledek:  . Skutečně, kdyby bylo  (kladné být nemůže), položme  a z  (*) máme , což je spor s předpokladem. Uvážíme-li tuto nulovou hodnotu ve středním součtu (*), dostaneme
. Suma vpravo je nekladná ( l0i  0 , ), je tedy
  a  je řešením úlohy konvexního programování.
Věta 6: Je-li  řešením úlohy konvexního programování, pak existuje vektor  tak, že  je sedlový bod Lagrangeovy funkce.
Důkaz je zdlouhavý a vyžaduje značný aparát. Zájemce odkazuji na specializovanou literaturu.
Langange vyvinul metodu multiplikátorů pro variační počet. Tam je vysoce efektivní, zatímco v NLP je hledání sedlového bodu obtížné. Východiskem je následující věta:
Věta 7: (Kuhn-Tuckerova)
Vektor je řešením úlohy konvexního programování když a jen když existuje vektor  takový, že je splněno následujících šest (Kuhn-Tuckerových) podmínek:
(KT1)         pro všechna j

(KT2)       

(KT3)       		(standardní podmínka nezápornosti řešení)

(KT4)            (omezení)

(KT5)       

(KT6)       

Příklad: Ilustrujme si tuto ne právě jednoduchou větu na praktickém příkladu. Mějme hledat minimum účelové funkce  na 
množině , dané nerovnostmi
                           
Řešení: Funkce f nabývá absolutního minima v bodě  [5 , 5]. Vrstevnice jsou soustředné kružnice se středem v tomto bodě. Hledaný vázaný extrém (řešení naší úlohy) je zřejmě bod, ve kterém se dotýká vrstevnice s nejmenší funkční hodnotou oblasti . Je jím zřejmě bod     [2 , 2].  Ověřme si teď Kuhn-Tuckerovy podmínky:
   
Parciální derivace Lagrangeovy funkce dle   označme v1, v2:
	
Jak víme z důkazu V5, musí být v optimu   (také KT5), odtud  . Podle  (KT2) je také , a protože  x1 0, x2 0,  bude v1=v2=0. Odtud l2=10-2x2=10-4=6
Uvedené hodnoty ( ) vyhovují Kuhn-Tuckerovým podmínkám. 

Důkaz: 
Úvodní část: Buď   řešením úlohy konvexního programování. Extrém může nastat (tj. může ležet) buď uvnitř nebo na hranici . Pokud leží na hranici, je aspoň jedna omezující podmínka splněna jako rovnost. 
V důkazu věty 5 je zdůrazněn tento výsledek: všechny součiny   jsou v optimu nulové. Z toho zejména plyne: leží-li řešení (optimum) uvnitř , budou všechny multiplikátory nulové (neboť všechny podmínky jsou splněny jako ostré nerovnosti, tj.   0  ). Leží-li na hranici, budou některé podmínky splněny jako nulové (pro ty nadplochy, na kterých optimum leží), ostatní jako ostré nerovnosti. Nenulové pak mohou být jen ty multiplikátory, které přísluší nulovým podmínkám.

Důkaz implikace  (předpokládejme, že  je řešením úlohy, dokážeme (KT1) až (KT6)):
(KT1): a) Leží-li  uvnitř , pak, poněvadž minimalizuje , je 
            b) Leží-li   na hranici, uspořádejme podmínky tak, že  0 pro i=1,2,..k,  pro i=k+1,..,m. Je  pro i=1,2,..k  a 
             c) Jestliže neleží na hranici, dané funkcemi  gi  (tudíž ) , avšak platí-li pro určité j, že   (jde rovněž o hranici, avšak danou implicitní podmínkou nezápornosti  ), můžeme zavést hraniční funkci   a rozšířenou Lagrangeovu funkci . Poněvadž ale , je  . Dál: 
          
, a poněvadž  lm+1  0,  je  
              d) Nastanou-li obě situace b) a c) současně (což je samozřejmě možné), bude   . První a třetí člen však dává  F , takže

(KT2) je důsledkem: 
(KT3), (KT4) jsou podmínky úlohy
(KT5) je víckrát zmiňovaný důsledek z důkazu V5 (věty 5)
(KT6) byla rovněž ukázána v důkazu V5

Opačná implikace 
Ať platí Kuhn-Tuckerovy podmínky. Podle V3 je 

Třetí člen je nula dle (KT3), druhý je nezáporný (jde o kladný násobek derivace ve směru, a ta je v minimu kladná, resp. nezáporná),  je tedy 
Druhou nerovnost dokážeme takto:  je lineární v , tedy konvexní. Proto 

(rovnost platí proto, že funkce je lineární, její přírůstek v libovolném směru je roven přírůstku tečné nadroviny v tomto směru)
Třetí sčítanec je nula dle (KT5), druhý je záporný dle (KT4), je tedy 
Obě nerovnosti dohromady znamenají, že jde o sedlový bod, tedy řešení úlohy.

Jedním z nejméně sympatických úkazů v matematice je dosti častý rozpor mezi jednoduchostí a elegancí myšlenky a jejím pracným a málo přehledným důkazem. Přesný důkaz ovšem je třeba podat a tak se čtenář často setkává se zdlouhavými a nesrozumitelnými konstrukcemi, jejichž prvotní význam mu zůstává utajen. Důkaz (KT1) je typickým reprezentantem tohoto jevu a tak se teď pokusme zapomenout na jeho nesympatický formalismus a pokusme se najít Ariadninu nit základná myšlenky.
Je-li hledané minimum konvexní funkce uvnitř , jde o stacionární bod, v němž jsou derivace účelové funkce nulové. Ten bychom uměli najít i bez Kuhn-Tuckerovy věty, proto si tohoto případu nebudeme všímat.
Je-li hledané minimum na hranici , uplatní se v plné míře Lagrangeova idea hledání vázaného extrému metodou neurčitých koeficientů. Pokusme se tuto ideu vyložit na následujícím problému:  

Má se najít minimum funkce 
na oblasti , vyznačené na obrázku, tedy pro
  . 
Oblast je ohraničena třemi přímkami: 

Vrstevnice jsou kružnice se středem [2,2], minimum je v hraničním bodě [0,2] na hraniční přímce .
Úlohu lze řešit takto: 
1.	Najdeme volné minimum. Vidíme, že neleží v , proto pokračujeme dál.
2.	Najdeme minimum f  na každé hraniční přímce zvlášť (řešení právě takové úlohy podal Lagrange). Z těchto minim najdeme nejmenší.
V bodu 2 bychom tedy řešili tři úlohy. Náhodou bychom dostali přípustné řešení, neboť bod 
[0,2], kde je nejmenší z těchto hodnot, leží v . Kdyby však šlo o účelovou funkci , nevedla by tato metoda k cíli, neboť „nejmenší z nejmenších“ hodnot nastává sice v bodě přímky , ale mimo  ( pro záporné x).  Je tedy zřejmě třeba uvažovat všechny hraniční úsečky současně. Příslušná Lagrangeova funkce by byla
 . Říkejme jí třeba úplná (Lagrangeova funkce). Řešením úlohy konvexního programování je sedlový bod právě této funkce, to jest bod, ve kterém jsou všechny derivace (podle x,y,l1,l2,l3) rovny nule.
Z lineárního programování je známo, že je možné podmínky nezápornosti z modelu vytěsnit, to jest zařídit, aby se v početním modelu přímo nevyskytovaly. Samozřejmě se však při výpočtu respektují. Kuhn s Tuckerem se pokusili, a to se zdarem, o podobné. Vyloučili z Lagrangeovy funkce podmínky nezápornosti. Tím si značně zkomplikovali odvození, tedy důkaz svých podmínek, ovšem výsledkem bylo zjednodušení početního modelu. Ten se v kvadratickém případě nápadně podobá modelu z lineárního programování (viz příští odstavec), a také se podobně řeší.
Pro náš praktický příklad to znamená, že se místo 
pracuje s redukovanou funkcí 

Cenou za toto zjednodušení pak je fakt, že derivace této funkce mohou být v optimu i kladné (nejen rovny nule).

Formulace Kuhn-Tuckerových podmínek, určená pro početní model:

Pro přesné a zároveň srozumitelné znění věty užijeme této notace:
-	označme  vj parciální derivaci Lagrangeovy funkce dle proměnné  xj ,  v0j pak hodnotu této  derivace v bodu , tedy     ,      
-	označme  di  záporně vzatou derivaci Lagrangeovy funkce dle  li,              
           ,  d0i pak hodnotu  di v bodu  , tedy     
           ,  
 Kuhn-Tuckerova věta: Vektor   je řešením úlohy konvexního programování když a jen když existuje takový vektor  , že je splněno následujících šest (Kuhn-Tuckerových) podmínek:
(KT1)         pro všechna j  (j=1..n)
(KT2)         
(KT3)       	(standardní podmínka nezápornosti řešení)
(KT4)        	 (omezení)
(KT5)       
(KT6) 	      	

Podmínky 1,3,4,6 jsou podmínky nezápornosti – všechny proměnné jsou v optimu nezáporné
Podmínky 2 a 5 jsou vylučovací: vždy aspoň jedna ze stejnolehlých  párových proměnných   , respektive    je (v optimu) rovna nule
Podmínky jsou nutné a postačující. Jakmile se nám podaří najít bod, ve kterém jsou splněny, máme řešení. Jako v lineárním případě nemusí být řešení jediné. Na příklad v problému
	 
je řešením celá úsečka  [0,2][2,0].	

Ukázky cvičení:

Symboly apod. značit sloupcové vektory. Řádkové vektory budeme ve shodě s faktem, že jde o transponované vektory sloupcové, značit  

1. Buď A čtvercová matice řádu n,  (sloupcový) vektor délky n. Které součiny jsou definovány a jakou mají dimenzi?   .
2. Spočtěte .

3. Na základě posledního součinu z předchozího příkladu se pokuste zapsat postupně výrazy
  
 jako součin . Je matice A v druhém případě dána jednoznačně? Ne-li, najděte aspoň dvě různé. Najděte příslušnou symetrickou matici a pokuste se ukázat, že je jediná. 

4.Zapište maticově  funkci   , tj. najděte symetrickou matici C a  řádkový vektor , že  .

5. Změní se pravá strana rovnosti z předchozího příkladu, zaměníme-li součin  součinem
    ? Ověřte.

6. Když to tak hezky jde u druhého součinu, zamyslete se nad prvním. Šlo by jej nahradit součinem
        ?

Sylvestrovo kriterium:
7. Zjistěte, zda kvadratické formy   jsou kladně definitní resp. semidefinitní  přímo z definice.

8. Totéž Sylvestrovým kriteriem
9. Kvadratická forma ve třech proměnných x1,x2,x3 má matici . Formu vyjádřete analyticky a zjistěte, zda je pozitivně definitní.

Hledání volného extrému kvadratické funkce.
10. Funkce  . Pokuste se určit, o jakou plochu se jedná. Jaké čáry jsou její vrstevnice 
     . 			
(Vrstevnice jsou kružnice se středem v počátku. Pro x=0 bude z=y2 , tedy parabola. Analogicky pro y=0.  Plocha je tedy rotační paraboloid).
Určete gradient naší funkce v bodech (2,3), (1,1) apod. Jaký má směr?
(gradient je vektor parciálních derivací, zde (2x,2y). Pro bod (1,1) dostaneme (2,2). Tento vektor je   
kolmý na vrstevnici v daném bodě a má směr maximálního růstu funkce z).

11. Pozměňte funkci z předešlého příkladu na  . O jakou plochu půjde teď?
    ( Opět paraboloid, nikoli však rotační. Vrstevnice jsou elipsy).

12. Najděte volné maximum funkce .
      Určete gradient této funkce v bodech (-1,-1), (2,0), (3,5). 
13. Gradientní metoda hledání volného extrému spočívá v postupném přibližování se k extrému pomocí gradientu. Hledejme na příklad extrém funkce  . Spočteme gradient
      . Hledáme stacionární bod, tj. bod, v němž je gradient nulový (tzn. obě parciální derivace jsou nulové). Z názoru usoudíme, že hledaný extrém je minimum. Zvolíme nějak, co možná rozumně, výchozí bod – na příklad (0,0) – a spočteme v něm gradient (při této volbě to je (-1,-2)). Postoupíme o jistý krok v opačném směru (ve směru největšího poklesu funkce) se snahou zmenšovat gradient až k nule. Volba vhodného kroku je největší slabinou metody.
Pokusme se o krok 0,2 . Postoupíme tedy k bodu (0,0)+0,2(1,2)=(0.2,0.4). Zde je gradient
 (0.4-e-0.4,0.8-2e-0.8)=(-0.27032,-0.0986). Gradient se zmenšil, krok jsme zvolili vhodně. Podobně postupujeme dál. 
Jak je zřejmé, jde o metodu postupných aproximací (postupného přibližování)
14. Tutéž úlohu jako v př. 13 řešte Newtonovou metodou.
 Řešíme soustavu nelineárních rovnic 	
Soustava , zde , tedy 
Za nultou iteraci volíme počátek. Vyjde  . První iterace:   Gradient v tomto bodě je   
Po dosazení první iterace do soustavy vyjde  a druhá iterace vyjde
 s gradientem     ,
což je po druhém kroku velmi dobrý mezivýsledek.
(Studenti mají k dispozici interpret výrazů, který umí i formálně derivovat. S ním je naprogramování Newtonovy metody velmi jednoduché).

Literatura: 

[1]	CHURCHMAN C. W. , ACKOFF R.L., ARNOFF E.L. Úvod do operačného výskumu. ALFA,  
            Bratislava 1968.
 [2] 	LAŠČIAK A. a kol. Dynamické modely. ALFA, Bratislava 1985.
 [3] 	NOVÁK M. Probability theory in combined form of study at FEEC BUT, Mezinárodní 
            konference EPI Kunovice 2006.
 [4]      TYC O. Operační analýza. MZLU Brno 2002.
 [5]      ZAPLETAL J. Operační analýza. SKRIPTORIUM VOŠ. Kunovice 1995.  
 [6]      DUDORKIN N., Operační analýzy, FEL  ČVUT, Praha, 1997.