Exercise 1. Montrer que est un halfspace en l'exprimant sous la forme .

Solution. En mettant au carré : . Par la propriété du produit scalaire, .

Exercise 2. Montrer que est convexe. Hint : si , alors .

Solution. Soient deux points de , leur combi. conv. donne : . Montrons que . Par IAG, donc en remplaçant, . Ce qui conclut, , donc .

Exercise 3. Soit , un ensemble convexe. Montrer que est convexe.

Solution. Par définition de l'espérance, on réécrit l'inégalité sous forme linéaire : . Donc par intersection de P avec un demi espace on conclut.

Exercise 4. Soit , un ensemble convexe. Montrer que est convexe.

Solution. On a : . Or est convexe (carré d'une fonction affine + terme linéaire en ), donc est un sous-niveau convexe, et , intersection de deux convexes, est convexe.

Exercise 5. Soit , un ensemble convexe. Montrer que est convexe.

Solution. L'inégalité se réécrit : avec . Donc , est convexe par intersection de deux convexes.

Exercise 6. Montrer que, si et sont des ensembles convexes de , alors est convexe.

Solution. Soient avec et . Leur combi. conv est . Montrons que :

avec , car c'est une combinaison convexe de points de et est convexe. De même, .

Exercise 7. 1) Montrer que est un cône convexe.

Puis 2) montrer que s'il n'existe aucun hyperplan séparant et .

Solution. 1) Posons et :

Or, , l'intersection de deux cônes convexes est encore un cône convexe.

2) Supposons qu'il n'existe aucun hyperplan séparant C et D. Soit . Or, . Ainsi, . Et comme , . Donc .

Exercise 8. Montrer que .

Solution.

Exercise 9. Montrer que .

Solution.

Exercise 10. Montrer que toute droite est à la fois affine et convexe.

Solution. Soit une droite. Soient , deux points de la droite. Posons . Par injection, .

Exercise 11. Soit , un ensemble convexe. Montrer que est convexe, avec .

Solution. On note , alors :

Donc . On a la relation car ne prend que des valeurs finies . Ainsi, est convexe par intersection.

Exercise 12. Soit , un ensemble convexe. Montrer que est convexe, avec .

Solution. Prouvons que , c'est dire que lui-même réussit le test .

Or, est linéaire en donc (ce demi-espace) est convexe comme intersection de convexes.

Exercise 13. Montrer que, si est inversible, alors (1) , est inversible. (2) Déterminer et .

Solution. (1) Montrons que est injective : pour retrouver à partir de , on utilise . Comme , l'application de donne . On identifie . . Elle est donc injective donc bijective de son image donc inversible.

2) L'unique fonction candidate est , avec comme domaine candidat . On vérifie que la fonction la fonction candidate est bien définie :

Finalement, , et .

Exercise 14. Montrer que est convexe. Hint : si , alors .

Solution. Soient , leur combi conv. donne . Montrons que . Par IAG, . En remplaçant, . Or, . Donc .

Exercise 15. Montrer que est convexe si .

Solution. Soit . On a . Or . Donc est convexe par citère de la Hessienne et par la prop des sous-niveaux.

Exercise 16. Trouver le cône dual de avec .

Solution. Trouver le dual c'est trouver l'ensemble des vecteurs qui font un angle aigu avec tout le cône : pour tout . Mais comme tout est une combinaison positive des colonnes , il suffit en fait de vérifier la condition sur les colonnes elles-mêmes : pour chaque colonne. Matriciellement, positif composante par composante : .

Exercise 17. Supposons que l'ensemble soit fermé, qu'il ait un intérieur non vide et qu'il admette un hyperplan d'appui en tout point de sa frontière. Montrer que est convexe.

Solution. On montre que est égal à l'intersection de ses demi-espaces d'appui. II sera alors convexe par intersection. Pour chaque , notons , le demi-espace d'appui contenant .

