Chapitre II. Programmation convexe. Programmation convexe Programmation convexe nécessaire et conditions suffisantes

Si, dans une tâche de programmation mathématique, vous devez trouver l'extremum d'une fonction, par exemple:

sur l'ensemble des solutions réalisables données par les contraintes

1) la fonction objectif est différentiable et concave, c'est-à-dire la condition est remplie pour cela:

Pour toute,

2) et les côtés gauche de toutes les restrictions - fonctions différentiables et convexes, c'est-à-dire pour eux, les conditions suivantes sont remplies:

Pour toute,

Alors le problème (4.7) - (4.8) est appelé le problème programmation convexe.

Toute fonction linéaire satisfait simultanément les conditions de convexité et de concavité; ceux. il peut être considéré à la fois convexe et concave. Cela nous permet de considérer les problèmes linéaires comme un cas particulier de problèmes de programmation convexe.

Si pour les problèmes de programmation mathématique dans le cas général, il n'y a toujours pas de théorie cohérente de l'existence et de la stabilité d'une solution, alors pour les problèmes de programmation convexe il existe une telle théorie.

Introduisons trois définitions:

1). La fonction de Lagrange du problème de programmation convexe (4.7) - (4.8) est une fonction:

,

, (4.9)

2). On dit que le problème de programmation convexe (4.7) - (4.8) satisfait condition de régularités'il existe au moins un point intérieur de l'ensemble des solutions réalisables définies par des inégalités strictes obtenues à partir de (4.8) (i.e. ).

3). Le point est appelé selle point de la fonction si pour tout effectué:

Si la fonction objectif (supprimer)

Dans la théorie de la programmation non linéaire, la place centrale est occupée par le théorème de Kuhn-Tucker, qui généralise la méthode classique des multiplicateurs de Lagrange au cas où les contraintes du problème non linéaire, ainsi que les contraintes sous forme d'égalités, contiennent également des contraintes sous forme d'inégalités.

Théorème de Kuhn-Tucker. Si le problème de programmation convexe (4.7) - (4.8) satisfait la condition de régularité, alors un point est une solution optimale à ce problème si et seulement s'il existe un point avec des coordonnées non négatives qui est un point de selle de la fonction de Lagrange de ce problème.

Termes de Karush - Kuna - Tucker sous forme différentielle:

Si la fonction de Lagrange est convexe par rapport à, concave par rapport à et continuellement dérivable par rapport à tout et, alors pour qu'une paire soit un point de selle de la fonction de Lagrange, il est nécessaire et suffisant que les conditions suivantes soient satisfaites:

,

,

,

ExempleLe théorème de Kuhn-Tucker justifie la réduction du problème de programmation convexe au problème de trouver le point de selle de la fonction de Lagrange. Pour qu'une telle réduction ait un sens pratique, il est nécessaire que le problème qui en résulte soit un peu plus simple que celui d'origine. Cela ne se produit pas toujours; par conséquent, un certain nombre de méthodes directes ont été développées pour trouver une solution au problème non linéaire (4.5), (4.6). Considérons certains d'entre eux.

PROGRAMMATION CONVEXE, une section de programmation mathématique, dans laquelle le problème de la maximisation d'une fonction objectif concave f (x) d'un argument vectoriel x \u003d (x 1, ..., x n) satisfaisant les contraintes gi (x) ≥ 0, x Є X, i \u003d 1, ..., m, où gi sont des fonctions concaves, X est un ensemble convexe. Un point x satisfaisant ces contraintes est dit admissible. Le principal résultat de la théorie de la programmation convexe est le théorème du point de selle: pour qu'un point x * admissible d'un problème de programmation convexe soit optimal, il est nécessaire (dans des conditions assez larges) et suffisante l'existence d'un vecteur y * \u003d (y * 1, ..., ym *) avec des composantes non négatives y * telles que le point (x *, y *) soit un point de selle pour la fonction de Lagrange

problèmes de programmation convexe, c'est-à-dire que pour tout x Є X et y avec des composantes non négatives, les inégalités

Un certain nombre de méthodes de programmation convexes sont basées sur le théorème du point de selle, dans lequel soit la fonction φ (y 1, ..., y m) \u003d max x Є XL (x, y) est minimisée pour y i ≥ 0, i \u003d 1, .. ., m, ou le point de selle se trouve directement, et certaines de ses modifications sont parfois utilisées à la place de la fonction de Lagrange. Une autre approche pour résoudre le problème de la programmation convexe est associée à la recherche de directions possibles de mouvement du point admissible x, qui ne sont pas dérivées de l'ensemble des points admissibles et, en se déplaçant le long desquelles la fonction objectif augmente. Cette approche est implémentée en utilisant une séquence d'itérations. A chaque itération, la direction possible sortant du point suivant est calculée, après quoi un décalage est effectué dans cette direction d'une certaine distance vers le point suivant. Il existe des méthodes de résolution de problèmes de programmation convexe, spécialement adaptées au cas où la fonction objectif est non linéaire et les contraintes linéaires. En règle générale, les méthodes de programmation convexe nécessitent un nombre infini d'itérations pour déterminer avec précision le point optimal. Les exceptions sont les problèmes de programmation quadratique (la fonction objectif est la somme des fonctions concaves quadratiques et linéaires, les contraintes sont linéaires) et la programmation linéaire (la fonction objectif et les contraintes sont linéaires), pour lesquelles des méthodes finies sont principalement utilisées. De nombreuses méthodes informatiques de programmation convexe sont mises en œuvre sous la forme de programmes informatiques; il existe également des progiciels couvrant la programmation linéaire et les problèmes de programmation convexe. Voir également Recherche opérationnelle.

Lit.: Golshtein E.G. Programmation convexe. Éléments de la théorie. M., 1970; Zangwill W.I. Programmation non linéaire. Une approche. M., 1973.

Soit un système d'inégalités de forme

(4.3) et la fonction

Z \u003d f (x 1, x 2, ..., x n), (4,4)

de plus, toutes les fonctions sont convexes sur un ensemble convexe M, et la fonction Z est soit convexe sur l'ensemble M, soit concave.

Le problème de la programmation convexe est de trouver une solution au système de contraintes (4.3) où la fonction objectif Z atteint sa valeur minimale, ou la fonction concave Z atteint sa valeur maximale. (Les conditions de non-négativité des variables peuvent être considérées comme incluses dans le système (4.3)).

