Optimization
Nonconvex optimization
Branch & Bound (B&B)
Application of B&B to MPC
Application of B&B to Fuzzy MPC
Algorithms
Motivarion: Nonlinear MPC
João Sousa, José Borges
XVII. 2
1
Nonconvex optimization
João Sousa, José Borges
XVII. 3
Branch and Bound (B&B)
• Classified as a Search and Enumeration algorithm where
the problems are modeled on graphs. A graph exploration
algorithm specifies rules for moving around that graph.
• Branch and Bound (BB) is a general algorithm for finding
optimal solutions of various optimization problems,
especially in discrete and combinatorial optimization.
• B&B consists of a systematic enumeration of all candidate
solutions, where large subsets of fruitless candidates are
discarded en masse, by using upper and lower estimated
bounds of the quantity being optimized.
João Sousa, José Borges
XVII. 4
2
Application of Branch and Bound
João Sousa, José Borges
XVII. 5
B&B in MPC
João Sousa, José Borges
XVII. 6
3
Branching rule
João Sousa, José Borges
XVII. 7
One step in branch-and-bound
João Sousa, José Borges
XVII. 8
4
Bounds
João Sousa, José Borges
XVII. 9
Branch-and-bound tree
João Sousa, José Borges
XVII. 10
5
Algorithm: B&B applied to MPC
João Sousa, José Borges
XVII. 11
Algorithm: B&B applied to MPC (2)
João Sousa, José Borges
XVII. 12
6
Algorithm: B&B applied to MPC (3)
João Sousa, José Borges
XVII. 13
Algorithm: B&B applied to MPC (4)
João Sousa, José Borges
XVII. 14
7
Concluding remarks on the B&B
João Sousa, José Borges
XVII. 15
Drawbacks
João Sousa, José Borges
XVII. 16
8
B&B in fuzzy predictive control
João Sousa, José Borges
XVII. 17
Optimization criteria
João Sousa, José Borges
XVII. 18
9
Branch condition
João Sousa, José Borges
XVII. 19
One step in branch-and-bound
João Sousa, José Borges
XVII. 20
10
Algorithm: B&B in fuzzy MPC
João Sousa, José Borges
XVII. 21
Algorithm: B&B applied to MPC (2)
João Sousa, José Borges
XVII. 22
11
Algorithm: B&B applied to MPC (3)
João Sousa, José Borges
XVII. 23
Algorithm: B&B applied to MPC (4)
João Sousa, José Borges
XVII. 24
12