How to deal with an optimization problem that have a sum of nonlinear functions of Z as a constraint when Z is the quantity to be minimized?

Question

I have to minimize a quantity $Z$ subject to the following constraints:

$$ w_1 + w_2 + w_3 = 1 \tag{1}$$ $$ \frac{f_1(w_1 Z) + f_2(w_2 Z) + f_3(w_3 Z)}{Z} \ge k \tag{2}$$

where $k$ is a known constant. $f_1$, $f_2$, $f_3$ are nonlinear functions that we have empirical curves for. These curves are approximately logarithmic (maybe this can help for the resolution). $w_1$, $w_2$, and $w_3$ are weights whose optimal values are to be arrived at. $Z$ does not depend on the values of $w_1, w_2, w_3$.

I am aware of basic linear programming techniques. However, I was unable to reduce constraint (2) into a linear constraint.

Please note that I have posted a duplicate of this question on SciComp SE.

PS: Solutions that use Python would be ideal. However, I am more interested in the approach rather than the language/package used.

Answer 1

If well understood, w1, w2, w3, and Z are some continuous variables in your mathematical model, while k is a constant. If the functions f1, f2, f3 involved in constraint #2 are continuous and nonlinear, then the only way to proceed to solve the problem by using MILP techniques and solvers is to use piecewise linear approximations of these functions. There is a lot of literature on this. For example, you can have a look at this webpage for a short introduction.

The main drawbacks in such an approach is that:

• Your model is only an approximation of your original problem.
• In many cases, piecewise linear approximations force you to introduce binary variables that make the resulting mixed-integer linear model much harder to solve than (purely continuous) linear models.

Roughly speaking, the stronger the nonlinearities, the more linear pieces you need for the approximation, the more you have additional binary variables to deal with the pieces, the harder is the resulting MILP model to solve.

There exist some techniques and solvers, like LocalSolver, that allow tackling directly the original nonlinear formulation. LocalSolver uses piecewise linear approximations under the hood, but also some nonlinear optimization methods. With LocalSolver, you can give your three nonlinear functions f1, f2, f3 directly as arrays in your optimization model, or even as external functions (for example, if they can be simulated by some codes).

Note: If your problem has only the 4 variables w1, w2, w3, Z to decide, then you can easily solve your problem by using a dedicated derivative-free heuristic as pointed out by prubin. For an example, check our answer to a similar post previously discussed on this forum.

Disclosure: LocalSolver is our commercial software product.

Answer 2

If you are willing to take an approximate solution (no guarantee of optimality), it should be fairly easy to apply any of a number of metaheuristics to your problem. It would be helpful if, for fixed $w_i$, $f_i(w_i Z)/Z$ were monotone in $Z$ (with all such ratios monotone in the same direction, increasing or decreasing). If they are not all monotonic, you could probably still get at least some metaheuristics to work.

I'm fairly certain that you can find Python packages for most of the commonly used metaheuristics. Selecting a metaheuristic is somewhat a function of taste (or should I say religious preference, given the fervor of some of their adherents?). Under the monotonicity assumption I mentioned (and assuming all variables are nonnegative), I suspect I could get a genetic algorithm (my go-to choice) to handle the constraints properly.