Prof. Ming Gu, 861 Evans, tel: 2-3145
Email: XXXXXXXXXX
Math128B: Linear Alge
a and learning from data
Programming Assignment, Due Apr. 27, 2022
Solve the one-norm Lasso problem discussed in class.
You should turn in a .m file OneNormLassoxxx.m which contains a matlab function of the form
function
[solution_admm,solution_lp,info] = OneNormLassoxxx(A,b,params)
where xxx is your student id. On input, params is an object that contains at least three fields
params.rel tol, params.abs tol and params.maxit. On output, solution admm is the com-
puted solution with your admm method, and solution lp is the LP solution; and info should
have at least one field info.flag, which is 0 for a successful execution, and 1 otherwise. Compare
your admm solution with the LP solution for different levels of tolerance requirements.
Your program will be tested against a few random input matrices A and vector b with sparse
solutions. You must do all your programming work by yourself. A python progam instead of
matlab will be accceptable.
Submit your .m or .py file on gradescope by 23:59PM, Apr. 27, 2022.
Final Project: ADMM for one-norm Lasso
Consider the optimization problem
min ∥A x− b∥1 + τ ∥x∥1
for A ∈ Rm×n. We assume that m < n and τ > 0. This
optimization problem can also be reformulated as an LP.
â–¶ Develop and implement an ADMM algorithm for solving this
problem, by introducing two variables
u = A x− b, v = x.
â–¶ Compare the accuracy of your ADMM algorithm against a
eliable LP solver (in matlab or cvxopt, for example)
1 / 1