# What is the dual cone of a convex polyhedron?

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\}$$

• Does math.stackexchange.com/questions/1854434/… answer your questions? Commented Jan 22, 2020 at 20:51
• @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.
– user494522
Commented Jan 22, 2020 at 21:04

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\}.$$

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