UNIVERSIDADNACIONALDELCALLAOFACULTADDECIENCIASNATURALESYMATEMATICAOPTIMIZACIONCONTINUAERIKALEXPAPAQUIROZAgostode2011CALLAO-PERUGraciasportupaciencia.iiIndice1 Preliminares 31.1 Notaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 ResultadosdeAnalisis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 ElProblemadeOptimizacion 112.1 ProblemaGeneraldeOptimizacion . . . . . . . . . . . . . . . . . . . . . 122.2 ClasicaciondeProblemasdeOptimizacion . . . . . . . . . . . . . . . . 142.3 EjemplosdeProblemasdeOptimizacion . . . . . . . . . . . . . . . . . . 163 ExistenciadePuntosdeMnimoGlobal 333.1OptimosGlobalesyLocales . . . . . . . . . . . . . . . . . . . . . . . . . 333.2 ResultadosdeExistencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.3 EjemplosdeExistenciadePuntosOptimos. . . . . . . . . . . . . . . . . 403.4 EjerciciosResueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.5 EjerciciosPropuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 CondicionesdeOptimalidaddeProblemasDiferenciables 504.1 ProblemassinRestricciones . . . . . . . . . . . . . . . . . . . . . . . . . 504.2 RestriccionesArbitrarias . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.3 RestriccionesdeIgualdad . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.4 RestriccionesdeDesigualdad. . . . . . . . . . . . . . . . . . . . . . . . . 744.5 RestriccionesMixtas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844.6 EjerciciosResueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88iii4.7 EjerciciosPropuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075 ElementosdeConvexidad 1085.1 ElementosdeConvexidad . . . . . . . . . . . . . . . . . . . . . . . . . . 1085.2 ElTeoremadelaProyeccion. . . . . . . . . . . . . . . . . . . . . . . . . 1135.3 SeparaciondeConjuntosConvexos . . . . . . . . . . . . . . . . . . . . . 1165.4 Funcionesconvexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215.5 ContinuidaddeFuncionesConvexas. . . . . . . . . . . . . . . . . . . . . 1295.6 DerivadaDireccionaldeFuncionesConvexas . . . . . . . . . . . . . . . . 1325.7 Subdiferenciabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1345.8 FuncionesConvexasDiferenciables . . . . . . . . . . . . . . . . . . . . . 1435.9 EjerciciosResueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1445.10 EjerciciosPropuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1486 OptimizacionConvexa 1496.1 MinimizacionConvexaIrrestricta . . . . . . . . . . . . . . . . . . . . . . 1516.2 MinimizacionConvexaRestricta. . . . . . . . . . . . . . . . . . . . . . . 1526.3 ConvexidadGeneralizada . . . . . . . . . . . . . . . . . . . . . . . . . . . 1546.4 EjerciciosResueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1556.5 EjerciciosPropuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162ReferenciasBibliogracas 163ivIntroduccionEl material de la presente edicion trata del estudio formal del problema de encontrarlospuntosdemaximosy/omnimosdeunafuncionsinrestriccionesosujetaaalgunasrestricciones sobre su dominio. Esta funcion, llamada funcion objetivo, puede representardiversos fenomenos en estudio dependiendo del campo de aplicacion, por ejemplo, puederepresentar la temperatura, la energa, el benecio de una empresa, el costo de producciondeterminadosproductos, etc, esporesoqueel tematienegraninteresenlasdiversaslneasdeinvestigacionencienciaseingenieras.El area que estudia de manera rigurosa el problema de encontrar los puntos demaximosy/omnimosdeunafuncionesllamadaoptimizacionmatematicayestaasuvez, dependiendo cual sea la naturaleza del problema, se divide en optimizacion continua,combinatoria,entera,dinamica,estocastica,entreotras.El temaquepresentareenestaedicioneslaoptimizacioncontinuaenespacioseu-clidianosqueeslabaseparael estudiodelasotrassubareasdelaoptimizacionyqueenesenciaestudiaproblemasdeoptimizacioncuandolasvariablesquedenenel prob-lemanosondiscretas, estoes, puedentomarcualquiervalordentrodelconjuntodelasrestricciones.Despuesdepresentaralgunosproblemasdeoptimizacionencontradosenlasaplica-ciones, estudiaremos las condiciones sucientes para garantizar la existencia de solucionesoptimas, paraluegoestudiar las condiciones necesarias ysucientes paracaracterizaroptimosdefuncionessucientementeregulares. Finalizaremoseltrabajoconelestudiode la convexidad de conjuntos, funciones convexas y problemas de optimizacion convexa.Debo aclarar que no existe un aporte innovador en la teora presentada pero lo que siencontraremos, a diferencia de otros textos, es la variedad de ejemplos, contraejemplos y1ejerciciosresueltosparaquelateoraquedebiensustentadayentendida.El material estamotivadopor las lecturas de algunos libros de optimizacionqueseencuentranenlas referencias bibliogracas yquealolargodeestos a nos heleidocuidadosamente, es por eso, que algunos de los ejercicios propuestos en esos libros fueronaqu desarrollados. Tambien, algunos ejemplos de problemas de optimizacionfuerontomadosderecientestrabajosdeinvestigacionquehetenidolaoportunidadderevisarenalgunasrevistascientcasyotroscomoporejemplolosproblemasdeoptimizacionsemidenidadealgunasinvestigacionesqueherealizadoconalgunosco-autores.Este trabajo esta dividido en 6 captulos: El primer captulo da algunos preliminaresmatematicos usados a lo largo del texto. El segundo captulo presenta el problema generalde optimizacion y algunos ejemplos de problemas en diversos campos de las ciencias quepueden ser modelados como problemas de optimizacion. El tercer captulo trata sobre laexistencia de soluciones optimas de problemas denidos en espacios euclidianos. El cuartocaptulo presenta las condiciones de optimalidad necesarias y sucientes de problemas deoptimizacionparafuncionesdiferenciables. Elquintocaptulotratadelaconvexidaddeconjuntos,losteoremasdeseparacion,ascomotambien,delasprincipalespropiedadesde las funciones convexas y el sexto captulo trata de problemas de optimizacion convexa.Paranalizar deboresaltar queestematerial formopartedel cursodeSeminariodeTesisI, disciplinadel novenociclo, realizadoenlaFacultaddeCienciasNaturalesyMatematicadelaUniversidadNacionaldelCallaoaniveldePre-Gradoyporendemegustaraagradecer alas autoridades deestainstitucionpor lainvitacionparaformarparte de la plana docente, al profesor Runo Moya Calderon por la motivacion indirectapara continuar este trabajo cuando las fuerzas se desvanecian, al personal Administrativoque me ha dado toda la comodidad suciente para realizar un trabajo sin contratiempos,aloscolegasporlaarmoniosayamigableconvivenciaentodoestetiempoyagradecerespecialmentealosalumnosqueconsuspreguntasysugerenciashicieronnacerlaideadeprepararestetexto. Acadaunodeustedesquecolaborarondirectaeindirectamenteconelpresentetrabajounsinceroagradecimiento.Bellavista,3deAgostodel2011ErikAlexPapaQuiroz.2Captulo1PreliminaresEneste captulo presentamos las notaciones utilizadas a lo largo del texto comotambienlos resultados basicos de analisis real necesarios parael buenentendimientodelateorapresentada.1.1 NotacionesEneldecorrerdeestelibro,adoptaremoslassiguientesnotaciones:Rn= x = (x1, x2, . . . , xn) : xi R,paratodoi = 1, . . . , n.Rn++= x = (x1, x2, . . . , xn) Rn: xi> 0,paratodoi = 1, . . . , n.R+: elconjuntodelosn umerosrealesnonegativos.R++: elconjuntodelosn umerosrealespositivos.Dadosx, y Rn,xTy=

