Minimum sous contraintes non linéaires

tonio0

Bonjour,

je considère $\alpha_1,\alpha_2,\alpha_3,\alpha_4 \in [0,1]^4$. J'aimerai montrer la minoration suivante (qui est validée empiriquement) :

\begin{multline*}
\max \{(1-\alpha_2)\alpha_3 + \alpha_2(1-\alpha_3)\alpha_4+(1-\alpha_3)(1-\alpha_4),(1-\alpha_3)\alpha_4+(1-\alpha_1)(1-\alpha_3)(1-\alpha_4), \alpha_3 +(1-\alpha_1)(1-\alpha_3)(1-\alpha_4)\} \\ \geq \frac{1}{2}
\end{multline*}


Je peux peut-être considérer tout à tour les deux cas suivants : $(1-\alpha_3)\alpha_4 \geq \alpha_3$ et $(1-\alpha_3)\alpha_4 \leq \alpha_3$, ce qui me permet de réduire le problème à l'étude de

\[
\min_{(1-\alpha_3)\alpha_4 \geq \alpha_3} \max \{(1-\alpha_2)\alpha_3 + \alpha_2(1-\alpha_3)\alpha_4+(1-\alpha_3)(1-\alpha_4),(1-\alpha_3)\alpha_4+(1-\alpha_1)(1-\alpha_3)(1-\alpha_4)\}
\]

et

\[
\min_{(1-\alpha_3)\alpha_4 \leq \alpha_3} \max \{(1-\alpha_2)\alpha_3 + \alpha_2(1-\alpha_3)\alpha_4+(1-\alpha_3)(1-\alpha_4), \alpha_3 +(1-\alpha_1)(1-\alpha_3)(1-\alpha_4)\}
\]

mais sinon j'ai un peu de mal à manipuler tout ça. Quelqu'un pourrait-il juste m'indiquer comment avancer un peu ?

Merci d'avance.

Au pif

Et si tu prenais $\alpha_1=\alpha_2=\alpha_3=\alpha_4=1$ ? A moins que le véritable énoncé ne soit pas celui que tu as écrit ?

tonio0

Avec $\alpha_1 = \alpha_2=\alpha_3 = \alpha_4$ alors on se retrouve avec $\max \{0,0,1\}$, ce qui est bien supérieur à 1/2. Mais j'aimerai bien montrer ça pour n'importe quel quadruplet.

Héhéhé0

Si ca atteint 1 sur un quadruplet particulier, alors en particulier le max est au moins 1 qui est bien supérieur à 1/2....

tonio0

Ok je comprends, je n'ai pas été assez précis. Mon problème est de montrer que :

\begin{multline*}
\min_{\alpha_1, \alpha_2,\alpha_3,\alpha_4, \in [0,1]^4}\max \Big \{(1-\alpha_2)\alpha_3 + \alpha_2(1-\alpha_3)\alpha_4+(1-\alpha_3)(1-\alpha_4),(1-\alpha_3)\alpha_4+(1-\alpha_1)(1-\alpha_3)(1-\alpha_4), \alpha_3 +(1-\alpha_1)(1-\alpha_3)(1-\alpha_4) \Big\} \\ \geq \frac{1}{2}
\end{multline*}

Welfar

Quel sens celà a-t-il? Sur quoi porte le max?

tonio0

Il y a trois expressions dans le max, $(1-\alpha_2)\alpha_3 + \alpha_2(1-\alpha_3)\alpha_4+(1-\alpha_3)(1-\alpha_4)$, $(1-\alpha_3)\alpha_4+(1-\alpha_1)(1-\alpha_3)(1-\alpha_4)$ et $\alpha_3 +(1-\alpha_1)(1-\alpha_3)(1-\alpha_4)$. Pour n'importe quel quadruplet $\alpha_1, \alpha_2,\alpha_3,\alpha_4, \in [0,1]^4$ je prend donc la plus grande de ces trois quantités. J'aimerai que cette valeur soit toujours plus grande que 1/2.

Est-ce plus clair comme cela : montrer que quelque soit $\alpha_1, \alpha_2,\alpha_3,\alpha_4, \in [0,1]^4$ alors
\begin{multline*}
\max \{(1-\alpha_2)\alpha_3 + \alpha_2(1-\alpha_3)\alpha_4+(1-\alpha_3)(1-\alpha_4),(1-\alpha_3)\alpha_4+(1-\alpha_1)(1-\alpha_3)(1-\alpha_4), \alpha_3 +(1-\alpha_1)(1-\alpha_3)(1-\alpha_4)\}\geq \frac{1}{2}
\end{multline*}

