A certificate for the worst direction

The criterion with no derivative ended on an uncomfortable admission. Of the four design criteria measured in this field, three come with a certificate — an equality anybody can check with a matrix inverse, saying the design in hand cannot be improved — and the fourth does not. E-optimality, which maximises the smallest eigenvalue of the information matrix and so protects the worst-determined combination of coefficients, had an answer reported as the best of forty thousand iterations of a search. The essay named the theorem that would close the gap and did not implement it.

It is implemented here, and for the second-order model on a square the answer turns out to be short enough to write in one line. The design the search was approaching is E-optimal, the proof is a polynomial that never exceeds one fifth, and the certificate has a structure that explains exactly why a derivative could not find it.

What a certificate for a smallest eigenvalue has to be #

The smallest eigenvalue of a symmetric matrix M is a minimum: it is the least value of $v'Mv$ over unit vectors v, and equivalently the least value of $\operatorname{tr}(ME)$ over matrices E that are non-negative definite with trace one. That second form is the whole of the method. Take any such E and compute $f(x)'Ef(x)$ at every setting x in the region, where $f(x) = (1, x_1, x_2, x_1x_2, x_1^2, x_2^2)$ is the model’s vector. If that function never exceeds a number c, then for every design ξ,

$$\lambda_{\min}(M(\xi)) \;\le\; \operatorname{tr}(M(\xi)E) \;=\; \int f(x)'Ef(x)\,d\xi(x) \;\le\; c .$$

No design on the region has a smallest eigenvalue above c. If one design reaches c, it is optimal, and E is its certificate.

For a smooth criterion the certificate is forced: it is the design’s own derivative, and checking it is evaluation. The theorem that says when to stop is the D-optimal case, where the function to bound is the prediction variance and c is the number of parameters. For E-optimality, when the smallest eigenvalue is simple, E is forced too — it is $vv'$ for the one eigenvector — and the certificate is again a line to check. When the minimum is attained more than once, E can be any trace-one mixture of the eigenvectors that share it, and the certificate exists only if some mixture works. Finding it is a small convex problem: choose the mixture that makes the largest value of $f'Ef$ over the region as small as possible, and see whether that value reaches the smallest eigenvalue.

The design the search was approaching #

The subgradient search of the earlier essay finished at a design with 0.3979 of its weight at the centre, 0.1000 at each of the four edge midpoints, and between 0.0505 and 0.0506 at each corner. Those numbers look like approximations to simple fractions, and the obvious guess is that the search was converging to two fifths at the centre, a tenth at each edge midpoint and a twentieth at each corner, which sum to one.

The guess is easy to check, because at those weights every entry of the information matrix is a simple fraction and its eigenvalues come out exactly. They are 1⁄5, 1⁄5, 1⁄5, 2⁄5, 2⁄5 and 7⁄5. The minimum is one fifth, and it is attained three times — not twice, as the search’s design suggested. The third copy belongs to the interaction coefficient, whose precision is the total weight on the four corners, $4 \times 1/20 = 1/5$. The search’s design had put a little too much weight there, lifting that eigenvalue to 0.20214 and leaving the other two at 0.19999, so it showed a corner of multiplicity two near an optimum that has multiplicity three.

The exact design’s smallest eigenvalue is above the search’s, so the search had not arrived. Whether the exact design is the optimum is a separate question, and only a certificate can answer it.

The certificate, found and then written down #

The three eigenvectors at the minimum span a three-dimensional space, and a certificate is a trace-one non-negative definite matrix on it: five free numbers. A direct search over them, measuring the largest value of $f'Ef$ on an 81 by 81 grid of the square, brings that largest value down to within 4.1 × 10⁻⁸ of one fifth. The matrix it finds has almost no weight on the interaction direction and is lopsided between the two factors, and averaging it with its own mirror image — which is again a certificate, since the conditions are convex and the design is symmetric — gives something that can be read off exactly:

$$f(x)'Ef(x) \;=\; \tfrac15\,(1 - x_1^2 - x_2^2)^2 \;+\; \tfrac15\,(x_1^2 - x_2^2)^2 \;=\; \tfrac15 \;-\; \tfrac25\left[x_1^2(1-x_1^2) + x_2^2(1-x_2^2)\right].$$

The second form makes the proof immediate. On the square each coordinate lies between −1 and 1, so each $x_i^2(1 - x_i^2)$ is non-negative, and the certificate is at most one fifth everywhere. It equals one fifth exactly where both of those terms vanish, which is where each coordinate is −1, 0 or 1 — the nine points of the 3² grid and nowhere else. The matrix E behind it has trace one and eigenvalues 3⁄5 and 2⁄5, with the rest zero, so it is admissible. And under the exact design every support point sits at one fifth, so $\operatorname{tr}(ME)$ equals the smallest eigenvalue.

