Optimization and Search

Question 1

Optimization

We need:

Answer 1

Optimization

We need:

• A numerical representation of x for all possible solutions to the problem
• A function f(x) that tells us how good it is
• A way of finding max or min f(x)

Question 2

Exhaustive search

Answer 2

Exhaustive search

• Test all possible solutions, pick the best
• Guaranteed to find the optimal solution

Only works for simple discrete problems, but can be approximated in continuous problems

• Sample the space at regular intervals (grid search)
​• Sample the space randomly 𝑁 times

Question 3

Greedy search

Answer 3

Greedy search

• Pick a solution as the current best
• Compare to all neighboring solutions
  
  • If no neighbor is better, then terminate
  • Otherwise, replace the current best with the best of the neighbors
  • Repeat

Question 4

Hill climbing

Answer 4

• Pick a solution as the current best
• Compare to a random neighbor
  
  • If the neighbor is better, replace the current best
  • Repeat

Question 5

Examples of continuous optimization

Answer 5

Examples of continuous optimization

• Mechanics
  
  • Optimized design of mechanical shapes etc.
• Economics
  
  • Portfolio selection, pricing options, risk management etc.
• Control engineering
• Process engineering, robotics etc.

Question 6

Gradient ascent / descent

Answer 6

In continous optimization, we may be able to calculate the gradient of f(x).

The gradient tells us in what direction f(x) increases the most.

Starting from x⁰, we can iteratively find hight f(x^(k+1)) by adding a value proportional to the gradient to x^(k):

x^(k+1) = x^k + yΔf(x^k)

Question 7

Algorithms like _____ can only find local optima:

Answer 7

Algorithms like greedy search, hill climbing and gradient ascent/descent can only find local optima:

• They will only move through a strictly improving chain of neighbors
• Once they find a solution with no better neighbors they stop

Question 8

Exploitation

Answer 8

Question 9

Exploitation and Exploration

Answer 9

Search methods should combine:

• Trying completely new solutions (like in exhaustive search) => Exploration
• Trying to improve the current best solution by local search => Exploitation

Question 10

Mixed solution (exploration and exploitation)

Answer 10

Works better, but only if there are few local optima.

Question 11

Simulated annealing

Answer 11

• Set an initial temperatur T
• Pick an initial solution
• Repeat:
  
  • Pick a solution neighboring the current solution
  • If the new one is better, keep it
  • Otherwise, keep the new one with a probability
    P(Δf, T) = e^-Δf/T
  • Decrease T