4.3.3 Optimization by Separation
This inequality indicates that the value of v · x at x
is less than or equal to the value at any other
point in the upper level set. In other words, x
minimizes the function v · x subject to the constraint
f(x) c.
To show that the feasible set has no points in h
+
we can check that for each feasible x:
v · (x x
) 0
v ·x v · x
This means that the value of v · x at x
is greater than or equal to the value at any other x in the
feasible set. In other words, x
maximizes the function v · x subject to the constraints of the original
optimization problem. We can restate Theorem 4.10 in terms of this new vocabulary.
Alternate Formulation of Theorem 4.10
Suppose we have a continuous objective function f and some constraints. If f(x
) = c and for some
v =
0 we have
1 x
minimizes v ·x subject to f(x) c
2 x
maximizes v ·x subject to the constraints
Then x
maximizes f(x) given the constraints.
We can see that this is a condition for a maximizer without knowing much about hyperplanes. If
the feasible points all have values of v ·x less than or equal to k and the upper level sets all have values
greater than or equal to k, then the feasible set and the upper level can only meet where v · x = k.
4.3.4
The Tangent Hyperplane
An observant reader will have noticed that our separating lines have always been tangent to the level
curve f(x) = c. This is not a coincidence. It occurs in higher dimensions as well, where the tangent
lines become tangent hyperplanes.
Definition 4.11
Suppose a point a lies on level set f (x) = c, and f(a) =
0. The tangent hyperplane to f(x) = c
at a is the hyperplane containing of all the tangent lines to f (x) = c at a. Its normal vector is f(a).
Its equation is
f(a) · (x a) = 0
184
Back to Contents