<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 1A.algo - Optimisation sous contrainte
L'optimisation sous contrainte est un problème résolu. Ce notebook utilise une librairie externe et la compare avec l'algorithme Arrow-Hurwicz qu'il faudra implémenter. Plus de précision dans cet article Damped Arrow-Hurwicz algorithm for sphere packing.
Step1:  Le langage Python propose des modules qui permettent de résoudre des problèmes d'optimisation sous contraintes et il n'est pas forcément nécessaire de connaître la théorie derrière les algorithmes de résolution pour s'en servir. Au cours de cette séance, on verra comment faire. Même si comprendre comment utiliser une fonction d'un module tel que  cvxopt requiert parfois un peu de temps et de lecture. 
On verra également un algorithme simple d'optimisation. C'est une bonne façon de comprendre que cela prend du temps si on veut implémenter soi-même ce type de solution tout en étant aussi rapide et efficace.
Exercice 1 
Step2:  La documentation cvxopt est parfois peu explicite. Il ne faut pas hésiter à regarder les exemples d'abord et à la lire avec attention les lignes qui décrivent les valeurs que doivent prendre chaque paramètre de la fonction. Le plus intéressant pour le cas qui nous intéresse est celui-ci (tiré de la page problems with nonlinear objectives) 
Step3:  Cet exemple résoud le problème de minimisation suivant 
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Explanation: 1A.algo - Optimisation sous contrainte
L'optimisation sous contrainte est un problème résolu. Ce notebook utilise une librairie externe et la compare avec l'algorithme Arrow-Hurwicz qu'il faudra implémenter. Plus de précision dans cet article Damped Arrow-Hurwicz algorithm for sphere packing.
End of explanation
from cvxopt import solvers, matrix
m = matrix( [ [2.0, 1.1] ] )  # mettre des réels (float) et non des entiers
                              # cvxopt ne fait pas de conversion implicite
t = m.T                       # la transposée
t.size                        # affiche les dimensions de la matrice
Explanation: Le langage Python propose des modules qui permettent de résoudre des problèmes d'optimisation sous contraintes et il n'est pas forcément nécessaire de connaître la théorie derrière les algorithmes de résolution pour s'en servir. Au cours de cette séance, on verra comment faire. Même si comprendre comment utiliser une fonction d'un module tel que  cvxopt requiert parfois un peu de temps et de lecture. 
On verra également un algorithme simple d'optimisation. C'est une bonne façon de comprendre que cela prend du temps si on veut implémenter soi-même ce type de solution tout en étant aussi rapide et efficace.
Exercice 1 : optimisation avec cvxopt
On souhaite résoudre le problème d'optimisation suivant :
$\left { \begin{array}{l} \min_{x,y} \left { x^2 + y^2 - xy + y \right }  \ sous \; contrainte \; x + 2y = 1 \end{array}\right .$
Le module cvxopt est un des modules les plus indiqués pour résoudre ce problème. Voici quelques instructions qui l'utilisent :
End of explanation
from cvxopt import solvers, matrix, spdiag, log
def acent(A, b):
    m, n = A.size
    def F(x=None, z=None):
        if x is None: 
            # l'algorithme fonctionne de manière itérative
            # il faut choisir un x initial, c'est ce qu'on fait ici
            return 0, matrix(1.0, (n,1))
        if min(x) <= 0.0: 
            return None   # cas impossible
        
        # ici commence le code qui définit ce qu'est une itération
        f = -sum(log(x))
        Df = -(x**-1).T
        if z is None: return f, Df
        H = spdiag(z[0] * x**(-2))
        return f, Df, H
    
    return solvers.cp(F, A=A, b=b)['x']
A = matrix ( [[1.0,2.0]] ).T
b = matrix ( [[ 1.0 ]] )
print(acent(A,b))
# il existe un moyen d'éviter l'affichage des logs (pratique si on doit faire
# un grand nombre d'optimisation)
from cvxopt import solvers
solvers.options['show_progress'] = False
print(acent(A,b))
solvers.options['show_progress'] = True
Explanation: La documentation cvxopt est parfois peu explicite. Il ne faut pas hésiter à regarder les exemples d'abord et à la lire avec attention les lignes qui décrivent les valeurs que doivent prendre chaque paramètre de la fonction. Le plus intéressant pour le cas qui nous intéresse est celui-ci (tiré de la page problems with nonlinear objectives) :
End of explanation
import cvxopt
m = cvxopt.matrix( [[ 0, 1.5], [ 4.5, -6] ] )
print(m)
Explanation: Cet exemple résoud le problème de minimisation suivant :
$\left{ \begin{array}{l} \min_{X} \left{ - \sum_{i=1}^n \ln x_i \right } \ sous \; contrainte \;  AX = b \end{array} \right.$
Les deux modules numpy et cvxopt n'utilisent pas les mêmes matrices (les mêmes objets matrix) bien qu'elles portent le même nom dans les deux modules. Les fonctions de cvxopt ne fonctionnent qu'avec les matrices de ce module. Il ne faut pas oublier de convertir la matrice quand elle est décrite par une autre classe.
End of explanation
<END_TASK>