Optimisation convexe - Guide rapide

Ce cours est utile pour les étudiants qui souhaitent résoudre des problèmes d'optimisation non linéaires qui se posent dans diverses applications techniques et scientifiques. Ce cours débute par la théorie de base de la programmation linéaire et présentera les concepts d'ensembles et de fonctions convexes et les terminologies associées pour expliquer les divers théorèmes nécessaires pour résoudre les problèmes de programmation non linéaire. Ce cours présentera divers algorithmes qui sont utilisés pour résoudre de tels problèmes. Ces types de problèmes se posent dans diverses applications, y compris l'apprentissage automatique, les problèmes d'optimisation en génie électrique, etc. Il nécessite que les étudiants aient une connaissance préalable des concepts mathématiques et du calcul du secondaire.

Dans ce cours, les étudiants apprendront à résoudre les problèmes d'optimisation comme $ min f \ left (x \ right) $ sous certaines contraintes.

Ces problèmes sont facilement résolubles si la fonction $ f \ left (x \ right) $ est une fonction linéaire et si les contraintes sont linéaires. Ensuite, il est appelé un problème de programmation linéaire (LPP). Mais si les contraintes ne sont pas linéaires, alors il est difficile de résoudre le problème ci-dessus. À moins que nous puissions tracer les fonctions dans un graphique, alors essayer d'analyser l'optimisation peut être un moyen, mais nous ne pouvons pas tracer une fonction si elle est au-delà de trois dimensions. D'où viennent les techniques de programmation non linéaire ou de programmation convexe pour résoudre de tels problèmes. Dans ce tutoriel, nous nous concentrerons sur l'apprentissage de telles techniques et au final, quelques algorithmes pour résoudre de tels problèmes. nous apporterons d'abord la notion d'ensembles convexes qui est la base des problèmes de programmation convexes. Ensuite, avec l'introduction des fonctions convexes, nous allons quelques théorèmes importants pour résoudre ces problèmes et quelques algorithmes basés sur ces théorèmes.

Terminologies

• L'espace $ \ mathbb {R} ^ n $ - C'est un vecteur à n dimensions avec des nombres réels, défini comme suit - $ \ mathbb {R} ^ n = \ left \ {\ left (x_1, x_2, ... , x_n \ right) ^ {\ tau}: x_1, x_2, ...., x_n \ in \ mathbb {R} \ right \} $

• L'espace $ \ mathbb {R} ^ {mXn} $ - C'est un ensemble de toutes les matrices de valeurs réelles d'ordre $ mXn $.

Méthodologie

La programmation linéaire, également appelée optimisation linéaire, est une technique utilisée pour résoudre des problèmes mathématiques dans lesquels les relations sont de nature linéaire. la nature fondamentale de la programmation linéaire est de maximiser ou de minimiser unobjective function avec sujet à certains constraints. La fonction objectif est une fonction linéaire obtenue à partir du modèle mathématique du problème. Les contraintes sont les conditions qui sont imposées au modèle et sont également linéaires.

• À partir de la question donnée, trouvez la fonction objectif.
• trouvez les contraintes.
• Dessinez les contraintes sur un graphique.
• trouver la région réalisable, qui est formée par l'intersection de toutes les contraintes.
• trouver les sommets de la région réalisable.
• trouver la valeur de la fonction objectif à ces sommets.
• Le sommet qui maximise ou minimise la fonction objectif (selon la question) est la réponse.

Exemples

Step 1 - Maximisez 5 $ x + 3y $ sous réserve de

$ x + y \ leq 2 $,

$ 3x + y \ leq 3 $,

$ x \ geq 0 \: et \: y \ geq 0 $

Solution -

La première étape consiste à trouver la région réalisable sur un graphique.

Clairement à partir du graphique, les sommets de la région des possibles sont

$ \ gauche (0, 0 \ droite) \ gauche (0, 2 \ droite) \ gauche (1, 0 \ droite) \ gauche (\ frac {1} {2}, \ frac {3} {2} \ droite ) $

Soit $ f \ left (x, y \ right) = 5x + 3y $

En mettant ces valeurs dans la fonction objectif, nous obtenons -

$ f \ gauche (0, 0 \ droite) $ = 0

$ f \ gauche (0, 2 \ droite) $ = 6

$ f \ gauche (1, 0 \ droite) $ = 5

$ f \ gauche (\ frac {1} {2}, \ frac {3} {2} \ droite) $ = 7

Par conséquent, la fonction maximise à $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $

Step 2- Une entreprise horlogère produit une montre numérique et une montre mécanique. Les projections à long terme indiquent une demande prévue d'au moins 100 montres numériques et 80 montres mécaniques par jour. En raison des limites de la capacité de production, pas plus de 200 montres numériques et 170 montres mécaniques peuvent être fabriquées quotidiennement. Pour satisfaire un contrat d'expédition, au moins 200 montres au total sont expédiées chaque jour.

Si chaque montre numérique vendue entraîne une perte de $ \ $ 2 $, mais que chaque montre mécanique produit un profit $ \ $ 5 $, combien de chaque type devrait-il être fait quotidiennement pour maximiser les profits nets?

Solution -

Soit $ x $ le nombre de montres numériques produites

$ y $ le nombre de montres mécaniques produites

Selon la question, au moins 100 montres numériques doivent être fabriquées quotidiennement et au maximum 200 montres numériques peuvent être fabriquées.

$ \ Rightarrow 100 \ leq \: x \ leq 200 $

De même, au moins 80 montres mécaniques doivent être fabriquées quotidiennement et au maximum 170 montres mécaniques peuvent être fabriquées.

$ \ Rightarrow 80 \ leq \: y \ leq 170 $

Puisqu'au moins 200 montres doivent être produites chaque jour.

$ \ Flèche droite x + y \ leq 200 $

Étant donné que chaque montre numérique vendue entraîne une perte $ \ $ 2 $, mais chaque montre mécanique produit un profit $ \ $ 5 $,

Le profit total peut être calculé comme suit

$ Profit = -2x + 5 ans $

Et nous devons maximiser le profit, Par conséquent, la question peut être formulée comme -

Maximiser -2x $ + 5y $ sous réserve de

100 $ \: \ leq x \: \ leq 200 $

80 $ \: \ leq y \: \ leq 170 $

$ x + y \: \ leq 200 $

En traçant les équations ci-dessus dans un graphique, nous obtenons,

Les sommets de la région des possibles sont

$ \ gauche (100, 170 \ droite) \ gauche (200, 170 \ droite) \ gauche (200, 180 \ droite) \ gauche (120, 80 \ droite) et \ gauche (100, 100 \ droite) $

La valeur maximale de la fonction objectif est obtenue à $ \ left (100, 170 \ right) $ Ainsi, pour maximiser les profits nets, 100 unités de montres numériques et 170 unités de montres mécaniques devraient être produites.

Une norme est une fonction qui donne une valeur strictement positive à un vecteur ou à une variable.

La norme est une fonction $ f: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $

Les caractéristiques de base d'une norme sont -

Soit $ X $ un vecteur tel que $ X \ in \ mathbb {R} ^ n $

• $ \ gauche \ | x \ droite \ | \ geq 0 $

• $ \ gauche \ | x \ right \ | = 0 \ Leftrightarrow x = 0 \ forall x \ in X $

• $ \ gauche \ | \ alpha x \ droite \ | = \ gauche | \ alpha \ droite | \ gauche \ | x \ right \ | \ forall \: x \ in X and \: \ alpha \: is \: a \: scalar $

• $ \ gauche \ | x + y \ droite \ | \ leq \ gauche \ | x \ droite \ | + \ gauche \ | y \ droit \ | \ forall x, y \ dans X $

• $ \ gauche \ | xy \ droite \ | \ geq \ gauche \ | \ gauche \ | x \ droite \ | - \ gauche \ | y \ droit \ | \ droite \ | $

Par définition, la norme est calculée comme suit -

• $ \ gauche \ | x \ right \ | _1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ left | x_i \ droite | $

• $ \ gauche \ | x \ right \ | _2 = \ left (\ displaystyle \ sum \ limits_ {i = 1} ^ n \ left | x_i \ right | ^ 2 \ right) ^ {\ frac {1} {2}} $

• $ \ gauche \ | x \ right \ | _p = \ left (\ displaystyle \ sum \ limits_ {i = 1} ^ n \ left | x_i \ right | ^ p \ right) ^ {\ frac {1} {p}}, 1 \ leq p \ leq \ infty $

La norme est une fonction continue.

Preuve

Par définition, si $ x_n \ rightarrow x $ in $ X \ Rightarrow f \ left (x_n \ right) \ rightarrow f \ left (x \ right) $ alors $ f \ left (x \ right) $ est une fonction constante.

Soit $ f \ left (x \ right) = \ left \ | x \ droite \ | $

Par conséquent, $ \ left | f \ gauche (x_n \ droite) -f \ gauche (x \ droite) \ droite | = \ gauche | \ gauche \ | x_n \ droite \ | - \ gauche \ | x \ droite \ | \ droite | \ leq \ gauche | \ gauche | x_n-x \ droite | \: \ droite | $

Puisque $ x_n \ rightarrow x $ donc, $ \ left \ | x_n-x \ right \ | \ rightarrow 0 $

Donc $ \ left | f \ left (x_n \ right) -f \ left (x \ right) \ right | \ leq 0 \ Rightarrow \ left | f \ left (x_n \ right) -f \ left (x \ right) \ right | = 0 \ Rightarrow f \ left (x_n \ right) \ rightarrow f \ left (x \ right) $

Par conséquent, la norme est une fonction continue.

Le produit interne est une fonction qui donne un scalaire à une paire de vecteurs.

Produit interne - $ f: \ mathbb {R} ^ n \ times \ mathbb {R} ^ n \ rightarrow \ kappa $ où $ \ kappa $ est un scalaire.

Les caractéristiques de base du produit intérieur sont les suivantes -

Soit $ X \ in \ mathbb {R} ^ n $

• $ \ left \ langle x, x \ right \ rangle \ geq 0, \ forall x \ in X $

• $ \ left \ langle x, x \ right \ rangle = 0 \ Leftrightarrow x = 0, \ forall x \ in X $

• $ \ left \ langle \ alpha x, y \ right \ rangle = \ alpha \ left \ langle x, y \ right \ rangle, \ forall \ alpha \ in \ kappa \: et \: \ forall x, y \ in X $

• $ \ left \ langle x + y, z \ right \ rangle = \ left \ langle x, z \ right \ rangle + \ left \ langle y, z \ right \ rangle, \ forall x, y, z \ in X $

• $ \ left \ langle \ overline {y, x} \ right \ rangle = \ left (x, y \ right), \ forall x, y \ in X $

Note -

• Relation entre la norme et le produit intérieur: $ \ left \ | x \ right \ | = \ sqrt {\ left (x, x \ right)} $

• $ \ forall x, y \ in \ mathbb {R} ^ n, \ left \ langle x, y \ right \ rangle = x_1y_1 + x_2y_2 + ... + x_ny_n $

Exemples

1. trouvez le produit intérieur de $ x = \ left (1,2,1 \ right) \: et \: y = \ left (3, -1,3 \ right) $

Solution

$ \ gauche \ langle x, y \ droite \ rangle = x_1y_1 + x_2y_2 + x_3y_3 $

$ \ left \ langle x, y \ right \ rangle = \ left (1 \ times3 \ right) + \ left (2 \ times-1 \ right) + \ left (1 \ times3 \ right) $

$ \ gauche \ langle x, y \ droite \ rangle = 3 + \ gauche (-2 \ droite) + 3 $

$ \ gauche \ langle x, y \ droite \ rangle = 4 $

2. Si $ x = \ left (4,9,1 \ right), y = \ left (-3,5,1 \ right) $ et $ z = \ left (2,4,1 \ right) $, trouver $ \ left (x + y, z \ right) $

Solution

Comme nous le savons, $ \ left \ langle x + y, z \ right \ rangle = \ left \ langle x, z \ right \ rangle + \ left \ langle y, z \ right \ rangle $

$ \ left \ langle x + y, z \ right \ rangle = \ left (x_1z_1 + x_2z_2 + x_3z_3 \ right) + \ left (y_1z_1 + y_2z_2 + y_3z_3 \ right) $

$ \ left \ langle x + y, z \ right \ rangle = \ left \ {\ left (4 \ times 2 \ right) + \ left (9 \ times 4 \ right) + \ left (1 \ times1 \ right) \ droite \} + $

$ \ left \ {\ left (-3 \ times2 \ right) + \ left (5 \ times4 \ right) + \ left (1 \ times 1 \ right) \ right \} $

$ \ gauche \ langle x + y, z \ droite \ rangle = \ gauche (8 + 36 + 1 \ droite) + \ gauche (-6 + 20 + 1 \ droite) $

$ \ gauche \ langle x + y, z \ droite \ rangle = 45 + 15 $

$ \ gauche \ langle x + y, z \ droite \ rangle = 60 $

Local Minima ou Minimize

