2
$\begingroup$

I am trying to solve the following optimization problem:

$$\min_{\|Px\|_2=1} \|x\|_1$$

I know it is non-convex. But some non-convex problems are still solvable.

Update

$P$ is 2x3. $x$ is a 3-dimensional vector. Except that, $P$ has no special structure. I believe that the low dimension of the problem might give a rise to a simple solution.

$\endgroup$
  • $\begingroup$ $P$ is 2x3. $x$ is a 3-dimensional vector. $\endgroup$ – Alex Shtof Aug 16 '14 at 23:24
5
$\begingroup$

Given that $P$ is of size $2\times 3$, with $x$ being a $3$-dimensional vector, the set $\|Px\|_2=1$ is simply an cylinder with some ellipse as its base (I am assuming that $P$ has rank $2$ here; the degenerate case can be treated in the similar way, or with a perturbation argument). The minimization problem amounts to inscribing the largest possible octahedron $\|x\|=r$ into this cylinder. Any point at which such octahedron touches the cylinder is the solution of the minimization problem.

The cylinder is convex, and so is its interior. Therefore, if a vertex of octahedron is connected in the interior of the cylinder, so is any edge incident to this vertex (except maybe the other endpoint), and so is any face incident to this vertex (except maybe its boundary). Conclusion: the inscribed octahedron has at least one vertex on the boundary of the cylinder. In other words, minimum is attained by a point of the form $te_i$ with $i\in\{1,2,3\}$. It remains to plug such point into $P$, find $t$ for which $\|P te_i\|_2=1$, and take the index $i$ for which $t$ is smallest.

Summary: the minimum of $\|x\|_1$ is $\left(\max_i \|Pe_i\|_2\right)^{-1}$.

$\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.