# Linear Programming

## Standard primal and dual problems

The standard linear programming problem is

Without loss of generality we can take . We let be an optimal point.

The dual to the standard problem is

or alternatively

The variables are called dual variables and the variables are slack variables.

Theorem If is feasible for (P) and is feasible for (D), then

Further, if is optimal for (P) and is optimal for (D), then

The second condition is called complementary slackness.

### Basic solutions

A basic solution is given by a set of column indices such that the square matrix formed by the columns of is nonsingular. Then

Hence

Suppose is optimal. Then and

and hence .

## Lower and upper bounds on variables

The constrained primal linear programming problem is

Given lower bounded variables and upper bounded variables , the problem becomes

and the dual problem is

Note that the objective function can be written

To define a basic solution, we need to split the variables into three sets, the basic variables , the lower bounded variables and upper bounded variables . A basic solution then satisfies

## Lower and upper bounds on variables and constraints

The most general form of the linear programming problem is

Define auxiliary variables , and . The primal and auxiliary variables can be either basic , lower, upper or fixed. A lower or upper variable satisfies or , and a fixed variable satisfies (alternatively, .

After the introduction of auxiliary variables, the system can be written in the form (CP) above, with equations

If there are variables, inequality constraints and equality constraints, then the total number of basic variables , since there are equations and .

Given a basic solution, we can split the equations and variables into The basic variables are therefore given by

have the equations

The basic variables are therefore given by

Write

Since the objective function is given by , we have

Set dual variables

Then

This shows how the objective changes with changes in and . The main difficulty performing an update is that the number of basic variables may change during an algorithm.

## Primal and dual feasibility problems

• The primal feasibility problem is

• The dual feasibility problem is

• The constrained feasibility problem is

## Certificates of infeasibility / Farka's Lemma

• A certificate of infeasibility of is a vector such that and . For then , a contradiction.
• A certificate of infeasibility of is a vector such that and . For then , a contradiction.
• A certificate of infeasibility of partition into lower and upper variables and , and a vector such that , and . For then

• Alternatively, a certificate of infeasibility of partition into lower, upper and basic variables , and , and a vector such that , , and . For then

## Basic feasibility testing

Given a partition of variables into upper, lower and basic, we can test for a solution of the constrained feasibility problem.

• Set , and .
• If , then the basis gives a feasible solution.
• Otherwise, define such that if , if and otherwise.
• Set and .
• If and , then there is no feasible solution.
• Note that , so we can extend the variable sets taking and The correctness of the validation of feasibility is immediate. To prove correctness of the infeasibility validation, suppose is a feasible point. Then , but

since and .

## Robust feasibility problems

Due to numerical errors, the solution to a feasibility problem may be inaccurate. It is therefore important to be able to validate solutions to feasibility problems. One approach is to use rational arithmetic, but this is frequently too expensive. The alternative is to use interval arithmetic. For this, we need our problems to be robustly solvable.

Note that robustly solving an inequality is straightforward; we merely change to . To robustly solve a system of linear equalities, we need to choose a basis and express the basic variables in terms of the non-basic variables.

• The primal feasibility problem is robustly solvable if there exists a basis and non-basic values such that . A certificate of robust infeasibility is a vector such that and .
• The dual feasibility problem is robustly solvable if there exists such that . A certificate of robust infeasibility is a basis and an such that and .
• The constrained feasibility problem is robustly solvable if there exists a basis and non-basic values such that and . A certificate of robust infeasibility is a subdivision into lower and upper variables, and a vector such that , and .

## Robust basic solutions

Given a basis , and if necessary lower and upper variables and , we can attempt to solve robust feasibility problems by finding a robust basis. We can also set the nonbasic variables to the exact values, as long as the basic variables robustly satisfy the constraints. In order to check that a basis gives a solution to the robust dual feasibility problem,

• Given a basis for the primal feasibility problem , we can take .
• If some of the variables are still undetermined, we can (optionally) compute , and try adding positive linear combinations of columns of this matrix.
• To prove infeasibility, we take values which are negative, and show that they cannot be increased. Suppose . Take , the corresponding unit basic vector, and try .
• Given a basis for the dual feasibility problem take .
• To prove infeasibility, find some such that and .

TODO: It is not clear whether a robustly solvable problem has a robust basic solution.

## Certificates of robust (in)feasibility

A robust certificate for the primal feasibility problem is a base such that is nonsingular, and an such that ; this is equivalent to . A robust certificate of infeasibility is a point such that and .

Theorem Suppose is robust. Then either has full row rank and there exists such that , or there exists such that and .

A robust certificate for the dual feasibility problem is a point such that . A robust certificate of infeasibility is a base such that is nonsingular, and a vector such that and . We prove by setting , so that .

Theorem Suppose is robust. Then either there exists such that , or has full row rank and there exists such that and .

Proof If , then this holds also for perturbations of . If and is nonsingular, then . Perturbing and keeping constant, we obtain a perturbation of , and hence a certificate for the perturbed problem.
Conversely, suppose the problem is robustly solvable. Then the problem is solvable for and sufficiently small. Hence there exists such that .
Suppose the problem is robustly unsolvable Let be a matrix with all positive entries. Since is robustly unsolvable, is unsolvable for some . Then there exists such that , and . Then if , then , and since and .

## Converting robust feasibility problems to feasibility problems

To solve the robust primal feasibility problem,

we choose a vector and consider the problem

Let , and . Then we obtain the standard primal optimisation problem If the optimal value is negative, then we have found such that , so taking , we have . If the optimal value is non-negative, then we can attempt to solve the dual robust optimisation problem . Since if this problem is feasible, it has unbounded solutions, we can instead choose look for a positive optimal value of

To solve the robust dual feasibility problem,

we choose and consider the problem

Let , and . Then we obtain the standard dual optimisation problem If the optimal value is positive, then we have found such that . If the optimal value is zero or negative, then we can attempt to solve the primal robust feasibility problem However, even if the dual feasibility problem is unsolvable (i.e. ), the primal may become solvable by a perturbation of . We therefore consider a robust version and introduce to make a problem Note that if this problem has negative value, then we have found such that , and , which implies that the original dual problem has no solution. Taking , we obtain

## The simplex algorithm

Suppose we wish to update a basis of the standard linear programming problem.

• The current point (with ), and satisfies .
• If lower and upper constraints are being used, the non-basic variables are and .
• The current dual variables are .
• The reduced costs are .
• If the reduced costs are all positive, the optimum has been found and the algorithm terminates. Otherwise, select such that .
• The direction to move the basic variables is where is the column of .
• Choose maximal so that ; if the update is being used for feasibility, constraints violated by may be violated by . Choose corresponding to a newly saturated constraint.
• If lower and upper constraints are being used, we must be careful not to violate constraints on the new basic variable. The change in the new basic variable is , and we must have , with if , and if .
• Replace by to obtain new basic , and update .
• We have and and we want if is the basis variable..
• Let where is the column of .
• For , subtract from for all .
• Then divide by for all .
• Succinctly, where and .
• The new value is given by . The other basic variables are given by .

In general, if , then

## The dual revised simplex algorithm

Suppose we wish to update a dual feasible basis of the standard linear programming problem; note that the reduced costs satisfy satisfy .

• If the current point is positive, the algorithm terminates. Otherwise, select such that .
• The direction to move the primal variables is where is the row of .
• Choose maximal so that ; if the update is being used for feasibility, constraints violated by may be violated by . Choose corresponding to a newly saturated constraint.
• Replace by to obtain new basis , and update .

## The simplex algorithm with constraints

Suppose we wish to update a basis of the standard linear programming problem.

• The current point (with ).
• The current dual variables are .

## Algorithms for feasibility

• We solve primal feasibility problems by trying to solve the dual feasibility problem , . If the dual problem has a solution, then the primal problem has no solution, and vice-versa.

An alternative approach is to add constraints. We start with a basic feasible solution to and want to introduce the constraint . Assume . Introduce slack variable and try to minimise such that , . If a solution with is found, then the new constraint can be introduced.

A third approach is to start with a basic solution and gradually imposing the constraints by maximising without breaking for .
Suppose we have a basic feasible solution of and we wish to add the constraint .
1. Try to maximise while satisfying the other constraints. This can be done by solving the linear programming problem . We start with a dual feasible problem and aim to find a primal feasible problem using the dual simplex algorithm.
2. If a value of is found with , the new constraint can be added.

An alternative approach is to consider the primal problem . If an unbounded feasible solution to the primal exists, then the dual is infeasible.
• Constrained feasibility problem with equalities .
Find a set of basic variables so that is nonsingular, where is the matrix formed from the columns of in . Initialise to for non-basic variables, and set . Then , but possibly not .
Let if and if . Now minimise , but relax the currently violated constraints.

Remark: Since we do not assume the existence of in our number types, we use for the constraint ; this is the only unbounded constraint we allow.

See Chvatal [Chapter 8, pp 129] for more details on constrained feasibility.

## Efficiency of the simplex algorithm

For a linear programming problem of standard form, with an matrix, the number of iterations of the simplex algorithm for practical problems grows approximately as .

## The homogeneous self-dual algorithm

The homogeneous self-dual algorithm is a method for simultaneously computing optimality and feasibility. Consider the primal and dual problems

The homogeneous self-dual problem is

A feasible point is always given by . When , the first three equations reduce to , and . If and denote the slack variables, the final constraint becomes

We have the following result:

• Problem (HSD) has an optimal solution, and the set of optimal points is bounded (compact).
• The optimal value is zero, and for any feasible point, we have .
• There is an optimal solution with such that and .

To relate (HSD) to (P) and (D), we have:

• The primal problem has a bounded feasible solution if, and only if, . In this case, is primal optimal, and is dual optimal.
• There is no solution if, and only if, . In this case, if , then the dual problem is infeasible, and if , then the primal problem is infeasible,

To related (HSD) to the central path, we have:

• For any , there is a strictly feasible point such that and . The initial point , and is the solution for .

A potential function is given by

See: David G. Luenberger and Yinyu Ye "Linear and nonlinear programming".

## Feasibility problems for geometric operations

In the Geometry module, we need to solve the following linear programming problems to test intersection.

We notice that by introducing slack variables, we can convert all problems into a standard linear programming problem with constraints.

• Standard primal feasibility problem
• Constrained primal feasibility problem
• Standard dual feasibility problem
• Constrained dual feasibility problem

We can convert the standard dual feasibility problem into a primal linear programming problem , but it is not so straightforward to convert a constrained dual feasibility problem into its dual. Instead we add slack variables and solve . We can use the reduced simplex algorithm to take advantage of sparseness.

## Feasibility using Interior Point Methods

### Constrained Dual Feasibility

We shall be most concerned with the following problem:

• Find such that and , or show that such a does not exist.

Without the bounds on , it is easy to show that no solution exists if there exists such that , , and .

To solve the problem, introduce extended variables , slack variables and a value . The original (dual) feasibility problem becomes

whereas the prime feasibility problem becomes

. The original problem is feasible if the optimum value is positive, and infeasible if it is negative.

Robust primal and dual basic feasible solutions are easily found. Take , and such that . Finally, scale so that the sum is equal to . Take , and , and

We can now apply the standard interior point update. Although the matrix has been augmented, we can still recover a problem such that we only need to invert a matrix with only one extra row. Hence the dimension of the matrix inversion problem is equal to the dimension of the underlying space plus one.

### General feasibility problem

Consider feasibility of the linear programming problem

Special cases of this occur in, for example testing whether the image of a constraint set intersects another constraint set.

Introduce slack variables to transform the problem to

The duality conditions are

and the value function is

The complementary slackness conditions are

Consider a step updating the variables in an attempt to solve the complementarity system. The Newton equations are

where and are the residuals and which are typically zero.

Assuming the residuals are zero, we have

and hence so . Combined with the equation , we obtain the system

The left-hand matrix is symmetric, so can be (fairly) easily factorised. Further, the matrix is independent of the problem, so the initial part of the factorisation can be pre-computed.

Indeed, it may be better to completely eliminate at the start of the problem by explicitly solving for some variables of x. If we have a square submatrix of which is invertible, then

and the inequalities for become

.