10.8 Fonctions quadratiques

Dans cette section, nous étudions les fonctions quadratiques en utilisant la diagonalisation en base orthonormée.

10.8.1 Minimisation de fonction quadratique

Le problème visant à trouver une valeur réelle \(x\) minimisant une fonction quadratique \(f(x) = ax^2 + bx + c\), où \(a > 0\), est normalement étudié à l’école secondaire. On peut utiliser soit la méthode de complétion d’un carré ou le calcul différentiel afin de constater que la fonction atteint son minimum lorsque \(x = -\frac{b}{2a}.\)

Considérons maintenant un problème plus général. Pour \(\mathbf{A} \in \mathbb{R}^{n\times n},\) \(\mathbf{b} \in \mathbb{R}^{n}\) et \(c \in \mathbb{R},\) déterminons la valeur minimale (si elle existe) de la forme quadratique définie par \[P(\mathbf{x}) = \mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} + \mathbf{b}^\mathsf{T}\mathbf{x} + c.\]

Puisque \(\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} \in \mathbb{R},\) on doit avoir \((\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x})^\mathsf{T}= \mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x}.\) Mais \((\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x})^\mathsf{T}= \mathbf{x}^\mathsf{T}\mathbf{A}^\mathsf{T}(\mathbf{x}^\mathsf{T})^\mathsf{T}= \mathbf{x}^\mathsf{T}\mathbf{A}^\mathsf{T}\mathbf{x},\) d’où \[\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} = \mathbf{x}^\mathsf{T} \left(\frac{1}{2}(\mathbf{A}+\mathbf{A}^\mathsf{T})\right) \mathbf{x},\] ce qui revient à supposer, sans perte de généralité, que \(\mathbf{A}\) est symétrique puisque \(\frac{1}{2}(\mathbf{A}+\mathbf{A}^\mathsf{T})\) l’est.

D’après le théorème 10.5, il existe alors une matrice orthogonale \(\mathbf{U}\) et une matrice diagonale \(\mathbf{D}\) telles que \(\mathbf{A} = \mathbf{U}\mathbf{D}\mathbf{U}^\mathsf{T}\). En prenant \(\mathbf{y} = \mathbf{U}^\mathsf{T}\mathbf{x},\) nous obtenons \[\begin{align*} \mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} + \mathbf{b}^\mathsf{T}\mathbf{x} + c & = \mathbf{y}^\mathsf{T}\mathbf{U}^\mathsf{T} \mathbf{U}\mathbf{D} \mathbf{U}^\mathsf{T}\mathbf{U} \mathbf{y} + \mathbf{b}^\mathsf{T}\mathbf{U}\mathbf{y} + c \\ & = \mathbf{y}^\mathsf{T}\mathbf{D}\mathbf{y} + \mathbf{b}^\mathsf{T}\mathbf{U}\mathbf{y} + c \end{align*}\] La valeur minimum de \(P\) est donc égale à la valeur minimum de \[\mathbf{y}^\mathsf{T}\mathbf{D}\mathbf{y} + \mathbf{b}^\mathsf{T}\mathbf{U}\mathbf{y} + c.\] Mais \(\mathbf{D}\) est une matrice diagonale (ce n’était pas nécessairement le cas pour \(\mathbf{A}\)) et nous pouvons compléter le carré tel qu’illustré dans l’exemple suivant.

