# Direction of Steepest Descent within a Polyhedral Cone

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{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}

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

• How big it is? What happens if the solution is indeed what you say isn't feasible? – Royi Mar 28 at 22:48
• @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$. – Garrett Mar 29 at 5:00
• If the solution is $\mathbf x = \mathbf c / ||\mathbf c||$, that's great; we're done. But that's not the interesting case. – Garrett Mar 29 at 5:02
• Could we assume the norm of $\boldsymbol{c}$ is 1? Have you looked at my solution? – Royi Apr 11 at 23:53

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