ANNALES MATHÉMATIQUES

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

BLAISE PASCAL

K. BELKEZIZ, A. METRANE

Optimisation d'une fonction linéaire sur l'ensemble des
solutions efficaces d'un problème multicritère
quadratique convexe.

Volume 11, n°1 (2004), p. 19-33.

<http://ambp.cedram.org/item?id=AMBP_2004__11_1_19_0>

© Annales mathématiques Blaise Pascal, 2004, tous droits réservés.

L'accès aux articles de la revue « Annales mathématiques Blaise Pascal » (http://ambp.cedram.org/), implique l'accord avec les conditions générales d'utilisation (http://ambp.cedram.org/legal/). Toute utilisation commerciale ou impression systématique est constitutive d'une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copy-right.

Publication éditée par le laboratoire de mathématiques
de l'université Blaise-Pascal, UMR 6620 du CNRS
Clermont-Ferrand — France

cedram

Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
# Optimisation d'une fonction linéaire sur l'ensemble des solutions efficaces d'un problème multicritère quadratique convexe.

K. Belkeziz

A. Metrane

## Résumé

Dans ce papier, nous caractérisons l'ensemble des points efficients d'un problème de programmation multicritère quadratique convexe. Nous ramenons ainsi le problème de la minimisation d'une fonction linéaire sur l'ensemble des points efficients à la résolution d'un problème de programmation fractionnaire.

## 1 Introduction.

Les problèmes de programmation mathématique à objectifs multiples consistent à optimiser simultanément plusieurs critères non comparables sur un ensemble de solutions réalisables non vide. Le concept de points efficients joue un rôle important dans l'analyse et la résolution de ces problèmes.

Au cours de la dernière décennie, plusieurs chercheurs, citons en particulier, Benson [2, 4], Ecker, Hegner et Kouada [9], Gal [6], Isermann [8] et Tamara et Miura [12], motivés par de nombreuses applications [3, 5, 11], se sont intéressés à l'optimisation d'une fonction linéaire sur l'ensemble efficient d'un problème multiobjectif linéaire :

$$ \max Cx, \text{ sujet à } x \in X, \qquad (MOLP) $$

où C est une $p \times n$ matrice, $X = \{x \in \mathbb{R}^n/Ax \le b, x \ge 0\}$, A est une $m \times n$ matrice et $b \in \mathbb{R}^m$.

Après la caractérisation des points efficients, ils se sont intéressés à la résolution du problème de minimisation d'une fonction linéaire sur l'ensemble des points efficients *Eff* du problème (*MOLP*) :

$$ \left\{ \begin{array}{l} \min c^\top x \\ x \in \text{Eff}. \end{array} \right. \qquad (NC) $$
Notons que l'ensemble des solutions réalisables *Eff* est en général non convexe. Le problème (*NC*) rentre alors dans le cadre de l'optimisation globale (ou programmation non convexe).

Dans ce papier, nous nous intéressons au problème (*NC*), où *Eff* est l'ensemble des points efficients du problème multicritère quadratique convexe suivant :

$$
\min [f(x) = [f_1(x), f_2(x), \dots, f_p(x)] : x \in E \subset \mathbb{R}^n] \quad (\text{MOQP})
$$

avec $E = \{x \in \mathbb{R}^n / Ax = b\}$ et $A$ est une matrice $m \times n$ avec $m \le n$,
rang($A$) = $m$, $b \in \mathbb{R}^m$ les fonctions $f_i$ sont de la forme

$$
f_i(x) = \frac{1}{2} x^\top G_i x + g_i^\top x,
$$

où $G_i$ est une matrice $n \times n$ symétrique définie positive et $g_i \in \mathbb{R}^n$ pour $i \in \{1, \dots, p\}$.

Dans un premier temps, nous caractérisons l'ensemble des points efficients en terme de solutions d'un programme pondéré et nous montrons que le problème obtenu est équivalent à la résolution d'un système linéaire $A_\lambda x = b_\lambda$ où $\lambda \in \Lambda = \{ \lambda \in \mathbb{R}^p / \lambda_i \ge 0 \text{ et } \sum_{i=1}^p \lambda_i = 1 \}$. Les composantes de la solution de ce système s'expriment de façon explicite sous la forme fractionnaire $\frac{P(\lambda)}{Q(\lambda)}$ où $P$ et $Q$ sont deux polynômes.

Le problème de la minimisation d'une fonction linéaire sur l'ensemble des points efficients *Eff* se ramène alors à la résolution d'un problème de pro- grammation fractionnaire dans $\Lambda$.

Dans la deuxième section, nous rappelons des définitions et des résultats que nous utilisons par la suite. La troisième section est consacrée à la caractérisation des points efficients. Dans la quatrième section, nous donnons des conditions nécessaires d'optimalité du problème de la minimisation d'une fonction linéaire sur l'ensemble des points efficients d'une part, et d'autre part, nous montrons que ce problème se transforme en un problème de pro- grammation fractionnaire.

2 Rappels et Préliminaires.

Soient *E* un sous-ensemble non vide de $\mathbb{R}^n$, $p \ge 2$ et $\{f_i, i = 1, \dots, p\}$ une famille de fonctions réelles sur *E*. Le problème multi-objectif s'écrit sous la
forme suivante :

$$
\min [f(x) = [f_1(x), f_2(x), \dots, f_p(x)] : x \in E]. \quad (MOP)
$$

Nous rappelons quelques définitions et résultats utiles par la suite.

**Définition 2.1:** Le point $\bar{x}$ est dit un point efficient (solution efficace ou point extrémal de l'ensemble $f(E)$) du problème $(MOP)$ s'il n'existe pas de $x \in E$ tel que $f(x) \le f(\bar{x})$ et $f(x) \ne f(\bar{x})$.

Par Eff nous désignons l'ensemble des points efficients du problème (MOP).

Nous rappelons une caractérisation des points efficients du problème (MOP)
établie par Geoffrion [7].

**Théorème 2.2:** [7] Soit E un sous ensemble convexe non vide de $\mathbb{R}^n$. Si les fonctions $f_j$ sont strictement convexes pour tout $j \in \{1, 2, ..., p\}$, alors les assertions suivantes sont équivalentes :

i) $\bar{x}$ est un point efficient du problème (MOP).

ii) Il existe $\lambda \in \Lambda$ tel que $\bar{x}$ soit une solution du problème $(P_\lambda)$ suivant :

