Optimització contínua. Problemes

en w ::, a - len ,_ e <(  en w U) w :::, a - z o ,w 1UJ w - u z , u <C PROBLEMES OPTIMI ZACIÓ , CONTINUA Narcís abona F. Javier Heredia Departament d'Estadística i lnvestigació ,---------- - Operativa �-----. l:.LCT oc UNIVER,SITAT POLITÉCNICA DE CATALUNYA r UNIVERSITAT POUTECNICA DE CATALUNYA Biblioteca 11111\�l m llll\ 11�1111111111\ 111� 111111111111111 1400457904 Optimització Contínua PROBLEMES N arcís N abona F. Javier Heredia Departament d 'Estadística i Investigació Operativa Secció d 'Informa.ti ca UPC Q2/99-00 Títol: Optimització Contínua -Problemes Autor: Narcís Nabona i F. Javier Heredia Diposit Legal: B-8965-2000 Impres per : Ahlens, S. L. Sor Eulalia d 'Anzizu, sin 08034 Barcelona ÍNDEX Llista de problemes: Problema c-1 : pcomin2/Condicions de mínim ..................................... 1 Problema c-2 : pargo3/criteris d'Armijo-Goldstein ................................. 1 Problema c-3 : pgrad2/metode del gradient ........................................ 1 Problema c-4 : pluen2/metode de Newton, variant de Luenberger .................. 1 Problema c-5 : pden2/Métode de Newton, variant de Dennis-Schnabel .............. 1 Problerna c-6 : pmqrl2/mínims quadrats lineals .................................... 2 Problema c-7 : pkutu3 / condicions de K uhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Problema c-8 : pcl7 /Constriccions Lineals .......................................... 2 Problema c-9 � pcl8/Constriccions Lineals .......................................... 3 Problerna c-10 : pmusa3/metode de Murtagh-Saunders ............................. 3 Col-lecció de problemes resolts: Problema c-1 : pespal/esparsitat de matrius simetriques ........................... 5 Problema c-2 : pcominl/condicions d'optim ........................................ 9 Problema c-3 : pargol/criteris d'Armijo-Goldstein ................................ 12 Proble11.1a c-4 : pargo2/criteris d'Armijo-Goldstein ................................ 14 Problema c-5 : pgraq/metode del gradient amb funcions quadratiques . . . . . . . . . . . . . 17 Problema c-6 : pgradl/metode del gradient ....................................... 18 Problema c-7 : pgrcol/gradient conjugat .......................................... 20 Problema c-8 : pluenl/metode de Newton, variant de Luenberger ................. 22 Problema c-9 : pgimul/metode de Newton, variant de Gill-Murray ................ 25 Problema c-10 : pmqrll/mínims quadrats lineals .................................. 30 Problema c-11 : pkutul/condicions de Kuhn-Tucker .............................. 33 1 . Índex ( continuació) Proble111a c-12 : pkutu2/condicions de Kuhn-Tucker .............................. 35 Proble111a c-13 : pconl9/metodes de constr. lineals ................................ 38 Proble111a c-14 : pnwfsl/met. Newton amb fites simples ........................... 40 Problem.a c-15 : pmusal/metode de Murtagh-Saunders ........................... 44 Problem.a c-16 : pmusa2/metode de Murtagh-Saunders ........................... 47 Problen1a c-17 : pgrgl/Gradient Redu1t Generalitzat .............................. 50 NN-FJH/EIO/UPC/2000 PROBLEMA c-1. Llista de problemes/ OC I/ LJM-FME 1 Llista de problemes Donada la funció f(x) = Xi+ x� + x1x2 -6x1, trobeu (si existeix) el mínim de la funció subjecte a x1 2 2, x2 2 O. (Empreu la propietat de l'optim x* V f(x*)D 2 O per a tota direcció factible D respecte al domini de definí ció). PROBLEMA c-2. Per a la funció objectiu f(x) = xr + X1X2 + 2xi/x2 2.1.- Verífiqueu si la direcció D = [O -1 ]' és de descens per a la funció f(x) a partir del punt inicial X0 = [ 1 1 ]'. Si no ho fos, trobeu-ne una que ho sigui. 2.2.- Partint del punt X0 donat, efectueu exploració lineal per ajust quadratic en la direcció de descens que tingueu. Efectueu a continuació exploració lineal per ajust cúbic del ti pus y = a>. 3 + b). 2 + e/\ + el emprant els valors de la funció a X0 i al punt trobat a l'ajust quadratic i el valor de la derivada a X0• 2.3.- Efectueu per als punts trobats en les exploracions lineals per ajust quadratic Xq i ajust cúbic Xc, una comprovació d'acceptabilitat que no sigui la simple verificació ele que J(Xq) i J(Xc) valen menys que J(Xo)- PROBLEMA c-3. Donada la funció J( x1, x2) = 50xf + 3x1 X3 + 4x� + l5x� -6x1 + 8x2 -60x3 es demarra que: 3.1.- apliqueu una passa completa del metode del gradient per a minimitzar aquesta funció a partir de X0 = [O -1 O]'. 3.2.- comproveu, a través de la funció d'error e(X) = (X -X*)'Q(X -X*)/2, que la convergencia local de l'algorisme entre X0 i X1 (que haureu trobat) esta dins del límit teoric. PROBLEMA c-4. Efectueu una passa del rnetode de Newton en la variant de Luenberger aplicat sobre la funció J(x) = x¡ + x� + x1x2x5 a partir del punt Xo = [O 1/2 1]' pden2/!viétode de Newton, variant de Dennis-Schnabel NN-F JH/EIO /UPC/2000 PROBLEMA c-5. La funció: Llista de problemes/ OC 1/ LJM-FME 2 f(x) =xf + x� + (ll/2)x� + x! + (5/2)x� + x1x� + 6x1x3 + 3x1xs+ +2x2x4 + X�X5 + 6X3X5 + X4X5 té l'hessia indefinit al punt X0 = [1/2, O, -1, 1/2, O]'. Trobeu la direcció de minimització a partir de X0 pel metode de Dennis-Schnabel, sabent que la triangularització de Gill-Murray de l'hessia a X0 afegeix a l'hessia la matriu: 0.272727 o E= 0.022727 o 18.7 PROBLEMA c-6. Donat el següent sistema lineal i incompatible en X E IR-3: determineu per factorització QR el punt X* que soluciona els mínims quadrats lineals del sistema i la solució x+ de norma mínima del mateix problema. PROBLEMA c-7. Donat el següent problema de minimització: opt. subj.a f(X) = xf X3 + 2x� + 3x� + 2x1x2 + 4x1X3 + 2x2x3 -28x1 -lüx2 -33x3 1 2 11 2xl + X2 + X3 = 2 7 .1.- Determineu el caracter de maxim, mínim o punt de sella d 'un punt X que satisfa les condicions de 1 er ordre i tal que x1 = l. 7.2.- Si la constricció íos de desigualtat: subj. a : X seria també un mínim? pcl7 /Constriccions Lineals NN-F JH/EIO /UPC/2000 PROBLEMA c-8. Llista de problemes/ OC I/ LIM-FME 3 La matriu Q obtinguda per factorització LQ corresponent a les constriccions lineals :actives : -1 2-;2)(��) -2 ox- - 3 o-1 podr1a ser la ( 0.316 0.54 0.602 0.491 ) Q= -0.316 -0.54 0.767 -0.142 0.632 Ú.098 0.192 -0.744 -0.632 0.638 0.11 -0.425 1(de '.la qual la darrera columna és la matriu Z). ·netermineu un punt factible respecte a les constriccions per un metode de factoritza ·-cions ortogonals. Considerant el punt factible obtingut i la funció objectiu: ,efectueu una estimació de primer ordre dels multiplicadors de Lagrange de les constriccions íi feu un comentari sobre la seva bondat a la vista dels resultats obtinguts. PROBLEMA c-9. Donada la funció a minimi tzar ·subjecta a les constriccions 1 1 2 o ,efectueu una passa del metode de Newton per la tecnica de l'espai nul partint d'un punt i-1nicial determinat per aquestes mateixes tecniques. pmusa3/metode de 1\1urtagh-Saunders NN-F JH/EIO /UPC/2000 Col·leccíó de problemes resolts/ OC I/ LJM-FME 10 lO]X. X* és tal que QX* = B. Resolent el 1 -2/7 [2 1 7/2 que es traba fara de X¡ 2:: O, x2 2:: O, X3 2:: O. 1 -2/7 MÍNIM DE f(X) AL DOMINI DEFINIT PER x1 2:: O, x2 2:: O, x3 2:: O. El mínim al domini x1 2:: O, x2 2:: O, x3 2:: O haura de satisfer V(X*)D 2:: OVD factible, i estara sobre la frontera. S'hara dones de satisfer: [ 2x1 + x2 4x2 + x1 -x3 -5 6x3 -x, -10] [ ;: J :O, O Segons a quina faceta ens trobem de la frontera definida per x1 2:: O, x2 2:: O, X3 2:: O, es poden donar els casos següents: a) X1 = O, d2 i d3 qualsevol i d1 2:: O: X¡ pcominl/ condicions d 'optim Xz 2:: Ü 4x2 -X3 -5 = Ü(perque d1 2:: O) (perque d2 pot ser molt negatiu) (perque d2 pot ser molt negatiu) NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC I/ LlM-FME 11 d'on el sistema X2 = 40/23 2 0 X3 = 45/23 2 0 on X* és un mínima x1 2 O, x2 2 O, x3 2 O. b) x2 = O, d1 i d3 qualsevol i d2 > O: X¡ e) X3 = O, d1 i d2 qualsevol i d3 2 O: l\¡ ⇒ Jé• = [40�23] 45/23 x2 = O d1 i d3 qualssevol, i d2 2 O X1 = 0 (perque d1 pot ser molt negatiu) -X3 -5 2 o (perque d2 2 o)⇒ lx3 � -5 IMPOSSIBLEj 2x1 + X2 = o (perque d1 pot ser molt negatiu). Lla vors, si x1 2 O => x2 :S O i viceversa=> JIMPOSSIBLEJ L'únic mínim és dones jx• = [ O 40/23 45/23 ]',. pcominl/condicions d'optim NN-F JH/EIO/UPC/2000 PROBLEMA c-3. Col·lecció de problemes resolts/ OC I/ LIM-FME 12 Donada la funció de la figura adjunta, la qual expressa la variació del valor de f(Xk + >..D) en funció de>.., sent Xk,DEIR,n i f(X): lR,n-+R, copieu la figura i indiqueu les zones de l'eix de les abscisses on es satisfa la 1!!:. condició d'Armijo-Goldstein i, de forma diferenciada, les zones on es satisfa la 2!!:. condició d'Armijo-Goldstein. Indiqueu els valors numerics que utilitzeu per definir els parametres que caracteritzen les esmentades condicions. SOLUCIÓ 1 er CRITERI D'ARMIJO-GOLDSTEIN El 1 er criteri d'acceptabilitat d'una passa )... és que: . - --- - �'vf(1\)D 'vf(1\)D . - - --- 1-ª i 2l cond. O < a < 1 generalment a=0,1 ··········f(�) f(X¡}+11.aVJ(X¡}D - - - - _ 1.!! cond. satistefa � A -- '-E:------' � � 2f! cond. satisfeta pargol/criteris d'Armijo-Goldstein NN-F JH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC 1/ LIM-FME 13 22.!!. CRITERI D'ARMIJO-GOLDSTEIN Cal que: a < (3 < l generalment (3=0,5 La figura mostra les zones on es satisfa el 1 er i el 2°n cri teri d 'Armijo-Goldstein d'acceptabilitat de la passa. En el dibuix s'han utilitzat (aproximadament) els valors a=0,1 i /3=0,5 pargol/criteris d'Armijo-Goldstein NN-F JH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 14 PROBLEMA c-4. Donada la funció objeciu f(x) = Xi + x1x2 + 2�1, el punt iterat Xo = [ 1 -2 ]' i la direcció de cerca D = [ 2 l ] 1 : 4.1.- Feu exploració lineal a partir de X0 al llarg de D amb ajust quadratic emprant el valor de la derivada de la funció objectiu a X0. Comproveu si el punt obtingut satisfa la P· condició d' Armijo-Goldstein. 4.2.- Feu exploració lineal a partir de X0 al llarg de D amb ajust cúbic emprant el valor de la derivada de la funció objectiu a X0. Comproveu si el punt obtingut satisfa la 2ª condició d'Armijo-Goldstein. En cas de no fer l'ajust cúbic, comproveu aquesta condició sobre el punt associat a >. = 1/8. SOLUCIÓ CALCULS PRELIMIN ARS Vf(Xo)D = [ -1 f(Xo) = -2 3 = -- <O=} D de descens 2 AJUST QUADRATIC : Es pren el punt Xo + D com a punt addicional: f(Xo + D) = O Ajust quadratic : q(>-) = a>.2 + b>. + e >-=l q(O) =e= f(Xo) = -2 =} [e= -21 q(,\)' = 2a,\ +b ; q(O)' = b = v' J(Xo)D = -� ⇒ lb --�I q(l) =a+ b +e= f(Xo + D) = O =} a+ b +e= O pargo2/criteris d'Armijo-Goldstein 3 a---2=0 2 □ NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 15 b -3/2 � , . Calcul de >..q : q(>..q)' =2a>..q + b =O ; >..q = -2ª = -- 7-⇒ � m1n1m dones a> O. COMPROVACIÓ DE LA 1 ª COND. D'ARMIJO-GOLDSTEIN A Xo + >..qD: Condició AGl : f(Xo + >..D) � f(Xo) + a.V J(Xo)D>.. ; . a E (O, l]. S'acostuma a prendre un escalar a molt petit. Usarem a= 0.05. Xo + A,D = [ �2] + 134 [ �] = [ _\] J(Xo + >..qD) = -2.1102< 3 3 < J(Xo) + a'v'f(Xo)D>..q = -2 + 0.05( -2)14= -2.0161 AJUST CÚBIC ⇒IEs satisfa AG1J Es prenen els punts X0 +Di X0 + frD coma punts addicionals Xo+D = [ !1] ; J(Xo+D) = O; Xo+�D = [ �2] +� rn = { _y3] ; J(Xo+�D) = -1.5156 Ajust cúbic: u(>..) = a>..3 + b>..2 +e>..+ d >..=O : u(0) = d = J(Xo) = -2 ⇒ Id= -21 u(>..)'= 3a>..2 + 2b), + e u(O)'=c=v'f(Xo)D=-� =<> le -�1 2 2 7 >..=l :u(l)=a+b+c+d=J(Xo+D)=O ⇒ a+b=2 5 5 125 25 5 5 >.. = g : u(9) = a729 + b81 + c9-2 = f(Xo + 9D) = -1.5156 a= -1.7307 (*) ⇒ b = 5.2307 Calcul de >..e : 7 } a+ b= -2 (*) 125ª 25b=l.3176 729 + 81 u(>..u)' = 3a>..� + 2b>..u +e= O -5.1921>..� + 10.4614Au -1.5 = O Au =-10.4614 + J109.4408 -31.1526 = 0.1553 ⇒ J>..u = 0.15531 -10.3842 . . pargo2/ cri teris d 'Armijo-Goldstein NN-F JH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 16 COMPROVACIÓ DE LA 2A COND.D'ARMIJO-GOLDSTEIN A Xo + >-uD: Condició AG2 : V f(Xo + >..D)D � /3'v J(Xo)D ; /3 E [a, ½lUsarem /3 = 0.3. Xo + AuD= [ �2] +0.1553 [�] = [ �/t�:6] 'v f(Xo + >-uD)D = [ -0.3074 0.5403] [ �] = -0.07448 'vf(Xo + >-uD)D =-0.07448 > /3'vf(Xo)D = 0.3(-;) = -0.45 ⇒ j,- E_s_s_at-is_fa_A_G�2J COMPROVACIÓ DE LA 2A COND. D'ARMIJO-GOLDSTEIN A X0 + gD: Xo+>..uD= [ �2] +l [�] = [-�--��5] 'v f(Xo + AuD)D = [ -0.4416 0.5388] [ �] = -0.3444 'v f(Xo + � D)D = -0.3444 > /3'v f(Xo )D = 0.3( -�) = -0.45 ⇒ 1 Es satisfa AG21 pargo2/criteris d'Armijo-Goldstein NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 17 PROBLEMA c-5. Obtenció d'un punt des d'on el metode del gradient arriba en una sola passa al mínim d'una funció objectiu quadratica. !x, [7 {2 111/2 -�/2 -��2] X -[21/2 2O -1/2 11/2 -1 47 -58 41/2)X -1/2 -2 -1 15/2 Valors propis de Q : Ai = {9, 6, 4, 3} SOLUCIÓ [ 1/2 Prenem >.4 = 3 i determinem U4 : Q ->.41 = � -1/2 1 5/2 -1/2 -2 o -1/2 5/2 -1 -1/2] -2 -1 9/2 Per a resoldre el sistema homogeni ( Q ->.4I)U4 = O prenem U44 = 1 i considerem les tres primeres equacions [ 1/�2 1 º l 5/2 -1/2 -1/2 5/2 triangularitzant i resolent s'obté: 1 O l[U41] [1/2] [1/2 1/2 -1/2 U42 = 1 j Ü -1/2 5/2 U43 1 Ü QualsevolpuntX0 = X*+aU4 satisfalacondiciódemanada. PodemprendreXo = X*+U4 pgraq/metode del gradient amb funcions quadratiques NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC 1/ LJM-FME 18 PROBLEMA c-6. Feu una passa de minimització de la funció quadratica: (X)= !x, [ 19/3 -8-/2/3] X -[ 19 -8-/2]' X q 2 -8-/2/3 11/3 des del punt Xo=[ O 1 ]' obtenint el nou punt X1. Comproveu que la funció d'error E(X)=½(X -X*)'Q(X -X*) (sent X* el mínim de q(X)) als punts Xo i X1 satisfa la taxa de convergencia local propia de les funcions quadratiques, i comproveu que el gradient a X1 és ortogonal a la passa (X1 -Xo). SOLUCIÓ PASSA PEL METODE DEL GRADIENT A PARTIR DE X0 Donada una funció quadratica: q(X) =½X'QX -B'X amb X,BEffin, Q=Q'Effinxn, l'expressió de l'algorisme del gradient és: _ _ [ 19/3 -8-/2/3] [º] [ 19 ]-¡-ªv;+e17] Go -QXo -B --8-/2/3 11/3 1 --8� -11 +;4 v'2 Go' Go =742, 94082 Go' QGo = 6680, 2367 ao =O, 1112147 X [º] [ 8�+57 ]=[2,5324972 ] 1 = 1 -o, 111214 7 11+;4✓2-0, 6660379 FUNCIÓ D'ERROR A X0 I A X1 Per tal de calcular E(X)=½(X -X*)'Q(X -X*) necessitem coneixér X* el qual és solució de QX* = B. Resolent el sistema: [ 19/3 -8-/2/3] * [19 ] -8-/2/3 11/3 X = -8./2 obtenim X* = [ �] Fent els calculs pera Xo i peral punt trobat X1 trobem que E(Xo)=½(Xo -X*)'Q(Xo - X*)=41,647042 i que é(Xi)=½(X1 -X*)'Q(X1 -X*)=0,33111455 . pgradl/metode del gradient NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 19 FITA SUPERIOR A LA TAXA DE CONVERGENCIA Sabem que: E(Xk+1) < (A -ª) 2 E(Xk) -A+a on A ia són el més gran i el més petit valor propi de Q. Hem de calcular els valors propis de Q i ho farem resolent el polinomi característic det( Q -✓U) = O ( de grau 2 en aquest cas ). COMPROVACIÓ DE LA TAXA DE CONVERGENCIA LOCAL Efecti vament: E(X1) = 0,33111455 =O 00795< (A-a)2 = (9-1)2 =O 64 E(Xo) 41,647042 ' -A+a 9+1 ' COMPROVACIÓ DE L'ORTOGONALITAT DE G1 I (X1 -Xo) G Q v· B [ 19/3 -8�/3] [ 2, 5324972 ] [ 19 ] [-0, 4490648] 1 =.'\.¡ -= -8�/3 11/3 -0, 6660379 --8� = -0, 6790754 G '(X ·v ) [ ] [ 2, 5324972 ] O l d. l . 1 1 -."l.. 0 = -0,4490648 -0,6790754 _1,6660379 = ta com mateona pgradl/metode del gradient NN-F JH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LlM-FME 26 -6x2 o 'vf(X)' =[ 3xf -3x� + 4x1X4] -6X1X2 + X3X4 + 6 X2X4 -6x1 X4 X4 o 2xf + X2X3 X3 X2 Vf(Xo)' =m d'on m = 2, jaque emm = e22 = 24, i el sistema a resoldre és: cornprovació: l 6 -6 O 4 ] l 1] -6 -6 O -2 1 1 o o lO O O 1 0 = -12 < o 4 -2 1 O O Nota: també -DcN és una direcció de corbatura negativa a partir de X0 on 'vf(Xo)1=O. EXPLORACIÓ LINEAL PER AJUST CÚBIC AMB u(>.)= a/\3 + b/\2 +e/\+ el. u(>.)= a>.3 + b:>..2 +e>.+ d , u'(>.)= 3a>.2 + 2b>. + e , u"(>.)= 6a/\ + 2b a) En la direcció DcN: >. o : { u(O) =f(Xo) = Id -41 u'(O) = 'v f(Xo)DcN = le= ol Xo +DcN = [ �2 l +rn [ �2 l*f(Xo +DcN) = -4 'vf(Xo+DcN)=[O -18 O 4] 'vf(Xo+DcN)DcN=-18 u(l)=a+b+c+d=f(Xo+DcN)=-4 } a+b=-8 } [a=-21 u'(l)=3a+2b+c='vf(X0+DcN)DcN=-18 3a+2b=-18 ⇒ b=-6 pgimul/metode de Newton, variant de Gill-Jvlurray NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LIM-FME 27 Tenim dones u(A) = -2A3 -6A2 +4. Igualant a zero u'(Au) = 3aA; + 2bAu + e = O arribem a Au(-6.,\u -12) = O que té dos solucions: Au = O i Au = -2. Examinant amb u"(✓\) =6aA + 2b el caracter de maxim o mínim d'aquests punts veiem que: /\u = O dóna u"(O) = -12 < O i correspon a un maxim. Au = -2 dóna u"(-2)= 24 -12 =12 > O i correspon a un mínhn. La passa a aplicar en la direcció DcN és dones I.Au = -2,. Fenomens atípics observats: i) La passa Au = -2 és negativa, malgrat que no ens ha d'extranyar perque tant és de descens la direcció DcN com -DcN a partir de X0 amb V J(Xo) = O (vegeu figura 1). ii) Anomenant X1 = Xo + AuDcN tenim que: { f(X1) = -4 = = f(Xo + DcN) = -4 ( vegeu figura 1 ). L'ajust sembla indicar que és millar explorar cap a valors positius de /\ > 1, que no pas quedar-se a ✓\u = -2, jaque a.,\ = 1 la derivada és negativa (-18), i la funció baixa de valor augmentant A. iii) Si haguessim aplicat el criteri de considerar coma mínim de l'ajust cúbic la solució amb radicand positiu de u'(.,\) = -6>.2 -12>. = O, >. = 12 ± if212 )2 també hauriem obtingut que ). = -2 correspon a un nínim, i que A = O correspon a un maxim, pero cal anar amb compte de no canviar els signes a u'(A), ( quan e= O sembla natural considerar 6P + 12>. = O), perque aixo provocaría que aquest criteri no fos va.lid. -2 1 -4 Figura 1 b) En la direcció ÍJcN= -DcN= [-1 -1 O O]': pgimul/metode de Newton, variant de Gill-Murray NN-F JH/EIO/UPC/2000 Col·leccíó de problemes resolts/ OC I/ LlM-FME 28 Igualment al cas a) seguim tenint que le= O, d = 41. ). 1: Xo+DcN= [ �2] + [�i]-[�2]⇒J(Xo+DcN)=O v'f(Xo+DcN)=[O 6 O O] v'f(Xo+DcN)ÍJcN=-6 u(l) = a+ b +e+ d = J(Xo + DcN) = O } a+ b = -4 } u'(l) = 3a + 2b +e= v' J(Xo + DcN )DcN = -6 3a + 2b = -6 Tenim dones u(-\) = -2,\3 -6-\2 + 4. Igualant a zero u'(>.u) = 6>.� -12>-u = O arribem a >-u(6>.u -12) =Oque té dos solucions: >-u = O i Au = 2. Examinant amb u"(>.) = 12>. -12 el caracter de maxim o mínim d'aquests punts veiem que: Au = O: dóna u"(O) = -12 < O i correspon a un maxim. Au = 2: dóna u"(2) = 24 -12 = 12 > O i correspon a un mínirn (vegeu figura 2). La pass a a aplicar en la direcció .De N és dones I A u - 21 , e qui valent a la pass a amb DcN-Aixo pero és un fenomen particular d'aquest probl ma, perque en general, partint de X0 amb v' f(Xo) = O, les passes en una direcció i en la contraria, s'assemblen pero poden no coincidir, ja que la variació de la funció objectiu en una direcció i en la contraria no son sempre iguals. Figura 2 AJUST CÚBIC EMPRANT LA DIRECCIÓ P = [7/3 1 O o]'. Igualment al cas a) anterior seguim tenint que I e = O , d = 4 J. pgimul/metode de Newton, variant de Gill-!VIurray NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 29 r 1 J r7/3J r10/3J Xo+P= �2 + � �2 ⇒J(Xo+P)=244/27 ,\ - 1: \J f(Xo + P) = [ 64/3 -34 O 164/9] '9 f(Xo + P)P = 142/9 u(l) =a+ b +e+ d = f(Xo + P) = 244/27 } a+ b = 136/27 } a= 12574 u'(l) = 3a + 2b +e= \J f(Xo + P)P = 142/9 3a + 2b = 142/9 => b = -j Tenim dones u(>.) = 1l74 >.3-§"A2 + 4. Igualant a zero u'(,\u) = 1fl>.� -jAu = O anib m a Au ( 1B1>-u - j) = O qu té dos solucions: Au = O i Au = fr. Examinant amb ·u"(✓\) = �,\ -! el carader d ma:>..-im o mínim d'aquests punts veiem que: >-u= O: dóna u"(O) =-!<O i correspon a un maxim. Au = -f7: dóna u"( f7) = j > O i que correspon a un mínim. Anomenant Xp = Xo + AuP tenim que: X = X \ p = l� 1 = 83/77 r 1 l r 7 /3 J [ 2/11 l P o+✓ u -2 + 77 O -2 34624 142 f(Xp) =5929 < f(Xo+P) = g oo o -4 Figura 3 0.1 pgimul/metode de Newton, variant de Gill-Murray NN-F JH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LIM-FME 30 PROBLEMA c-10. Donat el següent sistema lineal sobredeterminat i incompatible en X E IR?: determineu per factorització QR el punt X* que soluciona els mínims quadrats lineals del sistema. SOLUCIÓ PROCEDIMENT Donat un sistema lineal AX= B amb XEffin, AEffimxn i BEffim, sent m > n, el punt X* que minimitza IIAX -BII és el mateix que minimitza IIQ(AX -B)II sent QEffimxm una matriu ortogonal. Fent que Q sigui la matriu que efectua la factorització QR d'A tindrem que IIQ(AX -B)ll2 = IIQ1(AX -B)ll2 + IIQ2(AX -B)II2, sent Q1 Effinxm les n primeres files de Q, i Q2Effi(m-n)xm les n-m derreres files de Q. Donat que Q1A = R (REffinxn sobretriangular) i QzA = O (OEffi(m-n)xn tota de zeros), la solució del problema sera el punt X* solució del sistema RX* = Q1B, ja que aleshores IIQ1(AX* -B)ll2 + IIQ2(AX* -B)ll2 = IIRX* -Q1Bll2 + IIOX* -Q2Bll2 = IIQ2Bll2 és independent de X* i és el mínim de 11 AX - B 11. PRIMERA MATRIU DE HOUSEHOLDER H1 I PRODUCTE H1A Cal trobar una matriu de Householder H1 =]_ -w'\v vVi vV{ que factoritzi la primera l l columna A1 d'A. La norma IIA1II val 5, així el vector de Householder vVi val: W1 = H1 = :ll - 2 W1 W{ = W{vVi Fem ara el producte H1A: [� [ �4 r-[� l - o o 1 o o o 1 o o o 1 o �] [� 2 -- 20 ¡�:] o8 o o o16 o o pmqrll/mínims quadrats lineals �] [ �¾ o 1 o o _1 �] o 3 o NN-F JH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LIM-FME 31 SEGONA MATRIU DE HOUSEHOLDER H2 I PRODUCTE Q = H2H1 La segona matriu de Householder H2 ha de servir per factoritzar la segona columna de H1A deixant sense canviar el seu primer element. La norma de la part de la segona columna de H1A que exclou el primer element és 7. Així el vector de Householder vV2 és: 2 / H2 =]. - W2 W2 = vV�W2 Q = H,H1 = [� o 6 I 7 2 7 w, -[! ] [� - 3 2 [� o o �] 1 o2 o114 o o o º l 1 o 3 {i [ �t 7 1 2 o --:; 6 o 7 ]- [� _i 5 o 3 5 o [ il] o 1 -3 -2 �] o i2 l -3 9 6 -[-\; -8 35 24 35 [� o o ii l 6 3 I 7 2 7 --:; 2 6 7 7 o4 {i l 6 -[ 7 -35 3 _§_ 7 35 2 18 7 35 Particionant Q en Q1 ( dues primeres files de Q) i Qz ( dues derreres files), tenim que: 6 ?g 35 6 ?g 7 35 o _§_ 7 i] [ 14 15] -[ 5 �] O 2 o 6 7 �,� il [{�] [ -'�: l -lJ [ �4 �5]= 0 -/ l [ {� l [ = ¡'¡ l no cal fer-ho, dones ja ho diu la teoria 1 IIQ2BII= O, 5225 residual (moderat) pmqrll/mínims quadrats lineals NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LIM-FME 32 SOLUCIÓ DELS MÍNIMS QUADRATS RX* =Q1B [ 522 l X*= _:1�6 245 (Noti 's que si en comptes de B = [ ;�] haguessin tingut ii = [ ;�] la solució hauria estat X* = [ !1] amb Q/B = [ �] ja que el sistema AX = B és compatible) pmqrll/mín.ims quadrats lineals NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LIM-FME 33 PROBLEMA c-11. En la minimització: .22 2 mm X1 + X2 + X1 X3 subj. -x/ + xl + 4x3 = O 11.1.- determineu si el punt X=[-! O ¼ ]', el qual satisfá les condicions de 1� ordre, és un mínim. SOLUCIÓ EXPRESSIÓ DE LES CONDICIONS DE 1 er ORDRE ( obtenció del multipli cador de Lagrange de la constricció) Definim el Lagrangia: .C(X, >.) =x1 2 + x2 2 + 2x1x3 + >.(-x12 + x2 2 + 4x3) Derivant respecte a X i a >., V >..C(X, >.)' = -x12 + x2 2 + 4x3 = O es satisfa a X. EXPRESSIÓ DE L'HESSIA DEL LAGRANGIÁ. V\.C(X, >.) =V\J(X) + L Ai'v\hi(X) [� o �] [-? o V�y f(X) =2 ( constant) 9lh¡(X) = � 2 2 o o o o o �] ( constant) ~ 2 >. = - 3 v2 .c(x 3:) = X ' rn 2 2] [-2 � + � � 2 º] [ � �] o = o ]0 la qual és indefinida o o O 2 o PLA TANGENT I BASE Z DEL PLA TANGENT A X Els punts Y del pla tangent a X han de satisfer: V h(X)Y =Ü, V h(X)=[ -2x1 2x2 4] i V h (X) és [ i O 4 ], així: [ ½ O 4] [�:] = O "? y3 = - �y1 condició de pla langenl a X pkutul/condicions de Kuhn-Tucker NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 34 X E IR3 i només hi ha una constricció: calen dones dos vectors per definir una base al pla tangent. Prenen dos vectors ortonormals. Un pot ser Z1 =[ O 1 O]' ( el qual satisfa y3 = -¾Y1 ). L'altre, ortogonal a Z1, podria ser: [ 1 O -¾ ]' normalitzat, és a dir: Z2=[ Jrr O -.fi3 ]'. Una base al pla tangent a X és dones: -� l v'l3 PROJECCIÓ DE L'HESSIÁ. DEL LAGRANGIÁ. AL PLA TANGENT Calculem Z'Vi.C(.X, ',\)z: 1 2 ~ ~ [ Ü Z V x.C(X, >..)Z = _3_ 1 o o 10 3 o -*3 l [_1ª. Q = 13 2 Ü - v'l3 1�0 ] (indefinida) Sent l'hessia del Lagrangia projectat al pla tangent indefinit, podem assegurar que .X no és un mínim. pkutul/condicions de Kuhn-Tucker NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC 1/ LJM-FME 35 PROBLEMA c-12. Considereu el problema d'optimització: minf(x) = XiXJ + 2x� + 3x� + 2x1x2 + 4x1x3 + 2x2x3 -4x1 -7x2 + 3x3 subj. a h(x) = �Xi +x2 +x3 -4 � O amb un punt extrem X tal que x1 = -2. Calculeu la resta de components de X 1 determineu la seva condició de maxim, mínim o punt de sella. SOLUCIÓ Si X satisfa les condicions necessanes de primer ordre (i té x1 = -2) hem de determinar el valor del multiplicador de Lagrange µ de la constricció de desigualtat per a saber si és activa o no. CONDICIONS NECESSÁRIES DE PRIMER ORDRE El Lagrangia.C(X, µ) és .C(X,µ) = Xix3+2x�+3x5+2x1x2+4x1x3+2x2x3-4x1-7x2+3x3+µ (�xi+ x2 + X3 -4) éJ.C(X,µ) � =2x1x3 + 2x2 + 4x3 + µxi -4 = O UX¡ éJL X ¡,) ---'----'-=2x1 + 4x2 + 2x3 + µ -7 = O OX2 { 2x2 -2µ = 4 -+ x1 = -2 -+ 4i2 + 2i3 + µ = 11 2x2 + 6x3 + µ = 1 havent-se de complir que µ ( i xf + i2 + X3 -4) = O. DETERMINACIÓ DE LA CONDICIÓ D'ACTIVA DE LA CONSTRICCIÓ DE DESIGUALTAT, I OBTENCIÓ DE X I µ a)Suposem que la constricció no sigui activa: llavors ½xf + i2 + i3 - 4 =f O, el qual forc;a a que µ sigui zero i el sistema que queda és : 2i? = 4 => i2 = 2 } � 3 �O ÉS COMPATIBLE. així dones el punt 4,""":2 + 2:t3 = 11 => :Í:3 = 2 X (an�b i1 = -2) no pot tenir la constricció no activa 2x2 + 6x3 # 1 pkutu2/condicions de Kuhn-Tucker NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 42 GRADIENT I GRADIENT PROJECTAT QUAN B=B ~ ~ El gradient a X o és Go = QXo -B: 3 3 -2 1 1 8 3 7.!. -2 44 Go= 3 4 1 §_ 8 4 4 6 .!. 2 !. 9 2 -8 23 6I.. 133 4 16 .!. 3 4 1 o o 2 37 1 95 2 15 o 1 2 o -1 o o 11 16 o -1 El gradient projectat és simplement el gradient de les variables lliures X11: G011 [ O O O O]', el qual és zero, així dones, no es pot efectuar una passa respecte a les variables lliures. Cal dones veure si val la pena separar alguna variable fixa de la seva fita. TAXACIÓ DE LES VARIABLES FIXES I NOU CONJUNT X11 Els multiplicadors de Lagrange A¡x de les igulatats X¡x =F (sent F el vector ele les components de X o X que són fites actives) són A¡x=±Go11 (amb { +} si la varíe ble esta fixada a la fita inferior i {-}si esta fixada a la superior). Així tenim A01.,=[ 1 i� -1 ]'. Val la pena dones separar la variable fixa x7 de la seva fita inferior passant-la a variable lliure. Tindrem dones que el nou conjunt de variables lliures sera el conjunt anterior i x7: X11 ={x1 X3 X4 X5 x1}1iX ¡x={x2 x5}1 • HESSIA PROJECTAT I DIRECCIÓ QUAN B=B L'hessia projectat correspon a Q u. L'equació a resoldre és dones: Q11P11 = -Go11 3 3 o o 3 -i 6 o o -2 4 3 P11 = o ::::} P11 =o 4 637 o o 15 1 2 2 15 PASSA I ACTUALITZACIÓ DE X QUAN B=B La direcció, donat que hi ha un sol component no zero, pot ser expressada com: P = [ O O O O O O 1 ]', la maxima passa permissible a la marca x1 la qual val O amb valor maxim 2 donant a-=2. Cal ara veure si la passa optima a* és més llarga o no que a. *-G�P l 2 _ ª =P1QP = 15 = 15 < a 2 2 Ú'Q =15 pnwfsl/met. Newton amb fites simples NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC 1/ LJM-FME 43 X1 = Xo + aoP = El gradient a X1 és 01 =[ O -1 O O i A1,., >Q). 1 2 2 7 ¡ 1 ¡ o 1 o o 1 2 o 2 o 7 2 ¡ +15o 1 -;¡ o o 181 240 o 1 1 O O]' i X1 és un optim (jaque G111 =.Q pnwfsl/met. Newton amb fües simples NN-F JH/EIO/UPC/2000 PROBLEMA c-15. Col·lecció de problemes resolts/ OC I/ LJM-FME 44 Donada la minimització: determineu el gradient projectat pel procediment de Murtagh-Saunders a partir del punt factible Xk = [2 O 1 3 5 1 5 2]', reordenant, si cal, les variables i comproveu que la direcció de menys el gradient projectat a partir de X k és una direcció factible de descens. SOLUCIÓ DETERMINACIÓ DE LES VARIABLES BASIQUES, SUPERBASIQUES I NO BASIQUES Les variables basiques Q :s; XB :s; X B , a ser possible estrictament entre fi.tes, han de tenir imprescindiblement columnes d'A linealment independents. Les variables superbasiques Q < Xs < X s han d'estar estrictament entre fites. Les variables no basiques X N han de tenir les seves components o a la seva fita superior: x N j = Xj, j E 7 o a la seva fi.ta inferior: x N J = O, J. E I, sent I i 1 els conjunt d'índexos de variables no basiques a fita superior i a fita inferior respectivament. Per triar les variables basiques tenim que: •x2 esta a la fita inferior i x5 i x7 estan a la superior (per tant, en principi, les excloem del conjunt de les basiques) •x1, x3 i x4 tenen les columnes linealment dependents (no poden ser simultaniament basiques) • x1, X3 i X6 poden ser les variables basiques XB perque tenen les columnes linealment independents: o 1 o •donat que hem trobat variables basiques estrictament entre fi.tes, totes les variables que es tan a una fita seran no basiques: X N = { x2, x5, x7}, i la resta de variables pmusal/metode de Murtagh-Saunders NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 45 ( estrictament entre fites) seran les superbasiques X s = { x4, x8}. ( Al tres combinacions de basiques i superbasiques són també possibles). MATRIUS S, N I A I CALCUL (NO NECESSARI) DE Z S és dones S = 8 -3 i N = [-3 3] d'on la matriu de constriccions actives B A és: o -3 O s N 1 3 o o -6 1 4 3 o -3 o -3 3 1 3 1 8-3 1 6 o -3 o-1 2 1 1 -1 -1 La matriu Z, la qual no és necessari tenir emmagatzemada de forma explícita, 1 -1 fóra: Z-[-B�-1S] _ -2 1 O -1 1 O O 1 o o o o o o ja que BVi = S1 dóna Vi GRADIENT I GRADIENT PROJECTAT Vf(X)' = X32 -2- - X5 + 3 -6 X1X3 -4 -4X5 -X1 -4x4 + 2x5X7Xa 2 X5 Xa X52X7 3 -2 -6 -2 -4 -2 8 2 5 Tenint en compte la ordenació i distribució de variables basiques X B = { x1, X3, X5} superbasiques Xs = { x4, x8} i no basiques X N = { x2, x5, x1}, tenim que: pmusal/metode de Murtagh-Saunders NN-F JH/EIO /UPC/2000 Col·lecció de problemes resolts/ OC I/ LlM-FME 46 Ga = h!] Gs = [-;4] GN = h�] i que la solució de B'II= G8 és: [ � ! J [ 3 �6]3] [ :: ] [ �!] _. rr = [!;] �3 l· [ !: ] = ¡ =�m DIRECCIÓ DE MENYS EL GRADIENT PROJECTAT Donat que IIZ'Gll2=14,5 no esta a prop de zero, haurem de fer una passa en la direcció Ps=Pz=-Z'G (o en la que s'obtindria de resoldre Z'HkZPz=-Z'G) i calcular Ps=-B-1SPs, ésa dir, resoldre BPs = -SPs i fer PN=Q. Calculant S Ps = [PBI] [ -61 [ -21 PB2 -3/2 obtenim Pa = 1/2 PB3 9/2 -7/2 La derivada direccional 'v J(Xk)P=G'sPB+G'sPs=-29/2<0 per tant queda compro vat que és una direcció de descens. pmusal/metode de Murtagh-Saunders NN-F JH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 47 PROBLEMA c-16. En la minimització de: pel procecliment de Iviurtagh-Saunders, s'ha trobat que en elp,�nt Xo=[ 3 O 3 ½ 5 4 5 lr Í partint d la subdivisió en variables basiques: XB={x¡, ;¡;3, xG}, superbasiques: Xs={ X4, xa} Í no basic¡ues: XN={x2,x5, X7}, el gradient projectat val zero: Z1V f(Xo)'=Q. Indiqueu si X0 pot ser un optim, i si no ho podés ser, quines variables haurien de canviar de valor i com calcularien el seu canvi. SOLUCIÓ CÁLCUL DEL GRADIENT A X0 I DELS MULTIPLICADORS II vf(X)' = � 5 X3 X2 -3xa2 • 2 xlo + 2x1 -2 2x5 -6X4Xa + 3 G = vf(Xo)' = 3 3 o -3 lQ2. 10 -2 10 1 Tenint en compte l'ordenació i distribució de variables basiques XB superbasiques X s = { x4, x8} i no basiques X N = { x2, x5, x7}, tenim que: i la matriu E de columnes bMiques és: E = [ �6 La solució de B1II = G B és: o 1 o pmusa2/metode de Jviurtagh-Saunders 1 o NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC 1/ LIM-FME 48 COMPROBACIÓ (NO NECESSÁRIA SEGONS L'ENUNCIAT) DE QUE Z'V f(Xo )'=Q La matriu Z és: [-3 3 l on S = 8 -3 -3 O TAXACIÓ DE LES VARIABLES NO BÁSIQUES La matriu de constriccions actives A és: 3 oo -3 3 1 3 1 B s N -6 14 8-3 1 6 o 3 o-3 -3 o -1 2 1 1 O) 1 -1 -1 L'equació de taxació (condició de 1� ordre) és: A'A = G amb A= [�] i cal que tots els components de I: siguin positius perque, sent Z'G=Q, siguem en un mínim. B'II = Ga II = [ �] (ja trobat) S'II = Gs --+ Gs -S'II =O= Z'G (segons enunciat) N'II+lI: = GN --+ I: =l(GN -N'II) Val la pena separar de la seva fita tota component XNj pera la qual CTj<Ü pmusa2/metode de lvfurtagh-Saunders NN-F J H/EIO /UPC/2000 Col·lecció de problemes resoJts/ OC I/ LJM-FME 49 _ (109 [ a5 --1 10 -3 6 2] ·[ i] ) =-�<O (x,: candidata a entrar) "' = -1 ( 10 -[ 1 O 1 ] · [ i] ) = -9< O ( x,: candidata a entrar) Donat que hi ha components de� negatius, NO soma l'optim (malgrat que Z'G=Q) ENTRADA D'UNA NO BÁSICA I DIRECCIÓ D'EXPLORACIÓ De les dues candi dates a entrar que tenim entrarem la de a i més negativa: x7, la �al sera afegida, provisionalment, al conjunt de les superbasiques: Xs={ x4, x8, x1} i XN={x2, xs}. Tenim així: és: S --[-_833 _303 �1] Gs --[-1103] [ l G N = \{9 i el nou gradient projectat Z' G -- - Z'G = Gs -S'II = 1 3 -3 O O O = Z�G [-3] ¡-3 8 -3] [.!.] [º] [] 10 1 O l i g signe de( 1x1x1 )a1 Farem una pass'.:: en la direcció Ps=Pz=-Z'G i calcularem Ps=-B-1SPs, ésa dir, resoldrem BPs = -SPs i fem PN=Q_. º] [PB1] 4 PB2 l PB3 -m obtenim Pe = [ ❖] Tenim dones Pe = [ ❖] i Ps = [ � 9] . Ara ca.ldria determinar la passa mii.xima i fer exploració lineal per determinar el nou punt. (Noti's que el component ps1=-9<0 és negatiu, com correspon a la variació de x1 que esta va a la seva fita superior). pmusa2/metode de Murtagh-Saunders NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC I/ LJM-FME 50 PROBLEMA c-17. Donada la minimització: m1n subj. a: 0�X�[4 4 4 4 4]' Efectueu un pas complet del metode del gradient redui:t generalitzat a partir del punt X0 = [1 O 3 1 1/2]', trobant: el gradient redui:t, la direcció d'exploració, la passa maxima i, prenent com a passa optima la meitat de la passa maxima, ún nou punt. A continuació efectueu una passa de projecció del nou punt sobre al hipersuperfície de les constriccions, segons el procediment del metode. Comproveu que la direcció d'exploració obtinguda és de descens. SOLUCIÓ GRADIENT I JACOBIÁ. A X0• Tenim un problema del tipus: 'vf(X)' = mm f(X) subj : H(X) = O o�x �x x2 -f -X5 + 3 -6 X1X3 -4Vf(Xo)' = -4 -xi 7 -6 -1 -4 -1 VH(X) = [ xi 3x11 X3 -2-1 X2 2xs 2x\- 1 l VH(Xo) = D 3x4 pgrgl/Gradient Redui·t Generalitzat 1 -1 1n 1o3 NN-FJH/EIO/UPC/2000 Col·lecció de problemes resolts/ OC 1/ LJM-FME 51 SELECCIÓ DE LES VARIABLES DEPENDENTS Y. No hauria de ser dependent la variable x2, perque esta a la seva fita inferior. Podem prendre dones Y = [ x 1 x3 ]', ja que: [1 -lJ ¡1 l ¡1 -lJ VyH(Xo) = 3 O = 3 O 3 és no singular. Les variables independents seran Z = [ x2 x4 x5 ]', i tenim que: [ 1 1 1 l VzH(Xo)= 1 3 1 Vyf(Xo)=[7 -1] Vzf(Xo)=[-6 -4 -1] Donat el LagrangiaL(Y,Z,A) = f(Y,Z)+A'H(Y,Z), imposant VyL = Vyf +A'VyH = O, tenim ¡ue podem calcular A amb el sistema Vy H' A = -V y f, i trobar el gradient redu:it fent: R' = V zL = V zf + A'V zH .. Així calculem primer A: i aleshores [ 1 3] A _ [1 l[ 1 3] [A1] __ [ 7 ] ⇒ { A1 = -1 -1 O --1 3 1 ,\2 --1 >.2 = -2 DIRECCIÓ I PASSA MÁXIMA DE LES VARIABLES INDEPENDENTS. Prenent D z basat en la direcció -R i donats els signes de -R en relació a les variables independents que es tan a la seva fita ( com x2 ), prenem: a2 = ( 4 -0)/9 = 4/9 } a4 = (4 -1)/11 = 3/11 ⇒ az = 3/11 Cl'.5 = ( 4 - 1/2)/4 = 7 /8 DI RECCIÓ I PASSA MÁXIMA DE LES VARIABLES DEPENDENTS. La direcció de canvi de les variables dependents es calcula a base de fer: H(Y + Dy, Z + Dz) � H(Y, Z) + '\lyH(Y, Z)Dy + V zH(Y, Z)Dz = O i donat que H(Xo) = O tenim: '\lyH(Y, Z)Dy = -V zH(Y, Z)Dz, així: [-46/3] Dy = 26/3 pgrgl/Gradient Redui't Generalitzat