Let $\mathbf c \in \mathbb{R}^n$ where $\mathbf c \neq \mathbf 0$ and $\mathbf A \in \mathbb{R}^{m \times n}$. What is the most efficient way to solve the following optimization problem? Even better, does it have an analytical solution?

\begin{equation} \begin{aligned} \max_{\mathbf x \in \mathbb{R}^n} & &&\mathbf c^\text{T}\mathbf x \\ \text{s.t.} & && \mathbf A \mathbf x \geq \mathbf 0, \\ & && \mathbf x\geq \mathbf 0, \\ & && ||\mathbf x||_2 \leq 1 \end{aligned} \end{equation}

I am interested in the case where $\mathbf x = \mathbf c / ||\mathbf c||$ is not a feasible solution for the problem.

  • $\begingroup$ How big it is? What happens if the solution is indeed what you say isn't feasible? $\endgroup$ – Royi Mar 28 at 22:48
  • $\begingroup$ @Royi, I'm interested in arbitrarily large instances of the problem. But, for concreteness, let's say $n \approx 10^6$ and $m \approx 10^6$. $\endgroup$ – Garrett Mar 29 at 5:00
  • $\begingroup$ If the solution is $\mathbf x = \mathbf c / ||\mathbf c||$, that's great; we're done. But that's not the interesting case. $\endgroup$ – Garrett Mar 29 at 5:02
  • $\begingroup$ Could we assume the norm of $ \boldsymbol{c} $ is 1? Have you looked at my solution? $\endgroup$ – Royi Apr 11 at 23:53

I don't think there is analytical solution.

But you can rewrite it as (Since you limited the norm any way):

$$\begin{aligned} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - c \right\|}_{2}^{2} \\ \text{subject to} \quad & A x \succeq \boldsymbol{0} \\ & x \succeq \boldsymbol{0} \\ & {\left\| x \right\|}_{2} \leq 1 \end{aligned}$$

The it becomes pretty close to your other question - Projection onto a Polyhedral Cone as Minimization of Different Norms with only one more set to project upon.
I took the code I created there and added the projection onto the Euclidean ($ {L}_{2} $ Norm) ball as in Orthogonal Projection onto the $ {L}_{2} $ Unit Ball.

The MATLAB Code which is accessible in my StackExchange Mathematics Q3599003 GitHub Repository.

| cite | improve this answer | |

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.