So no design on the square — not on a grid of candidates, but on the continuous region — has a smallest eigenvalue above one fifth, and the nine-point design reaches it. The design with 2⁄5 of its weight at the centre, 1⁄10 at each edge midpoint and 1⁄20 at each corner is E-optimal. The criterion that had only a best-so-far now has a proof shorter than the search that approximated it.

The certificate also answers a question the earlier essay could only describe. Its support is the 3² grid not because the search happened to put weight there but because those are the only points where the certificate touches its bound: any optimal design must put all its weight where $f'Ef$ equals one fifth, and that set is exactly those nine points. The shape of the answer is read off the shape of the proof.

The choice a derivative cannot make #

The two pieces of the certificate are the two eigen-directions it uses. The first, proportional to the coefficient combination $(1, -1, -1)$ on the intercept and the two squared terms, is the direction that separates the intercept from the curvature — the one the earlier essay identified as hardest to determine, because every corner has $x_1^2 = x_2^2 = 1$. The second, proportional to $(0, 1, -1)$ on the squared terms, is the difference between the two curvatures, determined only by the edge midpoints.

Either piece alone is the certificate a derivative-following method would offer, since a derivative picks out one eigenvector at a time. And either alone fails. At full weight, $(1 - x_1^2 - x_2^2)^2/3$ reaches 1⁄3 at the centre and the corners, and $(x_1^2 - x_2^2)^2/2$ reaches 1⁄2 at the edge midpoints — each well above one fifth, so neither proves anything.

The mixture’s largest value is 0.5 with all the weight on the second piece and 0.333 with all of it on the first. In between it falls, reaching one fifth at exactly three fifths on the first piece and two fifths on the second, and rising again on either side — 0.25 at an even split, 0.233 at seven tenths. The certificate is a point, not a region, in this family. A method that follows one eigenvector at a time oscillates between two failing certificates and cannot land on the one that works, which is the corner the earlier essay drew as two lines crossing, now seen from the side of the proof.

The interaction direction gets no weight at all, although its eigenvalue is also one fifth. That is a statement about which constraints bind. Lowering the corners’ weight would lower the interaction’s precision below one fifth; raising it would starve the other two directions. The interaction sits at the minimum because the optimum has no slack to give it more, not because it is part of what makes the design optimal, and the certificate is the instrument that tells those two apart.

What the search was worth #

With the optimum known exactly, the search can be scored against it instead of against itself.

The gap is 5.28 × 10⁻² after ten iterations, 8.88 × 10⁻³ after a hundred, 6.94 × 10⁻⁴ after a thousand and 1.34 × 10⁻⁵ after forty thousand, where the search sits at 99.993% of the optimum. Over the last two decades it falls faster than the $1/\sqrt t$ the method guarantees, which is a property of this problem rather than of subgradient methods. The derivative-based multiplicative update stopped at 0.0744, which is 37.2% of the optimum — the number the earlier essay reported as a share of the search’s best, and which turns out to be a share of the true optimum to the same three figures.

So the earlier essay’s numbers were right to the precision they were quoted at. What has changed is the kind of statement they are. “The best of forty thousand iterations is 0.19999” was a report about an algorithm. “No design on the square exceeds 1⁄5” is a statement about the problem, and the algorithm’s answer is now something that can be graded.

An audit that needs no optimum, and is weak here #

