Flashcards

ATMD

Oliver Boom Spanish English 62 cards

Cards in this deck (62)

1Tree of optimization
2x f(x) g(x) = 0 h(x) <= 0decision/design variable
the objective/cost
equality constraint
inequality constraint
3wrapper function.
4Decision variable scalingtakes vector [0,1] and scales to give values for decision varibles
5Scaled objectivecost J = objective + penalties for invalidating constraints
penalties scaled to baseline
Also arbitary 30* scaling based on judgement
6fmincon what to do after optimize results returnedCheck convergence
Check rationale
7if n = 1 when x is in R^nunivariate problem
use golden section search
8how much to shrink a univariate distance bywant same distance each time
9pros/cons with golden sectioncan evaluate numerically
simple
robust to continuity
doesnt find global optimum
10where x is in the set of R^n where n>1multivariate problem
11nelder mead simplexmethods moves a simplex around and compares cost at vertices
12nelder mead simplex process
13gradient based methodssteepest decent
newtons method
variation on newtons method
conjugate gradient
14gradient of fThe gradient of a scalar field is a vector
grad f
15which direction does the gradient pointin the direction of steepest uphill
ie. perpendicular to contours
16for analytical problem for numerical problem problem with numericaldifferentiate the cost
use perturbations
large amount of computations
need to be careful of d
17Steepest descentuse -grad f as search direction
for a small enough step guaranteed to reduce cost function. don't want to overshoot
slow convergence
18how to find step length for steepest descentuse univariate search algorithm. ie use golden section
19Neccessary conditionsGrad f = 0 yields a set of equations
must be true at optimum
may be true elsewhere though
local
20Newton RaphsonConverges very quickly
Erratic
21Damped Newton MethodsTake the direction of Newton but don't take the whole step
Line search along the step using either
backtracking or golden section
Preferable to steepest descent due to no zigzags
22The issue with (damped) Newton methodsNeed to find and invert the Hessian matrix
Difficult and expensive to invert Hessian matrix if not analytical
23Conjugate gradientModified version of steepest descent. Stops the zigzagging
Not far behind the backtracking newton but without having to evaluate the Hessian
24Quasi NewtonStart with H=I
Update the Hessian^-1 matrix with each iteration
25Convergence Comparison
26Convergence Rate Comparison Quadratic LinearThe number of correct decimal places roughly doubles with each step
Numer of correct dp is proportinal to the number of steps
27Computation required comparison
28Unbounded problem issueSearch may never finish
Think about asymptotes
293 potential termination criteriaNumber of steps
Cost change
Step size
30Newton with backtrackingIs great but the Hessian makes it expensive. Preferable to Golden section as less evaluations
31For multivariate unconstrained problemsolve the necessary conditions for grad f = 0
32Equality constraints g(x)Can be non-linear and non-seperate-able
Cant eliminate via substitution
33Constraint line and costWhere constraint line is parallel to the contour of the cost is the optimum
34Solving equality constraintsCan convert equality constraints into unconstrained problems with equivilant solutions
35Lagrange multipliersLamda
Have a Lagrange multiplier for each constraint condition
If multiple then there is a vector of multipliers
36How to solve equality constriant
37Barrier MethodA method that penalizes getting close to the constraint
for example -log(-h(x)) which climbs to infinity as the equality constraint is approached
38Barrier method approachsolve equality constraint condition
if solution not converged decrease mu and repeat
39What happens for a general non-linear caseAs mu goes to 0 barrier solution approaches true constrained solution
40Interior Point MethodTransverses around interior set of points in feasible constraint region
Generally faster and more reliable
Sequence of subproblems with different barrier levels
41Active SetSimplex algorithm
A sequence of subproblems with different constraints
Better for standard problems e.g LP
Solution travels along the edges of a feasible set
42Convex Functionif f(x) and every h(x) are all convex
43Convex Optimum ImplicationConvex optimiser cannot have more than one local optimum
If an algorithm returns a local optimum for a convex function then it is also the global optimum
44Discrete OptimizationIf decision variables can only take discrete values
45Things that can go wrong using local optimizerOnly find local minimum
Problem is unbounded (no lower limit on cost)
Problem is infeasible (does not satisfy constraints)
46Branch and BoundNot quick or easy. Non convex are hard to solve
47MILPMixed integer linear program
Takes an LP and constraints some of the values to take only integer values
48To switch between maximising and minimising a functionfitness = -1 * cost
49Simulated Annealing Method
50Simulated Annealing Coin TossThe worse a solution is the less likely to get accepted
Later in the run a worse solution is less likely to be accepted
Probability of getting heads:
51Stochastic methods and constraintsStochastic methods can't handle constraints
They apply them through a penalty
52Jump penalty
53Step penalty
54Quadratic Penalty
55Types of penaltyJump
Step
Quadratic
Ramp
56Ramp Penalty
57Stochastic pros/consNo assumption about the problem. Only need to be able to evaluate the cost
Limited constraint handling - need to include penalties
Easy to implement but need tuning
58Tuning required for stochastic methods GA SA BothMutation selection, selection, crossover probabilities
Cooling schedule
Encoding scheme
59Hessian Matrix
60gradientthe vector whose entries are partial derivatives of the
objective function with respect to each decision variables?
61GA methodologyChoose the number of chromosomes
These are random between upper and lower bounds
Encode decision variables in each chromosome
remove poor solutions
crossover parts of lowest code chromosomes
random changes made to parts of chromosomes
go until converged
62—