Return to Answer

In certain cases, this optimization problem is easy to solve and have closed from for example, box constraint or L2 ball.

The following figure gives how it works visually: where the red trace is projected gradient decent trace.

In certain cases, this optimization problem is easy to solve and have closed from for example, box constraint or L2 ball. For L2 ball, the solution is:

The following figure gives how it works visually: where the red trace is projected gradient decent trace. In the experiment, I set a large $\lambda$ on L1 regularization, and the optimal point is close to the origin. We can clear see the projected solution (red dots) is on the unit circle.

PS: R code if you want to experiment more.

fn<-function(x,A,b,l1,l2){
  e=A %*% x - b
  v=crossprod(e)+l2*crossprod(x)+l1*sum(abs(x))
  return(c(v))
}

gr<-function(x,A,b,l1,l2){
  v=t(A) %*% (A %*% x -b)
  return(2*c(v)+2*l2*x+l1*sign(x))
}

set.seed(0)
par(cex=1)
n_data=10
n_feature=2

A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=matrix(runif(n_data),ncol=1)

l1=50
l2=0

# plot obj function
x1=seq(-5,5,0.05)
x2=seq(-5,5,0.05)
d=expand.grid(x1,x2)
f_v=matrix(apply(d,1,fn, A=A, b=b, l1=l1 , l2=l2),nrow=length(x1))
contour(x1,x2,f_v, lwd=3, labcex=1,col='khaki4', xlim=c(-5,5),ylim=c(-5,5))
grid()
constraint_v=outer(x1,x2,function(x,y) x^2+y^2-1)
contour(x1,x2,constraint_v, lwd=3, levels=0, add=T,col="forestgreen",labcex=1.5)

# solve the unconstrained optimization using toolbox
opt_res=optimx::optimx(c(-1,-1),fn, gr, method="BFGS", A=A, b=b, l1=l1 , l2=l2)
opt_x=c(opt_res$p1,opt_res$p2)
points(opt_x[1],opt_x[2],pch=19,col="black")

#-------------------------------------------------------------------
# all algorithms fix step size
# solve unconstrained optimization using gradient decent
x_init=c(-2,-3)
t=0.0001
f_opt=opt_res$value
x=x_init
trace_x=x_init
while(fn(x, A, b, l1 , l2)- f_opt> 1e-2){
  x=x-t*gr(x, A=A, b=b, l1=l1 , l2=l2)
  trace_x=rbind(trace_x,x)
  print(x)
}
# for GD we just plot points not string labels
points(trace_x,type='b',pch=19)


# solve constrained optimization using projected gradient decent
# x_d means desired place to go, x means after projection
x_init=c(-2,-3)
t=0.0001
x=x_init
f_opt=opt_res$value
trace_x=x_init
trace_x_d=x_init

while(fn(x, A, b, l1 , l2)-f_opt>1e-2){
  x_d=x-t*gr(x, A=A, b=b, l1=l1 , l2=l2)
  trace_x_d=rbind(trace_x_d,x_d)

  if(norm(x_d,'2')<1){
    x=x_d
  }
  else{
    x=1*x_d/norm(x_d,'2')
  }
  trace_x=rbind(trace_x,x)
}
trace_x=head(trace_x)
trace_p=head(trace_x_d)

points(trace_x_d,type='b',col=4,pch=19,lwd=3)
points(trace_x,type='b',col=2,pch=19,lwd=3)


legend(1,-0.7,c('obj contour','constraint', 'gd unconstrained',
                 'gd before projection', 'gd after projection'),
       lwd=3,col=c("khaki4",'forestgreen','black','blue','red'))

The problem is valid and can be solved by Projected Gradient Descent. Check my answer here

Solving constrained optimization problem: projected gradient vs. dual?

The figure (from my linked answer) gives how it works visually, and your problem is almost identical, the only difference is adding the L1 regularization, where we changed the objective function contour (as shown later)

Where with Lass Regularization it looks like this

The problem is valid and can be solved by Projected Gradient Descent, where we project the solution to L2 ball constraint. Check my answer here for details.

In Projected Gradient Decent, the projection step is another optimization problem.In this problem, we want to find a point in $C$ (constraint set), this point is closest to a given point $x^*$. Which is $$ \underset{x \in C}{\text{arg min}} \|x-x^*\| $$

In certain cases, this optimization problem is easy to solve and have closed from for example, box constraint or L2 ball.

$$ \underset{x \in C}{\text{arg min}} \|x-x^*\|=\left\{ \begin{array}{ll} x^* & \|x^*\| \leq r \\ r \frac {x^*} {\|x\|} & \text{otherwise} \\ \end{array} \right. $$

The equation tells, if the point is inside of the constraint domain, then the projection is the point itself.

And I will demonstrate the $r \frac {x^*} {\|x\|}$ case graphically, check the points (labeled with numbers) in blue track and red track, the relationship is easy: connect the blue dots with the center of the circle, the intersection with the circle is the projection.

The following figure gives how it works visually: where the red trace is projected gradient decent trace.