Ainsi , par intersection de demi-espaces est convexe.

Exercise 18. (1) Exprimer l'ensemble convexe fermé comme une intersection de demi-espaces. (2) Soit , la boule unité de la norme dans , et soit un point de la frontière de . Déterminer explicitement les hyperplans d'appui de en .

Solution. (1) Sur la frontière, , donc tout point s'écrit , avec . La tangente en ce point délimite le demi-espace . Dire qu'un point appartient à l'intersection de tous les signifie que cette inégalité est vraie pour tout , autrement dit que sa plus petite valeur reste supérieure à : . Or, par IAG, , avec égalité pour . Ainsi, cet infimum vaut , donc . Finalement, .

(2) Un hyperplan passant par s'écrit . Il est d'appui en si . Déterminer tous les hyperplans d'appui revient donc à déterminer les vecteurs normaux possibles. Pour déterminer les , on modifie seulement , obtenant un point . Alors . Donc reste un maximum :

Ainsi, en supposant les valeurs de conditionnées tout , on a alors, dans chacun des trois cas, En sommant sur , Donc est bien un hyperplan d'appui.

Exercise 19. La fonction support d'un ensemble est définie par

Supposons que et soient des ensembles convexes fermés de . Montrer que si et seulement si leurs fonctions support sont égales.

Solution.

Exercise 20. On définit le cône monotone non négatif par

Autrement dit, il s'agit de l'ensemble des vecteurs à composantes non négatives, classées par ordre non croissant. (1) Montrer que est un cône propre. (2) Déterminer le cône dual .

Solution. (1) .

(2) Pour , tout s'écrit

Donc pour tout si et seulement si pour tout . Or . Ainsi, .

Exercise 21. Une matrice est dite copositive si pour tout .

(1) Vérifier que l'ensemble des matrices copositives est un cône propre. (2) Déterminer son cône dual.

Solution. (1)

(2) Chercher , c'est trouver les tels que pour toute copositive. L'astuce : comme , la définition de dit exactement que où est le cône engendré par les (stable par sommes, comme tout dual). étant convexe fermé, on dualise : , le cône des matrices complètement positives.

Exercise 1. Supposons que soit croissante et convexe sur son domaine . Soit son inverse, c'est-à-dire la fonction de domaine telle que pour . Que pouvez-vous dire au sujet de la convexité de ?

Solution. Ecrire l'inégalité de convexité de , puis on applique , qui est croissante. On obtient exactement l'inégalité de concavité de .

Exercise 2. Prouver qu'une fonction deux fois différentiable est convexe si et seulement si son domaine est convexe et pour tout .

Solution.

Exercise 3. Adapter la preuve de la concavité de la fonction log-déterminant pour montrer les résultats suivants.

(1) est convexe sur .

(2) est concave sur .

Solution. (1) Une fonction est convexe si et seulement si elle l'est le long de toute droite de son domaine. Fixons donc et symétrique, et montrons que est convexe sur l'intervalle où

Si était diagonale, connaître l'expression de serait simple : l'inverse se prend terme à terme, la trace somme la diagonale. Or en diagonalisant brutalement, , la matrice de passage bouge avec et les valeurs propres sont des fonctions moches de . Ce qu'il faudrait vraiment : un fixe, le même pour tout (ce qui équivaut à , faux en général). Mais l'identité, elle, commute avec tout le monde : ramenons à en factorisant , où . Ainsi, force le point de base à être . On passe donc du couple (point, direction) : à .

Il ne reste qu'un seul objet à diagonaliser, et il est fixe : , qui ne contient aucun . Comme est symétrique , le théorème spectral donne orthogonale et donc un une fois pour toutes, le même pour tout . Et la droite entière en hérite gratuitement: , aux valeurs propres affines en .

L'inverse traverse la factorisation: . Or, donc .

Et comme , la multiplier à gauche de multiplie la ligne de par ; la trace, qui ne lit que la diagonale, donne .

Or, pour assurer convexe, on a besoin de , et sur le domaine. Or , donc pour tout . De plus, équivaut à , donc pour tout . Enfin, sur cet intervalle, la fonction est convexe, car sa dérivée seconde vaut donc est convexe.

2) Comme en (1), il suffit de montrer la concavité de le long de toute droite, et la même factorisation s'applique. Par multiplicativité du déterminant et , on obtient , donc où .

Mais, un produit de fonctions concaves positives n'est pas concave en général, il faut donc calculer. Le logarithme transforme le produit en somme : avec . En posant , on a et , d'où .

Donc est concave, aussi comme multiple positif d'une fonction concave, et est concave.

Exercise 4. (a) Montrer que pour ,

est convexe sur .

(b) Montrer que

est convexe sur , où , , et .

Solution. (a) L'idée est de partir d'une fonction convexe, calculer sa perspective puis montrer qu'elle est égale à . On part de qui est une somme de fonction convexes, calculons sa perspective . C'est la fonction .

(b) On a la fonction perspective convexe (voir (a)) : . La fonction s'obtient par composition avec l'application affine . Comme la composition d'une fonction convexe avec une application affine est convexe, est convexe.

Exercise 5. (a) Montrer que est une fonction convexe de , où , et désigne la -ème plus grande composante de . (Vous pouvez utiliser le fait que est convexe sur .)

(b) Soit le polynôme trigonométrique

Montrer que la fonction

est convexe sur .

Solution. (a) On pose . Puis on utilise la transformation d'Abel avec et :

Donc est une combinaison à coefficients positifs des fonctions convexes .

(b) Posons , de sorte que est linéaire en . Le domaine est convexe comme intersection de demi-espaces ouverts. De plus, comme est convexe donc l'est aussi. On peux donc écrire la définition de la convexité : . Intégrons cette inégalité, valable pour chaque , sur (l'intégration préserve les inégalités, et tout est bien intégrable car est continue sur le compact ) :

Donc est convexe.

Exercise 1. Considérons le problème

où , , et . Nous supposons que , ce qui implique que pour tout admissible.

Solution. (1) Montrons donc que l'ensemble des sous-niveaux sont convexes et que les contraintes aussi :

(2) On pose . Montrons l'équivalence :

Exercise 2. Considérons le QCQP

avec . Montrer que , où , et où est la plus grande solution de l'équation non linéaire .

Solution. Comme , le problème est convexe : il suffit d'exhiber un couple vérifiant les conditions KKT. Avec le lagrangien , elles s'écrivent : (S) stationnarité : , (P) admissibilité primale: , (D) admissibilité duale: , (C) complémentarité : .

On commence par exploiter la condition de stationnarité . En posant , elle devient .

Comme par (D) , on a . De plus, , donc et cette matrice est inversible. Tout candidat vérifiant la stationnarité est donc de la forme .

Il reste maintenant à choisir de manière à satisfaire l'admissibilité primale et la complémentarité.

Le choix le plus naturel consiste d'abord à prendre . En effet, comme , cela revient à annuler le multiplicateur associé à la contrainte : la contrainte n'intervient alors plus dans la condition de stationnarité. On obtient , d'où .

Par définition de , cette équation est précisément la condition d'optimalité du problème sans contrainte. Ainsi, est naturellement le minimiseur libre. Il reste donc à vérifier s'il appartient à la boule unité.

Ainsi, le choix de dépend de la position du minimum sans contrainte par rapport à la boule unité : s'il est admissible, la contrainte est inutile et l'on garde , s'il ne l'est pas, il faut choisir pour déplacer le candidat jusqu'à la frontière de la boule.

Posons .

Les conditions d'admissibilité primale et de complémentarité s'écrivent alors et .

On distingue alors deux cas.

Finalement, .

