I have rewritten a max-min problem as a unique maximisation problem using strong duality. I have built a Matlab code which seems to show that my derivations are wrong. However, the code itself may be wrong. Therefore, I would like your help to firstly understand whether the math below is correct.
This is the original problem (1)
\begin{equation}
\begin{alignedat}{3}
\max_{b\in \mathbb{R}^{L}} &&& \min_{\substack{\text{$Z_1\in \mathbb{R}^{L+1}$}\\ \text{$Z_2\in \mathbb{R}^{K}_{\geq 0}$}}}
\Big[b^T \text{ } \text{ } \text{ }0 \text{ } \text{ } \text{ }0_{K}^T\Big] Z,\\
\text{s.t. } &&& b^Tb\leq 1, \\
&&& A_{\text{eq}}\text{ }Z = B_{\text{eq}},\\
&&& A_{\text{ineq}} \text{ }Z \leq 0_{d_{\text{ineq}}},
\end{alignedat}
\end{equation}
where: $Z\equiv (Z_1, Z_2)$ is an $(L+1+K)\times 1$ vector; $O_K$ is a $K\times 1$ vector of zeros; $d_{\text{ineq}}$ is the number of rows of $\text{A}_{\text{ineq}}$; $d_{\text{eq}}$ is the number of rows of $\text{A}_{\text{eq}}$ (used below); $0_{d_{\text{ineq}}}$ is a $d_{\text{ineq}}\times 1$ vector of zeros; $ \mathbb{R}^{K}_{\geq 0}$ is the $K$-dimensional Euclidean space of positive numbers.
Now, I transform the inner minimisation problem into a maximisation problem using strong duality and obtain problem (2).
\begin{equation}
\begin{alignedat}{3}
\max_{\substack{\text{$b\in \mathbb{R}^{L}$} \\ \text{$\lambda_{\text{eq}}\in \mathbb{R}^{d_{\text{eq}}}$} \\ \text{$\lambda_{\text{ineq}}\in \mathbb{R}^{d_\text{ineq}}_{\geq 0}$}}} &&& \Big[ -B_{\text{eq}}^T \text{ } \text{ } \text{ }0_{d_{\text{ineq}}}^T\Big] \lambda,\\
\text{s.t. } &&& b^Tb\leq 1, \\
&&& [A^T]_{1:|L|}\text{ } \lambda = \begin{pmatrix}-b\\ 0\end{pmatrix},\\
&&& -[A^T]_{L+1:\text{end}} \text{ }\lambda \leq 0_{K},
\end{alignedat}
\end{equation}
where: $\lambda\equiv (\lambda_{\text{eq}}, \lambda_{\text{ineq}})$ is a $(d_{\text{eq}}+d_{\text{ineq}})\times 1$ vector; $A$ is the $(d_{\text{eq}}+d_{\text{ineq}})\times( L+1+K)$ matrix obtained by stacking one on top of the other the matrices $A_{\text{eq}}$ and $A_{\text{ineq}}$, and $[A]_{i:j}$ denotes the sub-matrix of $A$ containing the rows $i,i+1,…,j$ of $A$.
If I have applied correctly strong duality, then the value of (1) is equal to the value of (2). Are my derivations correct?
Best Answer
Let $A\in\mathbb{R}^{m\times n}$ and $C\in\mathbb{R}^{p\times n}$ and consider the linear program in general form $\inf\{c^\top z : Az = b, Cz \le d, z\in\mathbb{R}^n\}$. Then Lagrangian is \begin{equation*} L(z,\lambda,\mu) = c^\top z + \lambda^\top(Az-b) + \mu^\top(Cz - d), \end{equation*} where $\mu\ge 0$. This is affine in $z$, and therefore the dual function is \begin{align*} g(\lambda,\mu) = \inf_{z\in\mathbb{R}^n}L(z,\lambda,\mu) = \begin{cases} -b^\top \lambda - d^\top\mu &\text{if $c+A^\top \lambda + C^\top\mu = 0$}, \\ -\infty & \text{otherwise}. \end{cases} \end{align*} Therefore, the dual problem becomes \begin{align*} &\text{maximize}&& -b^\top\lambda - d^\top \mu \\ &\text{subject to}&&c+A^\top\lambda + C^\top\mu = 0, \\ &&&\mu \ge 0, \end{align*} where the optimization variables are $\lambda\in\mathbb{R}^m$ and $\mu\in\mathbb{R}^p$.
Now, let's transform your inner linear program into the general form above. The objective is $f(z) = (b,0_{K+1})^\top z$, so $c = (b,0_{K+1})$. The equality constraint is $A_\text{eq}z = B_\text{eq}$, so $A=A_\text{eq}$ and $b=B_\text{eq}$. Finally, the inequality constraint is $A_\text{ineq}z \le 0_{d_\text{ineq}}$, so $C = A_\text{ineq}$ and $d = 0_{d_\text{ineq}}$. Putting these into our dual problem above, we find that the dual to the inner minimization is \begin{align*} &\text{maximize}&& -B_\text{eq}^\top \lambda - 0_{d_\text{ineq}}^\top \mu \\ &\text{subject to}&& \begin{bmatrix}b \\ 0_{K+1}\end{bmatrix} + A_\text{eq}^\top\lambda + A_\text{ineq}^\top\mu = 0, \\ &&& \mu\ge 0, \end{align*} which looks similar to your dual. I see one major difference: your dual should enforce the constraint that the dual variables associated with the primal inequality are nonnegative, i.e. $\mu\ge 0$. In your formulation, it looks like you are using $A_\text{ineq}^\top \mu \ge 0$ instead. In general, this will not suffice to constrain $\mu\ge 0$. If you already have code solving your dual problem, I suggest checking whether the resulting optimal dual variable $\mu^*$ is indeed elementwise nonnegative. If it's not, try fixing the constraint as outlined above. Hope this helps!