$ \ bar {x} \ in \: S $ est dit minima locaux d'une fonction $ f $ if $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ bar {x} \ right) $ où $ N_ \ varepsilon \ left (\ bar {x} \ right) $ signifie le voisinage de $ \ bar {x} $, soit $ N_ \ varepsilon \ left (\ bar {x} \ right) $ signifie $ \ left \ | x- \ bar {x} \ right \ | <\ varepsilon $

Local Maxima ou Maximizer

$ \ bar {x} \ in \: S $ est dit être les maxima locaux d'une fonction $ f $ if $ f \ left (\ bar {x} \ right) \ geq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ bar {x} \ right) $ où $ N_ \ varepsilon \ left (\ bar {x} \ right) $ signifie le voisinage de $ \ bar {x} $, soit $ N_ \ varepsilon \ left (\ bar {x} \ right) $ signifie $ \ left \ | x- \ bar {x} \ right \ | <\ varepsilon $

Minimums mondiaux

$ \ bar {x} \ in \: S $ est dit être des minima globaux d'une fonction $ f $ if $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ en S $

Maximas globaux

$ \ bar {x} \ in \: S $ est dit maximum global d'une fonction $ f $ if $ f \ left (\ bar {x} \ right) \ geq f \ left (x \ right), \ forall x \ en S $

Exemples

Step 1- trouver les minima et maxima locaux de $ f \ left (\ bar {x} \ right) = \ left | x ^ 2-4 \ droite | $

Solution -

D'après le graphique de la fonction ci-dessus, il est clair que les minima locaux se produisent à $ x = \ pm 2 $ et les maxima locaux à $ x = 0 $

Step 2- trouver les minima globaux de la fonction $ f \ left (x \ right) = \ left | 4x ^ 3-3x ^ 2 + 7 \ droite | $

Solution -

D'après le graphique de la fonction ci-dessus, il est clair que les minima globaux se produisent à $ x = -1 $.

Soit $ S \ subseteq \ mathbb {R} ^ n $ Un ensemble S est dit convexe si le segment de droite joignant deux points quelconques de l'ensemble S appartient aussi au S, c'est-à-dire si $ x_1, x_2 \ dans S $ , puis $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ où $ \ lambda \ in \ left (0,1 \ right) $.

Note -

• L'union de deux ensembles convexes peut être convexe ou non.
• L'intersection de deux ensembles convexes est toujours convexe.

Proof

Soit $ S_1 $ et $ S_2 $ deux ensembles convexes.

Soit $ S_3 = S_1 \ cap S_2 $

Soit $ x_1, x_2 \ dans S_3 $

Puisque $ S_3 = S_1 \ cap S_2 $ donc $ x_1, x_2 \ dans S_1 $ et $ x_1, x_2 \ dans S_2 $

Puisque $ S_i $ est un ensemble convexe, $ \ forall $ $ i \ en 1,2, $

Ainsi $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ où $ \ lambda \ in \ left (0,1 \ right) $

Donc, $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_1 \ cap S_2 $

$ \ Rightarrow \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_3 $

Par conséquent, $ S_3 $ est un ensemble convexe.

• Moyenne pondérée de la forme $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, où $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ et $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ est appelée combinaison conique de $ x_1, x_2, .... x_k. $

• Moyenne pondérée de la forme $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, où $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ est appelée combinaison affine de $ x_1 , x_2, .... x_k. $

• La moyenne pondérée de la forme $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ est appelée combinaison linéaire de $ x_1, x_2, .... x_k. $

Exemples

Step 1 - Montrer que l'ensemble $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ est un ensemble convexe.

Solution

Soit $ x_1 $ et $ x_2 \ dans S $

$ \ Rightarrow Cx_1 \ leq \ alpha $ et $ \: et \: Cx_2 \ leq \ alpha $

Pour afficher: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ droite) $

$ Cy = C \ gauche (\ lambda x_1 + \ gauche (1- \ lambda \ droite) x_2 \ droite) = \ lambda Cx_1 + \ gauche (1- \ lambda \ droite) Cx_2 $

$ \ Rightarrow Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha $

$ \ Rightarrow Cy \ leq \ alpha $

$ \ Rightarrow y \ en S $

Par conséquent, $ S $ est un ensemble convexe.

Step 2 - Montrer que l'ensemble $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ est un convexe ensemble.

Solution

Soit $ x, y \ dans S $

Soit $ x = \ left (x_1, x_2 \ right) $ et $ y = \ left (y_1, y_2 \ right) $

$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ et $ y_ {1} ^ {2} \ leq 8y_2 $

Pour afficher - $ \ lambda x + \ left (1- \ lambda \ right) y \ in S \ Rightarrow \ lambda \ left (x_1, x_2 \ right) + \ left (1- \ lambda \ right) \ left (y_1, y_2 \ right) \ in S \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda) y_2] \ in S \ right) \ right] $

$ Maintenant, \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} = \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) x_1y_1 $

Mais $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $

Par conséquent,

$ \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) \ left (x_ {1} ^ {2} + y_ {1} ^ {2} \ right) $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda x_ {1} ^ {2} + \ left (1- \ lambda \ right) y_ {1} ^ {2} $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ lambda x_2 + 8 \ left (1- \ lambda \ right) y_2 $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ left [\ lambda x_2 + \ left (1- \ lambda \ right) y_2 \ right] $

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) y \ in S $

Step 3 - Montrer qu'un ensemble $ S \ in \ mathbb {R} ^ n $ est convexe si et seulement si pour chaque entier k, chaque combinaison convexe de tout k points de $ S $ est dans $ S $.

Solution

Soit $ S $ un ensemble convexe. puis, pour montrer;

$ c_1x_1 + c_2x_2 + ..... + c_kx_k \ in S, \ displaystyle \ sum \ limits_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ...., k $

Preuve par induction

Pour $ k = 1, x_1 \ dans S, c_1 = 1 \ Rightarrow c_1x_1 \ in S $

Pour $ k = 2, x_1, x_2 \ in S, c_1 + c_2 = 1 $ et Puisque S est un ensemble convexe

$ \ Rightarrow c_1x_1 + c_2x_2 \ dans S. $

Soit la combinaison convexe de m points de S dans S ie,

$ c_1x_1 + c_2x_2 + ... + c_mx_m \ in S, \ displaystyle \ sum \ limits_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ..., m $

Maintenant, Soit $ x_1, x_2 ...., x_m, x_ {m + 1} \ in S $

Soit $ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $

Soit $ x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) \ frac {\ mu_1x_1 + \ mu_2x_2 + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} + \ mu_ {m + 1} x_ {m + 1} $

Soit $ y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} $

$ \ Flèche droite x = \ gauche (\ mu_1 + \ mu_2 + ... + \ mu_m \ droite) y + \ mu_ {m + 1} x_ {m + 1} $

Maintenant $ y \ dans S $ car la somme des coe ff icients est 1.

$ \ Rightarrow x \ in S $ puisque S est un ensemble convexe et $ y, x_ {m + 1} \ in S $

D'où prouvé par induction.

Un ensemble $ A $ est dit un ensemble affine si pour deux points distincts, la ligne passant par ces points se trouve dans l'ensemble $ A $.

Note -

• $ S $ est un ensemble affine si et seulement s'il contient toutes les combinaisons affines de ses points.

• Les ensembles vides et singleton sont à la fois des ensembles affine et convexe.

  Par exemple, la solution d'une équation linéaire est un ensemble affine.

Preuve

Soit S la solution d'une équation linéaire.

Par définition, $ S = \ left \ {x \ in \ mathbb {R} ^ n: Ax = b \ right \} $

Soit $ x_1, x_2 \ dans S \ Rightarrow Ax_1 = b $ et $ Ax_2 = b $

Pour prouver: $ A \ left [\ theta x_1 + \ left (1- \ theta \ right) x_2 \ right] = b, \ forall \ theta \ in \ left (0,1 \ right) $

$ A \ left [\ theta x_1 + \ left (1- \ theta \ right) x_2 \ right] = \ theta Ax_1 + \ left (1- \ theta \ right) Ax_2 = \ theta b + \ left (1- \ theta \ right) ) b = b $

Ainsi S est un ensemble affine.

Théorème

Si $ C $ est un ensemble affine et $ x_0 \ en C $, alors l'ensemble $ V = C-x_0 = \ left \ {x-x_0: x \ in C \ right \} $ est un sous-espace de C.

Preuve

Soit $ x_1, x_2 \ dans V $

Pour afficher: $ \ alpha x_1 + \ beta x_2 \ in V $ pour certains $ \ alpha, \ beta $

Maintenant, $ x_1 + x_0 \ en C $ et $ x_2 + x_0 \ en C $ par définition de V

Maintenant, $ \ alpha x_1 + \ beta x_2 + x_0 = \ alpha \ left (x_1 + x_0 \ right) + \ beta \ left (x_2 + x_0 \ right) + \ left (1- \ alpha - \ beta \ right) x_0 $

Mais $ \ alpha \ left (x_1 + x_0 \ right) + \ beta \ left (x_2 + x_0 \ right) + \ left (1- \ alpha - \ beta \ right) x_0 \ en C $ car C est un ensemble affine .

Par conséquent, $ \ alpha x_1 + \ beta x_2 \ dans V $

D'où prouvé.

L'enveloppe convexe d'un ensemble de points dans S est la limite de la plus petite région convexe qui contient tous les points de S à l'intérieur ou sur sa frontière.

OU

Soit $ S \ subseteq \ mathbb {R} ^ n $ L'enveloppe convexe de S, notée $ Co \ left (S \ right) $ by est la collection de toutes les combinaisons convexes de S, c'est-à-dire $ x \ dans Co \ left (S \ right) $ si et seulement si $ x \ in \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $, où $ \ displaystyle \ sum \ limits_ {1} ^ n \ lambda_i = 1 $ et $ \ lambda_i \ geq 0 \ forall x_i \ en S $

Remark - La coque conve d'un ensemble de points en S dans le plan définit un polygone convexe et les points de S sur la frontière du polygone définissent les sommets du polygone.

Theorem $ Co \ left (S \ right) = \ left \ {x: x = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i, x_i \ in S, \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 \ right \} $ Montrer qu'une coque convexe est un ensemble convexe.

Preuve

Soit $ x_1, x_2 \ in Co \ left (S \ right) $, puis $ x_1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $ et $ x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ \ gamma x_i $ où $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ et $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Pour $ \ theta \ in \ left (0,1 \ right), \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ theta \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_ix_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i \ theta x_i + \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i \ gauche (1- \ theta \ droite) x_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ droite] x_i $

Compte tenu des coefficients,

$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ right] = \ theta \ displaystyle \ sum \ limits_ {i = 1 } ^ n \ lambda_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = \ theta + \ left (1- \ theta \ right) = 1 $

Par conséquent, $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

Ainsi, une coque convexe est un ensemble convexe.

Soit S un ensemble arbitraire dans $ \ mathbb {R} ^ n $ .Si $ x \ in Co \ left (S \ right) $, alors $ x \ in Co \ left (x_1, x_2, ...., x_n, x_ {n + 1} \ droite) $.

Preuve

Puisque $ x \ dans Co \ left (S \ right) $, alors $ x $ est représenté par une combinaison convexe d'un nombre fini de points dans S, ie,

$ x = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ lambda_jx_j, \ displaystyle \ sum \ limits_ {j = 1} ^ k \ lambda_j = 1, \ lambda_j \ geq 0 $ et $ x_j \ en S, \ forall j \ in \ left (1, k \ right) $

Si $ k \ leq n + 1 $, le résultat obtenu est évidemment vrai.

Si $ k \ geq n + 1 $, alors $ \ left (x_2-x_1 \ right) \ left (x_3-x_1 \ right), ....., \ left (x_k-x_1 \ right) $ sont linéairement dépendants .

$ \ Rightarrow \ exists \ mu _j \ in \ mathbb {R}, 2 \ leq j \ leq k $ (pas tout zéro) tel que $ \ displaystyle \ sum \ limits_ {j = 2} ^ k \ mu _j \ left (x_j-x_1 \ droite) = 0 $

Définissez $ \ mu_1 = - \ displaystyle \ sum \ limits_ {j = 2} ^ k \ mu _j $, puis $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ mu_j x_j = 0, \ displaystyle \ sum \ limites_ {j = 1} ^ k \ mu_j = 0 $

où tous les $ de $ \ mu_j ne sont pas égaux à zéro. Puisque $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ mu_j = 0 $, au moins un des $ \ mu_j> 0,1 \ leq j \ leq k $

Ensuite, $ x = \ Displaystyle \ sum \ limits_ {1} ^ k \ lambda_j x_j + 0 $

$ x = \ displaystyle \ sum \ limits_ {1} ^ k \ lambda_j x_j- \ alpha \ displaystyle \ sum \ limits_ {1} ^ k \ mu_j x_j $

$ x = \ Displaystyle \ sum \ limits_ {1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) x_j $

