Derive the dual problem $\min_{x,y}\max_{i=1,\dots, m}y_{i}$ such that $\ a_{i}^{\intercal}x+b_{i}\leq y_{i}, i=1,\dots, m.$

Question

Consider the following programming problem: $$\min_{x\in\mathbb{R}^{n},y\in\mathbb{R}^{m}}\max_{i=1,\dots, m}y_{i}$$ $$s.t.\ a_{i}^{\intercal}x+b_{i}\leq y_{i}, i=1,\dots, m.$$ I want to derive the Lagrangian dual function of this problem: $$L(x,y,\lambda)=\sum_{i=1}^{m}\lambda_{i}b_{i}+\Big(\sum_{i=1}^{m}\lambda_{i}a_{i}^{\intercal}\Big)x+\max_{i=1,\dots, m}y_{i}-\sum_{i=1}^{m}\lambda_{i}y_{i},$$ so that the dual function \begin{align*} \phi(\lambda)=\sum_{i=1}^{m}\lambda_{i}b_{i}+\inf_{x\in\mathbb{R}^{n}}\Big[\Big(\sum_{i=1}^{m}\lambda_{i}a_{i}^{\intercal}\Big)x\Big]+\inf_{y\in\mathbb{R}^{m}}\Big(\max_{i=1,\dots, m}y_{i}-\sum_{i=1}^{m}\lambda_{i}y_{i}\Big). \end{align*}

For the first inifimum, it is easy to see that $$ \inf_{x\in\mathbb{R}^{n}}\Big[\Big(\sum_{i=1}^{m}\lambda_{i}a_{i}^{\intercal}\Big)x\Big]= \begin{cases} 0,\ \text{if}\ \sum_{i=1}^{m}\lambda_{i}a_{i}^{\intercal}=0\\ -\infty,\ \text{otherwise}. \end{cases} $$

However, I got stuck at how to derive the condition for the second infimum to not be $-\infty$. The only thing I can think of is that $$\max y_{i}-\sum_{i=1}^{m}\lambda_{i}y_{i}\geq \max y_{i}(1-\sum_{i}\lambda_{i}).$$ However, this lower bound is not sufficient to guarantee $\max y_{i}-\sum_{i=1}^{m}\lambda_{i}y_{i}$ to be bounded from below. What am I missing?

---

To provide context, this problem is equivalent to $$\min_{x\in\mathbb{R}^{n}}\max_{i=1,\dots, m}(a_{i}^{\intercal}x+b_{i})$$ which is then also equivalent to $$\min_{x\in\mathbb{R}^{n},t\in\mathbb{R}}t$$ $$\text{subject to}\ a_{i}^{\intercal}x+b_{i}\leq t,\forall\ i=1,\dots, m.$$

By using the second equivalent form, it is easy ot see that $\sum_{i=1}^{m}\lambda_{i}=1$ must hold. This brings me the interest to look at the equivalent form at the start of this post. Since they are all equivalent, they should have the same dual problem. But why can't I derive the same condition using the first form? (Due to the equivalence and my particular problem, please do not change the form of the first programming problem. It simplifies the problem as my third equivalent form, but it is not in my interest.)

Answer 1

In case it helps, you can rewrite the epigraph formulation in standard form for linear programming (LP): minimize $t$ subject to \begin{align} -\sum_{j=1}^n a_{ij} x_j + t &\ge b_i &&\text{for $i\in\{1,\dots,m\}$} \\ x_j &\text{ free} &&\text{for $j\in\{1,\dots,n\}$} \\ t &\text{ free} \end{align} The dual LP problem is to maximize $\sum_{i=1}^m b_i \lambda_i$ subject to \begin{align} -\sum_{i=1}^m a_{ij} \lambda_i &= 0 &&\text{for $j\in\{1,\dots,n\}$} \\ \sum_{i=1}^m \lambda_i &= 1 \\ \lambda_i &\ge 0 &&\text{for $i\in\{1,\dots,m\}$} \end{align} Notice that if all $a_{ij}$ have the same sign for some $j$, the dual is infeasible and the primal is unbounded. Did you maybe mean for $x$ to be nonnegative?

Answer 2

You can write $\inf_y \{\max\limits_i y_i - \sum\limits_{i = 1}^m \lambda_i y_i \}$ as $$\sup_y\{\sum_{i = 1}^m \lambda_i y_i - \max\limits_i y_i\} = \sup_y\{\lambda^T y - \max_i y_i\} = f^*(\lambda)$$ where $f^*(\lambda)$ is the conjugate function. You can then show that $f^*(\lambda)$ is $0$ if $\sum \lambda_i = 1$ and $+\infty$ otherwise.