Minimizing a monomial function subject to inequality constraints

Question

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$.

Answer 1

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.

Answer 2

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.

Answer 3

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