02152 RR134

RIA

laboria

<figure><img src="image_1.png" /></figure>

laboratoire de recherche
en informatique
et automatique

Application
de la méthode
de pénalisation
aux problèmes
de contrôle
en nombres entiers

<figure><img src="image_2.png" /></figure>

C. Saguez

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°134

Octobre 1975
APPLICATION DE LA MÉTHODE DE PÉNALISATION
AUX PROBLEMES DE CONTROLE EN NOMBRES ENTIERS

C. Saguez

On se propose d'appliquer la méthode de pénalisation aux problèmes de contrôle optimal de systèmes gouvernés soit par une équation parabolique, soit par une équation aux valeurs propres, dans lesquels la variable de contrôle peut s'écrire sous la forme :

$$ \sum_{i=1}^{n} \alpha_i X_{A_i} $$

avec :
$A_i$ une famille donnée d'intervalle
d'interne
$X_{A_i}$ la fonction caractéristique de l'intervalle $A_i$
$\alpha_i \in \{0,1\} \quad \forall i = 1, \dots, n$.

On montre qu'il existe une valeur $r_o$ du coefficient de pénalisation, telle que pour $r > r_o$, le problème pénalisé fournisse le contrôle optimal exact. De plus dans le cas où les intervalles $A_i$ sont disjoints, le problème initial se ramène alors à un problème continu ($\alpha_i \in [0,1], \forall i = 1, \dots, n$).

Plusieurs méthodes de résolution numérique sont enfin proposées.

We apply the penalty-method for the problems of optimal control of systems governed by a parabolic equation or an eigenvalue problem, where the control-variables can be written :

$$ \sum_{i=1}^{n} \alpha_i X_{A_i} $$

with :
$A_i$ a given family of intervals
$X_{A_i}$ the characteristic function of $A_i$
$\alpha_i \in \{0,1\} \quad \forall i = 1, \dots, n$.

The existence of a value $r_o$ of the penalty-coefficient, such that for $r > r_o$, the penalty problem gives the exact optimal control, can be proved. Moreover, when the intervals $A_i$ are disjointed, the penalty-problem is equivalent to a problem with continuous variables. Finally several numerical methods are proposed.
# PLAN

## Introduction

### I - Pénalisation en variables mixtes

1-1 - Position du problème

1-2 - Le problème pénalisé associé

### II - Application au problème de contrôle optimal en nombres entiers d'un système gouverné par une équation parabolique

2-1 - Position du problème

2-2 - Le problème pénalisé associé

2-3 - Un résultat de convergence

2-4 - Cas où les intervalles $[a_i, b_i]$ sont disjoints

2-5 - Exemples

2-6 - Extensions à d'autres problèmes de contrôle en nombres entiers

### III - Application à un problème de contrôle optimal en nombres entiers d'un système gouverné par une équation aux valeurs propres

3-1 - Position du problème

3-2 - Le problème pénalisé associé

3-3 - Un résultat de convergence

3-4 - Cas où les intervalles $[a_i, b_i]$ sont disjoints

### IV - Résolution numérique

4-1 - Cas où le problème pénalisé se ramène à un problème continu

4-1-1 - Méthode du type Gauss Seidel

4-1-2 - Méthode utilisant un Lagrangien augmenté

4-2 - Cas général

4-2-1 - Algorithme de Branch and Bound utilisant la dualité

4-2-2 - Algorithme utilisant les coupes de Gomory

### V - Résultats numériques

## Bibliographie.
APPLICATION DE LA METHODE DE PENALISATION
AUX PROBLEMES DE CONTROLE EN NOMBRES ENTIERS

Les actions, que l'on peut avoir sur un système physique, ont très souvent un caractère discret. Ainsi pour le contrôle d'un véhicule interplanétaire, on effectue, à des instants donnés, des corrections de trajectoires en allumant, pendant un certain temps, un ou plusieurs moteurs auxilliaires. Un autre exemple peut-être donné par la régulation d'un réacteur nucléaire. On dispose alors d'un nombre fini de types de barres absorbantes et on doit choisir pour une implantation donnée à priori "le meilleur type".

Dans les exemples traités dans cet article, on considère le cas où le contrôle intervient sous la forme (ce qui est le cas dans les deux exemples cités précédemment) :

