Projection onto a Polyhedral Cone as Minimization of Different Norms

Question

Let $\mathbf c \in \mathbb{R}^n$ where $\mathbf c \neq \mathbf 0$. Let $\mathbf A \in \mathbb{R}^{m \times n}$. Finally, let $p \in \mathbb 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} \min_{\mathbf x \in \mathbb{R}^n} & && \|\mathbf c - \mathbf x\|_p \\ \text{s.t.} & && \mathbf A \mathbf x \geq \mathbf 0, \\ & && \mathbf x\geq \mathbf 0. \\ \end{aligned} \end{equation}

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

Right now, I am not too concerned about the value of $p$ (i.e., what type of norm we are minimizing). I'd be interested in a solution for $p = 1$, $p = 2$, or $p = \infty$. I know that for $p = 1$ and $p = \infty$ this can be reformulated as a linear program. However, given that the linear program has special structure, I'm wondering if there is a more efficient way to solve it than applying a generic linear programming algorithm.

Answer 1

I think that for the case $ p = 1 $ any modern LP solver be as efficient as you think of since it will be the canonical form of LP.

For $ p = 2 $ you have the Orthogonal Projection problem which is a special case of Orthogonal Projection onto the Intersection of Convex Sets.

All needed is to write the Matrix Inequality as a form of set of Orthogonal Projection onto a Half Space.

I wrote a proof of concept using MATLAB with 2 methods:

1. Quadratic form of the Hybrid Steepest Descent (See Quadratic Optimization of Fixed Points of Non Expensive Mappings in Hilbert Space).
2. Consensus ADMM method which is related to the Dykstra Projection algorithm.

I must add that I think an optimized Interior Points solver might be faster than each of them.

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