Zur Stabilit - dynardo.de€¦ · Zur Stabilit ¨ at von SQP-Verfahren und zur L ¨ osung globaler...

Zur Stabilitat von SQP-Verfahren und zur Losungglobaler und gemischt-ganzzahliger

Optimierungsprobleme

Klaus SchittkowskiFachgruppe Angewandte InformatikUniversitat Bayreuth

Inhalt:

- SQP-Verfahren- verteilte Liniensuche- nicht-monotone Liniensuche- globale Optimierung- gemischt-ganzzahlige nichtlineare Optimierung

SQP-Verfahren Klaus Schittkowski

Problemstellung

Nichtlineares Programm (NLP):

min f (x)

gj(x) = 0 , j = 1, . . . ,me

x ∈ IRn : gj(x) ≥ 0 , j = me + 1, . . . ,m

xl ≤ x ≤ xu

Anwendungsgebiete in der Strukturmechanik:

- Auslegungsoptimierung (sizing)- Geometrieoptimierung (shape)- Topologieoptimierung (topology)


Einsatz von SQP-Verfahren

NLPQL in Modellierungssystemen:

- IMSL Library (VN) - ANSYS/POPT (CAD-FEM)

- DesignXplorer (ANSYS) - STRUREL (RCP)

- TEMPO (OECD Reactor Project) - Microwave Office Suit (AWR)

- MOOROPT (Marintec) - iSIGHT (Enginious Software)

- POINTER (Synaps) - EXCITE (AVL, Graz)

- FRONTIER (ESTECO, Trieste) - MathCad (MathSoft)

- TOMLAB/MathLab - OptiSLang (DYNARDO, Weimar)

- AMESim (IMAGINE, Roanne)


SQP-Verfahren (sequentielle quadratische Programmierung)

Entwurfsziel: schnelle lokale Konvergenzgeschwindigkeit (Han 78, Powell 79, 81)

Idee: quadratische Approximation der Lagrange-Funktion und Linearisierung der

Nebenbedingungen

d ∈ IRn :

min 12dTBkd +∇f (xk)

Td

∇gj(xk)Td + gj(xk) = 0 , j = 1, . . . ,me

∇gj(xk)Td + gj(xk) ≥ 0 , j = me + 1, . . . ,m

xl ≤ xk + d ≤ xu

Neuer Iterationswert: xk+1 = xk + αkdk


SQP-Verfahren (Fortsetzung)

Motivation: Die Optimallosung des quadratischen Programms (dk, uk) ist einNewtonschritt zur Losung der KKT-Optimalitatsbedingungen, sofern Bk dieHessematrix der Lagrangefunktion

L(x, u) = f (x)−m∑j=1

ujgj(x)

Zu untersuchen:

1. Quasi-Newton-Update-Verfahren fur Bk (BFGS)

2. Behandlung inkonsistenter Teilprobleme

3. Abstieg bzgl. geeigneter Meritfunktion

4. Liniensuche, d.h. Bestimmung von αk


Beispiel

Funktionen:

f (x1, x2) = x21 + x2

g1(x1, x2) = 9− x21 − x22 ≥ 0

g2(x1, x2) = 1− x1 − x2 ≥ 0

Lagrange-Funktion:

L(x, u) = x21 + x2 − u1(9− x21 − x22)− u2(1− x1 − x2)

Optimallosung:

x� = (0,−3)T , I(x�) = {1}


Beispiel (Fortsetzung)

Iterationsverlauf: Anwendung des SQP-Verfahrens NLPQL (S., 1986)

k f (xk) r(xk) s(xk)0 4.0000000 1.0 17.21 3.0000008 0.0 8.12 −1.5781250 0.0 1.43 −2.8814583 0.0 0.224 −3.0011228 0.22× 10−1 0.54× 10−25 −3.0004040 0.25× 10−2 0.81× 10−36 −3.0000022 0.13× 10−4 0.43× 10−57 −3.0000000 0.74× 10−10 0.25× 10−108 −3.0000000 0.0 0.12× 10−18

