1
$\begingroup$

Let $\left\{\begin{matrix} \operatorname{min}_xc^Tx\\Ax\leq b \\ x\in \mathbb{R}^+ \end{matrix}\right.$ be a LP primal problem and $\left\{\begin{matrix} \operatorname{max}_yb^Ty\\A^Ty\geq c \\ y\in \mathbb{R}^+ \end{matrix}\right.$ its dual. Weak duality theorem says that the value of objective function of primal is bounded above by the value of objective function of dual. In fact:

$$c^Tx\leq (A^Ty)^Tx=y^T(Ax)=y^Tb=b^Ty$$

where $A^Ty\geq c \Rightarrow (A^Ty)^T\geq c^T \Rightarrow c^Tx \leq (A^Ty)^Tx$. But applying the dual function to calculate the dual problem of a Conic primal I obtain the contrary sign. Let $K^*$ be the dual cone of non-negative orthant $K\equiv \mathbb{R}_+^n=\begin{Bmatrix} x\in \mathbb{R}^n:x\geq 0 \end{Bmatrix}$. Thus

$$L:\mathbb{R}^n\times\mathbb{R}^m\times K^* \mapsto \mathbb{R} \space \operatorname{s.t} \space L(x,y,s)=c^Tx+\overset{=y(Ax-b) \operatorname{for} Ax-b=0\Leftrightarrow h(x)=0}{\overbrace{y^T(b-Ax)}}-\overset{=s(x) \operatorname{for} x\geq0\Leftrightarrow f(x)\leq0}{\overbrace{s^Tx}}$$

$$\Rightarrow g(y,s)\doteq \operatorname{min}_xL(x,y,s)=\operatorname{min}_xx^T(c-A^Ty-s)+b^Ty=\left\{\begin{matrix} b^Ty \operatorname{if} c-A^Ty-s=0\\ -\infty \operatorname{otherwise} \end{matrix}\right.$$

and for $L(x,y,s)\leq f_0(x)\Rightarrow g(y,s)=b^Ty\leq c^Tx$ with $x\in \begin{Bmatrix} x\in \mathbb{R}^n:Ax=b \end{Bmatrix}\cap K$.

What am I doing wrong? Thanks in advance.

$\endgroup$

1 Answer 1

0
$\begingroup$

Not sure about your conic problem, but for LP you have the roles of $\min$ and $\max$ reversed.

$\endgroup$
1
  • 1
    $\begingroup$ This seems like a comment, not an answer. $\endgroup$
    – LSpice
    Commented Sep 3, 2022 at 19:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .