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.

  • $\begingroup$ Any idea on how to maximize this new variable in Matlab? I tried using linprog but did not succeed (I didn't know what function to use). $\endgroup$ – Dayrush May 25 '13 at 19:08
  • 1
    $\begingroup$ 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$. $\endgroup$ – Matt L. May 25 '13 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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