Une introduction à l'optimisation robuste [... et une petite liste de courses que j'ai oublié ...]

Comment déterminer combien de personnes doivent être embauchées pour une nouvelle réalisation, quoi exactement pour le remplir et où placer un produit particulier? Plus l'entreprise est grande, plus l'incertitude est grande et plus l'erreur est coûteuse. Vaincre le chaos et choisir la meilleure solution est l'une des tâches de l'équipe de science des données. Et comme les mathématiques sont à la base de l'analyse des données, nous allons commencer avec.

Dans cet article, nous considérerons les problèmes d'optimisation avec l'incertitude des données et leur approximation par des problèmes convexes déterministes. C'est l'une des principales astuces d'une optimisation robuste - une technique qui vous permet de faire face à des tâches d'optimisation trop sensibles aux changements dans les données d'entrée.

La question de la sensibilité est très importante. Pour les tâches dont la qualité de la solution dépend peu des évolutions des données, il est plus simple d'utiliser l'optimisation stochastique habituelle. Cependant, dans les tâches à haute sensibilité, cette approche donnera un mauvais résultat. Il existe de nombreuses tâches de ce type dans les finances, la gestion de la chaîne d'approvisionnement, la conception et de nombreux autres domaines.

Et oui, c'est un exemple de poste où la complexité croît de façon exponentielle (poubelle déjà) ...

Que signifie «résoudre» le problème d'optimisation?

Commençons par un bref rappel.

La tâche d'optimisation en général ressemble à ceci:

$$

$$\ min_ {x \ in R ^ n} f (x) \\ s.t. \\ x \ in X$$

Ici $$$f (x)$ appelé la fonction objectif, et $$$X$ - un ensemble valide.

En résolvant le problème d'optimisation, nous entendons un tel point $$$x ^ * \ dans X$ pour lequel il est exécuté:

$$

$$f (x) - f (x ^ *) \ geq 0, \ quad \ forall x \ in X$$

Il s'agit du concept standard pour résoudre le problème d'optimisation sans incertitude.

Qu'est-ce qu'un problème d'optimisation avec incertitude?

Il est temps de s'interroger sur l'origine de la fonction $$$f (x)$ et limitations $$$X$ .

Très utile à partager

• logique structurelle du problème (en d'autres termes, quelles fonctions sont utilisées),
• limitations techniques (indépendantes de la logique ou des données humaines),
• paramètres qui sont évalués à partir des données.

Par exemple, un homme d'affaires est venu chez nous et a montré le problème de programmation linéaire:

$$

$$\ min_ {x \ in R ^ 2} 2,16 x_1 + 3,7 x_2 \\ s.t. \\ 0,973 x_1 + 2,619 x_2 \ leq 3,32 \\ x_1 \ geq 0, x_2 \ geq 0$$

Vous voyez cette tâche pour la première fois. Un homme aussi (peut-être pas, mais en blouson bleu, tout est si abstrait!). Vous ne connaissez pas la signification des variables. Mais même maintenant, avec beaucoup de confiance, nous pouvons dire que:

1. La tâche est très probablement linéaire, car quelqu'un l'a décidé. La linéarité est la structure qu'une personne a choisie.
2. Limitations $$$x_1 \ geq 0, x_2 \ geq 0$ sont techniques. Autrement dit, ils provenaient de la "physique" et non de données (par exemple, les ventes ne peuvent pas être négatives).
3. Coefficients spécifiques $$$\ {0.973, 2.619, 3.32 \}$ en limitant $$ dans notre exemple ont été évalués à partir des données. Autrement dit, au début, quelqu'un a dit que la variable $$$x_1$ associé à une variable $$$x_2$ , il a ensuite été dit que la relation est linéaire et, enfin, les coefficients de l'équation de couplage ont été estimés à partir des données. Il en va de même pour les cotes. $$$\ {2.16, 3.7 \}$ dans la fonction objectif.

Lorsque nous parlons de tâches avec incertitude, nous ciblons précisément l'incertitude des paramètres estimés à partir des données. Nous ne touchons pas aux limitations techniques ou au choix initial de la structure du problème.

Revenons à notre histoire. Nous avons un problème linéaire, quelqu'un a estimé les coefficients en quelque sorte. Si nous avions raison sur la nature des coefficients dans la fonction, alors en fait, on nous a demandé de résoudre le problème pour un scénario de développement d'événements (une instance spécifique du problème).

Parfois, cela nous suffit et nous le résolvons simplement.

Cependant, résoudre parfois un problème pour un scénario est une idée stupide (par exemple, si la solution est très sensible à la variation des données).

Que faire dans ce cas et comment modéliser l'incertitude des données?

Tout d'abord, notez que l'incertitude des données peut toujours être transférée de la fonction objectif aux contraintes ou vice versa. Comment faire, regardez sous la coupe.

Optimisation stochastique, en ligne, robuste et liste de produits

Nous pouvons avoir de nombreux scénarios d'incertitude, ainsi que des options pour en faire quoi. Nous illustrons plusieurs approches standard avec un exemple simple.

Je ne sais pas comment est la situation avec un lecteur respecté, mais ici je suis marié (avec succès) et je vais régulièrement à l'épicerie. Avec une feuille, bien sûr (donne l'invulnérabilité des achats impulsifs). Parfois non seulement au magasin, mais au conditionnel Auchan, où c'est moins cher, mais où aller loin.

Nous allons modéliser cette situation: nous sommes venus à Auchan avec une feuille entre les mains pour faire du shopping.

Attention, première question: comment modéliser?

Entrée: informations sur les produits à acheter et la quantité requise.

Pour plus de commodité, nous pouvons considérer la brochure comme un vecteur entier non négatif $$$y \ in Z _ + ^ n$ .

Comme variables, nous prenons, respectivement, un vecteur entier non négatif $$$x \ in Z _ + ^ n$ - combien et quels produits nous achèterons finalement (notre solution).

Le point est petit - prendre une sorte de fonction objective $$$f (x, y)$ , qui indique à quel point nous avons fait une erreur dans le choix des produits.

Selon le contexte, le type de fonction peut changer, mais il existe certaines exigences de base pour cela:

• Fonction $$$f (x, y)$ devrait avoir un minimum $$$x ^ * = \ arg \ min_ {x \ dans R ^ n} f (x, y) = y$ (c'est-à-dire que dans l'idéal, nous achèterons exactement ce qui est écrit dans la brochure)
• Fonction $$$f (x, y)$ doit être convexe $$$x$ (et de préférence lisse) - pour pouvoir calculer efficacement $$$min$ .

Ainsi, nous obtenons le problème:

$$

$$min_ {x \ in R ^ n} f (x, y)$$

Imaginez maintenant que la feuille reste à la maison ...

Donc, avec une remarque, nous sommes entrés dans le monde des tâches avec incertitude.

Alors, que faire si dans la tâche $$$min_ {x \ in R ^ n} f (x, y)$ inconnu de nous $$$y$ ?

La réponse, encore une fois, dépend du contexte.

Optimisation stochastique

L'optimisation stochastique (généralement) implique

• L'incertitude dans les données est de nature stochastique. Connaissance complète de la distribution probabiliste des valeurs des paramètres non déterministes
• Les limites, y compris l'incertitude, sont faibles

Dans notre exemple, si nous le modélisons en utilisant l'optimisation stochastique, nous dirions

• D'accord, je ne sais pas ce qui était écrit dans la brochure, mais je marche avec des tracts depuis 8 ans maintenant, et j'ai suffisamment de connaissances sur la distribution du vecteur $$$y$
• Même si je fais une erreur de choix (c'est-à-dire avec $$$x$ ), en rentrant chez moi, je découvre le vrai $$$y$ et, si je suis complètement en sécurité, je vais descendre à Pyaterochka et acheter là-bas, bien que plus cher.
• Maintenant, je vais en choisir un $$$x$ , ce qui minimisera une sorte d'agrégat de la fonction objectif d'origine et d'éventuelles «amendes» pour l'erreur.

Cela nous conduira à cette tâche:

$$

$$\ min_ {x \ in R ^ n} E_y [f (x, y) + \ psi (y, z)] \\ s.t. \\ x + z \ geq y$$

Notez que dans cette tâche, nous prenons de facto deux fois des décisions: premièrement, la principale décision d'achat chez Auchan, dont nous sommes responsables $$$x$ , puis «correction d'erreur» avec $$$z$ .

Les principaux problèmes de cette approche sont:

• Il n'y a souvent aucune information sur la distribution des paramètres.
• Les limitations peuvent être sévères (pour les tâches à haut risque - mort, ruine, apocalypse nucléaire ou zombie, etc.)
• Il n'est pas toujours possible de «corriger les erreurs» (une décision est prise une fois) ou vice versa, des décisions sont souvent prises (dans ce cas, de nombreuses intégrales imbriquées apparaîtront, et il sera très difficile de les compter).

Optimisation en ligne

L'optimisation en ligne est un cadre qui explore la prise de décision cohérente. L'une des approches standard de la modélisation dans ce cadre est les bandits multi-armés, qui ont déjà fait l'objet de nombreuses publications sur Habré.

Dans le cadre de notre exemple de jouet, nous voudrions:

• n'avait pas (et n'a jamais utilisé) de notice
  
