# Utilisation de la dualité dans les problèmes non convexes

Claude Lemaréchal

► To cite this version:

Claude Lemaréchal. Utilisation de la dualité dans les problèmes non convexes. [Rapport de recherche]
IRIA-RR-016, IRIA. 1973, pp.42. hal-04715980

HAL Id: hal-04715980

https://inria.hal.science/hal-04715980v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

# Utilisation de la dualité dans les problèmes non convexes

Claude Lemarechal

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

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n°16

avril 1973
# UTILISATION DE LA DUALITÉ DANS LES PROBLEMES NON CONVEXES

C. Lemaréchal

(présenté par A. Bensoussan)

## RESUME

On montre dans cet article que l'algorithme d'UZAWA peut, sous certaines conditions, s'étendre à des problèmes d'optimisation où le lagrangien n'est pas strictement convexe par rapport à x, et où le critère n'est pas continu.

On peut alors utiliser un algorithme se décomposant en deux phases :

1) Maximisation de la fonction duale. On montre, en utilisant un résultat de DANSKIN, que le problème se ramène à la maximisation d'une fonction concave non différentiable. On donne ici une généralisation de la notion de gradient, ainsi qu'un algorithme du type "ε-perturbation" de l'algorithme de "plus rapide montée".

2) Obtention d'une solution sous-optimale réalisable. Les variables duales optimales ne correspondent en général pas à une solution primale réalisable (et encore moins optimale). On montre alors que l'on peut cependant utiliser le résultat de la première phase pour trouver une solution primale réalisable, et proche de l'optimum absolu.
# I - INTRODUCTION.

On commence par donner un exemple concret (1) qui a motivé cet article.

## 1.1. UN PROBLEME D'ALLOCATION DE RESSOURCES.

On veut satisfaire la demande en n articles ; on dispose pour cela de m machines. Chaque article n'a à être fabriqué que par une machine, mais chaque machine peut en fabriquer successivement de plusieurs types. Il faut tenir compte des temps et des coûts de lancement.

On désigne par :

$T$ : la longueur de la période étudiée (le problème est stationnaire).

$D_i$ : la demande en article i.

$T_j$ : Le temps disponible pour la machine j.

$\alpha_{ij}$ (resp. $\beta_{ij}$) : le coût marginal de production (resp. lancement).

$\gamma_{ij}$ : le coût marginal de stockage (y compris le coût de l'argent).

$a_{ij}$ : le temps de fabrication d'une unité d'article.

$b_{ij}$ : le temps de lancement d'une série.

Pour formuler le problème, on désigne par :

$x_{ij}$ : la quantité de produit i fabriquée par la machine j.

$y_{ij}$ : le nombre de séries économiques d'article i passées sur la machine j.

Le coût de stockage est alors donné par la formule bien connue

$$T\gamma_{ij} \frac{x_{ij}}{y_{ij}}$$

<footnote>(1) Posé par la Compagnie Saint-Gobain-Pont-à-Mousson.</footnote>
Le coût à minimiser se formule alors :

$$
\text{(P1)}}
\left\{
\begin{array}{ll}
\displaystyle\sum_{i=1}^{n} \sum_{j=1}^{m} J_{ij}(x_{ij}, y_{ij}) & = \sum_{i=1}^{n} \sum_{j=1}^{m} (\alpha_{ij}x_{ij} + \beta_{ij}y_{ij} + T \gamma_{ij} \frac{x_{ij}}{y_{ij}}) \\[1.5em]
\text{Les contraintes de disponibilité de chaque machine } j \text{ s'écrivent} & \\
\displaystyle\sum_{i=1}^{n} (a_{ij}x_{ij} + b_{ij}y_{ij}) \le T_j & \quad j=1, \dots, m \\[1.5em]
\text{Les contraintes de demande, s'écrivent} & \\
\displaystyle\sum_{j=1}^{m} x_{ij} & = D_i
\end{array}
\right.
$$

Enfin, on a évidemment $x_{ij} \ge 0, y_{ij} \ge 0, J_{ij}(0,0) = 0$

On se trouve alors devant un problème de minimisation sous contraintes li-
néaires. Mais l'application (x,y) ↪ → J(x,y) n'est pas convexe. Nous avons
commencé par des expériences avec le gradient réduit. Infailliblement, la
méthode convergeait très vite vers un optimum local très mauvais. Le problème
se posait donc de trouver une solution initiale convenable.

Pour cela, on peut remarquer que, les contraintes de disponibilité n'exis-
tant pas, le problème serait très simple. D'où l'idée de penser à une mé-
thode duale. Mais dans un tel problème, l'existence d'un point-selle n'est
pas assurée. Il y a donc lieu de combiner une méthode duale avec une méthode
primale. Schématiquement, (les détails seront donnés au §6) on peut imaginer
un algorithme se divisant en trois phases :

lère Phase :

Résolution du problème dual par une méthode de type UZAWA.
**2ème Phase :**

Si le problème dual ne fournit pas de point-selle (parce qu'il n'en existe pas), détermination d'un point $(x,y)$ réalisable.

**3ème Phase :**

Application d'un algorithme standard de minimisation sous contraintes linéaires utilisant le point trouvé à la 2ème phase.

## 1.2. GENERALISATION - HYPOTHESES, NOTATIONS.

D'une façon générale, on peut se poser le problème suivant :

$$ (P2) \quad \left\{ \begin{array}{ll} \min & J(x) \quad x \in \mathbb{R}^n \\ & x \in D \quad D \subset \mathbb{R}^n \\ & g_i(x) \le 0 \quad i=1, \dots, m. \end{array} \right. $$

pour lequel on décide d'utiliser une méthode duale. On considère donc le

lagrangien :

$$ (1) \quad \left\{ \begin{array}{ll} L(x, \lambda) = J(x) + \sum_{i=1}^{m} \lambda_i g_i(x) = J(x) + (\lambda, g(x)). & \\ \lambda_i \ge 0 & x \in D \\ & x \in \mathbb{R}^n \end{array} \right. $$

Au problème P2, on associe le problème suivant :

$$ P(\lambda) \quad \left\{ \begin{array}{ll} \min & L(x, \lambda) \\ & x \in D \end{array} \right. $$

on pose

$$ (2) \quad h(\lambda) = \min_{x \in D} L(x, \lambda) $$
$$
(3) \quad X(\lambda) = \{ x \in D / L(x, \lambda) = h(\lambda) \} .
$$

Dans toute la suite, nous ferons les hypothèses fondamentales suivantes :

H1 ) J est semi-continue inférieurement

$g_i$ est continue, $i=1,...,m$.

H2 ) { Soit D borné
{ Soit : pour tout $\lambda$, $L(x,\lambda) \to +\infty$ lorsque $|x| \to +\infty$

H3 ) ∃ x₀ ∈ D tel que gᵢ(x₀) < 0 i=1,...,m.

Remarque 1.1

Critique des hypothèses fondamentales.

1) L'hypothèse H1) est réellement minimale. Sans elle, on n'aurait aucun résultat de régularité sur la fonction h(λ). Notons cependant qu'elle n'a plus de raison d'être si D est un ensemble fini (cas de la programmation en nombres entiers).

2) L'hypothèses H2) est destinée à donner un sens au problème P(λ).

Dans ces conditions, la fonction duale h(λ) est concave, continue ; pour tout λ, X(λ) est un ensemble non vide, fermé, borné. De plus, il est stable lorsque λ varie. En effet :

Lemme 1.1

Soit B un ensemble borné dans $R^m$.

∀ M > 0, ∃ A ne dépendant que de M et de B tel que

si $\lambda \ge 0$, $\lambda \in B$, $|x| \ge A$

alors $L(x, \lambda) \ge M$.
## Démonstration

B peut être plongé dans un polyèdre convexe de points extrémaux

$\lambda_1, \dots, \lambda_K$. Tout $\lambda$ de B s'écrit alors

$$ \lambda = \sum_{i=1}^{K} u_i \lambda_i \quad u_i \ge 0, \sum u_i = 1 $$

Pour tout M, $\exists$ A tel que si $|x| \ge A$, alors

$$ L(x, \lambda_i) \ge M \quad i=1, \dots, K $$

$$ \text{Donc, } \sum u_i L(x, \lambda_i) \ge \sum u_i M $$

D'après la linéarité en $\lambda$, ceci veut dire simplement que $L(x,\lambda) \ge M$. Cette hypothèse a lieu en particulier dans l'un des cas suivants :

a) J est coercive : $\frac{J(x)}{|x|} \to +\infty$ lorsque $|x| \to +\infty$ et les $g_i$ sont linéaires

b) J et les $g_i$ sont linéaires à coefficients positifs, D est contenu dans le 1er orthant (c'est le cas du problème (P1) du §1.1).

3) Quant à l'hypothèse H3), c'est une hypothèse de qualification assurant une solution au problème dual (i.e. maximiser $h(\lambda)$).

En effet, choisissons $x_o$ comme en H3). Pour tout $\lambda$, on a

