Flashcards
ATMD
Flashcards do conjunto (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—
Informações
- Descrição
- Spanish FlashCards sobre ATMD, criado por Oliver Boom em 12-03-2018.
- Criado por
- Oliver Boom
- Visualizações
- 1
- Avaliação