Question 10.9: Consider the unconstrained objective f(C) = 3C1² + 2C1C2 + 3......

The projection of objective f onto the\ C_1-C_2 plane (commonly referred to as a contour plot) is shown in Figure 10.18. It will be noted that all directions traveled in the cyclic coordinate search are parallel to the\ C_1  and  C_2 axes. The first direction is in the direction parallel to the\ C_1 axis, so the initial direction vector is\ v^{(0)} = (1,0) . The update to the next point\ C^{(1)} is

\ C^{(1)}=C^{(0)}+\xi v^{(0)}=(0,0)+\xi (1,0)=(\xi ,0),

where\ \xi = \xi^{(1)} for simplicity of notation. It follows that the objective function at the new points is\ f(C^{(1)}) =f(\xi, 0) = 3\xi^2 – 16\xi . Instead of using a line search, such as the golden ratio algorithm, we can find the minimum by setting the derivative of f equal to zero. Since f is now a function only of the variable ξ,

\ \frac{d}{d\xi}f(C^{(1)})=6\xi-16=0,\\\xi=\frac{8}{3}.

Therefore,\ C^{(1)} = (\frac{8}{3}, 0).

The question now is whether or not the process terminates. The Cauchy criterion compares\ C^{(1)} against\ C^{(0)} by simply considering the Euclidean two-norm, which is the same as the Euclidean distance between the two points. In this case,

\ \left\|C^{(1)}-C^{(0)}\right\|=\left\|(\frac{8}{3},0)-(0,0)\right\| =\frac{8}{3}.

Since the norm is relatively large, we conclude that a significant change has been made in the distance traveled, and thus we continue on to the next iteration. However, this time we go in the\ C_2 direction:\ v^{(1)} = (0, 1) . Proceeding as in the first iteration,

\ C^{(2)}=C^{(1)}+\xi v^{(1)}=(\frac{8}{3},0)+\xi (0,1)=(\frac{8}{3},\xi),\\[0.3cm] f(C^{(2)}) =f(\frac{8}{3},\xi) = 3\xi^2 – \frac{8}{3}\xi-\frac{64}{3}, \\[0.3cm] \frac{d}{d\xi}f(C^{(1)}+\xi v^{(1)})=6\xi-\frac{8}{3}=0.

It follows from this that\ \xi=\frac{4}{9}  and  C^{(2)} =(\frac{8}{3}, \frac{4}{9}). The norm defining the stopping criterion is now

\ \left\|C^{(2)}-C^{(1)}\right\|=\left\|(\frac{8}{3},\frac{4}{9})-(\frac{8}{3},0)\right\| =\frac{4}{9},

but this is still not “small”.

Therefore, we continue – but we cycle back to the vector\ v^{(2)} = (1,0). This gives

\ f(C^{(2)}+\xi v^{(2)})=3\xi^2+\frac{8}{9}\xi+\frac{1264}{81}.

This is minimized when\ \xi=-\frac{4}{27}\approx -0.1481, which implies that

\ C^{(3)}=C^{(2)}-\frac{4}{27}v^{(2)}\approx (2.5115,0.4444).

It follows that the norm is\ \left\|C^{(3)}-C^{(2)}\right\| \approx 0.1481 , which we might consider to be sufficiently small enough a change in position, and therefore terminate the process. Table 10.5 lists the sequence of iterates using two-decimal-place accuracy. It will be noted that even though approximation liberties were taken at intermediate steps, convergence to the correct solution (2.5, 0.5) is still accomplished in a timely manner. Also, we observe that in the case of cyclic coordinates, the norm is simply |ξ|.

TABLE 10.5   Sequence of Iterations for Example 10.9 Using the
cyclic coordinates Algorithm.

\ \begin{array}{c} \hline i&C^{(i)}&v^{(i)}&\xi&f(C^{(i)})\\\hline 0&(0.00,0.00)&(1,0)&2.67&0.000\\1&(2.67,0.00)&(0,1)&0.44&-21.333\\2&(2.67,0.44)&(1,0)&-0.15&-21.923\\3&(2.52,0.44)&(0,1)&0.05&-21.990\\4&(2.52,0.49)&(1,0)&-0.02&-22.000\\5&(2.50,0.49)&(0, 1)&0.01&-22.000\\6&(2.50,0.50)&(1,0)&0.00&-22.000\\\hline \end{array}