I have an energy function
$E({\bf y})=||\,g({\bf Ay+c})-{\bf d}\,||^2_2 + ||\,{\bf y-e}\,||^2_2 + \alpha\,|{\bf y}|_1$
I need to minimize this with respect to $\bf y$, all other variables being constant.
$g(\bf u)$ is a non-linear scalar function that acts on the elements of $\bf u$ independently. Typically this function is also monotonic and convex. In the simplest case, $g(\bf u) = u$, but other choices include $g({\bf u})=\log(1+\exp(\bf u))$.
My first question is whether this is a convex problem. I think that it is convex if $g(\bf u) = u$, but guessing it also might be convex if this function is nonlinear but has convex form, but I'm really not sure.
Then I would please like a suggestion as the quickest way to optimize for $\bf y$. I don't really know how to deal with the L1 term. The dimensionality of $\bf y$ is of the order 10,000 and $\bf A$ and $\bf B$ are typically sparse.
- Turns out this is not convex - see comments.
- Any suggestions on the best non-convex approach to use?
If $g(u)$ is convex, then you problem is convex as well:[EDIT by mcg: the linear/affine case is probably the only useful one for which this is convex.]Other cases can be convex as well. There are several simple rules to be used to detect convexity. You may want to take a look to a classic book:
http://stanford.edu/~boyd/cvxbook/
The $|\cdot|_1$ is a simple regularization term that you an easily convert in a set of linear constraints: $\min |x|_1$ is equivalent to
$$ \min \sum t_i\\ t_i\geq |x_i| \quad i=1,\ldots,n $$
and hence
$$ \min \sum t_i\\ t_i\geq x_i \quad i=1,\ldots,n t_i\geq -x_i \quad i=1,\ldots,n $$
More details are in the book I mentioned.
Than you can use any QP solver. If work on MATLAB and you do not want to work on the formulation, I would suggest you to use YALMIP or CVX.
You can find