module td_1a.optimisation_contrainte#

Short summary#

module ensae_teaching_cs.td_1a.optimisation_contrainte

quelques fonctions sur l’optimisation quadratique avec contraintes

source on GitHub

Functions#

function

truncated documentation

Arrow_Hurwicz

contrainte

C dans Arrow_Hurwicz()

exercice_particulier1

exercice_particulier2

f_df

F dans Arrow_Hurwicz()

f_df_H

Fonction demandée par la fonction solvers.cp. …

Documentation#

quelques fonctions sur l’optimisation quadratique avec contraintes

source on GitHub

ensae_teaching_cs.td_1a.optimisation_contrainte.Arrow_Hurwicz(F, C, X0, p0, epsilon=0.1, rho=0.1, do_print=True)#

On implémente l’algorithme de Arrow-Hurwicz d’une façon générique. Cela correspond au problème d’optimisation :

\left\{ \begin{array}{l} \min_{X} f(X) \\ sous \; contrainte \; C(x) = 0 \end{array}\right.

Paramètres:

  • F – fonction qui retourne f(X) et \nabla f(X)

  • C – fonction qui retourne C(X) et \nabla C(X)

  • X0 – premier X

  • p0 – premier \rho

  • epsilon – paramètre multiplicatif devant le gradient

  • rho – paramètre multiplicatif durant la mise à jour prenant en compte la contrainte

  • do_print – pour écrire des résultats intermédiaire en fonction des itérations

Renvoie:

un dictionnaire {'x': solution, 'iteration': nombre d'itérations }

source on GitHub

ensae_teaching_cs.td_1a.optimisation_contrainte.contrainte(X)#

C dans Arrow_Hurwicz

source on GitHub

ensae_teaching_cs.td_1a.optimisation_contrainte.exercice_particulier1()#

solver.cp de cvxopt

On résoud le problème suivant avec cvxopt :

\left\{ \begin{array}{l} \min_{x,y} \left \{ x^2 + y^2 - xy + y \right \} \\ sous \; contrainte \; x + 2y = 1 \end{array}\right.

Qui s’implémente à l’aide de la fonction suivante :

def f_df_H(x=None,z=None) :
    if x is None :
        # cas 1
        x0 = matrix ( [[ random.random(), random.random() ]])
        return 0,x0
    f = x[0]**2 + x[1]**2 - x[0]*x[1] + x[1]
    d = matrix ( [ x[0]*2 - x[1], x[1]*2 - x[0] + 1 ] ).T
    h = matrix ( [ [ 2.0, -1.0], [-1.0, 2.0] ])
    if z is None:
        # cas 2
        return  f, d
    else :
        # cas 3
        return f, d, h

solvers.options['show_progress'] = False
A = matrix([ [ 1.0, 2.0 ] ]).trans()
b = matrix ( [[ 1.0] ] )
sol = solvers.cp ( f_df_H, A = A, b = b)

source on GitHub

ensae_teaching_cs.td_1a.optimisation_contrainte.exercice_particulier2()#

algorithme de Arrow-Hurwicz

On résoud le problème suivant avec l’algorithme de Arrow-Hurwicz.

\left\{ \begin{array}{l} \min_{x,y} \left \{ x^2 + y^2 - xy + y \right \} \\ sous \; contrainte \; x + 2y = 1 \end{array}\right.

Qui s’implémente à l’aide de la fonction suivante :

import random
from ensae_teaching_cs.td_1a.optimisation_contrainte import Arrow_Hurwicz

def f_df(X) :
    x,y = X
    f = x**2 + y**2 - x*y + y
    d = [ x*2 - y, y*2 - x + 1  ]
    return f, d

def contrainte(X) :
    x,y = X
    f = x+2*y-1
    d = [ 1,2]
    return f, d

X0  = [ random.random(),random.random() ]
p0  = random.random()
sol = Arrow_Hurwicz(f_df, contrainte, X0, p0, do_print=False)

source on GitHub

ensae_teaching_cs.td_1a.optimisation_contrainte.f_df(X)#

F dans Arrow_Hurwicz

source on GitHub

ensae_teaching_cs.td_1a.optimisation_contrainte.f_df_H(x=None, z=None)#

Fonction demandée par la fonction solvers.cp.

Elle répond aux trois cas :

  • F() : la fonction doit retourne le nombre de contraintes non linéaires (f_k) et un premier point X_0,

  • F(x) : la fonction retourne l’évaluation de f_0 et de son gradient au point x,

  • F(x,z) : la fonction retourne l’évaluation de f_0, son gradient et de la dérivée seconde au point x.

Voir exercice_particulier1. Le problème d’optimisation est le suivant :

\left\{ \begin{array}{l} \min_{x,y} \left\{ x^2 + y^2 - xy + y \right\} \\ sous \; contrainte \; x + 2y = 1 \end{array}\right.

source on GitHub