• et à la maison, nous serions félicités / grondés pour les produits que nous avons achetés (en même temps, nous ne pouvions que deviner l'ensemble souhaité)
• la tâche serait d’apprendre le plus rapidement possible à acheter de la nourriture ainsi que son ancien prince imaginaire, enfin, ou le meilleur ami du fils de sa mère.

Optimisation robuste

L'optimisation robuste est une extension logique de l'idée d'une solution minimax.

Idéalement, nous devrions dès maintenant prendre une décision qui sera toujours acceptable, quelles que soient les circonstances. Les concepteurs de pots, de fers à repasser et de réfrigérateurs en URSS l'ont fait dans le cadre d'une optimisation robuste: le produit devrait fonctionner même s'il a été utilisé pendant 20 ans comme principal outil d'extermination des mutants apparus après la guerre nucléaire (il doit également survivre).

De plus, je veux que la tâche soit poussée dans un solveur ordinaire - et ils ne comprennent pas les restrictions "pour toute implémentation d'une variable aléatoire" (s'il n'y a pas un nombre fini de ces implémentations).

Dans le cas d'un dépliant, la décision doit être prise ici et maintenant et rester valable en toutes circonstances:

$$

$$\ min_ {x \ in R ^ n, t \ in R} t \\ s.t. \\ f (x, y) \ leq t \ quad \ forall y \\ x \ geq y \ quad \ forall y$$

Il est clair que même dans cet exemple de jouet, si vous n'avez besoin de rien de $$$y$ , alors aucune solution significative ne fonctionnera.

Alors, comment gérez-vous ces tâches?

Création d'une version robuste d'une tâche à l'aide de l'exemple de tâche LP

Considérons un problème d'optimisation linéaire avec incertitude:

$$

$$\ min_ {x \ in R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

Paramètres $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ ont été dérivées de données et incluent l'incertitude.

Hypothèse 1: plusieurs valeurs (implémentations) $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ peut être paramétré, c'est-à-dire il y a $$$\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix}, \ begin {pmatrix} c_1 ^ T, d_1 \\ A_1, b_1 \ end {pmatrix}, \ dots, \ begin {pmatrix } c_k ^ T, d_k \\ A_k, b_k \ end {pmatrix}$ que toute mise en œuvre de données $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ réside dans l'ensemble:

$$

$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix} \ in U = \ left \ {\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \ begin {pmatrix} c_i ^ T, d_i \\ A_i, b_i \ end {pmatrix} | \ quad \ zeta \ dans Q \ sous-ensemble R ^ k \ right \}$$

Ici $$$\ begin {pmatrix} c ^ T_0, d_0 \\ A_0, b_0 \ end {pmatrix}$ sont appelés données «nominales», et $$$\ begin {pmatrix} c ^ T_i, d_i \\ A_i, b_i \ end {pmatrix} \ quad (1 \ leq i \ leq k)$ - «changements».



Nous savons déjà que toute l'incertitude du problème peut être levée dans les limites. Faisons-le.

Nous avons le problème

$$

$$\ min_ {x \ in R ^ n, t \ in R} t \\ st \\ c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ in U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ in U \\ $$

Version robuste de la tâche

Il est maintenant temps pour l'une des astuces les plus cool de l'optimisation robuste - comment passer d'un nombre infini de contraintes à un ensemble fini de bonnes contraintes.

Pour commencer, considérez un exemple simple lorsque

$$

$$Q = \ {\ zeta \ dans R ^ k | \ | \ zeta \ | _2 \ leq 1 \}$$

Toutes les restrictions dans le système

$$

$$c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ in U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ en U \\ $$

le même type - ce sont juste des inégalités linéaires. Apprenez à travailler avec un seul - apprenez à travailler avec tout le monde.

Par conséquent, nous considérons une restriction du type d'inégalité:

$$

$$a ^ Tx \ leq b \ quad \ forall (a, b) \ in U = \ {(a_0, b_0) + \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i, b_i) | \ quad \ zeta \ dans Q \} \\ (a_0 + \ sum_ {i = 1} ^ k \ zeta_i a_i) ^ Tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ in Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx \ quad \ forall \ zeta \ in Q \\ \ max _ {\ zeta \ dans Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx$$

Permettez-moi d'expliquer ce qui s'est passé.

Premièrement, nous avons transféré toutes les parties incertaines du côté gauche de l'inégalité; $$$\ zeta$ .
Après cela, nous avons examiné le pire des cas (pour chaque $$$x$ il est le sien).
En conséquence, nous avons obtenu le record suivant:

$$

$$g (x) = max _ {\ zeta \ in Q} f (x, \ zeta) \ leq b_0 - a_0 ^ Tx$$

.

L'étape suivante consiste à écrire une fonction explicite $$$g (x)$ . Pour ce faire, il suffit de résoudre le problème d'optimisation en $$$\ zeta$ et substituer l'optimal $$$\ zeta *$ :

$$

$$\ max _ {\ | \ zeta \ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) = \ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx - b_i) ^ 2}$$

