Page 141 -

have Cauchy’s steepest ascent. If f is concave
and one chooses H equal to the negative of the
inverse Hessian, we have the modified Newton’s
V method.

variable upper bound (VUB) A constraint
of the form: x ≤ x .
i
j
valid inequality An inequality constraint
variational calculus An approach to solv-
added to a relaxation that is redundant in the ori-
ing a class of optimization problems that seek a
ginal mathematical program. An example is a functional(y)tomakesomeintegralfunction(J)
linear form, ax ≤ b, used as a cutting plane in an extreme. Given F in C , the classical uncon-
1
the LP relaxation of an integer program. strained problem is to find y in C to minimize
1
A linear form that is a facet of the integer poly- (or maximize) the following function:
hedron.

x 1

J(y) = F(x, y, y )dx.
value iteration This is an algorithm for x 0
infinite horizon [stochastic] dynamic programs An example is to minimize arc length, where

that proceeds by successive approximation to sat- 2

F = (1 + y ). Using the Euler-Lagrange
isfy the fundamental equation
equation, the solution is y(x) = ax + b, where
a and b are determined by boundary conditions:

F(s) = Opt {r(x, s)+a P(x, s, s )F(s )},
0
1
s y(x ) = y and y(x ) = y .
1
0

If constraints take the form G(x,y,y ) = 0,
where a is a discount rate. The successive this is called the problem of Lagrange; other
approximation becomes the DP forward equa- forms are possible.
tion. If 0 <a < 1, this is a fixed point, and
Banach’s theorem yields convergence because variational crime Consider a linear vari-
then “Opt” is a contraction map. Even when ational problem a(u, v) = f (v), v ∈ V, f ∈
thereisnodiscounting, policyiterationcanapply. V ,a : V × V → C a sesqui-linear form, V a

Banach space. In two ways a discretization based
on a finite element space V can go beyond the
h
value (of a quantity) Magnitude of a particu-
usual Galerkin framework:
lar quantity generally expressed as a unit of mea-
surement multiplied by a number. (i.) The sesquilinear form a and the linear
form f may be replaced with mesh-dependent
approximations a : V × V → C and f :
h
h
h
h
variablemetricmethod Originallyreferred
V h → C. This happens, for instance, when
to as the Davidon-Fletcher-Powell (DFP)
numerical quadrature is employed for the eval-
method, this is a family of methods that
uation of integrals.
choose the direction vector in unconstrained
(ii.) The finite element space V might be
h
optimization by the subproblem: d ∗ in
non-conforming with respect to V , that is
argmax {gradf(x)d : d = 1}, where d
V ⊂ V .
h
is the vector norm (or metric) defined by the

quadratic form, d Hd. With H symmetric Whether these variational crimes still lead to a

and positive definite, the constraint d Hd = 1 meaningful discrete problem can be checked by
restricts d by being on a circle, i.e., equidistant means of Strang’s lemmas.
from a stationary point, called the center (the ori-
n
gin in this case). By varying H, as in the DFP variational inequality Let F : X → R .
update, to capture the curvature of the objective The variational inequality problem is to find x
function, f , we have a family of ascent algo- in X such that F(x)(y − x) ≥ 0 for all y in X.
rithms. Besides DFP, if one chooses H = I,we This includes the complementarity problem.
c
© 2003 by CRC Press LLC
© 2003 by CRC Press LLC