$$ h(\lambda) \le L(x_o, \lambda). $$

Si $|\lambda| \to \infty$ avec $\lambda_i \ge 0, L(x_o, \lambda) \to -\infty$, ce qui assure que le maximum de $h(\lambda)$ est atteint en un point $\bar{\lambda}$ à distance finie.

## Remarque 1.2

Ces trois hypothèses sont minimales. En fait, nous verrons au §4 que, pour résoudre le problème dual, nous aurons en outre besoin de l'hypothèse
H4) On sait calculer explicitement l'ensemble

$$
X_{\varepsilon}(\lambda) = \{ x \in D/L(x,\lambda) \le h(\lambda) + \varepsilon \}
$$

De plus, nous verrons au §5 que pour résoudre le problème primal (P2) à
partir d'une solution duale, il nous faut également

H5) Les $g_i$ sont convexes.

Un cas particulier important sera le cas où toutes les fonctions sont dé-
couplées :

$$
J(x) = \sum_j J_j(x_j) , \quad g_i(x) = \sum_j g_{ji}(x_j) \quad \blacksquare
$$

Dans le cadre de ces hypothèses, les méthodes duales ont déjà fait l'objet
de nombreuses publications. Des essais numériques, en particulier, ont été
faits dans (4) , (6) , (12) , (18).

EVERETT (7) a montré que pour un $\lambda$ donné, les solutions de $P(\lambda)$ sont solutions d'un problème (P2) perturbé. La question se posait alors de savoir quel $\lambda$ utiliser pour avoir la plus petite perturbation possible sur (P2). Pour cela, il était naturel de chercher à maximiser la fonction duale (2) ; ce qui a donné lieu à l'algorithme de BROOKS et GEOFFRION (2) qu'on peut résumer ainsi :

1. Soient $(\lambda_0, x_0)$, $(\lambda_1, x_1)$, ..., $(\lambda_k, x_k)$

ou $x_i \equiv X(\lambda_i)$

2. Résoudre le problème linéaire en $(\lambda, v)$ suivant :

$$
\text{(P3)} \quad \left\{
\begin{array}{ll}
\max & v \\
\text{J}(x_i) + (\lambda, g(x_i)) & \ge v \quad \text{i=0,\dots,k} \\
\lambda & \ge 0
\end{array}
\right.
$$
3. Soit $\lambda_{k+1}$ une solution de ce problème. Déterminer un $x_{k+1}$ en résolvant $P(\lambda_{k+1})$, faire $k=k+1$ et aller en 1.

On pourra remarquer que le dual de (P3) est

$$
\begin{array}{ll}
\min & \displaystyle\sum_{j=0}^{k} \alpha_j J(x_j) \\
\\
\left\{
\begin{array}{l}
\displaystyle\sum_{j=0}^{k} \alpha_j g(x_j) \le 0 \\[1em]
\displaystyle\sum_{j=0}^{k} \alpha_j = 1, \quad \alpha_j \ge 0.
\end{array}
\right.
\end{array}
$$

qui correspond à l'algorithme des colonnes de DANTZIG-WOLFE (13) .

L'algorithme de BROOKS et GEOFFRION a été étudié en détails dans (10).

On peut en trouver des applications dans (20) , où on traîte un problème
en nombres entiers. ■

Dans cet article, on considère la fonction duale h(λ) en tant que fonction concave non différentiable, et on attaque directement sa maximisation par un algorithme de type "plus rapide montée".

Le plan sera le suivant : au §2, on expose les résultats essentiels uti-
lisés par la suite. Au §3, on traîte la recherche de la meilleure direction
de montée pour la fonction duale.

Au §4, on donne un algorithme convergent de maximisation de la fonction duale. Au §5, on expose l'utilisation d'un point max-min obtenu aux §3 et 4, pour chercher une solution primale réalisable. Au §6, on donne l'algorithme utilisé pour résoudre le problème §1.1.
## II - RESULTATS FONDAMENTAUX.

Dans toute la suite, nous utiliserons fondamentalement les trois théo-
rèmes suivants :

### Théorème 2.1

(DANSKIN (3) ; la démonstration se trouve également dans (13). Une démonstration plus intéressante pour notre objet est donnée dans (11)).

Soit E un espace topologique, SCE

$$F : E \times \mathbb{R}^m \longrightarrow R \quad F = F(x; u_1, u_2, \dots, u_m).$$

Hypothèses :

i) S est compact,

ii) F est continue,

iii) $\displaystyle\frac{\partial F}{\partial u_i}$ sont continues pour $i=1, \dots, m$.

Alors, posant

$$\phi(u) = \min_{x \in S} F(x,u), \quad X(u) = \{x \in S | F(x,u) = \phi(u)\}$$

et

$$D \phi(u;s) = \lim_{\alpha \to 0^+} \frac{\phi(u+\alpha s) - \phi(u)}{\alpha},$$

on a

$$D \phi(u;s) = \min_{x \in X(u)} \sum_{i=1}^{m} s_i \frac{\partial F(x,u)}{\partial u_i}$$

### Corollaire immédiat

Partout où elle est définie, la fonction $h(\lambda)$ définie par (2) est sous-différentiable, et les dérivées directionnelles sont données par la formule

$$(4) \qquad Dh(\lambda;s) = \min_{x \in X(\lambda)} (s,g(x)).$$
La proposition (4) reste vraie même si J est semi-continue inférieurement (Cf. (11)).

Notons d'ailleurs que la fonction $h(\lambda)$ est concave.

Ce théorème nous permettra d'une part de définir des directions de montée pour $h(\lambda)$, et d'autre part d'obtenir une condition nécessaire et suffisante caractérisant un maximum de cette même fonction.

**Théorème 2.2**

(EVERETT (7)).

Soit $\lambda \ge 0$ fixé. Si $\bar{x} \in X(\lambda)$, alors $\bar{x}$ est solution du problème suivant :

$$ P(\lambda, \bar{x}) \left\{ \begin{array}{ll} \min & J(x) \\ \\ x \in D \\ \\ g_i(x) \le y_i \\ \\ y_i = g_i(\bar{x}) & \text{si } \lambda_i > 0 \\ \\ y_i \ge g_i(\bar{x}) & \text{si } \lambda_i = 0 \end{array} \right. $$

**Théorème 2.3**

dit $\in$-théorème d'EVERETT.

Soit $\lambda \ge 0$ fixé. Si $\bar{x}$ vérifie

$$ L(\bar{x}, \lambda) \le L(x, \lambda) + \varepsilon \quad \forall x \in D, $$

alors $\bar{x}$ vérifie

$$ J(\bar{x}) \le J(x) + \varepsilon \quad \forall x \in D(\bar{x}, \lambda) $$

$$ \text{où } D(\bar{x}, \lambda) = \{ x \in D | g_i(x) \le y_i, \begin{array}{l} y_i = g_i(\bar{x}) \quad \text{si } \lambda_i > 0 \\ y_i \ge g_i(\bar{x}) \quad \text{si } \lambda_i = 0 \end{array} \}. $$
Ces deux théorèmes nous permettront, à partir d'un point $x_o$ supposé proche d'un optimum de (P1), de trouver un point réalisable $x_l$ proche de $x_o$, donc d'un optimum.

Supposons en effet que pour un $\lambda$ donné, $x_o$ résolve le problème (P$\lambda$) et qu'il soit possible de trouver un point $x_l$ tel que

$$i) \quad g_i(x_l) \le 0$$

$$ii) \quad \lambda_i g_i(x_l) = 0$$

$$iii) \quad L(x_l, \lambda) = L(x_o, \lambda) + \varepsilon .$$

Alors, on saura que $x_l$ résout à $\varepsilon$ près le problème fondamental.

La recherche d'un point $\lambda$ tel qu'il soit possible d'avoir i), ii), iii) constitue la première phase de la méthode, que nous exposons maintenant. La recherche de $x_l$ constitue le §5.

### III - ÉTUDE DU "GRADIENT" DE LA FONCTION DUALE.

#### 3.1. LE PROBLEME.

L'idée fondamentale de la méthode d'UZAWA (c'est à dire l'incrémentation des variables duales par la formule $\lambda_{n+1} = \lambda_n + \rho g(x_n)$) est très naturelle et correspond à une pénalisation ajustée à chaque contrainte (ce fait a en particulier été remarqué dans (17)).

