II.1.4.7: Majorizing Value Functions

Suppose and , i.e. for all and and for all and . Then, by weak duality, where Note that which means that actually and thus majorizes in .


Note: See how the following fits in 03/07/15. Or does it ?


Suppose the problem we want to solve is minimizing over and . If both minimizing over for fixed and minimizing over for fixed is easy, then we often use block-relaxation, alternating the two conditional minimization problems until convergence.

But now suppose only one of the two problems, say minimizing over for fixed , is easy. Define and let ( be any such that .

Suppose we have a majorizing function for . Thus Suppose our curent best solution for is , with corresponding . Let be any minimizer of over . Now which means that gives a lower loss function value than . Thus we have, under the usual conditions, a convergent algorithm.


Note: See how the following fits in 03/13/15. Or does it ?


Suppose and . Define . Then Not necessary that . Only has to majorize for to majorize, can be anything. This may be in the composition section.