aurelpage

Salut,

je te propose l'approche suivante :

J'ai l'impression que c'est plus lisible avec les variables~$\beta_i = 1-\alpha_i$, les trois expressions dans le max deviennent alors $\beta_2(1-\beta_3)+(1-\beta_2)\beta_3(1-\beta_4)+\beta_3\beta_4 = (1-2\beta_3+\beta_3\beta_4)\beta_2 + \beta_3$, $\beta_3(1-\beta_4)+\beta_1\beta_3\beta_4$ et~$1-\beta_3+\beta_1\beta_3\beta_4$.
Comme~$\beta_2$ n'intervient que dans la première expression, on peut commencer par minimiser suivant cette variable. La première expression étant affine en~$\beta_2$, on obtient en regardant si cette fonction est croissante ou décroissante que son min pour~$\beta_2$ dans~$[0,1]$ est~$\beta_3+\min(0,1-2\beta_3+\beta_3\beta_4)$.
On observe maintenant que~$\beta_4$ n'apparaît que dans des expressions~$\beta_3\beta_4$ et~$\beta_1$ seulement dans des expressions~$\beta_1\beta_3\beta_4$. En posant~$\gamma_4 = \beta_3\beta_4$ puis~$\gamma_1 = \beta_1\gamma_4$ on obtient que le minimum que tu cherches est aussi le minimum sur les~$\gamma_1,\beta_3,\gamma_4$ satisfaisant~$0\le\gamma_1\le\gamma_4\le\beta_3\le 1$ du maximum des trois expressions~$\beta_3+\min(0,1-2\beta_3+\gamma_4)$, $\beta_3-\gamma_4+\gamma_1$, $1-\beta_3+\gamma_1$.
Comme toutes les expressions sont linéaires en les variables et que les contraintes sont linéaires, ta question est ramenée à un nombre fini de minimisations de fonction linéaire sur un polytope convexe, que tu peux faire calculer à un logiciel (ou les faire à la main).

Aurel

tonio0

Encore une fois, merci Aurel ! Voici ce que j'ai fait pour l'instant.
1. $1-2\beta_3+\gamma_4 \geq 0$
Le but est donc de trouver\[
\min_{\beta,\gamma} \max \Big \{ \beta_3 , \beta_3 - \gamma_4 + \gamma_1, 1-\beta_3 +\gamma_1 \Big \}
\] sous les contraintes $1-2\beta_3+\gamma_4 \geq 0$ et $0\leq \gamma_1 \leq \gamma_4 \leq \beta_3 \leq 1$.
1.1 $\beta_3$ est le maximum
Mais comme $\beta_3 \geq 1-\beta_3 +\gamma_1$ alors $2 \beta_3 \geq 1+ \gamma_1 \geq 1$.
1.2 $\beta_3 - \gamma_4 + \gamma_1$ est le maximum
Alors $\beta_3 - \gamma_4 + \gamma_1 \geq 1-\beta_3 +\gamma_1$, d'où $2\beta_3 \geq 1+ \gamma_4 \geq 1$.
1.3 $1-\beta_3 +\gamma_1 $ est le maximum
Alors $1-\beta_3 +\gamma_1 \geq \beta_3$, d'où $\beta_3 \leq 1/2(1+\gamma_1)$, d'où $1-\beta_3 +\gamma_1 \geq 1 -1/2(1+\gamma_1)+\gamma_1 = 1/2(1+\gamma_1) \geq 1/2$.

tonio0

Pardon il y a une petite erreur dans 1.2, mais je pense que j'ai compris comment ça marchait.

aurelpage

En fait tu peux éliminer 1.2 car~$\gamma_1-\gamma_4\le 0$ donc~$\beta_3\ge \beta_3-\gamma_4+\gamma_1$. ;-)

tonio0

Oui exactement. Quand on regarde le cas que je n'ai pas traité il y a aussi un des trois terme qui disparaît. Aurel, disons que tu as résolu le problème car tu es astucieux et a réussi à simplifier à l'aide de changements de variables. Par curiosité, y-a-t-il un autre moyen de s'y prendre quand on est moins astucieux et qu'on veut faire les choses à la main?

aurelpage

A ma connaissance, l'optimisation polynomiale en toute généralité est un problème difficile. Si ça tu veux en apprendre plus, cette vidéo est probablement intéressante (Lasserre est un expert du sujet). Mais c'est toujours une bonne idée de profiter des particularités de ton problème lorsqu'il n'y a pas de solution systématique efficace.

tonio0

Ok, encore merci Aurel !

aurelpage

De rien