Variable substitution in optimisation: a paradox

Given an optimisation problem of the form $\min_{x,y} \{f(x,y) = g(x) + h(y), g(x) = \alpha y\}$, where $\alpha \neq 0$, can we equivalently solve the problem $\min_{x,y} \{\alpha y + h(y)\}$?

This question was published in Harvey J. Greenberg’s “Myths and Counterexamples in Mathematical Programming,” which can be found online (see NLP Myth 5). The author points out to:

D. M. Bloom. FFF #34. The shortest distance from a point to a parabola. The College Mathematics Journal, 22(2):131, 1991,

where Bloom addresses the simple problem of determining the shortest distance between the point $(0,5)$ on the plane and the parabola $16y = x^2$.

A simple sketch reveals that the unique minimiser of this problem is the point $(0,0)$ and the distance is equal to 5.

The original problem, using the squared distance, is

\begin{aligned} \mathrm{minimise}_{x,y}\, &x^2 + (y-5)^2,\\ &\text{s.t.}\, 16y = x^2. \end{aligned}

Now if we simply substitute $x^2$ by $y$ we get the problem

\begin{aligned} \mathrm{minimise}_{y}\, &y + (y-5)^2. \end{aligned}

However, in doing so we have dropped the requirement that $y\geq 0$. This leads to the “paradox” that the solution of the second problem is $y=-3$ which corresponds to an imaginary x-coordinate.

The correct way to go is, of course, to use the KKT conditions of the original problems to determine its critical points.

mathbabe

Exploring and venting about quantitative issues

Look at the corners!

The math blog of Dmitry Ostrovsky

The Unapologetic Mathematician

Mathematics for the interested outsider

Almost Sure

A random mathematical blog

Mathematix

Mathematix is the mathematician of the village of Asterix