Dual optimization problem for standard linear programming

Question

Let $K$ be a proper convex cone. Let's have a cone problem

$$ \text{min } \textbf{c}^T\textbf{x} \\ \text{s.t. } A\textbf{x} =\textbf{b}\\\textbf{x}\succeq_K \textbf{0} $$

How to derive the dual program for this one? Thx

I know that when solving duals one works with the Lagrange dual function - but in this case, I have troubles because of the cone inequality.

Answer 1

Notice:

If $K$ is a proper cone, we have:

$$\mathbf{x} \succeq_{K} \mathbf{y} \text{ if and only if } \boldsymbol{\lambda}^T \mathbf{x} \geq \boldsymbol{\lambda}^T \mathbf{y} \text{ for all } \boldsymbol{\lambda} \in K^*,$$ where $K^*$ is the dual cone of $K$.

Suppose the generalized inequality is the component wise inequality defined by $K = \mathbb{R}_+^n$. For the standard linear programming (LP) problem we have:

\begin{aligned} & \min_{\mathbf{x} \in \mathbb{R}^n} && \hspace{-1mm} \mathbf{c}^T \mathbf{x} \\ & \hspace{2mm} \text{s.t.} && \hspace{-4mm} \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \text{} && \hspace{-2mm} \mathbf{x} \succeq \mathbf{0} \end{aligned}

The Lagrangian can be written as

\begin{aligned} \mathcal{L}(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\nu}) &= \mathbf{c}^T \mathbf{x} - \boldsymbol{\lambda}^T \mathbf{x}+ \boldsymbol{\nu}^T(\mathbf{A}\mathbf{x}-\mathbf{b}) \\ &= (\mathbf{c}-\boldsymbol{\lambda}+\mathbf{A}^T\boldsymbol{\nu})^T \mathbf{x} - \mathbf{b}^T \boldsymbol{\nu}. \end{aligned}

As it is clear $\mathcal{L}$ is an affine function over $\mathbf{x}$ and hence it is unbounded below except for the case $\mathbf{c} \boldsymbol{\lambda}+\mathbf{A}^T\boldsymbol{\nu} = \mathbf{0}$. Thus, the dual function is

\begin{aligned} g(\boldsymbol{\lambda},\boldsymbol{\nu}) &= \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\nu}) \\ &= \begin{cases} - \mathbf{b}^T \boldsymbol{\nu} & \quad \text{if:} \;\mathbf{c}-\boldsymbol{\lambda}+\mathbf{A}^T\boldsymbol{\nu} = \mathbf{0}\\ -\infty & \quad \text{otherwise} \end{cases}, \end{aligned}

where $\text{dom } g = \{(\boldsymbol{\lambda},\boldsymbol{\nu})| \; \mathbf{c}-\boldsymbol{\lambda}+\mathbf{A}^T\boldsymbol{\nu} = \mathbf{0}\}$.

Then, the Lagrange dual problem of the LP problem can be obtained as

\begin{aligned} & \hspace{-10mm} \max_{(\boldsymbol{\lambda},\boldsymbol{\nu}) \in \text{dom } g} && \hspace{-1mm} g(\boldsymbol{\lambda},\boldsymbol{\nu}) \\ & \hspace{-3mm} \text{s.t.} && \hspace{-1mm} \boldsymbol{\lambda} \succeq \mathbf{0}, \end{aligned}

and hence the dual problem can be described as \begin{aligned} & \hspace{6mm} \max_{\boldsymbol{\lambda},\boldsymbol{\nu}} && \hspace{-5mm} - \mathbf{b}^T \boldsymbol{\nu} \\ & \hspace{8mm} \text{s.t.} && \hspace{-3mm} \boldsymbol{\lambda} \succeq \mathbf{0} \\ & {} && \hspace{-3mm} \mathbf{c}-\boldsymbol{\lambda}+\mathbf{A}^T\boldsymbol{\nu} = \mathbf{0}. \end{aligned}