Package in julia for solving optimization problems with cubic objective function

Specific Domains Optimization (Mathematical)
21

In addition to @mbesancon 's answer, if you’re using Gurobi, you can write the SOC constraint as a quadratic constraint directly; Gurobi will recognize it automatically.

Namely, instead of writing

model = Model()
@variable(model, x[1:n])
@variable(model, z)
@constraint(model, soc, [t; x] in SecondOrderCone())

you can write

model = Model(Gurobi.Optimizer)
@variable(model, x[1:n])
@variable(model, z >= 0)  # ⚠️ z must be non-negative
@constraint(model, qcp, sum(x[i]^2 for i in 1:n) <= z^2)

and Gurobi will detect that the problem is convex.

Please note:

  • the z variable must be non-negative for the problem to be convex
  • as far as I know, only Gurobi supports this; other solvers will likely treat the problem as non-convex
  • if you pass the constraint z >= sqrt(sum(x[i]^2 for i in 1:n)), Gurobi will 1) not support it out of the box and 2) likely won’t recognize this as a convex problem.
22

Thank you! :slightly_smiling_face:

I am not sure if I have understood you correctly but I do not think that substituting the euclidean norm (||sqrt(A) * sqrt(p) * eta||_2) with t will solve the problem. The reason for this is that the same etas are also present in other constraints as just a one-dimensional variable.

An example is:
For a given node m in t = t I have the following constraint where S_m is the set of successors of the node m and v is the parent of node m:

B_{t} \cdot (w_{v} \cdot w_m) + \eta_{m} + x_{m} \geq A \cdot \sqrt{\sum_{n \in \mathcal{S}_{m}} p_n \cdot \eta_n^2}

In t = t+1, every node will have the same type of constraint. Looking at a node n which is a successor of m, the constraint will be:

B_{t+1} \cdot (w_{m} \cdot w_n) + \eta_{n} + x_{n} \geq A \cdot \sqrt{\sum_{r \in \mathcal{S}_{n}} p_r \cdot \eta_r^2}

Here we see that the eta in the euclidean norm of the first constraint will appear in another constraint on the left hand side of the \geq. The same holds for all of the other etas.

Is there another way I could reformulate the problem instead of substituting the whole euclidean norm, so I can use Gurobi?

23

You can introduce a new variable z_{m} with the SOC constraint

z_m \ge \sqrt{...}

and then use z_m in the constraint:

\ldots + x_m \ge A \cdot z_m

24

I understood that a square root in a constraint was problematic when running the model using Gurobi. Wouldn’t I get the same problem with this formulation?

1 Like
25

Oh, yes, I didn’t mean to actually use the sqrt.

You should implement it as z_m^2 \ge ... with z_m >= 0.

1 Like