$$
\sum_{i=1}^{n} \alpha_{i} X_{A_{i}} \text{ avec } \{A_{i}\} \ i = 1, \dots, n \text{ une famille donnée d'intervals } X_{A_{i}} \text{ le fonction caractéristique de } A_{i} \\
\alpha_{i} \in \{0,1\} \ \forall i = 1, \dots, n.
$$

On étudie le cas d'un système gouverné soit par une équation parabolique, soit par une équation aux valeurs propres du deuxième ordre.

On utilise une méthode de pénalisation des équations d'état,
considérées alors comme contraintes ([9] YVON).

On se ramène alors à un problème en variables mixtes. Dans
le cas où les intervals $A_i$ sont disjoints le problème est alors équivalent à un
problème continu.
# I - PENALISATION EN VARIABLES MIXTES

## 1-1 - Position du problème

Soient - V et Y deux espaces de Banach réflexifs

- I un ensemble discret fini {$α_1, ..., α_p$}

- f une application de I×Y dans $\mathbb{R}$ convexe, continue sur Y

- g une application de I×Y dans V continue de I×Y faible dans V faible.

On suppose de plus que f et g vérifient une des deux hypothèses suivantes :

$$ (1-1) \qquad \left\{ \begin{array}{l} f(\alpha,y) \to +\infty \quad \text{et } G(\alpha) = \{y \mid y \in Y, g(\alpha,y) = 0\} \text{ convexe, fermé} \\ \|y\|_Y \to +\infty \end{array} \right. $$

$$ (1-1)' \qquad \begin{array}{l} \text{l'ensemble } \{y \mid \|g(\alpha,y)\|_V \le c_1 \; ; \; f(\alpha,y) \le c_2, x \in I\} \\ \text{est borné dans Y.} \end{array} $$

On considère alors le problème de minimisation en variables mixtes suivant :

$$ (1-2) \qquad \left\{ \begin{array}{l} \text{Min } f(\alpha,y) \\ g(\alpha,y) = 0 \\ \alpha \in I \; ; \; y \in Y \end{array} \right. $$

**Proposition 1** : *Sous les hypothèses précédentes, le problème (1-2) admet au moins une solution.*

En effet pour $α$ donné, le problème (1-2) admet au moins une solution et $α$ ne peut prendre qu'un nombre fini de valeurs.

<figure><img src="image_3.png" /></figure>

## Remarque 1 :

Supposons $f(\alpha,y)$ deux fois continuent différentiable en $(\alpha,y)$ et $I = \{0,1\}^k$, alors le problème (1-2) est équivalent à un problème où la fonction à minimiser est convexe globalement en $(\alpha,y)$.
En effet si $I=\{0,1\}^k$ le problème (1.9) est équivalent à :

$$
\left\{
\begin{array}{l}
\displaystyle \text{Min } f(\alpha, y) + \sum_{i=1}^{k} p_i \alpha_i (\alpha_i - 1) \\[1em]
\text{g}(\alpha, y) = 0 \\[1em]
\alpha \in I \ ; \ y \in Y
\end{array}
\right.
$$

et $f(\alpha,y) + \sum_{i=1}^{k} p_i \alpha_i (\alpha_i - 1)$ est alors convexe par rapport à $(\alpha,y)$ pour $p_i$ assez grand.

■

**Remarque 2 :**

Si $f(\alpha,y)$ est strictement convexe en $y$, si pour $\alpha$ fixé l'ensemble
$G(\alpha) = \{y|y\in Y, g(\alpha,y) = 0\}$ est un convexe fermé, alors il existe un problème
mixte admettant comme unique solution, une solution du problème (1-2).

En effet on peut toujours construire une fonction h(α) telle que

$$
h(\alpha_i) \neq h(\alpha_j) \quad \forall \alpha_i \neq \alpha_j, \alpha_i \in I
$$

et

$$
|h(\alpha)| < c_1 \quad \forall \alpha \in I \quad \text{puisque } I \text{ est un ensemble fini.}
$$

Notons $f^*(\alpha) = \text{Min } f(\alpha, y)$, (ce problème admet une solution

$$
\begin{cases}
g(\alpha, y) = 0 \\
y \in Y
\end{cases}
$$

unique et $f^*(\alpha)$ prend un nombre fini de valeurs pour $\alpha \in I$.)

$$
\text{Soit } C = \text{Min} |f^*(\alpha_i) - f^*(\alpha_j)| \quad (1-3) \\
\alpha_i, \alpha_j \in I, f^*(\alpha_i) \neq f^*(\alpha_j)
$$
alors le problème :

$$
\left\{
\begin{array}{ll}
\text{Min } f(\alpha,y) + \eta h(x) & \\
\\
g(\alpha,y) = 0 & \text{avec } \eta < \frac{C}{C_1} \\
\alpha \in I, y \in Y &
\end{array}
\right.
$$

répond à la question.

■

1-2 - Le problème pénalisé associé

On introduit le problème pénalisé suivant :

$$
(1-4) \quad \left\{
\begin{array}{ll}
\text{Min } f(\alpha,y) + \frac{1}{\epsilon} \|g(\alpha,y)\|_V^2 & \\
\alpha \in I \; ; \; y \in Y &
\end{array}
\right.
$$

On a le résultat suivant :

Proposition 2 :

Si $(\alpha^*, y^*)$ est une solution de (1-4), tout point adhérent faible de la suite $(\alpha^*, y^*)$ est une solution du problème (1-2).

De plus si (1-2) admet une solution unique alors

$$
\[
\alpha_{\epsilon}^{*} = \alpha^{*} \quad \text{pour } \epsilon \text{ suffisamment petit}
\]
\[
\begin{cases}
y_{\epsilon}^{*} \to y^{*} & \text{dans } Y \text{ faible} \\
\epsilon \to 0
\end{cases}
\]
$$

avec $(\alpha^*, y^*)$ solution du problème (1-2).

Démonstration :

i) Soit la suite $\{\alpha_{\epsilon}^*\}$ des solutions $\alpha_{\epsilon}^*$ pour chaque $\epsilon$. Comme $\alpha_{\epsilon}^*$ appartient à un ensemble fini, il existe une sous-suite encore notée $\{\alpha_{\epsilon}\}$ telle que

$$
(1-5) \qquad \alpha_{\epsilon}^{*} = \alpha \quad \forall \epsilon
$$
$$
\text{ii) Soient } M = \min \{ f(\alpha, y) \text{ et } g(\alpha, y) = 0 \text{ tel que } \alpha \in I \text{ ; } y \in Y\}
$$

$$
\text{On a } f(\alpha_{\epsilon}^{*}, y_{\epsilon}^{*}) + \frac{1}{\epsilon} \|g(\alpha_{\epsilon}^{*}, y_{\epsilon}^{*})\|_{V}^{2} \leq M
$$

Avec l'hypothèse (1-1) ou (1-1)' on a

$$
(1-6) \qquad \|y_{\varepsilon}^{*}\|_{Y} \leq K
$$

donc il existe une sous-suite encore notée $\{y_{\epsilon}^*\}$ telle que :

$$
(1-7) \quad y_{\epsilon}^{*} \rightarrow y \text{ dans } Y \text{ faible}
$$

iii) On a les inégalités :

$$
\mu + \frac{1}{\epsilon} \|g(\alpha_{\epsilon}^{*}, y_{\epsilon}^{*})\|_{V}^{2} \leq f(\alpha_{\epsilon}^{*}, y_{\epsilon}^{*}) + \frac{1}{\epsilon} \|g(\alpha_{\epsilon}^{*}, y_{\epsilon}^{*})\|_{V}^{2} \leq M
$$

On en déduit :

$$
\|g(\alpha_{\epsilon}^{*}, y_{\epsilon}^{*})\|_{V}^{2} \le \epsilon(M-m)
$$

donc :

$$
\|g(\alpha_{\epsilon}^{*}, y_{\epsilon}^{*})\|_{V}^{2} \rightarrow 0 \quad \epsilon \rightarrow 0
$$

d'après les propriétés de continuité de g et avec (1-5)

(1-7) on obtient :

$$
(1-8) \qquad g(\alpha, y) = 0
$$

IV) (α, y) est solution du problème (1-2).

En effet sinon il existerait (α*, y*) ∈ I×Y tel que

$$
\text{(1-9)} \quad \left\{
\begin{array}{l}
f(\alpha^*, y^*) < f(\alpha, y) \\
g(\alpha^*, y^*) = g(\alpha, y) = 0
\end{array}
\right.
\\[1em]
\text{On a } f(\alpha^*, y^*) + \frac{1}{\epsilon} \|g(\alpha^*, y^*)\|_V^2 \le f(\alpha^*, y^*)
\\[1em]
f(\alpha^*, y^*) \le f(\alpha^*, y^*)
$$
et d'après les propriétés de continuité de $f$ on obtient :

$$f(\alpha, y) \leq f(\alpha^*, y^*)$$

d'où une contradiction avec (1-9)

donc $(\alpha, y)$ est optimal.

<figure><img src="image_4.png" /></figure>

**Remarque 3 :**

Dans le cas où $f(\alpha, y)$ est strictement convexe en $y$, et $G(\alpha)$ un convexe fermé pour tout $\alpha \in I$, on a vu (Remarque 2) qu'on pouvait se ramener à un problème ayant une solution unique. On a alors le résultat :

$$\text{pour } \varepsilon < \varepsilon_0 \text{ on a } \alpha_{\varepsilon}^* = \alpha^* (\alpha^* \text{ contrôle optimal du problème (1-2)}).$$

Alors pour obtenir l'état optimal, il suffit de résoudre le problème

$$\begin{cases} \text{Min } f(\alpha^*, y) \\ g(\alpha^*, y) = 0 \\ y \in Y \end{cases} \quad \text{dont l'unique solution est } y^*$$

Dans le cas particulier où il existe un $y$ unique tel que $g(\alpha, y) = 0$ pour $\alpha \in I$ (par exemple cas d'un contrôle optimal d'un système gouverné par des équations aux dérivées partielles), alors il suffit de résoudre $g(\alpha^*, y) = 0$ pour avoir l'état optimal.

**Remarque 4 :**

Dans la pratique, on résoud le problème pénalisé pour un $\varepsilon$ fixé et on veut savoir si le contrôle obtenu est le contrôle optimal.

Pour cela il suffit que

$$|f(\alpha_{\varepsilon}^*, y_{\varepsilon}^*) + \frac{1}{\varepsilon} \|g(\alpha_{\varepsilon}^*, y_{\varepsilon}^*)\|^2 - f^*(\alpha_{\varepsilon}^*)| < C$$

avec $f^*$ et $C$ définis à la Remarque 2.

Si ce test n'est pas vérifié alors on diminue $\varepsilon$ et ainsi de suite.
Remarque 5 :

D'après les deux remarques précédentes, on voit que les difficultés de convergence et de stabilité reconstrées dans le cas d'un contrôle continu n'existent plus puisque pour ε suffisamment petit, on obtient le contrôle optimal exact. Cependant dans le cas général le problème pénalisé est un problème en variables mixtes qui peut s'avérer difficile à résoudre.

II - APPLICATION AU PROBLEME DE CONTROLE OPTIMAL EN NOMBRES ENTIERS D'UN SYSTEME GOUVERNE PAR UNE EQUATION PARABOLIQUE

2-1 - Position du problème

V, H étant deux espaces de Hilbert avec :

V ⊂ H ⊂ V' avec injection continue et densité
t uésigne le temps.

Soit $a(t, \varphi, \psi)$ une famille de formes linéaires continues sur $V$ telles que

$$
(2-1) \qquad \left\{
\begin{array}{l}
\forall \varphi, \psi \in V \quad t \to a(t; \varphi, \psi) \text{ est mesurable sur } ]0,T[ \\
\text{et } |a(t; \varphi, \psi)| \le C \|\varphi\|_V \|\psi\|_V
\end{array}
\right.
$$

$$
(2-2) \quad \left\{
\begin{array}{ll}
\text{il existe } \lambda \text{ tel que} & \\
\qquad a(t; \varphi, \varphi) + \lambda |\varphi|_{H}^{2} \ge \alpha |\varphi|_{V}^{2} & \forall \varphi \in V \\
\qquad \forall t \in ]0, T[ &
\end{array}
\right.
$$

on écrit :

$$
(2-3) \qquad
\begin{gathered}
a(t; \varphi, \psi) = (A(t)\varphi, \psi)_{V' \to V} \\
\text{avec } A(t) \in \mathcal{L}(L^2(0, T; V), L^2(0, T; V'))
\end{gathered}
$$

Soit u l'espace des fonctions en escalier sur ]0, T[, muni du
produit scalaire de L²(0, T)

$$
(2-4) \quad B \in \mathcal{L}(u, L^2(0, T; V'))
$$
On définit l'état y du système comme la solution de :

$$
(2-5) \quad \begin{cases} \frac{dy}{dt} + Ay = f + Bu \\ y(x, 0) = y_0(x) \end{cases}
$$

avec
f donné dans L²(O, T ; V')
y₀ donné dans H

On prend maintenant u de la forme suivante :

$$
(2-6) \quad u = \sum_{i=1}^{n} \mu_i \alpha_i X_{[a_i, b_i]}
$$

avec :

n un entier fixé

$\mu_i \in \mathbb{R} ; \alpha_i \in \{0,1\} \ i=1,...,n$

$[a_i, b_i]$ une famille d'intervalle de ]0, T[

$X[a_i, b_i]$ la fonction caractéristique de l'intervalle $[a_i, b_i]$.

Alors pour u fixé le problème (2-5) admet une solution et une
seule y, fo tion de αᵢ, dans W(O, T) ([7] LIONS)

$$
W(O, T) = \{y \mid y \in L^2(O, T ; V) ; \frac{dy}{dt} \in L^2(O, T ; V')\}
$$

On note $I = \{0,1\}^n$ et $I_{ad}$ un sous-ensemble de $I$.

On définit la fonctionnelle suivante :

$$
(2-7) \quad J(\alpha) = \|y - z_d\|_{L^2(O, T; H)}^2 + \nu \|u\|_{L^2(O, T)}^2 \quad \nu \ge 0
$$

avec $z_d$ donné dans $L^2(O, T; H)$.

On considère le problème de contrôle suivant :

Trouver $\alpha^* \in I_{ad}$ tel que :

$$
(2-8) \quad J(\alpha^*) = \min J(\alpha) \\
\qquad \alpha \in I_{ad}
$$
**Proposition 3** : *Le problème (2-8) admet au moins une solution*

En effet $\alpha$ ne pouvant prendre qu'un nombre fini de valeurs,
il en est de même pour $J(\alpha)$. Donc il y a au moins une solution.

Remarquons tout de suite que la Remarque 2 s'applique à ce
problème, il suffit de prendre $h(\alpha) = \sum_{i=1}^{n} 2^{i-1} \alpha_i$

$$
\text{On définit } \eta \le \frac{1}{\sum_{i=1}^{n} 2^{i-1}} \quad \text{Min} \left| J(\alpha_i) - J(\alpha_j) \right| \\
\left\{ \begin{array}{ll} \alpha_i, \alpha_j \in I_{ad} & J(\alpha_i) \neq J(\alpha_j) \end{array} \right.
$$

Soit le problème :

$$
(2-9) \qquad \begin{array}{ll}
\text{Min} & J(\alpha) + \eta h(\alpha) \\
\alpha & \in I_{\text{ad}}
\end{array}
$$

Ce problème admet comme unique solution une solution optimale
de (2-8). En fait cela revient à prendre parmi toutes les solutions optimales
de (2-8) la solution qui minimise h(α).

Donc dans la suite nous supposerons que le problème (2-8) admet
une solution et une seule.

2-2 - Le problème pénalisé associé

On introduit l'espace $Y$ :

$$
(2-10) \quad Y = \{y \mid y \in L^2(0, T; V) ; \frac{\partial y}{\partial t} + Ay \in L^2(0, T; V') \}
$$

on munit $Y$ de la norme :

$$
(2-11) \quad \|y\|_{Y}^{2} = \|y\|_{L^{2}(O, T; V)}^{2} + \|\frac{\partial y}{\partial t}\|_{L^{2}(O, T; V')}^{2} + \|y(x, 0)\|_{H}^{2}
$$
alors Y a la structure d'espace de Hilbert.

On définit sur $\mathcal{I}\times\mathcal{Y}$ la fonctionnelle pénalisée :

$$ (2-12) \qquad J_{\varepsilon}(\alpha, y) = \|y-z_d\|^2_{L^2(0, T; H)} + v \|u\|^2_{L^2(0, T)} \\ \qquad + \frac{1}{\varepsilon_1} \|\frac{\partial y}{\partial t}\|_{L^2(0, T; V')}^2 + \frac{1}{\varepsilon_2} \|y(x,0) - y_0(x)\|^2_H $$

On a alors le problème pénalisé suivant :

Trouver $(\alpha^*, y^*) \in I_{ad} \times \mathcal{Y}$ tel que

$$ (2-13) \qquad J_{\varepsilon}(\alpha^*, y^*) = \text{Min}_{\alpha \in I_{ad}} J_{\varepsilon}(\alpha, y) \\ \qquad \qquad \alpha \in I_{ad} ; y \in \mathcal{Y} $$

Ce problème est quadratique - quadratique en variables mixtes.

**Proposition 4** : *Le problème (2-13) admet au moins une solution*

En effet si on considère pour $\alpha$ fixé dans $I_{ad}$ le problème :

Trouver $\bar{y}_\varepsilon \in \mathcal{Y}$ tel que

$$ J_{\varepsilon}(\alpha, \bar{y}_{\varepsilon}) = \text{Min}_{y \in \mathcal{Y}} J_{\varepsilon}(\alpha, y) $$

Ce problème admet une solution ([7] LIONS) et d'autre part $\alpha$ ne peut prendre qu'un nombre fini de valeurs.

## 2-3 - Un résultat de convergence

**Proposition 5** : Tout point adhérent faible de la suite $(\alpha^*, y^*)_{\varepsilon}$ des solutions de (2-13) est solution de (2-8)

Démonstration :

$$ \text{On a } J_{\varepsilon}(\alpha^*, y^*) \le J(\alpha^*) $$
Donc en particulier :

$$
(2-14) \quad \left\| y_{\varepsilon}^* - z_d \right\|_{L^2(0, T; H)} \le C_1
$$

$$
(2-15) \quad \left\| \frac{\partial y_{\varepsilon}^{*}}{\partial t} + Ay_{\varepsilon}^{*} - f - Bu_{\varepsilon}^{*} \right\|_{L^2(0, T; V')} \le C_2 \sqrt{\varepsilon_1}
$$

$$
(2-16) \quad \| y_{\epsilon}^{*}(x, 0) - y_{0}(x) \|_{H} \le C_{3} \sqrt{\epsilon_{2}}
$$

Or pour tout $\eta$ positif on a l'inégalité :

$$
(2-17) \quad (\alpha-2 \eta) \|y_{\varepsilon}^{*}\|_{L^2(0, T; V)}^2 + \frac{1}{2} |y_{\varepsilon}^{*}(x, T)|_{H}^{2} \le \frac{1}{2\eta} \|\frac{\partial y_{\varepsilon}^{*}}{\partial t}\|_{L^2(0, T; V')}^2 \\
\qquad + \lambda \|y_{\varepsilon}^{*}\|_{L^2(0, T; H)}^2 + \frac{1}{2} |y_{\varepsilon}^{*}(x, 0)|_{H}^{2}
$$

on en déduit que :

$$
(2-18) \quad \frac{\partial y_{\varepsilon}^{*}}{\partial t} + Ay_{\varepsilon}^{*} \text{ est borné dans } L^{2}(0, T; V')
$$

$$
(2-19) \quad y_{\epsilon}^{*} \text{ est borné dans } L^{2}(0, T; V)
$$

$$
(2-20) \quad y_{\epsilon}^{*}(x, 0) \text{ est borné dans H}
$$

donc $y_{\epsilon}^{*}$ est borné dans Y

il existe alors deux sous-suites encore notées $y_{\epsilon}^{*}$ et $\alpha_{\epsilon}^{*}$ telles que :

$$
\begin{cases}
y_{\epsilon}^{*} \rightarrow y \text{ dans } Y \text{ faible} \\
\alpha_{\epsilon}^{*} = \alpha
\end{cases}
$$
et d'après (2-15)-(2-16) on en déduit que :

$$
\left\{
\begin{array}{l}
\frac{\partial y}{\partial t} + Ay = f + Bu \\
y(x, 0) = y_0(x)
\end{array}
\right.
$$

Enfin comme pour la proposition 2 on démontre que $\alpha$ est optimal
pour le problème (2-8).

2-4 - Cas où les intervalles $]a_i, b_i[$ sont disjoints

Dans ce cas la fonctionnelle Jε(α, y) ne contient pas de
termes de la forme αᵢ, αⱼ, mais seulement de la forme αᵢ². Or comme αᵢ ∈ {0,1} on
a αᵢ² = αᵢ. Donc le problème (2-13) est équivalent à un problème où α intervient
linéairement. Alors le problème continu associé avec αᵢ ∈ [0,1] admet la même
solution que le problème mixte. On est donc ramené à résoudre un problème
linéaire-quadratique (en général non convexe) en variables continues.

2-5 - Exemples

On considère le système suivant :

$$
(2-21) \quad \frac{\partial y}{\partial t} - \Delta y = f + \sum_{i=1}^{n} \alpha_i \mu_i X_{[a_i, b_i]} \quad \text{sur } \Omega \times ]0, T[
$$

$$
(2-22) \qquad y|_{\Sigma} = 0 \qquad \text{avec } \Sigma = \partial \Omega \times ]0, T[
$$

$$
(2-23) \quad y(x, 0) = y_0(x)
$$

avec $\mu_i$ donné dans $\mathbb{R}$

f(x, t) donné dans L²(Q)

$y_0(x)$ donné dans $L^2(\Omega)$
On définit d'autre part que la fonctionnelle :

$$
(2-24) \quad \int_{\Omega} \int_{0}^{T} |y - z_d|^2 dxdt = J(\alpha) \quad \text{avec } z_d \text{ donné dans } L^2(Q)
$$

Le problème de contrôle s'écrivant :

Trouver $\alpha^* \in \{0, 1\}^n$ tel que

$$
(2-25) \qquad J(\alpha^*) = \min J(\alpha) \\
\alpha \in \{0, 1\}^n
$$

On obtient la fonctionnelle pénalisée :

$$
(2-26) \quad J_{\varepsilon}(\alpha, y) = \int_{\Omega} \int_{0}^{T} |y - z_{d}|^2 dxdt \\
\qquad + \frac{1}{\varepsilon_1} \left\| \frac{\partial y}{\partial t} - \Delta y - f - \sum_{i=1}^{n} \alpha_i \mu_i x[a_i, b_i] \right\|_{L^2(Q)}^2 \\
\qquad + \frac{1}{\varepsilon_2} \left\| y(x, 0) - y_{c_0}(x) \right\|_{L^2(\Omega)}^2
$$

Le problème pénalisé s'écrit :

Trouver $(\alpha_{\varepsilon}^*, y_{\varepsilon}^*) \in \{0, 1\}^n \times Y$ tel que

$$
(2-27) \quad J_{\varepsilon}(\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}) = \min_{\varepsilon} J_{\varepsilon}(\alpha, y) \\
(\alpha, y) \in \{0, 1\}^{n} \times Y
$$

avec
$$ Y = \{y | y \in L^2(0, T; H_0^1(\Omega)) ; \frac{\partial y}{\partial t} - \Delta y \in L^2(\Omega)\} $$
Dans le cas où les intervalles $]a_i, b_i[$ sont disjoints, on définit :

$$
\begin{align*}
(2-28) \qquad \tilde{J}_{\varepsilon}(\alpha, y) &:= \|y-zd\|^2 + \frac{1}{\varepsilon_1} \left\{ \left\| \frac{\partial y}{\partial t} - \Delta y - f \right\|^2 \right. \\
&\qquad \left. - 2 \left\langle \frac{\partial y}{\partial t} - \Delta y - f, \sum \alpha_i \mu_i X_{Ai} \right\rangle \right\rangle_{L^2(Q)} \\
&\qquad + \left. \sum_i \alpha_i \mu_i^2 \|X_{Ai}\|^2 \right\} + \frac{1}{\varepsilon_2} \|y(x, 0) - y_0(x)\|^2 \tag{Ω}
\end{align*}
$$

On doit donc alors résoudre le problème continu :

Trouver $(\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}) \in [0,1]^{n} \times Y$ tel que

$$
\begin{align*}
(2-29) \quad \tilde{J}_{\varepsilon}(\alpha_{\varepsilon}^*, y_{\varepsilon}^*) &= \min_{\alpha \in [0,1]^n} \tilde{J}_{\varepsilon}(\alpha, y) \\
&\qquad \alpha \in [0,1]^n \\
&\qquad y \in Y
\end{align*}
$$

2-6 - Extensions à d'autres problèmes de contrôle en nombres entiers

i) Remarquons d'abord que si u dépend de façon indépendante des divers $\alpha_i$, alors u peut s'écrire sous la forme d'une fonction affine de $\alpha$ et donc on a un problème du même type que (2-8). En particulier dans le cas où u est de la forme :

$$
\begin{align*}
u &= \sum_{i=1}^{n} \alpha_i \delta(x - b_i) \\
\text{avec } \alpha_i \in \{0,1\} \quad \forall i = 1, \dots, n \\
\{b_i\} \quad i = 1, \dots, n \text{ une famille de points de } \Omega \\
\delta(x - b_i) \quad \text{la mesure de Dirac au point } b_i.
\end{align*}
$$
## ii) Cas d'équations non linéaires

Dans ce cas, la méthode de pénalisation, présente un intérêt supplémentaire, car de toute façon on ne peut pas comme dans le cas linéaire expliciter directement $J(\alpha)$ en fonction de $\alpha$ et appliquer un algorithme de programmation entière.

Donnons un exemple :

L'état du système est solution de :

$$ (2-30) \qquad \frac{\partial y}{\partial t} - \frac{\partial^2 y}{\partial x^2} + \left( \sum_{i=1}^{n} \alpha_i \mu_i x[a_i, b_i] \right) y = f \quad \text{sur } \Omega \times ]0, T[$$

$$ (2-31) \qquad y\left|_{\Sigma} = 0 $$

$$ (2-32) \qquad y(x,0) = y_0(x) $$

avec :
$f$ donné dans $L^2(\Omega)$ et $y_0(x)$ donné dans $L^2(\Omega)$
$[a_i, b_i]$ : $i=1, \dots, n$ une famille d'intervalle de $\Omega$.
$\mu_i \in \mathbb{R}$ : $i=1, \dots, n$ donné.

On définit la fonctionnelle :

$$ (2-33) \qquad J(\alpha) = \int_{\Omega} \int_{0}^{T} |y - z_d|^2 d dt + \nu \int_{\Omega} |u|^2 dx $$
avec $z_d$ donné dans $L^2(\Omega)$ et $u = \sum_{i=1}^{n} \alpha_i \mu_i x[a_i, b_i]$.

On considère le problème de contrôle.

Trouver $\alpha^* \in \{0,1\}^n$ tel que :

$$ (2-34) \qquad J(\alpha^*) = \begin{cases} J(\alpha) & \alpha \in \{0,1\}^n \\ \infty & \alpha \notin \{0,1\}^n \end{cases} $$

On démontre comme au 1) que ce problème admet au moins une solution.
On définit le problème pénalisé suivant :

$$
\begin{equation}
\begin{split}
J_{\varepsilon}(\alpha, y) = {}& \|y-z_d\|_{L^2(Q)}^2 + \nu \|\psi\|_{L^2(0,T)}^2 \\
& + \frac{1}{\varepsilon_1} \left\| \frac{\partial y}{\partial t} - \frac{\partial^2 y}{\partial x^2} + \left( \sum_{i=1}^n \alpha_i \mu_i X[a_i, b_i] \right) y - f \right\|_{L^2(Q)}^2 \\
& + \frac{1}{\varepsilon_2} \left\| y(x,0) - y_o(x) \right\|_{L^2(\Omega)}^2
\end{split}
\end{equation}
$$

$$
(2-36) \qquad Y = \{ y \in L^2(0,T; H_0^1(\Omega)) \mid \frac{\partial y}{\partial t} - \Delta y \in L^2(\Omega) \}.
$$

$$
\begin{array}{@{}l@{\qquad}l@{}}
(2-37) & \begin{cases}
\text{Trouver } (\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}) \in \{0,1\}^{n} \times Y \text{ tel que} \\
\quad J(\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}) = \text{Min } J(\alpha, y) \\
\quad (\alpha, y) \in \{0,1\}^{n} \times Y
\end{cases} \\
& \text{On a alors des résultats de convergence analogue au cas parabolique}
\end{array}
$$

On a alors des résultats de convergence analogue au cas parabolique
([7] LIONS pour le cas du contrôle continu, u ∈ L∞(Q)).

### III - APPLICATION A UN PROBLEME DE CONTROLE OPTIMAL EN NOMBRES ENTIERS D'UN SYSTEME GOUVERNE PAR UN EQUATION AUX VALEURS PROPRES.

On se place dans le cas où la dimension est 1.

3-1 - Position du problème.

On considère le problème aux valeurs propres suivant :

L'état y du système satisfait aux équations :

$$
(3-1) \qquad - \frac{d^2 y}{dx^2} + \left( \sum_{i=1}^{n} \alpha_i \right) X[a_i, b_i] y = \lambda y \quad \text{sur } \Omega = ]0, R[
$$

$$
(3-2) \qquad \frac{\partial y}{\partial n}(0) = 0 ; \quad y(R) = 0
$$

y étant la fonction propre associée à la plus petite valeur
propre positive λ telle que :

$$
(3-3) \qquad y(0) = 1
$$
avec $\alpha_i \in \{0,1\} \quad \forall i=1,...,n$.

$\{[a_i, b_i]\}$ $i=1,...,n$ une famille d'intervalle de $\Omega$.

$a \in \mathbb{R}^+$ donné, $\mu_i \in \mathbb{R}$ $i=1,...,n$ donné.

Ce système admet une solution et une seule, caractérisée par
le fait qu'elle ne s'annule que sur le bord $\partial\Omega$ de $\Omega$.

On introduit la fonctionnelle :

$$
(3-4) \qquad J(\alpha) = \int_{\Omega} |y - z_d|^2 d\Omega + v(\lambda - \lambda_o)^2
$$

avec $z_d$ donné dans $L^2(\Omega)$

$v > 0$ donné

$\lambda_o$ donné dans $\mathbb{R}$

On considère alors le problème de contrôle suivant :

Trouver $\alpha^* \in I = \{0,1\}^n$ tel que

$$
(3-5) \qquad J(\alpha^*) = \min J(\alpha) \\
\alpha \in I
$$

Le problème (3-5) admet au moins une solution et de plus la
remarque 2 pour obtenir l'unicité est applicable comme dans le cas paraboli-
que.

3-2 - Le problème pénalisé associé.

On introduit l'espace $Y = H^2(\Omega) \cap V$. Muni de la topologie de $H^2(\Omega)$, Y à la structure d'espace de Hilbert.

$$
V = \{y \mid y \in H^1(\Omega), y(\mathbb{R}) = 0\}
$$

On définit la fonctionnelle pénalisée :
$$
(3-6) \quad J_{\varepsilon}(\alpha, y, \lambda) = \|y-z_d\|_{L^2(\Omega)}^2 + v(\lambda-\lambda_0)^2 + \frac{1}{\varepsilon_1} \left\| -\frac{d^2 y}{dx^2} + \left(\sum_{i=1}^n \alpha_i x_i [a_i, b_i]\right) y \right\|_{L^2(\Omega)}^2 \\
\qquad + \frac{1}{\varepsilon_2} \left\| y \right\|_{L^2(\Omega)}^2 + \frac{1}{\varepsilon_3} [y(o) - 1]^2 + \frac{1}{\varepsilon_4} \left\| \frac{\partial y}{\partial n} \right\|_{L^2(\Gamma)}^2
$$

On remarque d'autre part que, dans le problème (3-1) (3-2) :

$$
(3-7) \quad \lambda = \min_{y \in V} \frac{\int_{\Omega} (|\operatorname{grad} y|^2 + \sum_{i=1}^{n} \alpha_i x_i [a_i, b_i] y^2) \, d\Omega}{\int_{\Omega} y^2 \, d\Omega}
$$

donc en particulier $\lambda \le (\Pi^2 + 1)$ mes $(\Omega) = \lambda_1$

On définit alors $\Lambda = \{\lambda \mid 0 < \lambda \le \lambda_1\}$

On considère le problème pénalisé :

Trouver $(\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}, \lambda_{\varepsilon}^{*}) \in \{0,1\}^{n} \times Y \times \Lambda$ tel que

$$
(3-8) \quad J_{\varepsilon} (\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}, \lambda_{\varepsilon}^{*}) = \min_{(\alpha, y, \lambda) \in I \times Y \times \Lambda} J_{\varepsilon} (\alpha, y, \lambda)
$$

**Proposition 6** :

Le problème (3-8) admet au moins une solution.

i) On a $J_{\varepsilon}(\alpha, y, \lambda) \to +\infty$ si $||y||_Y \to \infty$

en effet

$$
J_{\varepsilon}(\alpha, y, \lambda) \ge (1 - \theta_1) \|y\|_{L^2}^2 + (1 - \frac{1}{\theta_1}) \|z_d\|_{L^2}^2 - v\lambda + \frac{1}{\varepsilon_1} (1 - \theta_2) \left\| \frac{\partial^2 y}{\partial x^2} \right\|_{L^2}^2 \\
+ \frac{1}{\varepsilon_1} (1 - \frac{1}{\theta_2}) \left\| \left( \sum_{i=1}^n \alpha_i x_i [a_i, b_i] - \lambda \right) y \right\|_{L^2}^2 + \frac{1}{\varepsilon_3} (y(o) - 1)^2 \\
+ \frac{1}{\varepsilon_4} \left\| \frac{\partial y}{\partial n} \right\|_{L^2(\Gamma)}^2
$$
ii) $J_{\varepsilon}(\alpha, y, \lambda)$ est faiblement semi-continue inférieurement par rapport à $(y, \lambda)$.

Donc pour $\alpha$ fixé le problème

Trouver $(\bar{y}, \bar{\lambda}) \in Y \times \Lambda$ tel que

$$ J_{\varepsilon}(\alpha, \bar{y}, \bar{\lambda}) = \min_{(y, \lambda) \in Y \times \Lambda} J_{\varepsilon}(\alpha, y, \lambda) $$

admet au moins une solution.

Or comme $\alpha$ ne peut prendre qu'un nombre fini de valeurs on a la proposition.

### 3-3 - Un résultat de convergence.

**Proposition 7 :**

Tout point adhérent faible de la suite $(\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}, \lambda_{\varepsilon}^{*})$ est solution du problème (3-5).

$J_{\varepsilon}(\alpha_{\varepsilon}^{*}, y_{\varepsilon}^{*}, \lambda_{\varepsilon}^{*})$ est borné supérieurement par $J(\alpha^{*})$, et de plus comme $\Lambda$ est borné on a $\lambda_{\varepsilon}^{*} \le \lambda_{o}$, on en déduit que :

$$ (3-9) \qquad \|y_{\varepsilon}^{*} - z_{d}\|_{L^{2}} \le c_{1} $$

$$ (3-10) \qquad \left\| \frac{d^2 y_{\varepsilon}^*}{dx^2} + \left( \sum_{i=1}^n \alpha_i^* \varepsilon X[a_i, b_i] \right) y_{\varepsilon}^* - \lambda_{\varepsilon}^* y_{\varepsilon}^* \right\|_{L^2} \le c_2 \sqrt{\varepsilon_1} $$

$$ (3-11) \qquad \|y_{\varepsilon}^{*}\|_{L^{2}} \le c_{3} \sqrt{\varepsilon_{2}} $$

$$ (3-12) \qquad (y(0) - 1)^2 \le c_4 \sqrt{\varepsilon_3} $$

$$ (3-13) \qquad \left\| \frac{\partial y}{\partial n} \right\|_{L^2(\Gamma)} \le c_5 \sqrt{\varepsilon_4} $$
De (3-9) et (3-10) on déduit que

$$
(3-14) \quad y_{\varepsilon}^{*} \text{ est borné dans } Y
$$

Donc comme $\alpha_{\varepsilon}^*$ ne peut prendre qu'un nombre fini de valeurs, il
existe une sous-suite, encore notée $(\alpha_{\varepsilon}^*, y_{\varepsilon}^*, \lambda_{\varepsilon}^*)$ telle que.

$$
\alpha_{\varepsilon}^{*} = \alpha
$$

$$
(3-15) \quad y_{\epsilon}^{*} \to y \quad \text{dans } Y \text{ faible}
$$

$$
\lambda_{\varepsilon}^{*} \to \lambda \text{ dans } \mathbb{R}^{+}
$$

l'injection de Y dans L²(Ω) étant compacte on a donc

$$
\left\{
\begin{array}{l}
y_{\epsilon}^{*} \rightarrow y \text{ dans } L^2(\Omega) \text{ fort.} \\
\\
\|y_{\epsilon}^{*}\|_{L^2}^2 \rightarrow \|y\|_{L^2}^2
\end{array}
\right.
$$

on en déduit que (α,y,λ) est solution de

$$
\left\{
\begin{array}{l}
- \frac{d^2 y}{dx^2} + \left( \sum_{i=1}^{n} \alpha_i x[a_i, b_i] \right) y - \lambda y = 0 \\[1em]
y(R) = 0 \quad ; \quad \frac{dy}{dn}(0) = 0 \\[1em]
\|y\|_{L^2}^2 = 0 \quad \text{et} \quad y(0) = 1
\end{array}
\right.
$$

Enfin comme au I) on démontre que (α,y,λ) est un contrôle optimal.
Donc on peut également appliquer le principe de pénalisation pour un problème aux
valeurs propres.
### 3-4 - Cas où les intervalles $[a_i, b_i]$ sont disjoints.

Comme au 2-4 dans ce cas le problème pénalisé en variables mixtes, est équivalent à un problème en variables continues.

On a le problème continu :

$$ (3-16) \qquad \begin{aligned} \tilde{J}_{\varepsilon}(\alpha, y, \lambda) = & \|y-z_d\|_L^2 - v\lambda + \frac{1}{\varepsilon_1} \left\{ \sum_{i=1}^n \alpha_i < x_{[a_i, b_i]} y, y > L \right. \\ & \left. + < - \frac{d^2 y}{dx^2} + 2 \sum_{i=1}^n \alpha_i x_{[a_i, b_i]} y - \lambda y, - \frac{d^2 y}{dx^2} - \lambda y > L^2 \right\} \\ & + \frac{1}{\varepsilon_2} \|y\|_L^2 + \frac{1}{\varepsilon_3} [y(0) - 1]^2 + \frac{1}{\varepsilon_4} \|\frac{\partial y}{\partial n}\|_{L^2(\Gamma)}^2 \end{aligned} $$

Trouver $(\alpha^*, y^*, \lambda^*) \in [0,1]^n \times \mathcal{Y} \times \Lambda$ tel que

$$ (3-17) \qquad \begin{aligned} J(\alpha^*, y^*, \lambda^*) = & \operatorname{Min} J(\alpha, y, \lambda) \\ & (\alpha, y, \lambda) \in [0,1]^n \times \mathcal{Y} \times \Lambda \end{aligned} $$

■

## IV - RESOLUTION NUMERIQUE.

### 4-1 - Cas où le problème pénalisé se ramène à un problème continu.

#### 4-1-1 - Méthode du type GAUSS-SEIDEL, fournissant un minimum local

On notera y l'ensemble des variables continues et $\alpha$ la variable entière.

- Description de l'algorithme :

1) Initialisation de $\alpha$ et $y$, soit $\alpha_0$ et $y_0$
   $n = 0$

2) $n = n + 1$

Calcul du gradient de $\tilde{J}_{\varepsilon}$ par rapport à $\alpha_i$, soit $G_{i}^{n}$.
$$
I_n = \{i \mid G_{\alpha_i}^n < 0 \}
$$

$$
J_n = \{ i \mid G_{\alpha_i}^n > 0 \}
$$

$$
K_n = \{ i \mid G_{\alpha_i}^n = 0 \}
$$

$$
\text{On prend alors : } \alpha_i^n = 1 \quad \text{si } i \in I_{\gamma_1} .
$$

$$
\alpha_i^n = 0 \quad \text{si } i \in J_{\Pi} .
$$

$$
\alpha_i^n = \alpha_i^{n-1} \quad \text{si } i \in K_n .
$$

3) Calcul du gradient de $\tilde{J}_{\varepsilon}$ par rapport à y soit $G_{y_i}^n$.

$y_i^n = y_i^{n-1} - \rho_n G_{y_i}^n$ avec $\rho_n$ optimal

4) $\sum |y_i^n - y_i^{n-1}|^2 < \eta$ si oui → FIN sinon retour en 2).

■

- On définit la notion de minimum local pour une fonctionnelle en variables mixtes ([6] HAMMER-RUBIN), de la façon suivante.

**Définition.** Si $f(\alpha,y)$ est une fonction réelle, avec $\alpha$ variable booléenne.
Si d représente la distance dans l'espace $Y$
et $d_1$ la distance euclidienne classique dans $\mathbb{R}^n$.

On note

$$
W_k^\epsilon(\alpha, y) = \{(\beta, z) \in \{0,1\}^n \times Y \mid d(y,z) \le \epsilon \text{ et } d_1(\beta, \alpha) = k\}.
$$

alors (α,y) est un minimum local pour f s'il existe un ε positif tel que

$$
f(\alpha, y) \le f(\beta, z) \quad \forall (\beta, z) \in W_1^\varepsilon(\alpha, y)
$$

de même on définira un k-minimum local pour f s'il existe un ε positif tel que
$$f(\alpha,y) \leq f(\beta,z) \quad \forall (\beta,z) \in W_k^\epsilon(\alpha,y)$$

- Dans le cas du II (Problème parabolique) pour un tel algorithme on a le résultat suivant :

**Proposition 8 :**

L'algorithme précédent fournit un minimum local pour le problème de contrôle.

En effet dans ce cas la fonctionnelle $\tilde{J}_\epsilon$ est convexe séparément en $\alpha$ et en $y$.

■

D'une manière générale, un tel algorithme fournit une borne supérieure utilisable pour initialiser un Branch and Bound, afin d'obtenir un minimum global du problème.

### 4-1-2 - Méthode utilisant un Lagrangien augmenté.

#### a) principe de la méthode:

Nous considérons le problème suivant :

$$\begin{array}{ll} \text{Min} & f(\alpha,y) \\ \alpha & \in [0,1]^n \\ y & \in Y \end{array}$$

soit

$$\begin{array}{ll} \text{(4-1)} & \text{Min } f(\alpha,y) = \text{Inf} (P) \\ & y \in Y; \quad \alpha \in \mathbb{R}^n \\ & \alpha_i(\alpha_i - 1) \le 0 \quad \forall i = 1, \dots, n. \end{array}$$

On introduit le Lagrangien augmenté suivant : ([8] ROCKAFELLAR)

$$\text{(4-2)} \quad L(\alpha,y,p,r) = f(\alpha,y) + \sum_{i=1}^{n} [p_i \text{Max}(\alpha_i(\alpha_i - 1); -p_i/2r) + r \text{Max}^2(\alpha_i(\alpha_i - 1), -p_i/2r)]$$
$$
\text{pour} \quad \alpha \in \mathbb{R}^n, \quad y \in Y \\
\phantom{\text{pour} \quad} (p,r) \in \mathbb{R}^n \times (0,\infty) = T
$$

On définit le problème dual suivant :

$$
(4-3) \quad \begin{array}{l} \text{Sup (D)} = \text{Sup} \quad \text{Inf} \quad \text{L}(\alpha, y, p, r) \\ \quad (p, r) \in T \quad (\alpha, y) \in \mathbb{R}^n \times Y \end{array}
$$

On introduit alors la fonction de perturbation :

$$
(4-4) \quad v(u) = \begin{cases} \inf f(\alpha, y) & \alpha \in \mathbb{R}^n, y \in Y \\ \alpha_i (\alpha_i - 1) \le u_i & \forall i=1, \dots, n. \end{cases}
$$

On obtient alors le résultat suivant (ROCKAFELLAR [8])

Proposition 9 :

- s'il existe deux nombres réels $r \ge 0$ et $q$ tels que
  $$v(u) \ge q - r|u|^2 \quad \forall u \in \mathbb{R}^n.$$

- s'il existe un voisinage U de l'origine et une fonction $\Pi$ de U dans $\mathbb{R}$ de classe $C^2$ tels que
  $$v(u) \ge \Pi(u) \quad \forall u \in U \text{ et } v(0) = \Pi(0)$$

alors

$$
\inf(P) = \max(D)
$$

b) Application au problème (2-29)

Le problème discrétisé associé au problème (2-29) s'écrit sous
la forme d'une fonction quadratique en (α,y) ; α ayant un ordre partiel égal à 1.

Donc si on note $g(\alpha) = \min_{\epsilon} \tilde{J}_{\epsilon}(\alpha, y)$, $g(\alpha)$ est une fonction quadra-
$y \in Y$

tique. De plus l'optimum est atteint pour les bornes de l'intervalle de définition
de $\alpha$, soit comme $\alpha_i(\alpha_i - 1) \le u_i$

$$ \text{pour} \quad \alpha_i = \frac{1 \pm \sqrt{1 + 4u}}{2} $$

Alors la fonction $v(u)$ est un assemblage continu de fonction de la forme $au + b + c\sqrt{1 + 4u}$. Comme on peut modifier la fonctionnelle $\tilde{J}_{\varepsilon}$ de manière à avoir une solution unique, il existe un voisinage de zéro où $v(u)$ à la forme précédente avec a,b,c constants.

La fonction $v(u)$ vérifie donc les hypothèses de la proposition 9 et donc $\text{Inf}(P) = \text{Max}(D)$. Par conséquent on peut utiliser cet méthode pour résoudre le problème (2-29).

Les résultats obtenus par ces deux méthodes sont donnés au V.

### 4-2 - Cas général.

Dans le cas général la fonctionnelle $J_{\varepsilon}(\alpha, y)$ est quadratique en $\alpha_i$.

#### 4-2-1 - Algorithme de Branch and Bound utilisant la dualité :

L'idée est d'utiliser le résultat d'un problème dual pour éliminer des branches dans l'énumération.

On introduit le problème dual suivant :

$$ \begin{array}{ll} \text{Max} & \text{Min} \quad \left[ J_{\varepsilon}(\alpha, y) + \sum_{i=1}^{n} p_i \alpha_i(\alpha_i - 1) \right] = \text{Sup} (D) \\ \text{(1-5)} & \alpha \in \mathbb{R}^n \; ; \; y \in Y \end{array} $$

$$ \text{Si on note } \text{Inf}(P) = \text{Min}_{\alpha \in \{0,1\}^n} J_{\varepsilon}(\alpha, y) \quad (4-6), \\ \qquad \qquad \qquad \qquad \qquad \qquad y \in Y $$

on a la relation $\text{Sup}(D) \le \text{Inf}(P)$, avec en général inégalité stricte (existance d'un saut de dualité).
On a même la relation :

$$ (4-7) \qquad \begin{array}{l} \displaystyle\underset{\alpha,y}{\text{Min}} \quad \left[ \sum_{i=1}^{n} p_i \alpha_i (\alpha_i - 1) \right] \le \text{Inf}(P). \\ \alpha \in \mathbb{R}^n; \quad y \in Y \end{array} $$

Notons enfin que si $\alpha^*$ solution de (4-5) appartient à $\{0,1\}^n$
alors $\alpha^*$ est solution optimale du problème (4-6)

On en déduit l'algorithme suivant :

1) Initialisation, par résolution du problème (4-6) par un algorithme du type GAUSS-SEIDEL (cf. 4-1-1) on obtient ainsi une borne supérieure $B$ pour $\text{Inf}(P)$.

2) On effectue un algorithme du type Branch and Bound avec comme la règle d'élimination suivante :
On résoud un problème du type (4-5) pour les $\alpha$ non encore fixées. Si on obtient alors une inégalité du genre

$$ \begin{array}{l} \displaystyle\underset{\alpha,y}{\text{Min}} \quad \left[ \sum_{i=1}^{n} p_i \alpha_i (\alpha_i - 1) \right] > B \\ \alpha \in \mathbb{R}^n; \quad y \in Y \end{array} $$

on élimine la branche.

**Remarques :**

1) Dans le cas du II pour $p$ fixée à chaque étape on a une minimisation d'un fonctionnelle quadratique, qui peut donc s'effectuer par la méthode du gradient conjugué.

2) Cet algorithme étant basé sur un principe d'énumération fournit bien entendu la solution exacte au bout d'un nombre fini d'opérations.

### 4-2-2 - Un algorithme utilisant les coupes de GOMORY.

On considère le problème suivant :

$$ (4-8) \qquad \begin{array}{l} \displaystyle\underset{\alpha = b}{\text{Min}} f(\alpha, y) \\ \alpha \in \{0,1\}^n \\ y \in Y \end{array} $$
avec C une matrice à coefficients entiers

b un vecteur entier.

On peut se ramener à un problème sans contraintes. En effet pour $\epsilon$
assez petit le problème suivant admet la même solution que (4-8) ([5] GONDRAN)

$$
(4-9) \qquad \begin{gathered} \text{Min } f(\alpha, y) + \frac{1}{\epsilon} [C\alpha - b]^2 \\ y \in Y; \quad \alpha \in \{0,1\}^n \end{gathered}
$$

On pose alors $\gamma_{ij} = \alpha_i \alpha_j$ et le problème (4-9) est équivalent à

$$
\begin{gathered}
\text{Min } F(\alpha, \gamma, y) \\
y \in Y
\end{gathered}
$$

$$
(4-10) \quad \left\{
\begin{array}{l}
\gamma_{ij} \le \alpha_i \\
\gamma_{ij} \le \alpha_j \\
\gamma_{ij} \ge \alpha_i + \alpha_j - 1
\end{array}
\right.
$$

$\alpha$, $\gamma$ entiers, non négatifs.

où $F(\alpha,\gamma,y)$ est linéaire en $(\alpha,\gamma)$

Algorithme de résolution.

On résoud une suite finie de problèmes continus générés de la
façon suivante :

1) On résoud le problème continu associé à (4-10) par un algo-
rithme de gradient conjugué réduit.

F étant linéaire en (α,γ) on obtient une solution optimale,
sommet du simplexe associé aux contraintes de (4-10).

2) Si la solution obtenue est entière, c'est la solution de (4-10) sinon comme on est à un sommet du simplexe, on peut générer une coupe de GOMORY à partir de cette solution. Et on itère en résolvant le nouveau problème continu associé comme au 1) et ainsi de suite.
3) D'après la théorie des coupes de GOMORY, on est certain d'obtenir la solution du problème initial au bout d'un nombre fini d'itérations.

Cet algorithme se trouve détaillé en Annexe 1.

# V - <u>RESULTATS NUMERIQUES.</u>

## Système gouverné par une équation parabolique.

On reprend l'exemple (2-21) (2-22) (2-23) (2-24) (2-25) avec les données suivantes :

$$f(x,t) = 0 \ ; \ y_0(x) = 0 \ ; \ v = 0$$

et pour $\mu_i$ et $z_d$ les diverses valeurs :

$$\text{Ex 1 :} \quad \mu_i = 1 \quad \forall i \\ z_d(x,t) = 5 \sin 2 \Pi t$$

$$\text{Ex 2 :} \quad \mu_i = 10 \quad \forall i \\ z_d(x,t) = 1 + \sin 2 \Pi t$$

$$\text{Ex 3 :} \quad \mu_i = 3 \quad \forall i \\ z_d(x,t) = 4x(x-1) \sin 2 \Pi t$$

On a appliqué pour ces 3 exemples les méthodes (1-1) et (1-2). Les résultats numériques pour la méthode (1-1) sont représentés sur les figures 1-2-3.

Il est à noter que les deux méthodes fournissent des résultats analogues. Il semble qu'on obtienne dans tous ces exemples le minimum absolu bien que la théorie ne puisse garantir ce résultat.

Pour la méthode (1-2) on obtient :

Exemple 1 : 1,0037 ; 0,9990 ; 1,0039 ; 1,0014 ; -0,0007 ; -0,0039 ; -0,0035 ; -0,0043 ; -0,0026 ; -0,0005 .
Exemple 2 : 0,9970 ; 1,0023 ; 0,9997 ; 0,9989 ; 1,0068 ; -0,0052 ;
-0,0019 ; -0,0063 ; 1,0130 ; 1,0111 .

Exemple 3 : 0,0022 ; 0,0007 ; 0,0015 ; 0,0042 ; 1,0052 ; 0,9923 ;
0,9955 ; 0,9942 ; 0,9923 ; -0,0090 .

Cependant avec la méthode (1-2) on a un temps de calcul (de l'ordre de 2mn 30s sur CII 10070) supérieur à celui de la méthode (1-1) (qui est de l'ordre de 1mn 30s sur CII 10070).
Exemple 1

$$z_d(x,t) = 5 \sin 2 \Pi t$$

$$\mu_i = 1 \quad \forall i$$

<figure><img src="image_5.png" /><figcaption>Fig. 1</figcaption></figure>
Exemple 2

$$z_d(x,t) = 1 + \sin 2 \pi t$$

$$\mu_i = 10 \quad \forall i$$

<figure><img src="image_6.png" /><figcaption>Fig. 2</figcaption></figure>
Exemple 3

$$z_d(x,t) = 4x(x-1) \sin 2 \Pi t$$

$$\mu_i = 3 \quad \forall i$$

<figure><img src="image_7.png" /><figcaption>Fig. 3</figcaption></figure>
# ANNEXE 1.

## I - L'algorithme du gradient conjugué réduit utilisé.

On considère le problème continu suivant :

$$ 
\begin{array}{l}
\text{Min } F(e,y) \\
y \in Y \\
e \ge 0 ; \quad Ae = b .
\end{array}
 $$

On utilise les notations de CEA [1]

Soient : $A_i$ la ième colonne de A
B une base de vecteurs $A_i$
$e_1$ les vecteurs de base
$e_2$ les vecteurs hors base.

On écrit alors $Ae = b \quad <=> \quad Be_1 + Ce_2 = b$

On note : $F(B^{-1}(b - Ce_2), e_2 ; y) = H(e_2,y)$

Soient

$$ U^r = \{e_2 \ge 0 \mid e_1 = B^{-1}(b - Ce_2) \ge 0\} $$

$$ U_b^r = \{e_2 \in R^n \mid e_1 = B^{-1}(b - Ce_2) \ge 0\} $$

$$ U_{hb}^r = \{e_2 \in R^n \mid e_2 \ge 0\} $$

donc

$$ U^r = U_b^r \cap U_{hb}^r . $$

## Algorithme de résolution.

1) Initialisations :

On choisit : I ensemble des indices d'une base $A_i$
$$ u = (e_1 = B^{-1}(b - Ce_2); e_2 ; y) $$
avec $e_1 > 0 ; y \in Y$
2) Soit $G = (G_1, G_2)$ le gradient conjugué au point $(e_2, y)$ pour la fonctionnelle $H$

$$ \text{On pose } d_i = \begin{cases} 0 & \text{si } e_2^i = 0 \\ G_1^i & \text{sinon} \end{cases} \quad G_1^i > 0 $$

alors $D = (d, G_2)$ sera la direction de descente

si $d = 0$ on va en 4)

$d \neq 0$ on va en 3)

$$ 3) \text{ On pose } \rho_b = \sup \rho \\ e_2^r - \rho d \in \mathcal{U}_b^r $$

