Background Information and Techniques - Computer Animation: Algorithms and Techniques - page 487

expensive to evaluate. The derivative might have similar variations. There might be constraints on the
values that the input parameters can have ( constrained optimization ), and the functionmight havemultiple
output values. Because optimization can be applied in a variety of situations under a variety of assump-
tions, strategies come in many forms. As a result, optimization does lend itself to a nice single taxonomy.

B.9.1 Analytic Solution
Many approaches to optimization are merely extensions of basic calculus taught in high school physics
or calculus class. A basic analytic approach usually involves finding the optimal input x * that mini-
mizes (or maximizes) a function f ( x ) by computing a solution to f 0 ( x *)

¼ 0 where the second derivative

at x indicates a minimum ( f 00 ( x *) 0) or a maximum ( f 0 ( x *)

> < 0). In this case, optimization needs to

find the roots of the first derivative.
If f 00 ( x ) 0 for all x , then the function is considered convex . Convex means that the function's slope is

always increasing. This is important because it means that, assuming f 0 ( x ) is negative at negative infinity,
it will increase until it reaches zero and that, once f 0 ( x )

>

0, it will continue to increase as x increases; that
is, it will never go back down to zero. This means that f ( x *) is a minimum ( f 0 ( x *)

¼

0and f 00 ( x *)

0) and
there is no other minimum because f 0 ( x ) will never get back down to zero; that is, x *isa global minimum
of the function. Similarly, if f 00 ( x )

¼ >

0 for all x , then the function is concave and x * is a global maximum.
It should be pointed out that if the derivative function is not easily available or computable, then approx-
imations to the derivative by finite differencing can be used with a corresponding degree of inaccuracy.
Functions that are not convex do not necessarily have a global minimum. In such cases, the initial guess is
important as this will dictate which, if any, minimum is found.

<

B.9.2 Numerical methods
At the risk of oversimplifying the area, there are two basical approaches to numerical optimization. The
first simply randomly samples values of the function and adaptively samples more often in areas of the
parameter space where lower values are found. This approach is usually used for functions in a high
dimensional space where there are many local optima, so the random sampling hopes to uncover the
global optimum or at least an acceptable near-global optimum. This is guaranteed to succeed only in
the limit (i.e., taking an infinite number of samples). The second approach to numerical optimization uses
knowledge about local trends of the function value to search in a particular direction. The direction is
based on derivatives of the function or finite difference approximations to the derivative. The derivative
indicates which direction to follow in order to reduce (or increase) the function value. The local minimum
(maximum) is found when the derivative is equal to zero and the second derivative is positive (negative).
Gradient information can be used to direct the search of parameter space to drive the function to a
minimum or drive the derivative to zero. In cases where f 0 ( x ) 0 cannot be solved analytically, numer-

ical techniques can be used to find its zero values. The Taylor series expansion of a function g ( x þ dx )is
shown in Equation B.161 using the big O notation as a function of x

¼

2 to represent the error term when

using the first two terms as an approximation to g ( x þ dx ).

0

2

gðx þ dxÞ¼gðxÞþg ðxÞdx þ Oðdx Þ (B.161)

a * g 0 ( x 0) can be computed if g 0 ( x ) can be computed or is estimated.
With the objective of driving the value of g () to zero with successive guesses, the Taylor approximation

If x 0 is an initial guess, x 1 ¼ x 0