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 .


plot of chunk qcm

Figure 1: Quadratic Majorization of a Quartic


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.


[Insert quarticCubicMe.R Here](../code/quarticCubicMe.R)


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. plot of chunk ex2

Figure 2: Quadratic Majorization of a Quartic at a Saddlepoint


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


[Insert itQuartic.R Here](../code/itQuartic.R)


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.


plot of chunk symq

Figure 3: Quadratic Majorization of a Symmetric Quartic


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.


plot of chunk qcub

Figure 4: Cubic Majorization of a Quartic


Table 1 shows different iteration counts for different values of In this case we have , where .


Table 1: Cubic Majorization of a Quartic