$$ \rho_{hb} = \sup \rho \\ e_2^r - \rho d \in \mathcal{U}_{hb}^r $$

$$ \hat{\rho} = \min (\rho_b, \rho_{hb}) $$

On choisit alors $\tilde{\rho}$ tel que :

$$ H(e_2 - \tilde{\rho}d, y - \tilde{\rho}G_2) \le H(e_2 - \rho d, y - \rho G_2) $$

$$ \forall \rho \in [0, \hat{\rho}], \text{ avec } \tilde{\rho} \in [0, \hat{\rho}] $$

On définit :

$$ e_2' = e_2 - \tilde{\rho}d $$

$$ e_1' = B^{-1}(b - Ce_2'), $$

$$ y' = \operatorname{Proj}_{\mathbb{Y}} (y - \tilde{\rho}G_2) $$

si $\tilde{\rho} < \rho_b$ on garde la même base $I$ et retour en 2)

$\tilde{\rho} = \rho_b$ on définit une nouvelle base ainsi :

On classe les variables de la manière suivante

$$ 0 = e_1'^{J_1} = \dots = e_1'^{J_S} < e_1'^{J_{S+1}} \le \dots \le e_1'^{J_p} $$

$$ e_2'^{J_2} \ge \dots \ge e_2'^{J_{in}} \ge 0 $$
On prend comme nouvelle base :