Dans le cas des problèmes convexes, cette méthode n'est autre que la méthode du gradient appliquée à la maximisation de la fonction duale.

Il est donc normal d'essayer de maximiser la fonction duale pour trouver une valeur privilégiée des variables duales.

Pour cela, il est nécessaire de définir des directions de montées $s_n$ et des pas d'incrémentation $\rho_n$ de façon à pouvoir utiliser la formule
$$
(5) \qquad \lambda_{n+1} = \lambda_n + \rho_n s_n .
$$

Pour un $\lambda$ donné, on appellera gradient de la fonction duale une direction $s$ maximisant la dérivée directionnelle $Dh(\lambda;s)$.

On appellera direction de montée une direction s telle que $Dh(\lambda;s) > 0$.

3.2. <u>RECHERCHE D'UNE DIRECTION DE MONTEE.</u>

Pour un λ donné, on choisira donc une direction compatible maximisant
la dérivée directionnelle de la fonction duale. Se souvenant de (4), la re-
cherche d'une telle direction s se ramène alors au problème suivant :

$$
\begin{array}{ll}
\text{(P4)} & \text{Trouver} \\
& \alpha_i = \max_{|s|=1} \min_{x \in X(\lambda_i)} (s,g(x)). \\
& s_i \ge 0 \quad i \in I \\
\text{où} & I = \{i / \lambda_i = 0\} .
\end{array}
$$

Remarque 3.1

La contrainte $s_i \ge 0$ pour $i \in I$ est essentielle car l'ensemble des directions de montée n'est pas un demi-espace, contrairement à ce qui se passe dans le cas différentiable. Donc, la projection du "gradient" n'est pas forcément une direction de montée. ■

Le problème (P4) est équivalent au problème suivant

$$
\left\{
\begin{array}{ll}
\max & \alpha \\
(s,g(x)) & \ge \alpha \quad \forall x \in X(\lambda) \\[1em]
\sum_{i=1}^{m} & s_i^2 = 1 \\[1em]
& s_i \ge 0 \quad i \in I.
\end{array}
\right.
$$

(P5) n'est pas un problème convexe, et possède de plus une contrainte non
linéaire. Pour le résoudre, nous allons donc étudier le problème auxiliaire
suivant

$$
\text{(P6)} \quad \left\{
\begin{array}{ll}
\max & \alpha \\[1ex]
\text{(s,g(x))} & \ge \alpha \quad \forall x \in X(\lambda) \\[1ex]
\sum_{i=1}^{m} & s_i^2 \le 1 \\[1ex]
& s_i \ge 0 \quad \text{i} \in I.
\end{array}
\right.
$$

qui est le problème (P5) "convexifié", et

$$
\text{(P7)} \quad \left\{
\begin{array}{ll}
\min & \sum_{i=1}^{m} s_i^2 \\[1ex]
\text{(s,g(x))} & \ge 1 \quad \forall x \in X(\lambda) \\[1ex]
s_i & \ge 0 \quad \text{i} \in I.
\end{array}
\right.
$$

Remarque 3.2

(P7) est un simple problème de projection sur un convexe. Bien entendu,
on ne saura le résoudre que si X(λ) est une ensemble fini ; mais cette
hypothèse n'est nullement indispensable pour la suite.

Nous nous proposons alors de démontrer le

Théorème 3.1

1) Si les contraintes de (P7) sont incompatibles, alors (P4) a une solution $\alpha_4$ négative ou nulle, et le point $\lambda$ considéré maximise la fonction duale.

2) Si le problème (P7) admet une solution $s_7$, elle est unique, non nulle, et $\frac{s_7}{|s_7|}$ résout le problème (P4).
Le seul point non trivial est la colinéarité de $s_7$ et $s_4$. Cependant, la démonstration est compliquée du fait que (P4) et (P7) ne sont pas toujours équivalents. La démonstration tient donc en une suite de lemmes. Posons

$$ (6) \qquad R^{I+}(\lambda) = \{ s \in \mathbb{R}^m \mid \forall i, s_i \ge 0, i \in I \}. $$

$R^{I+}(\lambda)$ est ainsi l'ensemble des directions réalisables au point $\lambda$.

Désignons par $\alpha_5, \alpha_6$ les valeurs optimales du critère dans (P5) et (P6).

**Lemme 3.1**

Les trois propositions suivantes sont équivalentes.

i) (P5) a une solution $\alpha_5 \le 0$

ii) Les solutions optimales de (P6) annulent le critère ($\alpha_6=0$).

iii) Les contraintes de (P7) sont incompatibles.

**Démonstration**

i) $\Rightarrow$ ii. C'est immédiat si l'on remarque que le point $(\alpha=0, s=0)$ est réalisable dans (P6). Montrons qu'il est optimal

L'assertion i) signifie que

$$ \forall s \in R^{I+}(\lambda), \quad |s| = 1 \quad \Rightarrow \quad \exists x \in X(\lambda) \quad \text{tel que } (s,g(x)) \le 0. $$

Comme $R^{I+}(\lambda)$ est un cône, cela entraîne que

$$ \forall s \in R^{I+}(\lambda), s \neq 0 \quad \left\{ \begin{array}{l} \Rightarrow \exists x \in X(\lambda) : \left( \frac{s}{\|s\|}, g(x) \right) \le 0. \\ k \ge 1 \end{array} \right. $$

Comme les points de la forme $\frac{s}{\|s\|}$ recouvrent l'ensemble des points réalisables dons (P6), (0,0) est bien optimal dans (P6).

ii) $\Rightarrow$ iii). Supposons qu'il existe un point réalisable dans (P7) :

$$ \exists s \in R^{I+}(\lambda) \quad \text{t.q. } (s,g(x)) \ge 1. \quad \forall x \in X(\lambda) $$
Cela entraîne en particulier que $s \neq 0$. En divisant par $|s|$, on obtient

$$ \exists s' \equiv R^{I+}(\lambda), |s'| = 1, (s',g(x)) \geq \frac{1}{|s|} > 0 \quad \forall x \equiv X(\lambda). $$

Ce qui contredit ii).

iii) $\Rightarrow$ i). Démontrons le encore par l'absurde.

Supposons qu'il existe $\alpha_5 > 0$ tel que

$$ \exists s \equiv R^{I+}(\lambda) \text{ tel que } |s| = 1 \text{ et } (s,g(x)) \geq \alpha_5 > 0 \quad \forall x \equiv X(\lambda). $$

Alors, le vecteur $\frac{s}{\alpha_5}$ vérifie

$$ \frac{s}{\alpha_5} \equiv R^{I+}(\lambda), \left(\frac{s}{\alpha_5}, g(x)\right) \geq 1 \quad \forall x \equiv X(\lambda) \text{ ce qui contredit iii).} $$

Ce lemme 3.1 démontre la clause 1) du théorème 3.1. En effet, si on a iii), aucune direction compatible ne fournit une dérivée directionnelle positive. Comme h est concave, $\lambda$ maximise h.

### Remarque 3.3

La négation de ii) dans le lemme précédent est : $\alpha_6 > 0$

En effet, le point $(\alpha=0, s=0)$ étant réalisable dans (P6), on a nécessairement $\alpha_6 \geq 0$. Le lemme 3.1 est donc équivalent au suivant :

### Lemme 3.2

Les trois propositions suivantes sont équivalentes :

* j) (P5) a une solution $\alpha_5 > 0$

* jj) (P6) a une solution $\alpha_6 > 0$

* jjj) Dans (P7), les contraintes sont compatibles.
Nous nous plaçons maintenant dans les hypothèses de ce lemme, c'est-à-dire dans
le cas où $\lambda$ne maximise pas h; nous montrons alors l'équivalence entre (P4) et
(P7).

**Lemme 3.3**

$\alpha_6 > 0 \Rightarrow (P6) \text{ admet une solution unique } s_6, \text{ et } |s_6| = 1.$

Démonstration

Montrons d'abord que toute solution s de (P6) est de norme 1.

Comme $\alpha_6 > 0$, il existe un point réalisable $(s,\alpha)$ non nul dans (P6),
c'est-à-dire tel que

