Ein bisschen über konische Dualität

Beim Studium theoretischer Kurse in maschinellem Lernen (Mathematik, Wirtschaft, Optimierung, Finanzen usw.) wird häufig das Konzept eines „dualen Problems“ gefunden.

Doppelte Aufgaben werden häufig verwendet, um niedrigere (oder obere) Schätzungen für die Zielfunktion bei Optimierungsproblemen zu erhalten. Darüber hinaus hat das Doppelproblem für fast jede aussagekräftige Aussage des Optimierungsproblems eine aussagekräftige Interpretation. Das heißt, wenn Sie mit einem wichtigen Optimierungsproblem konfrontiert sind, ist höchstwahrscheinlich auch das doppelte Problem wichtig.

In diesem Artikel werde ich über konische Dualität sprechen. Diese Art der Konstruktion doppelter Aufgaben wird meiner Meinung nach zu Unrecht der Aufmerksamkeit beraubt ...

Nächste matan ...

Wie werden normalerweise doppelte Aufgaben aufgebaut?

Es sei ein Optimierungsproblem angegeben:

$$

$$\ min_ {x \ in R ^ n} f (x) \\ f_i (x) \ leq 0, \ quad 1 \ leq i \ leq k \\ h_i (x) = 0, 1 \ leq i \ leq m$$

Die Doppelaufgabe ist nach folgendem Schema aufgebaut:

• Baue Lagrangian

$$

$$L (x, \ lambda, \ mu) = f (x) + \ sum_ {i = 1} ^ k \ lambda_i f_i (x) + \ sum_ {i = 1} ^ m \ mu_i h_i (x)$$

• Bauen Sie eine Doppelfunktion auf

$$

$$g (\ lambda, \ mu) = \ inf_x L (x, \ lambda, \ mu)$$

• Holen Sie sich eine doppelte Aufgabe

$$

$$\ max _ {\ lambda, \ mu} g (\ lambda, \ mu) \\ \ lambda \ geq 0$$

Die Hauptschwierigkeit in diesem Schema wird im Suchschritt verdrahtet $$$\ inf_x L (x, \ lambda, \ mu)$ .

Wenn das Problem nicht konvex ist, ist dies ein Sarg - im allgemeinen Fall kann es nicht in Polynomzeit gelöst werden (wenn $$$P \ neq NP$ ) und solche Probleme in diesem Artikel werden wir in Zukunft nicht mehr ansprechen.

Angenommen, das Problem ist konvex, was dann?

Wenn das Problem glatt ist, können wir die Optimalitätsbedingung erster Ordnung verwenden $$$\ nabla_x L (x, \ lambda, \ mu) = 0$ . Wenn aus dieser Bedingung alles in Ordnung ist, ergibt sich daraus oder $$$x (\ lambda, \ mu) = \ arg \ min_x L (x, \ lambda, \ mu)$ und $$$g (\ lambda, \ mu) = L (x (\ lambda, \ mu), \ lambda, \ mu)$ oder direkt funktionieren $$$g (\ lambda, \ mu)$ .

Wenn das Problem nicht glatt ist, könnten wir ein Analogon der Bedingung erster Ordnung verwenden $$$0 \ in \ partielle_x L (x, \ lambda, \ mu)$ (hier $$$\ partielle_x L (x, \ lambda, \ mu)$ bezeichnet eine Subdifferenz einer Funktion $$$L (x, \ lambda, \ mu)$ ) ist dieses Verfahren jedoch in der Regel viel komplizierter.

Manchmal gibt es ein äquivalentes "reibungsloses" Optimierungsproblem, und man kann ein duales dafür konstruieren. Für die Verbesserung der Struktur (von nicht glatt zu glatt) müssen Sie jedoch in der Regel immer eine Erhöhung der Abmessung zahlen.

Konische Dualität

Es gibt einige Optimierungsaufgaben (Beispiele unten), die die folgende Darstellung zulassen:

$$

$$\ min_ {x \ in R ^ n} c ^ Tx \\ Ax + b \ in K$$

wo $$$A$ - Matrix $$$b$ - Vektor $$$K$ - nicht entarteter konvexer Kegel.

In diesem Fall kann die Doppelaufgabe nach dem folgenden Schema konstruiert werden:

