Un peu sur la dualité conique

Lorsque l'on étudie des cours théoriques en machine learning (mathématiques. Economie, optimisation, finance, etc.), la notion de «double problème» se retrouve souvent.

Les tâches doubles sont souvent utilisées pour obtenir des estimations inférieures (ou supérieures) pour la fonction cible dans les problèmes d'optimisation. De plus, pour presque toutes les déclarations significatives du problème d'optimisation, le double problème a une interprétation significative. Autrement dit, si vous êtes confronté à un problème d'optimisation important, son double est également très probablement important.

Dans cet article, je parlerai de la dualité conique. Cette façon de construire des tâches duales, à mon avis, est à juste titre privée d'attention ...

Matan suivant ...

Comment les tâches doubles sont-elles généralement construites?

Soit un problème d'optimisation donné:

$$

$$\ 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$$

La double tâche est construite selon le schéma suivant:

• Construire 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)$$

• Construire une double fonction

$$

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

• Obtenez une double tâche

$$

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

La principale difficulté de ce schéma est liée à l'étape de recherche $$$\ inf_x L (x, \ lambda, \ mu)$ .

Si le problème n'est pas convexe, alors c'est un cercueil - dans le cas général, il ne peut pas être résolu en temps polynomial (si $$$P \ neq NP$ ) et de tels problèmes dans cet article, nous ne les aborderons pas à l'avenir.

Supposons que le problème soit convexe, alors quoi?

Si le problème est lisse, nous pouvons utiliser la condition d'optimalité de premier ordre $$$\ nabla_x L (x, \ lambda, \ mu) = 0$ . De cette condition, si tout va bien, il s’avère déduire ou $$$x (\ lambda, \ mu) = \ arg \ min_x L (x, \ lambda, \ mu)$ et $$$g (\ lambda, \ mu) = L (x (\ lambda, \ mu), \ lambda, \ mu)$ ou fonctionner directement $$$g (\ lambda, \ mu)$ .

Si le problème n'est pas lisse, alors nous pourrions utiliser un analogue de la condition de premier ordre $$$0 \ in \ partial_x L (x, \ lambda, \ mu)$ (ici $$$\ partial_x L (x, \ lambda, \ mu)$ désigne un sous-différentiel d'une fonction $$$L (x, \ lambda, \ mu)$ ), cependant, cette procédure est généralement beaucoup plus compliquée.

Parfois, il y a un problème d'optimisation «fluide» équivalent et on peut en construire un double. Mais pour l'amélioration de la structure (de non lisse à lisse), en règle générale, vous devez toujours payer une augmentation de dimension.

Dualité conique

Il existe plusieurs tâches d'optimisation (exemples ci-dessous) qui admettent la représentation suivante:

$$

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

où $$$A$ - matrice $$$b$ - vecteur $$$K$ - cône convexe non dégénéré.

Dans ce cas, la double tâche peut être construite selon le schéma suivant:

La double tâche est construite selon le schéma suivant:

• Construire Lagrangian

$$

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

• Construire une double fonction

$$

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

• Obtenez une double tâche

$$

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

où est le cône conjugué $$$K ^ *$ pour cône $$$K$ défini comme $$$K ^ * = \ left \ {y \ in R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ in K \ right \}$ .

Comme nous le voyons, toute la complexité de la construction du double problème a été transférée à la construction du double cône. Mais la joie est qu'il existe un bon calcul pour construire des cônes doubles et très souvent un cône double peut être écrit immédiatement.

Exemple

Supposons que nous devons construire un problème d'optimisation double pour le problème:

$$

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

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

La première chose que vous pouvez remarquer: la fonction objectif peut toujours être rendue linéaire!

Au contraire, il y a toujours un problème équivalent avec une fonction objectif linéaire:

$$

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

Maintenant, vous devez utiliser un peu de connaissances secrètes: beaucoup

$$

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

et

$$

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

sont des cônes convexes.

Ainsi, nous arrivons à la notation équivalente du problème:

$$

$$\ 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$$

Maintenant, nous pouvons immédiatement écrire un double problème:

$$

$$\ 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 \ dans R ^ k _ +$$

ou, pour simplifier un peu,

$$

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

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

Liens pour une étude plus approfondie:

• S. Boyd & L. Vanderberghe, Optimisation convexe, 2.6 (p. 51)
• A. Ben-Tall et L. El Ghaoui et A. Nemirovski, Robust Optimization, App. Un