$$
\left\{
\begin{array}{l}
|s| \le 1 \\
\\
(s,g(x)) \ge \alpha > 0 \quad \forall x \in X(\lambda) \quad \text{(donc, en particulier, s≠0)} \\
\\
s_i \ge 0 \quad \text{si } i \in I
\end{array}
\right.
$$

Il est alors évident que ($\frac{s}{|s|}$, $\frac{\alpha}{|s|}$) est également réalisable. Or, si
$|s| < 1$, ce point est manifestement meilleur que le point $(s,\alpha)$.

Donc, un point $(s, \alpha)$ tel que $|s| < 1$ ne saurait être optimal.

Soient maintenant deux solutions $s_6$ et $s'_6$ optimales, donc de norme 1. Comme
le problème (P6) est convexe, toute combinaison convexe de solutions est
encore solution. En particulier $\frac{1}{2}(s_6 + s'_6)$ est solution. Donc, est de norme
1, ce qui entraîne

$s_6 = s'_6$ (stricte convexité de la norme). $\blacksquare$

Comme l'ensemble des points réalisables de (P5) est contenu dans l'ensemble
des points réalisables de (P6), on déduit de ce lemme 3.3 :

**Corollaire 3.1**

Dans le cas de j), jj), jjj), les solutions de (P5) et de (P6) sont
uniques et identiques.
**Remarque 3.4**

En ce qui concerne (P7), il y a nécessairement unicité, car les contraintes sont linéaires et le critère est strictement convexe.

**Lemme 3.4**

$$jjj) \Rightarrow \left\{ \begin{array}{l} - \text{Le problème (P6) a une solution unique } (\alpha_6, s_6). \\ - \text{Le problème (P7) a une solution unique } s_7. \\ - \text{On a alors } \alpha_6 = \frac{1}{|s_7|} \text{ et } \alpha_6 s_7 = s_6. \end{array} \right.$$

**Démonstration**

Seule la troisième proposition reste à démontrer.

Tout d'abord, remarquons que $\alpha_6 > 0$ et $s_7 \neq 0$ $\frac{s_7}{|s_7|} \simeq R^{I+}(\lambda)$ et est de norme 1.

D'autre part,

$$(\frac{s_7}{|s_7|}, g(x)) \geq \frac{1}{|s_7|} \quad \forall x \in X(\lambda).$$

Donc, $(\frac{1}{|s_7|}, \frac{s_7}{|s_7|})$ est réalisable dans (P6), ce qui entraîne nécessairement

$$ (7) \qquad \frac{1}{|s_7|} \leq \alpha_6 $$

De plus, comme la solution de (P6) est unique,

$$ (8) \qquad \frac{1}{|s_7|} = \alpha_6 \quad \Rightarrow \quad \frac{s_7}{|s_7|} = s_6 $$

Or, de la même façon, $\frac{s_6}{\alpha_6}$ est réalisable dans (P7). Donc

$$ (9) \qquad \left| \frac{s_6}{\alpha_6} \right| \geq |s_7| \quad , \text{ ce qui signifie que} $$

$$ (10) \qquad \frac{1}{|s_7|} \geq \alpha_6 \quad (\text{puisque } |s_6| = 1). $$
En rapprochant (7) et (10) et en tenant compte de (8), le lemme se trouve
démontré. ■

**Corollaire 3.2**

Le lemme 3.4 et le corollaire 3.1 démontrent la clause 2) du théorème 3.1.

De plus, on a

$$
(11) \qquad Dh(\lambda, s_7) = 1.
$$

Remarque 3.5

Dans tout ce qui précède, nous avons implicitement supposé que les g(x)
ne sont pas tous nuls pour x ≃ X(λ). Le seraient-ils d'ailleurs, le problème
(P4) n'aurait pas de sens, et λ maximiserait évidemment la fonction duale.

Remarque 3.6

Dans la formulation de (P7), il suffit de n'envisager que les contraintes
(s,g(x)) ≥ 1 où x est tel que g(x) soit point extrêmal de g(x(λ)).

3.3. CAS OU ON NE PEUT PAS UTILISER EXPLICITEMENT L'ENSEMBLE X(λ).

Au §3.2, nous avons caractérisé d'une manière simple la direction de
plus rapide montée dans l'espace Rm muni de la norme euclidienne. Pour cela,
nous avons remplacé le problème (P5) par le problème (P7). Notons d'ailleurs
que ce paragraphe aurait été très simplifié si on avait choisi pour Rm la
norme l∞ : |s| = max_l |s_l| ; le problème (P6) aurait alors été linéaire,
et (P7) n'aurait plus eu de raison d'être. Ceci dit, on peut se trouver dans
l'une des situations suivantes :

- Soit on ne sait pas expliciter l'ensemble X(λ).

- Soit (P7) est mal conditionné parce que X(λ) est trop grand.

Dans l'un et l'autre cas, en supposant que X(λ) est un ensemble fini,
on peut trouver une direction de montée-non optimale, mais utilisable quand
même.
En effet, plaçons-nous dans la situation où, étant donné un $\lambda \ge 0$, on sait calculer $h(\lambda)$ et un $x \in X(\lambda)$.

Supposons qu'en un point $\lambda$, on connaisse

$$ - E_k = \{ x_1, x_2, \dots, x_k \} \subset X(\lambda) $$

- Une direction $s_k$ telle que $(s_k, g(x_i)) \ge 1 \quad i=1, \dots, k$.

Le problème est de passer de $\lambda$ à $\mu$ tel que $h(\lambda) < h(\mu)$.

Pour cela, on définit une suite $\rho_n$ de nombres positifs tendant vers 0 ;
on calcule $h(\lambda+\rho_n s_k)$, et un $x_n = \lambda+\rho_n s_k$.

Si, pour un $n$ donné, $h(\lambda+\rho_n s_k) > h(\lambda)$, le problème est résolu.

Sinon, il existe un $x = \lambda+\rho_n s_k$ tel que $(s_k, g(x)) \le 0$ (donc, $x \notin E_k$).
On a alors le résultat suivant :

### Théorème 3.2

Toute valeur d'adhérence $x$ de la suite $x_n$ ainsi définie vérifie

$$ (i) \quad x \in X(\lambda) $$

$$ (ii) \quad (s_k, g(x)) \le 0 $$

### Démonstration

La suite $x_n$ est bornée (lemme 1.1)

(i) résulte de la semi-continuité supérieure de la multi-application

$\lambda \mapsto X(\lambda)$. D'autre part, $h(\lambda+\rho_n s_k) \le h(\lambda) \quad \forall n$ équivaut à dire

$$ J(x_n) + (\lambda, g(x_n)) + \rho_n(s_k, g(x_n)) \le h(\lambda). $$

donc, $\rho_n(s_k, g(x_n)) \le h(\lambda) - L(x_n, \lambda) \le 0 \quad \forall n$
ce qui prouve (ii). ■

En incorporant donc n'importe quelle valeur d'adhérence $k$ à l'ensemble $E_k$ et en cherchant $s_{k+1}$ tel que
$$ (s_{k+1}, g(x_i)) \ge 1 \quad i=1, \dots, k+1 $$

On peut réitérer le processus. si $X(\lambda)$ est un ensemble fini, on obtiendra ainsi soit une direction de montée soit la certitude que $\lambda$ maximise la fonction duale.

## IV - UN ALGORITHME DE MAXIMISATION DE LA FONCTION DUALE.

### 4.1. REMARQUES NUMERIQUES.

D'un point de vue numérique, l'ensemble $X(\lambda)$ n'a pas de sens.

D'autre part, la fonction duale n'étant pas différentiable, un algorithme de plus rapide montée peut converger vers un point $\lambda$ qui n'est pas un maximum (Cf. (15)). On remarquera à ce sujet l'analogie entre le problème (P5) et le problème de la recherche d'une direction compatible dans l'algorithme de ZOUTENDIJK (Cf. (21)). Or, on sait que cet algorithme peut se bloquer sur les contraintes et qu'il convient de lui adapter un algorithme dit de $\varepsilon$-perturbation ( (21) chap. 13).

On est donc amené à envisager, au lieu de $X(\lambda)$, l'ensemble

$$ (12) \qquad X_{\varepsilon}(\lambda) = \{ x \in D/L(x,\lambda) \le h(\lambda) + \varepsilon \}. $$

et à remplacer le problème (P7) par le problème

$$ P_{\varepsilon}(\lambda) = \begin{cases} \min & |s|^2 \\ (s,g(x)) \ge 1 & \forall x \in X_{\varepsilon}(\lambda) \\ s \in \mathbb{R}^{I+}(\lambda) & \end{cases} $$

Ce problème a un sens, grâce au résultat suivant :

**Lemme 4.1**

$X(\lambda)$ est un ensemble fermé.
## Démonstration

Soit $x_n \in X_\varepsilon(\lambda)$ et $x_n \to x$

$$L(x_n, \lambda) \le h(\lambda) + \varepsilon$$

D'après la semi-continuité inférieure de $x \to L$, on a donc

$$L(x, \lambda) \le \liminf L(x_n, \lambda) \le \limsup L(x_n, \lambda) \le h(\lambda) + \varepsilon$$