mit s(xk) =| f (xk)Tdk | + ∑m

i=1 | u(k)i gi(x

(k)) |


Beispiel (Fortsetzung)

-4

-3

-2

-1

0

1

2

3

4

-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6

g2(x) = 0

f(x) = c

g1(x) = 0

x1

x2

o

o

o

oo

oo

✲

✻

❍❍❍❍


Liniensuche

Ziel: Stabilisierung im Sinne von Konvergenzerzwingung, Korrektur schlechter

Startwerte, Vermeidung zu großer Restriktionsverletzungen, hinreichender Abstieg

Schrittlangenbestimmung: Suche αk durch quadratische Interpolation und

Reduktion, bis

Φrk(xk + αdk) ≤ Φrk(xk) + µαdTk∇Φrk(xk)r : Penaltyparameter

µ : konstant

dTk∇Φrk(xk) < 0 : Abstiegsrichtung

Muster: exakte Penaltyfunktion

Φr(x) = f (x) + rm∑i=1

|min(0, gj(x))|


Parallelisierung der Liniensuche

Ziel: Gleichzeitige Bereitstellung von l Funktionswerten zu Beginn der

Schrittlangenbestimmung, logarithmisch verteilt zwischen 0 < ε ≤ 1

Leistungsverhalten: Anzahl der erfolgreichen Testlaufe (NSUCC) und Anzahl

der Iterationen (NIT) bezogen auf Anzahl der simulierten Prozessoren (L)

L NSUCC NIT L NSUCC NIT1 306 25 9 299 323 206 179 10 300 294 251 126 12 301 285 282 80 15 297 266 291 50 20 299 267 292 42 50 300 268 297 35

306 Testbeispiele: http://www.uni-bayreuth.de/departments/math/˜kschittkowski/downloads.htm


Nicht-Monotone Liniensuche

Ziel: Vermeidung von Abbruchen aufgrund von Rechenfehlern bei Funktions-

und/oder Gradientenauswertungen (NLPQL: IFAIL=4)

Idee: Wahle alternativen Referenzwert fur Abbruchbedingung

Φrk(xk + αdk) ≤ Φk + µαdTk∇Φrk(xk)

mit Φk = max{Φri(xi) : i = k −m, k}


Nicht-Monotone Liniensuche (Fortsetzung)

Leistungsverhalten: Anzahl der erfolgreichen Testlaufe (1 %) fur monotone

und nicht-monotone Liniensuche unter zufalligen Storungen (ERR)

adaptive Toleranz konstante Toleranz (10−7)ERR monoton nicht-monoton monoton nicht-monoton0 304 306 306 30610−12 304 302 304 30010−10 299 305 292 29810−8 283 301 210 29910−6 260 297 71 28310−4 202 287 23 24610−2 117 255 23 156

Gradienten: Vorwartsdifferenzen

Beobachtung: Fur nicht-monotone Liniensuche reichen Vorwartsdifferenzen!


’Globale’ Optimierung

Problem: sukzessive Verbesserung restringierter lokaler Minima

x1

* x*

Voraussetzung: Funktionsberechnungen zu teuer, um stochastische

Suchverfahren anwenden zu konnen!


’Globale’ Optimierung (Fortsetzung)

Vorgehensweise: Gegeben sei ein lokales Minimum x�k

1. Anpassung der Restriktion f (x) ≤ f�k − ε1|f�k | mit f�k = min0≤i≤k f (x�i )

2. Fuge neue Restriktion ‖x− x�k‖2 ≥ ε2 an

3. Relaxiere die Restriktionen

Schwierigkeiten:

1. Wahl der Parameter

2. Wahl neuer Startwerte

3. lokale Losungen im relaxierten Raum


’Globale’ Optimierung (Fortsetzung)

Testbeispiele: 35 aus der Literatur (bis uber 1000 lokale Losungen), einheitliche

Toleranzen

Resultate:

Anzahl der globalen Losungen (1 %) : 27

Anzahl der lokal verbesserten Losungen (50 %) : 4

