All Pages

From Glossary

Jump to: navigation, search

P-matrix

A square matrix with all of its principal minors positive. This includes all symmetric, positive definite matrices. Here is an example of a P-matrix that is not positive definite:


LaTeX: 
A = \begin{bmatrix}
1 & -3 \\
0 & 1
\end{bmatrix}


The principal minors are positive, but LaTeX: \textstyle (1, 1)A(1, 1)^t < 0. The significance of this class is in the theorem:

The linear complementarity problem, defined by LaTeX: (M, q), has a unique solution for each q in Rn if, and only if, LaTeX: M is a P-matrix.


Packing problem

The set packing problem is the question, "Does a collection of sets contain at least LaTeX: K mutually disjoint subsets?" (LaTeX: K is a positive integer not greater than the number of sets given.) This is solvable in polynomial time if no set has more than 2 members. Otherwise, it has the NP-hard equivalent integer program: LaTeX: \textstyle \max \left \{ \sum_j x_j: Ax \le 1, x \in \left \{0, 1 \right \}^n\right\}, where LaTeX: x_j = 1 if element LaTeX: j is selected; else, LaTeX: x_j = 0. The matrix LaTeX: A has 0's and 1's, where the i-th row corresponds the i-th set to be packed: LaTeX: A_{(i, j)}=1 means element j is in set i; else, LaTeX: A_{(i, j)}=0. The constraint LaTeX: Ax \le 1 means that at most one element of each set can be selected. If the IP maximum is less than LaTeX: K-1, or if it equals LaTeX: K-1 = number of elements, the answer to the set packing problem is "No". Otherwise, let LaTeX: \textstyle x_1, \dots, x_{(K-1)} be among those elements selected (re-index, if necessary). Let LaTeX: S_i be all sets containing LaTeX: x_i. Due to the packing constraints, no selected element can be in two sets, so these are disjoint. The remaining set, LaTeX: S_K, is composed of all other elements LaTeX: \textstyle (x_K, \dots, x_n), and must be disjoint from the other sets, so the answer to the set packing question is "Yes" (and we can construct the disjoint subsets).

A special case is the node packing problem on a graph: find a set of nodes of maximum cardinality such that no node is incident with the same edge (or arc). In that case, every row of LaTeX: A has exactly two 1's, and this is sometimes called [[Degree-2_inequality|]]egree-2 inequalities. Another special case is the bin packing problem.

The IP formulation has the natural extension: LaTeX: \textstyle \max \left \{ cx: Ax \le b, x \in \left \{0,1 \right \}^n \right \}, where LaTeX: \textstyle c \ge 0 and LaTeX: \textstyle b \ge 1. This allows up to LaTeX: b_i elements to be selected from the i-th set, and elements can be weighted by value LaTeX: (c).


Parallel algorithm

This is an algorithm that executes more than one instruction at a time by having a computing environment with more than one processor. The types of parallel computing environments are:

MIMD: Multiple Instruction/Multiple Data (includes massively parallel);
MISD: Multiple Instruction/Sequential Data (unusual);
SIMD: Sequential Instruction/Multiple Data (e.g., array processor).


Parallel tangents

(PARTAN). An algorithm developed from the zigzag phenomenon observed using Cauchy's steepest descent. It takes two gradient steps, then performs a line search on the line through the first and last points LaTeX: \textstyle (x^{k+2} - x^k). (For a quadratic objective, PARTAN is equivalent to the conjugate gradient method.)


Parameter

A constant in a mathematical program, not subject to choice in the decision problem, but one that could vary outside the control of the decisions. Examples are supplies, demands, loss factors, exponents and coefficients in polynomial functions (of the decision variables). Not all coefficients are parameters, as many are zero by the logic of the model. For example, the only data for a standard transportation problem are the costs, supplies and demands. These can depend upon parameters, but the LP matrix does not – it is the incidence matrix of the network. In general, parameters are data-dependent constants, rather than logically fixed for all instances of the model. Some parameters are simply units of measurement, such as the amount of energy (Btu) in a ton of coal, whereas some parameters are uncertain, like demand for a product.


Parametric analysis

The sensitivity analysis of parameters, which can be vectors in any designated region.


Parametric programming

Solving a family of mathematical programs over a parameter space. For example, consider the family of linear programs:

LaTeX: 
\min \left \{ cx: Ax = b + td, x \ge 0 \right \},

