Term
| Intermediate Value Theorem |
|
Definition
| If f is continuous on a closed interval [a,b] and c lies in between f(a) and f(b) then there is some value x in [a,b] such that f(x) = c. |
|
|
Term
|
Definition
| For a continuously differentiable function f, if the Jacobian matrix Jf is nonsingular at a point x then there is a neighborhood of f(x) in which f is invertible. That is, the equation f(x) = y has a solution for any y in the neighborhood of f(x). Nonsingular J = locally invertible everywhere ≠ globally invertible |
|
|
Term
| Contraction Mapping Theorem |
|
Definition
If g is contractive on a closed set S and g(S) is a subset of S then g has a unique fixed point in S.
Contractive: function g on set S if there is a constant γ with 0< γ<1 such that
||g(x)-g(z)|| < γ||x-z|| |
|
|
Term
|
Definition
A continuous function f on an unbounded set S if lim(as ||x|| goes to infinity) of f(x) = +infinity.
For any constant M there is an r > 0 (dependent on M) such that f(x) >=M for any x in S such that ||x|| >= r. |
|
|
Term
|
Definition
A set S is convex if it contains the line segment between any two of its points
i.e. for all x,y ε S, 0 < α < 1, αx + (1 - α)y ε S |
|
|
Term
|
Definition
| The derivative of f with respect to every variable, in form of a vector. The gradient points uphill while the negative gradient points downhill towards points having lower function values than f(x). |
|
|
Term
|
Definition
| The Jacobian of the gradient of f. hij is the second partial derivative of f(x) with repect to both xi and xj. |
|
|
Term
|
Definition
| For constrained optimization, the solution often occurs on the boundary of the set. So, consider only feasible directions. A nonzero vector s is a feasible direction at a point x in S if there is an r > 0 such that x + αs is in S for all α in [0,r]. |
|
|
Term
|
Definition
f(x) = 0 and f'(x) = 0
The curve defined by f has a horizontal tangent on the x axis.
Root of multiplicity 2. |
|
|
Term
|
Definition
| An iterative method is said to converge with rate r if lim(k→∞)||ek+1||/||ek||r = C where C is a constant. |
|
|
Term
| Interval Bisection Method |
|
Definition
Begins with an initial bracket and successively reduces its length until the solution has been isolated as accurately as desired.
At each iteration, f is evaluated at the midpoint of the current intervalue and half of the interval is discarded. |
|
|
Term
|
Definition
The point x=g(x) is a fixed point of the function g since x is unchanged when g is applied. For fixed-point iteration, g is a function chosen so that its fixed points are solutions for f(x) = 0.
xk+1=g(xk) |
|
|
Term
| Newton's Method in One Dimension |
|
Definition
xk+1=xk-f(x)/f '(x)
Converges if started close enough to root
Quadratic if not multiple root
|
|
|
Term
| Convergence Rate of Newton's Method in One Direction |
|
Definition
g(x) = x - f(x)/f '(x)
g '(x) = 1 - (f(x)f''(x) - (f '(x))2)/(f '(x))2
= f(x)f '(x)/(f '(x))2 = 0 if simple root
|
|
|
Term
|
Definition
xk+1=xk-(xk-xk-1)f(xk)/(f(xk)-f(xk-1))
because f '(xk) ≈ (f(xk)-f(xk-1))/(xk-xk-1) |
|
|
Term
|
Definition
| Fit the values xk as a function of the values yk=f(xk) by a polynomial p(y) so that the next approximate solution is simply p(0). At each iteration we have three approximate solution values. The next approximate solution is found by fitting a quadratic polynomial to these values and then evaluating it at 0. |
|
|
Term
|
Definition
| Rapidly convergent methods are unsafe -- may not converge unless they are started close enough to the solution. Hybrid methods safe and fast. Could use a rapidly converent method but maintain a bracket around the solution and if outside, use safe method to return to interval. |
|
|
Term
| Fixed-point Iteration for Systems of Equations |
|
Definition
| For some starting vector x0, xk+1=g(xk), convergent if ρ(G(x))<1 where G(x) is the Jacobian of g evaluated at x. If G(x)=0 then convergence rate is at least quadratic. |
|
|
Term
|
Definition
|
|
Term
| Newton's Method for Systems of Equations |
|
Definition
At each iteration:
Solve Jf(xk)sk=-f(xk)
xk+1=xk+sk |
|
|
Term
|
Definition
B0=initial Jacobian approx (I)
for k = 0, 1, 2, ...
Solve Bksk=-f(xk) for sk
xk+1=xk+sk
yk=f(xk+1)-f(xk)
Bk+1=Bk+((yk-Bksk)skT)/(skTsk) |
|
|
Term
|
Definition
|
|
Term
|
Definition
| Newton step is computed as usual, but new iterate is taken to be xk+1=xk+αksk. Far from solution, step is often too large. Monitor ||f(x)|| and ensure that it decreases sufficiently each iteration. When close, αk=1 to maintain usual convergence. |
|
|
Term
| Newton's Method with Trust Region |
|
Definition
| Maintain an estimate of the radius of a trust region within which the Taylor Series approximation is sufficiently accurate. Adjust size of trust region as necessary to constrain step size. Large enough to permit full Newton steps when close. |
|
|
Term
|
Definition
| If f is unimodal on [a,b], x1,x2 in [a,b] with x1<x2. Evaluate f(x1), f(x2) and discard either [a,x1) or (x2,b]. Want τ2 = (1-τ). |
|
|
Term
| Successive Parabolic Interpolation |
|
Definition
| Initially, the function f to be minimized is evaluated at three points and a quadratic polynomial is fit to the three resulting function values. The minimum of the parabola is the new approximate minimum, and oldest of last three points is dropped. Repeat. |
|
|
Term
| Newton's Method for One Dimensional Optimization |
|
Definition
xk+1=xk - f '(xk)/f ''(xk)
f(x+h)≈f(x)+f '(x)h+.5f ''(x)h2
f '(x+h) ≈ f'(x) + f''(x)h = 0
h = -f '(x) / f ''(x) |
|
|
Term
| Safeguarded One Dimensional Optimization |
|
Definition
| Use interval bracketing to maintain a safe method whenever the fast method generates an iterate that lies outside the interval |
|
|
Term
|
Definition
x0=initial guess
for k = 0, 1, 2, ...
sk = -grad(f(xk))
Choose αk to minimize f(xk+ αksk)
xk+1=xk+ αksk |
|
|
Term
| Newton's Method for Unconstrained Optimization |
|
Definition
x0=initial guess
for k = 0, 1, 2, ...
Solve Hf(xk)sk=-grad(f(xk))
xk+1=xk+sk |
|
|
Term
|
Definition
Newton's method requires substantial amount of work per iteration (especially with dense Hessian). Reduce overhead or improve reliability.
xk+1=xk - αkBk-1grad(f(xk)) where αk is line search parameter and Bk is approximation to Hessian |
|
|
Term
| Conjugate Gradient Method for Unconstrained Optimization |
|
Definition
for k = 0, 1, 2, ...
Choose αk to minimize f(xk+ αksk)
xk+1=xk+ αksk
gk+1=grad(f(xk+1))
sk+1= - gk+1 + ||gk+1||/||gk|| sk |
|
|
