Solution methods for bilevel optimization

Сентябрь 13, 2022

Главная
Математика
Solution methods for bilevel optimization

Содержание

2. Overview Definition and general form of a bilevel problem Discuss optimality (KKT-type) conditions Reformulate general bilevel
3. Stackelberg Game (Bilevel problem) Players: the Leader and the Follower The Leader is first to make
4. Example Taxation of a factory Leader – government Objectives: maximize profit and minimize pollution Follower –
5. General structure of a Bilevel problem
6. Important Sets
7. Solution methods Vertex enumeration in the context of Simplex method Kuhn-Tucker approach Penalty approach Extract gradient
8. Concept of KKT conditions
9. Value function reformulation
10. KKT for value function reformulation
11. Assumptions
12. KKT-type optimality conditions for Bilevel
13. Further Assumptions (for simpler version)
14. Simpler version
15. NCP-Functions Define Give a reason (non-differentiability of constraints) Fischer-Burmeister
16. Simpler version in the form of the system of equations
17. Iterative methods
18. For Bilevel case
19. Newton method Define Explain that we are dealing with non-square system Suggest pseudo inverse Newton
20. Pseudo inverse
21. Newton method with pseudo inverse
22. Gauss-Newton method Define Mention the wrong formulation Refer to pseudo-inverse Newton
23. Gauss-Newton method
24. Convergence of Newton and Gauss-Newton Talk about starting point condition Interest for future analysis
25. Levenberg-Marquardt method
26. Numerical results
27. Plans for further work
28. Plans for further work 6. Construct the own code for Levenberg-Marquardt method in the context of
31. References
33. Скачать презентацию

Слайд 2

Overview
Definition and general form of a bilevel problem
Discuss optimality (KKT-type) conditions
Reformulate

general bilevel problem as a system of equations
Consider iterative (descent direction) methods applicable to solve this reformulation
Look at the numerical results of using Levenberg-Marquardt method

Слайд 3

Stackelberg Game (Bilevel problem)
Players: the Leader and the Follower
The Leader is

first to make a decision
Follower reacts optimally to Leader’s decision
The payoff for the Leader depends on the follower’s reaction

Слайд 4

Example
Taxation of a factory
Leader – government
Objectives: maximize profit and minimize pollution
Follower

– factory owner
Objectives: maximize profit

Слайд 5

General structure of a Bilevel problem

Слайд 6

Important Sets

Слайд 7

Solution methods
Vertex enumeration in the context of Simplex method
Kuhn-Tucker approach
Penalty approach
Extract

gradient information from a lower objective function to compute directional derivatives of an upper objective function

Слайд 8

Concept of KKT conditions

Слайд 9

Value function reformulation

Слайд 10

KKT for value function reformulation

Слайд 11

Assumptions

Слайд 12

KKT-type optimality conditions for Bilevel

Слайд 13

Further Assumptions (for simpler version)

Слайд 14

Simpler version

Слайд 15

NCP-Functions
Define
Give a reason (non-differentiability of constraints)
Fischer-Burmeister

Слайд 16

Simpler version in the form of the system of equations

Слайд 17

Iterative methods

Слайд 18

For Bilevel case

Слайд 19

Newton method
Define
Explain that we are dealing with non-square system
Suggest pseudo inverse

Newton

Слайд 20

Pseudo inverse

Слайд 21

Newton method with pseudo inverse

Слайд 22

Gauss-Newton method
Define
Mention the wrong formulation
Refer to pseudo-inverse Newton

Слайд 23

Gauss-Newton method

Слайд 24

Convergence of Newton and Gauss-Newton
Talk about starting point condition
Interest for future

analysis

Слайд 25

Levenberg-Marquardt method

Слайд 26

Numerical results

Слайд 27

Plans for further work

Слайд 28

Plans for further work
6. Construct the own code for Levenberg-Marquardt method

in the context of solving bilevel problems within defined reformulation.
7. Search for good starting point techniques for our problem. 8. Do the numerical calculations for the harder reformulation defined .
9. Code Newton method with pseudo-inverse.
10. Solve the problem assuming strict complementarity
11. Look at other solution methods.

Слайд 29

Слайд 30

Слайд 31