1
$\begingroup$

Let $A$ be an $m \times n$ matrix (over $\mathbb{R}$), $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$ and $K \subseteq \mathbb{R}^n $ is a closed, convex, pointed cone with non-empty interior. We define a conic program to be $$ \min_{x\in \mathbb{R}^n} c^Tx \\ \text{subject to } Ax = b , x\in K$$

Furthermore, define the dual problem to be $$ \max_{y\in \mathbb{R}^m, z \in \mathbb{R}^n} b^Ty \\ \text{subject to } c = z + A^Ty, z \in K^*$$ where $K^*$ is the dual cone of $K$.

Question: Is the dual problem also a conic program (by the definition given)? If I try the obvious solution where $(y,z) \in \mathbb{R}^m \times K^*$, then the issue is that $\mathbb{R}^m \times K^*$ is a closed convex cone with non-empty interior but is not pointed. How can I get around this?

Thank you.

Edit: To clarify, a cone is defined as a set $K \subseteq \mathbb{R}^n$ satisfying $x \in K \implies ax \in K$ for all $a \geq 0$. A cone is pointed if it satisfies $K \cap (-K) = \{0\}.$

$\endgroup$
  • 1
    $\begingroup$ Out of curiosity, what reference are you using that defines conic programs to be defined over pointed cones? $\endgroup$ – David M. Mar 19 at 23:56
  • $\begingroup$ This is from lectures in a course I'm following – unsure what reference the lecturer is following. They assume K is a proper cone when defining conic programs. Here proper cone is defined to be closed, convex, pointed cone with non-empty interior as stated in my question. $\endgroup$ – dstivd Mar 20 at 0:08
  • $\begingroup$ @DavidM. Is this definition of conic programs unusual? $\endgroup$ – dstivd Mar 20 at 0:08
  • $\begingroup$ I don’t do much conic programming, but I checked Wikipedia, and they don’t define it this way. If you don’t require $K$ to be pointed, your problem goes away. $\endgroup$ – David M. Mar 20 at 0:09
  • $\begingroup$ Why do you think that $\mathbb R^m \times K^*$ isn't pointed? $\endgroup$ – user251257 Mar 20 at 0:23
2
$\begingroup$

The dual program is equivalent to a conic program, by applying following transformations

  1. Replace $y\in\mathbb R^m$ with $y=u - v$ for $u,v\in\mathbb R^m_+$ (cone of non-negative orthant).
  2. Replace $\max ...$ with $-\min -(...)$.

Finally, we obtain the following equivalent conic program, that is we can map the feasible points of both programs into other (not necessarily bijectively) and we can map the optimal points of both programs into other:

$$ \min_{(u,v,z)} \; \begin{bmatrix}-b \\ b \\ 0 \end{bmatrix}^T \begin{bmatrix}u \\ v \\ z \end{bmatrix} $$ $$ \text{s.t. } \begin{bmatrix}A^T & -A^T & I\end{bmatrix} \begin{bmatrix}u \\ v \\ z \end{bmatrix} = c, \; \begin{bmatrix}u \\ v \\ z \end{bmatrix}\in\mathbb R^m_+ \times \mathbb R^m_+ \times K^*$$

Notes:

  • If $y$ is given, then we can take $u = \max(y, 0)$ and $v = \max(-y, 0)$ component-wise.
  • We can think of $u$ as the "positive" part of $y$ and $v$ as the "negative" part of $y$.
$\endgroup$
  • $\begingroup$ Nice trick. This is indeed a conic program by my definition I think. Thank you! $\endgroup$ – dstivd Mar 20 at 1:29

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.