donc $x \in X_\varepsilon(\lambda)$. ■

## 4.2. UN ALGORITHME.

Nous envisageons, pour simplifier, le cas où les $\lambda_i$ sont non contraintes, c'est-à-dire le cas où les contraintes primales sont des contraintes d'égalité. Ceci est destiné à supprimer le problème du blocage sur les contraintes $\lambda_i \ge 0$.

On peut alors considérer l'algorithme suivant :

Soit $\varepsilon > 0$ donné.

1. Choisir $\lambda_o$ quelconque. Poser $n=0$

2. Calculer $X_\varepsilon(\lambda_n)$ en résolvant le problème $P(\lambda)$ (cf. Hypothèse H4).

3. Résoudre le problème

$$P'(\lambda_n) = \begin{cases} \min |s|^2 \\ (s,g(x)) \ge 1 & \forall x \in X_\varepsilon(\lambda_n). \end{cases}$$

3. Si $P'(\lambda_n)$ n'a pas de solution, stop. sinon : soit $s_n$ sa solution unique.

4. Calculer $\rho_n$ par la formule $h(\lambda_n + \rho_n s_n) = \sup_{\rho>0} h(\lambda_n + \rho s_n)$

5. Faire $\lambda_{n+1} = \lambda_n + \rho_n s_n$, $n=n+1$, aller en 2. ■
**Remarque 4.1**

Comme $X(\lambda_n) \subseteq X_\epsilon(\lambda_n)$, la direction $s_n$ est certainement une direction de montée. La suite $h(\lambda_n)$ est donc strictement croissante.

D'autre part, si l'on suppose que la fonction duale atteint son maximum, l'étape 4 fournit un $\rho_n > 0$.

Enfin, nous verrons plus loin (théorème 4.2) une justification du test d'arrêt en 3 : si le problème $P'_\epsilon(\lambda_n)$ n'a pas de solution, on déduit que $\lambda_n$ est proche du maximum.

**Remarque 4.2**

Dans le cas des contraintes $\lambda \ge 0$, il faut se méfier des zigzags pouvant être engendrés par une méthode de directions compatibles.

Il y a lieu d'adopter alors l'une des deux politiques suivantes :

1) Soit remplacer $P'_\epsilon(\lambda_n)$ par le problème

$$ \begin{cases} \min & |s|^2 \\ (s,g(x)) & \ge 1 \quad \forall x \in X_\epsilon(\lambda_n) \\ s_i & \ge 0 \quad \text{si} \quad \lambda_i \le \eta \quad \text{pour un } \eta > 0 \text{ donné.} \end{cases} $$

et, dans l'étape 5, de faire

$$ \lambda_{n+1} = \max (0, \lambda_n + \rho_n s_n) $$

2) Soit de résoudre

$$ \begin{cases} \min & |s|^2 \\ (s,g(x)) & \ge 1 \quad \forall x \in X_\epsilon(\lambda_n) \\ s_i & \ge 0 \quad \text{si} \quad \lambda_i = 0 \end{cases} $$

et

$$ \lambda_{n+1} = \lambda_n + \rho_n s_n $$
$$
\lambda_{n+1} = \begin{cases} \lambda_{n+1/2} & \text{si } \lambda_{n+1/2} \ge \eta \\ 0 & \text{sinon} \end{cases}
$$

4.3. THEOREMES DE CONVERGENCE.

Lemme 4.2

Soient ε > 0 et un compact K ⊂ Rm

∀ ε' < ε, ∃ η tel que λ ∈ K, μ ∈ K et |λ - μ| ≤ η ⇒ x_ε; (μ) ∈ X_ε (λ) .

Démonstration

Posons

