2
$\begingroup$

Assuming an objective function is a multivariable polynomial with real coefficients, in variables $\{x_1, x_2, \ldots, x_n\}$ with all exponents no larger than $1$, and with linear inequalities on the variables, what are some good sources and/or approaches?

For instance:

$$ \min 0.3 x_1 - 0.5 x_2 + 0.4 x_3 + 0.9 x_1 x_2 - x_1 x_2 x_3$$

subject to

$$0 \le x_1$$

$$0 \le x_2$$

$$0 \le x_3$$

$$x_1+x_2 \le 0.9$$

$$x_2+x_3 \ge 0.3$$

to find the solution $[x_1,\,x_2,\,x_3]^T=[0,\,0.9,\,0]^T$.

Improve this question
$\endgroup$
1
  • $\begingroup$ Yes, (x1,x2,x3)=(0,.9,0). achieving the objective value -0.45, is the global minimum solution, to your example problem; and is easily obtained using any of the techniques mentioned in my answer. $\endgroup$
    – Mark L. Stone
    Commented Aug 2, 2022 at 20:49

3 Answers 3

Reset to default
6
$\begingroup$

The objective function you described is called multilinear.

Although not necessarily the best way of solving this problem, it can be "lifted" into a higher dimensional space, thereby becoming a non-convex quadratic objective subject to non-convex quadratic constraints; specifically becoming a bilinear optimization problem. That is accomplished by introducing new variables for various products of variables in such a manner that there are no products involving more than 2 variables. Such a formulation can then be solved with a bilinear solver, such as Gurobi, which can solve it to global optimality if it doesn't run out of time or memory. (Note that CPLEX's QCQP solver could not be used because it does not allow non-convex quadratic constraints).

In you example, introduce variables x1_2 and x1_2_3, along with constraints

x1_2 = x1*x2
x1_2_3 = x1_2*x3

The objective can then be written as .3 x1 - .5 x2 + .4 x3 + .9 x1_2 - x1_2_3.

This formulation can be provided to any solver which can handle any combination of non-convex quadratic objective and quadratic equality constraints (in addition to the linear constraints your problem has).

If you use a more general purpose non-convex global solver, you can provide it either the "lifted" formulation as shown above, or enter your original formulation as is. In such case, it might be better to use the original formulation, and let the solver handle any reformulations.

Another approach is to directly provide one of the above formulations to a local non-convex optimizer, in which case I suspect the original formulation might be best.

Improve this answer
$\endgroup$
3
$\begingroup$

To some extent, the answer depends on whether the objective function is convex (assuming minimization) or not. One general approach would be to approximate the objective with a piecewise linear function. With a convex objective, this would be an LP. Otherwise, it would be a MIP. There may also be a version/generalization of McCormick envelopes that would be useful.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! I have not studied McCormick envelopes, will do so. $\endgroup$
    – Kerry M. Soileau
    Commented Aug 2, 2022 at 20:14
1
$\begingroup$

You can directly use a Global solver such as LINGO, thus:

Min= .3x1 - .5x2 + .4x3 + .9x1* x2 - x1x2 x3;

!subject to;

! Variables are >= 0 by default;

x1+x2 <= .9;

x2+x3 >=.3;

Global optimal solution found.

Objective value: -0.4500000

Objective bound: -0.4500000

 Variable           Value     
       X1        0.000000    
       X2        0.900000        
       X3        0.000000          

      Row    Slack or Surplus     
        1       -0.450000         
        2        0.000000         
        3        0.600000
Improve this answer
$\endgroup$

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.