2
$\begingroup$

A convex polyhedron is defined as $P=\{x \in \mathbb{R}^n \mid Ax \geq b\}$. On the other hand, the dual cone of any set $S$ is defined as $S^{*}=\{ y \in \mathbb{R}^n \mid x^{\top}y \geq 0 \,\,\,\,\,\forall x \in S\}$.

Question: what is the dual cone of $P$? or how can we characterize $P^{*}$ in terms of $A$ and $b$.

$$ P^{*}=\{ y \in \mathbb{R}^n \mid x^{\top}y \geq 0 \,\,\,\,\,\forall x \in P\} $$

$\endgroup$
2
  • 1
    $\begingroup$ Does math.stackexchange.com/questions/1854434/… answer your questions? $\endgroup$ Commented Jan 22, 2020 at 20:51
  • $\begingroup$ @Steven Stadnicki: no. it does not characterize the set based on what I want in this problem ($A$ and $b$). I want to know once we are given $A$ and $b$ how we can characterize the dual cone based on them. $\endgroup$
    – user494522
    Commented Jan 22, 2020 at 21:04

1 Answer 1

1
$\begingroup$

Here is an optimization take, using (strong) Lagrange duality. Let $ C = \{x: Ax \ge b\} $ and let $\delta_C$ denote the convex analysis indicator of $C$, that is, $\delta_C(x) = 0$ if $x \in C$ and $=\infty$ if $x \notin C$.

Consider the optimization problem: \begin{align*} \phi(y) &= \inf_{Ax \ge b} x^T y \\ &= \inf_{x \in \mathbb R^n} x^T y + \delta_C(x), \\ &\stackrel{(a)}{=} \inf_{x \in \mathbb R^n} \,\sup_{\lambda \ge 0} \big[ x^Ty + \lambda^T (b-Ax) \big] \\ &\stackrel{(b)}{=} \sup_{\lambda \ge 0}\inf_{x \in \mathbb R^n}\big[ x^Ty + \lambda^T (b-Ax) \big] \\ &= \sup_{\lambda \ge 0}\big[ \lambda^T b + \inf_{x \in \mathbb R^n} x^T(y - A^T \lambda) \big] \\ &\stackrel{(c)}{=} \sup_{\substack{\lambda \ge 0, \\ A^T \lambda = y}} \lambda^T b \end{align*}

  • Step (a) is the common way of encoding inequlity constraints as part of the objective function. Note that $$ \sup_{\lambda \ge 0} \lambda^T (b-Ax) = \begin{cases} 0 & b - Ax \le 0 \\ \infty & \text{otherwise} \end{cases} = \delta_C(x) $$ for the $C$ defined above. (If one of the coordinates of $b-Ax$ is positive, you can send the corresponding coordinate of $\lambda$ to $\infty$.)

  • Step (b) is the strong duality.

  • Step (c) is obtained by noting that unless $y-A^T\lambda = 0$, the $\inf$ over $x$ evaluates to $-\infty$, hence these values of $\lambda$ can be dropped when considering the outer $\sup$ optimization.

The dual cone is characterized by $\phi(y) \ge 0$. The above dual expression for $\phi$ says that $y$ belongs to the dual cone if and only if there exists $\lambda \ge 0$ such that $y = A^T\lambda$ and $\lambda^T b \ge 0$. That is $$P^* = \{ A^T \lambda \mid \lambda \ge 0, \;\lambda^T b \ge 0\}.$$

$\endgroup$
2
  • $\begingroup$ can you tell me how you get second line form first line with equality? $\endgroup$
    – user494522
    Commented Jan 22, 2020 at 22:06
  • $\begingroup$ @Saeed, I have added some more details on that step. $\endgroup$
    – passerby51
    Commented Jan 23, 2020 at 6:15

You must log in to answer this question.