$$
(13) \quad M = \sup \left\{ \left| g(x) \right| \middle| x \in X_{\varepsilon}(\lambda), \lambda \in K \right\} \quad M < +\infty \quad \text{d'après le lemme 1.1}
$$

On a toujours

$$
L(x, \mu) = L(x, \lambda) + (\mu - \lambda, g(x))
$$

Si $x \in X_\varepsilon$, ($\mu$), on a

$$
L(x, \mu) \leq h(\mu) + \epsilon'
$$

Donc, $\forall x \in X_\varepsilon$, ($\mu$), on a

$$
L(x, \lambda) \leq h(\mu) + |\mu - \lambda| |g(x)| + \epsilon'
$$

Comme $\epsilon' < \epsilon$, on peut choisir

$$
\eta_1 > 0 \text{ tel que } h(\mu) \le h(\lambda) + \frac{\epsilon - \epsilon'}{2} \text{ dès que } |\mu - \lambda| \le \eta_1 .
$$

$$
\eta_2 = \frac{\epsilon - \epsilon'}{2M} > 0
$$
Dés que $\mu \equiv K$ et $|\mu - \lambda| \le \eta = \min(\eta_1, \eta_2)$, on a

$$L(x, \lambda) \le h(\lambda) + \frac{\varepsilon - \varepsilon'}{2} + \frac{\varepsilon - \varepsilon'}{2M} \quad M + \varepsilon'$$

ce qui exprime bien que $x \equiv X_{\varepsilon}(\lambda)$. ■

Remarquons que si $\lambda \equiv K$, le rôle de $\lambda$ et $\mu$ est symétrique, ce qui permet d'affirmer également que $X_{\varepsilon}(\lambda) \supseteq X_{\varepsilon}(\mu)$.

Moyennant une modification convenable de l'hypothèse de qualification H3), destinée à conserver la décroissance à l'infini de la fonction duale, (malgré l'absence de contraintes $\lambda_i \ge 0$), on peut énoncer le

**Théorème 4.1**

La suite $\lambda_n$ définie par l'algorithme 4.2 est bornée.

Pour tout $\varepsilon'> \varepsilon$ et pour toute valeur d'adhérence $\lambda$ de cette suite, le problème $P'_{\varepsilon}$, $(\lambda)$ n'a pas de solution.

**Démonstration**

Supposons qu'il existe un $\varepsilon_1 > \varepsilon$ tel que $P_{\varepsilon_1}(\lambda)$ ait une solution :

$$(15) \qquad \exists s_o \text{ tel que } (s_o g(x)) \ge 1 \quad \forall x \equiv X_{\varepsilon_1}(\lambda).$$

**Point 1**

La suite $s_p$ est bornée

En effet, d'après le lemme 4.2, pour $p$ suffisamment grand,

$$X_{\varepsilon}(\lambda_p) \equiv X_{\varepsilon_1}(\lambda).$$

Donc, $s_o$ défini par (15) est a fortiori compatible dans le problème $P'_{\varepsilon}(\lambda)$.

Par construction, on a nécessairement $|s_p| \le |s_o|$ pour tout $p$ suffisamment grand.
Nous démontrons maintenant le

### Point 2

Pour $\rho > 0$ tel que $h(\lambda + \rho s_p) \ge h(\lambda) + \rho$ pour tout $p$ suffisamment grand.

Appliquons encore le lemme 4.2 avec $\varepsilon'=0$: $\exists \eta$ tel que si

$$ (16) \qquad |\lambda + \rho s_p - \lambda_p| \le \eta, \text{ alors} $$

$$ (17) \qquad X(\lambda + \rho s_p) \subseteq X_{\varepsilon}(\lambda_p). $$

Dès que $|\lambda - \lambda_p| \le \eta_1 < \eta$, on a

$$ | \lambda + \rho s_p - \lambda_p | \le \eta_1 + \rho | s_p | . $$

Mais $|s_p| \le |s_o|$. Donc, (16) a lieu dès que

$$ \rho \le \frac{\eta - \eta_1}{|s_o|} $$

qui est une majoration indépendante de $p$.

Alors, on a $\forall x \in X(\lambda + \rho s_p)$,

$$ h(\lambda + \rho s_p) = L(x,\lambda) + \rho(s_p,g(x)) \ge h(\lambda) + \rho(s_p,g(x)) $$

Mais d'après (17), $(s_p,g(x)) \ge 1$, ce qui démontre le point 2.

### Point 3

Pour $k$ tel que $h(\lambda_{k+1}) > h(\lambda)$.

En effet, soit $\lambda_k$ une sous-suite telle que $s_k \to s$, et soit $\rho$ défini comme au point 2.

Alors, $\lambda_k + \rho s_k$ a une limite, qui est la même que celle de $\lambda + \rho s_k$ ($\rho$ étant celui du point 2).
D'après la continuité de h, ceci entraîne que

$$ (h(\lambda_k + \rho s_k) = h(\lambda + \rho s_k) + \epsilon_k \ge h(\lambda) + \rho + \epsilon_k \\ \text{avec } \epsilon_k \to 0. $$

Dès que $|\epsilon_k| \le \frac{\sigma}{2}$, on a donc

$$ h(\lambda_{k+1}) = h(\lambda_k + \rho_k s_k) \ge h(\lambda_k + \rho s_k) \ge h(\lambda) + \frac{\sigma}{2} > h(\lambda). \quad \text{c.q.f.d.} $$

Or, ce point 3 constitue une contradiction : puisque $h(\lambda_n)$ est strictement croissante, on a nécessairement $h(\lambda_n) < h(\lambda_p) < h(\lambda)$ pour tout n, y compris pour $n=k+1$. ■

**Lemme 4.3**

Soient $\lambda$ et $\epsilon \ge 0$ donnés. On a

$$ (18) \quad \sup_{\rho > 0} \frac{h(\lambda + \rho s) - h(\lambda) - \epsilon}{\rho} \le \min_{x \in X_{\epsilon}(\lambda)} (s,g(x)). $$

**Démonstration.**

$$ \forall x \in X_{\epsilon}(\lambda), \quad \forall \rho > 0, \text{ on a} $$

$$ h(\lambda + \rho s) \le L(x, \lambda + \rho s) = L(x, \lambda) + \rho(s, g(x)) \le h(\lambda) + \epsilon + \rho(s, g(x)) $$

on en déduit

$$ \frac{h(\lambda + \rho s) - h(\lambda) - \epsilon}{\rho} \le (s,g(x)). $$

$X_{\epsilon}(\lambda)$ étant un ensemble fermé, on en déduit la proposition (18). ■

**Théorème 4.2**

Toute valeur d'adhérence $\lambda$ de l'algorithme 4.2 vérifie

$$ h(\lambda) \ge \max h - \epsilon $$
## Démonstration

D'après le théorème 4.1, $\forall \varepsilon_1 > \varepsilon$ et $\forall s$, on a

$$ \min_{x \in X_{\varepsilon_1}} (s,g(x)) \le 0 $$

Car le problème $P'_\varepsilon(\lambda)$ n'a pas de solution.

Donc, d'après le lemme 4.3

$$ \sup_{\rho>0} \frac{h(\lambda + \rho s) - h(\lambda) - \varepsilon_1}{\rho} \le 0 $$

ce qui peut s'écrire

$$ \max h \le h(\lambda) + \varepsilon_1 $$

et ceci pour tout $\varepsilon_1 > \varepsilon$, donc y compris pour $\varepsilon$. ■

## Remarque 4.3

Il existe à propos de cet algorithme une conjecture : se termine-t-il en un nombre fini d'itérations ? Il faudrait pour cela pouvoir augmenter $h$ indépendamment de $n$ à chaque itération ; ce fait est lié à la convergence d'une sous-suite de $s_n$, sans faire l'hypothèse que $P'_\varepsilon(\lambda)$ n'a pas de solution.

Signalons à ce sujet un résultat négatif : le lemme 4.3 ne peut être amélioré par un résultat du type

$$ (19) \qquad \sup_{\rho>0} \frac{g(\lambda + \rho s) - h(\lambda) - \varepsilon}{\rho} = \min_{x \in X_\varepsilon(\lambda)} (s,g(x)). $$

En effet, si $h$ est différentiable (problème (P2) convexe) alors, $X_\varepsilon(\lambda)$ engendre l'é-sous-différentiel de $h$, défini par (cf. (19) p.219).
$$
\partial_{\varepsilon} h(\lambda) = \{ \lambda^* / h(\mu) \le h(\lambda) + (\mu - \lambda, \lambda^* ) + \varepsilon, \forall \mu \}
$$

et dans ce cas, (19) a lieu. Cependant, ce résultat est en général faux
dans le cas non convexe.

Par contre, le lemme 4.3 s'interprète ainsi : s'il existe au point $\lambda$
une direction permettant d'obtenir une incrémentation d'au moins $\varepsilon$, cette
direction vérifie certainement les contraintes du problème $P'_{\varepsilon}(\lambda)$. Par con-
séquent, dans quelle mesure doit-on résoudre avec précision ce problème ?
Ne faudrait-il pas plutôt en résoudre un autre, voisin ? Toutes questions
qui restent ouvertes. ■

Nous verrons au §5 qu'on a besoin de connaître un $\lambda$ et un $\varepsilon$ tels que $P'_{\varepsilon}(\lambda)$ n'ait pas de solution. Pour cela, on a le résultat suivant :

Théorème 4.3

Soit $\lambda_p$ une sous-suite convergente dans l'algorithme 4.2.

$\forall \varepsilon_1 > \varepsilon, \exists p \text{ tel que } P'_{\varepsilon_1}(\lambda_p) \text{ n'ait pas de solution.}$

Démonstration

Soit $\varepsilon_1$ donné. Choisissons $\varepsilon_2$ tel que $\varepsilon < \varepsilon_2 < \varepsilon_1$. On sait que $P'_{\varepsilon_2}(\lambda)$ n'a pas de solution. Or, d'après le lemme 4.2, dès que $p$ est suffisamment grand,

$$
X_{\epsilon_2}(\lambda) \subseteq X_{\epsilon_1}(\lambda_p).
$$

Donc, $P'_{\varepsilon_1}(\lambda_p)$ n'a a fortiori pas de solution. ■

Remarque 4.4

Pour obtenir un théorème semblable dans le cas des contraintes $\lambda \ge 0$, il faudrait adapter tout le chapitre 13 de (21), ce qui nous entraînerait trop loin ici. Nous admettrons donc que l'algorithme 4.2 modifié pour tenir
compte de ces contraintes fournit en un nombre fini d'itérations un $\lambda_p$ et
un $\varepsilon'> \varepsilon$ tels que le problème $P_\varepsilon, (\lambda_p)$ n'ait pas de solution.

V - UTILISATION DU POINT MAX-MIN OBTENU.

Supposons pour simplifier que la fonction duale atteint son maximum une
seule fois au point $\bar{\lambda}$.

Alors, ($\bar{\lambda}$, $X(\bar{\lambda})$) forme l'ensemble des points max-min du lagrangien mais
peut ne contenir aucun point-selle. Si le problème (P1) n'est pas convexe,
il peut n'exister dans $X(\bar{\lambda})$ aucun point $\bar{x}$ réalisable et a fortiori optimal.

Nous allons maintenant montrer qu'on peut, à partir de $\bar{\lambda}$, obtenir des
solutions réalisables et sous-optimales.

Posons

$$
(20) \quad \left\{
\begin{array}{ll}
I = \{i | \bar{\lambda}_i = 0\}. & \\
G(\bar{\lambda}) = \{g \in \mathbb{R}^m / g=g(x), x \in X(\bar{\lambda})\} . & \\
G_{\varepsilon}(\bar{\lambda}) = \{ g \in \mathbb{R}^m / g=g(x), x \in X_{\varepsilon}(\bar{\lambda}) \} . & \\
\hat{G}(\bar{\lambda}) \quad \text{l'enveloppe convexe de } G(\bar{\lambda}) &
\end{array}
\right.
$$

L'essentiel de ce paragraphe tient dans le résultat suivant :

Théorème 5.1

Si $\bar{\lambda}$ maximise la fonction duale

Si $X(\bar{\lambda})$ est un ensemble fini

Alors, il existe dans $\hat{G}(\bar{\lambda})$ un $\bar{g}$ tel que

$$
(21) \quad \left\{
\begin{array}{l}
\bar{g} \le 0 \\
\bar{\lambda} \quad \bar{g} = 0
\end{array}
\right.
$$
## Démonstration

Si $\bar{\lambda}$ maximise la fonction duale, toutes les dérivées directionnelles sont négatives. Le problème (P6) du §3.2 admet la solution $(\alpha_6=0, s=0)$ (lemme 3.1). Dans ce cas, la contrainte $|s| \le 1$ est inutile : il est évident que le problème

$$ (22) \qquad \left\{ \begin{array}{ll} \max & \alpha \\ (s,g(x)) & \ge \alpha \quad \forall x \in X(\bar{\lambda}) \\ s_i & \ge 0 \quad i \in I \end{array} \right. $$

admet également l'optimum $\alpha=0$.

Soient $x_1, x_2, \dots, x_k$ les points de $X(\bar{\lambda})$. Le problème (22) est à son tour équivalent au problème

$$ (23) \qquad \left\{ \begin{array}{ll} \max & \alpha \\ (s,g(x_k)) & \ge \alpha \quad k=1, \dots, K. \\ s_i & \ge 0 \quad i \in I \end{array} \right. $$

Comme ce problème est linéaire, il existe à l'optimum des multiplicateurs de LAGRANGE $\bar{u}_1, \bar{u}_2, \dots, \bar{u}_K$.

Le Lagrangien associé à (23) s'écrit :

$$ M(\alpha, s, u) = - \alpha + \sum_{k=1}^{K} u_k (\alpha - (s, g(x_k))) $$

Posons :

$$ \bar{g} = \sum_{j=1}^{K} \bar{u}_k g(x_k) = (\bar{g}_1, \bar{g}_2, \dots, \bar{g}_M) . $$

On voit alors facilement que les conditions de KUHN et TUCKER donnent :
$$
\left\{
\begin{array}{ll}
\bar{u}_k \ge 0 & k=1, \dots, k \\
\\
\frac{\partial M}{\partial \alpha} = -1 + \sum_{k=1}^{K} \bar{u}_k = 0 & \\
\\
\frac{\partial M}{\partial s_i} = - \bar{g}_i & \left\{
\begin{array}{ll}
= 0 & \text{si } i \neq I \\
\ge 0 & \text{si } i \in I.
\end{array}
\right.
\end{array}
\right.
$$

Le point $\bar{g}$ vérifie évidemment la proposition. ■

**Remarque 5.1**

Pour faire le joint avec §4, il suffit de remarquer qu'on a la même
proposition avec $X_{\epsilon}(\bar{\lambda})$ si le problème $P_{\epsilon}(\bar{\lambda})$ défini au §4.1 n'a pas de
solution (Cf. Théorème 4.3). ■

Pour pouvoir utiliser commodément le théorème 5.1, nous supposons à
partir de maintenant que dans le problème (P1), les contraintes sont con-
vexes. On a alors les résultats suivants :

Corollaire 5.1

Si, dans le problème initial (P1), D est convexe et si les contraintes
$g_i$ sont convexes ; si de plus $X(\bar{\lambda})$ est fini, alors, il existe dans $\hat{X}(\bar{\lambda})$
un point $\bar{x}$ réalisable.

Démonstration.

Le théorème 5.1 s'applique.

Alors, le point $\bar{x} = \sum_{j=1}^{K} \bar{u}_j x_j$ vérifie la proposition, car $\bar{x} \in D$ d'une part, et

$$
0 \ge \sum_{j=1}^{K} \bar{u}_j g(x_j) \ge g\left(\sum_{j=1}^{K} \bar{u}_j x_j\right)
$$

d'après la convexité de l'application g. Si les contraintes sont linéaires
on a le résultat plus fort suivant :
**Corollaire 5.2**

Si, dans le problème initial (P1), D est convexe et les $g_i$ sont affines, alors, $\bar{\lambda}$ maximisant la fonction duale, il existe dans $\hat{X}(\bar{\lambda})$ un point $\bar{x}$ vérifiant les conditions de transversalité :

$$ \begin{cases} g(\bar{x}) \le 0 \\ \bar{\lambda} g(\bar{x}) = 0 \end{cases} \blacksquare $$

Posons maintenant

$$ (24) \qquad m = L(\bar{x}, \bar{\lambda}) - h(\bar{\lambda}) $$

Dans le cas des contraintes linéaires, 1'ε-théorème d'EVERETT (Théorème 2.3) nous permet directement d'affirmer le résultat suivant :

**Théorème 5.2**

Si

* D est convexe et les $g_i$ affines

* $\bar{\lambda}$ maximise la fonction duale.

Alors il existe dans $\hat{X}(\bar{\lambda})$ un point $\bar{x}$ résolvant à m près le problème (P1), m étant défini par (24). ■

**Remarque 5.2**

Dans le cas de contraintes linéaires, la recherche d'un point $\bar{x}$ du corollaire 5.2 équivaut à une phase 1 de simplexe appliquée à l'inconnue $u_1, u_2, \dots, u_k$.

D'autre part, si le m défini en (24) n'est pas jugé suffisamment petit, on peut appliquer un algorithme de minimisation standard utilisant $\bar{x}$ comme point initial.
### Remarque 5.3

Dans le cas de problèmes discrets, la contrainte $x \in \hat{X}(\bar{\lambda})$ peut être abusive ($\hat{X}(\bar{\lambda}) \neq \lambda$) D peut être réduit à $X(\bar{\lambda})$. Il faudrait trouver un point voisin de $\bar{x}$ par tâtonnements, utiliser ce point pour initialiser un algorithme standard...la situation n'est plus aussi nette. En fait, on reste dans les difficultés exprimées dans (7), (12), (16), (18), (20). Dans ce cas, seuls les §3 et 4 du présent article s'appliquent.

## VI - APPLICATION NUMERIQUE.

On peut illustrer l'algorithme 4.2 en l'appliquant au problème de LORIE et SAVAGE (12). Ce problème s'écrit :

$$ \begin{cases} \min & \sum_{i=1}^{n} a_i x_i \\ \text{c.} \ x. & \sum_{j=1}^{n} c_{ij} x_{ij} \le t_j, \quad i=1, \dots, m \\ x_i = 0 & \text{ou } 1 \end{cases} $$

Dans ce cas, l'ensemble $X_{\varepsilon}(\lambda)$ est particulièrement simple à déterminer. Nous nous contenterons cependant de donner l'application des §3, 4, 5 au problème du §1.1.

Rappelons qu'il s'agit de résoudre :

$$ (24) \quad \min \quad J(x,y) = \sum_{i=1}^{n} \sum_{j=1}^{m} \left( \alpha_{ij} x_{ij} + \beta_{ij} y_{ij} + \gamma_{ij} \frac{x_{ij}}{y_{ij}} \right) $$

$$ (25) \quad \sum_{i=1}^{n} (a_{ij}x_{ij} + b_{ij}y_{ij}) \le T_j $$

$$ (26) \quad \sum_{j=1}^{m} x_{ij} = D_i $$
$$ (27) \qquad x_{ij} \ge 0, \quad y_{ij} \ge 0 $$

## 6.1. UTILISATION DE LA DUALITE.

On dualise les contraintes (25). On obtient ainsi le lagrangien

$$ L(x,y,\lambda) = \sum_{i,j} L_{ij}(x_{ij},y_{ij},\lambda_j) - \sum_j \lambda_j T_j $$

où

$$ (28) \qquad L_{ij}(x_{ij}, y_{ij}, \lambda_j) = (\alpha_{ij} + \lambda_j a_{ij})x_{ij} + (\beta_{ij} + \lambda_j b_{ij})y_{ij} + \gamma_{ij} \frac{x_{ij}}{y_{ij}} $$

### Phase 1

Maximisation de la fonction duale.

Remarquons que $y_{ij} \to L_{ij}$ est strictement convexe. Au minimum, on a donc nécessairement ($y_{ij}$ n'est pas contraint)

$$ (29) \qquad y_{ij} = y_{ij}(x,\lambda) = \sqrt{\frac{\gamma_{ij} x_{ij}}{\beta_{ij} + \lambda_j b_{ij}}} $$

L'application $x_{ij} \to L_{ij}(x_{ij},y_{ij}(x,\lambda), \lambda_j)$ est alors strictement convexe. Son minimum est donc atteint en l'un des points extrémaux du domaine défini par (26), (27). On calcule donc

$$ (30) \qquad F_{ij}(\lambda) = L_{ij}(D_i, y_{ij}(D_i, \lambda_j), \lambda_j) $$

1) Pour calculer $h(\lambda)$, on détermine pour chaque i un $j(i)$ tel que

$$ F_{ij}(\lambda) \ge F_{ij}(i)(\lambda) \quad j=1,\dots,m $$

$$ \text{et} \quad h(\lambda) = \sum_{i=1}^{n} F_{ij}(i)(\lambda) - \sum_{j=1}^{m} \lambda_j T_j . $$
2) On ne peut pas calculer $X_{\epsilon}(\lambda)$ commodément, mais on peut l'approcher en envisageant systématiquement pour chaque $i$ l'ensemble des $j$ tels que

$$F_{ij}(\lambda) \le F_{ij(i)}(\lambda) + \epsilon$$

### Remarque 6.1

Il n'y a aucune relation d'inclusion entre $X_{\epsilon}(\lambda)$ et l'ensemble ainsi défini, mais cette méthode est suffisante. ■

D'après le théorème 4.3, l'algorithme 4.2 donne comme réponse un $\bar{\lambda}$ et un $\epsilon$ tels que l'ensemble noté $X_{\epsilon}(\bar{\lambda})$ satisfait aux hypothèses du théorème 5.1. Notons

$$ (31) \qquad \{ (x,y)_1, (x,y)_2, \dots, (x,y)_k \} \text{ cet ensemble.} $$

D'autre part, $h(\bar{\lambda})$ est un minorant du coût optimal pour le problème (24)-(27).

### Phase 2

Obtention d'une solution primale réalisable.

On peut alors trouver par programmation linéaire un point $(\bar{x}, \bar{y})$ tel que

$$ (32) \qquad (\bar{x}, \bar{y}) = \sum_{\ell=1}^{k} u(x, y_{\ell}) \qquad u_{\ell} \ge 0 \quad \sum_{\ell=1}^{k} u_{\ell} = 1. $$

$$ (33) \qquad \bar{\lambda} \quad ( \sum_{j=1}^{k} (a_{ij}\bar{x}_{\ell} + b_{ij}\bar{y}_{\ell}) - T_j ) = 0. $$

$$ (34) \qquad \sum_{i=1}^{h} (a_{ij}\bar{x}_{\ell} + b_{ij}\bar{y}_{\ell}) \le T_j $$

Posons

$$ m_i = J(\bar{x}, \bar{y}) - h(\bar{\lambda}) . $$

La phase 2 est maintenant terminée. Si $m_i$ est jugé trop grand, on peut
passer à la phase 3 :

### Phase 3

Obtention d'une solution primale sous-optimale

Soit un point $x$ vérifiant

$$ (35) \qquad x_{ij} \ge 0 $$

$$ (36) \qquad \sum_{j=1}^{m} x_{ij} = D_i \quad j=1, \dots, m $$

$$ (37) \qquad \sum_{i=1}^{n} a_{ij} x_{ij} < T_j \quad i=1, \dots, n $$

On peut définir facilement

$$ (38) \quad \left\{ \begin{array}{l} H(x) = \min_j J(x,y) \\ \qquad y \\ y_{ij} \ge 0 \\ \sum_{i=1}^{n} b_{ij} y_{ij} \le T_j - \sum_{i=1}^{n} a_{ij} x_{ij} \end{array} \right. $$

Le problème (24)-(27) est alors équivalent au problème

$$ \left\{ \begin{array}{l} \min H(x) \\ x \text{ vérifiant } (35), (36), (37) \end{array} \right. $$

On montre

1) que la contrainte (37) est inutile : si $x$ tend vers un point de la frontière (c'est-à-dire réalisant l'égalité dans (37)), alors, $H(x) \to +\infty$
2) Que la fonction H(x) est dérivable sur le relatif intérieur du domaine défini par (35), (36), (37) (ce qui n'est pas évident a priori)

Or, le point $\bar{x}$ donné par la phase 2 vérifie (35), (36), (37). On peut
donc utiliser un algorithme classique (gradient réduit par exemple) pour
l'améliorer.

Remarque 6.2

Pour calculer la fonction H(x), on dualise les contraintes de couplage.
Il y a m multiplicateurs $\mu_j$. On montre alors que chaque $\mu_j$ est soit
nul soit solution d'une équation.

$$
\begin{cases}
F_j(\mu_j) = 0 \\
\mu_j \ge 0
\end{cases}
$$

dans laquelle F_j est monotone, ce qui permet d'employer la méthode de
Newton.

La phase 3 donne un point $(\bar{x}, \bar{y})$ et une qualité $m_2 = J(\bar{x}, \bar{y}) - h(\bar{\lambda})$.

6.2. RESULTATS NUMERIQUES.

La méthode du §6.1 a été testée en FORTRAN sur ordinateur CII 90.80.
Le programme comporte 1 600 cartes. Temps de compilation et de chargement:
7 minutes.

On a résolu deux cas pratiques, donnés par la compagnie Saint-Gobain.

- L'exemple 1 : comporte 3 machines et 21 produits (n=21, m=3)

- L'exemple 2 : n=46, m=7.
le tableau de résultats est le suivant.

<table><thead><tr><th></th><th>Exemple 1</th><th>Exemple 2</th></tr></thead><tbody><tr><th>Phase 1</th><td>30 s</td><td>5mn</td></tr><tr><th>Phase 2</th><td>Temps négligeable</td><td>30 s<br>optimum à 1%</td></tr><tr><th>Phase 3</th><td>Temps négligeable</td><td>20mn</td></tr><tr><th>Temps total</th><td>30 s</td><td>26mn</td></tr><tr><th>qualité de (x,y).</th><td>3°/oo</td><td>1°/oo</td></tr></tbody></table>

### Remarque 6.3

Dans l'exemple 2, deux machines sont identiques. Si un produit passe sur l'une des deux, il peut passer dans les mêmes conditions sur l'autre. A chaque itération duale, il y a ainsi au moins un grand nombre d'optimums (64 en l'occurence) ce qui explique la forte augmentation des temps par rapport à l'exemple 1, où le nombre d'optimums n'excède jamais 4.

## VII - CONCLUSION.

Nous avons donné un algorithme du type UZAWA permettant de résoudre par dualité des programmes mathématiques assez généraux. Les points faibles de cet algorithme sont
1) Il faut savoir très bien résoudre le problème du lagrangien avec une précision donnée (calcul de $X_e(\lambda)$). Ceci exigea en général des fonctions découpées.

2) On est en présence d'une méthode double-itérative (le calcul du gradient est lui-même un programme mathématique) et la méthode est donc sensible à la façon dont la méthode itérative la plus interne s'effectue.

3) Les contraintes doivent être convexes, sinon, on en est réduit à des heuristiques en phase finale.

4) La qualité de la solution obtenue ne peut pas être déterminée à l'avance.

Cependant, les résultats obtenus sur des exemples concrets (§6.2) sont très encourageants.
BIBLIOGRAPHIE

(1) R.E. ALCALY, A.K. KLEVORICK : A note on the dual price of integer programs. Econometrica - 34 n°1 (Janvier 1969).

(2) R. BROOKS, A. GEOFFRION : Finding Everett's Lagrange Multipliers by linear programming. Operations Research 14(1966) pp. 1149-53.

(3) J.M. DANSKIN : The theory of max-min with applications. SIAM J. on Applied Math. 14 - n°4 (1966) pp. 641-655.

(4) J.P. EVANS, F.J. GOULD : Application of the GLM technique to a production planning problem. Naval Research Logistic Quarterly 18(1971) 59-74.

(5) J.P. EVANS, F.J. GOULD : Stability in nonlinear programming. Operations Research 18 (1970)pp.107-118.

(6) J.P. EVANS, F.J. GOULD : A generalized Lagrange multipliers algorithm for optimum or near optimum production scheduling. Management Science 18 n°3 (Janvier 1972-I)

(7) H. EVERETT III : Generalized Lagrange multiplier method for solving problems of optimum allocation resources. Operations Research 11 (1963) pp. 399-417.

(8) F.J. GOULD : Extensions of Lagrange multipliers in non linear programming. SIAM J. on Applied Math. 17 n°6(Novembre 69)

(9) H.J. GREENBERG : Lagrangian duality gaps : their source and resolution. Techn. Report n° C.P. 69005 Southern Methodist University-Dallas. Texas 75 222.
(10) H.J. GREENBERG, T.C. ROBBINS : The theory and computation of Everett's Lagrange Multipliers by generalized linear programming.
Techn. Report N°70008. Ibidem.

(11) R.C. GRINOLD : Lagrangien Subgradients.
Management Science 17 n°3 (Novembre 1970)

(12) S. KAPLAN : Solution of the Lorie-Savage and similar integer programming problems by the generalized lagrange multipliers method.
Operations Research 14 (1966) pp.1130-1136

(13) L.S. LASDON : Optimization theory for large systems.
Mac Millan - London 1970.

(14) D.G. LUENBERGER : Control problems with kinks.
IEEE transactions on automatic control
A.C. 15 n°15.

(15) S.K. MITTER, D.P. BERTSEKAS : Descent numerical methods for optimization problems with non differentiable cost functionnals.
A paraître dans SIAM J. on Control.

(16) G. NEMHAUSER, Z. ULLMAN : A note on the generalized Lagrange Multiplier solution to an integer programming problem.
Operations Research 16 (1968) 450-453.

(17) P. NEPOMIASTCHY : Méthode de pénalisation pour les systèmes gouvernés par des équations différentielles avec contraintes sur l'état.
Publication LABORIA n°7224/72027(Oct.72)

(18) D. POTIER : Algorithmes de coordination. Application à la gestion d'unités de production interdépendantes.
Thèse d'Ingénieur. Paris.

(19) R.T. ROCKAFELLAR : Convex analysis. Princeton 1970.

(20) J.F. SHAPIRO : Generalized Lagrange multipliers in integer Programming.
Operations Research 19(1971) 68-76.

(21) W.I. ZANGWILL : Non linear Programming Prentice-Hall 69.