# Any idea of solving an optimization problem with cubic constraints?

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?

• seems a standard case for Lagrange factors Jun 6, 2023 at 3:20
• @Erik The system becomes somewhat easier if you set $x=yz$ and express everything in terms of $x$ and $y$. Jun 6, 2023 at 8:57
• Have you tried WolframAlpha? Dec 7, 2023 at 23:25

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

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.