Final report
48
pages
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
48
pages
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- exposé - matière potentielle : application
- expression écrite - matière potentielle : annotations
- exposé - matière potentielle : the print
- expression écrite - matière potentielle : the note
- exposé
- expression écrite
- kind of annotation
- pliny
- personal annotation
- dh development community
- digital humanities
- annotation
- objects
- application
- software
- work
Outline
Optimality conditions
Algorithms
Gradient-based algo
Derivative-free algorithms
Lecture 2: Unconstrained Optimization
Kevin Carlberg
Stanford University
July 28, 2009
Kevin Carlberg Lecture 2: Unconstrained OptimizationOutline
Optimality conditions
Algorithms
Gradient-based algo
Derivative-free algorithms
1 Optimality conditions
Univariate minimization
Multivariate
2 Algorithms
3 Gradient-based algorithms
Line search methods
Descent directions
Trust region methods
Global optimization
Computation of gradients
4 Derivative-free algorithms
Categorization
Genetic Algorithm
Kevin Carlberg Lecture 2: Unconstrained OptimizationOutline
Optimality conditions
Algorithms
Gradient-based algo
Derivative-free algorithms
Unconstrained optimization
This lecture considers unconstrained optimization
minimize f (x)
nx2R
Things become signi cantly more complicated with
constraints!
Kevin Carlberg Lecture 2: Unconstrained OptimizationOutline
Optimality conditions
Univariate minimization
Algorithms
Multivariate
Gradient-based algo
Derivative-free algorithms
Univariate minimization
Consider the unconstrained minimization of a function in one
dimension
minimize f (x) (1)
x2R
In this class, we assume all functions are \su ciently smooth"
(twice-continuously di erentiable)
f(x)
x
What is a solution to (1)?
Kevin Carlberg Lecture 2: Unconstrained OptimizationOutline
Optimality conditions
Univariate minimization
Algorithms
Multivariate
Gradient-based algo
Derivative-free algorithms
What is a solution?
f(x)
x
Global minimum: A point x satisfying f (x ) f (x)8x2R
Strong local minimum: A neighborhoodN of x exists such
that f (x )< f (x)8x2N .
Weak local minima A a neighborhoodN of x exists such
that f (x ) f (x)8x2N .
Kevin Carlberg Lecture 2: Unconstrained OptimizationOutline
Optimality conditions
Univariate minimization
Algorithms
Multivariate
Gradient-based algo
Derivative-free algorithms
Convexity
For convex objective functions in one variable,
f (x +y)f (x) +f (y)
f(x) f(x)
x x
In this case, any local minimum is a global minimum!
Kevin Carlberg Lecture 2: Unconstrained OptimizationOutline
Optimality conditions
Univariate minimization
Algorithms
Multivariate
Gradient-based algo
Derivative-free algorithms
Optimality conditions for univariate minimization
Theorem (Necessary conditions for a weak local minimum)
0 A1. f (x ) = 0 (stationary point)
00 A2. f (x ) 0.
Theorem (Su cient conditions for a strong local minimum)
f (x)
0 B1. f (x ) = 0 (stationary point) and
00 B2. f (x )> 0.
x
A1 A2
f (x)
B1, B2
x
Kevin Carlberg Lecture 2: Unconstrained OptimizationOutline
Optimality conditions
Univariate minimization
Algorithms
Multivariate
Gradient-based algo
Derivative-free algorithms
Optimality conditions for univariate minimization
A1 Maxima
A2 Saddle points
Weak minima
B1, B2
Strong minima
Kevin Carlberg Lecture 2: Unconstrained Optimization
