4
$\begingroup$

I'm trying to solve the below min-max nonlinear integer programming problem with the following objective functions: $$\min_{x_i,y_i} \max_i \left\{\frac{x_i}{2+3y_i} + \frac{2x_i}{4+7y_i}\right\} \\ \text{subject to some linear and non-linear constraints}$$ Now, to solve this problem, I'm converting the min-max problem into a minimization problem as follows: $$\min_{x_i,y_i,z} z \\ \text{subject to } z \geq \left\{\frac{x_i}{2+3y_i} + \frac{2x_i}{4+7y_i}\right\},\forall i \\ \text{previous linear and non-linear constraints}$$ When I'm using a commercial solver to solve this reformulated problem, I'm getting a solution. However, I'm not sure if both these solutions are the same as this can be guaranteed for a linear or convex problem.

$\endgroup$
1
  • 3
    $\begingroup$ Note that you are using the term multi-objective incorrectly. You only have one objective (which happens to involve a function called max). Multi-objective optimization is something different. $\endgroup$ Mar 8, 2022 at 17:50

1 Answer 1

4
$\begingroup$

Whether or not the (continuous relaxation of the) problem is convex, these two formulations are equivalent, meaning they have the same global minimum objective value, and the same argmins (optimal variable values) which achieve that global minimum.

Many optimization modeling systems and solvers automatically reformulate the 1st formulation as the 2nd formulation. The 2nd formulation uses the epigraph formulation of max.

It could be viewed that both of your formulations are single objective models; and to the extent there are "multiple" objective functions, they have already been crunched down to a single objective function by use of max.

That said, if the problems are not solved to global optimality, the "solutions" provided by the solver might differ between the formulations, because one or both of them might not be globally optimal. Even if solutions to both problems are globally optimal, the optimal objective values would be the same, but the argmins produced by the solver might differ between the problems (even changing the order of variables or constraints could cause that to happen).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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