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

Reset to default
-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$
    – Michael Grant
    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$
    – Michael Grant
    Aug 8, 2015 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.