Active set method. This proceeds by partitioning inequality
constraints into two sets: active
(or sufficiently close to be deemed active for this iteration)
and
inactive. The inactive constraints
are ignored for the iteration. The active set for this iteration is
sometimes called the working set. Then, the new point is
selected by moving on the surface defined by the working set (called
the working surface).
_____
| c_j | <--- cost or revenue
|-----|
| - | <--- input to activity j
| |
|-----|
| + | <--- output from activity j
|_____|
In general, the
reduced cost then represents the net worth of the activity for
the prices, p:
d_j = c_j – pA_j = input cost – output revenue.
This leads to an economic interpretation not only of LP,
but also of the simplex method:
agents (activity owners) respond instantaneously to changes in prices,
and the activity with the greatest net revenue wins a bid to become
active (basic), thus changing the prices for the next time (iteration).
In this context, activities can be regarded as transformations,
from inputs to outputs. Three prevalent transformations are:
form, place and time. Here are examples:
blend transport inventory
_____ _____ _____
| c | | c | | c |
|-----| |-----| |-----|
|-.4 | apples | -1 | Chicago | -1 | t
|-.6 | cranberries |-----| |-----|
|-----| | .6 | Denver | 1 | t+1
| 1 | cranapple | .4 | Seattle | |
|_____| |_____| |_____|
Transformation Transformation Transformation
of form of place of time
Admissibility need not be for directions of change in the context of
sensitivity analysis. The term is used elsewhere and defined for the
context in which it is used. For example, a
primal ascent algorithm could define a direction, say d, to be
admissible if x+td is feasible and f(x+td) > f(x) for all t
in [0, t*) for some t* > 0.
Advanced basis. Using a basis to begin the
simplex method, other than
simply all logical variables. The advanced basis could be
optimal for some parameter values, but those values have changed.
It is usually better to start with an advanced basis because it
will generally require fewer iterations to reach the new optimal
basis.
Estimate dual:y = [AX²A']–1 A[X²]c' and
d = c - y'A.
Move: x' = x - aX²d'/Max{d_j x_j},
where a is a parameter in (0, 1).
Multiplication of A and c by X is a scaling operation, using current
levels as scale values (i.e., AX multiplies column j of A by x_j, and
Xc'
multiplies c_j by x_j). Note that the
reduced cost (d) is in the null space of A (i.e., Ad = 0), so d is
a feasible direction.
This affine scaling direction is used in its own right for
interior methods. It
minimizes the duality gap subject to
Ax=b and x in an ellipsoid (replacing x >= 0).
A stochastic algorithm is one whose algorithm map is a random
variable. Unlike the meaning in computer science, most people in
mathematical programming mean an algorithm whereby an iterate is selected
by some random mechanism. One example is
simulated annealing. When x^k
is a random variable, there is a meaning to
convergence that differs from ordinary (deterministic) sequences.
An online algorithm is one that obtains a solution for an
online problem. Typically, this
is a heuristic that obtains a
"good" solution because there is not enough time to guarantee
optimality.
Note that the analytic center depends on how the set is defined -- i.e.,
the nature of g, rather than just the set, itself. For example,
consider the analytic center of the box, [0,1]^n. One form is to have
2n functions as: {x: x >= 0 and 1-x >= 0}. In this case, the
analytic center is x*_j=y* for all j, where y* is the solution to:
Max ln(y) + ln(1 - y): 0 < y < 1.
Since y* = 1/2, the analytical center is what we usually think of
as the center of the box. However, the upper bounds could also be
defined by 1-(x_j)^p >= 0 for all j, where p > 1 (so 1-(x_j)^p
is concave). This changes
the functional definition, but not the set -- it's still the unit box.
The analytic center becomes skewed towards the corner because now the
defining mathematical program is:
Max ln(y) + ln(1 - y^p): 0 < y < 1.
The solution is y* = [1/(1+p)]^(1/p), so the analytic center
approaches (1,1,...,1) as p-->inf.
ANALYZE.
A computer-assisted analysis system to analyze mathematical
programs, including an artificially intelligent level of support.
Assembly line balancing problem. This is a
combinatorial optimization
problem. An assembly line consists of m work stations, connected
by a conveyor belt. Each station performs a set of tasks that takes
a cycle time, c. Each task must be assigned to exactly one
station such that
precedence constraints are satisfied. One model is to minimize the
total cycle time, given the number of stations. Another is to minimize
the number of stations, given the maximum allowable cycle time. There
are variants of this simple form.
Multi-dimensional assignment. More than 2 indexes, the
variables are of the form, X(i, j, k, ...). The constraints sum all but
one index -- for example, the 3-index assignment problem is given by:
Min Sum i,j,k{C(i, j, k) X(i, j, k)}: X >= 0;
Sum j,k{X(i, j, k)} = 1 for all i;
Sum i,k{X(i, j, k)} = 1 for all j;
Sum i,j{X(i, j, k)} = 1 for all k.
Asymptotic Linear Programming. A
linear program in which the coefficients are
functions of a single parameter, usually denoting time.
(Some authors require the functions to be rational – i.e., of the form p(t)/q(t),
where p and q are polynomials.)
The problem is to find a steady state solution – i.e., one that is
optimal (or nearly optimal) for sufficiently
large values of the time parameter.
Augmented Lagrangian. The
Lagrangian augmented by a term that retains the stationary
properties of a solution to the original mathematical program but alters
the hessian in the subspace defined by the
active set of constraints.
The added term is sometimes called a penalty term, as it
decreases the value of the augmented Lagrangian for x off the surface
defined by the active constraints.
For example, the penalty term could be proportional to the squared
norm of the active constraints:
L_a(x, y) = L(x, y) + p G(x)'G(x),
where p is a parameter (negative for maximization), G(x) is the vector
of active constraints (at x), and L is the usual Lagrangian.
In this case, suppose x* is a
Kuhn-Tucker point with multiplier y*. Then, L_a(x*, y*) = L(x*, y*)
(since G(x*)=0). Further, the gradient of the penalty term with
respect to x is 0 at x*, and the hessian of the penalty term is simply
p A(x*)'A(x*), where A(x*) is the
matrix whose rows are the gradients of the active constraints.
Since A(x*)'A(x*) is
positive semi-definite,
the penalty term has the effect of increasing the
eigenvalues (decreasing them if maximizing).