Could someone guide me through how I could go about finding the dual of the following LP. Let $A \subset \Bbb R^{m x n}$, and $x = (x_1, ..., x_m)$.
$$\text{max } z \\ \text{st } z \le x^TA_{.j} , \forall j \in \{1, \ldots, m\} \\ x_1 + \ldots + x_m = 1 \\ x \ge \vec{0} $$
, where $A_{.j}$ represents the j'th column of A.
My confusion is coming from the fact that in this case, $A$ is a constant matrix, but all the $x_i$'s are variables; as is z. So I can't see how I can apply the standard primal-dual conversion.
Thanks!
You could define $x'=\begin{pmatrix}x \\ z\end{pmatrix}$, then the problem is: $$\begin{align} \max \quad & \begin{pmatrix}0 \\ 0 \\ \vdots \\ 0 \\ 1\end{pmatrix}^T x' \\ \text{s.t.} \quad & \begin{pmatrix} A^T & -e \\ e^T & 0 \\ -e^T & 0\end{pmatrix}x' \leq \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ 1 \\ -1\end{pmatrix} \\ & x' \geq 0. \end{align}$$ Deriving the dual is now simple.