Exemple 10.9 Nous voulons déterminer la valuer minimale de la form quadratique \[f(x_1,x_2) = 3x_1^2 + 4x_1 x_2 + 3x_2^2 + x_1 - 2x_2,\] si elle existe. Notons que \[f(x_1, x_2) = \mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} + \mathbf{b}^\mathsf{T}\mathbf{x},\] où \(\mathbf{x} = \begin{bmatrix} x_1 \\ x_2\end{bmatrix},\) \(\mathbf{A} = \begin{bmatrix} 3 & 2 \\ 2 & 3\end{bmatrix}\) et \(\mathbf{b} = \begin{bmatrix} 1 \\ -2 \end{bmatrix}.\) Une diagonalisation en base orthonormée de \(\mathbf{A}\) est donnée par \(\mathbf{U} \mathbf{D} \mathbf{U}^\mathsf{T}\) où \(\mathbf{D} = \begin{bmatrix} 1 & 0 \\ 0 & 5 \end{bmatrix}\) et \(\mathbf{U} = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix}.\) Posons \(\mathbf{y} = \mathbf{U}^\mathsf{T}\mathbf{x}.\) On obtient alors la fonction quadratique \[\begin{align*} \mathbf{y}^\mathsf{T}\mathbf{D}\mathbf{y} + \mathbf{b}^\mathsf{T}\mathbf{U}\mathbf{y} & = y_1^2 + 5y_2^2 + \frac{3}{\sqrt{2}}y_1 - \frac{1}{\sqrt{2}} y_2 \\ & = \left(y_1+\frac{3}{2\sqrt{2}}\right)^2 + 5\left(y_2-\frac{1}{10\sqrt{2}}\right)^2 - \left(\frac{3}{2\sqrt{2}}\right)^2 - 5\left(\frac{1}{10\sqrt{2}}\right)^2 \\ & = \left(y_1+\frac{3}{2\sqrt{2}}\right)^2 + 5\left(y_2-\frac{1}{10\sqrt{2}}\right)^2 - \frac{23}{20}, \end{align*}\] dont la valeur minimale de \(-\frac{23}{20}\) est atteinte lorsque \(\begin{bmatrix} y_1 \\ y_2 \end{bmatrix} = \begin{bmatrix} -\frac{3}{2\sqrt{2}} \\ \frac{1}{10\sqrt{2}}\end{bmatrix}.\) Il s’ensuit que \(f(x_1,x_2)\) atteint sa valeur minimale de \(-\frac{23}{20}\) lorsque \[\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \mathbf{U} \mathbf{y} = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} -\frac{3}{2\sqrt{2}} \\ \frac{1}{10\sqrt{2}}\end{bmatrix} = \begin{bmatrix} -\frac{7}{10} \\ \frac{4}{5} \end{bmatrix}.\]

Remarque. La minimisation d’une fonction quadratique s’effectue facilement en utilisant le calcul de plusieurs variables. Cependant, la justification complète de la méthode requiert une étude théorique qui excède de loin l’approche algébrique illustrée ci-dessus.

10.8.2 Quotient de Rayleigh

On présente un dernier résultat au sujet des matrices symétriques réelles.

Théorème 10.6 Soit \(\mathbf{A} \in \mathbb{R}^{n\times n}\) une matrice symétrique et \(\lambda_{\min}\) la valeur propre la plus petite de \(\mathbf{A}\). (Notons que toutes les valeurs propres de \(\mathbf{A}\) sont réels d’après le corollaire 7.1.) Alors, \[\min_{\mathbf{x} \neq \mathbf{0}} \frac{\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x}}{\mathbf{x}^\mathsf{T}\mathbf{x}} = \lambda_{\min}.\]

Démonstration. D’après le théorème 10.5, \(\mathbf{A} = \mathbf{Q}\mathbf{D} \mathbf{Q}^\mathsf{T}\), où \(\mathbf{Q}\) est orthogonale et \(\mathbf{D}\) une matrice diagonale avec les valeurs propres de \(\mathbf{A}\) sur sa diagonale.

Alors, \[\begin{align*} \min_{\mathbf{x} \neq \mathbf{0}} \frac{\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x}}{\mathbf{x}^\mathsf{T}\mathbf{x}} & = \min_{\mathbf{x} \neq \mathbf{0} } \frac{(\mathbf{Q}\mathbf{x})^\mathsf{T}\mathbf{D} (\mathbf{Q}\mathbf{x})}{\mathbf{x}^\mathsf{T}\mathbf{x}} \\ & = \min_{\mathbf{Q}^\mathsf{T}\mathbf{y} \neq \mathbf{0} } \frac{\mathbf{y}^\mathsf{T}\mathbf{D} \mathbf{y}}{(\mathbf{Q}^\mathsf{T}\mathbf{y})^\mathsf{T}(\mathbf{Q}^\mathsf{T}\mathbf{y})} \\ & = \min_{\mathbf{y} \neq \mathbf{0} } \frac{\mathbf{y}^\mathsf{T}\mathbf{D} \mathbf{y}}{\mathbf{y}^\mathsf{T}\mathbf{y}} \\ \end{align*}\] puisque \(\mathbf{Q}\mathbf{Q}^\mathsf{T}= \mathbf{I}\) et \(\mathbf{y} = \mathbf{0}\) si et seulement si \(\mathbf{Q}^\mathsf{T}\mathbf{y} = \mathbf{0}\).

