Optimització No Lineal I (ONL1)
| Professors Responsables: |
NARCÍS NABONA FRANCISCO (nabona eio.upc.edu )
|
|
Crèdits: 6.0 (3.0 T 1.5 P 1.5 L)
| |
Departament:
EIO
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
|
MDIO2
- Pre-requisit per la EI
|
|
Objectius docents
Presentar les bases teòriques dels principals algorismes
d'Optimització No Lineal i les seves eines professionals de
resolució de problemes reals i d'alta dimensionalitat. Amb aquesta
finalitat:
- es justificarà l'eficiència computacional dels algorismes que
es presenten
- s'arribarà a la comprensió de part de les propietat dels
algorismes per experimentació computacional
- s'adquirirà pràctica en l'ús dels paquests professionals
d'Optimització No Lineal
- s'entrarà en contacte amb problemes reals d'Optimització No
Lineal.
(En el curs d'Optimització No Lineal II s'estudien altres
algorismes d'Optimització No Lineal i s'arriba a un major aprofondiment
en alguns temes).
En la classificació dels temes es distinguix entre temes
teòrics -amb la indicació (t)- i temes s'exercicis computacionals -amb la
indicació (c)-. Les classes de pràctiques estan dedicades tant a
problemes com a preparació d'exercicis computacionals. Com a part dels
exercicis computacionals hi ha l'explicació i codificació d'un
problema real d'optimització sense constriccions lineals {proc1} i d'un
problema amb contriccions qualsevol {procq}.
Programa
1. Repàs de conceptes bàsics:
-(t) Funcions de diverses variables. Gradient. Hessià. Vector de
funcions. Jacobià. Condició de definició de matrius.
Resolució de sistemes d'equacions lineals a partir de
triangularització de matrius.
-(t) Esparsitat de vectors i matrius. Ubicadors i accessibilitat. Operacions.
Graf equivalent de matrius simètriques esparses.
Triangularització i reordenacions.
-(c) Exercicis FUNQ i UBIC.
2. Optimització sense Constriccions:
-(t) L'explotació lineal. Derivada direccional. Ajustos
quadràtics i cúbics. Condicions 1a i 2ona d'Armijo Goldstein.
-(c) Codificació de les rutines de valor de la funció objectiu i
gradient d'un {prosc} (problema real d'optimització sense constriccions).
Exercicis QREX i FREX.
-(t) La convergència del mètode del gradient.
-(t) El mètode de Newton i la seva convergència. Modificacions de
Luenberger i de Dennis-Schnabel.
-(c) Exercicis QRAD i GRAD. Codificació de l'hessià d'un {prosc}.
Exercicis NOUT, NEWT i NOUE.
-(t) Direccions conjugades. Teorema del subespai expansionant. Mètode del
gradient conjugat. Aplicació a la solució d'un sistema lineal i
simètric d'equacions.
-(c) Exercicis QRAC i GRAC.
-(t) Repàs de les condicions d'òptim subjecte a constriccions
d'igualtat i de desigualtat. Constriccions actives. Pla tangent i base dels
vectors del pla tangent. Lagràngia, el seu gradient i el seu
hessià. Condicions de segon ordre.
-(t) Optimització subjecta a constriccions lineals d'igualtat i fites
simples de les variables. Mètode de Murtagh-Saunders. Similitud i parts
comunes amb l'algorisme de simplex.
-(c) Definició d'un {proc1} (problema real d'optimització amb
constriccions lineals). Ús del paquet MINOS. Codificació de la
rutina FUNOBJ de Minos per al {proc1}. Expressió de les constricions
lineals del {proc1} en l'arxiu MPS.
3. Optimització amb Constriccions Qualsevol
-(t) El mètode de Newton-Raphson per resoldre sistemes d'equacions no
lineals. Cas de menys constriccions que incògnites i possibilitat
d'optimització.
-(c) Definició d'un {procq} (problema real d'optimització amb
constriccions qualsevol). Ús dels paquet MINOS. Codificació de la
rutina FUNOBJ de Minos per al {procq}. Expressió en la rutina FUNCON de
les constriccions qualsevol.
-(t) El mètode del gradient reduït generalitzat. Cas de
constriccions lineals i de constriccions qualsevol. Retorn a
l'hipersuperfície de les constriccions actives.
Avaluació
- Examen de teoria i problemes 55%;
- problemes resolts per l'estudiant 15%;
- exercicis computacionals 30%.
Bibliografia
Bibliografia bàsica
- DENNIS Jr., J.E. & SCHNABEL, R.B Numerical Methods for Nonlinear
Equations and Unconstraiend Minimization Prentice Hall, Englewword Cliffs, 1983
- DUFF, I.S.; ERISMAN, A.M. & REID, J.K Direct Methods for Sparse
Matrices Oxford University press, Oxford, G.B, 1989
- GILL, P.E.; MURRAY & WRIGHT, M.H Practical Optimization Academic Press Inc., London G.B, 1981
- LUENBERGER, D.G Linear and Nonlinear Programming Addison-Wesley
Publ. Co., Reading, Mass, USA, 1984
- PERESSINI, A.L.; SULLIVAN, F.E. & UHL, J.J The Mathematics of
Nonlinear Programming Undergraduate Texts in Mathematics, Springer-Velarg,
Berlin, 1988
Informació complementària
A les classes de problemes (7 o 8) s'explica la resolucio dels distints
tipus de problemes que hi ha en una col.leccio de problemes resolts
posada a la disposicio dels alumnes. Al final de cada classe de problemes
se'n planteja un de semblant als explicats a classe a ser resolt de forma
individual pels alumnes i lliurat a la seguent classe de problemes.
Els problemes resolts pels alumnes son qualificats i retornats, i la nota
mitja obtinguda d'aquest problemes resolts pels alumnes constitueix el
15% de la qualificació de l'assignatura.
|
