II.1.5.2: Cubics and Quartics
Suppose is a cubic, which is non-trivial in the sense that its third derivative is non-zero. Thus has no minimum or maximum, because it is unbounded below and above. This immediately shows there can be no linear or quadratic majorizer of , because if there was then would be a non-trivial cubic, which does not have a minimum.
For a quadratic to majorize a non-trivial quartic at we must have for all . Of course is a constant, independent of , for a quartic. This can be written as for all , where If > no quadratic majorization exists. If < we complete the square to and see we must have
Example 1: In our first example we use the polynomial , and we show quadratic majorizers using for equal to and .
Note that the quadratic majorizer for is concave, which means it does not have a minimum and we cannot carry out a majorization step. All four majorizers have two support points, one at and the other at , which is the solution of if .
The R
code for drawing the figures is in quarticCubicMe.R
. Note the function quarticCubicMe
does not return anything, it is merely used for its graphical side effects.
The majorization algorithm corresponding to our quadratic majorization is If it converges to a stationary point at with and then the iteration radius is Note that in the quartic case both and are quadratics, so the convergence rate is a ratio of two quadratics. If and then . If then and we have superlinear convergence. If and we have and convergence is sublinear.
Example 2: We illustrate this with the quartic which has both and . Quadratic majorizers are shown in Figure 2.
The iterative majorization algorithm in
itQuartic.R
, which stops if we have reached a solution to within 1e-10, has not converged after 100,000 iterations.
Iteration: 100000 xold: -0.99998667 xnew: -0.99998667 fold: -0.29166667 fnew: -0.29166667 lbd: 0.99998000
$x
[1] -0.9999867
$lbd
[1] 0.99998
Example 3: The next quartic has and . This implies that for all , which in turn implies that quadratic majorizers using have their minima or maxima at 1. We identify the polynomial by requiring , and . This gives Quadratic majorizers are in Figure 3.
In this case the majorization algorithm converges to the solution in a single iteration, no matter where we start. This is true even if the quadratic is concave, because then the update actually goes to the maximum of the majorizing quadratic (which means that, strictly speaking, we do not make a majorization step).
If we want to majorize a quartic by a cubic then we can use the same reasoning as before to come up with In each iteration we have to minimize the cubic over . This needs to be qualified, of course, because the cubic does not have a minimum. So we modify the rule to choosing the local minimum of the cubic, if there is one. Differentiating the implicit function for the update gives and thus at a fixed point the iteration radius, using , it is We have fast convergence if is close to , and superlinear convergence if .
Example 4: In Figure 4 we use the quartic again to illustrate cubic majorization with cleverly chosen to be . The cubic majorization functions are much closer than the quadratic ones in Figure 1.
Table 1 shows different iteration counts for different values of In this case we have , where .