Scribd
Upload
103 views1 page

Lagrange Dual & Optimality in L1 Norm Optimization

This document provides additional problems for an optimization assignment involving minimizing the L2 norm of a residual plus an L1 regularization term. It asks the student to: (1) derive the Lagrange dual of an equivalent problem, (2) show properties of the optimal point if the residual is non-zero, and (3) show a condition under which elements of the optimal point must be zero based on properties of the columns of the matrix A.

Uploaded by

Morokot Angela
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
103 views1 page

Lagrange Dual & Optimality in L1 Norm Optimization

This document provides additional problems for an optimization assignment involving minimizing the L2 norm of a residual plus an L1 regularization term. It asks the student to: (1) derive the Lagrange dual of an equivalent problem, (2) show properties of the optimal point if the residual is non-zero, and (3) show a condition under which elements of the optimal point must be zero based on properties of the columns of the matrix A.

Uploaded by

Morokot Angela
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

L.

Vandenberghe

EE236B Winter 2016

Additional problem for assignment #6


Consider the optimization problem
minimize kAx bk2 + kxk1
with A Rmn , b Rm , and > 0. The variable is an n-vector x.
1. Derive the Lagrange dual of the equivalent problem
minimize kyk2 + kxk1
subject to Ax b = y
with variables x Rn and y Rm .
2. Suppose Ax? b 6= 0 where x? is an optimal point. Define r = (Ax? b)/kAx? bk2 .
Show that
kAT rk ,
rT Ax? + kx? k1 = 0.
3. Show that if the Euclidean norm of the ith column of A is less than , then x?i = 0.

You might also like