# Maximization of minimum difference

Suppose we have a function of the form: $(x_1 - x_2) + (x_3 - x_4) + (x_5 - x_6)$ and we have maximized this summation using linprog (using some constraints which are not important for this matter). This provides us with a value for the different x variables.

The problem I now want to solve is the maximization of the minimum $(x_i - x_j)$ and with the constraint that the solution $(x_1, x_2, ...)$ filled in in the original summation should have a higher or the same value (constraint).

This would distribute the difference between the variables $x_1,x_2; x_3,x_4, ...$

How can this problem be solved in Matlab (maximization of the minima)?

In order to maximize a minimum using linear programming techniques, you can introduce an additional variable $\delta$ and add constraints of the form
$$x_i-x_j\ge \delta$$
The variable $\delta$ must then be maximized. For your problem to be well-defined there should of course be additional constraints on the variables $x_i$, probably like the ones you used in the first problem.
• If only $\delta$ needs to be maximized, your objective function looks like $f^Tx$, where $x$ is the vector with your variables. If $\delta$ is the first element of vector $x$, then $f=[-1,0,\ldots,0]$ because $\tt{linprog}$ minimizes (instead of maximizes) the objective function, i.e. you're now minimizing $-\delta$. – Matt L. May 25 '13 at 19:15