Prozentsatz der ’erfolgreichen’ Losungen : 89 %

durchschnittliche beste Losung gefunden im 3. Teilproblem

durchschnittliche Zahl der gelosten Teilprobleme : 7

durchschnittliche Zahl der Funktionsberechnungen : 317

durchschnittliche Zahl der Gradientenberechnungen : 179


Gemischt-ganzzahlige nichtlineare Optimierung

Problem (MINLP):

min f (x, y)

gj(x, y) = 0 , j = 1, . . . ,me

x ∈ IRn, y ∈ ZZm : gj(x, y) ≥ 0 , j = me + 1, . . . ,m

xl ≤ x ≤ xu

yl ≤ y ≤ yu

Voraussetzungen:

- Die Modellfunktionen sind glatt bzgl. der kontinuierlichen Variablen x- Das Problem ist konvex (?)

Offen: Was mussen wir uber die ganzzahligen Variablen y wissen?


Klassifikation der ganzzahligen Variablen

Relaxierbare Variable: MINLP fur y ∈ IRm losbar, d.h., die Modellfunktionen

konnen auch an allen Punkten zwischen benachbarten ganzzahligen Werten

berechnet werden

Beispiel: Blechdicke einer mechanischen Struktur

Physikalische Variable: physikalische Bedeutung, d.h. kleine Anderungen der

ganzzahligen Werte ziehen kleine Anderungen der Funktionswerte nach sich

Beispiel: Anzahl der Rippen eines Kuhlers

Kategorische Variable: MINLP nicht relaxierbar, keine Ordnungsbeziehungen

zwischen den ganzzahligen Variablen

Beispiel: Unterschiedliche Materialien, u.U. separate FE-Analysen

(s. 0/1-Probleme, diskrete Optimierung)


Heuristische Methoden

Bekannte Verfahren:

- Rundung der Losung eines relaxierten Problems

- Erzwingung der Ganzzahligkeit durch zusatzliche Restriktionen, z.B.

sin2(πyi) = 0 , yi(1− yi) = 0 oder (y1i − d1i )(y

2i − d2i ) . . . (y

ki − dki ) = 0

- stochastische Suchverfahren, z.B. genetische Algorithmen

- Branch-and-Bound-Verfahren

- sukzessive Linearisierung (MILP) (außere Approximationen)

- sukzessive quadratische Approximation (MISQP)


Sequentielle gemischt-ganzzahlige quadratische Programmierung

Voraussetzung: physikalische Variable, keine Relaxierbarkeit, d.h. keine

Ableitungen an Gitterpunkten

Vorgehensweise:

1. Quasi-Newton-Approximation (BFGS) der Hessematrix bzgl. der stetigen

Variablen

2. Differenzen 2. Ordnung an Gitterpunkten zur Approximation der Diagonalen

der Hessematrix bzgl. der ganzzahligen Variablen

3. Formulierung und Losung eines gemischt-ganzzahligen quadratischen

Programms (B & B)

4. Stabilisierung durch Vertrauensbereiche (trust regions)


MISQP: numerische Resultate

Testbeispiele: 41 aus der Literatur, darunter 8 0/1-Probleme

Resultate:

Anzahl der erfolgreichen Losungen (1 %) : 32

Anzahl der ’lokalen’ Losungen : 6

Prozentsatz der ’erfolgreichen’ Losungen : 93 %

durchschnittliche Zahl der Funktionsberechnungen : 59

durchschnittliche Zahl der Gradientenberechnungen : 7

Anwendungen: EPCOS, LMS Optimus


Fallstudie: Rillenhorner fur Kommunikationsatelliten


Fallstudie: Rillenhorner (Fortsetzung)



Entwurfsparameter:

ra - Offnungsradius x1 - Lange der Eingangssektionxcon - Lange der konischen Sektion xa - Gesamtlangeα - Anstellwinkel der konischen Sektion lr - Rillenbreitels - Rippenbreite t1 - Rillentiefe in Eingangssektiont2 - Rillentiefe in konischer Sektion



