Online problem. A decision problem that is ongoing, so its
data values are frequently changing with uncertainty.
Here are some examples:
- Allocation of bandwidth during video conferencing on a
telecommunications network;
- Investment decisions in a portfolio, selling and buying as
the market changes;
- Scheduling jobs as they arrive;
- Load forcasting and dispatching for electric power.
In general, an online decision problem could be the allocation of
resources that is done in real time with changes in the amount of
resources, their costs and the demands for what they produce.
A problem that is not online is sometimes called an
offline problem.
Optimal. For a mathematical program in
standard form, x* in X (the domain)
is an optimal solution if it is a maximum
(or a minimum):
- x* is feasible;
- f(x*) >= f(x) for all feasible x (maximum value).
Some authors refer to an optimal solution when they mean a
local optimum; others mean a member
of the optimality region (which
are global optima). In either case,
the optimal value is the objective value, evaluated at an optimal solution.
A solution is nearly optimal if it is feasible, but the
optimality condition (2) is replaced by
f(x*) >= f(x) - t
for all feasible x,
where t > 0. (t=0 corresponds to being optimal).
Typically, t is specified as a small fraction, such as a cut-off
tolerance for an algorithm to terminate finitely.
Optimal partition. Consider a primal-dual pair of
linear programs:
Min{cx: x >= 0, Ax >= b} and
Max{yb: y >= 0, yA <= c}.
Define primal surplus variables,
s = Ax - b, and dual
slack variables, d = c - yA. For any non-negative vector, v,
define its support set as those indexes for which the coordinate
value is positive: I(v)={j: v_j > 0}. In an optimal solution,
complementary slackness
must hold, so that j in I(x) implies j is not in I(d), and i in I(s)
implies i is not in I(y). Thus, the intersections, I(x)/\I(d) and
I(s)/\I(y), are empty. If the solution is strictly complementary, these
support sets yield partitions because then I(x)\/I(d) = {1,...,n} and
I(s)\/I(y) = {1,...,m}. A strictly complementary solution is an
interior solution (and conversely),
so each interior solution yields a partition of these index sets.
A key fact is that every LP with an optimal solution must have an
optimal interior solution. Further, every optimal interior solution
yields the same partition, so it is called the
optimal partition.
Optimal response function. The optimal value of the objective
as a function of parameters, typically the
right-hand side:
f*(b, c) = Sup{f(x): x in X, g(x) <= b, h(x) = c}.