$$
\min \left[ f_{\lambda}(x) = \sum_{i=1}^{p} \lambda_{i} f_{i}(x) : x \in E \right] \qquad (P_{\lambda})
$$

$$
où \quad \lambda_i \ge 0 \quad et \quad \sum_{i=1}^{p} \lambda_i = 1.
$$

Comme les fonctions $f_j$ sont strictement convexes, alors les notions de so-
lution efficace, solution faiblement efficace et solution proprement efficace
définies dans [10] coincident.

Considérons le problème multicritère quadratique convexe suivant :

$$
\min [f(x) = [f_1(x), f_2(x), \dots, f_p(x)] : x \in E \subset \mathbb{R}^n] \quad (MOQP)
$$

où

$$
\bullet f_i(x) = \frac{1}{2} x^\top G_i x + g_i^\top x \text{ pour } i \in \{1, 2, \dots, p\}.
$$

* $G_i$ est une matrice $n \times n$ symétrique définie positive.
• $g_i \in \mathbb{R}^n$.

• E un ensemble convexe.

Le problème $(P_\lambda)$ s'écrit

$$ \min f_{\lambda}(x) = \frac{1}{2} x^{\top} G_{\lambda} x + g_{\lambda}^{\top} x : x \in E \subset \mathbb{R}^{n}. $$

$$ \text{avec } G_{\lambda} = \sum_{i=1}^{p} \lambda_{i} G_{i} \text{ et } g_{\lambda} = \sum_{i=1}^{p} \lambda_{i} g_{i}. $$

**Remarques 2.3:** (i) Comme les matrices $G_i$ sont définies positives, alors $G_\lambda$ est une matrice définie positive et par suite $f_\lambda$ est strictement convexe.
(ii) Comme $E$ est un ensemble convexe et la fonction $f_\lambda$ est strictement convexe, alors pour chaque $\lambda \in \Lambda = \{ \lambda \in \mathbb{R}^p / \lambda_i \ge 0 \text{ et } \sum_{i=1}^p \lambda_i = 1 \}$, le problème $(P_\lambda)$ admet une solution unique.

# 3 Caractérisation de l'ensemble des points efficaces.

## 3.1 Etude de problème (MOQP) sans contrainte.

Suivant le théorème 2.2, nous avons le résultat suivant : $\bar{x}$ est un point efficient du problème (MOQP) si et seulement s'il existe $\lambda \in \Lambda$ tel que $\bar{x}$ soit une solution optimale du problème $(P_\lambda)$, d'après la remarque 2.3 (ii), pour chaque $\lambda \in \Lambda$, le problème $(P_\lambda)$ admet une solution optimale unique. Alors à chaque $\lambda \in \Lambda$ correspond un seul point efficient.

