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.