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

parameter space. Geometric problems that define vertex placement or selection can have tens of thou-
sands of vertices and, of course, triple the number in coordinate values. Animation problems might
have a relatively small set of parameters, such as velocity or torque, but require the values for these
parameters over thousands of frames of animation. The resulting high-dimensional parameter space
can be too complex for an animator to easily set the parameters and produce the desired motion.
The other common feature is that the function that evaluates the parameters to find the “best” values
is not an analytic function; rather, it is a rather computationally expensive procedure. Thus, techniques
that require fewer function evaluations are preferred.
Optimization is finding the optimal, or best, value among a set of alternatives. For the current dis-
cussion, the minimum function value is sought over the space spanned by the function's parameters.
For example, in Equation B.158 , the minimum value is 1.

min
x 2 ℜ

f ðxÞ (B.158)

n

Alternatively, optimization can also be expressed in terms of finding the values for a set of
input parameters that minimize (or maximize) a function's single output value. For example, in
Equation B.159 , the input value that corresponds to the function's minimum is 0.
arg min
x 2 ℜ

f ðxÞ (B.159)

n

The number of parameters and their possible values define the search space. The input parameters may
be unconstrained ,asin“ x in reals,” or the optimization problem may be constrainted ,asin“ x greater
than 0.” The constraints can include equality as well as inequality constraints ( Eq. B.160 ).

minimize f ð X Þ

Subject to c i ð X Þ¼ 0 i ¼ 1 ; 2 ; ...; k eq (B.160)

Subject to c j ð X Þ¼ 0 j ¼ 1 ; 2 ; ...; k le

The function, f , can be anything that is able to be evaluated given values for its input parameters. As
mentioned, in computer graphics applications, the function is often not analytically defined because the
function is actually an arbitrarily complex procedure that produces a value such as the time it takes to
get somewhere, or a motion that minimizes the maximum torque during some task.
This discussion of optimization will often consider minimizing a function, although it obviously
does not matter whether we are trying to minimize or maximize something—a function to be maxi-
mized uses the same principles as a function to be minimized, or, if desired, a function to be maximized
can be negated and the resulting function considered for minimization. Numerical optimization is often
used in situations in which the function is not analytic and an exhaustive search over the parameter
space is not feasible because the function is very expensive to evaluate, or because the parameter space
is very large, or both.
Optimization techniques can be characterized by the type of function, the type of input parameters, the
number and type of constraints, the type of the output value(s), and so forth. The function can be analytic,
comprised of mathematical operations that can be evaluated given the input values. The functionmight, or
might not, be continuous and differentiable. The input parameters and/or function value might be reals or
could be restricted to integer values ( integer programming ) or might be a mixture of integers and reals
( mixed programming ). The function can be relatively simple to compute or it can be computationally