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" ) on an open domain
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 with 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 differentials of 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...
(2007-09-23)
Calculus of Variations
(cf. Lagrangian mechanics)
Euler-Lagrange equations hold whenever a path integral
is stationary.
Let L be a smooth enough function
of 2n+1 variables:
L =
L ( q 1 , q 2 ... q n ,
v1 , v2 ... vn , t )
Assume that the first n variables (q) are actually functions of the
last one (t) and also that the subsequent variables (v)
are their respective derivatives:
| v i (t) = |
d |
q i (t) |
|
| dt |
This makes L a function of t alone and we may consider
the following integral S (called the "action" of L )
for given [fixed] values at both extremities of all the
2n quantities
q i (a) and
q i (b).
The fundamental problem of the calculus of variations is to
establish the local conditions which make S stationary,
for optimal functions q i .
Namely:
Euler-Lagrange equations
| ¶ L |
= |
d |
( |
¶ L |
) |
|
|
|
| ¶ q i |
dt |
¶ vi |
|
Proof :
From a set of optimal functions q i
and arbitrary (sufficiently smooth) functions
h i which vanish at both extremities
a and b, we may construct the following family of
functions, depending on a single parameter x :
| Q i (t) = q i (t) +
x h i (t)
| |
V i (t) = v i (t) +
x |
d |
h i (t) |
|
| dt |
Those yield a value S(x) of the action which must be
stationary at x = 0
(since the functions q i
are optimal). Thus, the derivative of S(x) vanishes
at x = 0:
| 0 = |
ò |
b |
å i |
[ |
h i |
¶ L |
+ |
d h i |
|
¶ L |
] dt |
|
|
|
|
| a |
¶ q i |
dt |
¶ vi |
Since every h i vanishes at both extremities
a and b , we may
integrate by parts
the second term of the square bracket to obtain:
| 0 = |
ò |
b |
å i |
h i |
[ |
¶ L |
- |
d |
( |
¶ L |
) |
] dt |
|
|
|
|
| a |
¶ q i |
dt |
¶ vi |
As h i is arbitrary, the square bracket must vanish
everywhere, for every i.
Example :
Video:
Lagrangian & Field Theory
by Leonard Susskind
blog
(2008-11-10)
The Isoperimetric Inequality
Among planar loops of unit length, the circle encloses the largest area.
If P is the perimeter of a closed planar curve and S
is the surface area it encloses, then:
S ≤ P 2 / 4p
Let's see how the above formalism of the
calculus of variations
can be used to show ...
The three-dimensional equivalent of the isoperimetric inequality says that the
closed surface of area S which encloses the largest volume
V is a sphere.
V 2 ≤ S 3
/ 36 p
We conjecture that
the above generalizes to n dimensions:
No hypersurface of hyperarea S encloses a larger
hypervolume V than the hypersphere.
This makes the relations given in the
oldest Numericana article yield:
V n-1 ≤
G ( 1 + n/2 )
[ S / nÖp ] n
(2008-11-10)
Plateau's Problem
The surface of least area with a given border.
The Plateau rules (1873
state that the solutions are smooth surfaces of constant mean curvature with only
two possible types of singularities:
lines where 3 such smooth surfaces meet at
120° angles and isolated points
where 4 of those lines meet in a regular tetrahedral configuration.
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.
(2008-11-09)
Shortest Way to Connect Three Points
How to connect three dots with lines of least total length?
The three vertices of a triangle ABC
can be connected using just two of its three sides.
Unless the three points are aligned, this is not
the most economical way to do so.
Instead, we may use three straight lines (OA, OB, OC)
connecting the vertices to some center (O)
which is yet to be determined.
For the optimal center O, the three lines
OA, OB and OC
meet at 120° angles.
(2008-11-09)
The Honeycomb Theorem
In 1999, Thomas Hales finally proved
an "obvious" fact.
Nobody questioned
the celebrated Honeycomb conjecture
before 1993, when Phelan and Weaire showed its
3D counterpart (Kelvin's conjecture)
to be false!
The issue was settled in
1999
with a proper proof by Thomas C. Hales :
Thus, the 2D Honeycomb conjecture
is now a theorem! Here it is:
Honeycomb Theorem
In any partition of the plane into tiles of unit area,
each tile cannot have a lesser perimeter than the regular hexagon
of unit area.
(Loosely speaking, the regular honeycomb tiling
is the most economical one.)
The first proof by
Thomas C. Hales
(1999)
was surprisingly intricate.
It was crucial to get rid of the
convexity restriction which earlier authors had reluctantly imposed.
(The isoperimetric inequality
implies that the boundaries between
optimal shapes are either circular arcs or straight lines.
Both sides of such a boundary are convex only in the latter case.)
The reason curved boundaries are ruled out
is not at all obvious; it is false
in the 3D case.
(2008-11-09)
On Minimal Foams
Kelvin's problem & counterexamples to Kelvin's conjecture.
The Kelvin problem asks for a partition of space into cells of equal volume and minimal area.
It has been described by
Simon Lhuilier
(1750-1840) and others as one of the most difficult problems in geometry.
In 1993, Denis Weaire and Robert Phelan disproved Kelvin’s conjecture
by describing a totally different structure
which turns out to be more economical than Kelvin's.
The A15 Weaire-Phelan
structure is one example of the so-called Frank-Kasper foams.
It consists of two distinct types of cells having
either pentagonal or hexagonal faces;
one is a squashed dodecahedron, the other is a tetradecahedron.
