1
$\begingroup$

If I have such an optimization problem: $$ \arg\min_{x,z} \dfrac{||y-x||_2^2}{z}+z(||y-x||_2^2) $$ where $y$ is known and $z>0$.

If $z$ is fixed, then this function w.r.t $x$ is convex. Similarly, if $x$ is given, this function w.r.t $z$ is also convex. However, I wonder:

  1. Is the original function w.r.t $x$ and $z$ jointly convex?
  2. If so, can I optimize the function alternatively by fixing $x$ solving for $z$ and fixing $z$ solving for $x$ until converging?
  3. Are there any relevant papers/materials that I should read for this kind of question?
$\endgroup$
  • 2
    $\begingroup$ I hesitate to give an answer because I'm not sure I'm correct. But WLOG suppose y=0. Then we have $\| x\|_2^2 ( \frac{1}{z} + z)$. This is not convex unless we restrict the domain of z to be positive. In fact, if x is given we have $c(z + \frac{1}{z}$ where c is a constant. In addition to being undefined at 0, it is non-convex, contrary to what you said in your post. $\endgroup$ – David Kozak Nov 19 '17 at 3:09
  • 2
    $\begingroup$ In general, a book on functional analysis ought to answer these types of questions -- Kreyszig's Introductory Functional Analysis with Applications is quite good. $\endgroup$ – David Kozak Nov 19 '17 at 3:14
  • 1
    $\begingroup$ Look at Boyds Convex Analysis $\endgroup$ – kjetil b halvorsen Nov 19 '17 at 9:42
  • 1
    $\begingroup$ Any bilinear function defined on $\mathbb{R}^2$, such as $f(x,y)=xy$, provides simple counterexamples to $(1)$ and $(2)$. $\endgroup$ – whuber Nov 19 '17 at 16:49
  • 1
    $\begingroup$ @kjetil b halvorsen is referring to the freely available "Convex Optimization", by Boyd and Vandenberghe web.stanford.edu/~boyd/cvxbook . Section 3.2 is "Operations that preserve convexity". $\endgroup$ – Mark L. Stone Nov 19 '17 at 19:11
2
$\begingroup$

This is not jointly convex in x and z, even when z > 0.

Consider the example x and z both being 1-D. Let y=0, x=1, z=2. Then the Hessian w.r.t x and z has eigenvalues 5.43 and -0.18, and is therefore indefinite.

I suggest you try using a general purpose nonlinear non-convex optimizer in which you can impose the non-negativity constraint on z. Either use a local optimizer, or you could try using a global optimizer, such as BARON, if the problem dimension is not too high. If using BARON, you will need to place finite lower and upper bounds on all variables - if they are achieved at the optimum, then you need to adjust.

I would suggest trying off the shelf optimizers before trying to gin up your own algorithm. You can try an alternating optimization as you proposed in 2, but I don't think there is any guarantee it will converge, and if it does converge, that it will do so to the correct answer.

$\endgroup$

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.