Optimització No Lineal II (ONL2)
| Professors Responsables: |
NARCÍS NABONA FRANCISCO (nabona eio.upc.edu )
|
|
Crèdits: 4.5 (3.0 T 0.75 P 0.75 L)
| |
Departament:
EIO
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
|
ONL1
- Pre-requisit per la EI
|
|
Objectius docents
Completar els coneixements impartits a Optimització No Lineal I
ampliant i aprofondint en els algorismes i les 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 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} (diferents dels d'Optimització
No Lineal I).
Programa
1. Optimització sense Constriccions:
-(t) Mètodes quasi-Newton actualitzant la inversa de
l'hessià. Algorisme DFP.
-(c) Codificació de les rutines de valor de la funció objectiu i
agradient d'un {prosc} (problema real d'optimització sense
constriccions). Exercicis QERA, DQFP i DAFP.
-(t) Actualitzacions de factoritzacions quan s'afegeixen o sostreuen matrius de
rabg u. Mètodes quasi-Newton actualitzant l'hessià. Algorismes
PSB i BFGS. Invariança i mètrica.
-(c) Exercicis LESK i bfgs. Utilització d la rutina VA13 de la llibreria
Harwell.
-(t) Matrius de Householder i factoritzacions QR i LQ. Submatrius Y i Z de Q.
Mínims quadrats lineals. Mínims quadrats qualsevol pel
mètode de Gauss-Newton.
-(c) Exercicis MQRL I MORO.
2. Optimització amb Constriccions Lineals:
-(t) Minimització amb constriccions lineals d'igualtat. Obtenció
de la matriu Z per factorització LQ i pel mètode de
reducció de variable. Gradient i hessià projectat.
Estimació de multiplicadors de Lagrange.
-(t) Minimització amb constriccions lineals de desigualtat. Mètode
del conjunt actiu. Actualitzacions de la matriu Z i de l'hessià
projectat quan s'afegeixen i descarten constriccions. Programació
quadràtica definida positiva. Minimització subjecta a fites
simples.
-(c) Exercici NEFS. 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 constriccions lineals del {proc1} en l'arxiu MPS.
-(t) Introducció a l'algorisme de Karmarkar de programació
lineal.
3. Optimització amb Constriccions Qualsevol:
-(t) Mètodes de penalització i barrera. Convergència local
d'aquests mètodes.
-(t) Concepte i mètode de Lagrangià augmentat. Mètodes
de Lagrangians projectats. Formulacions 1a i 2ona. el paquet MINOS i la seva
formulació.
-(c) Definició d'un {procq} (problema real d'optimització amb
constriccions qualsevol). Ús del paquet MINOS. Codificació de la
rutina FUNOBJ de Minos per al {procq}. Expressió en la rutina FUNCON de
les constriccions qualsevol.
Avaluació
- Examen (teoria i problemes) sobre Optimització Sense Constriccions
30%;
- examen (teoria i problemes) sobre Optimització Amb Constriccions
30%;
- exercicis computacionals 40%.
Bibliografia
Bibliografia bàsica
- DENNIS Jr., J.E. & SCHNABEL, R.B Numerical Methods for Nonlinear
Equations and Unconstraiend Minimization Prentice Hall, Englewword Cliffs, 1983
- 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
- NEMHAUSER, G.L.; RINOY, A.G.H. & TODD Optimization Handbooks in
Operations and Management Science, vol. 1, Elsevier Science Publ., Amsterdam, 1989
- PERESSINI, A.L.; SULLIVAN, F.E. & UHL, J.J The Mathematics of
Nonlinear Programming Undergraduate Texts in Mathematics, Springer-Velarg,
Berlin, 1988
|