Choisissez $ \ alpha $ tel que $ \ alpha = min \ left \ {\ frac {\ lambda_j} {\ mu_j}, \ mu_j \ geq 0 \ right \} = \ frac {\ lambda_j} {\ mu _j}, $ pour certains $ i = 1,2, ..., k $

Si $ \ mu_j \ leq 0, \ lambda_j- \ alpha \ mu_j \ geq 0 $

Si $ \ mu_j> 0, alors \: \ frac {\ lambda _j} {\ mu_j} \ geq \ frac {\ lambda_i} {\ mu _i} = \ alpha \ Rightarrow \ lambda_j- \ alpha \ mu_j \ geq 0, j = 1,2, ... k $

En particulier, $ \ lambda_i- \ alpha \ mu_i = 0 $, par définition de $ \ alpha $

$ x = \ Displaystyle \ sum \ limits_ {j = 1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) x_j $, où

$ \ lambda_j- \ alpha \ mu_j \ geq0 $ et $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) = 1 $ et $ \ lambda_i- \ alpha \ mu_i = 0 $

Ainsi, x peut être représenté comme une combinaison convexe d'au plus (k-1) points.

Ce processus de réduction peut être répété jusqu'à ce que x soit représenté comme une combinaison convexe de (n + 1) éléments.

Soit S un ensemble non vide, fermé et borné (également appelé ensemble compact) dans $ \ mathbb {R} ^ n $ et soit $ f: S \ rightarrow \ mathbb {R} $ une fonction continue sur S, alors le problème min $ \ left \ {f \ left (x \ right): x \ in S \ right \} $ atteint son minimum.

Preuve

Puisque S est non vide et borné, il existe une borne inférieure.

$ \ alpha = Inf \ left \ {f \ left (x \ right): x \ in S \ right \} $

Soit maintenant $ S_j = \ left \ {x \ in S: \ alpha \ leq f \ left (x \ right) \ leq \ alpha + \ delta ^ j \ right \} \ forall j = 1,2, ... $ et $ \ delta \ in \ left (0,1 \ right) $

Par la définition d'infimium, $ S_j $ est non vide, pour chaque $ j $.

Choisissez des $ x_j \ dans S_j $ pour obtenir une séquence $ \ left \ {x_j \ right \} $ pour $ j = 1,2, ... $

Puisque S est borné, la séquence est également bornée et il existe une sous-séquence convergente $ \ left \ {y_j \ right \} $, qui converge vers $ \ hat {x} $. Donc $ \ hat {x} $ est un point limite et S est fermé, donc $ \ hat {x} \ dans S $. Puisque f est continue, $ f \ left (y_i \ right) \ rightarrow f \ left (\ hat {x} \ right) $.

Depuis $ \ alpha \ leq f \ left (y_i \ right) \ leq \ alpha + \ delta ^ k, \ alpha = \ displaystyle \ lim_ {k \ rightarrow \ infty} f \ left (y_i \ right) = f \ left ( \ hat {x} \ right) $

Ainsi, $ \ hat {x} $ est la solution de minimisation.

Remarques

Il y a deux conditions nécessaires importantes pour que le théorème de Weierstrass se vérifie. Ce sont les suivants -

• Step 1 - L'ensemble S doit être un ensemble borné.

  Considérez la fonction f \ left (x \ right) = x $.

  C'est un ensemble illimité et il a des minima à tout moment dans son domaine.

  Ainsi, pour que les minima soient obtenus, S doit être borné.

• Step 2 - L'ensemble S doit être fermé.

  Considérons la fonction $ f \ left (x \ right) = \ frac {1} {x} $ dans le domaine \ left (0,1 \ right).

  Cette fonction n'est pas fermée dans le domaine donné et ses minima n'existent pas non plus.

  Par conséquent, pour que les minima soient obtenus, S doit être fermé.

Soit S un ensemble convexe fermé non vide dans $ \ mathbb {R} ^ n $ et soit $ y \ notin S $, alors $ \ existe $ un point $ \ bar {x} \ dans S $ avec une distance minimale de y, c'est-à-dire $ \ gauche \ | y- \ bar {x} \ droit \ | \ leq \ gauche \ | yx \ droite \ | \ forall x \ dans S. $

De plus, $ \ bar {x} $ est un point de minimisation si et seulement si $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ ou $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Preuve

Existence du point le plus proche

Puisque $ S \ ne \ phi, \ existe $ un point $ \ hat {x} \ dans S $ tel que la distance minimale de S à partir de y soit inférieure ou égale à $ \ left \ | y- \ hat {x} \ right \ | $.

Définissez $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ droite \ | \ leq \ gauche \ | y- \ hat {x} \ right \ | \ droite \} $

Puisque $ \ hat {S} $ est fermé et borné, et que la norme est une fonction continue, alors par le théorème de Weierstrass, il existe un point minimum $ \ hat {x} \ dans S $ tel que $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Unicité

Supposons $ \ bar {x} \ in S $ tel que $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Puisque S est convexe, $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Mais, $ \ gauche \ | y- \ frac {\ hat {x} - \ bar {x}} {2} \ right \ | \ leq \ frac {1} {2} \ left \ | y- \ hat {x} \ right \ | + \ frac {1} {2} \ left \ | y- \ bar {x} \ right \ | = \ alpha $

Cela ne peut pas être une inégalité stricte car $ \ hat {x} $ est le plus proche de y.

Par conséquent, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, pour quelques $ \ mu $

Maintenant $ \ left \ | \ mu \ right \ | = 1. $ Si $ \ mu = -1 $, alors $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Flèche droite y = \ frac {\ hat {x} + \ bar {x}} {2} \ en S $

Mais $ y \ dans S $. D'où la contradiction. Ainsi $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Ainsi, minimiser le point est unique.

Pour la deuxième partie de la preuve, supposons $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ pour tout $ x \ en S $

Maintenant,

$ \ gauche \ | yx \ droite \ | ^ {2} = \ gauche \ | y- \ hat {x} + \ hat {x} -x \ right \ | ^ {2} = \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ left \ | \ hat {x} -x \ right \ | ^ {2} +2 \ left (\ hat {x} -x \ right) ^ {\ tau} \ left (y- \ hat {x} \ right) $

$ \ Flèche droite \ gauche \ | yx \ droite \ | ^ {2} \ geq \ gauche \ | y- \ hat {x} \ right \ | ^ {2} $ car $ \ left \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ et $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Ainsi, $ \ hat {x} $ minimise le point.

Inversement, supposons que $ \ hat {x} $ est un point de minimisation.

$ \ Flèche droite \ gauche \ | yx \ droite \ | ^ {2} \ geq \ gauche \ | y- \ hat {x} \ right \ | ^ 2 \ forall x \ in S $

Puisque S est un ensemble convexe.

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ right) \ in S $ pour $ x \ in S $ et $ \ lambda \ in \ left (0,1 \ right) $

Maintenant, $ \ left \ | y- \ hat {x} - \ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ 2 $

Et

$ \ gauche \ | y- \ hat {x} - \ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} = \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ lambda ^ 2 \ left \ | x- \ hat {x} \ right \ | ^ {2} -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) $

$ \ Flèche droite \ gauche \ | y- \ hat {x} \ right \ | ^ {2} + \ lambda ^ {2} \ left \ | x- \ hat {x} \ right \ | -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ geq \ left \ | y- \ hat {x} \ right \ | ^ {2} $

$ \ Rightarrow 2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq \ lambda ^ 2 \ left \ | x- \ hat {x} \ right \ | ^ 2 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $

D'où prouvé.

Soit S un ensemble convexe fermé non vide dans $ \ mathbb {R} ^ n $ et $ y \ notin S $. Alors, il existe un vecteur non nul $ p $ et scalaire $ \ beta $ tel que $ p ^ T y> \ beta $ et $ p ^ T x <\ beta $ pour chaque $ x \ dans S $

Preuve

Puisque S est un ensemble convexe fermé non vide et $ y \ notin S $ donc par le théorème du point le plus proche, il existe un point de minimisation unique $ \ hat {x} \ dans S $ tel que

$ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 \ forall x \ in S $

Soit $ p = \ left (y- \ hat {x} \ right) \ neq 0 $ et $ \ beta = \ hat {x} ^ T \ left (y- \ hat {x} \ right) = p ^ T \ chapeau {x} $.

Puis $ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ T \ left (x- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ Tx \ leq \ left (y- \ hat {x} \ right) ^ T \ hat {x} = \ hat {x} ^ T \ left (y- \ hat {x} \ right) $ i, e., $ p ^ Tx \ leq \ beta $

De plus, $ p ^ Ty- \ beta = \ left (y- \ hat {x} \ right) ^ Ty- \ hat {x} ^ T \ left (y- \ hat {x} \ right) $

$ = \ left (y- \ hat {x} \ right) ^ T \ left (yx \ right) = \ left \ | y- \ hat {x} \ right \ | ^ {2}> 0 $

$ \ Rightarrow p ^ Ty> \ beta $

Ce théorème conduit à séparer les hyperplans. Les hyperplans basés sur le théorème ci-dessus peuvent être définis comme suit -

Soit $ S_1 $ et $ S_2 $ des sous-ensembles non vides de $ \ mathbb {R} $ et $ H = \ left \ {X: A ^ TX = b \ right \} $ être un hyperplan.

• On dit que l'hyperplan H sépare $ S_1 $ et $ S_2 $ si $ A ^ TX \ leq b \ forall X \ in S_1 $ et $ A_TX \ geq b \ forall X \ in S_2 $

• On dit que l'hyperplan H sépare strictement $ S_1 $ et $ S_2 $ si $ A ^ TX <b \ forall X \ in S_1 $ et $ A_TX> b \ forall X \ in S_2 $

• On dit que l'hyperplan H sépare fortement $ S_1 $ et $ S_2 $ if $ A ^ TX \ leq b \ forall X \ in S_1 $ et $ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $, où $ \ varepsilon $ est un scalaire positif.

Un ensemble non vide C dans $ \ mathbb {R} ^ n $ est dit cône de sommet 0 si $ x \ in C \ Rightarrow \ lambda x \ in C \ forall \ lambda \ geq 0 $.

Un ensemble C est un cône convexe s'il est convexe aussi bien qu'un cône.

Par exemple, $ y = \ left | x \ right | $ n'est pas un cône convexe car il n'est pas convexe.

Mais, $ y \ geq \ left | x \ right | $ est un cône convexe car il est aussi bien convexe qu'un cône.

Note - Un cône C est convexe si et seulement si pour tout $ x, y \ en C, x + y \ en C $.

Preuve

Puisque C est un cône, pour $ x, y \ dans C \ Rightarrow \ lambda x \ dans C $ et $ \ mu y \ dans C \: \ forall \: \ lambda, \ mu \ geq 0 $

C est convexe si $ \ lambda x + \ left (1- \ lambda \ right) y \ in C \: \ forall \: \ lambda \ in \ left (0, 1 \ right) $

Puisque C est un cône, $ \ lambda x \ en C $ et $ \ left (1- \ lambda \ right) y \ en C \ Leftrightarrow x, y \ en C $

Ainsi C est convexe si $ x + y \ dans C $

En général, si $ x_1, x_2 \ dans C $, alors, $ \ lambda_1x_1 + \ lambda_2x_2 \ in C, \ forall \ lambda_1, \ lambda_2 \ geq 0 $

Exemples

• La combinaison conique d'un ensemble infini de vecteurs dans $ \ mathbb {R} ^ n $ est un cône convexe.

• Tout ensemble vide est un cône convexe.

• Toute fonction linéaire est un cône convexe.

• Puisqu'un hyperplan est linéaire, c'est aussi un cône convexe.

• Les demi-espaces fermés sont également des cônes convexes.

Note - L'intersection de deux cônes convexes est un cône convexe mais leur union peut ou non être un cône convexe.

Soit S un ensemble non vide dans $ \ mathbb {R} ^ n $ Alors, le cône polaire de S noté $ S ^ * $ est donné par $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Remarque

• Le cône polaire est toujours convexe même si S n'est pas convexe.

• Si S est un ensemble vide, $ S ^ * = \ mathbb {R} ^ n $.

• La polarité peut être vue comme une généralisation de l'orthogonalité.

Soit $ C \ subseteq \ mathbb {R} ^ n $ alors l'espace orthogonal de C, noté $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Lemme

Soit $ S, S_1 $ et $ S_2 $ des ensembles non vides dans $ \ mathbb {R} ^ n $ alors les déclarations suivantes sont vraies -

• $ S ^ * $ est un cône convexe fermé.

• $ S \ subseteq S ^ {**} $ où $ S ^ {**} $ est un cône polaire de $ S ^ * $.

• $ S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*} $.

Preuve

Step 1 - $ S ^ * = \ left \ {p \ in \ mathbb {R} ^ n, p ^ Tx \ leq 0 \: \ forall \: x \ in S \ right \} $