ni=1xiyi.Dadox Rn, |x| :=xTx: lanormaeuclidiana.(0, 1) := z R : 0 < z< 1.DadoX Rn,XdenotaralaclausuratopologicadeX.DadoX Rn,Front(X)eslafronteradeX.DadoX Rn,int(X)eselinteriordeX.x XY signicaquex Xyx/ Y.xk x,denotalimk+xk= x.3f:elgradientedef.B( x, ) = x Rn: |x x| < :labolaabiertadecentro xyradio.Dadox = (x1, x2, . . . , xn) Rn,x 0signicaquexi 0,paratodoi = 1, . . . , n.2f(x)denotalamatrizhessianadefenelpuntox.Ker(h(x))denotaeln ucleodelamatrizh(x).Im h(x)T= v Rn: v= h(x)T.DadoA Rnn,ATdenotalatranspuestadeA.DadoA Rnn,A 0signicaqueAesdenidapositiva.DadoA Rnn,A _ 0signicaqueAessemidenidapositiva.on= X Rnn: X= XT: elespaciodelasmatricessimetricas.DadoX on,tr(X)denotalatrazadelamatrizX.DadoX on,XY:= tr(XY ): produtointernoen on.Seaunabiertode Rn,Ck() = F: U Rm: fes k vecesdiferenciableen U.C() = F: Rm: Fesunafuncioninnitamentediferenciableen .liminfk+f(xk) = supn infknf(xk).limsupk+f(xk) = infn supknf(xk).L2() =_f: C, medibleenelsentidodeLebesgue y_[f[2< _.H10() = u L2() : u L2() u(x) = 0 , x Front().Dadog: X RnR, x argmaxg(y): y X, denotag(x) g(y), paratodoy X.Dadog: X RnR, z argming(y) : y X, denotag(z) g(y), paratodoy X.ln zdenotaellogaritmoneperianodez.Fc= RnFdenotaelcomplementodelconjuntoF.1.2 ResultadosdeAnalisisConsideremoselespacio Rn= x = (x1, . . . , xn) : xi Rydenamosdosoperaciones:+ : RnRnRn: +(x, y) := (x1 + y1, . . . , xn +yn),4 : R RnRn:(, x) := (x1, . . . , xn).Porsimplicidaddenotaremos+(x, y)=x + y, y(, x)=x. ObservequeRnconestas dos operaciones forma un espacio vectorial sobre el cuerpo de los n umeros reales R.As,hemosdotadoa Rnconpropiedadesalgebraicas.Como en todo espacio es necesario medir magnitudes, calcular errores, etc, dotaremosa Rndeunametrica,paraellodenimos:d : RnRnR : d(x, y) :=n

i=1(xiyi)2.Sepuedevericarquedcumplelassiguientespropiedades:d1: Paratodo x, y Rn, d(x, y) 0,d(x, y) = 0si,ysolosi,x = y.d2: Paratodo x, y Rn, d(x, y) = d(y, x).d3: Paratodo x, y, z Rn, d(x, z) d(x, y) + d(y, z).La funcion d se llama metrica euclidiana y el espacio vectorial Rncon esta metrica esllamadoepacioeuclidiano.Enelespacioeuclidiano Rn,denamos|.| : RnR : |x| := d(x, 0) =n

i=1x2i.Estafuncionesllamadanormaeuclidianaonorma2ysatisface:n1: |x| 0, para todo x Rn; [[x[[ = 0si,ysolosi,x = 0.n2: |x| = [[[[x[[, para todo x Rn,paratodo R.n3: |x + y| |x| +|y|, para todo x, y Rn.Enelespacioeuclidianotambienesposibleintroducirunproductointernoqueper-mitiradenirposteriormenteelconceptodeanguloentredospuntos , ) : RnRnR : x, y) :=n

i=1xiyi.Elproductointerno x, y)seradenotadotambienporxTy.5Observacion1.1Delasdenicionesdadasobtenemoslassiguientesigualdades:d(x, y) = [[x y[[ =_(x y)T(x y).Dado x Rny > 0denamosB( x, ) = x Rn: [[x x[[ < .Denicion1.1UnconjuntoA Rnesabiertoen Rnsiparatodox A,existex> 0tal queB(x, x) A.UnconjuntoF Rnescerradoen Rnsiparatodasucesi on xk Ftalquexk xsetienequex F.Denicion1.2DadoX Rn, unpunto x RnesllamadopuntoadherentedeXsiparatodo > 0,B( x, ) X ,= .Unpunto x RnesllamadopuntodeacumulaciondeXsi paratodo>0, B( x, ) X x ,= .Denicion1.3DadoX Rn, laclausuradeX, denotadoporX, esel conjuntodetodoslospuntosadherentes.Teorema1.1SeaF Rn. FescerradoenRnsi ysolosi FC= RnFesabiertoenRn.Demostracion. Ver[11],Teorema17,pagina. 40.Denicion1.4UnconjuntoC RnesllamadoacotadosiexisteM> 0talque [[c[[ M, paratodoc C.Teorema1.2Si xk Rnesunasucesi onlimitada, entoncesexisteunasubsucesi onxkjde xkconvergente.Demostracion. Ver[11],Teorema5,pagina. 17.Denicion1.5SeaunconjuntoK Rn. Kescompactosi ys olosi Kescerradoyacotado.6Denicion1.6DadounamatrizA Rnn,Aesllamadamatrizsemidenidapositiva,denotadoporA _ 0,sidTAd 0,paratodod Rn.AesdenidapositivasidTAd > 0,paratodod Rn 0 .Denicion1.7Seaf: A RmunafunciondondeA Rn.Sedicequefescontinuaen x Asi paracada>0, existe>0tal quesi [[x x[[ 0.29FaseExplotacionElagente debe beneciarse alobtener unnuevo estadomejorado.Elescogeexplotarsubenecioenuntiempo > 0.Es as quedel estadox Xdescubrimos unnuevoestadoy Xmejorado, tal queg(y) > g(x),demodoquen(y) < n(x).Encadaperiodok IN,seconsideralafunciongananciaproximalPk(xk, y) = g(y) kC(xk, y, )dondexk, y E(xk, r(xk)), k=1k, C(xk, y, )esel costodedesplazamientosatisfa-ciendoC(xk, xk, 0) = 0.AsumiremosporsimplicidadqueE(xk, r(xk)) = X, k IN. As,el agentetratar ademaximizarsugananciaproximal resolviendoparacadakxk+1 argmaxPk(xk, y) : y X,el cual esequivalentea: xk+1 argminn(y) + kC(xk, y, ); y X.El objetivo de este modelo es generar una sucesion_xk_tal que en el lmite se obtengalametapropuesta.Ejemplo2.15(Suma de los mayores autovalores). Recientemente Overton y Wom-ersley[14] (Teorema3.4, pagina329), presentaronlasiguientecaracterizaci onparalasumadelosprimeroskmayoresautovaloresdeunamatrizsimetrica1(A) + . . . + k(A) =maxAX: TrX= k, 0 _ X _ I,dondej(A), j =1, . . . , k, denotael j-esimomayorautovalordeAyAXdenotalatrazadeAX. El problemadadoperteneceaunaclaseespecial deproblemas deopti-mizaci onllamadosproblemasdeoptimizacionsemidenida(lasvariablessonmatricessemidenidaspositivas)ycuyoformatogeneral parael casoacotadoesminXSnf(X) : /X= b, 0 _ X _ I (2.4)donde f : onRes una funcionreal, ones el espacio vectorial de las matricessimetricas, I ones lamatriz identidad, el operador /: onRmes denidopor/X:= (Ai X)mi=1 Rm, conAi on;X on; X _ 0signicaqueXessemidenidapositiva,yX _ IsignicaqueI X _ 0.30Ejemplo2.16(Mnimodelasumadelosmayoresautovalores,ver[15]). Con-sideremosel problemademinimizarlasumadelosprimeroskmayoresautovaloresdeunamatrizsimetrica:min1(A(y)) + . . . + k(A(y)) : y RmdondeA(y) = A0 +m

i=1yiAi. Puedeserprobado(verAlizadeh[1],Teorema4.3),queeldual deesteproblemaesmaxA0 X: TrX= k, AjX= 0paraj= 1, . . . , m, 0 _ X _ I. (2.5)Notequepodemosexpresar(2.5)comomaxA0 X ; /X= b, 0 _ X _ I,donde /X=(IX, A1 X, . . . , Am X)Tyb=(k, 0, 0, . . . 0) Rm+1. Portanto, esteproblematienelaformade(2.4).Ejemplo2.17(Minimizaciondelasumaponderadadelosautovalores). Con-sidereel siguienteproblema:minm11(A) + . . . +mkk(A), dondem1 . . . mk> 0. (2.6)DonathyHomanen[6]reformularonestasumacomosigue:m11+. . . +mkk= (m1m2)1+(m2m3)(1+2) +. . . +(mk1mk)(1+. . . +k),dondeporsimplicidadusamoslanotacioni=i(A). Paracadasumaparcial deauto-valores del lado derecho de la igualdad podemos usar la formulacion del ejemplo anterior,obteniendomin (m1m2)X1 A + (m2m3)X2 A + . . . +mkXkAs.a: Tr(Xi) = i para i = 1, . . . , k0 _ Xi _ I.Observe que este problema puede ser expresado en la forma (2.4), donde f(X) = CX, conX= diag(X1, X2, . . . , Xn),C= diag((m1m2)A1, . . . , , (mk1mk)Ak), /(X) = IX,yb = (1, 2, . . . , k)T. As,(2.6)esuncasoparticularde(2.4).31Ejemplo2.18(El problemadeparticiondeungrafo). Unimportantecasodelproblemadeparticiondeungrafo,ver[1],esformuladocomo:minCX; Xii= k/n, 0 _ X _ I. (2.7)Podemos expresar (2.7) como (2.4) usando f(X) = CX, A1= diag(1, 0, . . . , 0), A2=diag(0, 1, 0, . . . , 0), . . . , An= (0, 0, . . . , 0, 1)yb = (k/n, k/n, . . . , k/n) Rn.32Captulo3ExistenciadePuntosdeMnimoGlobalEl espacioeuclidianodondeestudiaremoslascondicionesdeexistenciaycaracteri-zacion de las soluciones optimas de problemas de optimizacion es un espacio bien naturalparamodelarproblemasdeoptimizacion. Inclusosielproblemaseencuentraenunodedimensioninnitalosdiversosmetodosdediscretizacionpermitentransformarel prob-lemaoriginalenunproblemadenidoenunespacioeuclidiano.3.1OptimosGlobalesyLocalesEn Optimizacion existen dos tipos de optimos: locales y globales, que pasamos a denir.Denicion3.1(Mnimolocalymnimoglobal) Seaf: X RnRunafunci ondenidasobreX. Unpunto x Xesllamadounpuntodemnimolocal defsobreXsiexiste > 0tal quef( x) f(x),paratodox X B( x, ).El punto x Xes llamado punto de mnimo global de fsobre Xsi f( x) f(x), paratodox X.Observacion3.1Larelacioninmediatadeestasdosdenicionesesquetodomnimoglobal esunmnimolocal,perolaviceversa,evidentemente,noesverdadera.Analogamente,tenemoslasiguientedenicion.33Denicion3.2(Maximolocalymaximoglobal) Sea f: X RnR una funci ondenidasobreX. Unpunto x Xesllamadounpuntodemaximolocal defsobreXsiexiste > 0tal quef( x) f(x),paratodox X B( x, ).El punto x Xesllamadopuntodemaximoglobal def sobreXsi f( x) f(x), paratodox X.Figura3.1:Optimoslocalesyglobales.Observacion3.2Desde que todoproblemade maximizaci onpuede ser transformadoenunodeminimizacion, apartir deahoraconsideraremos parael analisis solamenteproblemasdeminimizacion.3.2 ResultadosdeExistenciaConsidereelproblemaminf(x) : x X,dondef : X RnRes unafunciondenidasobreX. Unapreguntanatural essabersiexisteunpuntoqueresuelvaelproblemaplanteado. VeremosqueparaelloseranecesarioimponeralgunascondicionessobrefyX.34Una condicion necesaria para probar la existencia de un punto de mnimo global es quelafuncionfseaacotadainferiormente, estoes, inff(x):x X> . Observemosque esta condicion no es suciente, considere por ejemplo la funcion exponecial f(x) = ex,dondex R.Estafuncionesacotadainferiormenteporceroperonoexiste unpuntodemnimoglobalcomosemuestraenlagura3.2.yx1exFigura3.2: Lafuncionexponencialtiene nmoperonomnimo.Unresultadoclasicoparagarantizarlaexistenciadepuntosdemnimoglobal eselconocidoTeoremadeBolzano-Weierstrass,aplicadoafuncionescontinuassobreconjun-toscompactos. Enestelibroconsideraremosunahipotesismasdebil, lacondiciondesemicontinuidadinferior,quepasamosadenir.Denicion3.3Dadaunafuncionf : X RnR. f es semicontinuainferioren x X,siparatodasucesi on xkdeXconvergenteen xsetienequeliminfk+f(xk) f( x),dondeliminfk+f(xk) := supnN infknf(xk). Sifessemicontinuainferiorparatodox X,entoncesdecimosquefessemicontinuainferiorenX.Resultaclarodeladenicionquetodafuncioncontinuaessemicontinuainferiorperoelrecproconoesverdadcomomuestraelsiguienteejemplo.35Ejemplo3.1Lafuncionf: [1, 2] Rtal quef(x) =___(x + 1)2, six (1, 2],1, six = 1,essemicontinuainferioren x=1peronoescontinuaen x=1(vergura3.3). Enefecto, es obvio que la funcion no es continua en 1, probemos que es semicontinua inferioren este punto. Sea xk [1, 2] tal que xk 1, como la funcion es creciente para n INtenemosqueinfknf(xk) = 4,porlotantosupnN infknf(xk) = 4 > 1 = f(1).Figura3.3: Lafuncionfessemicontinuainferiorperonoesunafuncioncontinua.Teorema3.1Dadaunafuncionf: X RnR. SifessemicontinuainferiorenunconjuntonovacioycompactoXentoncesexisteunpuntodemnimoglobal.Demostracion. Probemos inicialmente que f es acotada inferiormente. Por con-tradiccion,supongamosqueexisteunasucesion xk Xtalquelimk+f(xk) = . (3.1)Como xk XyXes unconjuntocompacto, entonces estasucesioncontieneunasubsucesion xkjconvergenteenX, estoes, existe x Xtal que limj+xkj= x.36Debidoquefessemicontinuainferiortenemos:f( x) liminfj+f(xkj).Yaque f(xkj)esunasubsucesionde f(xk)ypor(3.1)obtenemosquef( x) ,locualesunacontradiccion. Porlotanto,feslimitadainferiormenteenX. As,existe Rtalque = inff(x) : x X,estoimplicaque existe unasucesion xl Xtal que liml+f(xl) =. Por lacompacidad de Xexiste una subsucesion xlj y x Xtal quelimj+xlj= x. Debidoalasemicontinuidadinferiorf( x) limj+f(xlj) = .De esta ultima desigualdad obtenemos que f( x) = y por lo tanto f( x) f(x), paratodox X,estoes, xesunmnimoglobaldefenX.Ejemplo3.2ConsiderelafuncionfdenidaenelEjemplo3.1,comoestaessemicon-tinuainferiory[1, 2] escompacto, entoncesusandoel teoremaanteriorconcluimosqueparafexisteunmnimoglobal en[1, 2].Corolario3.1Dadaunafuncionf:X Rn R. Si XesnovacioycompactoyfescontinuaenX,entoncesexisteunpuntodemnimoglobal.Prueba. Si f es continuaentonces es semicontinuainferior yaplicandoel teoremaprecedenteobtenemoselresultado.Observacion3.3Lacondici ondecompacidaddeXesmuyfuerteparagarantizarlaexistenciadeunmnimoglobal. Enefecto,considereel problemaminx2: x R (3.2)AquX= Rnoescompactoperoexisteel mnimoglobal.ParadebilitarlahipotesisdecompacidaddeX,denamos,para R,elconjuntoLf() := x X: f(x) ,llamadoconjuntodenivel inferiordef(Vergura3.4).37Figura3.4: Gracodelconjuntodenivelinferior.Corolario3.2Sea una funcion f: X RnR. Si Lf() es no vacio y compacto paraalg un RyfessemicontinuainferiorenLf(),entoncesexisteunpuntodemnimoglobal defenX.Prueba. Consideremoselsiguienteproblemadeoptimizacionminf(x) : x Lf().ComofessemicontinuainferiorenLf()yLf()esnovacioycompacto,entoncesporelTeorema3.1,existe x Lf()talquef( x) f(x), paratodox Lf().Tomemos x como candidato para mnimo global de fsobre X. Sea x X(arbitrario) yconsideremosdoscasos:i). Six Lf(),porelresultadoanteriortenemosf( x) f(x).ii). Six/ Lf(),entoncesf(x) > f( x).As,f( x) < f(x).Deamboscasosobtenemosque xesunmnimoglobaldefsobreX.Corolario3.3Seaunafuncionf: X RnR. SiXescerradoyLf()esnovacioyacotadoparaalg un R, conf semicontinuainferiorenLf(), entoncesexisteunpuntodemnimoglobal defenX.Prueba. Similaralcorolarioanterior.38Observacion3.4En el corolario anterior la condici on de cerradura de Xes fundamen-tal. En efecto, considere por ejemplo X= (1, 1] (conjunto no cerrado) y f(x) = (x+1)2.Aquparatodo R++setienequeLf() = (1, 1] esnovacio,acotadoyfescontinuaperonoexisteel mnimoglobal defenX.Paradebilitarmasa unlascondicionesdeexistenciademnimosglobalesdeniniremoselconceptodefuncioncoerciva.Denicion3.4Decimos que una sucesi on xk en Xes crtica (en relacion al conjuntoX)si: limk+|xk|=+limk+xk= x XX, dondelanotacion x XXsignicaque x Xy x/ X.Lafuncionf:X Rn ResllamadacoercivaenXsi paratodasucesi oncrticaxksetiene:limsupk+f(xk) = +,donde limsupk+f(xk) :=infnN supknf(xk).Ejemplo3.3Dadox0 Rnjo, f: Rn Rtal quef(x)= |x x0|, esunafunci oncoercivaenRn.Corolario3.4Dadaunafuncionf : X RnR. Si f escoercivaysemicontinuainferiorenunconjuntonovacioX,entoncesexisteunpuntodemnimoglobal defenX.Prueba. ComoX ,= ,existe RtalqueLf() ,= (X ,= ,entoncesexiste x X,as podemostomar=f( x)). ProbaremosqueLf()esacotado. Porcontradiccion,supongamos que Lf() no es acotado, entonces existe una sucesion xk Lf() tal quelimk+|xk| = +,luego xkesunasucesioncrticaenLf(). ComoxkLf(), setienef(xk) ,tomandolmitesuperior cuandok +yusandolacoercividaddef tenemosquelimsupk+f(xk) =+ , loque es unacontradiccion. Por lotantoLf() esacotado.39Probaremos ahora que Lf() es cerrado. Sea xk Lf() una sucesion tal que xk xysupongamosque x/ Lf(),estoes, x/ Xof( x) > .Si x/ Xentonces xkesunasucesioncrticayporlacoercividaddefsetieneque:+ =limsupk+f(xk) ,loqueesunacontradiccion.Sif( x) > ,entoncesporlasemicontinuidadinferiorsetieneque < f( x) liminfk+f(xk) ,loqueesunacontradiccion. Porlotanto x Lf()yasLf()escerrado.Finalmente,usandoelCorolario3.2obtenemoselresultadodeseado.3.3 EjemplosdeExistenciadePuntosOptimosEjemplo3.4(Existenciadesolucionesdeproblemasdemaximizaci on). Considereelproblemademaximizaci onmaxf(x) : x X (3.3)dondef:X Rn RyXdenotael conjuntodelasrestricciones. Decimosquefessemicontinuasuperior(s.c.s.) en x X,siparatodasucesi on xk Xtalquexk xsetieneque limsupk+f(xk) f( x).Usando los resultados del Teorema 3.1 se puede probar facilmente que si f: X RnRess.c.senX,novacioycompacto,entoncesexisteunmaximoglobal.ConsideremosahoraelconjuntodenivelsuperiorUf() := x X: f(x) .Usandoel Corolario3.2sepuedeprobarquesifess.c.senXyUf()esnovacioycompacto,paraalg un,entoncesexisteunpuntodemaximoglobal defenX.Ademas, usandoel Corolario3.4setienequesi f escoercivays.c.senunconjuntonovacioX,entoncesexisteunpuntodemaximoglobal defenX.Ejemplo3.5Dadosp = (p1, ..., pn), conpi> 0, i = 1, ..., n, yb R++. El problemadelautilidadmnimaymaximadel Ejemplo2.13consisteenresolveroptf(x) : pTx b, x 040donderecordamosqueoptsignicaminimizaromaximizarfyx 0signicaquecadacomponentexi 0, paratodoi = 1, ..., n.Estudiaremossiel problemadadotienemnimoymaximoglobal. DenamosX=_x Rn: pTx b, x 0_.ArmamosqueXescompacto. Enefecto,dadox X,entoncesp1x1 +p2x2 + .... + pnxn b.Comolosxi 0ypi> 0,entoncesxi bpi, paratodoi = 1, ..., n.DenamosM= minpi, i = 1, ..., n > 0. Elevandoalcuadradoladesigualdadanteriorytomandosumatoriatenemos: |x|2nb2M2,estoes, |x| nbM.Si fes semicontinua inferior, entonces el problema tiene un mnimo global y si fes semi-continuasuperiorel problematienemaximoglobal. Ademas, si f escontinuaentoncesconcluimosqueel problematienemnimoymaximoglobal.Ejemplo3.6El problemadel funcionamientodeunsistemadeproducciondeenergaelectricaconsistaenresolver:min_n

i=1Ti(xi) :n

i=1xi= Ec + Ep, i xi i_.EsfacilprobarqueX=_x :n

i=1xi= Ec +Ep, i xi i_escompactoyquef(x) =n

i=1Ti(xi)essemicontinuainferior,entoncesusandoelTeorema3.1,setienequeelprob-lemadadotieneunmnimoglobal.Ejemplo3.7El problemademinimizacioncuadraticaconsisteenresolvermin_f(x) =12xTAx bTx + c : x Rn_,dondeA Rnn,b Rnycesunn umeroreal. SisecumplequeA 0,entoncesexisteunpuntodemnimoglobal. Enefecto, probaremosquelafuncionf escoercivaenRn.Porcontradiccion,supongamosquefnolosea,entoncesexiste_xk_tal que__xk__ +, pero f(xk) M, paratodok IN,41paraalg unMR. Tenemos por lotantoque:12xkTAxkbTxk+cM. Paraksucientementegrandesetienequexk,= 0y12_xkT|xk|_A_xk|xk|_bT_xk|xk|2_+c|xk|2 M|xk|2.Tomandounasubsucesi onsiesnecesario,existez ,= 0tal quezk=xk|xk| z.Pasandoallmiteenla ultimadesigualdadymultiplicandopor2seobtienezTAz 0,loque contradice la hip otesis de que A es denida positiva. As,f(x) =12xTAxbTx+c escontinua y coerciva y por lo tanto, usando el Corolario 3.4, se tiene que existe un mnimoglobal def.Ejemplo3.8(Elproblemadelamnimadistancia). DadounsubconjuntoXde Rn.Elproblemadelamnimadistanciade yaXesmin f(x) = |x y| : x X .Si Xescerrado, entoncesexisteel mnimoglobal del problema. Enefecto, analisemosdoscasosi.) SiXesacotado,entoncesXescompactoycomofescontinua,el mnimoglobalexiste.ii.) SiXnoesacotado, entoncesexiste_xk_tal que limk+|xk|=+. ComoXescerrado, entonces_xk_esunasucesi oncrtica, ycomof(xk) +, setienequefescoercivaenX.Comofescontinuaycoercivaentoncesexisteel mnimoglobal.3.4 EjerciciosResueltosEjercicio3.1Probarqueel problema___min f(x, y) = x2+ y +1x+ysujeto a : x + y> 0tieneunasolucionglobal.42Solucion. ConsideremoselconjuntoX= (x, y) R2:x + y>0,quenoescerradoniacotado,laideaentoncesesprobarqueelconjuntodenivelLf(c) =_(x, y) X: x2+ y +1x + y c_escompactoparaalg unc R.ProbemosqueLf(c)esacotado.Supongamos que Lf(c) no es acotado, entonces existe_(xk, yk)_ Lf(c)tal que |(xk, yk)| +,entonces:(xk)2+ (yk)2 + (3.4)Desdeque_(xk, yk)_ Lf(c),tenemostambienque:_xk12_214< (xk)2+ (yk) < (xk)2+ (yk) +1xk+ yk c (3.5)Entonces_xk_es acotadoyporlaecuacion(3.4),(yk)2 +,cuando k +,luegosetienequeyk +,cuandok +(siyk ,delacondicionxk+yk> 0ydelalimitaciondexksetendraque 0).De la ecuacion (3.5) se tiene que + c, lo que es una contradiccion, entonces Lf(c) esacotado.ProbemosqueLf(c)escerrado.Porcontradiccion,supongamosqueLf(c)noescerrado,entoncesexiste_(xk, yk)_ Lf(c) : (xk, yk) (x, y) XX.Asx + y= 0.Usandonuevamentelaecuacion(3.5)setiene(xk)2+ (yk) +1xk+yk c.Tomandolmitetenemosque+ c,loqueesunacontradiccion.Deambos resultados concluimos queLf(c) es compactoycomof es continuaenXentoncesexisteunmnimoglobal.Ejercicio3.2Digasilafuncionf(x1, x2) = x41 + x4232x22esonoescoerciva.Solucion. Lafuncionf puedeserexpresadacomof(x1, x2)=x41 + (x22 16)2 162.Probaremosquefescoerciva. Paraellosea (xk1, xk2)unasucesiontalquelimk[[(xk1, xk2)[[ = +.Deaqusetieneque limk[xk1[ = +o limk[xk2[ = +.43Si limk[xk1[ = +y como f(x1, x2) x41162, se tiene quelimkf(xk1, xk2) = +Si limk[xk2[ = +y como f(x1, x2) (x2216)2162, se tiene que limkf(xk1, xk2) =+.Asquedaprobadoquelafuncionfescoerciva.Ejercicio3.3Vericarsilassiguientesfuncionessononocoercivas:a) f(x1, x2, x3) = x61 + 5x42 +x33x1x2x23.b) f(x1, x2, x3) = ex21+ ex22+ ex23x1001x1002x1003.Solucion.a) Lafuncionf(x1, x2, x3) = x61 + 5x42 +x33x1x2x23,noescoerciva.Enefecto, tomelasucesion xk, dondexk=(0, 0, k), entonces tenemos que[[xk[[ +pero limk+f(xk) =limk+k = .b) Lafuncionf(x1, x2, x3)=ex21+ ex22+ ex23 x1001 x1002 x1003escoercivadesdequelimr+er2r100= +.Ejercicio3.4SeanX1yX2subconjuntosdeRntalesqueX2 X1yf: Rn Runafunciondada,pruebeque infxX1 f(x) infxX2 f(x). Ademas,si xesunminimizadordefsobreX1tal que x X2entonces xesunminimizadordeX2.Solucion. SifnoesacotadainferiormenteenX1entonces infxX1f(x) = infxX2f(x)yelejercicioquedaprobado.Sea f acotada inferiormente en X1entonces existe el nmo de f en concescuenciainfxX1f(x) :=m f(x), paratodox X1. ComoX1 X2, enparticular tenemos:m f(x), paratodox X2,deaqu,fesacotadainferiormenteenX2yasexisteelnmodefenX2ym infxX2f(x).SustituyendoelvalordemseobtieneinfxX1f(x) infxX2f(x).Si x es minimizador de fsobre X1, entonces f( x) f(x) para todo x X1. En particularsetienef( x) f(x), paratodox X2, luego, comoporhipotesis x X2setienequeestepuntoesunminimizadordefsobreX2.44Ejercicio3.5Supongamosqueel problemademinimizacionirrestrictadeunafunci oncontinuaenRntieneunmnimoglobal. Respondersi esoimplicaqueftieneunmini-mizadorglobalsobrecualquierconjuntocerradode Rn.Sinolofueradaruncontraejem-plo.Solucion. Noimplica. Enefecto,considerelafuncion:f(x) =___ex,x (, 0];(1 x)2,x (0, +)fescontinuaenRytieneunminimizadorglobal enx=1. Considerandoel conjuntocerrado (, 0] (pues el complemento (0, +) es abierto) se tiene que fno tiene mnimo(, 0].Ejercicio3.6Seaf:RnRcontinua. Pruebeque xesunminimizadorglobal defenRnsiys olositodox Rntal quef(x) = f( x)esunminimizadorlocal.Solucion.Si x es un minimizador global de fentonces todo x tal que f(x) = f( x) es un minimizadorglobalyporlotantolocal.Supongamos ahoraque todox Rntal que f(x) =f( x) es unminimizador local.Probaremosque xesunminimizadorglobal. Porcontradiccion,supongamosqueexiste Rntalquef() < f( x)y0 < f( x) f()tomando = (f( x) f())/2yusandoladeniciondecontinuidaddefen,existe> 0talque,paratodox B(, )setiene:[f(x) f()[ liminfkf(xk),entoncesexiste Rtalque:f(x) > > liminfkf(xk). (3.8)Deaqu sededuceque>liminfkf(xk):=supnIN_infknf(xk)_, peroestoim-plicaque >infknf(xk),paratodon IN,yenconsecuencia >infknf(xk),paratodon IN.Asexisteunasubsucesion xklde xktalquef(xkl) .Deaqu,xkl Lf() y xkl x.Ademas, comoLf()escerradosetienequex Lf()yas f(x) . Deloanterioryde(3.8)tenemosquef(x) > f(x),loqueesunacontradiccion. Porlotantofessemicontinuainferior.Ejercicio3.9Estudielacoercividaddelafuncionf(x) = aTx,dondea Rn.Solucion. estudiaremosdoscasos:i) Si a = 0, entonces la funcion es f(x) = 0, paratodox Rny as esta no es coerciva.ii) Si a ,= 0, entonces existe i0 1, 2, ..., ntal que ai0 ,= 0. Sin perdida de generalidad,supongamosqueai0>0,entoncespodemosdenirlasucesion xk,talquexk=47(0, 0, ..., k, 0, ..., 0), donde el valor de k corresponde a la componente i0, y obtenerque [[xk[[ +.Luego,setienequelimk+f(xk) = limk+aTxk= limk+ai0k = .Deamboscasos,concluimosquelafuncionfnoescoerciva.Ejercicio3.10Estudielacoercividaddef(x) = aTx + [[x[[2,donde > 0yx RnSolucion. Por la desigualdad de Cauchy-Schwartz se tiene que f(x) ([[x[[ [[a[[)[[x[[.Sea xk una sucesion tal que limk[[xk[[ = +. De aqu y de la desigualdad anteriorsetieneque limkf(xk) = +.3.5 EjerciciosPropuestos1. ElproblemadelacarteradeinversiondelEjemplo2.4consisteenresolvermin_f(x) :n

i=1xi= 1, G n

i=1xiRi, 0 xi Si_,dondef(x) =f(x1, ..., xn) =

ni=1x2i2i+ 2

n1i=1

nj=i+1xixjij. Vericar si elproblematienesolucion.2. ElproblemadetransportedelEjemplo2.7consisteenresolver:min_n

j=1n

i=1cijxij:n

j=1xij= ai,m

i=1xij= bj, xij 0_.Vericarsielproblematienesolucion.3. Considereelproblema:opt_xTAx : |x| = 1_.Vericarsielproblematienemaximosymnimos.4. Estudielaexistenciadesolucionesdelproblema:min_f(x1, x2) = ln(x21 + x22) : (x1, x2) R2_.485. Una empresa produce dos bienes en competencia perfecta, siendo p1 y p2 sus preciosrespectivamente. Lafunciondecostodelaempresabienedadopor:c(x1, x2) = 2x21 + x1x2 + 2x22,dondex1, x2sonlascantidadesproducidasporel bien1y2respectivamente. Elobjetivoesmaximizarlafuncionbenecio:b(x1, x2) = Ingresos Costos = (p1x1 + p2x2) (2x21 + x1x2 + 2x22).Aselproblemadeoptimizacionesmaxf(x1, x2) = (p1x1 + p2x2) (2x21 + x1x2 + 2x22) ; x1 0, x2 0.Analizarsielproblematienesolucion.6. Se quiere construir una cisterna metalica abierta para agua, conuntriangulorectangulocomobase ylados verticales. Si el volumende lacisternadebe serde2m3, obtenerel problemadeoptimizaciontal quelacisternatengalamenorarea. Elproblematienesolucion?49Captulo4CondicionesdeOptimalidaddeProblemasDiferenciables4.1 ProblemassinRestriccionesApesar de que en la practica la gran mayoria de problemas de optimizacion son restric-tos, el estudio de tecnicas para optimizacion irrestricta es importante por varias razones,unadeellas es quelamayoradealgoritmos resuelvenproblemas restrictos transfor-mandolosenunasucesiondeproblemasirrestrictos, lasegundaesquelastecnicasdeoptimizacionirrestrictapuedenserextendidasdemaneranatural pararesolverproble-masconrestricciones.Enestaseccionconsideraremoselproblemairrestrictodeoptimizacionminf(x) : x Rn (4.1)dondefesunafunciondenidaenelespacioeuclidiano Rn.Teorema4.1(CondicionNecesariadePrimerOrden) Sea f: RnR una funci ondiferenciableenx. Sixesunpuntodemnimolocal del problema(4.1),entoncesf(x) = 0.Demostracion. Supongamosqued= f(x) ,=0. Denamosh(t)=f(x(t)), donde50x(t) = xtd.Yaquefesdiferenciableenxsetienequehesdiferenciableen0yh(t) = h(0) +th(0) +o(t),donde limt0o(t)t=0. Comoxesunmnimolocal def, entoncest=0esmnimolocal deh, as, existe >0tal queh(t) h(0) 0, paratodot (, ). Usandoesteresultadoenlaecuacionanterior, obtenemosh(0) +o(t)t0, paratodot (0, ).Tomando lmite cuando t converge para cero se obtiene que h(0) 0. Usando la regla delacadenaconcluimosque, 0> |f(x)|2= f(x)Td 0, implicandoque0>0,loqueesunacontradiccion. Porlotantoobtenemoselresultadodeseado.Ejemplo4.1Seaf : R2Rtal quef(x1, x2)=x21 + x22, el puntox=(0, 0)esunmnimoglobal ycumple f(x) = 0.Observacion4.1Lacondici on f(x)=0esnecesariaperonosucienteparacarac-terizarmnimos de fpues existen funciones donde el gradiente de lafunci on se anulaenalg unpuntosinembargotal puntonoesunmnimoglobal nilocal. Enefecto,considerelafuncionf(x1, x2)=x21 x22, el punto x=(0, 0)cumple f( x)=0peroestenoesmnimoglobalnilocalyaqueencualquiervecindadde xlafuncionftomavaloresmay-oresymenoresque0 = f(0, 0)(verFigura4.1). Paraotroejemplo,considerelafunci onf(x1, x2) = x21 x22, el puntox= (0, 0)satisfacelacondici on f(x) = 0peroxnoesunmnimo(esmaximoglobal).Denicion4.1Dadof : RnR, unpunto x Rnesllamadopuntocrticooesta-cionariosi f( x) = 0.Observacion4.2Del Teorema4.1concluimosqueloscandidatosamnimosdel pro-blemairrestrictoseobtienenresolviendoel sistema f(x) = 0.Teorema4.2(CondicionNecesariadeSegundoOrden) Sea f : RnRunafunciondosvecesdiferenciableenx. Si xesunpuntodemnimolocal del problema(4.1),entonces f(x) = 0y 2f(x)essemidenidapositiva.51x3x2x1f(x1, x2) = x21x21Figura4.1: Elpunto x = (0, 0)satisface f( x) = 0peronoesmnimonimaximo.Demostracion. Que f(x) = 0 es consecuencia del Teorema 4.1, por eso solo probare-mosqueparatodod Rn:dT2f(x)d 0.Ladesigualdadesobviasid = 0. Poreso,sead ,= 0ydenamosh(t) = f(x(t)),dondex(t)=x td. Yaquef esdosvecesdiferenciableenx, tenemosquehesdosvecesdiferenciableen0yporlaaproximaciondeTaylordesegundoordentenemosh(t) = h(0) +th(0) +t22 h(0) +o(t2),donde limt0o(t2)t2=0. Comoxesunmnimolocal, t=0esmnimolocal deh, as,existe> 0talqueh(t) h(0) 0,paratodot (, ). Usandoesteresultadoenlaecuacionanteriorresultath(0) +t22 h(0) +o(t2) 0, paratodot (, ).Comoh(0) = f(x)Td = 0yh(0) = dT2f(x)d,tenemosquedT2f(x)d + 2o(t2)t2 0, paratodot (0, ).Tomandolmitecuandotconvergeparacerotenemoselresultadodeseado.Ejemplo4.2Apliquemos el resultado del teoremaanterior a la funci onf(x1, x2) =x21 x22. El punto x=(0, 0)cumple f( x)=0sinembargolahessiana 2f(x)noes52semidenidapositiva,porlotantousandoelTeorema4.2tenemosque xnoesunpuntodemnimolocal.Observacion4.3La condicion dada en el Teorema 4.2 es s olo necesaria y no suciente.Enefecto, considere la funcionf(x) =x3, el punto x =0 satisface f( x) =0 yf( x) = 0 0peronoesmnimolocal yporlotantotampocoesmnimoglobal.Paradarunacondicionsucientedemnimolocalnecesitamoslasiguientedenicion.Denicion4.2(Mnimolocalestricto) Seaf : RnRunafunci on. Unpunto x Rnesunpuntodemnimolocal estrictodef si existe>0tal quef( x) 0talquef(x) f(x), paratodox B(x, ) X. (4.4)Porlaconexidaddelabola, existe1 (0, )tal que(t) B(x, ) X, paratodot [0, 1]. As, de(4.4)tenemosque(0) (t), paratodo t [0, 1). Enparticular,(0) (t), paratodot (0, 1). Luego,(t)(0)t 0, para todo t (0, 1). Como esderivableencerotomandolmitecuandotvaparaceroyusandolaregladelacadenatenemos f(x)T(0) = (0) 0.Corolario4.1Si xesunpuntointeriordeXtal quexesunminimizadorlocal de(4.3)yfesdiferenciableenx,entonces f(x) = 0.Prueba. Por contradiccion, supongamos que f(x) ,= 0. Como x es un punto interior,existe > 0 tal que B(x, ) X. Sea 1= /(2 |f(x)|) y deniendo : [0, 1] Rntal que (t) = xtf(x), tenemos que (0) = x, (0) = f(x) y (t) B(x, ) X. As, es una curva en Xde clase C1pasando por xy como xes un mnimo localentoncesporelTeorema4.4tenemos f(x)Tf(x) 0.Estoimplicaque0 f(x)Tf(x) = |f(x)|2< 0,56loqueesunacontradiccion. Porlotantoobtenemoselresultadodeseado.Ejemplo4.5Considere el problema minf(x) : x > 0 donde f: RnR es diferencia-bleen Rn. Porlacaractersticadelproblemaelpuntodemnimolocaloglobal,siexiste,esunpuntointeriorde Rn++,entoncesporCorolario4.1lacondici ondeprimerordenesf(x) = 0.Observacion4.6Siel puntodemnimolocal noesunpuntointerior,el resultadodelCorolario 4.1 puede ser falso. En efecto, considere por ejemplo la funci on f(x) = (x+2)2yX=[0, 1], el puntox=0esunmnimoglobal (noesunpuntointeriordeX)yf(0) = 4 ,= 0.Observacion4.7Lacondici ondel Corolario4.1noessuciente. Enefecto,considerelafuncionf(x) =x3yX=[1, 1]. El puntox=0perteneceal interior deXysatisfacef(0) = 0peronoesunmnimolocal.Teorema4.5(CondicionNecesariadeSegundoOrden) Sea xunminimizadorlocal de(4.3)yfdosvecesdiferenciableenx.1. Paracadacurva: [0, ] XdeclaseC1partiendodexseobtienef(x)T(0) = (0) 0,donde(t) = f((t)).2. Si : [0, ] XesunacurvaenXdeclaseC2partiendodexy(0)=0,entonces(0) 0.Demostracion. Elitem1esdadoporelTeorema4.4.Probaremoselitem2. Cuando(0) = 0tenemosporeldesarrollodeTaylor(t) = (0) +12(0)t2+ o(t2),donde limt0o(t2)t2= 0. Comoxesunminimizadorlocalexiste1 (0, )talque(t) (0) =12(0)t2+ o(t2) 0, paratodot (0, 1).Dividiendo por t2y tomando lmite cuando t va para cero tenemos nuestro resultado.57Denicion4.4Dadox X, diremosqueesunacurvaenXdeclaseCkpasandoporxsi: [, ] X, > 0,(0) = xy Ck[, ].Lema4.1Si x Xesunminimizadorlocal de(4.3), esunacurvaenXdeclaseC1pasandoporxyfdiferenciableenx,entonces f(x)T(0) = 0.Prueba. Denamoslassiguientescurvas1:[0, ] Xy2:[0, ] Xdadaspor1(t)=(t)y2(t)=(t). Asobtenemosque1y2partendexycomoxesunmnimolocal,usandoelTeorema4.4tenemosf(x)T(0) = f(x)T1(0) 0,f(x)T((0)) = f(x)T2(0) 0.Deambasdesigualdadesobtenemoselresultadodeseado.Corolario4.2Sifesdosvecesdiferenciableenx,xesunpuntointeriordeXyunminimizadorlocal de(4.3),entonces f(x) = 0y 2f(x)essemidenidapositiva.Prueba. Laprimeraparte fue probadoenel Corolario4.1, probaremos lasegundaparte. Comoxes unpuntointerior deX, existe >0tal queB(x, ) X. Sead Rn(arbitrario)diferentedeceroydenamoslacurva:_2d,2d_Rntalque(t) = x +td. Tenemos que es una curva de clase C1pasando por xy que (t) X.Por el lema 4.1 tenemos que (0) = f(x)Td = 0, donde (t) = f((t)). Usando ahorael Teorema 4.5 tenemos que dT2f(x)d = (0)2f(x)(0) = (0) 0, esto es lo quedeseabamosprobar.Observacion4.8El recproco del Corolario 4.2 es falso. En efecto, considere la funci onf(x)=x3yX=(1, 1), el puntox=0satisfacef(0)=0yf(0)=0 0, peronoesunpuntodemnimolocal.Denicion4.5(Mnimolocalestricto) Seaf : X RnRunafunci on. Unpunto x Rnes un mnimo local estricto de fsobre Xsi existe > 0 tal que f( x) < f(x),paratodox B( x, ) X, x ,= x.58Teorema4.6(CondicionSucientedeSegundoOrden) Si f : XRes unafunciondos veces diferenciableenunpuntointerior xdeX, tal que f(x) =0y2f(x)esdenidapositiva, entoncesxesunminimizadorlocal estrictodel problema(4.3).Demostracion. Analogoalcasoirrestricto.Observacion4.9El recprocodel teoremaanterior es falso. Enefecto, considere lafuncionf(x) = x4yX= (2, 2),elpuntox= 0esunpuntointeriordemnimoglobalestrictosinembargosetienequef(0) = 0noespositivo.Observacion4.10Consideremosel siguienteproblemaminf(x) : x U,dondeUes unconjuntoabiertodeRn. Usandolos corolarios anteriores tenemos lassiguientescondicionesdeoptimalidadparaproblemasrestrictosaconjuntosabiertos:1. Condici onnecesariadeprimerordensobreabiertos: sixesunmnimolocaldefenUyfesdiferenciableenxentonces f(x) = 0.2. Condici onnecesariadesegundoordensobreabiertos: sixesunmnimolocal defenUyfesdosvecesdiferenciableenx,entonces 2f(x) _ 0.3. Condici onsucientedesegundoordensobreabiertos: si el punto x Usatifacef( x)=0y 2f( x) 0, entonces, xesunpuntodemnimolocal estrictodefsobreU.Concluimosquelascondicionesdeoptimalidaddeproblemasrestrictossobreconjuntosabiertossonidenticasalascondicionesdeoptimalidaddeproblemassinrestricciones.4.3 RestriccionesdeIgualdadConsideremoselproblemadeoptimizacionconrestriccionesdeigualdad(p)minf(x) : h(x) = 059dondeh: RnRmesunafunciontal queh(x)=(h1(x), h2(x), . . . , hm(x)), conhi:RnR. PoniendoenelformatogeneraltenemosqueX= x Rn: h(x) = 0.Denicion4.6Seax X, llamamosconjuntotangenteaXenel puntox(denotadopor TxX) al conjunto de los vectores tangentes a las curvas en Xpasando por x, es decir,TxX= v Rn: existe : [, ] X, C([, ])tal que(0) = x y (0) = vTxXX 0 x = (0)(0) = v(t)Figura4.2: GracodelconjuntotangentedeX.Usaremoslasiguientenotacionh(x) =__h1x1(x)h1x2(x) . . .h1xn(x)h2x1(x)h2x2(x) . . .h2xn(x)............hmx1(x)hmx2(x) . . .hmxn(x)__=__h1(x)Th2(x)T...hm(x)T__,donde hi(x)Tdenotalatranspuestadel vectorcolumna hi(x).Podemos relacionar TxXcon el n ucleo del Jacobiano de h, denotado por Ker(h(x)).Lema4.2Paratodox X,Tx(X) Ker(h(x)).Prueba. Seav TxX, entoncesexiste:[, ] Xtal que(0)=xy(0)=v.Como(t) X,paratodot [, ],entonces,h((t)) = 0. Derivandousandolaregladelacadena, tenemosqueh((t))(t)=0. Evaluandoent=0yusando(0)=vtenemosqueh(x)v= 0. As,v Ker(h(x)).60Observacion4.11Elrecprocodellemaanteriornoesverdadero. Enefecto,consider-emosporejemploh(x1, x2) = x1x2,entoncesX= (x1, x2) R2: h(x1, x2) = x1x2= 0.Tomandox=(0, 0) setieneT(0,0)X= (v1, v2) R2: v1v2= 0. Enefecto, seav T(0,0)Xentoncesexiste:[, ] Xtal que(0)=(0, 0) y (0)=v. Deaqu setieneque1(t)2(t)=0, paratodo[, ]. Loanteriorimplica1(t)=0 o2(t)=0,paratodot (, ).Tomando enparticular para t =0 obtenemos 1(0)2(0) =v1v2=0, es decir que1(0)2(0) = 0. Recprocamente,seav= (v1, v2) R2talquev1v2= 0. Dado > 0de-namos: [, ] R2: (t) = (0, 0) +t(v1, v2),entonces(0) = (0, 0),(0) = (v1, v2)y1(t)2(t) = (tv1)(tv2) = 0. As,(t) Xyporlotantov= (v1, v2) T(0,0)X.Por otrolado, Ker(h((0, 0))) = (v1, v2) R2: 0v1 + 0v2= 0=R2. As obtenemosqueKer(h((0, 0))) , T(0,0)X.Paratenerlaigualdadnecesitamosintroduciralgunashipotesissobreh.Denicion4.7Decimosquex X= x Rn: h(x) = 0esunpuntoregular, si elrangodeh(x)esigual am(h1(x), . . . , hm(x)eslinealmenteindependiente).Lema4.3SeaA Rmn,m < n,conrangomentonces,AATesinvertible.Prueba. Seav =(v1, v2, . . . vn)Rmtal que (AAT)v =0, probaremos que v =0. Como(AAT)v =0, entonces ATvKer(A). Usandoel resultado(deAlgebraLineal) Ker(A) =(Im(AT)), tenemos ATv_Im(AT)_. Luego, obtenemos que(ATv)T(ATv) = 0. DenotandoAcomosigueA =__AT1AT2...ATm__,tenemosqueATv=v1A1 + v2A2 + . . . + Amvm=0. ComoA1, . . . , Amsonlinealmenteindependientessetienequev= 0.Teorema4.7SeanX= x Rn: h(x) = 0, h Ck(Rn), x Xunpuntoregular,entoncesTxX= Ker(h(x)).61Demostracion. LainclusionTxXKer(h(x)) (sinlahipotesis depuntoregular)fueprobadoenel lema4.2. Probaremosahoralaotrainclusion. Seav Ker(h(x)),entoncesh(x)v= 0. (4.5)Consideremoselsiguientesistemadeecuaciones(engeneralnolineal)(t, u) = h(x + tv + h(x)Tu) = 0Paraxyv jos, estesistemaes de mecuaciones ym + 1incognitas ycumplenlassiguientescondicionesi) i Ck(R Rm), i = 1, . . . , m,dondei(t, u) = hi(x + tv +h(x)Tu).ii) Tomando(t, u) = (0, ),dondedenotaelvectornulo,tenemosque(0, ) = h(x) = 0iii) LamatrizJacobianade(conrespectoau)evaluadoenelpunto(0, )es(0, ) = h(x)h(x)T,elcualesnosingularyaqueh(x)tienerangom(verLema4.3).Luegoporel teoremadelafuncionimplcita(verTeorema1.6), existe Ckdenidoen[, ]talque (0) = , y(t) = (t, (t)) = h_x + tv + h(x)T (t)_= 0,paratodot [, ].Derivandoyevaluandoent = 0,tenemos(0) = h(x)(v + h(x)T (0)) = 0. Usando(4.5),laecuacionanteriorsereduceah(0) = (h(x)h(x)T) (0) = 0. Comoh(x)h(x)Tesinvertiblesetieneque (0)=. Ahoradenamos:[, ] Rntal que(t)=x+tv +h(x)T (t). De la denicion anterior tenemos que (0) = x, (t) Xy (0) = v.As,v TxXydeestamaneraKer(h(x)) TxX,porlotantoseobtieneelresultado.Teorema4.8Sixesunminimizadorlocal regulardel problemaminf(x) : h(x) = 0,entonces f(x)Ker(h(x)).62Demostracion. Seav Ker(h(x))(arbitrario). Comoxesunpuntoregular, porTeorema4.7tenemos que vTxXyas existe : [, ] Xtal que (0) =xy(0) =v. Aplicandoel Lema4.1tenemos f(x)Tv =0. As obtenemos quef(x)Ker(h(x)).Denicion4.8Considereel problemaconrestriccionesdeigualdad(p) minf(x) : h(x) = 0.DenimoslafunciondeLagrangeofuncionLagrangeana, conrespectoal problema(p),comoL : RnRm RdadoporL(x, ) = f(x) +

mi=1ihi(x),donde1, . . . , m RsonllamadosmultiplicadoresdeLagrange.DenotaremosxL(x, ) = f(x) +m

i=1ihi(x)2xxL(x, ) = 2f(x) +m

i=1i2hi(x)Teorema4.9(CondicionNecesariadeLagrange) Si x Rnesunmnimolocalregular del problema (p), entonces existen unicos 1, 2, . . . , m R tal que xL(x, ) =0.Demostracion. ProbemoslaexistenciadelosmultiplicadoresdeLagrange. Comoxes un mnimo local regular, por el Teorema 4.8 obtenemos f(x)Ker(h(x)). Del re-sultadodeAlgebraLineal,Ker(h(x)) = (Imh(x)T),tenemos f(x) Imh(x)T.Luegoexisten1, 2, . . . , m Rtalquef(x) = h(x)T=m

i=1hi(x)i. (4.6)Deniendoi= i , paratodoi =1, 2 . . . , m, obtenemos xL(x, ) = f(x) +

mi=1ihi(x) = 0. Ahora probaremos la unicidad. Supongamos que existe otro vector ,= talquef(x) = h(x)T. (4.7)63De (4.6) y (4.7) tenemos h(x)T( ) = 0, esto es,

mi=1(ii)hi(x) = 0. Comohi(x) son linealmente independientes obtenemos que i= ipara todo i = 1, . . . , n,loqueesunacontradiccion. Porlotantoes unico.Observacion4.12Sinlahip otesisderegularidaddelpuntodemnimolocaltambienesposibleprobarlaexistenciadelosmultiplicadoresdeLagrangeparaunaclaseespecialdeproblemasdeoptimizacioncomoveremosenel siguienteresultado.Teorema4.10Sixesunmnimolocal del problemaminf(x) : Ax = b,entonces,existen1,2, . . . ,m Rtal que xL(x,) = f(x) + AT = 0.Demostracion. Seanv Ker(A)y>0. Denamoslacurva(t)=x+ tv, cont [, ]. TenemosqueA((t))=A(x + tv)=Ax + tAv=b, estoes, (t) X=x Rn: Ax = b. Como(0) = xy(0) = v,podemosdecirqueesunacurvaquepasa por xde clase C1. As por lema 4.1, tenemos f(x)Tv= 0. Como ves arbitrarioentonces f(x)Ker(A). DebidoqueKer(A) = (ImAT)tenemos f(x) ImAT.Luego existen 1, 2, . . . , m R tal que f(x) = AT . Deniendoi= i,para todolosi = 1, 2 . . . , m,obtenemos xL(x,) = f(x) + AT.Observacion4.13Losresultadosdelosteoremas4.10y4.9,nosdicequeparaobtenercandidatos a solucion del problema de minimizacion con restricciones de igualdad debemosresolverel siguientesistema(m +n) (m + n)___xL(x, ) = f(x) +m

i=1ihi(x) = 0h(x) = 0.Lospuntosqueresuelvenestaecuaci onsonllamadospuntoscrticosoestacionariosocandidatosasoluciondel problema(p).Ejemplo4.6Considere el problema minf(x1, x2) = x21+12x22: x21+x22= 1. La funci onobjetivo fes continua y el conjunto que dene las restricciones del problema es compacto,64as el problematieneunmnimoglobal. Usandolaobservacionanteriorhallaremosloscandidatos a solucion. La funcion Lagrangeana es L(x1, x2, ) = (x21+12x22)+(x21+x221)ysugradienteconrespectoalasvariables(x1, x2)esxL(x1, x2, ) =__2x1 + 2x1x2 + 2x2__As,paraobtenerloscandidatosasoluciondebemosresolverel siguientesistema___x1 + x1= 0x2 + 2x2= 0x21 + x22= 1.Six1 ,= 0yx2 ,= 0entoncesdelaprimeraysegundaecuaci on,respectivamente, = 1y = 12, lo que no puede suceder, as x1= 0 x2= 0. Si x1= 0, entonces de la terceraecuaci onx2= 1,loqueimplicaque = 12. Six2= 0,entoncesdelaterceraecuaci onx1= 1,loqueimplicaque = 1,porlotantolospuntoscandidatosasolucionson(0, 1), (0, 1), (1, 0), (1, 0),dondelosdosprimerospuntosesconrespectoalmultiplicador = 12ylosdos ultimosconrespectoa = 1, verFigura4.3. Observemostambienqueestospuntossonregu-lares, as el mnimoglobal es unodeestos puntos. Debidoquelos puntos candidatosformanunconjunto nito podemos inmediatamente encontrar el mnimo global sim-plementeevaluandolafuncionobjetivof ycomparandosus valores. Enefecto, comof(0, 1) =12, f(0, 1) =12, f(1, 0) = 1yf(1, 0) = 1,setienequelospuntosdemnimoglobal son(0, 1)y(0, 1),verFigura4.4.Teorema4.11Supongamosquef : RnRyh: RnRmsonfuncionesdosvecesdiferenciablesenunminimizadorlocal regularxdel problema(p)y1, 2, . . . , m Rson los multiplicadores de Lagrange dado en el Teorema 4.9, entonces vT2xxL(x, )v 0,paratodov Ker(h(x)).65(0, 1)(1, 0)(1, 0)(0, 1)Figura4.3: Puntoscandidatosamnimo.Demostracion. Del Teorema4.9tenemosque f(x) + h(x)T=0. Tomemosunv Ker(h(x)), porel Teorema4.7existeunacurvaenXdeclaseC2pasandoporx((0) =x)tal que(0) =v, as tenemos(0) Ker(h(x)). Denamosahora(t) =f((t)). Porel Lema4.1setiene(0) = f(x)T(0) =0, luegousandoelTeorema4.5(0) = (0)T2f(x)(0) +f(x)T(0) 0. (4.8)Como(t) Xsetienei(t) := ihi((t)) = 0. Tenemosasparatodot (, +)i(t) = ihi((t))T(t) = 0, yi(t) = i(t)T2hi((t))(t) + ihi((t))T(t) = 0Sumandodei = 1hastamyevaluandoent = 0tenemosm

i=1i(0) = (0)Tm

i=1i2hi(x)(0) +Th(x)(0) = 0 (4.9)Sumando(4.8)y(4.9)sesigue(0)T_2f(x) +m

i=1i2hi(x)_(0) +_f(x) + h(x)T_(0) 0Finalmente, usandolacondicionque f(x) + h(x)T=0tenemosel resultado.66(0, 1)(0, 1)Figura4.4: Puntosdemnimoglobal.Teorema4.12Supongamosquef : RnRyh: RnRmsonfuncionesdosvecesdiferenciablesenx. Six X= x Rn: h(x) = 0entoncesi. xL(x,) = 0,paraalgunos1,2, . . . ,m R.ii. vT2xxL(x,)v> 0,paratodov Ker(h(x)), v ,= 0.entoncesxesunmnimolocal estrictodefenX.Demostracion. Por contradiccion,supongamos que xno es un punto de mnimolocalestrictodefenX,entoncesexisteunasusecion xk X,xk,= x,talquexk xyf(xk) f(x),paratodok IN.DelaaproximaciondeTaylordesegundoordenydeladesigualdadanteriortenemos0 f(x)T(xkx) +12(xkx)T2f(x)(xkx) + o(|xkx|2), (4.10)donde limxkxo(xkx

2)xkx

2= 0.Deformaanalogaparacadahi,i = 1, ..., m,setiene0 = hi(xk) hi(x) = hi(x)T(xkx) + 12(xkx)T2hi(x)(xkx) +(|xkx|2),67donde limxkx(xkx

2)xkx

2= 0.Multiplicandoporilaigualdadanteriorysumandodei = 1hastamlaecuacionanteriorobtenemos0 =m

i=1ihi(x)T(xkx)+m

i=112(xkx)Ti2hi(x)(xkx)+o(|xkx|2) (4.11)Sumando(4.10)y(4.11),usandolahipotesisidelteoremaydividiendopor |xkx|2tenemos0 12_xkx|xkx|_T2xxL(x,)_xkx|xkx|_+O(|xkx|2)|xkx|2. (4.12)Observemosquelasucesiondk =_xkx|xkx|_es acotada, de aqu existe una subsucesion dkj que converge a un puntod ,= 0. Tomandoenparticulark = kjen(4.12)yhaciendotenderj +tenemosdT2xxL(x,)d 0 (4.13)Porotrolado,comoxk, x X,xk,= xyporlaaproximaciondeprimerordensetiene0 = hi(x)Tdk+o(|xkx|)|xkx|, i = 1, ..., mTomandok=kjyj tenemosque hi(x)Td=0, i =1, 2, ..., m; estoes,d Ker(h(x)).Finalmente, deloanterioryde(4.13)llegamosaunacontradiccionconlahipotesisiidelteorema.Ejemplo4.7Vimos en el Ejemplo 4.6 que los puntos candidatos a solucion del problemadado eran (0, 1), (0, 1), (1, 0), (1, 0), donde los dos primeros puntos es con respecto almultiplicador = 12y los dos ultimos con respecto a = 1. Como la unica restriccionesh(x1, x2) = x21+x221tenemos queh(x1, x2) = 2(x1x2). Entonces podemosvericarque Ker(h(x1, x2)) = (v1, v2) R2: x1v1+x2v2= 0 y la matriz hessiana de la funci ondeLagrangeest adadopor2xxL(x1, x2, ) =__2 + 2 00 1 + 2__Analizaremosencadapuntocandidatoasolucion.68i. Para x = (0, 1)conmultiplicador = 12tenemosKer(h(0, 1)) = (v1, v2) R2: v2= 0,2xxL(0, 1, ) =__1 00 0__Luego,paratodov= (v1, v2) Ker(h(0, 1)), v ,= (0, 0),tenemosquev1 ,= 0yasvT2xxL(0, 1, )v= v21> 0,yaplicandoel Teorema4.12concluimos que el punto(0, 1) es unmnimolocalestricto.ii. Para x=(0, 1) conmultiplicador = 12tenemos enformaanalogaal casoanteriorque(0, 1)esunmnimolocal estricto.iii. Para x = (1, 0)conmultiplicador = 1tenemosKer(h(1, 0)) = (v1, v2) R2: v1= 0,2xxL(1, 0, ) =__0 00 1__As, paratodov=(v1, v2) Ker(h(1, 0)), v ,=(0, 0), tenemosquev2 ,=0ysetienevT2xxL(0, 1, )v= v22< 0,luegoaplicandoel Teorema4.11ysiendo(1, 0) unpuntoregularconcluimosque(1, 0)noesunmnimolocal.iv. Similaral casoanterior.Observacion4.14Consideremosel problemademaximizaci on:(P) maxf(x) : h(x) = 0Comovimosanteriormenteesteproblemaesequivalentea(P) minf(x) : h(x) = 069LafunciondeLagrangeysusderivadassonL(x, ) = f(x) + Th(x)xL(x, ) = f(x) +m

i=1ihi(x)2xxL(x, ) = 2f(x) +m

i=1i2hi(x)Usandolosteoremas4.9,4.11,4.12,setienequelascondicionesdeoptimalidadparael problema(P)son:1. Condici onnecesariade primer orden: Si xes unmaximolocal regular de (P)entoncesexisten unicos 1, 2, . . . , m Rtal que f( x) +m

i=1 ihi( x) = 0.Enefecto, como xes unmaximolocal regular, entonces xes unmnimolocalregularde(P). Deaqu, usandoel Teorema4.9, existen1,2, . . . ,m Rtalque f( x) +m

i=1ihi( x) = 0. Deniendo i= i,tenemosel resultado.2. Condici onnecesariadesegundoorden: Si xes unmaximolocal regularde(P)entoncesexisten unicos 1, 2, . . . , m Rtalquelamatriz 2f( x) +m

i=1 i2hi( x)es semidenidanegativasobre Ker(h( x)). Enefecto, si xes unmaximolocalregular de (P) entonces x es un mnimo local regular de (P) entonces, por Teorema4.11 aplicado al problema (P), la matriz 2f( x) +m

i=1i2hi( x), es semidenidapositivasobreKer(h( x)), yportanto 2f( x) +m

i=1i2hi( x), essemidenidanegativasobreKer(h( x)). Deniendo i= i, parai =1, . . . , msetieneelresultado.3. Condici onsucientedesegundoorden: Si x X= x Rn: h(x) = 0satisface(a) estacionaridaddel Lagrangiano xL( x, ) = f( x) +m

i=1ihi( x) = 0.(b) laHessianadelafunciondeLagrange 2xxL( x, )= 2f( x) +m

i=1i2hi( x),esdenidanegativasobreel Ker(h( x))0.entonces, xes unmaximolocal estrictodef sobreX. Enefecto, de(a) y(b)tenemos que f( x)+m

i=1(i)hi( x) = 0, y la matriz 2f( x)+m

i=1(i)2hi( x)70es denida positiva sobre Ker(h( x))0, luego aplicando el Teorema 4.12, tenemosque xesunmnimolocal estrictode f, loqueesequivalentea xesunmaximolocal estrictodefenX.Observacion4.15Basados en la observacion anterior y la Observaci on 4.13, con-cluimosqueparaobtenercandidatosdemnimoymaximodeunmodelodeoptimizacionconrestriccionesdeigualdaddebemosresolverel siguientesistema(m+ n) (m +n)___xL(x, ) = f(x) +m

i=1ihi(x) = 0h(x) = 0.Ejemplo4.8Comounaaplicaci ondelosresultadosprevios,considereel problemaoptf(x1, x2) = x21 +12x22: x21 + x22= 1.Por el Ejemplo4.6ylaobservacionanteriorobtenemos quelos candidatos amnimoymaximoson (0, 1), (0, 1), (1, 0), (1, 0), dondelosdosprimerospuntosest anaso-ciadosal multiplicador= 12ylosdos ultimosa= 1. Yavimosenel ejemplo4.7que(0, 1)y(0, 1)sonlos unicosmnimoslocalesestrictosycomotienenel mismovalorentonces, estossonmnimosglobales. Ademaspodemosprobar, usandolascondi-cionessucientesdesegundoordenparamaximizaci on, quelospuntos(1, 0)y(1, 0)sonmaximoslocalesestrictosycomotienenel mismovalorobjetivo,entoncesellossonmaximosglobales.Ejemplo4.9Considereel problemadeoptimizacionminf(x1, x2, x3) = x21 +12x22 +13x23: x21 + x22 + x23= 1,x1x2= 0El problematienesolucionpuesfescontinuayel conjuntoquedenelasrestriccionesescompacto. Hallaremoslasolucionusandolascondicionesdeoptimalidaddeprimerysegundoorden. LafunciondeLagrangeesL(x1, x2, x3, 1, 2) = x21 +12x22 +13x23 + 1(x21 +x22 +x231) +2x1x271Lasecuacionesdeprimerordenquedebesatisfacerel puntodemnimoson___2x1 + 21x1 + 2x2= 0x2 + 21x2 + 2x1= 0(2/3)x3 + 21x3= 0x21 +x22 +x23= 1.x1x2= 0.Six2 ,= 0,entoncesx1= 0ylasecuacionessereducena___2x2= 01 + 21= 0(2/3)x3 + 21x3= 0x22 + x23= 1.dedondeobtenemoslospuntos(0, 1, 0)y(0, 1, 0)con1= 12y2=0. Si x1 ,=0,entoncesx2= 0ylasecuacionessereducena___1 + 1= 02x1= 0(1/3)x3 + 1x3= 0x21 + x23= 1.Resolviendoelsistema,obtenemoslospuntos(1, 0, 0)y(1, 0, 0)con1= 1y2= 0.Si x1=x2=0, entoncesx3=1 x3= 1, con1= 13y2 R. Luegolospuntoscandidatosasolucionparaestecasoson(0, 0, 1)y(0, 0, 1)con1= 13y2 R. Delostrescasosanalizamosconcluimosquelospuntoscandidatosamnimodel problemasoni) (0, 1, 0)y(0, 1, 0)con1= 12y2= 0.ii) (1, 0, 0)y(1, 0, 0)con1= 1y2= 0.iii) (0, 0, 1)y(0, 0, 1)con1= 13y2 R.72Como segunda etapa, analizaremos la condici on de segundo orden. La matriz hessianadelafunciondeLagrangees2xxL(x1, x2, x3, 1, 2) =_____2 + 212021 + 2100 023+ 21_____yKer(h(x)) =___(v1, v2, v3) :x1v1 + x2v2 + x3v3= 0x2v1 + x1v2= 0___Analizaremostodoslospuntoscandidatosasolucion.a. x = (0, 1, 0)con1= 12y2= 0. Enestecasotenemos2xxL( x, 1, 2) =_____1 0 00 0 00 0 13_____;yKer(h(0, 1, 0))= (0, 0, v3):v3 R. Seav=(0, 0, v3)conv3 ,=0, entoncesvT2xxL( x, 1, 2)v= 13v23< 0,luegoporelTeorema4.11,(0, 1, 0)y(0, 1, 0)nosonmnimosdel problema.b. x = (1, 0, 0)con1= 1y2= 0. Enestecasotenemos2xxL( x, 1, 2) =_____0 0 00 1 00 0 43_____;yKer(h(1, 0, 0))= (0, 0, v3):v3 R. Seav=(0, 0, v3)conv3 ,=0, entoncesvT2xxL( x, 1, 2)v= 43v23< 0, luego por la condici on necesaria de segundo orden,Teorema4.11,(1, 0, 0)y(1, 0, 0)nosonmnimosdel problema.c. x= (0, 0, 1)con1= 13y2cualquiern umeroreal,enestecasotenemos:2xxL(x, 1, 2) =_____432021300 0 0_____y73Ker(h(0, 0, 1)) = (v1, v2, 0) : v1, v2 R = R2Tomandoenparticular2=13tenemosquelamatriz 2xxL(x, 1, 2)esdenidapositiva sobre R2, por lo tanto por la condici on suciente de segundo orden, Teorema4.12, los puntos (0, 0, 1) y(0, 0, 1) sonmnimos locales estrictos del problema(observequeestospuntosnosonpuntosregularesesporesoque2noes unico).4.4 RestriccionesdeDesigualdadConsideremoselproblemadeoptimizacionconrestriccionesdedesigualdad(pd)minf(x) : g(x) 0dondef : RnResunafuncionconvalorreal, g: RnRpesunafunciontal queg(x)=(g1(x), g2(x), . . . , gp(x)), congi: RnRylanotaciong(x) 0signicaquegi(x) 0,paratodoi = 1, 2, . . . , p.Denicion4.9Para cada x X= x Rn: g(x) 0, gi es llamada restriccion activaen xsigi( x) = 0. An alogamentellamamosagirestriccioninactivaen xsigi( x) < 0.Dado xdenotaremosI( x) = i 1, 2, . . . , p : gi( x) = 0 .Ejemplo4.10Consideremosel problemaminx12x2: 2x1 + x2 6; x1 + x2 4; x1 0; x2 0.LaregionviableesdadaporX= (x1, x2):2x1 + x2 6; x1 + x2 4; x1 0; x2 0,cuyagracasemuestraenlaFigura4.5. Enesteproblemag1(x1, x2)=2x1 + x2 6,g2(x1, x2) = x1 + x2 4, g3(x1, x2) = x1yg4(x1, x2) = x2. Dado x = (3, 0),tenemosqueg1(3, 0)=0, g2(3, 0)= 1, g3(3, 0)= 3, g4(3, 0)=0. As g1yg4sonrestriccionesactivaspara(3, 0)yI(3, 0)= 1, 4. Sitomamos x=(0, 4)entoncessepuedevericarfacilmentequeI(0, 4) = 2, 3.746(0, 0)(3, 0)(4, 0)(2, 2)(0, 4)XFigura4.5: Regionviable.Denicion4.10Unpunto x X= x Rn:g(x) 0esllamadopuntoregulardelproblema(pd)si gi( x)iI( x)existenysonlinealmenteindependientes.Lema4.4Si xes unminimizador local del problema(pd), entonces xes unmini-mizadorlocal del problemaminf(x) : gi(x) = 0, i I(x).Prueba. Inmediatodeladeniciondemnimolocal.Lema4.5Si xesunminimizadorlocal regularde(pd)entoncesparacadai I(x),existen unicosi Rtal que f(x) +

iI(x)igi(x) = 0.Prueba. AnalogoalTeorema4.9.Observacion4.16El Lema anterior nos dice que en un punto de mnimo local regular elf(x) es combinacion lineal de los gradientes de las restricciones activas. El siguienteresultadomuestraque lacombinaciondadaes unacombinacionconica(combinacionlineal dondelosescalaressonnonegativos).Teorema4.13(CondiciondeKarush-Kuhn-Tucker) Si xes un mnimo local reg-ulardel problema(pd), f ygi, i I(x), sondiferenciablesenxygi, i / I(x), son75continuasenx,entoncesexisten unicosi R,paratodoi I(x),tal que___f(x) +

iI(x)igi(x) = 0i 0, paratodoi I(x).Demostracion. Porellemaanteriorexisten unicosi Rtalquef(x) +

iI(x)igi(x) = 0. (4.14)Probaremosquei 0,paratodoi I(x). Porcontradiccion,supongamosqueexistek I(x)talquek< 0. DenamosXI(x)= x Rn: gi(x) = 0, i I(x),yXk= x Rn: gi(x) = 0, i I(x), i ,= kyseanTxXI(x)yTxXksus respectivos conjuntos tangentes. Por laregularidaddex, gk(x)noescombinacionlineal delosotrosgradientesderestriccionesactivasenx. Por lotantoexiste yTx(Xk) tal que gk(x)Ty 0ydeniendoel punto(x1, x2) = (2+, 0) donde (0,62) (0, ) tenemos que (x1, x2) B( x, ) y ademasf(2 +, 0) = (2 + 2)2(x25)2< f( x)Corolario4.3Conlaship otesisdel teoremaanteriorysiademasgisondiferenciablesi/ I(x),entoncesexisten unicosi 0,paratodoi = 1, 2, . . . , mtalesque___f(x) +p

i=1igi(x) = 0igi(x) = 0, i = 1, 2 . . . , pi 0, i = 1, 2 . . . , p.7821f(0, 4) = (2, 1)g2(0, 4) = (1, 1)1 g3(0, 4) = (1, 0)Figura4.8: GracadelascondicionesdeKKTenelpunto x = (0, 4).Prueba. Inmediatodelteoremaprevio.Observacion4.18El resultadoanterior nos ofrece unmetodoparaobtener los can-didatosasolucionmediantelasoluciondel sistemaquedenominaremoscondicionesdeoptimalidaddeKKT(Karush-Kuhn-Tucker)___f(x) +

pi=1igi(x) = 0gi(x) 0, i = 1, 2 . . . , pigi(x) = 0, i = 1, 2 . . . , pi 0, i = 1, 2 . . . , p.Lospuntosxqueresuelvenel sistemasonllamadospuntosdeKKT.Ejemplo4.13Consideremosel problemadadoenel Ejemplo4.10,estoes,minx12x2: 2x1 + x2 6; x1 + x2 4; x1 0; x2 0Usaremos el metodo para encontrar los candidatos a soluci on. La funci on de LagrangeesL(x1, x2, 1, 2, 3, 4) = x12x2 + 1(2x1 + x26) +2(x1 + x24) 3x14x2El gradientedelafunciondeLagrangeesxL(x1, x2, 1, 2, 3, 4) = (1 + 21 + 23, 2 + 1 + 24)794X63(3, 3) 3(0, 0)Figura4.9: GracadelaregionviabledelEjemplo4.12.Luegoel sistemaKKTquedaestablecidopor___1 + 21 + 23= 02 +1 + 24= 01(2x1 + x26) = 02(x1 + x24) = 03x1= 04x2= 02x1 +x2 6x1 + x2 4x1, x2 01, 2, 3, 4 0Delaterceraecuaci ontenemosque1=0 2x1 + x2 6=0. Si 2x1 + x2 6=0,llegamos a una contradiccion con el sistema dado, por lo tanto debemos tener que 1= 0.Deaqu,laprimeraysegundaecuaci onsereducen,respectivamente,a23= 1 (4.15)24= 2 (4.16)80f(3, 3)g2(3, 3) = (1, 3)g1(3, 3) = (6, 1)Figura4.10: Gracadelacombinacionconica.De ambas ecuaciones se tiene que 2 ,= 0 (Si 2= 0 entonces 3< 0 el cual contradicelacondici ondenonegatividaddelavariable). Luegodelacuartaecuaci ondel sistemasetienequex1 + x2= 4 (4.17)Tambiensetieneque3 ,=0(puesdelocontrariode(4.15)tendriamos2=1yde(4.16),4= 1 < 0loqueesunacontradiccion). Asdelaquintaecuaci ondel sistemaseobtienequex1=0yde(4.17), x2=4. Usandoesteresultadoenlasextaecuaci ondel sistemaobtenemos4= 0ysubstituyendoen(4.16)setiene2= 2. Finalmentede(4.15), obtenemos 3= 1. Concluimos as que el unico candidato a solucion del problemaes(0, 4)conlosmultiplicadores1= 4= 0,2= 2y3= 1.Teorema4.14Sif,gi,i I(x),sondosvecesdiferenciablesenx,gi,i/ I(x),soncontinuasenxyxesunpuntodemnimolocal regulardel problema(pd), entoncesexisten unicospuntosi 0,i = 1, ..., m,tal que1. f(x) +

iI(x)i gi(x) = 0.2. vT2xxL(x, )v 0,paratodo v Rn: gi(x)Tv= 0,ytodoi I(x),81dondeL(x, ) = f(x) +

pi=1igi(x).Demostracion. Laparte1esunaconsecuenciadel Teorema4.13. Probemoslaparte2.DelLema4.4ydelTeorema4.11tenemosquevT__2f(x) +

iI(x)i 2gi(x)__v 0, v Rn: gi(x)Tv= 0, i I(x).Deniendo= 0, i/ I(x)obtenemosquevT2xxL(x, )v 0, v Rn: gi(x)Tv= 0, i I(x).Teorema4.15Seanf, gi, i I(x), dos veces diferenciables enx. Si xX=x Rn: g(x) 0satisface:i. f(x) +

iI(x)i gi(x) = 0,paraalgunosi 0, i I(x)ii. vT_2f(x) +

iI(x)i 2gi(x)_v> 0,paratodov Rn, v ,= 0 : gi(x)Tv=0,ytodoi I(x).Entoncesxesunmnimolocal estrictodefenX.Demostracion. Por contradiccion,supongamos que xno es un punto de mnimolocalestrictodefenX,entoncesexisteunasusecion xk X,xk,= x,talquexk xyf(xk) f(x),paratodok IN.DelaaproximaciondeTaylordesegundoordenydeladesigualdadanteriortenemos0 f(x)T(xkx) +12(xkx)T2f(x)(xkx) + o(|xkx|2), (4.18)donde limxkxo(xkx

2)xkx

2= 0.Deformaanalogaparacadagi,i I(x),setiene0 gi(xk) gi(x) = gi(x)T(xkx) + 12(xkx)T2gi(x)(xkx) +(|xkx|2),donde limxkx(xkx

2)xkx

2= 0.Multiplicandoporiladesigualdadanteriorysumandoparatodoi I(x)obtenemos0

iI(x)igi(x)T(xkx) +12

iI(x)(xkx)Ti2gi(x)(xkx) + o(|xkx|2)(4.19)82Sumando(4.18)y(4.19),usandolahipotesisidelteoremaydividiendopor |xkx|2tenemos0 12_xkx|xkx|_T__2f(x) +

iI(x)i 2gi(x)___xkx|xkx|_+O(|xkx|2)|xkx|2.(4.20)Observemosquelasucesiondk =_xkx|xkx|_es acotada, de aqu existe una subsucesion dkj que converge a un puntod ,= 0. Tomandoenparticulark = kjen(4.20)yhaciendotenderj +tenemosdT__2f(x) +

iI(x)i 2gi(x)__d 0 (4.21)Porotrolado,comoxk,= xyporlaaproximaciondeprimerordensetiene0 gi(xk) = gi(x)Tdk+o(|xkx|)|xkx|, i I(x)Tomandok = kjyj tenemosquegi(x)Td 0, i I(x) (4.22)Tambiendelaaproximaciondeprimerordenparaftenemos0 f(xk) f(x) = f(x)T(xkx) + +o(|xkx|)Dividiendopor [[xkx[[,tomandok = kjytendiendoj obtenemos:0 f(x)Td.Delahipotesisisetienequef(x)Td =

iI(x)i gi(x)Td,deaqugi(x)Td 0, i I(x) (4.23)De (4.22) y (4.23) se tiene que gi(x)Td = 0, i I(x). Finalmente, de (4.21) llegamosaunacontradiccionconlahipotesisiidelteorema.83Ejemplo4.14Considereel problemamin(x15)2+ (x25)2: x21x2 6, x1 + 3x2 12, x1 0, x2 0Vimosenel ejemplo4.12queel puntox=(3, 3)satisfacelacondici onidel Teorema4.15. ComoI(x) = 1, 2,entoncestenemosque2f(x) +

iI(x)i 2gi(x) =__5 + 2100 5__donde1=8/19, el cual esunamatrizdenidapositivaentodoR2enparticularenelconjunto v R2:v ,=0, gi(x)Tv=0, i=1, 2. As secumpletambienlacondici oniidel Teorema4.15yporlotantox= (3, 3)esunmnimolocal estricto.4.5 RestriccionesMixtasFinalmenteconsideremoselproblemadeoptimizacionnolineal(PNL)___min f(x)h(x) = 0g(x) 0dondeh : RnRmyg: RnRpsonfuncionesdadas.PodemosestablecercondicionesanalogasalTeorema4.13paraelproblema(PNL).De manera similar a los casos anteriores, denimos punto regular del conjunto viable comoun punto donde los gradientes de las restricciones activas son linealmente independientes.Lasdemostracionessonsimplesextensionesdeloscasosvistosanteriormenteesporesosedejacomoejercicioparaellector.Teorema4.16Sixesunminimizadorlocalde(PNL)yademasesunpuntoregular,estoes,h1(x), . . . , hm(x) gi(x) ,i I(x)esunconjuntolinealmenteindependientedondeI(x)= i 1, . . . , p: gi(x)=0,entoncesexisten unicos1, . . . , m Ryi 0paratodoi I(x)tal quef(x) +m

i=1ihi(x) +v

iIigi(x) = 0.84Corolario4.4Asuma las condiciones del teorema anterior y que gison funciones difer-enciablesen x, i I( x), entoncesexisten unicos1, . . . , m Ryi 0paratodoi = 1, . . . , ptal quef(x) +m

i=1ihi(x) +p

i=1igi(x) = 0.Observacion4.19El corolarioanteriornos daunmetodoparaencontrarlospuntoscandidatosasoluciondel problema(PNL). Unpuntocandidatoasolucionesunpuntoxtal queparaalgunosescalares(, )sesatisfacef(x) +m

i=1ihi(x) +p

i=1igi(x) = 0 (4.24)h(x) = 0 (4.25)igi(x) = 0, i = 1, . . . , m (4.26)i 0, i = 1, . . . , mgi(x) 0, j= 1, . . . , qLasn + m + pecuaciones(4.24)-(4.26)formanunsistemanolineal enlasinc ognitasx Rn, Rmy Rp. Lospuntosqueresuelvenestesistemasonllamadospuntosestacionariosde(PNL).Teorema4.17Sixesunpuntoregularyminimizadorlocalde(PNL),Aeslamatrizcuyaslassonlosgradientesdelasrestriccionesactivasenxexcluyendolosgradientesdeaquellasrestriccionesdedesigualdadcuyomultiplicadorescero,entoncesyT2xxl(x, , )y 0 paratodo y ^(A),dondeysonlosvectoresdemultiplicadoresdeLagrangedadosenelTeorema4.16yl(x, , ) = f(x) +m

i=1ihi(x) +p

i=1igi(x).Teorema4.18Siexisten(x, , )satisfaciendolacondici onnecesariadeprimeror-denpara(PNL)yademasyT2xx(x, , )y> 0,85paratodoy ^(A), y ,=0, dondeAeslamatrizcuyaslassonlosgradientesdelasrestricciones activas en xexcluyendo los gradientes de aquellas restricciones de desigual-dadcuyomultiplicadorescero, entoncesxesminimizadorlocal estrictodel problema(PNL).Ejemplo4.15Considereel problemaminf(x1, x2, x3) = x21 +12x22 +13x23: x21 +x22 + x23 1, x1 + x2 + x3= 1/2El problematienesolucionpuesfescontinuayel conjuntoquedenelasrestriccionesescompacto. Hallaremoslasolucionusandolascondicionesdeoptimalidaddeprimerysegundoorden. LafunciondeLagrangeesl(x1, x2, x3, 1, 2) = x21 +12x22 +13x23 + 1(x1 + x2 + x31/2) +1(x21 + x22 + x231)El sistemadeprimerordenquedebesatisfacerel puntodemnimoson___2x1(1 +1) + 1= 0x2(1 + 21) + 1= 0x3((2/3) + 21) +1= 0x1 + x2 +x3= 1/2x21 + x22 +x23 1.1(x21 + x22 + x231) = 01 0.Resolviendoel sistemaobtenemos queel unicopuntocandidatoasoluciones x=(1/2, 1/6, 1/4)con1= 1/6y 1=0. Analizaremosahoralacondici ondesegundoorden.Delasdosrestricciones,tenemosquela unicarestriccionactivaparaelpuntocrticoesh(x) = x1 + x2 + x31/2yporlotantoA = h(x)T= (1 1 1). yas^(A) = v R3: v1 + v2 + v3= 086LamatrizhessianadelafunciondeLagrangees2xxl(x1, x2, x3, 1, 1) =_____2 + 210 00 1 + 2100 023+ 21_____Evaluandoenel punto x = (1/2, 1/6, 1/4)con1= 1/6y 1= 0,tenemos2xxl( x,1, 1) =_____2 0 00 1 00 023_____,queesunamatrizdenidapositivaentodoR3yas enparticularsobre ^(A). Porlotanto x == (1/2, 1/6, 1/4)esunmnimolocal estricto.Ejemplo4.16Considereel problemaminf(x1, x2) = 5x212x1x2 + 5x22: x1 + x2= 1, x1 0, x2 0Hallaremoslospuntosdemnimo. LafunciondeLagrangeesl(x1, x2, 1, 1, 2) = 5x212x1x2 + 5x22 + 1(x1 + x21) 1x12x2,ylascondicionesdeKKTson___10x12x2 + 11= 02x1 + 10x2 + 12= 0x1 + x2= 1x1 0x2 01x1= 02x2= 01 02 087Resolviendo el sistema tenemos que el unico punto candidato a soluciones x =(1/2, 1/2)con1= 4,1= 0y2= 0. Analicemoslacondici ondesegundoorden. LamatrizhessianadelafunciondeLagrangees2xxl( x,1, 1, 2) =__10 22 10__Observamosquela unicarestriccionactivaesh(x)=x1 + x2 1entoncestenemosquelamatrizA= h(x)T=(1 1), luego ^(A)= v R2:v1 + v2=0. Ahora, seav ^(A),v ,= 0,deaqutenemosquevT2xxlv=_v1v2___10 22 10____v1v2__= 24v21> 0,porlotanto x = (1/2, 1/2)esunpuntomnimoglobal estricto.4.6 EjerciciosResueltosEjercicio4.1Considereel problemamin_f(x1, x2, x3) = x1 +x224x1+x23x2+2x3: x1, x2, x3> 0_Probarquef escoercivaenel conjuntoderestriccionesyencontrarlassolucionesglobalesdel problema.Solucion. SeaX= (x1, x2, x3) : xi> 0, para todo i = 1, 2, 3,entonceselproblemaes___min f(x)s.a:x XProbemosquef escoerciva. Porcontradiccion, supongamosquef noescoerciva,entoncesexisteunasucecioncrtica xk Xtal que limkf(xk) ,=+, estoes,existe c > 0 siempre que f(xk) c, para todo k IN. Usando la denicion de ftenemosxk1 +(xk2)24xk1+(xk3)2xk2+2xk3 c. (4.27)88Entonces, xk es limitada (ya que cada 0 < xki c) y como xk es crtica, entoncesexistex FrontXtal quexkx=(x1, x2, x3). Luego, existei 1, 2, 3tal quexi=0, loqueimplica, xki0, yde(4.27)tenemosque+ c, quecontradicelasuposicion,porlotantofescoercivaenX.Como fes coerciva y continua en Xentonces por Corolario 3.4 existe un mnimo global.Hallemoslospuntoscandidatosasolucion(f(x)=0). Derivandoconrespectoalasvariablesx1, x2, x3tenemosfx1= 1 x224x21= 0,fx2=x22x1x3x2= 0,fx3=2x3x22x23= 0.Delaprimera,segundayterceraecuacionobtenemosrespectivamente_x2x1_2= 4. (4.28)x22x1=_x3x2_2(4.29)x3x2=1x23(4.30)De(4.28)yconsiderandoquex1, x2> 0,tenemosx2x1= 2 (4.31)Sustituyendolaecuacion(4.31)en(4.29)da1 =_x3x2_2,loqueimplicaquex3= x2. (4.32)Sustituyendo(4.32)en(4.30)tenemosx23= 1yasx3= 1. Sustituyendoen(4.32)y(4.31)obtenemosqueel unicopuntocandidatoesx = (12, 1, 1)ycomoexisteunmnimoglobalesteesel unicomnimoglobaldelproblema.Ejercicio4.2Demostrar que la funcion f(x1, x2) = (x2x21)2+x51tiene un unico puntoestacionarioquenoesmaximizadorniminimizadordefenRn.89Solucion.i) Hallemos los puntos estacionarios. Las derivadas parciales sonfx1=2(x2 x21)(2x1)+4x41= 4x1(x2 x21)+4x41yfx2=2(x2 x21)(1) =2(x2 x21).Parahallarlospuntoscrticosformamoslaecuacion___4x1(x2x21) + 4x41= 0(x2x21) = 0Severicafacilmentequeel unicopuntoqueresuelvelasecuacionesesx = (0, 0).As,lafuncionf(x1, x2) = (x2x21)2+ x51tieneun unicopuntoestacionario.ii) Veamossi xesunpuntodemnimo, maximoopuntodesilla. Lasderivadasdesegundo orden son2fx21= 4(x2x21)+(4x1)(2x1)+16x31,2fx22= 2,2fx2x1= 4x1y2fx1x2= 4x1. Deaqutenemosque2f(0, 0) =__0 00 2__Vemosquelamatriznoessemidenidanegativaconcluyendoque x=(0, 0)noespuntodemaximoni local ni global. Tambien, comoestamatrizes solosemidenidapositivaelcriteriodesegundoordennonosdicenadadelpuntoobtenido.Porotrolado,observemosqueencualquiervecindadde x = (0, 0)existenpuntosdondelosvaloresdelafuncionsonnegativos,tomeporejemplox1< 0yx2= x21. Porlotantoel punto x=(0, 0)noestampocomnimolocal ni global. Concluimosportantoque x = (0, 0)noesmaximizadorniminimizadordefen Rn.Ejercicio4.3Estudielaexistenciadesolucionesdel problemaopt_f(x1, x2) = x21x22: (x1, x2) R2_Solucion. Es facilver que el punto crticoes x = (0, 0). Ademas,en cualquier vecindadde xpodemostomarx1= 0yx2 ,= 0obteniendof(0, x2) < 0,ascomotambien,x1 ,= 0yx2= 0obteniendof(x1, 0) > 0. Porlotanto x = (0, 0)notienemnimonimaximo.90Ejercicio4.4Encontrar todos los valores del parametro R para los cuales el problemademinimizacionirrestrictadelafuncionf(x1, x2) = x21 + 4x1x2 + 4x22 +x1 +x2,tienesolucionlocal.Solucion.i) Hallemoslospuntoscrticosusando f(x) = 0.___fx1= 2x1 + 4x2 + 1 = 0fx2= 4x1 + 8x2 + 1 = 0Sumandolasdosecuacionestenemos(2 2)x1 +12= 0ydeaqu,x1= 14(1).Sustituyendoenlaprimeraecuaciontenemos quex2=28. Luegolos puntoscrticosson(x1, x2) =_14(1),28_, ,= 1.ii) Calculemos la hessiana de f. Derivando parcialmente obtenemos2fx21= 2,2fx1x2=4,2fx2x1= 4,2fx22= 8. Luego2f(x) =__2 44 8__2f(x) 0 > 0 16 16 > 0 > 0 1 > 0Luego, los valores paralos cuales el parametrohacequelafunciontengaunmnimoes(1, +).Ejercicio4.5Seaf:(a, b) R, a, b R, continuaen(a, b). Pruebeque, si xesunmnimolocal defentoncesf( x) = 0of( x)noexiste.Solucion. Si fderivable en x entonces por la condicion necesaria de primer orden dadaenelTeorema4.1setienequef( x) = 0. Sifnoesderivableentoncesnoexistef( x).Ejercicio4.6Sean 2yf(x1, x2) = (1 +xn)3n1

i=1x2i+ x2n. Muestrequei) x = 0esel unicopuntoestacionariodefenRn.91ii) x = 0esunmnimolocal estrictoperonoesmnimoglobal.Solucion.i) Hallemoslospuntoscrticosfxi= 2(1 +xn)3xi= 0, paratodoi = 1, . . . (n 1). (4.33)fxn= 3(1 +xn)2n1

i=1x2i+ 2xn= 0. (4.34)De(4.33) tenemos (1 + xn) =0 xi=0, paratodoi =1, . . . , n 1, estoes,xn= 1 xi=0, paratodoi =1, . . . , n 1. Si xn= 1, entoncesde(4.34)tenemos quexn= 1=0, loquees unacontradiccion. Por lotanto, xi=0,paratodoi =1, . . . , n 1. Sustituyendoen(4.34) resultaque xn=0, luego x = (0, 0, . . . , 0)esunpuntocrtico.ii) Probemosque xesunmnimolocalestricto. Como2fx2i= 2(1 +xn)3,2fxixn= 6(1 +xn)2xi, 2fx2n= 6(1 +xn)n1

i=1x2i+ 2,tenemosque2f( x) =________2 0 0 00 2 0 0...0 0 0 2________ 0.UsandolacondicionsucientedesegundoordendadoporelTeorema4.2tenemosque x = 0 es mnimo local estricto con valor objetivo f(0) = 0. Ahora probemos que xnoesmnimoglobal. Consideremoselcason = 2,entoncestenemosf(x1, x2) =(1 + x2)3x21+ x22, aqu tomamoslospuntosx1=4, yx2= 2, as tenemosquef(4, 2) = 16 + 4 = 12 < 0 = f(0),as x = 0noesmnimoglobal.Ejercicio4.7SeaA = ATyxunpuntocrticodel problema___min12Ax, x) b, x) + cs.a.x Rn92Pruebeque:1. SiA _ 0entoncesxesunmnimoglobal def.2. SiA 0entoncesxesel unicomnimoglobal def.Solucion. ComoxesunpuntocrticoentoncesporelTeorema4.1f(x) = Axb = 0luego,paracadax Rnf(x) =12Ax, x) b, x) + c=12A(x x), x x) + f(x)Astenemosparacadax Rnf(x) = f(x) +12A(x x), x x)1. SiA _ 0entoncesf(x) f(x),patatodox Rn.2. Si A 0entoncesf(x)>f(x), paratodox ,=x. Porlotanto, xesel unicomnimoglobal.Ejercicio4.8Enel problemaanterior, muestrequesi xesunmnimolocal entoncesA x = byA _ 0.Solucion. Solousarlascondicionesdeoptimalidaddadoporlosteoremas4.1y4.2.Ejercicio4.9Sea f: RnR una funcion diferenciable en x. Muestre que si f( x) ,= 0entonces xnoesmnimonimaximolocal defsobreRn.Solucion. UsarlanegaciondelTeorema4.1.Ejercicio4.10Demostrar que la funcion f(x, y) = (1+ex) cos xyeytiene una innidaddemaximosperonotienemnimos.93Solucion. Hallemoslospuntosestacionariosdeffx= (1 +ey)senx = 0 (4.35)fy= eycosx eyyey= ey(cosx 1 y) = 0 (4.36)De(4.35)tenemosquesin x=0, ydel resultadoanteriorcumpleparatodoslosxtalquex = k,paratodo k ZZ(conjuntoden umerosenteros). Reemplazandoen(4.36)tenemosqueparatodok ZZ : y= cosk 1,estoimplicaquey=___0, sikesparok = 02, si k es imparEntonceslospuntosestacionariosson(x, y) =___(k, 0), si k = 0ok es par(k, 2), si k es imparHallemoslamatriz 2fa).2fx2= (1 +ey)cosxb).2fxy= sin xeyc).2fyx= sin xeyd).2fy2= ey(cosx 2 y)Evaluandoenlospuntosestacionariostenemos,sik=0okespar2fx2(k, 0) = (1 +e0) = 22fyx(k, 0) = senke0= 02fxy(k, 0) = senke0= 02fy2(k, 0) = e0(cosk 2 0) = 1As,paraelcasodondek = 0okesparlamatrizhessianaes2f(x, y) =__ 2 00 1__94Sikesimpar2fx2(k, 2) = (1 +e2)cosk= (1 +e2) = 1 +1e22fyx(k, 2) = senke2= 02fxy(k, 2) = senke2= 02fy2(k, 2) = e2(cosk 2 y) = e2(3 y) =3e2 ye2.Entonces,sikesimpartenemos2f(k, 0) =__1 1e2003e2 ye2__En ambos casos para k tenemos que la matriz obtenida es denida negativa (pues susautovaloresquesonlasdiagonalessonnegativas),porlotantotodoslospuntoscrticos(x, y) =___(k, 0), sik = 0okespar(k, 2), sikesimparson puntos de maximo y como k puede tomar cualquier n umero entero entonces tenemosunainnidaddepuntosdemaximo. Ahorasupongamosqueexisteunpunto(x0, y0)demnimo local o global, entonces por la condicion de segundo orden, Teorema 4.2, se debetenerquelamatrizhessianaenestepuntoessemidenidapositiva, loqueesimposibleyaquetodaslasmatricesHesianasenlospuntoscrticossondenidasnegativas.Ejercicio4.11Encontrarlosmnimosymaximosde___opt x313+ x2s.a.(x1, x2) X= (x1, x2) : x21 + x22= 2Solucion.i) Probemos la existencia, f(x1, x2) =x313+x2es continua en Rn, en particular en X,yXescompactoentonces,existepuntosdemnimoymaximoglobal.95ii) f, h C(Rn),dondeh(x1, x2) = x21 + x222;ademash(x1, x2) =_____2x12x2_____esl.i paratodo(x1, x2) X. Portantotodopuntodemnimoomaximoesunpuntocrtico.iii) Hallemoslospuntoscrticos. Siguiendolaobservacion4.13formamosel siguientesistema___xL(x1, x2, ) = 0x21 + x222 = 0.donde L(x1, x2, ) =x313+x2 +(x21 +x222). Hallando el gradiente de L tenemosqueelsistemaanteriorquedaestablecidoporx21 + 2x1= 0 (4.37)1 + 2x2= 0 (4.38)x21 + x222 = 0 (4.39)De(4.37)tenemosquex1(x1 + 2)=0si ysolosix1=0 x1= 2. Ahora, six1= 0,de(4.39)tenemosx2= 2ysustituyendoen(4.37)resulta = 12x2= 12(2)= 122= 24Luego x=(0,2), con= 24y x=(0, 2), con=24. Porotrolado,si x1= 2, de (4.38) tenemos x2= 12. Sustituyendoen(4.39) obtenemos = 12. Luego x1= 2(12)= 1ytambien x2= 12= 12(112)= 1. Astenemos, x=(1, 1), con =12, x=(1, 1) y = 12. As tenemos quelospuntoscrticosson(a) x = (0,2)con = 22,entoncesf( x) =2 = 1.414.(b) x = (0, 2)con =22,entoncesf( x) = 2 = 1.414.(c) x = (1, 1)con =12,entonces f( x) = 13 1 = 43= 1.333 . . ..96(d) = (1, 1)con = 12,entonces f( x) =13+ 1 =43= 1.333 . . ..Comparando los valores objetivos, y sabiendo por i) que los valores optimos globalesexisten, tenemos que x = (0,2) es un maximo global y x = (0, 2) es un mnimoglobal.iv) Evaluaremos las condiciones de 2doordenpara saber si los demas puntos sonoptimoslocales.2xxL(x, ) =__2x1 + 2 00 2__Ker(h(x)) = (d1, d2)/h(x)d = 0=___(d1, d2) : 2(x 1, x2)__d1d2__= 0___= (d1, d2) : x1d1 + x2d2= 0Para x = (1, 1)tenemosKer(h(1, 1)) = (d1, d2) : d1d2= 0 = (d1, d2) : d2= d1Luego,paratodod Ker(h(1, 1)),tenemos2xxL( x,)d, d) =_d1d1___2(1) + 2(1/2) 00 2(1/2)____d1d1__=_d1d1___ 1 00 1____d1d1__= d21 + d21= 0Luego x solo satisface la condicion necesaria de segundo orden. As el criteriononosdicenadasiesunmnimoomaximolocal.Para x = (1, 1)tenemos2xxL( x,)d, d) =_d1d1___2 + 2(1/2) 00 2(1/2)____d1d2__= 0Luego xsolosatisfacelacondicionnecesariadesegunorden, porlotantoelcriteriononosdamasinformacion.97Ejercicio4.12Seap=(p1, p2, p3) R3y L= a + td/ t RunarectaenR3dondea = (a1, a2, a3), (d1, d2, d3) R3. Sip , L,entoncesel problemadelamnimadistanciadepa Lpuedeserformuladocon___min |x p|2s.a.x LRespondalasiguientepregunta,existelasoluciondelproblema?Sinoexistejustique.Casocontrario,hallarel puntodemnimo.Solucion. El problema tiene solucion pues L es un conjunto cerrado y as podemos usarelresultadodadoenelejemplo3.8. Hallemoselpuntodemnimo. x =(x1, x2, x3) Lx = a +td,paraalgunt R,aspodemosexpresar___x1= a1 + td1x2= a2 + td2x3= a3 + td3Luego,elproblemapuedeserformuladopor___min(x1p1)2+ (x2p2)2+ (x3p3)2s.a.x1= a1 + td1x2= a2 + td2x3= a3 + td3Sustituyendoelvalordex___min(a1 + td1p1)2+ (a2 + td2p2)2+ (a3 + td3p3)2s.a.t R98Asobtenemosunproblemairrestrictodeunasolavariable,dondef(t) = (a1 + td1p1)2+ (a2 + td2p2)2+ (a3 + td3p3)2Hallemoslospuntoscrticosf(t) = 2(a1 +td1p1)d1 + 2(a2 + td2p2)d2 + 2(a3 + td3p3)d3= 0Aplicandolapropiedaddistributivayasosiandoconvenientementetenemosa1d1 + td21p1d1 +a2d2 + td22p2d2 + a3d3 + td23p3d3= 0t(d21 + d22 + d23) + (a1d1 + a2d2 +a3d3) (p1d1 + p2d2 + p3d3) = 0t|d|2+a p, d) = 0t = a p, d)|d|2Luegoel unicopuntodemnimodelproblemaes x = a +_p a, d)|d|2_dEjercicio4.13SeaA Rnnunamatrizsimetrica. Pruebequelospuntoscrticosdelproblema___opt12Ax, x)s.a :|x| = 1sonlosautovectoresdelamatrizA. Cualessonlosautovalores?Solucion.i) f(x)=12Ax, x)escontinuayX= x Rn: |x|=1escompacto, entoncesexistenpuntosdemnimoymaximoglobales.ii) fyh(x) = |x| 1 =_x, x) 1sondiferenciablesen Rn. Ademas,h(x) =122x_x, x)=x_x, x)= x, x Xluegotodopuntodemnimoymaximoespuntodesilla.99iii) Hallemoslospuntoscrticos, L(x, )= Ax, x) + (|x| 1). Lospuntoscrticossonobtenidosresolviendo___xL(x, ) = 0h(x) = 0estoes, Ax + xx,x=0y |x|=1. EntoncessetieneAx= x. Denotando= , obtenemosquelospuntoscrticossatisfacenAx=x. As, lospuntoscrticossonlosautovectoresdelamatrizAylosautovaloressonelinversoaditivodelosmultiplicadoresdeLagrange.Ejercicio4.14Considerandoquelafunciondeutilidaddeuncomercianteesf(x, y) = 18 12x21x22donde x1e x2representa las cantidades de carne y verduras que vende (en kilos). Supong-amosqueelcapitaldelcomercianteesde12soles(elcualest aobligadoainertirlototal-menteenlosdosproductos)ylospreciosdex1yx2son2y3solesrespectivamente.a) Formularel problemadeoptimizacion.b) Resolverel problema.Solucion.a) Laformulaciondelmodeloesmax18 12x21x22: 2x1 + 3x2= 12, x1> 0, x2> 0b) Elproblemadadoesequivalenteamin18 +12x21 + x22: 2x1 + 3x2= 12, x1> 0, x2> 0i) Hallemosellagrangiano,L(x1, x2, s, p, q) = 18 +x212+ x22 + s(2x1 + 3x212) px1qx2dedondexL =__x1 + 2s p2x2 + 3s q__.100Elsistemaquedaestablecidocomo___x1 + 2s p = 0,2x2 + 3s q= 0,2x1 + 3x2= 12,x1> 0,x2> 0,px1= 0,qx2= 0,p, q 0Comoxeysonpositivos,entonces p = 0yq= 0luegoelsistemasereduce a___x1 + 2s = 0,2x2 + 3s = 0,2x1 + 3x2= 12,x1> 0,x2> 0,De la primera y segunda ecuacion tenemos que x2= (3/4)x1. Sustituyendo enla tercera ecuacion obtenemos x1=4817y x2=3617. Reemplazando en la primeraecuaciondas= 2417. Luegoel unicopuntocrticoes(x1, x2)=(4817,3617)cons = 2417.ii) HallemoslamatrizHessianadelafunciondeLagrange. Derivandoparcial-menteLobtenemos2xxL =__1 00 2__Esta matriz es denida positivaentodo R2, enparticular enel Ker(h(x, y)),luego usando el Teorema 4.12 obtenemos que el punto es mnimo local estricto.Ademas como la funcion objetivo es convexa,entonces tal mnimo es global yporlotantosoluciondelproblemadeoptimizacion.101Ejercicio4.15Sif(x) =12xTAx bTx +c,dondeA Rnn,A = ATyA _ 0. Pruebeodeuncontraejemplodelasiguienteproposicionftieneunmnimoglobbalsobre RnSolucion. Laproposicionesfalsa. Enefecto,considereA =__1 11 1__yb =__23__Supongamos que existe un mnimo global x = ( x1, x2) R2, por la condicion necesariadeprimerordensetienequeAx = b,locualequivalea__1 11 1____ x1 x2__=__23__deaqu sededucequex1+ x2=2yx1+ x2=3peroestoes, 2=3, loqueesunacontradiccion.Ejercicio4.16Considereel problemamin[[ Ax b [[2: x RndondeA Rmn, m n, b Rm,rangodeA = n.a) Pruebequeel problematienesolucionglobal.b) Escribelacondici onnecesariadeprimerordendeoptimalidad.Esunacondici onsuciente?.c) Encuentrelasolucionoptima.Solucion.a) Lafuncionfsepuedeexpresarcomo:f(x) = [[Ax b[[2= Ax b, Ax b)=ATAx, x_2ATb, x_+[[b[[2.102Asfpuedeserexpresadacomof(x) = xT(ATA)x 2(ATb)Tx +[[b[[2.SeaB=ATA y b=ATb entonces, f(x) =xTBx 2(b)Tx + [[b[[2. ComoBT= (ATA)T= ATA = B(Bessimetrica)yparatodoz ,= 0zTBz= zT(ATA)z=zT(ATA)1/2(ATA)1/2z=((ATA)1/2z)((ATA)1/2z)>0(Besdenidapositiva),concluimosqueesteproblemaesuncasoparticulardelEjemplo3.7. Porlotanto,fescoercivayaselproblematienesolucionglobal.Ejercicio4.17Considereel siguienteproblemamax18 12x2y2: 2x + 3y 12, x 0, y 0i) El problematienesolucion?ii) HallarlascondicionesdeKKT.iii) Siexistelasoluciondel problema,hallarla.Solucion.i) Elproblemaesequivalenteamin12x2+ y218 : 2x + 3y 12, x 0, y 0Lafuncionf(x) =12x2+y218escontinuayX= (x, y) : 2x + 3y 12, x 0, y 0escompacto,entonceselproblematienesolucion.ii) L(x, y, s1, s2, s3) =12x2+ y218 +s1(2x + 3y 12) s2x s3y,as(x,y)L(x, y, s1, s2, s3) =__x + 2s1s22y + 3s1s3__103LascondicionesdeKKTson___xL(x, s) = 0viabilidads 0___x + 2s1s2= 0,2y + 3s1s3= 0,2x + 3y 12,x 0,y 0s1(2x + 3y 12) = 0,s2x = 0,s3y= 0,s1, s2, s3 0.iii) Debemosresolver___x + 2s1s2= 02y + 3s1s3= 02x + 3y 12,s2x = 0,s3y= 0,s1(2x + 3y 12) = 0,x, y, s1, s2, s3 0.dedonde,s2x = 0siysolosis2= 0 x = 0.Sis2= 0entoncesx + 2s1= 0,comox 0ys1 0 x = 0 s1= 0. 2y= s3. y 4 2y.y= 0 y= 0Portanto,elpunto(0, 0, 0, 0, 0)satisfacelascondicionesdeKKT.Six = 0entonces2s1= s2s3y= 0 s3= 0y= 0104Siy= 0 3s1= s3 s1= 0Luego,elpuntoes(0, 0, 0, 0, 0).Sis3= 0 2y + 3s1= 0 y= 0 s1= 0 s1= 0 (0, 0, 0, 0, 0)satisfacelascondicionesdeKKT.Luego, el unicopuntoquesatisfacelascondicionesdeKKTes(0, 0), yusandoeltemi,concluimosque(0, 0)eseloptimodelproblema.Ejercicio4.18Hallarlospuntoscrticosdel problemamincTx +12xTBx : Ax = b,dondec Rn,B Rnnsimetrica,invertibleyA Rmnderangom < n.Solucion.i) LafunciondeLagrangees: L(x, )=cTx +12xTBx T(Ax b), ycomoBessimetricaentonces x_12xTBx_=Bx, luegotenemosque xL(x, )=c + Bx AT.ii) LascondicionesdeKKTson___xL(x, ) = 0,Ax = b.dedondesededuceAT Bx = c (4.40)Ax = b, (4.41)105Multiplicando (4.40) por B1y por A, usando (4.41) resulta AB1ATb = AB1c.ComoAesderangomentoncesAB1ATesinvertible,assetiene = (AB1AT)1(b + AB1c). (4.42)De(4.40) tenemos quex=B1AT B1c, ydelaecuacion(4.42), tenemosx = B1AT(AB1AT)1b +BAT(AB1AT)1AB1c B1c. Por lo tanto, el unicopuntocrticoesx = B1AT(AB1AT)1(b + AB1c) B1c.Ejercicio4.19hallarlascondicionesdeoptimalidaddeKKTdel siguienteproblemaminf(x) m

i=1ln(gi(x)) : gi(x) 0, hj(x) = 0dondef, gi, i = 1, . . . , myhj,j= 1, . . . , psonfunciones diferenciables sobre Rny > 0esunparametrojo.Solucion. Porlanaturalezadelproblema,esteesequivalenteaminf(x) m

i=1ln(gi(x)) : hj(x) = 0Formamos la funcion lagrangiana, L(x, ) = f(x)

mi=1 ln(gi(x)) pj=1jhj(x).i) HallamoselgradientedelafunciondeLagrangexL(x, ) = f(x) x_m

i=1ln(gi(x))_Th(x). (4.43)Sea(x) =

mi=1 ln(gi(x)) = ln g1(x) + ln g2(x) + + ln gn(x),entonces(x)xi=g1(x)xig1(x)+g2(x)xig2(x)+ +gm(x)xigm(x).As,x_m

i=1ln gi(x)_= (x) = g1(x)g1(x)+ g2(x)g2(x)+. . . + gm(x)gm(x)=m

i=1gi(x)gi(x)Sustituyendoestaexpresionen(4.43)tenemosxL(x, ) = f(x) m

i=1gi(x)gi(x)Th(x).106ii) Luego,lascondicionesdeKKTson___xL(x, ) = 0h(x) = 0gi(x) > 0___f(x)

mi=1gi(x)gi(x)Th(x) = 0h(x) = 0gi(x) > 0.4.7 EjerciciosPropuestos1. Considereelproblemamin(x112)2+ (x25)2: 2x1 + x2 6; x1 + x2 4; x1 0; x2 0. Obtengalospuntoscandidatosasolucion.107Captulo5ElementosdeConvexidadEnestecaptulopresentaremosloselementosbasicosdeconvexidadquenospermitiranabordar posteriormente los problemas de optimizacion convexa que tienen un gran campodeaplicacionesendiferentesareasdelascienciaseingenieras.5.1 ElementosdeConvexidadDenicion5.1UnconjuntoC RnesllamadoconvexosiC= oparatodox, y Cytodo [0, 1] setienex + (1 )y C. UnconjuntoA Rnesllamadoan, siparatodox, y Aytodot R,tx + (1 t)y A. UnsubconjuntoK Rnesunconosi,paratodod Kyt 0,td K.xyCFigura5.1: Gracadeunconjuntoconvexo.Ejemplo5.1Ejemplosdeconjuntosconvexosson:108yxCFigura5.2: Gracadeunconjuntoquenoesconvexo.El espacioeuclidianoRn.LabolaabiertaB( x, ),donde x Rny > 0.El ortantenonegativoRn+.El semiespacio x Rn: Ax b,dondeA Rmn,b Rm.El hiperplano x Rn: a, x) = ,dondea Rny R.Ejemplosdeconjuntosquenosonconvexosson:Rn0.LaesferaunitariaS(0, 1) = x Rn: [[x[[ = 1.Ejemplo5.2Lasrectas,losplanossonespaciosanes.Ejemplo5.3Rn+, on+sonconosconvexos.Denicion5.2DadoX Rn, lacerraduraconicadeX, denotadopor cono(X)eselmenorconoquecontieneaX.Proposicion5.1SiXesconvexoentoncescono(X) = x : x X; 0.Prueba.Denicion5.3Unpuntox Rnesunacombinacionconvexadepuntos x1, . . . , xpsiexisteni 0,i = 1, . . . , p,tal que

pi=1i= 1ysesatisfacex =

pi=1ixi.109R2+Figura5.3: R2+esconjuntoconvexo.yxCFigura5.4: R2+ R2+noesunconjuntoconvexo.Teorema5.1Unsubconjunto CRnes convexo si y solamente si para cualquiern umerop IN,xi C,i 0,i = 1, 2, . . . , p,con

pi=1i= 1,setiene

pi=1ixi C.Demostracion. SeaCconvexo,probaremosporinduccionquelacombinacionconvexaestacontenidaenC. Si p=1, el resultadoesinmediato. Supongamosquelahipotesisesverdaderaparap = n(hipotesisinductiva),probaremosqueesvalidaparap = n + 1.Veamos; seax1, x2, . . . , xn, xn+1Cy1, 2, . . . , n, n+1 0, tal que

n+1i=1i=1,entonces

n+1i=1ixi=

ni=1ixi+ n+1xn+1. Si n+1=1entoncesel resultadoesver-dadero(similaralcasop = 1).Sean+1 ,= 1,estoes,1 n+1 ,= 0,entoncesn+1

i=1ixi= (1 n+1)n

i=1_i1 n+1_xi+ n+1xn+1(5.1)110Como

n+1i=1i= 1, se tiene,

ni=1i= 1n+1, esto es,

ni=1_i1n+1_= 1, dondelarelacioni1n+1 0,paratodoi = 1, 2, . . . , n.Como x1, x2, . . . , xnCy

ni=1_i1n+1_=1. Aplicando hipotesis inductiva,

ni=1_i1n+1_xiC. Usandoesteresultadoenlaecuacion(5.1) ypor lahipotesisgeneral (convexidadde C) tenemos que

n+1i=1ixiC. El recprocoes inmediatotomandoenparticularp = 2.Teorema5.2(deCaratheodory) Si x Rnesunacombinacionconvexadepuntosde XRn, entonces existenxiXy iR+, i =1, 2, . . . , n+1, satisfaciendo

n+1i=1i= 1y x =

n+1i=1ixi.Demostracion. SixesunacombinacionconvexadeX,entoncesexistep INtalqueX=p

i=1ixi,p

i=1i= 1.Mostraremosquesi p>n + 1, entoncespodemoseliminarunpuntodelacombi-nacionconvexa. Si existei0 1, . . . , p, tal quei0=0, entoncespodemoselim-inarel puntoxi0obteniendoel objetivodeseado. Seai>0, paratodoi =1, . . . , p.Comop>n + 1entoncesp 1>n, porunresultadodealgebralineal, el conjuntox1xp, x2xp, . . . , xp1xp es linealmente dependiente, entonces existen 1, . . . , p1notodosnulostalque

p1i=1i(xixp) = 0.Seap= p1i=1i,entonces

pi=1i= 0. Ademas,p

i=1ixi=p1

i=1i(xixp) = 0. (5.2)Seaj0 1, 2, . . . , ptal quej0j0=max1kp_kk_. Comoexistei ,=0entonces,sii> 0,tenemosj0j0> 0,casocontrario,sii< 0,delaigualdad

ni=1i= 0,existej> 0yasj0j0> 0. Deamboscasostenemosj0j0> 0.111Denamosqi=i j0j0i, paratodoi =1, . . . , p. Deaqu tenemosqueqi 0yqj0= 0,ademas,p

i=1qi=p

i=1ij0j0p

i=1i= 1.Luego,x =p

i=1ixi=p

i=1qixi+j0j0p

i=1ixi0=p

i=1qixi,dondela ultimaigualdadseobtienede(5.2). Comoqj0=0, entoncesconcluimosquex=

pi=1i=j0qixi. As, xes unacombinacionconvexadep 1puntos. Repitiendoelprocesop (n + 1)vecesobtenemoslacombinacionconvexaden + 1puntos.Denicion5.4SeaX Rnunconjuntoarbitrario. LaenvolturaocerraduraconvexadeX, denotadopor Conv(X) es denidocomolaintersecciondetodos los conjuntosconvexosquecontienenaX,estoes,Conv(X) =

XCCCconvexo.Observacion5.1Puede probarse que la envoltura convexaConv(X) es un conjunto con-vexoyquesiXesconvexo,entoncesConv(X) = X.Ejemplo5.4 Conv (x Rn: |x| = 1) = x Rn: |x| 1.Ejemplo5.