$$
\begin{array}{l}
I = \{i, \dots, i_s, j_s+1, \dots, j_p\} \\
\text{et } e_2 = \{e_2^i, \dots, e_2^{i_s}, e_1^{j_s+1}, \dots, e_1^{j_p}\} \\
\text{et on retourne en 2).}
\end{array}
$$

4) à ce niveau deux cas se présentent :

i) les composantes hors base $e_2$ sont toutes nulles, alors on se trouve bien à un sommet du simplexe. On arrête l'algorithme.

ii) Certaines composantes hors base sont non nulles.

Ceci provient du fait que le problème continu associé admet tout un sous-ensemble solution (défini par les variables hors base nulles). Alors on doit déterminer un des sommets de ce sous-ensemble (et plus particulièrement un sommet entier s'il en existe un).

Cette détermination se fait par résolution d'un problème liné-
aire par la méthode du simplexe. (cf. détermination d'une solu-
tion de départ pour le simplexe).

On se trouve alors dans la même situation qu'au i) et on arrête
l'algorithme.

II - Génération des coupes de GOMORY.

On suppose qu'on connait une solution du problème continu, obtenu par
la méthode précédente, et qu'il existe $i_1$ tel que $e_1^{i_1}$ ne soit pas entier.

Soit $((e_1,e_2),y)$ avec $e_2^i = 0 \quad \forall i$
B, C étant les deux matrices définies au I.

alors

$$
e_1 = B^{-1}b - B^{-1}Ce_2
$$

si on note,

$$
B^{-1}b = a_o ; \quad B^{-1}C = D = (d_{ij}) ;
$$

l'égalité précédente s'écrit :

$$
e_1^i = a_o^i - \sum_{j=1}^{n} C_{ij} e_2^j
$$
comme $e_2^j = 0$, la non-intégrité de $e_1^{i_1}$ provient uniquement des coefficients de $B^{-1}$ et b.

Donc on obtient une condition nécessaire, pour que $e_1^{i_1}$ soit entier en écrivant :

$$a_0^{i_1} - \sum_{j=1}^{n} c_{ij}^{i_1} e_2^j \equiv 0 \pmod{1}$$

Si on pose

$$f_0^{i_1} \equiv a_0^{i_1} \pmod{1} \quad \text{avec } 0 \le f_0^{i_1} < 1$$

$$f_{ij} \equiv c_{ij} \pmod{1} \quad \text{avec } 0 \le f_{ij} < 1$$

on obtient

$$f_0^{i_1} - \sum_{j=1}^{n} f_{ij} \cdot e_2^j \equiv 0 \pmod{1}$$

mais comme $f_0^i < 1$, la dernière expression ne peut être entière que si

$$f_0^i - \sum_{j=1}^{n} f_{ij} e_2^j \le 0$$

ce qui fournit la coupe de GOMORY associée à la variable $e_1^{i_1}$.

### III - Description de l'algorithme général de résolution 4-2-2.

Soit P le problème à résoudre :

i) On résoud le problème continu associé à (P) par l'algorithme du gradient conjugué réduit.

