Here I outline non-linear duality theory and Lagrangian relaxation and report a war story where this approach badly beat some efforts with simulated annealing.
Basically non-linear duality theory has some surprising properties commonly just too powerful to ignore.
Basically we're considering a case of optimization or mathematical programming.
So, let R denote the set of real numbers, and suppose positive integers m and n are given. Let R^n be the usual n-dimensional real vector space of n-tuples. To use matrix notation, we regard each n-tuple x in R^n as a matrix with n rows and one column, that is, as n x 1.
Similarly for R^m.
We are given set C a subset of R^n and functions
f: R^n --> R
g: R^n --> R^m
We seek x in R^n to solve non-linear program (NLP)
min z = f(x)
subject to
g(x) <= 0
x in C
where the 0 here is the m x 1 matrix of zeros.
We let the feasible region R, a subset of R^n, be
F = { x | x in C and g(x) <= 0 }
We regard g as m x 1 where for j = 1, 2, ..., m component j of g is
g_j: R^n --> R
where here g_j, borrowing TeX notation, is g with subscript j.
Okay, given 1 x m l, we let the Lagrangian
L( x, l ) = f(x) + l g(x)
Then for l >= 0 and x in F,
f(x) >= L( x, l )
and
z >= L( x, l )
Then the dual is to find l to maximize
M( l ) = min_{x in C} L( x, l )
Then M( l ) <= z to that M( l ) is a lower bound on z.
In particular (H. Everett), if g(x) = 0, l >= 0, and
z >= M( l ) = min_{x in C} L( x, l ) =
min_{x in C} f(x) + l g(x) = f(x)
and x in F so that x solves NLP.
A practical special case is essentially if spend all the productive resources and do so optimally, then are optimal.
Of course, the usual notation used for l is lambda, and for a while around DC Everett ran Lambda Corporation which did resource allocation problems for the US DoD.
Theorem: M is concave.
Proof: For t in the interval [0,1] and m x 1 l_1 and l_2, we have
M( tl_1 + (1 - t)l_2) =
min_{x in C} L( x, t l_1 + (1 - t) l_2) =
min_{x in C} f(x) + ( t l_1 + (1 - t) l_2) g(x) =
min_{x in C} ( t + (1 - t)) f(x) + ( t l_1 + (1
- t) l_2) g(x) =
min_{x in C} t L( x, l_1 ) + (1 - t) L( x, l_2 )
>= t min_{x in C} L( x, l_1 ) + (1 - t) min_{x in C} L( x, l_2 )
= t M( l_1 ) + (1 - t) M( l_2 )
so that M is concave. Done.
Immediately we have supporting hyperplanes for our concave M:
Suppose y and l are given and
M( l ) = L( y, l )
Then for 1 x m u,
M( l + u ) = min_{x in C} L( x, l + u )
= min_{x in C} ( L( x, l ) + u g(x) )
<= L( y, l ) + u g(x)
= M( l ) + u g(x)
so that for 1 x m u
s( u ) = M( l ) + u g(x)
is a supporting hyperplane for concave M( l ); that is,
M( l + u ) <= s( u ) = M( l ) + u g(x)
and s( 0 ) = M( l + 0 ) = M( l ).
So, here we have the basic theory of non-linear duality as needed by the iterative algorithmic approach of primal-dual Lagrangian relaxation.
War Story:
Once some guys had a big resource application problem having to do with a suddenly legal case of cross selling for banks. They had formulated their problem as a 0-1 integer linear program with ~40,000 constraints and 600,000 variables.
They had tried simulated annealing, ran for days, and quit with no idea how close they were to optimality.
I looked at their formulation and found that, except for 16 of the constraints, the problem was comparatively easy.
So, I wrote out
L( x, l ) = f(x) + l g(x)
where l was 1 x 16 and g represented the 16 troublesome constraints. The set C represented the 0-1 constraints and the rest of the 40,000 constraints.
Then for each l, finding x to solve
M( l ) = min_{x in C} L( x, l )
was easy. Then I just had to find l to solve
max M( l )
subject to
l >= 0
and that was just to maximize a concave function.
So, I did some primal-dual iterations:
Set
k = 1
Pick l^k >= 0
Step 1 (Primal):
Find x = x^k to solve
min_{x in C} L( x, l^k )
Then
M( l^k ) = L( x^k, l^k )
Step 2 (Termination)
If x^k in F then
M( l^k ) <= z <= f( x^k )
so that if
M( l^k ) - f( x^k )
is sufficiently small, then
terminate. Else if k i
to large, terminate.
Step 3 (Dual):
Find 1 x m u and w in R to solve
max w
subject to
w <= M( l^p ) + u g(x^p)
p = 1, 2, ..., k
Of course, this is just a linear
program. Set
l^(k + 1) = l^K + u
k = k + 1
Go to Step 1.
For the real problem, in 905 seconds on a 90 MHz processor, I ran 500 primal-dual iterations and, then, had a feasible solution, from the bound inequalities, guaranteed to be within 0.025% of optimality.
Worked fine! So, simulated annealing is not the only tool in the tool box! Sometimes Lagrangian relaxation can work well, too!