Optimierungsproblem:

p ∈ IRn : min∑l2

j=1 (bj2(p)− b

j2)2 + µ b11(p)

2

pl ≤ p ≤ pu

(b1(p)

b2(p)

)=

(S�11(p) S�

12(p)

S�21(p) S�

22(p)

)︸︷︷︸total scatteringmatrix

(a1

a2

)

a1 - Amplitude der Hornanregung (1. Einheitsvektor)a2 - Amplituden der reflektierten Moden an der Offnung (Fernfeldanalyse)

bj2 - Zielamplitudenµ - Wichtung fur Verlust



Numerische Komplexitat (Beispiel):- 70 Eigenmoden- 140× 140 komplexe Eintrage fur Streumatrizen(E, H bzw. U , I)

- Auswertung doppelter Integrale fur jeden Koeffizient und von Besselfunktionen- 40 Rillen und Rippen, d.h. Multiplikation von 80 Matrizen der Große 2 · 140× 140- Matrixmanipulationen an jeder Ubergangsstelle, inverse Dekompositionen

IT F SCV NA I ALPHA DELTA KT-----------------------------------------------------------------1 .16795478D+01 .00D+00 37 0 .00D+00 .00D+00 .37D+002 .14476536D+01 .57D+00 37 1 .10D+01 .00D+00 .31D+013 .11909891D+01 .68D+00 37 2 .10D+00 .00D+00 .43D+01.. ..... .... .. . ....... ........ .....49 .17397940D-02 .40D-02 37 1 .10D+01 .00D+00 .44D-0450 .17219966D-02 .35D-03 37 1 .10D+01 .00D+00 .22D-0551 .17225078D-02 .53D-06 37 1 .10D+01 .00D+00 .13D-07


Fallstudie: Entwurf von SAW-Filtern (Surface Acoustic Wave)

Ziel: Erfullung von Entwurfsvorgaben elektronischer Filter (EPCOS AG)

Wellengleichung: (∆− 1

c2

(∂2

∂t2

))φ(x, y, t) = 0


Fallstudie: SAW-Filter (Fortsetzung)

P-Modell: Auswertung kaskadierender Matrizen

b1

b2i

= P

a1

a2u

, e.g. Pe =

0 1 E

1 0 −E∗−2E 2E∗ 2|E|2 + i(−H{2|E|2} + ωC)

H - HilberttransformationC - statische Kapazitat zwischen zwei Fingern

E - Anregung definiert durch E = −i 0.5√ωWK · ∫

trσe(x) exp−ik|x| dx

ω - FrequenzW - Offnung des IDTK - Materialkonstanteσe - elektrische Ladungsverteilung, k = ω

c


Fallstudie: SAW-Filter (Fortsetzung)

max mini:fuR2≤fi≤foR2

Ti(x)

Ti(x) ≤ TR1, fuR1

≤ fi ≤ foR1x ∈ IRn : Ti(x) ≥ TR2

, fuR2≤ fi ≤ foR2

Ti(x) ≤ TR3, fuR3

≤ fi ≤ foR3xl ≤ x ≤ xu


Schlussfolgerungen

Heuristische Beobachtungen:

1. Die Liniensuche kann in SQP-Verfahren parallel gerechnet werden. Empfohlenwerden mindestens 10 Prozessoren.

2. Nicht-monotone Liniensuche kann je nach vorhandener Storung dieRobustheit von SQP-Verfahren drastisch verbessern.

3. Sukzessive Verbesserung lokaler Losungen moglich, aber sensitiv gegenuberWahl der Toleranzen.

4. Fur glatte Abhangigkeiten von ganzzahligen Variablen konnengemischt-ganzzahlige, nichtlineare und nichtkonvexe Programme mit Hilfeeines MISQP-Verfahrens und Trust-Regions effizient gelost werden.Relaxierung ist nicht erforderlich.


Date post:	18-Oct-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Zur Stabilit - dynardo.de€¦ · Zur Stabilit ¨ at von SQP-Verfahren und zur L ¨ osung globaler...

Documents