Conic representation of convex hull of unit ball and point

146 Views Asked by At

Let $S = \mathrm{conv}(B \cup p)$ where $B = \{x \in \mathbb{R}^2 | x^Tx \leq 1 \}$ and $p = (-2,0)$

Can this set be represented in conic form $Ax \preceq_{\mathcal{K}} b$ where $\mathcal{K}$ is $\mathcal{K}_+ \times \mathcal{K}_{SOC}$ ? That is, can it be represented as the intersection of linear and second-order cone constraints, possibly by introducing additional variables ?

I can represent the set using its support function as: $$\sigma_S(a) = \{\mathrm{sup}\, a^Tx \,| x \in S\} = \text{max}(a^Tp, ||a||_2)$$

Using this representation you can determine if another set $C$ is a subset of $A$ using the following: $$C \subseteq S \iff \sigma_C(a) \leq \sigma_B(a) \, \forall \, a $$

Querying if a point $x^*$ belongs to $S$ can then be solved using an SOCP which implements the above condition. However, I'd like to know if you can represent $S$ as the intersection of conic inequalities so membership just involves evaluating $Ax^* \preceq_\mathcal{K} b$ without solving an optimization problem.

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

Answering my own question after doing some reading and finding the solution in [1]. By using the perspective of the quadratic constraint function we can represent the convex hull using only linear and second-order cone constraints.

We first introduce new variables (a lifting), $s_1, s_2 \in \mathbb{R}, z_1, z_2 \in \mathbb{R}^2$. Then the following constraints ensure $x \in S$.

$$\begin{align} x = z_1 + z_2 \\ ||z_1|| \leq s_1 \\ z_2 = s_2p \\ s_1 + s_2 = 1 \\ s_1 \geq 0 \\ s_2 \geq 0 \\ \end{align} $$

The $s_1 \geq 0$ constraint is redundant due to the norm constraint, but I left it in for clarity when comparing to the general case discussed in [1].

As an aside, it appears YALMIP utilizes this lifting approach to represent the convex hull as well [2].

[1] Boyd & Vandenberghe - Convex Optimization (p.207, Exercise 4.56)

[2] https://yalmip.github.io/command/hull/