ce qui conduit à l'inégalité:

$$

$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$$

Notez que l'inégalité résultante est convexe et tout $$$x$ le satisfaire satisfait l'original $$$a ^ Tx \ leq b$ pour toute mise en œuvre $$$(a, b) \ en U$ ...

Limitation $$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$ appelé la version robuste de la contrainte $$$a ^ Tx \ leq b \ quad \ forall (a, b) \ in U$ .

C'est l'un des principaux chevaux de bataille de l'optimisation robuste - l'approximation des contraintes de probabilité par un ensemble fini de contraintes convexes.

Que faire des contraintes plus complexes (non linéaires)?

Construire des versions robustes de contraintes en utilisant la dualité conique

Un grand nombre de contraintes non linéaires standard peuvent être représentées sous une forme conique (c'est-à-dire sous la forme $$$Axe + b \ en K$ où $$$K$ est un cône convexe fermé):

• Non-négativité $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ in R ^ n _ +$
• Restrictions des normes $$$\ | x \ | _p \ leq p \ quad \ leftrightarrow \ quad \ begin {pmatrix} x \\ p \ end {pmatrix} \ in K_p ^ n = \ left \ {(x, t) \ in R ^ n \ fois R_ + | \ quad \ | x \ | _p \ leq t \ right \}$
• Contraintes sur le caractère définitif positif de la matrice $$$x_1F_1 + \ points x_nF_n + G \ succeq 0$

Retour à des restrictions robustes.

Supposons que le problème d'optimisation par rapport à $$$\ zeta$ réussi à être réduit à une forme conique

$$

$$\ max _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx - b_i) \\ s.t \\ C \ zeta + d \ in K$$

Nous construisons un dual pour ce problème.

Il y a quelque temps, j'ai publié un article sur la dualité conique exactement afin de consacrer un peu moins d'attention à la technique de cet article.

$$

$$\ min _ {\ lambda} \ lambda ^ Td \\ st \\ C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k \\ \ lambda \ en K ^ *$$

Maintenant, c'est à la petite chose - le théorème de la dualité faible:

$$

$$\ max _ {[\ zeta: \ quad C \ zeta + d \ in K]} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) \ leq \ min _ {\ lambda \ in G} \ lambda ^ Td \\ où \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ in K ^ * \ right \}$$

Par conséquent, comme une approximation robuste de la contrainte initiale $$$a ^ Tx \ leq b, \ quad (a, b) \ in U$ la restriction peut être utilisée

$$

$$\ lambda ^ Td \ leq b_0 - a_0 ^ Tx \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ in K ^ * \ right \}$$

où $$$\ lambda$ même variable que $$$x$ .

Nous avons donc construit une contrainte robuste pour l'inégalité d'origine.

Conclusion

Nous avons examiné la technique d'approximation des mauvaises contraintes (stochastiques) par un ensemble de bonnes contraintes convexes. Cela peut être utile, par exemple, si:

• Vous ne voulez pas écrire vous-même des algorithmes, mais le solveur que vous utilisez ne sait pas comment travailler avec des contraintes de probabilité.
• Il y a un problème avec les paramètres stochastiques, tandis que l'optimum est très sensible aux fluctuations des données.
• Et, bien sûr, les tâches avec incertitude, où toutes les restrictions sont strictes (le prix de l'erreur est trop élevé)