CS B553: ALGORITHMS FOR OPTIMIZATION AND LEARNING 1 Global optimization AGENDA: GLOBAL OPTIMIZATION Local search, optimization Branch and bound search Online search
GLOBAL OPTIMIZATION min f(x), x in S Rn f x1 S x2
Want guarantees on a global optimum 3 EXHAUSTIVE SEARCH S e 4
EXHAUSTIVE SEARCH S 5 LOWER-BOUND FUNCTION LowerBound(A): for any set A S, returns a lower bound on f(x) for all xA f
x2 x1 SA fL(A) 6 PRUNING THE SEARCH TREE 1
2 4 2.5 3 Values of LowerBound(A) f(x) = 3.2 7
BRANCH-AND-BOUND ALGORITHM Let f* be the best value seen so far Init: f* = f(point in S ) 0 Q = {S0} While S
Q not empty, repeat: What order? = remove an item from Q If LowerBound(S) f* or |S|
PERFORMANCE Works well when When LowerBound is relatively tight When n isnt too large Methods for generating LowerBound Interval
arithmetic Solving relaxed versions of f Problem-specific ways 9 EXAMPLE: 3D NEEDLE STEERING FEEDBACK CONTROLLER Closed-loop feedback rule: 1. Sense current position/orientation of needle
2. Twist at the speed such that the predicted helix path minimizes the distance to target CONSTANT-TWIST-RATE HELICES 11 REACHABLE POINTS UNDER CONSTANT-TWIST-RATES 12
FINDING CLOSEST POINT Find small initial domain Use cylindrical lower bound BnB takes < 1ms on average 13 COLLISION CHECKING Check whether objects overlap 14
HIERARCHICAL COLLISION CHECKING Enclose objects into bounding volumes (spheres or boxes) Check the bounding volumes 15 HIERARCHICAL COLLISION CHECKING Enclose objects into bounding volumes (spheres or boxes) Check the bounding volumes first Decompose an object into two
16 HIERARCHICAL COLLISION CHECKING Enclose objects into bounding volumes (spheres or boxes) Check the bounding volumes first Decompose an object into two Proceed hierarchically
17 HIERARCHICAL COLLISION CHECKING Enclose objects into bounding volumes (spheres or boxes) Check the bounding volumes first Decompose an object into two Proceed hierarchically
18 BOUNDING VOLUME HIERARCHY (BVH) A BVH (~ balanced binary tree) is pre-computed for each object (obstacle, robot link) 19 BVH OF A 3D TRIANGULATED CAT
20 COLLISION CHECKING BETWEEN TWO OBJECTS A B A C BVH of object 1 B
C BVH of object 2 [Usually, the two trees have different sizes] Search for a collision 21 SEARCH FOR A COLLISION Search tree AA
pruning A A 22 SEARCH FOR A COLLISION Search tree AA Heuristic: Break the largest BV
A A 23 SEARCH FOR A COLLISION Search tree AA BA CA
Heuristic: Break the largest BV B C A 24 SEARCH FOR A COLLISION Search tree AA
BA CA CB CC C B C 25
SEARCH FOR A COLLISION Search tree AA BA CA CB CC
If two leaves of the BVHs overlap (here, C and B) check their content C B for collision C B 26 SEARCH STRATEGY If there is no collision, all paths must eventually be followed down to pruning or a leaf node
But if there is collision, one may try to detect it as quickly as possible Greedy best-first search strategy with f(N) = h(N) = d/(rX+rY) [Expand the node XY with largest relative overlap (most likely to contain a collision)] rX X
d rY Y 27 PERFORMANCE On average, over 10,000 collision checks per second for two 3-D objects each described by 500,000 triangles, on a contemporary PC
Checks are much faster when the objects are either neatly separated ( early pruning) or neatly overlapping ( quick detection of collision) 28 REVIEW OF OPTIMIZATION UNIT Descent vs root finding Gradient descent, Newtons method, Quasinewton methods
Constraints: Lagrange multipliers and KKT conditions Convex optimization LP, QP Interior point methods Metaheuristic methods
PUTTING OPTIMIZATION INTO PRACTICE Being able to formulate optimization problems is often just as important as choosing the right algorithm Well conditioned functions Constraints Auxiliary variables Transformations
Analysis vs. computation WHAT ELSE IS OUT THERE? Special techniques for sparse problems Special problem formulations e.g., SDP, SOCP
Mixed-integer programming Semi-infinite programming In-depth analysis suitable for industrial strength optimization MODERN TRENDS Learning with big data Combinatorial / hybrid problems Online or distributed optimization Specific function classes:
Stochastic functions Robot/biomechanical motions Feedback control policies READINGS FOR NEXT CLASS K&F, Chapter 2