I want to solve a linear program but with a subset of the variables taken from a unit sphere. That is, given fixed $\textbf{c} \in \mathbb{R}^{n}$, $\textbf{A} \in \mathbb{R}^{m \times (n+k)}$, I want to find variables $\left[ \begin{array}{c} \textbf{x} \\ \textbf{y} \end{array} \right]$ with $\textbf{x} \in \mathbb{R}^k$ and $\textbf{y} \in \mathbb{R}^n$ so that

$\min~~\textbf{c}^T \textbf{y}$

$s.t.~~\textbf{A} \left[ \begin{array}{c} \textbf{x} \\ \textbf{y} \end{array} \right] \geq 0$

$and~~~~\|\textbf{x}\|_2 = 1$.

Introducing the equality constraint on the norm of $\textbf{x}$ makes the problem a (non-convex) quadratically-constrained linear program. My understanding is that problems with non-convex constraints are not easy to solve in the general case (e.g., solving a general QCQP is an NP-hard problem).

That said, this problem has some structure to it --- the objective function is linear, and in particular the only quadratically constrained variables $\textbf{x}$ do not (explicitly) appear in the objective function.

With that in mind, I have two questions:

(1) Is this problem type a well-studied sub-problem of some sort? It seems like the unit-vector constraint is common enough that the problem type might be studied in its own right (e.g. linear program, over a unit sphere). Can this be converted to a well-studied problem type (e.g. a semidefinite program) that has an efficient solution?

(2) Regardless of the answer to (1), is there a good approach to solving this optimization problem? An efficient means of solving it or obtaining a good approximation?

I'd be grateful for any insight. Thank you!

  • 1
    $\begingroup$ If you replace $\|\mathbf{x}\|_2 = 1$ with $\|\mathbf{x}\|_2 \leq 1$, you can rewrite as a (convex) semidefinite program. $\endgroup$ – Rodrigo de Azevedo Jul 29 '19 at 8:30
  • $\begingroup$ I had known about this technique but didn't mention it because for my specific problem, the optimum over the unit-ball does not lie on the unit sphere, and I specifically need $\textbf{x}$ on the sphere itself. Is there a way to use this relaxation to find optima on the sphere itself? Perhaps by modifying the cost function to penalize smaller $\|\textbf{x}\|$ ? Something like $\textbf{c}^T \textbf{y} - \gamma \| \textbf{x} \|_2$ for some $\gamma$ ? $\endgroup$ – kklosteer Jul 29 '19 at 21:25
  • $\begingroup$ Seems related: google.com/url?sa=t&source=web&rct=j&url=http://… $\endgroup$ – user35593 Apr 19 '20 at 10:48

Going by the first comment, the optimal solution to the convex problem (= replaced by $\leq$) must give a solution on the unit sphere. Firstly, Since $\{0,0\}$ is a feasible point, the optimal value cannot be positive. It can either be $0$ or negative. If its zero, an optimal solution can be scaled to lie on the unit sphere. So it suffices to check for negative case.

Now suppose $||x^*||=\delta<1$ for an optimal solution $\{x^*, y^*\}$. One can then choose the feasible point $\{\frac{1}{\delta}x^*,\frac{1}{\delta}y^*\}$, which has a smaller cost. This is a contradiction to the assumption of optimality.

  • $\begingroup$ Nice! Great solution, thank you. $\endgroup$ – kklosteer Apr 19 '20 at 22:50

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.