1
$\begingroup$

I have a question concerning the formulation of a linear programmign task. I am trying fo find $x^* \in argmax_{x \in R^n}\{ a_1x_1 + a_2x_2, a_2x_2 + a_3x_3 + a_4x_a, a_4x_4 + a_5x_5 \}$, subject to $\sum_{i=1}^5 x_i = 3000, x_i \geq 0$, where $a_i$ are some coefficients $\in R$.

This can be formulated as a linear programming task like this:

\begin{equation} (x^*, \lambda^*) \in argmin_{x, \lambda} -\lambda \end{equation} Subject to:

\begin{equation} \begin{aligned} a_1x_1 + a_2x_2 \geq \lambda \\ a_2x_2 + a_3x_3 + a_4x_4 \geq \lambda \\ a_4x_4 + a_5x_5 \geq \lambda \\ \sum_{i=1}^5 x_i = 3000 \\ x_i \geq 0 \end{aligned} \end{equation}

I intuitively know, why I formulate it like this and that lambda is the "worst case" scenario (minimum value of my criterial function). What I would like to know is how exatly formally write why is the LP formulation equivalent to the first formulation I provided (what did I do to the first equation to get the LP one). Thanks in advance!

  • 0
    I know what the $\text{arg}\,\max$ of a function is, but what's the $\text{arg}\,\max$ of a set?2012-11-24

1 Answers 1

1

Let $C=\{x | x_i\geq 0,\, \sum_i x_i = 3000 \}$ (note $C$ is compact so we can write $\max, \min$ below) and $\psi(x)= \max (a_1x_1 + a_2x_2, a_2x_2 + a_3x_3 + a_4x_a, a_4x_4 + a_5x_5)$.

Then the original problem is $\alpha= \max_{x \in C} \psi(x)$ and the modified problem is $\alpha'= \max_{x\in C, \lambda \in \mathbb{R}} \{ \lambda | \lambda \leq \psi(x) \}$

If $x \in C$ we have $\psi(x) \leq \alpha$, which gives $\alpha' \leq \alpha$ (since $\{\lambda | \lambda \leq \psi(x)\} \subset \{\lambda | \lambda \leq \alpha\}$).

Furthermore, since $\{\psi(x)\}_{x \in C} \subset \{\lambda | \lambda \leq \psi(x) \}_{x\in C, \lambda \in \mathbb{R}}$, it is clear that $\alpha \leq \alpha'$. Hence $\alpha = \alpha'$.

Finally we notice $\max_{x\in C, \lambda \in \mathbb{R}} \{ \lambda | \lambda \leq \psi(x) \} = -\min_{x\in C, \lambda \in \mathbb{R}} \{ -\lambda | \lambda \leq \psi(x) \}$, and that $\lambda \leq \psi(x)$ iff $\lambda \leq a_1x_1 + a_2x_2$, $\lambda \leq a_2x_2 + a_3x_3 + a_4x_a$ and $\lambda \leq a_4x_4 + a_5x_5$.