Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
I know what the $\text{arg}\,\max$ of a function is, but what's the $\text{arg}\,\max$ of a set? –  littleO Nov 24 '12 at 18:17
add comment

1 Answer

up vote 1 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.