Objectives, Stationary Points, and Local Optima

An optimization problem contains variables, an objective, a feasible set, and sometimes several competing criteria. The optimizer can only improve the mathematical problem it receives. A stationary point satisfies a local first-order condition. It may be a minimum, maximum, saddle, or flat region. The objective's global structure determines which conclusions are justified.

Before selecting an algorithm, the modeling team should ask whether the objective represents the real decision and whether its variables include every controllable choice. What that question is worth is on the record. A commercial risk-prediction algorithm affecting millions of patients was trained on health-care costs as a surrogate for health need. The decision it fed was who receives extra help. Obermeyer and three colleagues dissected it in Science in 2019, and correcting the substitution changes who is selected: “Remedying this disparity would increase the percentage of Black patients receiving additional help from 17.7 to 46.5%.” No optimizer in that pipeline was failing. The declared objective was.

Optum's Impact Pro, the risk-prediction system named in the New York regulators' letter of 25 October 2019, separates optimization from utility line by line.

A zero gradient is not a complete classification. Supplying the missing classification is not merely tedious. It is provably intractable, for the simplest nonconvex objective there is. Deciding whether a given point of a nonconvex quadratic program is a local minimum is NP-hard: Murty and Kabadi showed it in 1987, and Pardalos and Schnitger showed the same for constrained quadratic programs in 1988. Whether a local minimizer could nonetheless be found efficiently was left open, and it sat on Pardalos and Vavasis's 1992 list of seven open problems in complexity theory for numerical optimization, phrased this way: “Murty and Kabadi (1987, [11]) and Pardalos and Schnitger (1988, [12]) have shown that it is NP-hard to test whether a given point for such a problem is a local minimizer, but that does not rule out the possibility that another point can be found that is easily verified as a local minimizer.” The open problem stood for three decades. Ahmadi and Zhang closed it in 2022.

The flat column of the comparison is not a metaphor either. Sagun and four colleagues measured the Hessian spectrum of trained networks in 2017, and found it comes in two pieces: “we empirically show that the spectrum of the Hessian is composed of two parts: (1) the bulk centered near zero, (2) and outliers away from the bulk”. Most directions in parameter space carry essentially no curvature, which is what weak identification looks like numerically. The same abstract draws the consequence — “the flatness of such landscapes (which can be measured by the singularity of the Hessian) implies that classical notions of basins of attraction may be quite misleading”. Papyan reports the same geometry independently across deep-learning spectra in 2020: “These include spectral outliers, "spikes", and small but distinct continuous distributions, "bumps", often seen beyond the edge of a "main bulk".”

Keeping these pieces separate prevents algorithm choices from hiding modeling decisions. Impact Pro separates cleanly along exactly these lines: the variables and the objective were about recorded cost, the decision the system fed was about need, and only an evaluation rule aimed at the second quantity could ever have shown that the first was standing in for it.

For an unconstrained differentiable problem, a local interior optimum must have zero gradient. This is a necessary condition, not a sufficient one. With constraints, only feasible directions matter. A nonzero gradient can point outside the allowed region while no feasible descent direction remains. For nonsmooth objectives, gradients may not exist. Subgradients, proximal operators, or other generalized conditions replace the ordinary stationary equation.

The multiplier conditions that describe optimality at a constraint boundary have a disputed date. Kuhn and Tucker published them in 1951. William Karush had already obtained them in 1939, in an unpublished University of Chicago master's thesis, and never advertised the fact. Richard Cottle documented the priority in 2012; his prologue says of Karush's work: “It tells the story of fundamental optimization results that he obtained in his master’s thesis: results that he neither published nor advertised and that were later independently rediscovered and published by Harold W. Kuhn and Albert W. Tucker.” That is why the conditions carry three initials today rather than two.

A clear formulation prevents algorithm tuning from masking a misspecified objective. Step 5 is where a cost column standing in for health need gets written down as a surrogate rather than passed off as the target. Step 6 is where someone measures the system against need instead of against cost. Do that yourself, or a state Superintendent and a state Commissioner will do it for you.