HAX606X - Convex optimization (2020 - 2023)

Go down, deep down.
statistics
optimization
machine learning

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.

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