1

I am now struggling with the following problem:

\begin{alignat}{3} \max_{\mathbf x} & \quad& \mathbf c^T \mathbf x && \\ \text{subject to} &\quad& ||\mathbf x||_2 &=& 1 \\ &\quad& \mathbf{Ax} &\leq& \mathbf b \end{alignat}

If I replace the norm constraint by $||\mathbf x||_2 \leq 1$, then everything is easy as I only need to maximise a linear function subject to convex constraints. Many algorithms could be used to solve it. Yet, things become highly nonconvex after the inequality is replaced by equality.

I was wondering if there are any tools to solve it. Any direct calculations or iterative algorithms are welcome.

Thanks.

fuyutsuki
  • 11
  • 1
  • Is the implementation the issue or the problem? If implementation is the issue, what happens if you replace $||x||_2 = 1$ with $||x||_2 \leq 1$ and $||x||_2 \geq 1$? – user2974951 Jun 30 '21 at 08:31
  • Because of the linearity of the objective function it seems to me that the solution for the inequality version of the problem must have $\|x\|_2=1$ and so solve your problem, unless the hyperplane $Ax=b$ is orthogonal to the direction $c$. And if it is orthogonal, the problem should simplify. – Thomas Lumley Jun 30 '21 at 09:02
  • 1
    Unfortunately we do not necessarily have $||\mathbf x||_2 = 1$ after relaxing it to $||\mathbf x||_2 \leq 1$. Here is a counter example, consider $\mathbf x \in \mathbb R^2$, take $\mathbf c = (-1, -1) ^T$ and the affine constraint to be $\mathbf x \geq \mathbf 0$. Then we have $\mathbf x^* = (0, 0)^T.$ – fuyutsuki Jun 30 '21 at 09:08
  • Perhaps the technique I describe at https://stats.stackexchange.com/a/301561/919 (replacing the sphere with the ball) might help. – whuber Jun 30 '21 at 14:01

0 Answers0