Best way to minimize a function containing an l1 term

I have a loss function that I am minimizing. It includes a nonconvex score term and an l1 regularization term. Currently, to minimize this function, I have been using the fminunc function with the quasi-newton algorithm. So, presumably, the fminunc function is doing some sort of smoothing on the l1 term as it minimizes the overall loss function. This works fairly well.

My question is: Is there a better way to handle this minimization? One possibility I have considered is to reformulate the l1 term as a linear function with linear constraints. I am not sure if that would be more viable than my current approach, or if there is some other option that MATLAB would be more amenable to.

Answer 1

[Walter Roberson]

The most efficient constraints are pure bounds constraints. The optimizers that handle constraints at all mostly enforce bounds contraints at every step (or trial point).

The second most efficient is linear inequality constraints; some of the algorithms will actively analyze them and reason about them. The optimizers do not necessarily enforce these at every trial point but do enforce them at every generation.

The third most efficient is linear equality constraints. Some of the algorithms can reason about these. They are less likely to be enforced at every trial point.

Least efficient is nonlinear constraints (inequality or equality.) The algorithms basically cannot reason about these, and often do not even try to enforce them at every trial point.

If you can degrade a nonlinear constraint to a linear inequality constraint then you are probably going to get better results and faster.

I would also note here that sometimes the best way to deal with a constraint is through a change of variables, especially an equality constraint: sometimes you can reduce the number of variables and then inside the objective function reconstruct the "missing" variable by knowledge of the equality constraint.