Dans cette section, nous étudions l'ensemble des points efficaces du problème (MOQP) sans contrainte suivant

$$ \min [f(x) = [f_1(x), f_2(x), \dots, f_p(x)] : x \in \mathbb{R}^n]. \quad (\text{MOQP1}) $$

Le problème $(P_\lambda)$ associé est

$$ \min \left[ f_{\lambda}(x) = \frac{1}{2} x^{\top} G_{\lambda} x + g_{\lambda}^{\top} x : x \in \mathbb{R}^{n} \right], $$
avec $G_{\lambda} = \sum_{i=1}^{p} \lambda_{i} G_{i}$ et $g_{\lambda} = \sum_{i=1}^{p} \lambda_{i} g_{i}$.

**Proposition 3.1:** Le point $\bar{x} \in \mathbb{R}^n$ est efficient du problème (MOQP1) si et seulement s'il existe $\lambda \in \Lambda$ tel que $\bar{x}$ soit une solution du système $G_{\lambda}\bar{x} = -g_{\lambda}$.

PREUVE: En utilisant le théorème 2.2 et les conditions nécessaires et suffisantes d'optimalité du problème ($P_{\lambda}$), nous obtenons le résultat suivant : le point $\bar{x} \in \mathbb{R}^n$ est efficient du programme (MOQP1) si et seulement s'il existe $\lambda \in \Lambda$ tel que $\bar{x}$ satisfait $\nabla (\frac{1}{2}x^{\top}G_{\lambda}x + g_{\lambda}^{\top}x) = 0$. D'où le résultat. $\square$

## 3.2 Etude de problème (MOQP) avec contraintes.

Dans cette section, nous nous intéressons au problème (MOQP) avec contrainte suivant

$$ \min [f(x) = [f_1(x), f_2(x), \dots, f_p(x)] : x \in E \subset \mathbb{R}^n] \quad (\text{MOQP}) $$

où l'ensemble réalisable $E = \{x \in \mathbb{R}^n / Ax = b\}$ et $A$ est une matrice $m \times n$, avec $m \le n$ et rang($A$) = $m$ et $b \in \mathbb{R}^m$. Nous ramenons le problème ($P_{\lambda}$) à un problème sans contrainte.

En effet :

Soit $\nu$ un point arbitraire du sous-espace affine $E$, il existe alors une matrice $B \in \mathbb{R}^{n \times (n-m)}$ et une matrice $C \in \mathbb{R}^{(n-m) \times n}$ toutes les deux de rang $n-m$ tel que pour tout $y \in \mathbb{R}^{(n-m)}$, il existe un seul $x \in E$ tel que

$$ x - \nu = By \quad (3.1) $$

et

$$ y = C(x - \nu). \quad (3.2) $$

**Remarque 3.2:** D'après la relation (3.1), nous avons $B^{\top}A^{\top} = 0$. Comme $\text{rang}(B) = n-m$ et $\text{rang}(A) = m$, alors $\text{Im}(A^{\top}) = \ker(B^{\top})$.
En remplaçant $x$ par $By + \nu$, la fonction $f_\lambda$ s'écrit comme suit :

$$
\begin{align*}
f_{\lambda}(x) &= \frac{1}{2} x^{\top} G_{\lambda} x + g_{\lambda}^{\top} x \\
&= \frac{1}{2} (\nu + By)^{\top} G_{\lambda} (\nu + By) + g_{\lambda}^{\top} (\nu + By) \\
&= \frac{1}{2} y^{\top} B^{\top} G_{\lambda} By + (B^{\top} G_{\lambda} \nu + B^{\top} g_{\lambda})^{\top} y + \frac{1}{2} \nu^{\top} G_{\lambda} \nu + g_{\lambda}^{\top} \nu \\
&= \hat{f}_{\lambda}(y).
\end{align*}
$$

Par suite, le problème $(P_\lambda)$ se transforme en un problème sans contrainte :