Die Doppelaufgabe ist nach folgendem Schema aufgebaut:

• Baue Lagrangian

$$

$$L (x, \ Lambda) = c ^ Tx + \ Lambda ^ T (Ax + b)$$

• Bauen Sie eine Doppelfunktion auf

$$

$$g (\ lambda) = \ inf_x L (x, \ lambda) = \ begin {Fälle} \ lambda ^ T b, \ quad c + A ^ T \ lambda = 0 \\ - \ infty, \ quad c + A. ^ T \ lambda \ neq 0 \ end {Fälle}$$

• Holen Sie sich eine doppelte Aufgabe

$$

$$\ max _ {\ lambda} b ^ T \ lambda \\ c + A ^ T \ lambda = 0 \\ - \ lambda \ in K ^ *$$

Wo ist der konjugierte Kegel? $$$K ^ *$ für Kegel $$$K$ definiert als $$$K ^ * = \ left \ {y \ in R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ in K \ right \}$ .

Wie wir sehen, wurde die gesamte Komplexität der Konstruktion des Doppelproblems auf die Konstruktion des Doppelkegels übertragen. Aber die Freude ist, dass es einen guten Kalkül für die Konstruktion von Doppelkegeln gibt und sehr oft ein Doppelkegel sofort ausgeschrieben werden kann.

Beispiel

Angenommen, wir müssen ein duales Optimierungsproblem für das Problem konstruieren:

$$

$$\ min_ {x \ in R ^ n} \ | x \ | _2 + \ | x \ | _1 \\ Ax \ geq b$$

Hier $$$\ | x \ | _1 = \ sum_ {i = 1} ^ n | x_i |$ , $$$\ | x \ | _2 = \ sqrt {\ sum_ {i = 1} ^ n x_i ^ 2}$

Das Erste, was Sie bemerken können: Die Zielfunktion kann immer linear gemacht werden!

Vielmehr gibt es bei einer linearen Zielfunktion immer ein äquivalentes Problem:

$$

$$\ min_ {x \ in R ^ n, y \ in R, z \ in R} y + z \\ \ | x \ | _2 \ leq y \\ \ | x \ | _1 \ leq z \\ Ax \ geq b$$

Jetzt müssen Sie ein wenig geheimes Wissen verwenden: viele

$$

$$K_1 = \ {(x, t) \ in R ^ n \ mal R | \ quad \ | x \ | _1 \ leq t \}$$

und

$$

$$K_2 = \ {(x, t) \ in R ^ n \ mal R | \ quad \ | x \ | _2 \ leq t \}$$

sind konvexe Zapfen.

So kommen wir zur äquivalenten Notation des Problems:

$$

$$\ min_ {x \ in R ^ n, y \ in R, z \ in R} y + z \\ I_ {n + 1} \ begin {pmatrix} x \\ y \ end {pmatrix} + 0_ {n +1} \ in K_2 \\ I_ {n + 1} \ begin {pmatrix} x \\ z \ end {pmatrix} + 0_ {n + 1} \ in K_1 \\ Ax-b \ in R _ + ^ k$$

Jetzt können wir sofort ein doppeltes Problem aufschreiben:

$$

$$\ max _ {\ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda_i + \ mu_i + [A ^ T \ nu] _i = 0, \ quad 1 \ leq i \ leq n \\ \ lambda_ { n + 1} + 1 = 0 \\ \ mu_ {n + 1} +1 = 0 \\ - \ lambda \ in K_2 ^ * (= K_2) \\ - \ mu \ in K_1 ^ * (= K _ {\ infty}) \\ - \ nu \ in R ^ k _ +$$

oder, um ein wenig zu vereinfachen,

$$

$$\ max _ {\ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda + \ mu + A ^ T \ nu = 0 \\ \ | \ lambda \ | _2 \ leq 1 \\ \ | \ mu \ | _ {\ infty} \ leq 1 \\ - \ nu \ in R ^ k _ +$$

wo $$$\ | \ mu \ | _ {\ infty} = \ max_ {i} | \ mu_i |$ .

Links für weitere Studien:

• S. Boyd & L. Vanderberghe, Konvexe Optimierung, 2.6 (S. 51)
• A. Ben-Tall und L. El Ghaoui und A. Nemirovski, Robust Optimization, App. A.