HAX606X - Convex optimization (2020 - 2023)

This is an undergraduate course (in French!) introducing standard techniques from convex optimization. Numerical elements are provided in Python and are written with Tanguy Lefort.


Descente de gradient, petit pas Descente de gradient, grand pas


References

  • Mathematics for Machine Learning; Marc Peter Deisenroth, A. Aldo Faisal, and Cheng Soon Ong; mml-book.pdf

  • Introduction à l'analyse numérique matricielle et à l'optimisation; G. Ciarlet

  • Fragments d’Optimisation Différentiable - Théories et Algorithmes; Jean Charles Gilbert .pdf

TP

  1. Premiers pas en Python et introduction à VSCodium TP0.html
  2. Prise en main de Python pour l'optimisation TP1.html
  3. Méthode de la sécante / méthode du nombre d'or: TP2.html
  4. Méthode de descente de gradient et variantes TP3.html, fichiers annexes: dico_math_functions.py widget_convergence.py widget_level_set.py
  5. Méthode de descente de gradient projeté et moindres carrés TP4.html

Notes pour aller plus loin





Cheat Sheet

This work is deeply inspired and adapted from the great work by Nicolas Rougier: https://github.com/rougier/numpy-tutorial

Code Result 
 x = np.zeros(9) 
 x = np.ones(9)
 
 x = np.full(9, 0.5)
 
 x = np.array([0, 0, 1, 0, 0, 0, 0, 0, 0])
 
 x = np.arange(9)
 
 x = rng.random(9)

Creation: matrix cases

Code Result 
M = np.ones((5, 9)) 
M = np.zeros((5, 9))
 
 M = np.array(
    [
        [0.0, 0.0, 0.5, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], 
        [1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.4, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    ]
)
 
 M = arange(5 * 9).reshape(5, 9)
 
 M = rng.random(9)
 
 M = np.eye(5, 9)
 
 M = np.diag(np.arange(5)) 
 M = np.diag(np.arange(3), k=2)

Creation: tensor cases

Code Result 
T = np.zeros((3, 5, 9))
 
T = np.ones((3, 5, 9))
 
T = np.arange(3 * 5 * 9).reshape(3, 5, 9)
 
T = rng.random((3, rows, cols))

Matrix reshaping

Code Result 
M = np.zeros((3, 4)); M[2, 2] = 1
 
M = M.reshape(4, 3)
 
M = M.reshape(12, 1)
 
M = M.reshape(1, 12)
 
M = M.reshape(6, 2)
 
M = M.reshape(2, 6)

Slicing

Start from a zero matrix and get the following simple slicing operations:



Code Result 
M = np.zeros((5, 9)) 
M[...] = 1 
M[:, ::2] = 1
 
M[::2, :] = 1
 
M[1, 1] = 1
 
M[:, 0] = 1
 
M[0, :] = 1
 
M[2:, 2:] = 1
 
M[:-2, :-2] = 1
 
M[2:4, 2:4] = 1
 
M[::2, ::2] = 1
 
M[3::2, 3::2] = 1