• Soit $ x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $ et $ x_ {2} ^ {T} x \ leq 0, \ forall x \ in S $

  Pour $ \ lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ right) ) ^ T + \ left \ {\ left (1- \ lambda \ right) x_ {2} \ right \} ^ {T} \ right] x, \ forall x \ in S $

  $ = \ left [\ lambda x_ {1} ^ {T} + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ gauche (1- \ lambda \ droite) x_ {2} ^ {T} \ leq 0 $

  Ainsi $ \ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \ in S ^ * $

  Donc $ S ^ * $ est un ensemble convexe.

• Pour $ \ lambda \ geq 0, p ^ {T} x \ leq 0, \ forall \: x \ in S $

  Par conséquent, $ \ lambda p ^ T x \ leq 0, $

  $ \ Flèche droite \ gauche (\ lambda p \ droite) ^ T x \ leq 0 $

  $ \ Rightarrow \ lambda p \ dans S ^ * $

  Ainsi, $ S ^ * $ est un cône.

• Montrer que $ S ^ * $ est fermé, c'est-à-dire montrer si $ p_n \ rightarrow p $ comme $ n \ rightarrow \ infty $, alors $ p \ dans S ^ * $

  $ \ forall x \ in S, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ right) ^ T x $

  Comme $ p_n \ rightarrow p $ comme $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

  Donc $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $. Mais $ p_ {n} ^ {T} x \ leq 0, \: \ forall x \ in S $

  Ainsi, $ p ^ Tx \ leq 0, \ forall x \ in S $

  $ \ Flèche droite p \ dans S ^ * $

  Par conséquent, $ S ^ * $ est fermé.

Step 2 - $ S ^ {**} = \ left \ {q \ in \ mathbb {R} ^ n: q ^ T p \ leq 0, \ forall p \ in S ^ * \ right \} $

Soit $ x \ dans S $, puis $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Ainsi, $ S \ subseteq S ^ {**} $

Step 3 - $ S_2 ^ * = \ left \ {p \ in \ mathbb {R} ^ n: p ^ Tx \ leq 0, \ forall x \ in S_2 \ right \} $

Depuis $ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1 $

Donc, si $ \ hat {p} \ in S_2 ^ *, $ alors $ \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_2 $

$ \ Rightarrow \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_1 $

$ \ Rightarrow \ hat {p} ^ T \ dans S_1 ^ * $

$ \ Rightarrow S_2 ^ * \ subseteq S_1 ^ * $

Théorème

Soit C un cône convexe fermé non vide, alors $ C = C ^ ** $

Preuve

$ C = C ^ {**} $ par le lemme précédent.

Pour prouver: $ x \ in C ^ {**} \ subseteq C $

Soit $ x \ in C ^ {**} $ et soit $ x \ notin C $

Alors par théorème de séparation fondamental, il existe un vecteur $ p \ neq 0 $ et un scalaire $ \ alpha $ tel que $ p ^ Ty \ leq \ alpha, \ forall y \ dans C $

Par conséquent, $ p ^ Tx> \ alpha $

Mais puisque $ \ left (y = 0 \ right) \ en C $ et $ p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0 $ et $ p ^ Tx> 0 $

Si $ p \ notin C ^ * $, alors il existe des $ \ bar {y} \ dans C $ tels que $ p ^ T \ bar {y}> 0 $ et $ p ^ T \ left (\ lambda \ bar {y} \ right) $ peut être rendu arbitrairement grand en prenant $ \ lambda $ suffisamment grand.

Cela contredit le fait que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Par conséquent, $ p \ dans C ^ * $

Puisque $ x \ in C ^ * = \ left \ {q: q ^ Tp \ leq 0, \ forall p \ in C ^ * \ right \} $

Par conséquent, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Mais $ p ^ Tx> \ alpha $

Ainsi est la contardiction.

Ainsi, $ x \ en C $

D'où $ C = C ^ {**} $.

Un point de la forme $ \ alpha_1x_1 + \ alpha_2x_2 + .... + \ alpha_nx_n $ avec $ \ alpha_1, \ alpha_2, ..., \ alpha_n \ geq 0 $ est appelé combinaison conique de $ x_1, x_2, ..., x_n. $

• Si $ x_i $ sont dans le cône convexe C, alors chaque combinaison conique de $ x_i $ est également dans C.

• Un ensemble C est un cône convexe s'il contient toute la combinaison conique de ses éléments.

Coque conique

Une coque conique est définie comme un ensemble de toutes les combinaisons coniques d'un ensemble donné S et est désignée par coni (S).

Ainsi, $ coni \ left (S \ right) = \ left \ {\ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i: x_i \ in S, \ lambda_i \ in \ mathbb {R}, \ lambda_i \ geq 0, i = 1,2, ... \ right \} $

• La coque conique est un ensemble convexe.
• L'origine appartient toujours à la coque conique.

Un ensemble dans $ \ mathbb {R} ^ n $ est dit polyédrique s'il est l'intersection d'un nombre fini de demi-espaces fermés, ie,

$ S = \ left \ {x \ in \ mathbb {R} ^ n: p_ {i} ^ {T} x \ leq \ alpha_i, i = 1,2, ...., n \ right \} $

Par exemple,

• $ \ left \ {x \ in \ mathbb {R} ^ n: AX = b \ right \} $

• $ \ left \ {x \ in \ mathbb {R} ^ n: AX \ leq b \ right \} $

• $ \ left \ {x \ in \ mathbb {R} ^ n: AX \ geq b \ right \} $

Cône polyédrique

Un ensemble dans $ \ mathbb {R} ^ n $ est dit cône polyédrique s'il est l'intersection d'un nombre fini de demi-espaces contenant l'origine, c'est-à-dire $ S = \ left \ {x \ in \ mathbb { R} ^ n: p_ {i} ^ {T} x \ leq 0, i = 1, 2, ... \ right \} $

Polytope

Un polytope est un ensemble polyédrique qui est borné.

Remarques

• Un polytope est une coque convexe d'un ensemble fini de points.
• Un cône polyédrique est généré par un ensemble fini de vecteurs.
• Un ensemble polyédrique est un ensemble fermé.
• Un ensemble polyédrique est un ensemble convexe.

Soit S un ensemble convexe dans $ \ mathbb {R} ^ n $. On dit qu'un vecteur $ x \ dans S $ est un point extrême de S si $ x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ avec $ x_1, x_2 \ in S $ et $ \ lambda \ dans \ left (0, 1 \ right) \ Rightarrow x = x_1 = x_2 $.

Exemple

Step 1 - $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 1 \ right \ } $

Point extrême, $ E = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} + x_ {2} ^ {2} = 1 \ right \} $

Step 2 - $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_1 + x_2 <2, -x_1 + 2x_2 \ leq 2, x_1, x_2 \ geq 0 \ right \ } $

Point extrême, $ E = \ left \ {\ left (0, 0 \ right), \ left (2, 0 \ right), \ left (0, 1 \ right), \ left (\ frac {2} {3 }, \ frac {4} {3} \ right) \ right \} $

Step 3 - S est le polytope formé par les points $ \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2, 4 \ droite), \ gauche (0,2 \ droite) \ droite \} $

Point extrême, $ E = \ gauche \ {\ gauche (0,0 \ droite), \ gauche (1,1 \ droite), \ gauche (1,3 \ droite), \ gauche (-2,4 \ droite) \ droite \} $

Remarques

• Tout point de l'ensemble convexe S peut être représenté comme une combinaison convexe de ses points extrêmes.

• Ce n'est vrai que pour les ensembles fermés et bornés dans $ \ mathbb {R} ^ n $.

• Cela peut ne pas être vrai pour les ensembles illimités.

k points extrêmes

Un point dans un ensemble convexe est appelé k extrême si et seulement si c'est le point intérieur d'un ensemble convexe à k dimensions dans S, et ce n'est pas un point intérieur d'un ensemble convexe à (k + 1) dimensions dans S. Fondamentalement, pour un ensemble convexe S, k points extrêmes forment des faces ouvertes de k dimensions.

Soit S un ensemble convexe fermé dans $ \ mathbb {R} ^ n $. Un vecteur non nul $ d \ in \ mathbb {R} ^ n $ est appelé une direction de S si pour chaque $ x \ dans S, x + \ lambda d \ dans S, \ forall \ lambda \ geq 0. $

• Deux directions $ d_1 $ et $ d_2 $ de S sont dites distinctes si $ d \ neq \ alpha d_2 $ pour $ \ alpha> 0 $.

• Une direction $ d $ de $ S $ est dite direction extrême si elle ne peut pas être écrite comme une combinaison linéaire positive de deux directions distinctes, c'est-à-dire si $ d = \ lambda _1d_1 + \ lambda _2d_2 $ pour $ \ lambda _1, \ lambda _2> 0 $, puis $ d_1 = \ alpha d_2 $ pour quelques $ \ alpha $.

• Toute autre direction peut être exprimée comme une combinaison positive de directions extrêmes.

• Pour un ensemble convexe $ S $, la direction d telle que $ x + \ lambda d \ dans S $ pour certains $ x \ dans S $ et tout $ \ lambda \ geq0 $ est appelée recessive pour $ S $.

• Soit E l'ensemble des points où une certaine fonction $ f: S \ rightarrow $ sur un ensemble convexe non vide S dans $ \ mathbb {R} ^ n $ atteint son maximum, alors $ E $ est appelé face exposée de $ S $. Les directions des faces exposées sont appelées directions exposées.

• Un rayon dont la direction est une direction extrême est appelé un rayon extrême.

Exemple

Considérons la fonction $ f \ left (x \ right) = y = \ left | x \ right | $, où $ x \ in \ mathbb {R} ^ n $. Soit d un vecteur unitaire dans $ \ mathbb {R} ^ n $

Alors, d est la direction de la fonction f car pour tout $ \ lambda \ geq 0, x + \ lambda d \ in f \ left (x \ right) $.

Soit $ f: S \ rightarrow \ mathbb {R} $, où S est un convexe non vide défini dans $ \ mathbb {R} ^ n $, alors $ f \ left (x \ right) $ est dit convexe sur S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left ( x_2 \ right), \ forall \ lambda \ in \ left (0,1 \ right) $.

Par contre, Soit $ f: S \ rightarrow \ mathbb {R} $, où S est un convexe non vide défini dans $ \ mathbb {R} ^ n $, alors $ f \ left (x \ right) $ est dit être concave sur S si $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ geq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) ) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Soit $ f: S \ rightarrow \ mathbb {R} $ où S est un convexe non vide défini dans $ \ mathbb {R} ^ n $, alors $ f \ left (x \ right) $ est dit strictement convexe sur S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) <\ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Soit $ f: S \ rightarrow \ mathbb {R} $ où S est un convexe non vide défini dans $ \ mathbb {R} ^ n $, alors $ f \ left (x \ right) $ est dit strictement concave sur S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right)> \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Exemples

• Une fonction linéaire est à la fois convexe et concave.

• $ f \ gauche (x \ droite) = \ gauche | x \ right | $ est une fonction convexe.

• $ f \ left (x \ right) = \ frac {1} {x} $ est une fonction convexe.

Théorème

Soit $ f_1, f_2, ..., f_k: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ des fonctions convexes. Considérons la fonction $ f \ left (x \ right) = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_jf_j \ left (x \ right) $ où $ \ alpha_j> 0, j = 1, 2,. ..k, $ puis $ f \ left (x \ right) $ est une fonction convexe.

Preuve

Puisque $ f_1, f_2, ... f_k $ sont des fonctions convexes

Par conséquent, $ f_i \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f_i \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_i \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $ et $ i = 1, 2, ...., k $

Considérons la fonction $ f \ left (x \ right) $.

Par conséquent,

$ f \ gauche (\ lambda x_1 + \ gauche (1- \ lambda \ droite) x_2 \ droite) $

$ = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_jf_j \ left (\ lambda x_1 + 1- \ lambda \ right) x_2 \ leq \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_j \ lambda f_j \ gauche (x_1 \ droite) + \ gauche (1- \ lambda \ droite) f_j \ gauche (x_2 \ droite) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda \ left (\ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha _jf_j \ left ( x_1 \ right) \ right) + \ left (\ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha _jf_j \ left (x_2 \ right) \ right) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_2 \ right) \ leq \ left (1- \ lambda \ right) f \ gauche (x_2 \ droite) $

Par conséquent, $ f \ left (x \ right) $ est une fonction convexe.

Théorème

Soit $ f \ left (x \ right) $ une fonction convexe sur un ensemble convexe $ S \ subset \ mathbb {R} ^ n $ alors un minimum local de $ f \ left (x \ right) $ sur S est un minima globaux.

Preuve

Soit $ \ hat {x} $ un minimum local pour $ f \ left (x \ right) $ et $ \ hat {x} $ n'est pas un minimum global.

donc $ \ existe \ hat {x} \ in S $ tel que $ f \ left (\ bar {x} \ right) <f \ left (\ hat {x} \ right) $

