4
$\begingroup$

The non-convex multi-objective optimization problem in my case is defined below:

  • Objective 1: Minimize $f_1(X_1,X_2)=C_0+C_1(1/X_1)+C_2(X_2/X_1)+C_3X_1+C_4X_2+C_5(X_2^2/X_1)$

  • Objective 2: Minimize $f_2(X_1,X_2)=D_1X_1+D_2X_2+D_3X_1^2+D_4X_2^2+D_5X_1X_2$

  • Objective 3: Minimize $f_3(X_2)=-E_1X_2$

  • Constraint 1: $ 0 \le X_1 \le A_1$

  • Constraint 2: $ 0 \le X_2 \le A_2$

  • Constraint 3: $ X_1 + X_2 \le A_3$

Here, $C_1,C_2,C_3,C_4,C_5,D_1,D_2,D_3,D_4,D_5,E_1,A_1,A_2$ and $A_3$ are positive constant numbers. $X_1$ and $X_2$ are decision variables.

I want to linearize the objective functions and solve it using LP or MILP solvers for global optimization of $X_1$ and $X_2$. However, I am not sure what is the best method to linearize. For instance, with separable programming I am facing issues with number of breaking points.

Also, I have tried using evolutionary algorithms like MOPSO and NSGA-II for finding global optimum solutions. However, I want to explore if I can reduce the non-linear objective functions to linear and find global optimum solutions with less computation time.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I would think that a better approach is to use a global nlp solver. $\endgroup$
    – Erwin Kalvelagen
    Sep 29, 2021 at 20:59
  • $\begingroup$ @ErwinKalvelagen Are you aware of any multi-objective global NLP "solvers" that are actual solver and not just evolutionary algorithms, because i am not. $\endgroup$
    – worldsmithhelper
    Sep 29, 2021 at 22:06
  • $\begingroup$ @vp_050 how long do the evolutionary algorithms take to arrive an acceptably good approximation of the pareto front? $\endgroup$
    – worldsmithhelper
    Sep 29, 2021 at 22:26
  • 1
    $\begingroup$ If one does that one would need to use an epsilon-constraint method as varying the weights of a convex combination of objectives doesn't always generates the pareto frontier which i think would apply here. See MOP Myth 2 in Myths and Counterexamples in Multiple-Objective Programming by Harvey J. Greenberg. $\endgroup$
    – worldsmithhelper
    Sep 29, 2021 at 23:11
  • 1
    $\begingroup$ @worldsmithhelper I really only use the converse: any point found with a weighted objective is Pareto efficient. The algorithm can be "find a point, add no-domination constraints, find a new point etc. Continue until the model becomes infeasible, This is a well-known algorithm (mostly for linear models, but it can be used for nonlinear models as well, even if non-convex). We "fill" the holes because of the constraints. $\endgroup$
    – Erwin Kalvelagen
    Oct 21, 2021 at 14:57

1 Answer 1

Reset to default
3
$\begingroup$

One traditional method to linearize multi-linear/polynomial constraints are McCormick envelopes, which are refined over time. Here is a great resource on those. A single objective solver that uses them and improves them in an interesting way is Alpine to get an quick idea whether you could adapt ideas from it for you i would recommend this 22 minute presentation. Using McCormick relaxations would require solving a series of multi objective MILP problems. Finding new minimas of the and refining the linear relaxation there. Alpine doesn't support all the terms you have in your problem but lower bounds necessary to construct these envelopes could also be found using interval arithmetic for the division in $f_1$, and additive terms $D_3X_1^2$, $D_4X_2^2$.

I am not aware of any turn key solutions. One could also write a branch and bound solver which just uses interval arithmetic and handles the linear objective seperatly.

Improve this answer
$\endgroup$

Your Answer

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