Concavity is valuable in connection with the *Gradient Method* of
minimizing
with respect to
.

**Definition. **The *gradient* of the error measure
is defined as the
column vector

**Definition. **The *Gradient Method* (Cauchy) is defined as follows.

Given , compute

Some general results regarding the Gradient Method are given below.

**Theorem. **If
is a local minimizer of
, and
exists, then
.

**Theorem. **The gradient method is a *descent* method, *i.e.*,
.

**Definition. **
,
, is
said to be in the class
if all th order partial
derivatives of
with respect to the components of
are
continuous on
.

**Definition. **The *Hessian*
of at
is defined as the matrix
of second-order partial derivatives,

The Hessian of every element of
is a *symmetric
matrix* [7]. This is because continuous second-order
partials satisfy

**Theorem. **If
, then any cluster point
of the gradient sequence
is necessarily a
*stationary point*, *i.e.*,
.

**Theorem. **Let
denote the concave hull of
. If
, and there exist
positive constants and such that

for all and for all , then the gradient method beginning with any point in converges to a point . Moreover, is the unique global minimizer of in .

By the norm equivalence theorem [4], Eq. (4) is satisfied whenever
is a *norm* on
for each
. Since
belongs to
, it is a symmetric matrix. It is also
bounded since it is continuous over a compact set. Thus a sufficient
requirement is that
be *positive definite* on
. Positive
definiteness of
can be viewed as ``positive curvature'' of at
each point of
which corresponds to *strict concavity* of on
.

Download gradient.pdf

Download the whole thesis containing this material.

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

[Automatic-links disclaimer]