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.
-
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$– Johan LöfbergMar 8, 2022 at 17:50
1 Answer
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).