Puisque $ \ hat {x} $ est un minimum local, il existe un voisinage $ N_ \ varepsilon \ left (\ hat {x} \ right) $ tel que $ f \ left (\ hat {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $

But $f\left ( x \right )$ is a convex function on S, therefore for $\lambda \in \left ( 0, 1 \right )$

we have $\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}\leq \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left ( \bar{x} \right )$

$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left (\hat{x} \right )$

$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< f\left (\hat{x} \right ), \forall \lambda \in \left ( 0,1 \right )$

But for some $\lambda<1$ but close to 1, we have

$\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \in N_\varepsilon \left ( \hat{x} \right )\cap S$ and $f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )< f\left ( \bar{x} \right )$

which is a contradiction.

Hence, $\bar{x}$ is a global minima.

Epigraph

let S be a non-empty subset in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$ then the epigraph of f denoted by epi(f) or $E_f$ is a subset of $\mathbb{R}^n+1$ defined by $E_f=\left \{ \left ( x,\alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\leq \alpha \right \}$

Hypograph

let S be a non-empty subset in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$, then the hypograph of f denoted by hyp(f) or $H_f=\left \{ \left ( x, \alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\geq \alpha \right \}$

Theorem

Let S be a non-empty convex set in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}^n$, then f is convex if and only if its epigraph $E_f$ is a convex set.

Proof

Let f is a convex function.

To show $E_f$ is a convex set.

Let $\left ( x_1, \alpha_1 \right ),\left ( x_2, \alpha_2 \right ) \in E_f,\lambda \in\left ( 0, 1 \right )$

To show $\lambda \left ( x_1,\alpha_1 \right )+\left ( 1-\lambda \right )\left ( x_2, \alpha_2 \right ) \in E_f$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2 \right ]\in E_f$

$f\left ( x_1 \right )\leq \alpha _1, f\left ( x_2\right )\leq \alpha _2$

Therefore, $f\left (\lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f \left ( x_2 \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2$

Converse

Let $E_f$ is a convex set.

To show f is convex.

i.e., to show if $x_1, x_2 \in S,\lambda \left ( 0, 1\right )$

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Let $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right ),f\left ( x_1 \right ), f\left ( x_2 \right ) \in \mathbb{R}$

Since $E_f$ is a convex set, $\left ( \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )\right )f\left ( x_2 \right )\in E_f$

Therefore, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Let S be a non-empty convex set in $\mathbb{R}^n$ and $f:S \rightarrow \mathbb{R}^n$. Then f is convex if and only if for each integer $k>0$

$x_1,x_2,...x_k \in S, \displaystyle\sum\limits_{i=1}^k \lambda_i=1, \lambda_i\geq 0, \forall i=1,2,s,k$, we have $f\left ( \displaystyle\sum\limits_{i=1}^k \lambda_ix_i \right )\leq \displaystyle\sum\limits_{i=1}^k \lambda _if\left ( x \right )$

Proof

By induction on k.

$k=1:x_1 \in S$ Therefore $f\left ( \lambda_1 x_1\right ) \leq \lambda_i f\left (x_1\right )$ because $\lambda_i=1$.

$k=2:\lambda_1+\lambda_2=1$ and $x_1, x_2 \in S$

Therefore, $\lambda_1x_1+\lambda_2x_2 \in S$

Hence by definition, $f\left ( \lambda_1 x_1 +\lambda_2 x_2 \right )\leq \lambda _1f\left ( x_1 \right )+\lambda _2f\left ( x_2 \right )$

Let the statement is true for $n < k$

Therefore,

$f\left ( \lambda_1 x_1+ \lambda_2 x_2+....+\lambda_k x_k\right )\leq \lambda_1 f\left (x_1 \right )+\lambda_2 f\left (x_2 \right )+...+\lambda_k f\left (x_k \right )$

$k=n+1:$ Let $x_1, x_2,....x_n,x_{n+1} \in S$ and $\displaystyle\sum\limits_{i=1}^{n+1}=1$

Therefore $\mu_1x_1+\mu_2x_2+.......+\mu_nx_n+\mu_{n+1} x_{n+1} \in S$

thus,$f\left (\mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1} x_{n+1} \right )$

$=f\left ( \left ( \mu_1+\mu_2+...+\mu_n \right)\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+\mu_3}+\mu_{n+1}x_{n+1} \right)$

$=f\left ( \mu_y+\mu_{n+1}x_{n+1} \right )$ where $\mu=\mu_1+\mu_2+...+\mu_n$ and

$y=\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n}$ and also $\mu_1+\mu_{n+1}=1,y \in S$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq \mu f\left ( y \right )+\mu_{n+1} f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq$

$\left ( \mu_1+\mu_2+...+\mu_n \right )f\left ( \frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n} \right )+\mu_{n+1}f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n +\mu_{n+1}x_{n+1}\right )\leq \left ( \mu_1+ \mu_2+ ...+\mu_n \right )$

$\left [ \frac{\mu_1}{\mu_1+ \mu_2+ ...+\mu_n}f\left ( x_1 \right )+...+\frac{\mu_n}{\mu_1+ \mu_2+ ...+\mu_n}f\left ( x_n \right ) \right ]+\mu_{n+1}f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right )\leq \mu_1f\left ( x_1 \right )+\mu_2f\left ( x_2 \right )+....$

Hence Proved.

Let S be a non-empty open set in $\mathbb{R}^n$,then $f:S\rightarrow \mathbb{R}$ is said to be differentiable at $\hat{x} \in S$ if there exist a vector $\bigtriangledown f\left ( \hat{x} \right )$ called gradient vector and a function $\alpha :\mathbb{R}^n\rightarrow \mathbb{R}$ such that

$f\left ( x \right )=f\left ( \hat{x} \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x-\hat{x} \right )+\left \| x=\hat{x} \right \|\alpha \left ( \hat{x}, x-\hat{x} \right ), \forall x \in S$ where

$\alpha \left (\hat{x}, x-\hat{x} \right )\rightarrow 0 \bigtriangledown f\left ( \hat{x} \right )=\left [ \frac{\partial f}{\partial x_1}\frac{\partial f}{\partial x_2}...\frac{\partial f}{\partial x_n} \right ]_{x=\hat{x}}^{T}$

Theorem

let S be a non-empty, open convexset in $\mathbb{R}^n$ and let $f:S\rightarrow \mathbb{R}$ be differentiable on S. Then, f is convex if and only if for $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f\left ( x_2 \right )$

Proof

Let f be a convex function. i.e., for $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right )$

$f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

$ \Rightarrow f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )+f\left ( x_2 \right )$

$ \Rightarrow\lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2+\lambda \left ( x_1-x_2 \right ) \right )-f\left ( x_2 \right )$

$\Rightarrow \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\lambda +$

$\left \| \lambda \left ( x_1-x_2 \right ) \right \|\alpha \left ( x_2,\lambda\left (x_1 - x_2 \right )-f\left ( x_2 \right ) \right )$

where $\alpha\left ( x_2, \lambda\left (x_1 - x_2 \right ) \right )\rightarrow 0$ as$\lambda \rightarrow 0$

Dividing by $\lambda$ on both sides, we get −

$f\left ( x_1 \right )-f\left ( x_2 \right ) \geq \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right )$

Converse

Let for $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f \left ( x_2 \right )$

To show that f is convex.

Since S is convex, $x_3=\lambda x_1+\left (1-\lambda \right )x_2 \in S, \lambda \in \left ( 0, 1 \right )$

Since $x_1, x_3 \in S$, therefore

$f\left ( x_1 \right )-f \left ( x_3 \right ) \geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 -x_3\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - \lambda x_1-\left (1-\lambda \right )x_2\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \left ( 1- \lambda\right )\bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - x_2\right )$

Since, $x_2, x_3 \in S$ therefore

$f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-\lambda x_1-\left ( 1-\lambda \right )x_2 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \left ( -\lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )$

Thus, combining the above equations, we get −

$\lambda \left ( f\left ( x_1 \right )-f\left ( x_3 \right ) \right )+\left ( 1- \lambda \right )\left ( f\left ( x_2 \right )-f\left ( x_3 \right ) \right )\geq 0$

$\Rightarrow f\left ( x_3\right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Theorem

let S be a non-empty open convex set in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$ be differentiable on S, then f is convex on S if and only if for any $x_1,x_2 \in S,\left ( \bigtriangledown f \left ( x_2 \right )-\bigtriangledown f \left ( x_1 \right ) \right )^T \left ( x_2-x_1 \right ) \geq 0$

Proof

let f be a convex function, then using the previous theorem −

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\leq f\left ( x_1 \right )-f\left ( x_2 \right )$ and

$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

Adding the above two equations, we get −

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_2-x_1 \right )\geq 0$

Converse

Let for any $x_1,x_2 \in S,\left (\bigtriangledown f \left ( x_2\right )- \bigtriangledown f \left ( x_1\right )\right )^T \left ( x_2-x_1\right )\geq 0$

To show that f is convex.

Let $x_1,x_2 \in S$, thus by mean value theorem, $\frac{f\left ( x_1\right )-f\left ( x_2\right )}{x_1-x_2}=\bigtriangledown f\left ( x\right ),x \in \left ( x_1-x_2\right ) \Rightarrow x= \lambda x_1+\left ( 1-\lambda\right )x_2$ because S is a convex set.

$\Rightarrow f\left ( x_1 \right )- f\left ( x_2 \right )=\left ( \bigtriangledown f\left ( x \right )^T \right )\left ( x_1-x_2 \right )$

for $x,x_1$, we know −

$\left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( \lambda x_1+\left ( 1-\lambda \right )x_2-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )- \bigtriangledown f\left ( x_1 \right )\right )^T\left ( 1- \lambda \right )\left ( x_2-x_1 \right )\geq 0$

$\Rightarrow \bigtriangledown f\left ( x \right )^T\left ( x_2-x_1 \right )\geq \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )$

Combining the above equations, we get −

$\Rightarrow \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

Hence using the last theorem, f is a convex function.

Twice Differentiable function

Let S be a non-empty subset of $\mathbb{R}^n$ and let $f:S\rightarrow \mathbb{R}$ then f is said to be twice differentiable at $\bar{x} \in S$ if there exists a vector $\bigtriangledown f\left (\bar{x}\right ), a \:nXn$ matrix $H\left (x\right )$(called Hessian matrix) and a function $\alpha:\mathbb{R}^n \rightarrow \mathbb{R}$ such that $f\left ( x \right )=f\left ( \bar{x}+x-\bar{x} \right )=f\left ( \bar{x} \right )+\bigtriangledown f\left ( \bar{x} \right )^T\left ( x-\bar{x} \right )+\frac{1}{2}\left ( x-\bar{x} \right )H\left ( \bar{x} \right )\left ( x-\bar{x} \right )$

where $ \alpha \left ( \bar{x}, x-\bar{x} \right )\rightarrow Oasx\rightarrow \bar{x}$

Theorem

Let f be twice differentiable function. If $\bar{x}$ is a local minima, then $\bigtriangledown f\left ( \bar{x} \right )=0$ and the Hessian matrix $H\left ( \bar{x} \right )$ is a positive semidefinite.

Proof

Let $d \in \mathbb{R}^n$. Since f is twice differentiable at $\bar{x}$.

Therefore,

$f\left ( \bar{x} +\lambda d\right )=f\left ( \bar{x} \right )+\lambda \bigtriangledown f\left ( \bar{x} \right )^T d+\lambda^2d^TH\left ( \bar{x} \right )d+\lambda^2d^TH\left ( \bar{x} \right )d+$

$\lambda^2\left \| d \right \|^2\beta \left ( \bar{x}, \lambda d \right )$

But $\bigtriangledown f\left ( \bar{x} \right )=0$ and $\beta\left ( \bar{x}, \lambda d \right )\rightarrow 0$ as $\lambda \rightarrow 0$

$\Rightarrow f\left ( \bar{x} +\lambda d \right )-f\left ( \bar{x} \right )=\lambda ^2d^TH\left ( \bar{x} \right )d$

Since $\bar{x }$ is a local minima, there exists a $\delta > 0$ such that $f\left ( x \right )\leq f\left ( \bar{x}+\lambda d \right ), \forall \lambda \in \left ( 0,\delta \right )$

Theorem

Let $f:S \rightarrow \mathbb{R}^n$ where $S \subset \mathbb{R}^n$ be twice differentiable over S. If $\bigtriangledown f\left ( x\right )=0$ and $H\left ( \bar{x} \right )$ is positive semi-definite, for all $x \in S$, then $\bar{x}$ is a global optimal solution.

Proof

Since $H\left ( \bar{x} \right )$ is positive semi-definite, f is convex function over S. Since f is differentiable and convex at $\bar{x}$

$\bigtriangledown f\left ( \bar{x} \right )^T \left ( x-\bar{x} \right ) \leq f\left (x\right )-f\left (\bar{x}\right ),\forall x \in S$

Since $\bigtriangledown f\left ( \bar{x} \right )=0, f\left ( x \right )\geq f\left ( \bar{x} \right )$

Hence, $\bar{x}$ is a global optima.

Theorem

Suppose $\bar{x} \in S$ is a local optimal solution to the problem $f:S \rightarrow \mathbb{R}$ where S is a non-empty subset of $\mathbb{R}^n$ and S is convex. $min \:f\left ( x \right )$ where $x \in S$.