where t is a (scalar) parameter and d is a specified direction vector. Starting with LaTeX: t=0, the LP is solved, then an optimal basis is found (if possible) that remains optimal as LaTeX: t is increased. The max value of LaTeX: t is determined; if this is finite, the basis changes to a new optimal basis (for the max LaTeX: t value) such that LaTeX: t can be further increased, if possible. This is continued until either LaTeX: t cannot be increased any further or a basis is found that remains optimal on the interval, LaTeX: \textstyle [t_k, \infty), where LaTeX: \textstyle 0 < t_1 < t_2 < \dots < t_k are the break points of the optimal objective value as a function of the parameter.


Pareto optimum

See multiple objectives.


Partial conjugate gradient method

The conjugate gradient method is performed for some number of iterations, say LaTeX: k (< n), then it is restarted. (If LaTeX: k=0, this is the special case of Cauchy's steepest descent.)


Partial quasi-Newton method

A quasi-Newton method is performed for some number of iterations, say LaTeX: k (< n), then it is restarted.


Partial solution

Some of the variables are specified. This arises in a branch and bound algorithm, where some variables have been fixed by the branching process. It also arises in bidding algorithms.


Partially ordered set

(or poset). A set plus a binary relation on that set that is reflexive, antisymmetric and transitive. This arises in the presence of precedence constraints, and other relations that arise in combinatorial programs.


Particle Swarm Optimization

(PSO). This is an evolutionary algorithm based on swarm behavior of animals, like bird flocking. A move from a state is influenced by directions of states in its neighborhood. A consensus function is used to average neighbors' best fitness values, and this is combined with the original state's fitness to obtain a new position for the state. It applies to continuous variables, using a velocity term to derive state increments. The fundamental equation that governs state evolution is

LaTeX: 
v_p = wv_p + A r (x^*_p - x_p) + B r' (g^* - x_p)

where p is a particle, or state, and

LaTeX: v_p = velocity vector of particle LaTeX: p
LaTeX: x_p = position vector of particle LaTeX: p
LaTeX: x^*_p = previous position of particle LaTeX: p giving best fitness value
LaTeX: g^*_p = position of globally best fitness value
LaTeX: w = parameter, called "inertia weight"
LaTeX: r, r' are pseudo-random numbers in LaTeX: [0,1]
LaTeX: A, B = positive parameters, generally in LaTeX: [1,2]


Partitioning problem

This is the combination of packing and covering. Its IP form is LaTeX: \textstyle \mbox{Opt}\left \{cx: Ax=b, x \in \left \{0,1 \right \}^n \right \}, where Opt could be Min or Max, and LaTeX: A is a 0-1 matrix. The equation LaTeX: \textstyle A(i,.) x = b_i means that exactly LaTeX: b_i elements must be selected from set LaTeX: i. In particular, a multiple choice constraint is LaTeX: \textstyle \sum_j x_j = 1.


Path

As a (differentiable) curve, see path following. As a finite sequence, see graph or network.


Path consistency

A consistency property that is similar to arc consistency but that considers pairs of variables instead of just one. A pair of variables LaTeX: (x,y) is path-consistent with another variable LaTeX: z if for every consistent value pair for the binary constraint on LaTeX: x and LaTeX: y there exists a value for LaTeX: z such that all binary constraints between LaTeX: ({x},z) and LaTeX: (y,z) are satisfied.


Path following

In this context a path is a piecewise differentiable curve in space. The idea is to follow such a path (if one exists) from some initial point to a solution. One example of a path following algorithm is the barrier penalty function, with the path created by the parameter LaTeX: u in the solution, LaTeX: x^*(u) in LaTeX: \textstyle \argmax \left \{f(x) + uP(x): x \in X^0\right\}, where LaTeX: X^0 is the strict interior of the feasible region. (This is called the central path, or the path of the analytic center.)


Pattern search

This is a heuristic (in the sense of not guaranteeing convergence) for unconstrained optimization. It consists of two basic steps, where LaTeX: x is a current point and LaTeX: w is a vector of widths (both having been initialized).

  1. Exploration move. Set LaTeX: y=x and do for LaTeX: \textstyle j=1,\dots,n:
    If LaTeX: \textstyle f(y + w_j e_j) > f(y), replace LaTeX: y with LaTeX: y + w_j e_j.
    If LaTeX: f(y - w_j e_j) > f(y), replace LaTeX: y with LaTeX: y - w_j e_j.
    If LaTeX: x=y at the end of this, go perform a pattern move. Otherwise, set LaTeX: v = y-x (the change) and LaTeX: x = y (move to better point).
  2. Pattern move. If LaTeX: f(x + v) > f(x), replace LaTeX: x with LaTeX: x+v. Otherwise, reduce widths and return to exploration move.

The idea is to perform exploration moves as long as they are successful. Then, saving the last direction LaTeX: (v) when it was successful, this is used to advance LaTeX: x if it is an improvement, giving a new base point LaTeX: (x) for the next series of exploration moves. Termination occurs when the widths become too small.


Penalty function

The traditional concept is to augment the objective with a function and one positive constant, so that the original mathematical program is replaced by solving a parametric family of the form LaTeX: \textstyle \max \left \{f(x) - uP(x): x \in X^0\right\}. The function, LaTeX: P, is called a penalty function if it satisfies LaTeX: P(x) > 0 for LaTeX: x not feasible and LaTeX: P(x)=0 if LaTeX: x is feasible. The set LaTeX: X^0 depends on the type of penalty function, and there are two classical types, each requiring LaTeX: P to be continuous: interior (or barrier) and exterior. A penalty function is exact if there exists a finite parameter value such that its maximum is a solution to the original mathematical program.

More generally, a penalty function could involve many parameters, such as the Lagrangian, or it could be stated in parameter free form. A general model is the generalized penalty-function/surrogate dual, see the supplement on duals. The notion of an exact penalty function leads to a strong dual.


Perturbation

An imprecise term that means changing some parameter value (or function) and seeing what effect this has on the solution. This embodies continuity and differentiability properties of the optimal responses: objective value, policy set, and perhaps dual values too. This is what is sometimes called marginal analysis of solutions, and changes are limited to some neighborhood of the initial values. Some use perturbation function to mean the optimal objective value, even for large changes in the parameters, as in parametric programming.


Phase I and Phase II

Phase I of a mathematical program is finding a feasible solution, and Phase II is entered with a feasible solution to find an optimal solution. The standard Phase I is:


LaTeX: 
\max \sum_i \{u_i\} + \sum_i \{v_i + w_i\}: u, v, w \ge 0,

LaTeX: 
g(x) - u \le 0, h(x) - v + w = 0.

Then, for any LaTeX: x, one could set LaTeX: \textstyle u = g(x)^+, v = h(x)^+ and w = -h(x)^- to have a feasible solution to the Phase I mathematical program. The optimal objective value is 0 if, and only if, LaTeX: u=0 and LaTeX: v=w=0, in which case LaTeX: x is feasible in the original mathematical program (to commence Phase II). The Phase I problem is sometimes called an elastic program (thinking of the artificial variables LaTeX: (u,v,w) as providing "elastic" behavior in the levels of constraint violation).

In linear programming, the standard Phase I & II are:

I. Min ev: LaTeX: \textstyle x, v \ge 0, Ax + v = b, and
II. Max cx: LaTeX: \textstyle x \ge 0, Ax = b, \mbox{ where } b \ge 0 \mbox{ (multiply by } -1 \mbox{ for } i: b_i < 0.


Pivot

This is the algebra associated with an iteration of Gauss-Jordan elimination, using the forward transformation. The tableaux for a pivot on element LaTeX: a(p,q) LaTeX: (\ne 0), which means nonbasic variable LaTeX: x_q enters the basis in exchange for basic variable LaTeX: x_p, are as follows:

Before pivot:

LaTeX: 
\begin{array}{ll|ll}
Basic & & \multicolumn{2}{c}{Nonbasic} \\
Var. & Level & x_j & x_q \\
\hline \hline
x_i & b_i & a(i,j) & a(i,q) \\
x_p & b_p & a(p,j) & a(p,q)^* \\
\hline \hline
obj & -z & d_j & d_q  \\
\hline \hline
\end{array}

After pivot:

LaTeX: 
\begin{array}{ll|lr}
Basic & & \multicolumn{2}{c}{Nonbasic} \\
Var. & Level & x_j & x_q \\
\hline \hline
x_i & b_i - b_p a(i,q)/a(p,q) & a(i,j) - a(i,q)a(p,j)/a(p,q) & -a(i,q)/a(p,q) \\
x_q & b_p/a(p,q) & a(p,j)/a(p,q) & 1/a(p,q) \\
\hline \hline
obj & -a - b_p d_q/a(p,q) & d_j - a(p,j)d_q/a(p,q) & -d_q/a(p,q) \\
\hline \hline
\end{array}


A pivot is primal degenerate if the associated basic solution LaTeX: (x) does not change (i.e., the nonbasic variable enters the basis, but its level remains at the same bound value, in which case no basic variable changes level). Similarly, the pivot is dual degenerate if the associated dual solution (i.e., pricing vector and reduced costs) does not change. For dealing with degenerate pivots, see Bland's rule and the TNP rule.


Pivot selection

In the simplex method, this is a tactic to select a basis exchange. The incoming column is based on its effect on the objective function, and the outgoing column is based on its effect on feasibility.


Point-to-set map

Image of map is a set. If LaTeX: \textstyle F:X< \to 2^Y, this means LaTeX: F(x) is a subset of LaTeX: Y for each LaTeX: x \in X. An example is the feasibility map.


Pointed cone

A convex cone, LaTeX: C, such that LaTeX: \textstyle C \cap (-C) = \{0\}. An example is LaTeX: \textstyle C=R^{n+} (so LaTeX: \textstyle -C=\mathbb{R}^{n-}).


Polar cone

Polar cone, of a set LaTeX: \textstyle S \in \mathbb{R}^n. \left \{(y, y^0)\in \mathbb{R}^{n+1}: yx \le y^0 \mbox{ for all } x \in S \right \}.


Policy iteration

This is an algorithm for infinite horizon dynamic programs (generally stochastic) that proceeds by improving policies to satisfy the fundamental equation:

LaTeX: 
F(s) = r^*(s) + \sum_{s'} P(s,s') F(s'),

where LaTeX: F(s) is the maximum expected value when starting in state LaTeX: s, r^*(s) is the immediate expected return when in state LaTeX: s and following an optimal policy (a decision rule), and LaTeX: P(s,s') is probability of a transition from state LaTeX: s to state LaTeX: s' in one time period.

The algorithm has some policy, LaTeX: x^*(s), at the beginning of an iteration. This determines an approximation of LaTeX: F, which is exact if the equation holds. If the equation is violated, the violation identifies how the policy can be improved. This changes the policy for the next iteration. Convergence depends upon the underlying Markov process (e.g., whether it is ergodic). Another approach is value iteration.


Polyhedral annexation

This is a cutting plane approach to find an optimal solution known to lie at an extreme point of a polyhedron, LaTeX: P. The general algorithm is to start at some extreme point and solve the polyhedral annexation problem. This will result in ascertaining that the extreme point is (globally) optimal, or it will generate a recession direction from which a convexity cut is used to exclude the extreme point. The approach generates a sequence of shrinking polyhedra by eliminating the cut region. Its name comes from the idea of annexing a new polyhedron to exclude from the original, homing in on the extreme point solution.

Notes:

When applied to reverse convex programming, the convex set LaTeX: (S) in the polyhedral annexation problem is the objective level set, LaTeX: \{x: f(x) \le f(x^*)-t\}, where LaTeX: {t} > 0 is an optimality tolerance, and LaTeX: x^* is the best (extreme point) solution so far. The initial polyhedron is the feasible region, so this is an inner approximation strategy.

When applied to mixed integer programming, the original polyhedron is the LP relaxation, and the convex set LaTeX: (S) for the polyhedral annexation problem can vary according to the particular problem (exploiting structure, especially to find facets of the feasible region).


Polyhedral annexation problem

Given a convex cone LaTeX: C, a polytope LaTeX: P contained in LaTeX: C, and a compact, convex set LaTeX: S with 0 in intLaTeX: (S), find a point LaTeX: y in LaTeX: P\backslash S, or ascertain that LaTeX: P is contained in LaTeX: S.


Polyhedron

(pl. polyhedra). A set that equals the intersection of a finite number of halfspaces. This is generally written as LaTeX: \textstyle \left \{x: Ax \le b \right \}, where the representation LaTeX: (A,b) is not unique. It is often useful to separate the implied equalities: LaTeX: \textstyle \left \{x: Ax \le b, Ex = c \right \}, so that the relative interior is LaTeX: \textstyle \left \{x: Ax < b, Ex = c \right \}. The system, LaTeX: \textstyle \left \{Ax \le b, Ex = c \right \}, is a prime representation if it is irredundant, and it is minimal if it is irredundant and contains no implied equality. A polyhedron is degenerate if it contains an extreme point that is the intersection of more than LaTeX: n halfspaces (where LaTeX: n is the dimension of the polyhedron). An example is the pyramid.


Polymatroid

Let LaTeX: N be a finite set and let LaTeX: f be a submodular function on the subsets of LaTeX: N with LaTeX: f(\emptyset)=0. The polymatroid associated with LaTeX: (N,f) is the polytope:

LaTeX: 
\left \{x \in \mathbb{R}^{n+}: \sum_{j \in S} x_j \le f(S) \mbox{ for all } S \in N \right \}.


Polytope

A bounded polyhedron.


Pooling of inventory

When there are two or more demand points for a product, it may possible to save money if the separate inventories for these demand points can be combined or "pooled." There is a "square root economy of scale" from pooling for two of the simplest inventory models: a) the Economic Order Quantity (EOQ) model, and b) the Newsboy (NV) model.

For the EOQ case, where we want to minimize the fixed charge of ordering plus the holding cost of inventory carried, if we have two separate inventories for two demand points, each with constant demand rate LaTeX: D, fixed charge of ordering LaTeX: K, and holding cost/unit of inventory LaTeX: h, then the minimum total cost is LaTeX: \textstyle \sqrt{2\, D\, K\, h} at each demand point for a total cost of LaTeX: \textstyle 2\, \sqrt{2\, D\, K\, h}. If we combine the two demand streams and carry a single inventory for them, then the minimum total cost is LaTeX: \textstyle \sqrt{2\, (2\, D)\, K\, h} = 2\, \sqrt{D\, K\, h}, which decreases the total cost by a factor of LaTeX: \textstyle 1/\sqrt{2}.

For the NV case, if we have two demands, each independently Normal distributed with mean LaTeX: D and standard deviation LaTeX: \sigma, a specified service level LaTeX: \textstyle \alpha = \prob \left \{\mbox{Demand} < \mbox{inventory}\right\} at an inventory point, and LaTeX: z_\alpha being the number of standard deviations corresponding to a left tail probability of LaTeX: \alpha, then we must carry inventory LaTeX: \textstyle D + z_\alpha \sigma at each inventory point for a total inventory of LaTeX: \textstyle 2D + 2z_\alpha \sigma. If we can combine the two demands so we carry just one inventory, then the mean and standard deviation for the combined demands are LaTeX: 2D and LaTeX: \sqrt{2}\sigma. Thus, the total inventory we must carry is LaTeX: \textstyle 2D + \sqrt{2}z_\alpha\sigma, and there is a square root economy of pooling in the amount of safety stock we must carry. If we say that the system service level should be LaTeX: \alpha, then the benefits of pooling are even greater.

There is an interesting anomaly wherein pooling can increase inventory. Specifically, for the NV problem, if instead of there being a constraint on service level, the objective is simply to minimize the expected cost of unsatisfied demand and the cost of surplus inventory, and the demand distributions at each of two demand points (with associated inventory) are right skewed, e.g., the mean is greater than the median, then pooling the two inventories may in fact result in a higher total optimal inventory. For example, if the cost/unit short is 5, the cost/unit of inventory left over is 4, the demands at each of two demand points are independent Poisson distributed with mean 3.3, then the optimal amount to stock at each location is 3. If, however, the demands are pooled and a single inventory is carried so the demand is Poisson with mean 6.6, then the optimal amount to stock is 7. So pooling increased the optimal inventory. See Myths and Counter Examples for an additional example.


Pooling problem

A type of blending problem, as follows.

    Given:
  1. A set of sources, indexed by LaTeX: \textstyle 1,\dots,N_s. Each source supplies raw feeds in limited amounts, such as crude oil.
  2. A set of attributes, indexed by LaTeX: \textstyle 1,\dots,N_a. Each supply contains one or more attributes. An example of an attribute is the percent of sulfur in a crude oil supply.
  3. A set of products, indexed by LaTeX: \textstyle 1,\dots,N_d, for which there is demand; each product has a quality defined by its attributes. For example, if percent sulfur is an attribute, each refined petroleum product has a range of percent sulfur: 1.5% sulfur is a higher quality product than 2.5% percent sulfur.
  4. A set of pools, indexed by LaTeX: \textstyle {1},\dots,N_p. Each pool is formed by inflows from sources, whose attributes are linearly mixed to determine the attributes of the pool, and hence its quality. Pools combine to form products (see Flow of Materials below). For example, suppose a pool receives flow values LaTeX: x and LaTeX: y from two sources whose attribute values are LaTeX: A and LaTeX: B, respectively. Then, the pool's attribute value is the average: LaTeX: \textstyle (Ax+By)/(x+y).
                            Flow of Materials
                            ~~~~~~~~~~~~~~~~~
                Sources          Pools         Products
                         S(s,p)         P(p,d)
      SUPPLY --->(s)------------->(p)------------>(d)--->DEMAND
    

The objective is to minimize cost, which is the sum of source flow costs, subject to four types of constraints:

  1. Limited supplies: LaTeX: 
\frac{\sum_{1} S(s,1)}{\mbox{Total flow out of source } s \mbox{ (into pools)}} \le \mbox{SUPPLY}(s)

  2. Balances at pools: LaTeX: 
\frac{\sum_s S(s,p)}{\mbox{Total flow into pool (from source)}} - \frac{\sum_d P(p,d)}{\mbox{Total flow out of pool (to products)}} = 0

  3. Quality constraints:
    LaTeX: 
L(p,a) \le Q(p,a) = \frac{\sum_s w(s,a)S(s,p)}{\sum_s S(s,p)} \le U(p,a).
    The numerator is a weighted sum, where the weights (w) are the (given) quality values of attribute a at the sources (s). The denominator is the total flow into the pool (p).

  4. Demand requirements: LaTeX: 
\frac{\sum_p P(p,d)}{\mbox{Total flow into product (from pools)}} \ge \mbox{DEMAND}(p).


Portfolio selection problem

In its elementary form, this is the same as the capital budgeting problem, except that the objective is to minimize the risk, rather than maximize expected return. Let LaTeX: x_j be the percent of capital invested in the j-th opportunity (e.g., stock or bond), so LaTeX: x must satisfy LaTeX: \textstyle x \ge 0 and LaTeX: \textstyle \sum_j x_j = 1. Let LaTeX: v_j be the expected return per unit of investment in the j-th opportunity, so that LaTeX: vx is the sum total rate of return per unit of capital invested. It is required to have a lower limit on this rate: LaTeX: \textstyle vx \ge b (where LaTeX: b is between LaTeX: \min v_j and LaTeX: \max v_j). Subject to this rate of return constraint, the objective is the quadratic form, LaTeX: x^TQx, where LaTeX: Q is the variance-covariance matrix associated with the investments (i.e., if the actual return rate is LaTeX: V_j, then LaTeX: \textstyle Q(i,j) = E[(V_i - v_i)(V_j - v_j)].


Positive definite matrix

The symmetric matrix LaTeX: A is positive definite if LaTeX: \textstyle x^T Ax > 0 for all nonzero LaTeX: x. Equivalently, the matrix is positive definite if all its eigenvalues are positive.

Also see Positive semi-definite matrix


Positive semi-definite matrix

The symmetric matrix LaTeX: A is positive semi-definite if LaTeX: \textstyle x^T Ax \ge 0 for all LaTeX: x.

Also see positive definite matrix.


Postman problem

See Chinese postman problem.


Posynomial

A positive sum of monomials: LaTeX: \textstyle \sum_i c(i) \prod_{j} [x(j)^{a(i,j)}], where LaTeX: c > 0. Each monomial is the product,


LaTeX: 
\prod_j [x(j)^{a(i,j)}] = x(1)^{a(i,1)} \times x(2)^{a(i,2)} \times \dots \times x(n)^{a(i,n)},


and LaTeX: [a(i, j)] is called the exponent matrix. This is the fundamental function in geometric programming.

Example: LaTeX: \textstyle x(1)x(2) + 2x(3)/x(1)^{2} is a posynomial with 2 monomial terms and 3 variables. The exponent matrix is 2 by 3, showing the exponent in each monomial (row) of each variable (column):


LaTeX: 
\begin{bmatrix}
1 & 1 & 0 \\
-2 & 0 & 1
\end{bmatrix}


Pre-processing

Generally the same as presolve, but the purpose need not be to speed up optimization. Instead, it could be aimed at deepening one's knowledge about the mathematical program, such as what is forced by implication of the constraints versus what is determined by the economic trade-off.


Precedence constraint

When ordering objects, like jobs to to be performed, this is a constraint that restricts the order: i must precede j, denoted LaTeX: \textstyle i << j. If order really means time, and if the model has decision variables LaTeX: t_i and LaTeX: t_j to denote the start times of LaTeX: i and LaTeX: j, resp., this precedence constraint can be written as LaTeX: \textstyle t_j \ge t_i + T_i, where LaTeX: T_i is the time job LaTeX: i takes. On the other hand, a precedence constraint need not correspond to real time. For example, LaTeX: i << j could mean if project LaTeX: j is not selected, we cannot select project LaTeX: i. In that case, suppose the model has binary variables LaTeX: x_i and LaTeX: x_j, where LaTeX: x_i=1 means project LaTeX: i is selected, and LaTeX: x_i=0 means it is not selected. Then, the precedence constraint LaTeX: i << j is represented as: LaTeX: x_i \le x_j.


Preconditioning

A generalization of scaling that modifies the hessian so as to improve convergence properties. In the case of quadratic programming, this typically means multiplying the quadratic form matrix, LaTeX: Q, by a preconditioner, LaTeX: P, so that the condition number of LaTeX: PQ is as close to 1 as possible. There are many variations, including splitting a matrix, LaTeX: Q = P - S, to achieve a better conditioned matrix in the sense of its eigenvalue (and eigenspace) structure that governs convergence properties of algorithms like steepest ascent and conjugate gradient.


Predictor-corrector algorithm

This is a class of algorithms whose origin is in ordinary differential equations. One first "predicts" a solution with either a functional approximation or an algorithm, getting "close" to a solution. Then, this is the initial point for a "corrector" method, such as using Newton's method to get "closer" to the curve. Although it could be used to characterize many methods in mathematical programming, it arises most naturally in path following methods. The term began being widely used in connection with following the central path in an interior point method. One such algorithm is using the affine scaling direction as a predictor and centering as a corrector.


Presolve

A heuristic applied to reduce the problem in some way before starting an algorithm. In linear programming, for example, one might scan for an equation of the form LaTeX: x=0, then simply fix LaTeX: x at zero, thus reducing the number of variables and constraints. Further details are in the supplement, simplex method, by which each variable is evaluated for its potential to improve the value of the objective function. Let LaTeX: p = c_B[B^{-1}], where B is a basis, and LaTeX: c_B is a vector of costs associated with the basic variables. The vector LaTeX: p is sometimes called a dual solution, though it is not feasible in the dual before termination. LaTeX: p is also called a simplex multiplier or pricing vector. The price of the j-th variable is LaTeX: c_j - pA_j. The first term is its direct cost LaTeX: (c_j) and the second term is an indirect cost, using the pricing vector to determine the cost of inputs and outputs in the activity's column LaTeX: (A_j). The net result is called the reduced cost, and its value determines whether this activity could improve the objective value.

Other pricing vectors are possible to obtain information about the activity's rates of substitution without actually computing LaTeX: \textstyle r = [B^{-1}]A_j. If LaTeX: \textstyle p = v[B^{-1}], then LaTeX: \textstyle pA_j = vr, and LaTeX: v = c_B is the special case to get the reduced cost. Another special case is to obtain information about whether the (nonbasic) activity would need to perform a degenerate pivot. For LP in standard from, let LaTeX: v_i=1 if LaTeX: x_i=0 and LaTeX: v_i=0 if LaTeX: \textstyle x_i > 0. Then, LaTeX: \textstyle vr = \sum_i \left \{r_i: x_i = 0\right\}. Thus, if LaTeX: pA_j > 0, activity LaTeX: j must have a positive tableau value with respect to some basic variable whose level is zero, so the pivot would have to be degenerate.


Pricing

This is a tactic in the simplex method, by which each variable is evaluated for its potential to improve the value of the objective function. Let LaTeX: \textstyle p = c_B[B^{-1}], where LaTeX: B is a basis, and LaTeX: c_B is a vector of costs associated with the basic variables. The vector LaTeX: p is sometimes called a dual solution, though it is not feasible in the dual before termination. LaTeX: p is also called a simplex multiplier or pricing vector. The price of the j-th variable is LaTeX: \textstyle c_j - pA_j. The first term is its direct cost LaTeX: (c_j) and the second term is an indirect cost, using the pricing vector to determine the cost of inputs and outputs in the activity's column LaTeX: (A_j). The net result is called the reduced cost, and its value determines whether this activity could improve the objective value.

Other pricing vectors are possible to obtain information about the activity's rates of substitution without actually computing LaTeX: \textstyle r = [B^{-1}]A_j. If LaTeX: \textstyle p = v[B^{-1}], then LaTeX: \textstyle pA_j = vr, and LaTeX: v = c_B is the special case to get the reduced cost. Another special case is to obtain information about whether the (nonbasic) activity would need to perform a degenerate pivot. For LP in standard from, let LaTeX: v_i=1 if LaTeX: x_i=0 and LaTeX: v_i=0 if LaTeX: x_i > 0. Then, LaTeX: \textstyle vr = \sum_i \left \{r_i: x_i = 0 \right \}. Thus, if LaTeX: pA_j > 0, activity LaTeX: j must have a positive tableau value with respect to some basic variable whose level is zero, so the pivot would have to be degenerate.


Primal degeneracy

See Degeneracy


Primal method

An algorithm for which each iterate is feasible in the (primal) mathematical program.


Primal program

The original mathematical program, cited in the context of having its dual.


Prime representation

A set represented by an irredundant system of inequalities. (See polyhedron.)


Principle of optimality

The idea that an optimal path, or trajectory, is composed of optimal sub-paths. Equivalently, once we reach a particular state in a sequential decision process, the remaining decisions must be optimal with respect to that state. This is the foundation of dynamic programming.


Problems

There are various problems that have evolved that are popularly cited by name.


Product form of basis

See factored form of basis.


Product mix problem

To determine what mix of products to make from shared resources. For example, if a company has apples and cranberries, one could make a certain amount of apple juice, cranberry juice, cranapple juice, and applecran juice, each differing in the percentages of apples and cranberries. More extensive examples abound to illustrate one of the early, fundamental applications of linear programming.


Production scheduling problem

To determine levels of production over time. Constraints include demand requirements (possibly with backordering), capacity limits (including warehouse space for inventory), and resource limits. One basic model is as follows.

Let

LaTeX: x_t = level of production in period t (before demand);
LaTeX: y_t = level of inventory at the end of period t;
LaTeX: U_t = production capacity in period t;
LaTeX: W_t = warehouse capacity in period t;
LaTeX: h_t = holding cost (per unit of inventory);
LaTeX: p_t = production cost (per unit of production);
LaTeX: D_t = demand at the end of period t.

Then, the mathematical program is

LaTeX: 
\min \{ p^T x + h^T y : 0 \le (x, y) \le (U, W), \, y_{t+1} = y_t + x_t - D_t \mbox{ for } t=0,\dots,T \}.

LaTeX: y(0) is the given initial inventory, and LaTeX: T is the planning horizon.

The condition that LaTeX: y \ge 0 means there is no backordering. Other tacit assumptions, which could be relaxed to gain more scope of the model are as follows.

  • Letting quantities be multiple – e.g., LaTeX: x_{k,t} = level of production of product LaTeX: k at time LaTeX: t. In such cases, competition for warehouse space and other resources result in more equations.
  • There could be an ending inventory constraint, such as LaTeX: y_T=y_0.
  • There could be additional decision variables to allow capacity expansion.
  • Costs could be nonlinear functions.
  • This could be a stochastic program; for example, with demands not known with certainty.

Also see warehouse problem.


Projected gradient method

A feasible direction is obtained for the region LaTeX: \textstyle \left \{x: Ax=b \right \} by projecting the gradient of the objective function to the null space of LaTeX: \textstyle A: d = P \nabla f(x), where LaTeX: \textstyle P = \begin{bmatrix}I - A^T[AA^T]^{-1} & A \end{bmatrix} (note LaTeX: A[Py] = 0 for all LaTeX: y, so LaTeX: \textstyle \left \{Py \right \} is the null space of LaTeX: A). Thus, LaTeX: x + ad is feasible for all feasible LaTeX: x and all LaTeX: a > 0 (since LaTeX: Ad=0). Further, if LaTeX: \textstyle P \nabla f(x) \ne 0, LaTeX: f(x+ad) = f(x) + a \nabla f(x)' P \nabla f(x) > f(x) for LaTeX: \textstyle a > 0, so the objective value improves each iteration until its projected gradient is null. At that point where LaTeX: \textstyle P \nabla f(x)=0, x satisfies first-order conditions.


Propagation

See constraint propagation.


Proper optimum

A local optimum that is uniquely optimal in some feasible neighborhood.


Pseudo-boolean function

This maps LaTeX: \textstyle \left \{0,1 \right \}^n \to \mathbb{R}.


Pseudo-boolean program

LaTeX: \textstyle X = \left \{0,1 \right \}^n and all functions are pseudo-boolean.


Pseudo-inverse

(of a matrix). Same as generalized inverse.


Pseudo-monotone function

LaTeX: \textstyle f: \mathbb{R}^n \to \mathbb{R}^n is pseudo-monotone over LaTeX: X (subset of LaTeX: \textstyle \mathbb{R}^n) if


LaTeX: 
f(y)^T (x - y) \ge 0 \mbox{ implies } f(x)^T (x - y) \ge 0 \mbox{ for all } x, y \in X.


The gradient of a pseudoconvex function is a pseudo-monotone function.


Pseudoconcave function

Negative is pseudoconvex.


Pseudoconvex function

LaTeX: f is in LaTeX: C^1 and satisfies the property: LaTeX: \textstyle \nabla f(x)(y-x) \ge 0 implies LaTeX: \textstyle f(y) \ge f(x). While every differentiable convex function is pseudoconvex, LaTeX: \textstyle \arctan(x) is an example of a pseudoconvex function that is not convex.


Pseudocost

A numerical value put on a 0-1 variable that estimates the change in objective value for setting the variable to 0 or 1, called up-pseudocost and down-pseudocost, respectively. These are used to guide branch and bound in node selection.


Views
Personal tools