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

180 Chapter 8. The Simplex Minimization Search

7. It seems that the reCection step moved too far in the direction from p h to p m.
This is recti:ed by contracting the simplex from its highest point toward its centroid
using

p c = p h +(1 − )p m; (8.6)
where p c is the contracted point and 0 ≤ ≤ 1isthe contraction coe(cient. The function
is then evaluated at the new contracted point, giving f c = f(p c ). There are now two
possible cases:
(a) IF (f c¡f h ), then contraction has produced a better point. Thus, p h is removed
from the simplex and replaced by p c. The search then proceeds to step 8 to test for
convergence.
(b) ELSE it would appear that all the e+orts to move the highest point to a better location
has failed. All the vertices are, therefore, pulled toward the lowest point using

p i = p i + p l ; for all i (8.7)
2
8. Convergence is tested. IF the convergence criterion is satis:ed, then the search is stopped.
ELSE the search goes back to step 2.
Figure 8.2: Continued.

however, works by moving the point where the function value is largest
in di+erent directions using reCection, expansion, and contraction.
Thus, it explores directions other than that of the minimum distortion.
This makes the method more resilient to the local minimum pro-
blem.
3. As shown in Figure 8.1, a very important process in any optimization
method is the generation of a new set of search locations for the next
iteration. The performance and complexity of any method is highly de-
pendent on this process. The simplest approach is to use a predetermined
uniform distribution of search locations. This approach is adopted by
most fast BMME algorithms (see the Appendix). There are, however,
more complex approaches, like the use of crossover and mutation op-
erators in genetic algorithms or the use of gradients in gradient-descent
algorithms. The SMmethod is a compromise between the two extremes.
It uses very simple equations for reCection (8:4), expansion (8:5) and
contraction (8:6), as shown in Figure 8.2. As will be shown later, a
suitable choice of the coeDcients, ( ; ; ), can further reduce the com-
plexity of such equations.