0
$\begingroup$

The problem is to maximize the number of positive elements in the vector $Ax$ subject to $x\ge0$, $||x||=1$. The caveat is that $(Ax)_i$ need not be non-negative, i.e., we do not have $Ax\ge 0$. Can this be written as an LP?

This might help: Maximizing positive components in solution vector of linear programming problem

Here's what I've got. Clearly, $||x|| = 1$ can be dropped and $x$ can be normalised later. Suppose we "split" $x=y+z$ and write down the following problem:

Maximize the number of positive elements in vector $A(y+z)$

subject to: $Ay\ge0, y+z\ge0$

So now we have a non-negativity constraint on $Ay\ge0$ and we wish to maximize the number of strictly positive elements of $Ay$. (!)

"Splitting" further $y=u+v$ and writing down the following LP after the above link:

Maximize $||Au||$

Subject to $Av\ge0, 0\le Au\le1, u+v+z\ge0$

Note: $Ay=A(u+v)\ge0$ can be dropped in favour of the above constraints.

Does this solution appear correct? The optimal solution satisfies the constraints: if $x$ is optimal, then so is $cx$ (has the same number of positive elements). This can be used to scale $Ax$ until the least positive element is at least 1. Then split $Ax$ into negative parts ($Az$), set $(Au)_i$ equal to 1 if $(Ax)_i>0$, otherwise $0$, and $Av$ is the rest. [Provided of course such $z, u, v$ exist. Is it always the case? If not, is there a workaround?]

$\endgroup$
  • $\begingroup$ It´s not clear what the problem/exercise is. A numerical example helps to explain the exercise. $\endgroup$ – callculus Sep 1 '17 at 11:05
  • $\begingroup$ Maximize the number of positive elements in the vector Ax Subject to $||x||=1$, $x\ge0$ $\endgroup$ – poopdoop Sep 1 '17 at 15:14

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.