Vocabulary :
For an objective function of several variables, a "stationary point"
is a set of values of those variables where all partial derivatives
of the function vanish.
As illustrated below, a local extremum must be
a stationary point but the converse need not hold.
Because of the inclusive meaning
assigned by default to the simplest mathematical terms
(which is the exact opposite of the exclusive meaning often
attributed to simple words in everyday language)
most mathematicians consider "stationary point" and "saddlepoint"
to be synonymous:
At a saddlepoint, the relevant quantity may
rise in some directions and fall in others
but it's not required to do so...
There might very well be an extremum there!
Some authors reserve the term "saddlepoint"
to nonextremal stationary points.
We prefer to call those proper
saddlepoints
(thus following normal mathematical nomenclature).
(2007-09-23)
Optimizing a smooth function f
of a single variable.
'Tis little more than finding where the function's
derivative vanishes.
For a point x in the interior
of the domain of f and a small enough value
of e,
both points x-e
and x+e are in the allowed domain and
yield values of f which are on both sides of
f (x) if we just assume that f '
is nonzero. Therefore, there can be an extremum at point x
only when f ' (x) vanishes.
On the other hand, there's no such requirement for a point x
at the border of the allowed domain, because small displacements
of only one sign are allowed.
Away from the border, a saddlepoint x
(let's use that general term to indicate that
f ' (x) vanishes) will be
the location of a
minimum (resp. a
maximum )
when f '' (x)
is positive (resp. negative). If it's zero, further
analysis is needed to determine whether x
is the location of an extremum or not.
That discussion involving second-order
(or higher) derivatives is typical of what happens with
several variables when it comes to decide whether a saddlepoint
is an actual extremum, as illustrated in the
next article.
(E. M. of Wisconsin Rapids, WI.
2000-11-21)
Saddlepoints & Extrema
Determine the points where the [objective] function
z = 3x3+3y3-9xy
is maximized or minimized. [ Check for
second-order condition. ]
A necessary (but not sufficient) condition for a smooth function
of two variables to be extremal
( "minimized" or "maximized" )
is to be at a saddlepoint
where both partial derivatives vanish.
In this case that means:
9x2-9y = 0
and
9y2-9x = 0
Thus, an extremum of z can only occur when
(x,y) is either (0,0) or (1,1).
To see whether a local extremum actually occurs,
we must examine the second-order behavior of the
function about each such saddlepoint
(in the rare case where the second-order
variation vanishes, further analysis would be required).
Well, if the second-order partial derivatives are L, M and N, then
the second-order variation at point (x+dx, y+dy) is the quantity
½ [ L(dx)2 + 2M(dxdy) + N (dy)2 ]
We recognize the bracket as a quadratic expression whose sign remains the same
(regardless of the ratio dy/dx) if and only if
its (reduced) discriminant
(M2-LN) is negative.
If it's positive, the point in question is not an extremum.
In our example, we have L = 18x, M = -9 and N = 18y.
Therefore:
M2 - LN = 81 (1 - 4xy)
At (0,0) this quantity
is positive (+81).
Thus, there's no extremum there.
On the other hand, at the point (1,1)
this quantity is negative (-243) so the point (1,1) does
correspond to the only local extremum of z.
Is this a maximum or a minimum? Well, just look at the sign of L
(which is always the same as the sign of N for an extremum).
If it's positive, surrounding points yield higher values and,
therefore, you've got a minimum. If it's negative you've got a maximum.
Here, L = 18, so a minimum is achieved at (1,1).
To summarize: z has only one local extremum;
it's a minimum of -3, reached at x=1 and y=1.
Does this mean we have an absolute minimum?
Certainly not!
(When x and y are negative,
a large enough magnitude of either will make
z fall below any preset threshold.)
(2007-09-22)
Unconstrained (or "absolute") saddlepoints
Saddlepoints of a function of several independent variables.
We're seeking saddlepoints (stationary points) of a
scalar objective function
M of n variables x1 , ... , xn
which we view as components of a vector x.
M ( x1 , ... , xn ) = M ( x )
If those n variables are independent,
then a saddlepoint is obtained only at a point where
the differential form dM vanishes.
This is to say:
0 = dM = grad M . dx
As this relation must hold for any
infinitesimal vectorial displacement
dx, such absolute saddlepoints of M
are thus characterized by:
grad M = 0
That vectorial relation is shorthand for
n separate scalar equations:
| ¶ M |
= 0 |
 |
| ¶ xi |
(2007-09-22)
Lagrange Multipliers
An optimization involves one Lagrange multiplier per constraint.
Instead of a set of independent variables
(as discussed above) we may have to deal we several
variables that are tied to each other by some constraints.
For example, the variables may be subject to a single constraint :
E ( x1 , ... , xn ) = constant
While an unconstrained saddlepoint of M was obtained when dM = 0.
A constrained saddlepoint is obtained when dM is proportional to dE.
More generally, when k functions
E1 ... Ek are given to be constant,
a constrained saddlepoint of M is achieved when the
differential form dM is a linear
combination of the forms E1 ... Ek.
dM =
l1 dE1 +
l2 dE1 + ... +
lk dEk
In other words, there are k constants
li
(each is known as the Lagrange multiplier
associated with the corresponding constraint) such that the following
function has an unconstrained (or absolute)
saddlepoint.
M - (
l1 E1 +
l2 E1 + ... +
lk Ek )
(2007-09-23)
The fattest cone of given base...
What apex minimizes the lateral area of a cone of given base and volume?
The volume of a cone is one third of the product of its base area by its
height. So, by imposing the cone's volume, we're actually imposing
the height of the cone and looking for an optimal
apex somewhere in a fixed plane parallel to the base...
Denis Viala (2008-02-28)
Connect the dots, without crossings...
Given n blue dots and n
red dots in the plane (no 3 dots on the same line) there's always a
set of n disjoint segments with blue and red extremities.
HINT: This little puzzle appears among
optimization problems... Proof.
n=2, n=3, etc.
(2007-09-23)
Calculus of Variations
Euler-Lagrange equations hold whenever a path integral
is stationary.
