Bilevel optimization with acados

User Questions
1

Hi :wave:
I am using ACADOS with the Python API to solve a NMPC problem of path following with obstacle avoidance.
My problem looks the following

\begin{array}{rl} \displaystyle \min_{z(t),u(t)} J(z,u) & \\ \textbf{s.t.} & \dot{z}(t) = f(z(t), u(t)) \\ & \displaystyle \min_{z(t),u(t)} \kappa(z(t), u(t))<0 \end{array}

I managed to write the inequality condition as a CASADI nlp problem.

However, when trying to set the ACADOS problem formulation (and using a NL expression for the constraints) I get the following error:

 cc -fPIC -std=c99   -O2 -I/home/user/Documents/07_Dev/acados/include -I/home/user/Documents/07_Dev/acados/include/acados -I/home/user/Documents/07_Dev/acados/include/blasfeo/include -I/home/user/Documents/07_Dev/acados/include/hpipm/include  -c -o Spatialunicycle_model_constraints/Spatialunicycle_model_constr_h_fun_jac_uxt_zt.o Spatialunicycle_model_constraints/Spatialunicycle_model_constr_h_fun_jac_uxt_zt.c
 Spatialunicycle_model_constraints/Spatialunicycle_model_constr_h_fun_jac_uxt_zt.c:22:10: fatal error: coin-or/IpStdCInterface.h: No such file or directory
    22 | #include <coin-or/IpStdCInterface.h>
       |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~
 compilation terminated.

So my question : is there a way to have this kind of “nested” NLP resolution with ACADOS? If so, how to formulate it?

Thanks in advance!

2

Hi,

as such you cannot formulate this problem with acados. If the function \kappa is convex, you might include the KKT conditions of the low-level problem instead.

1 Like
3

Thanks for the quick response!
I have another question following up this one, say now that my problem is :

\begin{array}{rl} \displaystyle \min_{z(t),u(t)} J(z,u) & \\ \textbf{s.t.} & \dot{z}(t) = f(z(t), u(t)) \\ & \displaystyle \min_{s} \kappa(s, z(t))<0 \end{array}

I know how to formulate the KKT conditions of the nested minimization, as a function of “s”.
How should I set up the ACADOS formulation?
I was thinking of using an algebraic variable for “s”, is it the right way to go?

Thanks for your response!

4

Sounds good to me! You will need to include the constraint \kappa(s^*, z) \leq 0 via the nonlinear inequality h in the acados problem formulation

5

Sorry to bother you, I’m still facing issues here.

The KKT conditions of the problem are
\frac{\partial \kappa}{\partial s}(s*)=0
s \in ]0,1[

So my initial guess was to add in the constraints of the model s \in ]0,1[, \frac{\partial \kappa}{\partial s}(s,z)=0 and \kappa(s,z) \leq 0
Doing so, I change the integrator type to IRK to handle algebraic variables, but the value of s does not seem to evolve and is stuck at 0, leading to an error status 4 (because the constraints are not met)

When trying to use the variable s as an input of the system as suggested here, i get the same issue, the variable is stuck at 0, even if I set initial conditions.

Do you know how this can be solve ?
Thanks again,

6

If the lower-level problem includes constraints, things get more complicated: you will need to include both s and a multiplier \lambda as additional variables and the corresponding KKT conditions are no longer smooth due to the complementarity condition. If you formulate this problem exactly you will end up with a mathematical program with complementarity constraints which is in general very challenging to solve.

In general acados cannot handle this type of problems. Depending on how simple/difficult the lower-level optimization is and depending on how important it is for you to solve the lower level problem exactly, you might want to try to reformulate the constraint s \in [0,1] with penalty terms such that you end up with an unconstrained problem again.

7

Note again that all of this will only work reasonably if your lower level problem is convex!