Bilevel optimization with acados

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!


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

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!

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

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,

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.

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