$$
\left\{
\begin{array}{l}
\min \hat{f}_{\lambda}(y) = \frac{1}{2} y^{\top} M_{\lambda} y + F_{\lambda}^{\top} y + s_{\lambda} \\
y \in \mathbb{R}^{n-m},
\end{array}
\right.
\qquad (P_{\lambda}^{r})
$$

où :

$$
M_{\lambda} = B^{\top} G_{\lambda} B \tag{3.3}
$$

$$
F_{\lambda} = B^{\top} G_{\lambda} \nu + B^{\top} g_{\lambda} \qquad (3.4)
$$

$$
s_{\lambda} = \frac{1}{2} \nu^{\top} G_{\lambda} \nu + g_{\lambda}^{\top} \nu. \tag{3.5}
$$

Comme les matrices $G_i$ sont définies positives et $B$ est de rang $n-m$, alors les matrices $B^\top G_i B$ sont aussi définies positives, par suite $M_\lambda = \sum_{i=1}^p \lambda_i B^\top G_i B$ est définie positive, Ce qui assure la stricte convexité du problème $(P_\lambda^r)$.

Dans la proposition suivante, nous montrons que les problèmes $(P_\lambda)$ et $(P_\lambda^r)$ sont équivalents.

**Proposition 3.3:** *Soit* $\lambda \in \Lambda$ *alors* $\bar{x}$ *solution du problème* $(P_\lambda)$ *si et seule-
ment si* $\bar{y}$ *solution du problème* $(P_\lambda^r)$ *avec* $\bar{x} - \nu = B\bar{y}$ *et* $\bar{y} = C(\bar{x} - \nu)$.

PREUVE: Soient $\lambda \in \Lambda$ et $\bar{x}$ solution du problème $(P_\lambda)$. La condition nécessaire et suffisante (Utilisant Lagrangienne) pour que $\bar{x}$ soit solution est qu'il existe $u^* \in \mathbb{R}^{n-m}$ tel que

$$
A^{\top} u^{*} + G_{\lambda} \bar{x} = -g_{\lambda}.
$$

Comme $B^\top A^\top = 0$, alors

$$
B^{\top} G_{\lambda} \bar{x} = -B^{\top} g_{\lambda}.
$$
D'après la relation (3.1), on a

$$M_{\lambda}\bar{y} = -F_{\lambda}.$$

Comme $(P_{\lambda}^r)$ est strictement convexe, alors la condition $M_{\lambda}\bar{y} = -F_{\lambda}^{\top}$ est suffisante pour que $\bar{y}$ soit optimal.

De la même manière nous montrons la réciproque en se basant aussi sur les conditions nécessaires et suffisantes d'optimalité des problèmes $(P_{\lambda})$ et $(P_{\lambda}^r)$, la relation (3.1) et le fait que $\mathrm{Im}(A^{\top}) = \ker(B^{\top})$. $\square$

**Remarque 3.4:** D'après la remarque 3.2 et la proposition 3.3, on constate que pour chaque $\lambda \in \Lambda$, le problème $(P_{\lambda}^r)$ admet une solution unique.

**Théorème 3.5:** Soit $x \in \mathbb{R}^n$ un point efficient du programme (MOQP). Alors il existe $\lambda \in \Lambda$ tel que $y = C(x - \nu)$ soit solution du système $(PL_{\lambda})$ suivant :

$$\left\{ \begin{array}{l} M_{\lambda}y = -F_{\lambda}^{\top} \\ y \in \mathbb{R}^{n-m}. \end{array} \right. \qquad (PL_{\lambda})$$

Inversement, s'il existe $\lambda \in \Lambda$ tel que $y$ soit solution du problème $M_{\lambda}y = -F_{\lambda}$, alors $x = By + \nu$ est un point efficient du programme (MOQP).

**PRÉUVE:** D'après le théorème 2.2, nous avons : $x$ point efficient du programme (MOQP) si et seulement s'il existe $\lambda \in \Lambda$ tel que $x$ soit solution du problème $(P_{\lambda})$, d'après la proposition 3.3, $y = C(x - \nu)$ solution du problème quadratique strictement convexe sans contrainte de $(P_{\lambda}^r)$, par suite $y$ est solution de $(PL_{\lambda})$. De la même manière nous montrons la réciproque. $\square$

**Remarque 3.6:** Les points efficients des problèmes (MOQP1) sans contrainte et (MOQP) avec contrainte $Ax = b$ se caractérisent par le même type d'équation

$$G_{\lambda}x = -g_{\lambda}^{\top}$$

et

$$M_{\lambda}y = -F_{\lambda}^{\top}.$$
# 4 Résolution du problème (NC).

Dans cette section, nous nous intéressons au problème (NC) suivant :

$$ \left\{ \begin{array}{l} \min c^{\top} x \\ x \in \mathit{Eff} \end{array} \right. \qquad (NC) $$

où $\mathit{Eff}$ est l'ensemble des points efficients de (MOQP) et $c \in \mathbb{R}^n$.

Dans un premier lieu, nous donnerons les conditions nécessaires d'optimalité de (NC), puis nous montrons que ce problème est équivalent à un problème de programmation fractionnaire sur $\Lambda$.

D'après la relation (3.1), nous avons :

$$ c^{\top} x = c^{\top} By + B\nu. $$

Alors, suivant le théorème 3.5, le problème (NC) est équivalent au problème suivant :

$$ \min_{\lambda, y} \left[ \hat{c}^{\top} y : \begin{array}{l} \lambda \ge 0, \sum_{i=1}^{p} \lambda_i = 1 \\ \sum_{i=1}^{p} \lambda_i D_i y + \sum_{i=1}^{p} \lambda_i d_i = 0 \end{array} \right] . \qquad (NC^r) $$

où $\hat{c} = B^{\top} c$, $D_i = B^{\top} G_i B$ et $d_i = B^{\top} G_i \nu + B^{\top} g_i$.

Le théorème suivant établit une condition nécessaire d'optimalité du (NC$^r$).

**Théorème 4.1:** *Soit $(\bar{\lambda}, \bar{y})$ un minimum local de $(NC^r)$. Alors il existe $\alpha^* \in \mathbb{R}^{n-m} \setminus \{0\}$ tel que*

$$ \left\{ \begin{array}{l} \hat{c} + M_{\bar{\lambda}} \alpha^* = 0 \\ \delta_i^* . \bar{\lambda}_i = 0 \\ \delta_i^* \ge 0, \quad i = 1, \dots, p \end{array} \right. $$

où $\delta_i^* = \langle \alpha^*, D_i \bar{y} + d_i \rangle$ et $M_{\bar{\lambda}} = \sum_{i=1}^{p} \lambda_i D_i$.

**PRÉUVE:** Le problème $(NC^r)$ peut s'écrire comme suit :

$$ \left\{ \begin{array}{l} \min_{\lambda, y} \hat{c}^{\top} y \\ g(\lambda, y) = 0 \\ h(\lambda, y) = 0 \\ l_i(\lambda, y) \ge 0, \end{array} \right. $$

où,
• $g(\lambda, y) = \sum_{i=1}^{p} \lambda_i D_i y + \sum_{i=1}^{p} \lambda_i d_i$.

• $h(\lambda, y) = \sum_{i=1}^{p} \lambda_i - 1$.

• $l_i(\lambda, y) = \lambda_i \quad i = 1, \dots, p$.

Soit $(\bar{\lambda}, \bar{y})$ un minimum local de $(NC^r)$. Considérons l'ensemble suivant :

$$Z = \left\{ \begin{array}{l} (u, v) \in \mathbb{R}^p \times \mathbb{R}^{n-m} / (D_1 \bar{y} + d_1, \dots, D_i \bar{y} + d_i, \dots, D_p \bar{y} + d_p) \quad u = 0, \\ \left( \sum_{i=1}^p \bar{\lambda}_i D_i \right) v = 0_{\mathbb{R}^p}, \quad \sum_{i=1}^p u_i = 0, \quad v^\top \hat{c} < 0, \quad u_i \ge 0 \quad \text{pour } \bar{\lambda}_i = 0. \end{array} \right\}$$

Comme $\left(\sum_{i=1}^{p} \bar{\lambda}_i D_i\right)$ est une matrice définie positive, alors $v = 0_{\mathbb{R}^p}$. De plus $v^\top \hat{c} < 0$, par suite $Z = \emptyset$. Donc, la qualification des contraintes de premier ordre est vérifiée. D'après [1, Theorem1], ils existent $\alpha^* \in \mathbb{R}^{n-m}$, $\beta \in \mathbb{R}$ et $\delta^* \in \mathbb{R}^p$ tels que $(\bar{\lambda}, \bar{y}, \alpha^*, \beta, \delta^*)$ satisfait :

$$\nabla (\hat{c}^\top y) + (\alpha^*)^\top \nabla g(\lambda, y) + \beta \nabla h(\lambda, y) - \sum_{i=1}^{p} \delta_i^* \nabla l_i(\lambda, y) = 0, \quad (4.1)$$

$$\sum_{i=1}^{p} \lambda_i D_i y + \sum_{i=1}^{p} \lambda_i d_i = 0, \quad (4.2)$$

$$\sum_{i=1}^{p} \lambda_i = 1, \quad (4.3)$$

$$\lambda_i \ge 0, \quad i = 1, \dots, p, \quad (4.4)$$

$$\delta_i^* \lambda_i = 0, \quad i = 1, \dots, p, \quad (4.5)$$

$$\delta_i^* \ge 0, \quad i = 1, \dots, p. \quad (4.6)$$

L'égalité (4.1) nous donne

$$\langle \alpha^*, D_i \bar{y} + d_i \rangle + \beta - \delta_i^* = 0, \quad i = 1, \dots, p \quad (4.7)$$

$$\hat{c} + M_{\bar{\lambda}} \alpha^* = 0. \quad (4.8)$$
De (4.7), nous avons

$$ \left\langle \alpha^*, \sum_{i=1}^{p} \bar{\lambda}_i D_i \bar{y} \right\rangle + \left\langle \alpha^*, \sum_{i=1}^{p} \bar{\lambda}_i d_i \right\rangle + \sum_{i=1}^{p} \bar{\lambda}_i \beta - \sum_{i=1}^{p} \bar{\lambda}_i \delta_i^* = 0, $$

d'après les égalités (4.2), (4.3) et (4.5), nous avons $\beta = 0$. Par suite

$$ \begin{gathered} \hat{c} + M_{\bar{\lambda}} \alpha^* = 0 \\ \delta_i^* = \langle \alpha^*, D_i \bar{y} + d_i \rangle, \quad i = 1, \dots, p \\ \delta_i^* \ge 0, \quad i = 1, \dots, p. \end{gathered} $$

Ce qui termine la preuve.

□

Montrons maintenant que le problème (NC) se ramène à la résolution d'un problème de programmation fractionnaire sur $\Lambda$. Commençons d'abord par le lemme suivant.

**Lemme 4.2:** Les éléments de la matrice $M_\lambda$ et du vecteur $F_\lambda$ s'écrivent comme combinaison linéaire de $\lambda_1, \lambda_2, \dots, \lambda_p$ avec $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_p)$.

PREUVE: 1) D'après la relation (3.3), on a :

$$ M_{\lambda} = B^{\top} G_{\lambda} B, $$

$$ \text{avec } G_{\lambda} = \sum_{i=1}^{p} \lambda_{i} G_{i}. $$

Les éléments de la matrice $G_\lambda$ sont des combinaisons linéaires de $\lambda_1, \lambda_2, \dots, \lambda_p$. Puisque $B$ ne dépend pas de $\lambda$, alors $M_\lambda = (a_{ij})_{1\le i,j \le n-m}$ est une matrice dont les $a_{ij}$ sont aussi des combinaisons linéaires de $\bar{\lambda}_1, \bar{\lambda}_2, \dots, \bar{\lambda}_p$, alors des réels $b_{ij}^k$ existent tels que :

$$ a_{ij} = \sum_{k=1}^{p} b_{ij}^{k} \lambda_{k} \quad \forall i, j \in \{1, 2, \dots, n-m\}. $$

2) D'après la relation (3.4), on a :

$$ F_{\lambda} = B^{\top} G_{\lambda} \nu + B^{\top} g_{\lambda}. $$

Comme la matrice $B$ et le vecteur $\nu$ ne dépendent pas de $\lambda$, alors les éléments du vecteur $F_\lambda$ sont aussi des combinaisons linéaires de $\lambda_1, \lambda_2, \dots, \lambda_p$. □
La proposition suivante caractérise les solutions du système (PL$_{λ}$).

**Proposition 4.3:** *Soit $y(\lambda)$ une solution du système $(PL_\lambda)$, alors ses composantes s'écrivent comme suit*

$$y_i(\lambda) = \frac{P_i(\lambda_1, \lambda_2, \dots, \lambda_p)}{Q(\lambda_1, \lambda_2, \dots, \lambda_p)}$$

où $P_i$ et $Q$ sont deux polynômes de degrés $p_i$ et $q$ respectivement avec $p_i$, $q \le n-m$.

**PREUVE:** Le point $y(\lambda)$ est une solution du problème $(PL_\lambda)$ si et seulement si

$$\left\{ \begin{array}{l} M_{\lambda}y = -F_{\lambda}^{\top} \\ y \in \mathbb{R}^{n-m}. \end{array} \right. \qquad (PL_{\lambda})$$

Comme la matrice $M_\lambda$ est définie positive alors les composantes $y_i$ s'écrivent comme suit

$$y_i(\lambda) = \frac{P_i(\lambda_1, \lambda_2, \dots, \lambda_p)}{\det(M_\lambda)}$$

où $P_i$ un polynôme de degré $p_i \le n-m$ et $\det(M_\lambda)$ est un polynôme de degré $q \le \dim(M_\lambda) = n-m$. $\square$

Soit $x \in \mathbb{R}^n$ un point efficient du programme (MOQP), nous avons

$$\begin{align*} x_i &= v_i + \sum_{j=1}^{n-m} b_{ij} y_j \\ &= \frac{v_i \det(M_\lambda) + \sum_{j=1}^{n-m} b_{ij} P_j(\lambda_1, \lambda_2, \dots, \lambda_p)}{\det(M_\lambda)}. \end{align*}$$

Posons $T_i(\lambda) = v_i \det(M_\lambda) - \sum_{j=1}^{n-m} b_{ij} P_j(\lambda)$. Le polynôme $T_i$ est de degré $t_i$ tel que

$$\begin{align*} t_i &\le \max \left( \max_{1 \le i \le n-m} (p_i), q \right) \\ &\le n-m. \end{align*}$$

Par suite les composantes du vecteur $x$ sont des fractions de $\lambda_1, \lambda_2, \dots, \lambda_p$.
**Théorème 4.4:** Le problème (NC) est équivalent à un problème de pro-
grammation fractionnaire sur $\Lambda$.

PREUVE: D'après le théorème 3.5, le problème (NC) est équivalent au problème (NC$^r$) suivant :

$$
\{ \min [ \hat{c}^\top y : M_\lambda y = -F_\lambda, y \in \mathbb{R}^{n-m}, \lambda \in \Lambda. ]
$$

où $\hat{c}^\top = Bc^\top$. D'autre part, d'après la proposition 4.3, il existe un polynôme $P_i$ tel que $y_i(\lambda) = \frac{P_i(\lambda)}{\det(M_\lambda)}$, et par suite, (NC) est équivalent au problème suivant :

$$
\left\{
\min \left[ \sum_{i=1}^{n-m} \hat{c}_i y_i : y_i(\lambda) = \frac{P_i(\lambda)}{\det(M_\lambda)}, \lambda \in \Lambda \right]
$$

c'est-à dire,

$$
\frac{\sum_{i=1}^{n-m} \hat{c}_i P_i(\lambda)}{\min_{\lambda \in \Lambda} \det(M_\lambda)}
$$

où, $\sum_{i=1}^{n-m} c_0^i P_i(\lambda)$ et $\det(M_\lambda)$ sont deux polynômes de degré inférieur à $n-m$.

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

**Exemple 4.5:** On considère le problème suivant :

$$
\left\{
\begin{array}{ll}
\min & x_1 + 2x_2 - 1x_3 \\
\text{et} & x \in \text{Eff}
\end{array}
\right.
\tag{PE1}
$$

où *Eff* est l'ensemble des points efficients du problème bicritère quadratique
convexe suivant :

$$
\left\{
\begin{array}{l}
\min f_1(x) = \frac{1}{2} x^\top G_1 x + g_1^\top x \\
\min f_2(x) = \frac{1}{2} x^\top G_2 x + g_2^\top x \\
Ax = b \\
x \in \mathbb{R}^3
\end{array}
\right.
\qquad (\text{MOQP1})
$$

$$
\text{où } G_1 = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix}, \quad G_2 = \begin{pmatrix} 1 & -1 & 0 \\ -1 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad g_1 = \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix},
$$

$$
g_2 = \begin{pmatrix} 1 \\ -2 \\ 0 \end{pmatrix}, A = \begin{pmatrix} 2 & 1 & -1 \end{pmatrix} \text{ et } b = 1.
$$
Nous avons :

$$ \nu = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 2 & 1 \end{pmatrix} \quad \text{et} \quad C = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} $$

$$ D_1 = B^\top G_1 B = \begin{pmatrix} 6 & 0 \\ 0 & 1 \end{pmatrix} \quad \text{et} \quad D_2 = B^\top G_2 B = \begin{pmatrix} 5 & 1 \\ 1 & 3 \end{pmatrix}. $$

$$ d_1 = B^\top (G_1 \nu + g_1) = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \quad \text{et} \quad d_2 = B^\top (G_2 \nu + g_2) = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. $$

$$ \hat{c} = B^\top c = \begin{pmatrix} -1 \\ 1 \end{pmatrix}. $$

Alors, la matrice $M_\lambda$ et le vecteur $F_\lambda$ sont :

$$ M_\lambda = \lambda D_1 + \mu D_2 = \begin{pmatrix} 6\lambda + 5\mu & \mu \\ \mu & \lambda + 3\mu \end{pmatrix} \quad \text{et} \quad F_\lambda = \lambda d_1 + \mu d_2 = \begin{pmatrix} 0 \\ \lambda \end{pmatrix}. $$

où, $\lambda + \mu = 1$.

La résolution du problème linéaire $M_\lambda y = -F_\lambda$ donne :

$$ y_1(\lambda, \mu) = \frac{\lambda\mu}{6\lambda^2 + 22\mu\lambda + 15\mu^2} \quad (4.9) $$

$$ y_2(\lambda, \mu) = \frac{-6\lambda^2 - 5\mu\lambda}{6\lambda^2 + 22\mu\lambda + 15\mu^2}. $$

La résolution du problème (PE1) est équivalente à la résolution du problème de programmation fractionnaire suivant :

$$ \min_{\lambda \in [0,1]} \frac{-6\lambda}{-\lambda^2 - 8\lambda + 15} . \quad (PE1F) $$

Nous avons trouvé $\lambda = 1$ comme solution optimale de (PE1F). En posant $\lambda = 1$ et $\mu = 0$ dans (4.9), nous obtenons $\bar{y} = \begin{pmatrix} 0 \\ -1 \end{pmatrix}$ et par suite $\bar{x} = B\bar{y} + \nu = \begin{pmatrix} -1 \\ 2 \\ -1 \end{pmatrix}$ comme solution optimale du problème (PE1).

En utilisant le théorème 4.1, il existe $\alpha^* \in \mathbb{R}^{n-m} \setminus \{0\}$ tel que

$$ \left\{ \begin{array}{l} \hat{c} + M_{\bar{\lambda}} \alpha^* = 0 \\ \delta_i^* \bar{\lambda}_i = 0 \\ \delta_i^* \ge 0, \quad i = 1, \dots, p \end{array} \right. $$
K. BELKEZIZ, A. METRANE

où $\delta_i^* = \langle \alpha^*, D_i\bar{y} + d_i \rangle$ et $M_\lambda = \sum_{i=1}^p \lambda_i D_i$.

On vérifie que $\alpha^* = -M_\lambda^{-1}\hat{c} = \begin{pmatrix} \frac{1}{6} \\ -1 \end{pmatrix}$, $D_1\bar{y} + d_1 = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$, $D_2\bar{y} + d_2 = \begin{pmatrix} -1 \\ -3 \end{pmatrix}$ et $\langle \alpha^*, D_2\bar{y} + d_2 \rangle = \frac{17}{6} \ge 0$.

**Remerciements.** Je tiens à exprimer mes vifs remerciements au referee anonyme pour ses corrections et nombreuses remarques importantes.

## Bibliographie

[1] G. P. McCormick A. V. Fiacco. *Nonlinear Programming, Sequential unconstrained minimization techniques*. Classics in Applied Mathematics, 1990.

[2] H. P. Benson. Efficiency and proper efficiency in vector maximization with respect to cones. *Journal of Mathematical Analysis and Applications*, 93:273–289, 1983.

[3] H. P. Benson. Optimization over the efficient set. *Journal of Mathematical Analysis and Applications*, 98:562–580, 1984.

[4] H. P. Benson. An algorithm for optimizing over the weakly-efficient set. *European Journal of Operational Research*, 25:192–199, 1986.

[5] J. Fulop. A cutting plane method for linear optimization over the efficient set. *Generalized Convexity, Edited by S. Komlosi, T. Rapcsak, and S. Schaible*, pages 374–385, 1994.

[6] T. Gal. A general method for determining the set of all efficient solutions to a linear vector-maximum problem. *European Journal of Operational Research*, 1:307–322, 1977.

[7] A. M. Geoffrion. Proper efficiency and the theory of vector maximization. *Journal of Mathematical Analysis and Applications*, 22:618–630, 1968.
[8] H. Isermann. The enumeration of the set of all efficient solutions for all a linear multiple objective program. *Operationel Research Quarterly*, 28:711-725, 1977.

[9] N. S. Hegner J. G Ecker and I. A. Kouada. Generating all maximal efficient faces for multiple linear programs. *Journal of optimization Theory and applications*, 30:353-381, 1980.

[10] D. T. Luc. *Theory of Vector Optimization*. Springer-verlag, Berlin Heidelberg New-York London Paris Tokyo, 1989.

[11] H. Konno P. T. Thach and D. Yokota. *A Dual Approach to a Minimization on the Set of Pareto-Optimal Solutions*. Working Paper, Institute of Human and Social Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1994.

[12] K. Tamara and S. Miura. On linear vector maximization problems. *Journal of the Operations Research Society of Japan*, 20:139-149, 1977.

K. BELKEZIZ
UNIVERSITÉ CADI AYYAD
DEPARTEMENT DE MATHÉMATIQUES
LABORATOIRE DE M.A.D
FSSM BP 2390
MARRAKECH 40000
MOROCCO
Belkeziz@ucam.ac.ma

A. METRANE
UNIVERSITÉ CADI AYYAD
DEPARTEMENT DE MATHÉMATIQUES
LABORATOIRE DE M.A.D
FSSM BP 2390
MARRAKECH 40000
MOROCCO
metrane@ucam.ac.ma