Sum of L2 Norm in objective
Answered
Hi,
I am trying to formulate an objective function that includes a sum of L2 norms (for example, minimize x1 + x2 + sqrt(x3^2 + x4^2) + sqrt(x5^2 + x6^2))
Currently, my best implementation involves approximating the L2 norm terms using (a * L1_norm + (1-a) * Linf_norm).
Does Gurobi offer a better way to formulate this objective?
-
Hi Prateek,
You can use model.addGenConstrNorm() to set a variable equal to the norm of other variables and use it in the objective.
Best regards,
Simran
0 -
Hi Simran,
Would that still use the linear solver? The problem is quite large and does not work well with non-linear solvers (such as MIP). Hence I would still need it to be solved as an LP problem.
0 -
Hi Prateek,
Indeed, adding a simple general constraint like the 2-norm constraint to an otherwise continuous model will transform it into a MILP.
If solving your model a MILP takes longer than desired, you can:
- Use the Gurobi parameter tuning tool to tune the MILP model for improved solve time.
- Consider the option to disregard the square roots in the objective function, as minimizing sqrt(x) is the same as minimizing x, as long as x >= 0. With this, if all other variables in the model are continuous, your model will be solved as a continuous quadratic problem.
Best regards,
Simran
0 -
Hi Simran,
I have already tried to tune the parameters for MILP. It seems the problem is just too big for an effective solution to be reached quickly enough though.
As for option 2, I don't believe disregarding the square root works in the case that you have a sum of the square roots. For example:
For example √ 2 +√ 1 + √ 1 ~= 4.42 > 2.23 ~= √ 5 + √ 0 + √ 0 but 2 + 1 + 1 < 5
0 -
Hi Prateek,
Sorry, my bad. I missed the fact that you have a sum of square roots in the objective function.
Another approach can be to add the constraints of the form \( x_3^2 + x_4^2 <= y_1^2\) and \( x_5^2 + x_6^2 <= y_2^2\) and minimize \(x_1 + x_2 + y_1 + y_2\). With this, your model be solved as a Quadratic Constrained Problem. You will still need to check the performance of the model with this formulation.
Best regards,
Simran
0 -
Hi Simran,
I will give that a go, thank you.
Just out of curiosity, the LP file displays quadratic terms in the objective function as follows:
[2 x_3 ^2 + 2 x_4 ^2] / 2 + [2 x_5 ^2 + 2 x_6 ^2] / 2
Of course this simplifies to simply x_3^2 + x_4^2 + x_5^2 + x_6^2, but I was wondering if this is how the optimisation treats them? In other words, are the following all equivalent in terms of the optimisation:
[ 2 x_3 ^2 + 2 x_4 ^2 ] / 2 + [ 2 x_5 ^2 + 2 x_6 ^2 ] / 2
[ 2 x_3 ^2 + 2 x_4 ^2 + 2 x_5 ^2 + 2 x_6 ^2 ] / 2
[ 2 x_3 ^2 ] / 2 + [ 2 x_4 ^2 ] / 2 + [ 2 x_5 ^2 ] / 2 + [ 2 x_6 ^2 ] / 2
0 -
Hi Prateek,
As mentioned in the Single-Objective Case section of our LP format documentation, the quadratic terms in the objective function are enclosed in [ and ] and the quadratic expression is divided by 2.
Although the [ 2 x_3 ^2 + 2 x_4 ^2 ]/2 and [ 2 x_3 ^2 ] / 2 + [ 2 x_4 ^2 ] / 2 are equivalent, they might not be the same for the optimizer, especially if the resulting models have different fingerprints.
Best regards,
Simran
0
Please sign in to leave a comment.
Comments
7 comments