0
$\begingroup$

Hi,

I wanted to ask, under which conditions can one rewrite the optimization objective

$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$

as

$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$

I have particular interest in the case where $f(x) = \|x\|_1$ and $g(x) = \|y - Ax\|_2$ (i.e. for the Lasso!), but would like to know the details for the general case.

References to appropriate books would be equally useful.

Thank you!

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean? Except in very special cases there is no reason for the solutions of those two problems to be related at all. $\endgroup$
    – Robert Israel
    Commented Jun 23, 2013 at 18:54
  • $\begingroup$ Hi Robert. I know this is possible when f(x) = ||x||_1 and g(x) = ||A*(y-Ax)||_\infty (A is a matrix, and A* is its adjoint). Then, I assumed it would also be possible in the particular case I mentioned above. Could you shed some light on why this happens or mention a general procedure to manipulate the problem and see if such relation exists? Thank you very much! $\endgroup$
    – rodms
    Commented Jun 24, 2013 at 0:13

2 Answers 2

Reset to default
1
$\begingroup$

Here's a solution for the specific case where $f(x)=\| x \|_{1}$ and $g(x)=\| y-Ax \|_{2}$. The same appraoch applies to $g(x)=\| A^{T}(y-Ax) \|_{\infty}$.

There are two cases.

  1. If $g(0) \leq s$, then $x^{*}=0$ is feasible for the first problem and because $f(x) > 0$ for all $x \neq 0$, $x^{*}=0$ is the unique optimal solution to the first problem. In that case, let $t=0$. Then $x^{*}=0$ is the only feasible solution to the second problem and thus the unique optimal solution to the second problem.

  2. If $g(0) > s$, then $x=0$ is infeasible for the first problem. Since $x=0$ is the only unconstrained minimum of $f(x)$, any optimal solution to the first problem must have $g(x)=s$. Let $x^{*}$ be an optimal solution to the first problem. Let $t=f(x^{*})$. Clearly, $x^{*}$ is feasible for the second problem. We will show that $x^{*}$ is also optimal for the second problem.

suppose that there is some better solution to the second problem, $\hat{x}$. That is,

$f(\hat{x}) \leq t=f(x^{*})$

and

$g(\hat{x}) < g(x^{*}) = s $

Since $\hat{x}$ is interior to the feasible set for problem one (or simply because $g$ is continuous), we can find an $\epsilon$ with $0 < \epsilon < 1$ and such that

$\tilde{x}=(1-\epsilon)\hat{x}$

has $g(\tilde{x}) \leq s$.

Note that

$f(\tilde{x})=(1-\epsilon)f(\hat{x}) < f(x^{*})$.

This contradicts the assumption that $x^{*}$ was optimal for problem one.

This proof generalizes to any case where $f(x)$ is a vector norm and $g(x)$ is a continuous function.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In computational practice, if $g(x)$ is convex (which it is for your two $g(x)$ functions), and $f(x)$ is a vector norm, then the optimal value of the second problem is a monotone decreasing function of $t$, so you can just increase $t$ until you get a solution with $g(x^{*})=s$. $\endgroup$
    – Brian Borchers
    Commented Jun 26, 2013 at 3:16
1
$\begingroup$

You need to start by by being explicit about the "equivalence" between the problems. Do you mean that "For every $s$, there is a $t$ such that if $x^{ * }$ is an optimal solution to the first problem, then $x^{*}$ is also an optimal solution to the second problem?" Or (a little more strict) do you require that this work in both directions?

Even the simpler version of isn't true in general. Consider the example where $f(x)=0$ and $g(x)=\| x \|_{1}$ and $s=1$. There are many optimal solutions to the first problem, including $x^{*}_{1}=1$, $x^{*}_{j}=0\;\; j \neq 1$. There is no value of $t$ such that this $x^{*}$ is optimal for the second problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you Brian, you are right, I should have been more specific. By 'equivalent' I meant precisely what you stated first "For every $s$, there is a $t$ such that if $x*$ is an optimal solution to the first problem, then $x*$ is also an optimal solution to the second problem" It is now clear to me that under this notion, my statement is not true in general. However, I know it is true for $f(x) = \|x\|_1$ and $g(x) = \|A^T(y-Ax)\|_\infty$ ($A$ is an nxp matrix, and $x,y$ are vector of appropriate dimensions), but don't know how to prove it. Do you know why this is true? Thank you very much. $\endgroup$
    – rodms
    Commented Jun 24, 2013 at 21:15

You must log in to answer this question.

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