Then:

• $\bar{x}$ is a global optimal solution.

• If either $\bar{x}$ is strictly local minima or f is strictly convex function, then $\bar{x}$ is the unique global optimal solution and is also strong local minima.

Proof

Let $\bar{x}$ be another global optimal solution to the problem such that $x \neq \bar{x}$ and $f\left ( \bar{x} \right )=f\left ( \hat{x} \right )$

Since $\hat{x},\bar{x} \in S$ and S is convex, then $\frac{\hat{x}+\bar{x}}{2} \in S$ and f is strictly convex.

$\Rightarrow f\left ( \frac{\hat{x}+\bar{x}}{2} \right )< \frac{1}{2} f\left (\bar{x}\right )+\frac{1}{2} f\left (\hat{x}\right )=f\left (\hat{x}\right )$

This is contradiction.

Hence, $\hat{x}$ is a unique global optimal solution.

Corollary

Let $f:S \subset \mathbb{R}^n \rightarrow \mathbb{R}$ be a differentiable convex function where $\phi \neq S\subset \mathbb{R}^n$ is a convex set. Consider the problem $min f\left (x\right ),x \in S$,then $\bar{x}$ is an optimal solution if $\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right ) \geq 0,\forall x \in S.$

Proof

Let $\bar{x}$ is an optimal solution, i.e, $f\left (\bar{x}\right )\leq f\left (x\right ),\forall x \in S$

$\Rightarrow f\left (x\right )=f\left (\bar{x}\right )\geq 0$

$f\left (x\right )=f\left (\bar{x}\right )+\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right )+\left \| x-\bar{x} \right \|\alpha \left ( \bar{x},x-\bar{x} \right )$

where $\alpha \left ( \bar{x},x-\bar{x} \right )\rightarrow 0$ as $x \rightarrow \bar{x}$

$\Rightarrow f\left (x\right )-f\left (\bar{x}\right )=\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right )\geq 0$

Corollary

Let f be a differentiable convex function at $\bar{x}$,then $\bar{x}$ is global minimum iff $\bigtriangledown f\left (\bar{x}\right )=0$

Examples

• $f\left (x\right )=\left (x^2-1\right )^{3}, x \in \mathbb{R}$.

  $\bigtriangledown f\left (x\right )=0 \Rightarrow x= -1,0,1$.

  $\bigtriangledown^2f\left (\pm 1 \right )=0, \bigtriangledown^2 f\left (0 \right )=6>0$.

  $f\left (\pm 1 \right )=0,f\left (0 \right )=-1$

  Hence, $f\left (x \right ) \geq -1=f\left (0 \right )\Rightarrow f\left (0 \right ) \leq f \left (x \right)\forall x \in \mathbb{R}$

• $f\left (x \right )=x\log x$ defined on $S=\left \{ x \in \mathbb{R}, x> 0 \right \}$.

  ${f}'x=1+\log x$

  ${f}''x=\frac{1}{x}>0$

  Thus, this function is strictly convex.

• $f \left (x \right )=e^{x},x \in \mathbb{R}$ is strictly convex.

Let $f:S \rightarrow \mathbb{R}$ where $S \subset \mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1,x_2 \in S$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq max\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \},\lambda \in \left ( 0, 1 \right )$

For example, $f\left ( x \right )=x^{3}$

Let $f:S\rightarrow R $ where $S\subset \mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1, x_2 \in S$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\geq min\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}, \lambda \in \left ( 0, 1 \right )$

Remarks

• Every convex function is quasiconvex but the converse is not true.
• A function which is both quasiconvex and quasiconcave is called quasimonotone.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasiconvex if and only if $S_{\alpha} =\left ( x \in S:f\left ( x \right )\leq \alpha \right \}$ is convex for each real number \alpha$

Proof

Let f is quasiconvex on S.

Let $x_1,x_2 \in S_{\alpha}$ therefore $x_1,x_2 \in S$ and $max \left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}\leq \alpha$

Let $\lambda \in \left (0, 1 \right )$ and let $x=\lambda x_1+\left ( 1-\lambda \right )x_2\leq max \left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}\Rightarrow x \in S$

Thus, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq max\left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}\leq \alpha$

Therefore, $S_{\alpha}$ is convex.

Converse

Let $S_{\alpha}$ is convex for each $\alpha$

$x_1,x_2 \in S, \lambda \in \left ( 0,1\right )$

$x=\lambda x_1+\left ( 1-\lambda \right )x_2$

Let $x=\lambda x_1+\left ( 1-\lambda \right )x_2$

For $x_1, x_2 \in S_{\alpha}, \alpha= max \left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}$

$\Rightarrow \lambda x_1+\left (1-\lambda \right )x_2 \in S_{\alpha}$

$\Rightarrow f \left (\lambda x_1+\left (1-\lambda \right )x_2 \right )\leq \alpha$

Hence proved.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasiconcave if and only if $S_{\alpha} =\left \{ x \in S:f\left ( x \right )\geq \alpha \right \}$ is convex for each real number $\alpha$.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasimonotone if and only if $S_{\alpha} =\left \{ x \in S:f\left ( x \right )= \alpha \right \}$ is convex for each real number $\alpha$.

Theorem

Let S be a non empty convex set in $\mathbb{R}^n$ and $f:S \rightarrow \mathbb{R}$ be differentiable on S, then f is quasiconvex if and only if for any $x_1,x_2 \in S$ and $f\left ( x_1 \right )\leq f\left ( x_2 \right )$, we have $\bigtriangledown f\left ( x_2 \right )^T\left ( x_2-x_1 \right )\leq 0$

Proof

Let f be a quasiconvex function.

Let $x_1,x_2 \in S$ such that $f\left ( x_1 \right ) \leq f\left ( x_2 \right )$

By differentiability of f at $x_2, \lambda \in \left ( 0, 1 \right )$

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )=f\left ( x_2+\lambda \left (x_1-x_2 \right ) \right )=f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1-x_2 \right ) \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )-f\left ( x_2 \right )-f\left ( x_2 \right )=\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x2, \lambda\left ( x_1-x_2 \right )\right )$

But since f is quasiconvex, $f \left ( \lambda x_1+ \left ( 1- \lambda \right )x_2 \right )\leq f \left (x_2 \right )$

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right ) \right )\leq 0$

But $\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right )\right )\rightarrow 0$ as $\lambda \rightarrow 0$

Therefore, $\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right ) \leq 0$

Converse

let for $x_1,x_2 \in S$ and $f\left ( x_1 \right )\leq f\left ( x_2 \right )$, $\bigtriangledown f\left ( x_2 \right )^T \left ( x_1,x_2 \right ) \leq 0$

To show that f is quasiconvex,ie, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq f\left ( x_2 \right )$

Proof by contradiction

Suppose there exists an $x_3= \lambda x_1+\left ( 1-\lambda \right )x_2$ such that $f\left ( x_2 \right )< f \left ( x_3 \right )$ for some $ \lambda \in \left ( 0, 1 \right )$

For $x_2$ and $x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_2-x_3 \right ) \leq 0$

$\Rightarrow -\lambda \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\geq 0$

For $x_1$ and $x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_3 \right ) \leq 0$

$\Rightarrow \left ( 1- \lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\leq 0$

thus, from the above equations, $\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )=0$

Define $U=\left \{ x:f\left ( x \right )\leq f\left ( x_2 \right ),x=\mu x_2+\left ( 1-\mu \right )x_3, \mu \in \left ( 0,1 \right ) \right \}$

Thus we can find $x_0 \in U$ such that $x_0 = \mu_0 x_2= \mu x_2+\left ( 1- \mu \right )x_3$ for some $\mu _0 \in \left ( 0,1 \right )$ which is nearest to $x_3$ and $\hat{x} \in \left ( x_0,x_1 \right )$ such that by mean value theorem,

$$\frac{f\left ( x_3\right )-f\left ( x_0\right )}{x_3-x_0}= \bigtriangledown f\left ( \hat{x}\right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x_3-x_0 \right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\mu_0 \lambda f\left ( \hat{x}\right )^T \left ( x_1-x_2 \right )$$

Since $x_0$ is a combination of $x_1$ and $x_2$ and $f\left (x_2 \right )< f\left ( \hat{x}\right )$

By repeating the starting procedure, $\bigtriangledown f \left ( \hat{x}\right )^T \left ( x_1-x_2\right )=0$

Thus, combining the above equations, we get:

$$f\left ( x_3\right )=f\left ( x_0 \right ) \leq f\left ( x_2\right )$$

$$\Rightarrow f\left ( x_3\right )\leq f\left ( x_2\right )$$

Hence, it is contradiction.

Examples

Step 1 − $f\left ( x\right )=X^3$

$Let f \left ( x_1\right )\leq f\left ( x_2\right )$

$\Rightarrow x_{1}^{3}\leq x_{2}^{3}\Rightarrow x_1\leq x_2$

$\bigtriangledown f\left ( x_2 \right )\left ( x_1-x_2 \right )=3x_{2}^{2}\left ( x_1-x_2 \right )\leq 0$

Thus, $f\left ( x\right )$ is quasiconvex.

Step 2 − $f\left ( x\right )=x_{1}^{3}+x_{2}^{3}$

Let $\hat{x_1}=\left ( 2, -2\right )$ and $\hat{x_2}=\left ( 1, 0\right )$

thus, $f\left ( \hat{x_1}\right )=0,f\left ( \hat{x_2}\right )=1 \Rightarrow f\left ( \hat{x_1}\right )\setminus < f \left ( \hat{x_2}\right )$

Thus, $\bigtriangledown f \left ( \hat{x_2}\right )^T \left ( \hat{x_1}- \hat{x_2}\right )= \left ( 3, 0\right )^T \left ( 1, -2\right )=3 >0$

Hence $f\left ( x\right )$ is not quasiconvex.

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$ then f is said to be strictly quasicovex function if for each $x_1,x_2 \in S$ with $f\left ( x_1 \right ) \neq f\left ( x_2 \right )$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}$

Remarks

• Every strictly quasiconvex function is strictly convex.
• Strictly quasiconvex function does not imply quasiconvexity.
• Strictly quasiconvex function may not be strongly quasiconvex.
• Pseudoconvex function is a strictly quasiconvex function.

Theorem

Let $f:S\rightarrow \mathbb{R}^n$ be strictly quasiconvex function and S be a non-empty convex set in $\mathbb{R}^n$.Consider the problem: $min \:f\left ( x \right ), x \in S$. If $\hat{x}$ is local optimal solution, then $\bar{x}$ is global optimal solution.

Proof

Let there exists $ \bar{x} \in S$ such that $f\left ( \bar{x}\right )\leq f \left ( \hat{x}\right )$

Since $\bar{x},\hat{x} \in S$ and S is convex set, therefore,

$$\lambda \bar{x}+\left ( 1-\lambda \right )\hat{x}\in S, \forall \lambda \in \left ( 0,1 \right )$$

Since $\hat{x}$ is local minima, $f\left ( \hat{x} \right ) \leq f\left ( \lambda \bar{x}+\left ( 1-\lambda \right )\hat{x} \right ), \forall \lambda \in \left ( 0,\delta \right )$

Since f is strictly quasiconvex.

$$f\left ( \lambda \bar{x}+\left ( 1-\lambda \right )\hat{x} \right )< max \left \{ f\left ( \hat{x} \right ),f\left ( \bar{x} \right ) \right \}=f\left ( \hat{x} \right )$$

Hence, it is contradiction.

Strictly quasiconcave function

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$, then f is saud to be strictly quasicovex function if for each $x_1,x_2 \in S$ with $f\left (x_1\right )\neq f\left (x_2\right )$, we have

$$f\left (\lambda x_1+\left (1-\lambda\right )x_2\right )> min \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$$.

Examples

• $f\left (x\right )=x^2-2$

  It is a strictly quasiconvex function because if we take any two points $x_1,x_2$ in the domain that satisfy the constraints in the definition $f\left (\lambda x_1+\left (1- \lambda\right )x_2\right )< max \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$ As the function is decreasing in the negative x-axis and it is increasing in the positive x-axis (since it is a parabola).

• $f\left (x\right )=-x^2$

  It is not a strictly quasiconvex function because if we take take $x_1=1$ and $x_2=-1$ and $\lambda=0.5$, then $f\left (x_1\right )=-1=f\left (x_2\right )$ but $f\left (\lambda x_1+\left (1- \lambda\right )x_2\right )=0$ Therefore it does not satisfy the conditions stated in the definition. But it is a quasiconcave function because if we take any two points in the domain that satisfy the constraints in the definition $f\left ( \lambda x_1+\left (1-\lambda\right )x_2\right )> min \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$. As the function is increasing in the negative x-axis and it is decreasing in the positive x-axis.

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$ then f is strongly quasiconvex function if for any $x_1,x_2 \in S$ with $\left ( x_1 \right ) \neq \left ( x_2 \right )$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \},\forall \lambda \in \left ( 0,1\right )$