ii) Si la solution e est entière on va en iii). Sinon on génère la coupe de GOMORY associée à la première variable de base non entière.

On pose encore (p) le problème déduit de (p) en ajoutant la coupe de GOMORY, comme contrainte et retour en i).

iii) La variable e étant fixée à la valeur trouvée précédemment on termine l'optimisation par rapport à la variable continue y et Y.
## IV - Conclusion sur l'algorithme.

Nous avons donc ramené l'étude du problème quadratique en variables mixtes avec contraintes linéaires sur la variable entière, et un problème linéaire (par rapport à la variable entière), quadratique en variables continues avec des contraintes linéaires ne dépendant que de la dimension du problème.

- De plus nous savons que le simplexe associé à ces contraintes donne une bonne approximation de l'enveloppe convexe des points entiers.

- Le problème à résoudre étant linéaire par rapport à la variable entière l'algorithme du gradient conjugué réduit donne une solution à un sommet du simplexe ce qui permet d'utiliser le principe des coupes de GOMORY.

- D'après la théorie des coupes de GOMORY, nous sommes certains de la convergence de l'algorithme en un nombre fini d'itérations.

- Enfin l'algorithme du gradient conjugué réduit nous permet de ne pas résoudre complètement les problèmes (P) par rapport à y, ce qui provoque un gain important sur le temps de calcul.