The other use of a certificate is auditing. The theorem that says when to stop turns the D-optimal equality into an inequality any design satisfies: its D-efficiency is at least the number of parameters divided by its own largest prediction variance, a bound computable from the design alone. The same move works for E. Any trace-one E gives a bound, so a design’s own smallest eigenvector gives one: its E-efficiency is at least its smallest eigenvalue divided by the largest value of $(f'v)^2$ over the square.

The bound holds for all seven and it is loose for all seven. The D-optimal measure is 49.6% efficient for E and its own eigenvector proves only 17.2%; the A-optimal measure is 82.6% efficient and proves 34.1%; the I-optimal measure 87.7% and 36.7%. The face-centred composite with five centre runs is 76.9% efficient and proves 30.8%. Even the search’s own design, at 99.99%, proves only 40.0% from its own smallest eigenvector.

That last row is the non-smoothness once more. The search’s design has a simple minimum, so its own certificate is forced to be a single direction, and a single direction cannot certify a design whose optimum needs a mixture of two. Widening the audit to every eigenvector within 10% of the smallest — three of them for the search’s design — and choosing the best mixture among those lifts its bound to 99.66%. The I-optimal measure has two eigenvalues within that band and its bound rises from 36.7% to 68.8%; the other five designs have a smallest eigenvalue more than 10% below the next, so the wider audit is the narrow one again and changes nothing. An E-audit is therefore informative near the optimum and nearly useless away from it, which is the reverse of what an auditor wants. Now that the optimum is known exactly, the efficiencies in the figure need no audit — each is the design’s smallest eigenvalue divided by one fifth — but on a region or model without a closed-form certificate, the weakness of the cheap bound is the honest state of things.

What the proved design gives up #

A certificate settles what the criterion asks for. It does not settle whether the criterion is the right one, and with the optimum exact the trade can be priced exactly too.

Against the D-optimal measure, the E-optimal design has a D-efficiency of 73.4%: measured by the volume of the confidence ellipsoid it is a quarter worse. Against the A-optimal measure its average coefficient variance is 145⁄7, about 20.71, where the A-optimum reaches 17.89 — an A-efficiency of 86.4%. Those are the costs of insisting on the worst direction, and they are real.

What they buy is visible coefficient by coefficient. Under the D-optimal measure the intercept’s variance is 6.00 and each squared term’s 5.38, while the interaction’s is 1.71 and each linear term’s 1.35: D spends lavishly on the coefficients that are cheap to determine and leaves the intercept and the curvature as its worst. Under the E-optimal design the intercept falls to 15⁄7, about 2.14, and each squared term to 30⁄7, about 4.29, while the interaction rises to 5.00 and each linear term to 2.50. The design moves information from the easy directions to the hard one until three of them are equally hard, which is exactly what a minimum attained three times means.

Whether that is a good trade depends on the question the experiment is for. An experimenter who needs the height of the surface at its centre and its curvature — to locate an optimum, say — is asking about the directions E protects, and the two terms anybody wanted found a criterion aimed at the quadratic terms alone rewarding a similar shift towards the centre. An experimenter who mainly wants the slopes is better served by D. An efficiency that is a ratio is the general warning that every number in this paragraph is relative to a criterion someone chose, and the certificate does not choose it.

What is proved here, and what is not #

Proved: on the square $[-1, 1]^2$, under the full second-order model in two factors, no approximate design has a smallest information eigenvalue above 1⁄5, and the nine-point design with weights 2⁄5, 1⁄10 and 1⁄20 reaches it. The proof is the closed-form certificate and the inequality above, and it involves no grid: the grid was used to find E, and the closed form was then checked algebraically, with its value compared with $f'Ef$ for the stated matrix at forty thousand settings to twelve decimal places as a guard against a transcription error.

Not claimed: that this design is the only E-optimal one. Any optimal design must be supported on the nine touching points, but whether another weighting of those nine also reaches 1⁄5 is not settled here. Nor is anything claimed about exact designs with a fixed number of runs — at twenty runs, the fractions ask for eight at the centre, two at each edge midpoint and one at each corner, which happens to be a whole number of runs, but at most run counts it is not, and the design that has to be integers is about what rounding costs. And the price of choosing E over the other criteria is unchanged: the cross-table in four letters and two camps still applies, with E’s row now exact.

Still open: the disc, and a third factor #

The proof leans on the square. Each coordinate’s term $x_i^2(1 - x_i^2)$ is non-negative because each coordinate lies in $[-1, 1]$ separately, and the 3² grid is where both vanish. On a disc of radius one the coordinates are not separately bounded, the corners do not exist, and the certificate has to be a different polynomial — presumably one depending on $x_1^2 + x_2^2$ alone, by the disc’s rotational symmetry, touching its bound at the centre and on the whole boundary circle. Whether such a certificate exists, what the E-optimal design on the disc is, and whether its weight at the centre is again two fifths, is a computation the same convex search can make.

The other extension is a third factor. The obvious conjecture is the 3³ grid with weights falling by a factor at each step outwards and a certificate of the same two-piece form, one piece separating the intercept from the curvatures and the others separating curvatures from one another. With three squared terms there are two independent differences of curvature rather than one, so the mixture has more than one free number, and whether a certificate still exists at a single point of that family — or whether the optimum moves off the grid — is not known here. Augmenting a design that has already run showed the smooth criteria’s certificates surviving a change of problem with one number altered; whether E’s survives a change of dimension is the same kind of question, and now has a method.