Page 201 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience

178 Chapter 8. The Simplex Minimization Search

Initialization Evaluate
Start
procedure function

Not
Generate new Satisfied
Constraints set of search Termination
Criterion
locations
Satisfied
Basic search algorithm
Stop

Figure 8.1: Basic building blocks of constrained optimization methods

geometrical :gure that consists, in N dimensions, of N +1 vertices and all their
interconnecting line segments, polygonal faces, etc. Thus, in two dimensions,
a simplex is a triangle, whereas in three-dimensions it is a tetrahedron. A non-
degenerate simplex is one that encloses a :nite inner N -dimensional volume.
To minimize a function of N independent variables, the SMmethod must be
initialized with N +1 points (or search locations) de:ning an initial nondegen-
erate simplex. The method then takes a series of steps: re'ecting, expanding,
or contracting the simplex from the point where the function value is largest,
in an attempt to move it to a better point. Thus, the simplex is adapted to
the local landscape of the function surface: expanded along inclined planes,
reCected on encountering a valley at an angle, and contracted in the neigh-
borhood of a minimum. This process continues until a termination criterion is
satis:ed. The SMmethod is described in more detail in Figure 8.2.

8.3.2 Simplex Minimization for BMME: Why?

The SM optimization method is an attractive choice for solving the BMME
optimization problem for the following reasons:
1. Most fast BMME algorithms are based on a unimodal error surface
assumption. As already shown (Property 4:6:7:3), this assumption does
not hold true in most cases. For this reason, such algorithms are easily
trapped in local minima, giving a suboptimal prediction quality. The SM
method, however, is not based directly on this assumption.

2. Most fast BMME algorithms and optimization methods work by fol-
lowing the direction of the minimum distortion. The SMmethod,