Theorem

A quasiconvex function $f:S\rightarrow \mathbb{R}^n$ on a non-empty convex set S in $\mathbb{R}^n$ is strongly quasiconvex function if it is not constant on a line segment joining any points of S.

Proof

Let f is quasiconvex function and it is not constant on a line segment joining any points of S.

Suppose f is not strongly quasiconvex function.

There exist $x_1,x_2 \in S$ with $x_1 \neq x_2$ such that

$$f\left ( z \right )\geq max\left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}, \forall z= \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \in \left ( 0,1 \right )$$

$\Rightarrow f\left ( x_1 \right )\leq f\left ( z \right )$ and $f\left ( x_2 \right )\leq f\left ( z \right )$

Since f is not constant in $\left [ x_1,z \right ]$ and $\left [z,x_2 \right ] $

So there exists $u \in \left [ x_1,z \right ]$ and $v=\left [ z,x_2 \right ]$

$$\Rightarrow u= \mu_1x_1+\left ( 1-\mu_1\right )z,v=\mu_2z+\left ( 1- \mu_2\right )x_2$$

Since f is quasiconvex,

$$\Rightarrow f\left ( u \right )\leq max\left \{ f\left ( x_1 \right ),f \left ( z \right ) \right \}=f\left ( z \right )\:\: and \:\:f \left ( v \right ) \leq max \left \{ f\left ( z \right ),f\left ( x_2 \right ) \right \}$$

$$\Rightarrow f\left ( u \right )\leq f\left ( z \right ) \:\: and \:\: f\left ( v \right )\leq f\left ( z \right )$$

$$\Rightarrow max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$$

But z is any point between u and v, if any of them are equal, then f is constant.

Therefore, $max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$

which contradicts the quasiconvexity of f as $z \in \left [ u,v \right ]$.

Hence f is strongly quasiconvex function.

Theorem

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$. If $\hat{x}$ is local optimal solution, then $\hat{x}$ is unique global optimal solution.

Proof

Since a strong quasiconvex function is also strictly quasiconvex function, thus a local optimal solution is global optimal solution.

Uniqueness − Let f attains global optimal solution at two points $u,v \in S$

$$\Rightarrow f\left ( u \right ) \leq f\left ( x \right ).\forall x \in S\:\: and \:\:f\left ( v \right ) \leq f\left ( x \right ).\forall x \in S$$

If u is global optimal solution, $f\left ( u \right )\leq f\left ( v \right )$ and $f\left ( v \right )\leq f\left ( u\right )\Rightarrow f\left ( u \right )=f\left ( v\right )$

$$f\left ( \lambda u+\left ( 1-\lambda\right )v\right )< max \left \{f\left ( u \right ),f\left ( v \right ) \right \}=f\left ( u \right )$$

which is a contradiction.

Hence there exists only one global optimal solution.

Remarks

• A strongly quasiconvex function is also strictly quasiconvex fucntion.
• A strictly convex function may or may not be strongly quasiconvex.
• A differentiable strictly convex is strongly quasiconvex.

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1,x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )\geq f\left ( x_1 \right )$, or equivalently if $f\left ( x_1 \right )>f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )<0$

Pseudoconcave function

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1, x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )\leq f\left ( x_1 \right )$, or equivalently if $f\left ( x_1 \right )>f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )>0$

Remarks

• If a function is both pseudoconvex and pseudoconcave, then is is called pseudolinear.

• A differentiable convex function is also pseudoconvex.

• A pseudoconvex function may not be convex. For example,

  $f\left ( x \right )=x+x^3$ is not convex. If $x_1 \leq x_2,x_{1}^{3} \leq x_{2}^{3}$

  Thus,$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )=\left ( 1+3x_{1}^{2} \right )\left ( x_2-x_1 \right ) \geq 0$

  And, $f\left ( x_2 \right )-f\left ( x_1 \right )=\left ( x_2-x_1 \right )+\left ( x_{2}^{3} -x_{1}^{3}\right )\geq 0$

  $\Rightarrow f\left ( x_2 \right )\geq f\left ( x_1 \right )$

  Thus, it is pseudoconvex.

  A pseudoconvex function is strictly quasiconvex. Thus, every local minima of pseudoconvex is also global minima.

Strictly pseudoconvex function

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1,x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )> f\left ( x_1 \right )$,or equivalently if $f\left ( x_1 \right )\geq f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )<0$

Theorem

Let f be a pseudoconvex function and suppose $\bigtriangledown f\left ( \hat{x}\right )=0$ for some $\hat{x} \in S$, then $\hat{x}$ is global optimal solution of f over S.

Proof

Let $\hat{x}$ be a critical point of f, ie, $\bigtriangledown f\left ( \hat{x}\right )=0$

Since f is pseudoconvex function, for $x \in S,$ we have

$$\bigtriangledown f\left ( \hat{x}\right )\left ( x-\hat{x}\right )=0 \Rightarrow f\left ( \hat{x}\right )\leq f\left ( x\right ), \forall x \in S$$

Hence, $\hat{x}$ is global optimal solution.

Remark

If f is strictly pseudoconvex function, $\hat{x}$ is unique global optimal solution.

Theorem

If f is differentiable pseudoconvex function over S, then f is both strictly quasiconvex as well as quasiconvex function.

Remarks

• The sum of two pseudoconvex fucntions defined on an open set S of $\mathbb{R}^n$ may not be pseudoconvex.

• Let $f:S\rightarrow \mathbb{R}$ be a quasiconvex function and S be a non-empty convex subset of $\mathbb{R}^n$ then f is pseudoconvex if and only if every critical point is a global minima of f over S.

• Let S be a non-empty convex subset of $\mathbb{R}^n$ and $f:S\rightarrow \mathbb{R}$ be a function such that $\bigtriangledown f\left ( x\right )\neq 0$ for every $x \in S$ then f is pseudoconvex if and only if it is a quasiconvex function.

There are four types of convex programming problems −

Step 1 − $min \:f\left ( x \right )$, where $x \in S$ and S be a non-empty convex set in $\mathbb{R}^n$ and $f\left ( x \right )$ is convex function.

Step 2 − $min \: f\left ( x \right ), x \in \mathbb{R}^n$ subject to

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ and $g_i\left ( x \right )$ is a convex function.

$g_i\left ( x \right ) \leq 0,m_1+1 \leq m_2$ and $g_i\left ( x \right )$ is a concave function.

$g_i\left ( x \right ) = 0, m_2+1 \leq m$ and $g_i\left ( x \right )$ is a linear function.

where $f\left ( x \right )$ is a convex fucntion.

Step 3 − $max \:f\left ( x \right )$ where $x \in S$ and S be a non-empty convex set in $\mathbb{R}^n$ and $f\left ( x \right )$ is concave function.

Step 4 − $min \:f\left ( x \right )$, where $x \in \mathbb{R}^n$ subject to

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ and $g_i\left ( x \right )$ is a convex function.

$g_i\left ( x \right ) \leq 0, m_1+1 \leq m_2$ and $g_i\left ( x \right )$ is a concave function.

$g_i\left ( x \right ) = 0,m_2+1 \leq m$ and $g_i\left ( x \right )$ is a linear function.

where $f\left ( x \right )$ is a concave function.

Cone of feasible direction

Let S be a non-empty set in $\mathbb{R}^n$ and let $\hat{x} \in \:Closure\left ( S \right )$, then the cone of feasible direction of S at $\hat{x}$, denoted by D, is defined as $D=\left \{ d:d\neq 0,\hat{x}+\lambda d \in S, \lambda \in \left ( 0, \delta \right ), \delta > 0 \right \}$

Each non-zero vector $d \in D$ is called feasible direction.

For a given function $f:\mathbb{R}^n \Rightarrow \mathbb{R}$ the cone of improving direction at $\hat{x}$ is denoted by F and is given by

$$F=\left \{ d:f\left ( \hat{x}+\lambda d \right )\leq f\left ( \hat{x} \right ),\forall \lambda \in \left ( 0,\delta \right ), \delta >0 \right \}$$

Each direction $d \in F$ is called an improving direction or descent direction of f at $\hat{x}$

Theorem

Necessary Condition

Consider the problem $min f\left ( x \right )$ such that $x \in S$ where S be a non-empty set in $\mathbb{R}^n$. Suppose f is differentiable at a point $\hat{x} \in S$. If $\hat{x}$ is a local optimal solution, then $F_0 \cap D= \phi$ where $F_0=\left \{ d:\bigtriangledown f\left ( \hat{x} \right )^T d < 0 \right \}$ and D is a cone of feasible direction.

Sufficient Condition

If $F_0 \cap D= \phi$ f is a pseudoconvex function at $\hat{x}$ and there exists a neighbourhood of $\hat{x},N_\varepsilon \left ( \hat{x} \right ), \varepsilon > 0$ such that $d=x-\hat{x}\in D$ for any $x \in S \cap N_\varepsilon \left ( \hat{x} \right )$, then $\hat{x}$ is local optimal solution.

Proof

Necessary Condition

Let $F_0 \cap D\neq \phi$, ie, there exists a $d \in F_0 \cap D$ such that $d \in F_0$ and $d\in D$

Since $d \in D$, therefore there exists $\delta_1 >0$ such that $\hat{x}+\lambda d \in S, \lambda \in \left ( 0,\delta_1 \right ).$

Since $d \in F_0$, therefore $\bigtriangledown f \left ( \hat{x}\right )^T d <0$

Thus, there exists $\delta_2>0$ such that $f\left ( \hat{x}+\lambda d\right )< f\left ( \hat{x}\right ),\forall \lambda \in f \left ( 0,\delta_2 \right )$

Let $\delta=min \left \{\delta_1,\delta_2 \right \}$

Then $\hat{x}+\lambda d \in S, f\left (\hat{x}+\lambda d \right ) < f\left ( \hat{x} \right ),\forall \lambda \in f \left ( 0,\delta \right )$

But $\hat{x}$ is local optimal solution.

Hence it is contradiction.

Thus $F_0\cap D=\phi$

Sufficient Condition

Let $F_0 \cap D\neq \phi$ nd let f be a pseudoconvex function.

Let there exists a neighbourhood of $\hat{x}, N_{\varepsilon}\left ( \hat{x} \right )$ such that $d=x-\hat{x}, \forall x \in S \cap N_\varepsilon\left ( \hat{x} \right )$

Let $\hat{x}$ is not a local optimal solution.

Thus, there exists $\bar{x} \in S \cap N_\varepsilon \left ( \hat{x} \right )$ such that $f \left ( \bar{x} \right )< f \left ( \hat{x} \right )$

By assumption on $S \cap N_\varepsilon \left ( \hat{x} \right ),d=\left ( \bar{x}-\hat{x} \right )\in D$

By pseudoconvex of f,

$$f\left ( \hat{x} \right )>f\left ( \bar{x} \right )\Rightarrow \bigtriangledown f\left ( \hat{x} \right )^T\left ( \bar{x}-\hat{x} \right )<0$$

$\Rightarrow \bigtriangledown f\left ( \hat{x} \right) ^T d <0$

$\Rightarrow d \in F_0$

hence $F_0\cap D \neq \phi$

which is a contradiction.

Hence, $\hat{x}$ is local optimal solution.

Consider the following problem:$min \:f\left ( x\right )$ where $x \in X$ such that $g_x\left ( x\right ) \leq 0, i=1,2,...,m$

$f:X \rightarrow \mathbb{R},g_i:X \rightarrow \mathbb{R}^n$ and X is an open set in $\mathbb{R}^n$

Let $S=\left \{x:g_i\left ( x\right )\leq 0,\forall i \right \}$

Let $\hat{x} \in X$, then $M=\left \{1,2,...,m \right \}$

Let $I=\left \{i:g_i\left ( \hat{x}\right )=0, i \in M\right \}$ where I is called index set for all active constraints at $\hat{x}$

Let $J=\left \{i:g_i\left ( \hat{x}\right )<0,i \in M\right \}$ where J is called index set for all active constraints at $\hat{x}$.

Let $F_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown f\left ( \hat{x} \right )^T d <0 \right \}$

Let $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gI\left ( \hat{x} \right )^T d <0 \right \}$

or $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gi\left ( \hat{x} \right )^T d <0 ,\forall i \in I \right \}$

Lemma

If $S=\left \{ x \in X:g_i\left ( x\right ) \leq 0, \forall i \in I\right \}$ and X is non-empty open set in $\mathbb{R}^n$. Let $\hat{x}\in S$ and $g_i$ are different at $\hat{x}, i \in I$ and let $g_i$ where $i \in J$ are continuous at $\hat{x}$, then $G_0 \subseteq D$.

Proof

Let $d \in G_0$

Since $\hat{x} \in X$ and X is an open set, thus there exists $\delta_1 >0$ such that $\hat{x}+\lambda d \in X$ for $\lambda \in \left ( 0, \delta_1\right )$

