I have the following basic linear optimization problem. Let $A \in \mathbb{R}^{n,n},c\in \mathbb{R}^n$, then solve $$\inf_{x \in \mathbb{R}^n} c^Tx,\ \text{ s.t. }\begin{cases}A^Tx=c \\x_i \geq 0, i=1,..,n.\end{cases} $$ According to my lecture notes, the dual problem is this:
$$\sup_{y\in\mathbb{R}^n}c^Ty, \quad \text{, s.t. } Ay\leq b.$$
Now, when I try to derive this formula by myself, I get something different. First I set $$L(x,u,v)= c^Tx + u^T(A^Tx-c) + v^Tx =(c^T + u^TA^T + v^T)x -u^Tc.$$ Then minimizing w.r.t. $x$ needs that $$0\overset{!}{=}\frac{\partial L }{\partial x}(x,u,v)= (c^T + u^TA + v^T).$$
The dual function is then $$q(u,v) = \inf_{x \in \mathbb{R}^n} L(x,u,v) = \begin{cases}-u^Tc,\quad (c^T + u^TA + v^T)=0\\-\infty, \quad \text{else}\end{cases}$$
Then I get the dual problem as $$\sup_{u,v} -u^Tc, \text{ s.t. } (c + Au + v)=0$$ This does not look a lot like the problem from my notes. E.g. there is no inequality in the dual problem. Also I wonder about the multiplier $v$, that does only appear in the condition of my dual problem. Thanks!
There s a sign constraint for $v \le 0$ so that the Lagrangian is a lower bound of the original objective function.
Let $-u=y$, then we have $\sup_{u,v} y^Tc$ in our dual with the constraint:
$$c+Au+v=0$$ Since $v \le 0$, it can be written as $c+Au \ge 0$. $$Au \ge -c$$ $$-Ay \ge -c$$
$$Ay \le c$$