De plus, \[\mathbf{y}^\mathsf{T}\mathbf{D} \mathbf{y} = \sum_{i=1}^n \lambda_{ii} y_i^2 \geq \lambda_{\min} \sum_{i=1}^n y_i^2 = \lambda_{\min} \mathbf{y}^\mathsf{T}\mathbf{y}.\] Ainsi, \[\min_{\mathbf{x} \neq \mathbf{0} } \frac{\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x}}{\mathbf{x}^\mathsf{T}\mathbf{x}} \geq \lambda_{\min}.\] Notons que le minimum est atteint lorsque \(\mathbf{x}\) est un vecteur propre associé à \(\lambda_{\min}\).

Dans la littérature de problèmes d’optimisation, il existe des algorithmes efficaces pour résoudre le problème d’optimisation \(\min_{\mathbf{x} \neq \mathbf{0} } \frac{\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x}}{\mathbf{x}^\mathsf{T}\mathbf{x}}.\) (On peut consulter Bertsekas (2016) pour en apprendre plus.)

Remarque. Le théorème 10.6 peut aussi être utilisé afin de trouver toutes les valeurs propres de \(\mathbf{A}\). Une fois \(\lambda_{\min}\) trouvé, on obtient une vecteur propre associé \(\mathbf{q}\). On complète \(\{\mathbf{q}\}\) pour obtenir une base orthogonale, que l’on place dans \(\mathbf{Q}\). Le produit \(\mathbf{Q}\mathbf{A}\mathbf{Q}^\mathsf{T}\) est alors \(\begin{bmatrix} \lambda_{\min} & \mathbf{0} \\ \mathbf{0} & \mathbf{A}' \end{bmatrix},\) où \(\mathbf{A}'\) est symétrique. (Consulter la preuve du théorème 10.5.) On trouve ensuite les valeurs propres de \(\mathbf{A}',\) ainsi que des vecteurs propres associés. Cet algorithme n’est pas une méthode très pratique et peut donner lieu à des instabilités du point de vue numérique. Mais on mentionne afin de montrer que le calcul de toutes les valeurs propres d’une matrice symétrique n’est pas plus difficile que de trouver sa valeur propre la plus petite.

Exercices

1. Soient \(\mathbf{A} \in \mathbb{R}^{n \times n}\) et \(\mathbf{x} \in \mathbb{R}^n.\) Montrez directement que que \[\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} = \frac{1}{2} \mathbf{x}^\mathsf{T}(\mathbf{A}+\mathbf{A}^\mathsf{T}) \mathbf{x}.\]

2. Montrez que \[5x_1^2 - 4x_1 x_2 + 2x_2^2 - 6x_1 + 3 \geq 0.\]

3. Soit \(\mathbf{A} \in \mathbb{R}^{n\times n}\) une matrice symétrique et \(\lambda_{\min}\) la valeur propre la plus petite de \(\mathbf{A}\). Démontrez que \[\min_{\|\mathbf{x}\| = 1} \mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} = \lambda_{\min}.\]

Solutions

1. Pour tout \(\mathbf{Q} \in \mathbb{R}^{n\times n}\), nous avons \[\begin{align*} \mathbf{x}^\mathsf{T}\mathbf{Q} \mathbf{x} & = \begin{bmatrix} x_1 & \cdots & x_n \end{bmatrix} \begin{bmatrix} \displaystyle\sum_{j = 1}^n q_{1j}x_j \\ \displaystyle\sum_{j = 1}^n q_{2j}x_j \\ \vdots \\ \displaystyle\sum_{j = 1}^n q_{nj}x_j \end{bmatrix} \\ & = \sum_{i = 1}^n \left(x_i \sum_{j = 1}^n q_{ij}x_j\right) \\ & = \sum_{i = 1}^n \sum_{j = 1}^n q_{ij} x_i x_j \\ & = \sum_{i = 1}^n q_{ii} x_i^2 + \sum_{1 \leq i < j \leq n}^n (q_{ij}+q_{ji}) x_i x_j. \end{align*}\] Ainsi, \[\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} = \sum_{i = 1}^n a_{ii} x_i^2 + \sum_{1 \leq i < j \leq n}^n (a_{ij}+a_{ji}) x_i x_j\] et \[\begin{align*} \frac{1}{2} \mathbf{x}^\mathsf{T}(\mathbf{A}+\mathbf{A}^\mathsf{T}) \mathbf{x} & = \frac{1}{2}\left(\sum_{i = 1}^n (a_{ii} + a_{ii}) x_i^2 + \sum_{1 \leq i < j \leq n}^n ((a_{ij}+a_{ji}) + (a_{ji} + a_{ij})) x_i x_j\right) \\ & = \sum_{i = 1}^n a_{ii} x_i^2 + \sum_{1 \leq i < j \leq n}^n (a_{ij}+a_{ji}) x_i x_j, \end{align*}\] d’où \[\mathbf{x}^\mathsf{T}\mathbf{A} \mathbf{x} = \frac{1}{2} \mathbf{x}^\mathsf{T}(\mathbf{A}+\mathbf{A}^\mathsf{T}) \mathbf{x}.\]

2. Notons que \[\begin{align*} & 5x_1^2 - 4x_1 x_2 + 2x_2^2 - 6x_1 + 3 \\ = ~ & \begin{bmatrix} x_1 & x_2\end{bmatrix} \begin{bmatrix} 5 & -2 \\ -2 & 2\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + \begin{bmatrix} -6 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + 3 \\ = ~ & \begin{bmatrix} x_1 & x_2\end{bmatrix} \mathbf{U} \begin{bmatrix} 1 & 0 \\ 0 & 6\end{bmatrix} \mathbf{U}^\mathsf{T} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + \begin{bmatrix} -6 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + 3, \end{align*}\] où \(\mathbf{U} = \begin{bmatrix} \frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{5}}\end{bmatrix}.\) En prenant \(\begin{bmatrix} y_1 \\ y_2 \end{bmatrix} = \mathbf{U}\begin{bmatrix} x_1 \\ x_2 \end{bmatrix},\) il s’ensuit \[\begin{align*} & 5x_1^2 - 4x_1 x_2 + 2x_2^2 - 6x_1 + 3 \\ = ~ & y_1^2 + 6y_2^2 -\frac{6}{\sqrt{5}} y_1 - \frac{12}{\sqrt{5}} y_2 +3\\ = ~ & \left(y_1-\frac{3}{\sqrt{5}}\right)^2 + 6\left(y_2 -\frac{1}{\sqrt{5}}\right)^2 -\frac{9}{5} - \frac{6}{5} + 3 \\ = ~ & \left(y_1-\frac{3}{\sqrt{5}}\right)^2 + 6\left(y_2 -\frac{1}{\sqrt{5}}\right)^2 \geq 0, \end{align*}\] tel que désiré.

3. Soit \(\mathbf{x}'\) un vecteur propre unitaire de \(\mathbf{A}\) associé à la valeur propre \(\lambda_{\min}.\) Alors \[{\mathbf{x}'}^\mathsf{T}\mathbf{A} {\mathbf{x}'} = \lambda_{\min} {\mathbf{x}'}^\mathsf{T}{\mathbf{x}'} = \lambda_{\min}.\]

   Pour compléter la preuve, il suffit de montrer que \({\mathbf{x}'}^\mathsf{T}\mathbf{A} {\mathbf{x}'} \geq \lambda_{\min}\) si \(\mathbf{x}'\) est un vecteur unitaire.

   Mais c’est évidemment le cas puisque \[{\mathbf{x}'}^\mathsf{T}\mathbf{A} {\mathbf{x}'} = \frac{{\mathbf{x}'}^\mathsf{T}\mathbf{A} {\mathbf{x}'}}{ {\mathbf{x}'}^\mathsf{T}{\mathbf{x}'}} \geq \lambda_{\min}\] pour un tel \(\mathbf{x},\) d’après le théorème 10.6.

Bibliographie

Bertsekas, D.P. 2016. Nonlinear Programming. Athena scientific optimization and computation series. Athena Scientific.