CODEWITHSUNDEEP
pythonmathematical-optimizationscipy-optimize
develarist
develarist

Reputation: 1365

Bi-level optimization using Python scipy.optimize

How can I code a bi-level optimization problem using scipy.optimize.minimize which consists of the following two levels, (1) being the upper-level problem, which is subject to (2) being the lower-level:

  1. minimize linear programming problem, subject to a
  2. minimize quadratic programming problem

I know how to write a single objective function for quadratic programming as a typical scipy.optimize.minimize routine (step 2 by itself), but how can I add an upper level minimization problem as well that has its own objective function? Can scipy handle a minimization problem subject to a lower minimization problem? A rough outline of the code using minimize and linprog would help

Upvotes: 2

Views: 1398

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

I don't think scipy solvers are very suited for this.

A standard approach for bilevel problems is to form the KKT conditions of the inner problem and add these as constraints to the outer problem. The complementarity conditions make the problem hard. You need a global NLP solver or a MIP solver to solve this thing to proven optimality. Here are some formulations for linear bilevel problems. If the inner problem is a (convex) QP problem, things become a little bit more difficult, but the same idea can be applied (form KKT conditions of the inner problem).

For more information see Bard, Practical Bilevel Optimization: Algorithms And Applications, Springer, 1998.

Upvotes: 4

Related Questions