1
$\begingroup$

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?
$\endgroup$
1
  • $\begingroup$ What do you mean by a "monotone" vector-valued function ? - I'm afraid one can't say much about your problem for general g. In case g is affine (the identity mapping, e.g), then your problem is essentially an elastic-net regression problem which can be solved using LARS, FISTA, etc. - The choice g(u) = log(1 + exp(u)) is more than weird. What are you really trying to model ? $\endgroup$
    – dohmatob
    Aug 9, 2015 at 10:13

1 Answer 1

-1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ If $g(a_i^T y + c_i) - d_i$ changes the sign, then it's square isn't convex. Consider $(x^2 - 1)^2$ on an interval containing $[-1, 1]$. $\endgroup$
    – user251257
    Aug 8, 2015 at 12:24
  • 1
    $\begingroup$ I'm afraid user251257 is right. The only two cases that will reliably be convex are 1) $g(u)$ affine and 2) $g(u)$ convex and $g(u)\geq d$. But that $g(u)\geq d$ is not likely to be satisfied by any useful case. $\endgroup$ Aug 8, 2015 at 12:37
  • $\begingroup$ The answer is useful in that the author provides information about the L1 approach, but I see what you mean about the non-convexity. $\endgroup$
    – Robotbugs
    Aug 8, 2015 at 20:23
  • 2
    $\begingroup$ Indeed. I know @AC_MOSEK personally, and I assure you that he knows his convexity :-) He must not have had his coffee yet before he answered this. $\endgroup$ Aug 8, 2015 at 21:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .