2
$\begingroup$

Is there a tractable solution to the optimization problem

$$\min \|Ax\|_1 \mbox{ such that } \|x\|_2^2 = 1?$$

Because of the non-convexity of the equality constraint, it seems like this is hard. (In my specific application, $x$ is just $3$-dimensional, but the number of rows of $A$ can be large.)

Edit: The reason I introduced the $\|x\|_2^2 = 1$ constraint is to avoid the trivial solution $x = 0$. There might be other ways to avoid it, potentially leading to a different but equally practically useful solution. Any ideas?

Edit 2: Geometrically, the rows of $A$ are points, and we are looking for a plane that fits them. The points fall roughly into two groups: ones that fit a plane very well, and others that do not fit at all. The 1-norm seems better suited to such a fit than simple least squares.

$\endgroup$
  • 1
    $\begingroup$ With some random data I could solve a problem with 1000 rows in A in less than a minute to global optimality using GloMIQO. $\endgroup$ – Erwin Kalvelagen Oct 4 '16 at 8:21
  • $\begingroup$ If you can change the 1-norm in the objective to a 2-norm, the problem becomes considerably easier. $\endgroup$ – LinAlg Oct 4 '16 at 12:15
  • $\begingroup$ @ErwinKalvelagen thanks for the info. I'll look at that solver. I'd be curious what it did and how it can be sure it found the global minimum. $\endgroup$ – Milos Hasan Oct 4 '16 at 15:44
  • $\begingroup$ @LinAlg agreed. I considered that but it does not work so well. Imagine if $A$ has orthogonal columns: the value of $\|Ax\|_2$ will not change at all. Now say it's close to orthogonal; the value will change but the minimum may not be very useful. $\endgroup$ – Milos Hasan Oct 4 '16 at 15:46
  • $\begingroup$ @MilosHasan for GloMIQO, read Section 2 in optimization-online.org/DB_FILE/2011/11/3240.pdf for the details. It explains the basic idea in just a few lines. $\endgroup$ – LinAlg Oct 4 '16 at 16:00

Your Answer

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

Browse other questions tagged or ask your own question.