Any idea of solving an optimization problem with cubic constraints?

Question

I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?

$$ \begin{array}{ll} \underset {y, z} {\text{minimize}} & C \\ \text{subject to} & \frac{5+y}{2} \leq C, \\ & 1+\frac{2+y}{z\cdot y}\leq C \\& \frac{1}{z}\leq y \leq 1, \\ & 2\leq z\leq 3. \end{array} $$

In this optimization problem, $y$ and $z$ are the decision variables in the real line. And $C$ can also be considered as a decision variable. The first constraint can be transformed into $5-2C+y \leq 0$, and the second constraint can be transformed into $zy-Czy+y+2\leq 0$. Hence the second constraint can be seen as a cubic constraint, as it contains the term '$Czy$'. I would like to know are there any systematic ways of deriving the analytical solution of this optimization problem?

Answer 1

Seems you're actually trying to solve

min f(y,w) s.t. w <= y <= 1 2 <= 1/w <= 3 .... i.e., 2w <= 1 <= 3w. or 1/3 <= w <= 1/2

Here I replaced w = 1/z to make the bounds linear.

Two ways to go about solving this:

1. Plug this type of formulation into scipy (or some nonlinear solver) that uses some form of gradient descent. This will get you to a stationary point that might be optimal.

2. Reformulate this as a qcqp and plug it into gurobi to solve. In this case, you need to add variables to make this have only quadratic terms showing up.

Here is a sequence of transformations to make it a QCQP

$$ \begin{array}{cl} \underset{y, z}{\operatorname{minimize}} & C \\ \text { subject to } & \frac{5+y}{2} \leq C, \\ & 1+\frac{2+y}{z \cdot y} \leq C \\ & \frac{1}{z} \leq y \leq 1, \\ & 2 \leq z \leq 3 \end{array} $$

$$ \begin{array}{cl} \underset{y, z}{\operatorname{minimize}} & C \\ \text { subject to } & \frac{5+y}{2} \leq C, \\ & 2+y \leq (C -1)(yz)\\ & 1\leq yz \leq z, \\ & 2 \leq z \leq 3 \end{array} $$

$$ \begin{array}{cl} \underset{y, z}{\operatorname{minimize}} & C \\ \text { subject to } & \frac{5+y}{2} \leq C, \\ & 2+y \leq (C -1)w\\ & 1\leq w \leq z, \\ & 2 \leq z \leq 3\\ & w = yz \end{array} $$

$$ \begin{array}{cl} \underset{y, z,w,q,C}{\operatorname{minimize}} & C \\ \text { subject to } & \frac{5+y}{2} \leq C, \\ & 2+y \leq q\\ & 1\leq z \leq z, \\ & 2 \leq z \leq 3\\ & w = yz\\ & q = (C-1)w \end{array} $$

Here is some code to solve it: from gurobipy import Model, GRB, QuadExpr

Create a new model

m = Model("nonconvex_qp")

Create variables

y = m.addVar(lb=1/3, name="y") z = m.addVar(lb=2, ub=3, name="z") # bounds on z are 2 and 3 w = m.addVar(lb=1, name="w") q = m.addVar(lb=0, name="q") C = m.addVar(lb=2.5, name="C")

Set objective

m.setObjective(C, GRB.MINIMIZE)

Add constraint: 5 + y <= 2C

m.addConstr(5 + y <= 2 * C, "c0")

Add constraint: 2 + y <= q

m.addConstr(2 + y <= q, "c1")

Add constraint: w <= z

m.addConstr(z <= z, "c2")

Add constraint: w = yz

m.addConstr(w - y * z == 0, "c3")

Add constraint: q = (C - 1)w

m.addConstr(q - (C - 1) * w == 0, "c4")

Set the NonConvex parameter to 2 to allow Gurobi to solve nonconvex problems

m.params.NonConvex = 2

Optimize model

m.optimize()

for v in m.getVars(): print('%s %g' % (v.varName, v.x))

The optimal solution is y 0.47481 z 3 w 1.42443 q 2.47481 C 2.7374

Note: this is up to a tolerance of 10^-4.

If I crank it up a little, we get

y 0.4748096336 z 3.0000000000 w 1.4244289009 q 2.4748096336 C 2.7374048168

But I suppose that this means that z reaches it's upper bound of 3, so you can probably plug this into the original problem and try to obtain an analytical answer.

Answer 2

It seems the minimum is where these two curves meet.

So... ask Wolfram to solve https://www.wolframalpha.com/input?i=%285%2By%29%2F2+%3D%3D+1+%2B+%282%2By%29%2F%283*y%29

Yields 2 solutions: y = -7/6 - sqrt(97)/6 y = sqrt(97)/6 - 7/6

But only the second one is positive, so that must be the right answer.