Dual d’un problème d’optimisation quadratique

Positif

Salut à @tous ;

je considère $Y \in \mathbf{R}^{m \times 1},\  X \in \mathbf{R}^{m \times p} $ et ma variable est $\beta \in \mathbf{R}^p $. Ma fonctionnelle est $|| Y - X \beta ||^2$ que je développe en $\beta^T \cdot X^T X \cdot \beta - 2 \beta^T \cdot X^T Y + ||Y||^2$.

$ \min_{\beta}   \beta^T \cdot X^T X \cdot \beta - 2 \beta^T \cdot X^T Y + ||Y||^2 $
$ \mathrm{s.t} \ || \beta ||^2 \leq t $,

avec $t > 0$ une constante.

Donc c’est un problème

$ \min_{\beta} \max_{\alpha} \beta^T \cdot X^T X \cdot \beta - 2 \beta^T \cdot X^T Y + ||Y||^2 + \alpha ( t - \beta^T I_p \beta ) . $

La forme duale devient :

$ \min_{\alpha} \max_{\beta} \beta^T \cdot X^T X \cdot \beta - 2 \beta^T \cdot X^T Y + ||Y||^2 + \alpha ( t - \beta^T I_p \beta )  $

On va donc chercher le minimum de $  \beta^T \cdot X^T X \cdot \beta - 2 \beta^T \cdot X^T Y - \alpha \beta^T I_p \beta = \beta^T ( X^T X - \alpha I_p ) \beta - 2 \beta^T X^T Y $. Il est atteint en $ ( X^TX - \alpha I_p)^{-1} X^T Y $.

En remplaçant j’arrive à :

$\min_{\alpha} (X^TY)^T ( X^T X - \alpha I_p) X^TY -\alpha t $

Comment progresser, maintenant ? Faut-il dériver par rapport au réel $\alpha$ pour essayer de trouver une solution ? 

Positif

Contexte : dans Elements of Statistical Learning les auteurs disent que le ridge de la regression linéaire est équivalent au problème que je propose via le passage au dual, avec une correspondance entre $t$ et $\lambda$. Malheureusement il n’y a pas de preuve et je bloque dessus.

Dagothur

Intuitivement, dans le problème de minimisation

$ \min_{\beta}   ||Y-X\beta||^2$ $ \mathrm{s.t} \ || \beta ||^2 \leq t$

le min devrait être atteint sur le bord de la sphère $||\beta||^2\leq t$. Je vais supposer que c'est vrai, alors le problème équivaut à

$ \min_{\beta}   ||Y-X\beta||^2$ $ \mathrm{s.t} \ || \beta ||^2 = t$

Puis on résout par la méthode des multiplicateurs de Lagrange et la forme de la solution qu'on obtient est la même que celle qui serait obtenue si on résolvait un problème Ridge (avec la constante dans la formulation Ridge appropriée)

Positif

Merci @Dagothur mais je me pose donc une autre question. Disons que $\beta_0$ est la solution du problème non contraint, avec $t=+\infty$ par exemple. Si je fixe $t = 2 ||\beta_0||^2$ je ne vais pas saturer la contrainte. Je cherche donc comment retrouver la formulation du ridge via les multiplicateurs de Lagrange ou le dual.

Positif

J’ai appliqué la méthode de @Dagothur. Voici ce que j’obtiens : le lagrangien associé au problème est $\mathcal{L}( \beta , \alpha) = \beta^T ( X^T X ) \beta - 2 \beta^T ( X^T Y ) + \alpha ( t - \beta^T \beta ) $ (à la constante $||Y||^2  $ près).  Les conditions du premier ordre sont :

1 - $\partial_{\beta} \mathcal{L} = 0 : 2 X^T X \beta - 2 X^T Y - 2 \alpha \beta = 0 $

2 - $ \partial_{\alpha} \mathcal{L} = 0 :  \alpha ( t - \beta^T \beta ) = 0. $

Si $\alpha$ est nul, on retombe sur la classique régression linéaire. Supposons donc $\alpha$ non nul. L’équation 1- nous donne $ \beta = ( X^T X - \alpha I_p )^{-1} X^T Y $ ce qui est *presque* la forme close du ridge. Hum, il me faudrait montrer que  la constante $\alpha$ est négative pour cela. Toujours en prenant 1- mais en multipliant par $\beta^T$ j’obtiens : \[ \beta^T X^T X \beta - 2 \beta^T X^T Y = \alpha t .\]
Soit $ || X \beta - \frac12 Y ||^2 - \frac14 ||Y||^2 = \alpha t $.

Mais impossible d’aller plus loin. Je suis triste.

Dagothur

Je vais détailler mon raisonnement. Pour clarifier, je pose $f(\beta)=||X\beta-Y||^2$ et $g(\beta)=||\beta||^2$.

Le problème d'optimisation s'écrit en fonction de $f$ et $g$ comme $\min_{\beta} f(\beta)$ avec contrainte $g(\beta)=t$

Soit $\beta$ un point où le minimum est atteint. Par la théorie des multiplicateurs de Lagrange, on sait qu'il existe $\lambda$ réel tel que

$\nabla f(\beta)+\lambda \nabla g(\beta)=0$.

Or $\nabla f(\beta)=2 X^{T}X\beta-2X^{T}Y$ et $\nabla g(\beta)=2\beta$. Donc en réinjectant dans l'égalité plus haut

$X^{T}X\beta-X^{T}Y+\lambda\beta=0$ donc $(X^{T}X+\lambda I)\beta=X^{T}Y$

Et effectivement, là comme ça, je ne vois pas trop comment montrer que $\lambda$ est forcément positif, ni comment le relier à $t$.

Dagothur

Hum en fait après réflexion, il existe des situations dans lesquelles on doit forcément avoir $\lambda<0$ (en reprenant mes notations précédentes). En effet supposons par l'absurde $\lambda\geq 0$ quelque soit $t$. Je vais montrer qu'on a une impossibilité si on prend $t$ très grand. Je commence par diagonaliser $X^{T}X$. Soit $P$ orthogonale telle que $X^{T}X = P^{T}DP$ où $D$ est la matrice diagonale de valeurs propres $\lambda_1, ..., \lambda_n$ toutes strictement positives.

Alors $\beta = (X^{T}X+\lambda I)^{-1}X^{T}Y=P^{T}(D+\lambda I)^{-1}PX^{T}Y$. Si on peut borner $(D+\lambda I)^{-1}$, on en déduit que $\beta$ est borné ce qui contredit $t$ très grand (en effet $t$ impose $||\beta||^2$). Or $(D+\lambda I)^{-1}$ est une matrice diagonale de coefficients $0\leq(\lambda_i+\lambda)^{-1} \leq \max_{i}{\lambda_i^{-1}}$ car $\lambda$ est supposé positif, ce qui établit donc comme annoncé le caractère borné de $(D+\lambda I)^{-1}$.

Bibix

Ben c'est justement pour cela qu'il y a une relation à respecter entre $\lambda$ et $t$.

Dagothur

La relation étant grosso modo :

- quand $t$ tend vers $0$, $\lambda$ tend vers $+\infty$

- quand $t$ tend vers $+\infty$, $\lambda$ tend vers $-\lambda_1$ où $\lambda_1$ est la plus petite valeur propre de $X^{T}X$