## V - Résultats Numériques.

### Exemple 1.

Dans le cas de 3 variables entières, la coupe suivante :

$$-(z_{12} + z_{13} + z_{23} + c_{12} + c_{13} + c_{23}) \leq -1$$

(cij étant la variable d'écart associée à la contrainte)

$$z_{ij} \geq x_i + x_j - 1$$

fournit l'enveloppe convexe des points entiers.

### Exemple 2.

On considère 5 variables entières x_i et 5 variables continues y_i.

$$\text{Min } x,y \quad (-x_2 - 0,5 x_4 - 0,8 x_5 - 2,6 y_1 - y_2 - 0,5 y_3 - 6 y_5 + x_2 x_3 \\ + x_1 y_1 + x_4 y_2 + y_3 y_4 + x_5^2 + y_1^2 + y_2^2 + y_3^2 + y_4^2 + y_5^2)$$
On obtient en une itération la solution exacte entière :

$$x = (0,1,0,1,0)$$

$$y = (1,3 ; 0 ; 0,335 ; -0,1658 ; 3)$$

le temps de calcul est 7,8 s sur CII 10070 .
BIBLIOGRAPHIE

[1] BEALE
On quadratic programming
(Naval Research Logistics Quaterly Vol 6, 1959).

[2] CEA
Optimisation, théorie et algorithmes (Dunod).

[3] FISCHER - SHAPIRO
Constructive duality in integer programming
(SIAM J. Appl. Math. Vol 27 N° 1 July 1974).

[4] GARFINKEL - NEMHAUSER
Integer Programming (1972).

[5] GONDRAN
Une approche par pénalisation sur les variables des programmes quadratiques bivalents avec contraintes d'égalité.
(Bulletin EDF Etudes et Recherches N° 1 1972.)

[6] HAMMER - RUBIN
Some remarks on quadratic programming with 0-1 variables
(R.I.R.O. Vol 3 1970).

[7] LIONS
Contrôle optimal de systèmes gouvernés par des équations aux dérivées partielles.
(Dunod Gauthier - Villars 1968).

[8] ROCKAFELLAR
Augmented Lagrange multiplier functions and duality in nonconvex programming.
(SIAM J. Control Vol 12 N°2 May 1974).

[9] YVON
Application de la pénalisation à la résolution d'un problème de contrôle optimal.
(Thèse 3e cycle Paris 1968).