Exercise 3. Formuler les problèmes suivants sous forme de programmes linéaires (PL). Expliquer en détail la relation entre la solution optimale de chaque problème et la solution du PL équivalent.

Dans chaque problème, et sont donnés. (Voir §6.1 pour d'autres problèmes portant sur l'approximation et l'approximation sous contraintes.)

Solution. On utilise les relations équivaut à et équivaut à . On remplacera donc la minimisation de l'objectif normé par celle de son majorant ou sous la contrainte de leur relation.

On a donc :(1) s.c. . (2) s.c. . (3) s.c. . (4) s.c. .(5) s.c. .

Exercise 4. Supposons que soit une application affine, c'est-à-dire

où . Soient les valeurs propres de . Montrer comment formuler les problèmes suivants sous la forme de programmes semi-définis positifs (SDP).

Solution. On utilise les relations et . On remplacera donc la minimisation de l'objectif par celle de son majorant ou (maximisation)de son minorant sous la contrainte de leur relation. (1) On a donc s.c. . (2) : s.c. . (3) On a : s.c. cet objectif n'est pas linéaire. Posons , l'objectif n'est toujours pas linéaire il faut diviser toute l'inégalité de la contrainte par : , ce qui rend le problème linéaire. (4) Minimiser , or avec et on écrit donc ce qui donne s.c.

Exercise 5. Considérons le PL

avec carrée et non singulière. Montrer que la valeur optimale est donnée par

Solution. Posons . La contrainte peut donc se réécrire . De plus, on peut isoler pour obtenir . On peut donc réécrire le problème . L'objectif se réécrit :

Le premier terme étant constant, il faut maximiser le second terme pour minimiser l'objectif total donc :

On reconnait le classique maximiser une forme linéaire sur l'orthant positif. Deux cas :

Exercise 1. Considérons le problème

où les fonctions sont différentiables et convexes. Dans une méthode de pénalité exacte, on résout le problème auxiliaire

où est un paramètre. Le second terme de pénalise les écarts de par rapport à la réalisabilité. La méthode est appelée méthode de pénalité exacte si, pour une valeur suffisamment grande de , les solutions du problème auxiliaire sont également des solutions du problème initial .

(a) Montrer que est convexe.

(b) Le problème auxiliaire peut s'écrire sous la forme

où les variables sont et . Déterminer le problème dual de Lagrange de ce problème et l'exprimer en fonction de la fonction duale de Lagrange du problème.

(c) Utiliser le résultat de la question (b) pour démontrer la propriété suivante. Supposons que soit une solution optimale du problème dual de Lagrange de et que la dualité forte soit vérifiée. Si

alors toute solution du problème auxiliaire est également une solution optimale du problème .

Solution. (a) La somme d'une fonction convexe avec avec un maximum de fonction convexes (donc a fortiori une fonction convexe aussi) est convexe.

(b) Mettons le problème sous forme primal :

Le lagrangien est donné par . La fonction duale vaut directement

La fonction duale du problème 1 est le premier terme. Le second terme est calculable, si est positif alors la plus petite valeur est 0 et si est néfgatif la plus petite valeur est . Ainsi on a :

(c) Soit la valeur minimale optimale du problème initial et une solution optimale du problème auxiliaire primal et supposons , on a :

	Primal	Dual
Initial		(dualité forte)
Auxiliaire		?

. Le but est de mq la solution du problème auxiliaire est aussi une solution optimale du problème initial.

On veux mq . Il suffit de montrer et :

Ainsi, donc le problème auxiliaire atteint la même valeur minimale que le problème initial. réalisable pour le problème initial. Attention, une solution du probleme auxiliaire pourrait ne pas respecter les contraintes du problème initial (), si alors comme cela violerait les contraintes du problème initial. Il faut donc montrer que . Or, par définition de : . Comme et , . Mais , donc . Puisque et , on obtient . Ainsi, pour tout , et comme , est optimale pour le problème initial.