Compte tenu de la propriété 3 0, tout problème de programmation linéaire est un cas particulier de problème de programmation convexe. Dans le cas général, les problèmes de programmation convexe sont des problèmes de programmation non linéaires. La séparation des problèmes de programmation convexe en une classe spéciale s'explique par les propriétés extrémales des fonctions convexes: tout minimum local d'une fonction convexe (maximum local d'une fonction concave) est simultanément global; de plus, au vu de la propriété 2 0, une fonction convexe (concave) définie sur un ensemble borné fermé atteint un maximum global et un minimum global sur cet ensemble. Il s'ensuit donc que si la fonction objectif Z est strictement convexe (strictement concave) et si le domaine de solution du système de contraintes n'est pas vide et borné, alors le problème de programmation convexe a toujours une solution unique.

La fonction F (X) \u003d F (x 1, x 2, ..., x n) est appelée séparable, s'il peut être représenté comme une somme de fonctions dont chacune dépend d'une seule variable, c'est-à-dire si un

(il est possible que F i (x i) \u003d 0 pour certains i).

Supposons qu'un système de contraintes (4.3) et une fonction objectif (4.4) soient donnés dans un problème de programmation convexe, et la fonction objectif Z et toutes les contraintes sont séparables. Ensuite, le problème ressemble à:

Trouver le minimum d'une fonction convexe (maximum - concave)

avec restrictions

L'idée de la méthode d'approximation linéaire par morceaux est que tous les f i et tous sont remplacés par des lignes brisées constituées de segments de droite. Dans ce cas, le problème de programmation convexe d'origine est remplacé par un nouveau problème approximatif, qui est un problème de programmation linéaire. Ce problème est généralement résolu par la méthode simplex, et sa solution est une solution approximative au problème de programmation convexe d'origine.

Figure 12. Solution du problème de programmation convexe par approximation linéaire par morceaux

Pour construire un problème approximatif, considérons une approximation linéaire par morceaux d'une fonction d'une variable h (x) donnée sur un segment. Nous divisons ce segment en r parties par des points x 0

L'équation du segment de polyligne entre les points (x k; h k) et (x k + 1; h k + 1) a la forme (l'équation d'une ligne droite le long de deux points). Si chacune des relations de cette égalité est désignée par, alors on obtient:

Notez que pour chacun il existe une valeur unique satisfaisant les conditions (4.7). La dénotation peut être réécrite (4.7) sous la forme:

[Les équations (4.8) sont appelées équations paramétriques du segment.

Si h (x) \u003d 0, alors la seconde de ces équations se transforme en identité 0 \u003d 0, et la première prend la forme (4.1) - l'équation du segment situé en abscisse].

Ainsi, pour toute équation de la ligne brisée peut être écrite sous la forme:

et seules deux valeurs sont toujours différentes de zéro (si x est un point intérieur du kème segment de la partition) ou un (si x coïncide avec la fin du segment).

Revenant au problème de programmation convexe avec des fonctions séparables, nous notons que tout d'abord (en fonction du système de contraintes) il faut déterminer l'intervalle de variation de chaque variable x j. Ensuite, chaque intervalle est divisé en parties par des points x jk et, en utilisant les formules (4.9), une approximation linéaire par morceaux pour les fonctions f j et est construit. Après cela, pour le problème d'origine (4.6), nous pouvons écrire le problème approximatif:

Trouvez le maximum d'une fonction

soumis à des contraintes (4.10)

Puisque le problème approximatif (4.10) est un problème de programmation linéaire, qui est généralement résolu par la méthode du simplexe, les conditions de non-négativité des variables sont écrites séparément du reste des contraintes.

La différence entre le problème obtenu (4.10) et le problème de programmation linéaire habituel est que pour chaque x j il n'y a pas plus de deux voisins non nuls et, par conséquent, on ne peut pas prendre comme variables principales deux avec le même j et k non-adjacent. Notons également que, bien entendu, il n'est pas nécessaire d'effectuer une approximation linéaire par morceaux pour les conditions de non-négativité des termes variables f j (x j) et (s'il y en a).

Ce chapitre n'a passé en revue que quelques-unes des techniques d'optimisation utilisées par les managers pour prendre des décisions efficaces dans les entreprises. Cependant, les techniques décrites permettent de comprendre le principe de base de l'utilisation de l'appareil mathématique en économie, qui vous permet de choisir parmi une variété d'options alternatives optimales pour un cas ou une situation spécifique donné.

La fonction est appelée convexe

La fonction est appelée concave sur un ensemble convexe si pour des points et un nombre arbitraire que l'inégalité suivante tient:

Parfois, une fonction convexe est appelée convexe vers le bas par opposition à une fonction concave, qui est parfois appelée convexe vers le haut. La signification de ces noms ressort clairement de l'image géométrique d'une fonction typique convexe (Fig. 3.3) et concave (Fig. 3.4).

Figure: 3.3. Fonction convexe

Figure: 3.4. Fonction concave

Nous soulignons que les définitions des fonctions convexes et concaves n'ont de sens que pour l'ensemble convexe X, puisque seulement dans ce cas le point appartient nécessairement X.

Problème de programmation convexe est un cas particulier du problème général de la programmation mathématique (3.7), (3.8), lorsque la fonction objectif et les fonctions de contrainte sont concaves sur un ensemble convexe R.

Puisque le problème de la maximisation d'une fonction est équivalent au problème de la minimisation de cette fonction avec un signe moins, la contrainte est équivalente à une inégalité, et la convexité découle de la concavité et vice versa. D'ici

un problème de programmation convexe est également appelé le problème de minimisation d'une fonction convexe sous les contraintes:

, ,

où sont les fonctions convexes; R Est un ensemble convexe. C'est juste une autre forme du problème.

Il convient de noter que si un problème de programmation convexe est formulé comme un problème maximum, alors la fonction objectif est nécessairement concave, et si elle est formulée comme un problème minimum, alors elle est convexe. Si les contraintes sont écrites sous la forme, alors les fonctions de contraintes sont concaves, si les contraintes sont écrites sous la forme, alors les fonctions de contrainte sont convexes. Cette connexion est due à la présence de certaines propriétés du problème de programmation convexe, qui peuvent être absentes si une telle connexion est violée. Deux de ces propriétés principales sont énoncées dans le lemme suivant.

Lemme 1

L'ensemble des plans admissibles pour les problèmes de programmation convexe

est convexe. Tout maximum local de la fonction concave sur X est mondial.

Si les fonctions de contrainte étaient convexes, alors pour l'ensemble X (3.14) la convexité ne suivrait plus. Dans ce cas, la convexité de l'ensemble peut être prouvée:

Si la fonction objectif était convexe, alors l'assertion du lemme concernant ses maxima deviendrait invalide, mais une assertion similaire pourrait être prouvée pour les minima.

La fonction est appelée strictement convexe sur un ensemble convexe si pour des points , et un nombre arbitraire que l'inégalité tient.

La fonction est appelée strictement concave sur un ensemble convexe si pour des points , et un nombre arbitraire que l'inégalité suivante tient:

Lemme 2

La somme des fonctions convexes (concaves) est convexe (concave). Le produit d'une fonction convexe (concave) et d'un nombre positif est convexe (concave). La somme des fonctions convexe (concave) et strictement convexe (strictement concave) est strictement convexe (strictement concave).

Théorème 1

Si la fonction est strictement concave (strictement convexe) sur un ensemble convexe X, alors il ne peut avoir qu'un seul point maximum (minimum).

Preuve

Supposons le contraire, c'est-à-dire qu'il y a deux points ,, qui sont les points maximum d'une fonction strictement concave sur X... Dénotant, nous avons ... Alors pour tout, c'est vrai:

ceux. est venu à une contradiction. La preuve est similaire pour le minimum d'une fonction strictement convexe.

Une fonction linéaire est le seul exemple à la fois d'une fonction convexe et concave, elle n'est donc pas strictement convexe (strictement concave). Fonction quadratique peut ne pas être convexe (concave), mais peut être strictement convexe (strictement concave); tout est déterminé par la matrice ré... Éléments de la matrice ré représentent les secondes dérivées partielles d'une fonction quadratique, i.e.

.

On note la matrice des secondes dérivées partielles par.

Lemme 3

Pour la fonction quadratique était convexe (concave) dans tout l'espace, il est nécessaire et suffisant que la matrice ré a été défini positivement (négativement). Si un ré défini positivement (négativement), c'est-à-dire

alors il est strictement convexe (strictement concave).

Le problème de la maximisation (minimisation) d'une fonction quadratique sous contraintes linéaires, où ré Est une matrice définie négative (positive), et D T= réest appelé problème de programmation quadratique .

Il découle du lemme que le problème de programmation linéaire considéré dans la section 2, comme le problème de programmation quadratique, est un cas particulier du problème de programmation convexe.

Il existe des fonctions convexes dans un groupe de variables et concaves dans un autre. De telles fonctions représentent l'une des principales classes de fonctions pour lesquelles un point de selle existe certainement.

Théorème 2

(Sur l'existence d'un point de selle pour une fonction concave-convexe). Laisser être X et Oui sont des sous-ensembles bornés fermés convexes d'espaces euclidiens de dimension finie, et la fonction est continue en et, concave en et convexe en, a alors un point de selle.

Considérons la fonction de Lagrange pour un problème de programmation convexe:

(3.15)

défini sur un produit direct, où. En raison de sa concavité, cette fonction est concave et linéaire, et donc convexe.

Cependant, sur la base du théorème 1, on ne peut pas soutenir qu'il a une pointe de selle, puisque l'ensemble R n'est pas nécessairement fermé et limité, mais Oui évidemment illimité. Néanmoins, on peut s'attendre à ce que dans certaines conditions, une pointe de selle existera toujours.

Le théorème le plus célèbre lié à ce problème est le théorème de Kuhn-Tucker, qui établit un lien entre l'existence d'une solution à un problème de programmation convexe et un point de selle pour la fonction de Lagrange lorsque conditions Slater : un problème de programmation convexe satisfait la condition de Slater s'il y a un point tel que la condition est satisfaite: .

Théorème de Kuhn-Tucker

Si un problème de programmation convexe satisfait la condition de Slater, alors une condition nécessaire et suffisante pour l'optimalité de la conception est l'existence de tels que la paire est un point de selle de la fonction de Lagrange (3.15) sur.

L'exemple suivant montre que l'état de Slater est essentiel.

Exemple 1

Étant donné un problème de programmation convexe:

Ici, il est évident que x = 0 a une solution au problème, mais la fonction de Lagrange il n'y a pas de point de selle, car la limite externe dans le problème minimax n'est pas atteinte:

Partitionnement des contraintes dans un problème de programmation convexe en et , comme déjà mentionné, est conditionnel. Par conséquent, généralement sous R un ensemble d'une forme simple est compris, c'est soit tout l'espace E n, ou un orthant non négatif, ou un parallélépipède. La complexité du problème de programmation convexe est déterminée par le système de contraintes:

.

Puisque le point de selle de la fonction de Lagrange est recherché sur le produit d'ensembles, où Oui est aussi un ensemble de forme simple (orthant non négatif), le sens du théorème de Kuhn-Tucker est de réduire le problème de trouver l'extremum d'une fonction avec des contraintes complexes sur des variables au problème de trouver l'extremum d'une nouvelle fonction avec des contraintes simples.

Si l'ensemble R coïncide avec E n, alors les conditions extrêmes, comme on le sait, ont la forme:

De plus, ces conditions sont non seulement nécessaires pour que la fonction atteigne un maximum en, mais également suffisantes. C'est une propriété importante des fonctions concaves, et pour un problème de programmation convexe, elle est concave.

Théorème 3

Pour qu'une fonction concave continuellement différentiable ait un maximum en un point E n, il est nécessaire et suffisant que le gradient de la fonction au point soit égal à zéro, c'est-à-dire ...

Rappelons que le gradient de la fonction est:

.

Ainsi, pour trouver le point de selle de la fonction de Lagrange sur le produit, et, par conséquent, pour trouver une solution au problème de programmation convexe pour R= E n il est nécessaire de résoudre le système d'équations (3.16). Mais dans ce système n équations et inconnues n+ mpuisque d'ailleurs n-vecteur dimensionnel que nous ne connaissons pas et m-vecteur dimensionnel des multiplicateurs de Lagrange. Cependant, une propriété très importante est valable pour le point de selle de la fonction de Lagrange:

. (3.17)

L'équation (3.17) implique que l'un ou l'autre, ou, ou les deux simultanément. Cette propriété est similaire au deuxième théorème de dualité (Sec. 2.5) de la programmation linéaire. Contraintes satisfaites à un moment donné lorsque les égalités sont appelées actif .

Ainsi, seuls ces multiplicateurs de Lagrange peuvent être différents de zéro et correspondant aux contraintes actives au point. En tenant compte de cette propriété, pour trouver une solution à un problème de programmation convexe, considérez la méthode suivante.

Conférence 11.Programmation convexe

Définition 1. Z par programmation convexe est un problème de programmation non linéaire où toutes les fonctions sont convexes.

Ainsi, un problème de programmation convexe est un problème de minimisation conditionnelle, où la fonction objectif est convexe et le domaine réalisable est un ensemble convexe formé par un système d'inégalités convexes. Par conséquent, les déclarations obtenues précédemment dans la section 6 sont valides pour le problème de programmation convexe. Dans cette section, nous concrétisons ces résultats généraux et les présentons sous une forme plus pratique pour rechercher et résoudre le problème de programmation convexe suivant:

(1)

, (2)

. (3)

Nous aurons besoin de constructions auxiliaires dans l'espace
vecteurs
... Vecteur du premier
composante ponctuelle sera désigné par ... Alors,
.

Pour le problème (1) - (3), nous définissons l'ensemble

où
.

Lemme . Pour problème de programmation convexe (1) - (3) un tas de convexe.

Preuve. Nous choisissons des vecteurs arbitraires
de la multitude et le nombre
... Ensuite, il y a des points et de tels que et. Nous multiplions ces inégalités par et
, respectivement, et ajoutez-les. Puisque toutes les fonctions sont convexes, on obtient

Il résulte des inégalités obtenues que l'ensemble est convexe .

Théorème 1. (Le théorème de Kuhn-Tucker sous la forme du point de selle de la fonction de Lagrange d'un problème de programmation convexe ) Soit, dans le problème de programmation convexe (1) - (3), le système (2) satisfait la condition de Slater par rapport à était une solution au problème (1) - (3), il est nécessaire et suffisant qu'un vecteur non négatif tel que
Est le point de selle de la fonction Lagrange.

Preuve. Puisque la suffisance de cette condition a déjà été prouvée pour un problème de programmation non linéaire arbitraire (voir le théorème 2.6 de l'introduction), il ne reste plus qu'à prouver la nécessité.

Nécessité. Laisser être - solution au problème (1) - (3). nous mettons
... Il est évident que
, comme
,
et
.

Assurons-nous que
... Supposons le contraire. Cela signifie qu'il y a un point
tel que
... Par conséquent, - tel point admissible, la valeur de la fonction objectif dans laquelle est inférieure au minimum. Nous avons une contradiction avec le fait que - solution du problème de programmation convexe.

Alors,
... Selon le lemme, l'ensemble convexe. Par conséquent, toutes les exigences du théorème 8.2 sont satisfaites. Par conséquent, il y a un non nul

vecteur
point de pivot à la multitude :

Vérifions en outre que toutes les coordonnées du vecteur ne sont pas positifs. Supposons le contraire. Qu'il y ait une coordonnée
... Fixons le vecteur tous les composants sauf -Oh. Ensuite, étant donné que le produit
peut prendre des valeurs arbitrairement grandes (puisque les coordonnées ), on obtient une contradiction avec l'inégalité (4).

Il est facile de voir que pour tout
vecteurs
inclus dans de nombreux ... Puis de (4) nous avons:

Montrons que
... Qu'il n'en soit pas ainsi. ensuite
... Par conséquent,
... Par la condition de Slater, il existe un vecteur
tel que
... donc
... La contradiction qui en résulte signifie que
.

Nous dénotons
... Montrons que le vecteur construit est le vecteur requis des multiplicateurs de Lagrange. Il est évident que
et de (5) on obtient

Par conséquent, à
devrait

. (7)

D'autre part, depuis
(dans la mesure où
) et
, on obtient l'inégalité

... De ceci et (7) il s'ensuit qu'au point
la condition de relâchement complémentaire est satisfaite:

. (8)

De (6) et (8) nous avons

ou, qui est le même,

De plus, laissez
... ensuite
... De ceci et (8) nous obtenons l'inégalité

Inégalités (9), (10) et signifient que
Est le point de selle de la fonction de Lagrange du problème convexe

logo de programmation. Ce qui était nécessaire.

Avant de se familiariser avec une autre version du théorème de Kuhn-Tucker, nous présentons le théorème suivant, qui est un critère minimum conditionnel en termes de cônes vecteurs de support.

Théorème 2. Laisser être - convexe et différenciable sur
fonction, définir
convexe. Puis pour pointer
était le minimum conditionnel de la fonction sur le plateau
, il est nécessaire et suffisant pour l'inclusion

. (11)

La preuve découle directement du théorème 6.5 et de la définition du cône
vecteurs de soutien au point à la multitude
.

Théorème 3. (Théorème de Kuhn-Tucker sous forme différentielle pour un problème de programmation convexe ) Soit un problème de programmation convexe sous la forme (1), (2), où toutes les fonctions
sont continuellement différentiables, le système (2) satisfait la condition de Slater. Ensuite, pour que le vecteur
était une solution au problème (1), (2), il est nécessaire et suffisant qu'un vecteur non négatif telle que les conditions

, (12)

.

Preuve. Montrons que les conditions (12) et (13) sont équivalentes à l'inclusion (11). Laissez le point
est telle que
... ensuite
et
.

Laisse maintenant
... Ensuite, il découle des théorèmes 2 et 10.5 qu'une condition nécessaire et suffisante pour un extremum est l'existence de tels facteurs
,
Pour qui
... nous mettons
pour tous
et on obtient des dernières conditions d'égalité (12) et (13). Ce qui était nécessaire.

Pour conclure cette section, nous présentons les formulations de deux théorèmes de Kuhn-Tucker pour le problème de

programmation convexe avec contraintes linéaires.

Théorème 4. Soit le système de contraintes (2) dans le problème de programmation convexe (1) - (3) de la forme

, b - vecteur de dimension
... Ensuite, pour un vecteur non négatif était la solution au problème, il est nécessaire et suffisant que

il y avait un vecteur non négatif tel que
Est le point de selle de la fonction de Lagrange du problème donné.

Notez que dans ce cas, la fonction Lagrange a la forme.

Théorème 5. Soit dans le problème de programmation convexe (1), (2) la fonction objectif est continuellement différentiable, le système de contraintes (2) a la forme
, où A est une matrice de dimension
, b - vecteur de dimension
. Ensuite, pour que le vecteur
était une solution au problème, il est nécessaire et suffisant qu'il y ait un vecteur non négatif telle que les conditions
,
.

Notez que les théorèmes 4 et 5 ne nécessitent pas la réalisation de la condition de Slater; par conséquent, ils ne sont pas des cas particuliers des théorèmes 1 et 3 et nécessitent une preuve indépendante.