Also since $g_\hat{x}<0$ and $g_i$ are continuous at $\hat{x}, \forall i \in J$, there exists $\delta_2>0$, $g_i\left ( \hat{x}+\lambda d\right )<0, \lambda \in \left ( 0, \delta_2\right )$

Since $d \in G_0$, therefore, $\bigtriangledown g_i\left ( \hat{x}\right )^T d <0, \forall i \in I$ thus there exists $\delta_3 >0, g_i\left ( \hat{x}+\lambda d\right )< g_i\left ( \hat{x}\right )=0$, for $\lambda \in \left ( 0, \delta_3\right ) i \in J$

Let $\delta=min\left \{ \delta_1, \delta_2, \delta_3 \right \}$

therefore, $\hat{x}+\lambda d \in X, g_i\left ( \hat{x}+\lambda d\right )< 0, i \in M$

$\Rightarrow \hat{x}+\lambda d \in S$

$\Rightarrow d \in D$

$\Rightarrow G_0 \subseteq D$

Hence Proved.

Theorem

Necessary Condition

Let $f$ and $g_i, i \in I$, are different at $\hat{x} \in S,$ and $g_j$ are continous at $\hat{x} \in S$. If $\hat{x}$ is local minima of $S$, then $F_0 \cap G_0=\phi$.

Sufficient Condition

If $F_0 \cap G_0= \phi$ and f is a pseudoconvex function at $\left (\hat{x}, g_i 9x \right ), i \in I$ are strictly pseudoconvex functions over some $\varepsilon$ - neighbourhood of $\hat{x}, \hat{x}$ is a local optimal solution.

Remarques

• Soit $ \ hat {x} $ un point réalisable tel que $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, alors $ F_0 = \ phi $. Ainsi, $ F_0 \ cap G_0 = \ phi $ mais $ \ hat {x} $ n'est pas une solution optimale

• Mais si $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, alors $ G_0 = \ phi $, donc $ F_0 \ cap G_0 = \ phi $

• Considérez le problème: min $ f \ left (x \ right) $ tel que $ g \ left (x \ right) = 0 $.

  Puisque $ g \ left (x \ right) = 0 $, donc $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ et $ g_2 \ left (x \ right) = - g \ gauche (x \ droite) \ leq 0 $.

  Soit $ \ hat {x} \ in S $, puis $ g_1 \ left (\ hat {x} \ right) = 0 $ et $ g_2 \ left (\ hat {x} \ right) = 0 $.

  Mais $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $

  Ainsi, $ G_0 = \ phi $ et $ F_0 \ cap G_0 = \ phi $.

Conditions nécessaires

Théorème

Considérons le problème - $ min f \ left (x \ right) $ tel que $ x \ in X $ où X est un ensemble ouvert dans $ \ mathbb {R} ^ n $ et soit $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.

Soit $ f: X \ rightarrow \ mathbb {R} $ et $ g_i: X \ rightarrow \ mathbb {R} $

Soit $ \ hat {x} $ une solution faisable et soit f et $ g_i, i \ in I $ sont différentiables en $ \ hat {x} $ et $ g_i, i \ in J $ sont continus en $ \ hat { x} $.

Si $ \ hat {x} $ résout le problème ci-dessus localement, alors il existe $ u_0, u_i \ in \ mathbb {R}, i \ in I $ tel que $ u_0 \ bigtriangledown f \ left (\ hat {x} \ droite) + \ displaystyle \ sum \ limits_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0

où $ u_0, u_i \ geq 0, i \ in I $ et $ \ left (u_0, u_I \ right) \ neq \ left (0,0 \ right) $

De plus, si $ g_i, i \ in J $ sont également différentiables en $ \ hat {x} $, alors les conditions ci-dessus peuvent être écrites comme -

$ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $

$ u_ig_i \ left (\ hat {x} \ right) $ = 0

$ u_0, u_i \ geq 0, \ forall i = 1,2, ...., m $

$ \ left (u_0, u \ right) \ neq \ left (0,0 \ right), u = \ left (u_1, u_2, s, u_m \ right) \ in \ mathbb {R} ^ m $

Remarques

• Les $ u_i $ sont appelés multiplicateurs lagrangiens.

• La condition que $ \ hat {x} $ soit faisable pour le problème donné est appelée condition primale de faisable.

• L'exigence $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ est appelée double faisabilité état.

• La condition $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ est appelée condition de relâchement complémentaire. Cette condition nécessite $ u_i = 0, i \ in J $

• Ensemble, la condition de faisabilité primitive, la condition de faisabilité double et le relâchement complémentaire sont appelés conditions de Fritz-John.

Conditions suffisantes

Théorème

S'il existe un $ \ varepsilon $ -neighbourhood de $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ tel que f soit pseudoconvexe sur $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ et $ g_i, i \ in I $ sont strictement pseudoconvexes sur $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, puis $ \ hat { x} $ est la solution locale optimale au problème décrit ci-dessus. Si f est pseudoconvexe en $ \ hat {x} $ et si $ g_i, i \ in I $ sont à la fois une fonction strictement pseudoconvexe et quasiconvexe en $ \ hat {x}, \ hat {x} $ est la solution globale optimale au problème décrit ci-dessus.

Exemple

• $ min \: f \ left (x_1, x_2 \ right) = \ left (x_1-3 \ right) ^ 2 + \ left (x_2-2 \ right) ^ 2 $

  tel que $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ Et $ \ hat {x} = \ left (2 , 1 \ droite) $

  Soit $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5, $

  $ g_2 \ gauche (x_1, x_2 \ droite) = x_1 + 2x_2-4, $

  $ g_3 \ left (x_1, x_2 \ right) = - x_1 $ et $ g_4 \ left (x_1, x_2 \ right) = -x_2 $.

  Ainsi, les contraintes ci-dessus peuvent être écrites comme -

  $ g_1 \ gauche (x_1, x_2 \ droite) \ leq 0, $

  $ g_2 \ gauche (x_1, x_2 \ droite) \ leq 0, $

  $ g_3 \ left (x_1, x_2 \ right) \ leq 0 $ et

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Ainsi, $ I = \ left \ {1,2 \ right \} $ donc, $ u_3 = 0, u_4 = 0 $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ right) ) $ et $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  En mettant ces valeurs dans la première condition des conditions de Fritz-John, on obtient -

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ et soit $ u_2 = 1 $, donc $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  Ainsi les conditions de Fritz John sont satisfaites.

• $ min f \ gauche (x_1, x_2 \ droite) = - x_1 $.

  tel que $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,

  $ -x_2 \ leq 0 $ et $ \ hat {x} = \ left (1,0 \ right) $

  Soit $ g_1 \ left (x_1, x_2 \ right) = x_2- \ left (1-x_1 \ right) ^ 3 $,

  $ g_2 \ gauche (x_1, x_2 \ droite) = - x_2 $

  Ainsi, les contraintes ci-dessus peuvent être écrites comme -

  $ g_1 \ gauche (x_1, x_2 \ droite) \ leq 0, $

  $ g_2 \ gauche (x_1, x_2 \ droite) \ leq 0, $

  Ainsi, $ I = \ left \ {1,2 \ right \} $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (-1,0 \ right) $

  $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (0,1 \ right) $ et $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right) ) $

  En mettant ces valeurs dans la première condition des conditions de Fritz-John, on obtient -

  $ u_0 = 0, \: \: u_1 = u_2 = a> 0 $

  Ainsi les conditions de Fritz John sont satisfaites.

Considérez le problème -

$ min \: f \ left (x \ right) $ tel que $ x \ in X $, où X est un ensemble ouvert dans $ \ mathbb {R} ^ n $ et $ g_i \ left (x \ right) \ leq 0, je = 1, 2, ..., m $

Soit $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $

Soit $ \ hat {x} \ in S $ et soit $ f $ et $ g_i, i \ in I $ sont différentiables en $ \ hat {x} $ et $ g_i, i \ in J $ sont continus en $ \ hat {x} $. De plus, $ \ bigtriangledown g_i \ left (\ hat {x} \ right), i \ in I $ sont linéairement indépendants. Si $ \ hat {x} $ résout localement le problème ci-dessus, alors il existe $ u_i, i \ in I $ tel que

$ \ bigtriangledown f \ left (x \ right) + \ displaystyle \ sum \ limits_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $, $ \: \: u_i \ geq 0, i \ dans I $

Si $ g_i, i \ dans J $ sont également différentiables en $ \ hat {x} $. puis $ \ hat {x} $, puis

$ \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $

$ u_ig_i \ left (\ hat {x} \ right) = 0, \ forall i = 1,2, ..., m $

$ u_i \ geq 0 \ forall i = 1,2, ..., m $

Exemple

Considérez le problème suivant -

$ min \: f \ left (x_1, x_2 \ right) = \ left (x_1-3 \ right) ^ 2 + \ left (x_2-2 \ right) ^ 2 $

tel que $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5 $,

$ x_1,2x_2 \ geq 0 $ et $ \ hat {x} = \ left (2,1 \ right) $

Soit $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5 $,

$ g_2 \ gauche (x_1, x_2 \ droite) = x_ {1} + 2x_2-4 $

$ g_3 \ left (x_1, x_2 \ right) = - x_ {1} $ et $ g_4 \ left (x_1, x_2 \ right) = - x_2 $

Ainsi, les contraintes ci-dessus peuvent être écrites comme -

$ g_1 \ gauche (x_1, x_2 \ droite) \ leq 0, g_2 \ gauche (x_1, x_2 \ droite) \ leq 0 $

$ g_3 \ left (x_1, x_2 \ right) \ leq 0, $ et $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Ainsi, $ I = \ left \ {1,2 \ right \} $ donc , $ u_3 = 0, \: \: u_4 = 0 $

$ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ right) ) $ et

$ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

En mettant ces valeurs dans la première condition des conditions de Karush-Kuhn-Tucker, on obtient -

$ u_1 = \ frac {1} {3} $ et $ u_2 = \ frac {2} {3} $

Ainsi les conditions de Karush-Kuhn-Tucker sont satisfaites.

Méthode de descente la plus raide

Cette méthode est également appelée méthode Gradient ou méthode de Cauchy. Cette méthode implique les terminologies suivantes -

$$ x_ {k + 1} = x_k + \ alpha_kd_k $$

$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ ou $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $

Soit $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $

En différenciant $ \ phi $ et en l'assimilant à zéro, nous pouvons obtenir $ \ alpha $.

Donc, l'algorithme va comme suit -

• Initialisez $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ et définissez $ k = 0 $.

• Définissez $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ ou $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ droit \ |} $.

• trouver $ \ alpha_k $ tel qu'il minimise $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.

• Définissez $ x_ {k + 1} = x_k + \ alpha_kd_k $.

• Si $ \ left \ | x_ {k + 1-x_k} \ droit \ | <\ varepsilon_1 $ ou $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, passez à l'étape 6, sinon définissez $ k = k + 1 $ et passez à l'étape 2.

• La solution optimale est $ \ hat {x} = x_ {k + 1} $.

Méthode Newton

La méthode Newton fonctionne sur le principe suivant -

$ f \ left (x \ right) = y \ left (x \ right) = f \ left (x_k \ right) + \ left (x-x_k \ right) ^ T \ bigtriangledown f \ left (x_k \ right) + \ frac {1} {2} \ gauche (x-x_k \ droite) ^ TH \ gauche (x_k \ droite) \ gauche (x-x_k \ droite) $

$ \ bigtriangledown y \ left (x \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x-x_k \ right) $

À $ x_ {k + 1}, \ bigtriangledown y \ left (x_ {k + 1} \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x_ {k +1} -x_k \ droite) $

Pour que $ x_ {k + 1} $ soit la solution optimale $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $

Ainsi, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $

Ici, $ H \ left (x_k \ right) $ doit être non singulier.

Par conséquent, l'algorithme va comme suit -

Step 1 - Initialisez $ x_0, \ varepsilon $ et définissez $ k = 0 $.

Step 2 - trouver $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $.

Step 3 - Résoudre pour le système linéaire $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ pour $ h \ left (x_k \ right) $.

Step 4 - trouver $ x_ {k + 1} = x_k-h \ left (x_k \ right) $.

Step 5- Si $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ ou $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ puis passez à l'étape 6, sinon définissez $ k = k + 1 $ et passez à l'étape 2.

Step 6 - La solution optimale est $ \ hat {x} = x_ {k + 1} $.

Méthode de gradient conjugué

Cette méthode est utilisée pour résoudre les problèmes des types suivants -

$ min f \ left (x \ right) = \ frac {1} {2} x ^ T Qx-bx $

où Q est une matrice nXn définie positive et b est constant.

Étant donné $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $

Définissez $ d_0 = -g_0 $ pour $ k = 0,1,2, ..., $

Définir $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $

Calculer $ x_ {k + 1} = x_k + \ alpha_kd_k $

Définir $ g_ {k + 1} = g_k + \ alpha_kd_k $

Calculer $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $

Calculer $ x_ {k + 1} = x_k + \ alpha_kd_k $

Définir $ g_ {k + 1} = x_k + \ alpha_kQd_k $

Calculer $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $

Définissez $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.