Basic Python implementation of the barrier method to solve a Quadratic optimization Problem.
Implemented for the course "Convex optimization and applications in machine learning" for Master MVA.
We consider the (QP) problem:
minimize +
subject to
With
and where
.
The function v_seq = centering_step(Q,p,A,b,t,v0,eps) implements
the Newton method to solve the centering step given the inputs (Q, p, A, b), the
barrier method parameter t, initial variable and a target precision
The function outputs the sequence of variables iterates
, where
is the number of iterations to obtain the
precision, using a backtracking line search.
The function v_seq = barr_method(Q,p,A,b,v0,eps) which implements the barrier method to solve (QP) using precedent function given the data inputs (Q, p, A, b), a feasible point v0, a precision criterion . The function outputs the sequence of variables iterates
, where
is the number of iterations to obtain the
precision.
We test our function on randomly generated matrices X and observations y with λ = 10.
We plot precision criterion and gap in semilog scale (using the best value found for
as a surrogate for
). We repeat for different values of the barrier method parameter µ = 2, 15, 50, 100,... and check the impact on w.