Optimisation Flashcards
(26 cards)
What is an optimisation problem?
One where we have a function and want to minimise it via the adjusting of a parameter or set of parameters X
What is Jensen’s inequality?
A function is convex if and only if the secant line lies above the graph of f(x)
What is a convex set?
A set that contains every line segment between any two points in the set
How can you use a convex set to tell that an object is convex?
If you pick two points within a shape, and any line segment made between them stays within the shape, it is convex
What is an epigraph?
A set consisting of all points lying on or above a function’s graph
A function is convex if the epigraph [is/is not] a convex set.
Is
Given a convex function, we can find the minimum of x where…
The gradient is equal to zero
What is bracketing?
A method of optimisation that finds the root by iteratively moving brackets across x
A root of g(x) is said to be bracketed by two thresholds a and b if…
g(a) < 0 and g(b) > 0, or vice versa, hence there is a zero-crossing between a and b
What is parabolic interpolation?
We fit the curve by a parabola, finding a g(x) such that the intersection points of the parabola a, b and c intersect g(x), then creating a new parabola where the new c = b
Why should we ensure that step sizes diminish?
So that we converge and don’t actually step over the minimum
What method should we use if we have more than two dimensions to minimise y = f(x)?
Downhill simplex method
What is a simplex?
A geometrical figure consisting, in D dimensions, of D + 1 points and all of their interconnecting properties
What is downhill simplex method?
A method using the geometrical concept of a simplex to find the minimum of a function
If in the first dimension, a line is a simplex, as it is in 1 dimension with 2 points, what is a simplex in 2D?
A triangle
If in the first dimension, a line is a simplex, as it is in 1 dimension with 2 points, what is a simplex in 3D?
A tetrahedron; a 3D shape with four points
How do we calculate the efficiency of a simplex?
Find the best, worst and average function values and calculate their centroid
How do we learn via the downhill simplex method?
Perform some transformation on the worst vertex in the simplex to move it closer to an optimal solution
What is reflection in the downhill simplex method and when would we accept the result?
Reflect the worst vertex through the centroid of the best side, accepting it if it is better than the ‘average’ point
What is expansion in the downhill simplex method and when would we accept the result?
Expanding the worst vertex through the centroid of the best side, accepting it if it is better than the ‘best’ point, continuing if so
What is contraction in the downhill simplex method and when would we accept M1 over M2?
Contracting the simplex around the centroid such that we generate two ‘middle points’ M1 and M2 that are halfway between W-C and C-R
We accept M1 if it is better than both the worst point and M2, accepting M2 otherwise
What is shrinking in the downhill simplex method and when would we accept the result?
Shrinking towards the best point at a scale determined by some parameter, accepting only if all else fails to produce a result
What is the order of transformations in downhill simplex? Briefly explain the conditions that need to be met for each.
Reflection first, continuing to expansion only if the reflected point is not better than the ‘good’ point. If expansion cannot beat reflection, then we go on to contraction. If neither M1 or M2 can beat the ‘worst’ point, then we go to shrinking as a last resort
What is Rosenbrock’s test function (banana function)?
A non-convex test function used to measure performance in optimisation algorithms
