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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

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

%d bloggers like this: