失效链接处理 
Certificates of Primal or Dual Infeasibility PDF 下载
本站整理下载：
相关截图：
主要内容：
. Introduction
In general a linear program (LP) has an optimal solution if and only if the primal problem
and the corresponding dual problem is feasible and in this case the optimal value of the two
problems coincide. This implies if a primal and dual solution is computed and reported,
then optimality of the primal solution can easily be verified by checking whether the primal
and dual solution is feasible and the duality gap is zero. Hence, the optimal dual solution is
a certificate of the optimality of the primal solution. In practice this also implies that it is
easy for an user of an LP software to verify the correctness of the solution produced by the
software.
Similarly, in the case an LP is primal or dual infeasible, then a certificate should be
reported which allows easy verification of the infeasible status of the LP.
The reader may question why optimization software should return a certificate of the
infeasible status and not just a status indicator which indicates that the problem is infeasible. One reason is optimization software may produce incorrect results, so it advantageous to be able to check the software. Moreover, if for example the LP is a subproblem
arising within a column generation based solution method for largescale LPs, then a
certificate is required to generate more columns or to prove that the “real” problem is
infeasible.
Hence, a certificate of the infeasible status may be important for both theoretical and
practical reasons.
172 ANDERSEN
Recently interiorpoint methods have emerged as an efficient alternative to simplex based
solution methods for LPs. Unfortunately some of these methods such as the primaldual
algorithm discussed in [6] do not handle primal or dual infeasible LPs very well [6, p. 177].
However, interiorpoint methods based on the homogeneous model (or equivalently the selfdual embedding) detects a possible infeasible status both in theory and practice [1, 5]. These
interiorpoint methods generates an infeasibility certificate using Farkas’s lemma. This leads
to the question about the relation between an “interiorpoint” certificate of infeasibility and
the certificate of infeasibility generated by the simplex method. Moreover, in the case an
optimal interiorpoint solution is known, then it is possible to compute an optimal basic
solution in strongly polynomial time [3]. However, is it also possible given an “interiorpoint” certificate of infeasibility to compute a basis certificate of infeasibility?
The computation of a basis certificate of infeasibility starting from an arbitrary certificate
of infeasibility may not only be relevant for interiorpoint methods. For instance when an
LP is solved using the primal simplex method, then in the case the LP is primal infeasible an
optimal basis to a phase 1 problem is computed and reported. The optimal basic solution is
a certificate of the primal infeasibility, but unfortunately a phase 1 problem is not uniquely
defined [4, ch. 8]. Hence, it may be difficult to verify the conclusion of the certificate.
However, if such a certificate could easily be converted to a basis certificate of infeasibility
(to be defined precisely later), then a well defined certificate could always be reported.
The outline of the paper is as follows. First in Section 2 we present our notation. In
Section 3 we discuss primal infeasible LPs and give a definition of an optimal basis to an
infeasible LP. Moreover, by generalizing previous work in [2, 3] we show that such a basis
can be computed in strongly polynomial time given a Farkas type certificate of infeasibility.
In Section 4 we analyze dual infeasible problems. In Section 5 we discuss the usefulness
of computing a basis certificate of infeasibility and finally in Section 6 we present our
conclusions.
2. Notation and theory
The problem of study is an LP in standard form
(P) minimize cTx
subject to Ax = b, x ≥ 0,
where b ∈ Rm, A ∈ Rm×n, and c, x ∈ Rn. For convenience and without loss of generality
we assume that rank (A) = m. The dual problem corresponding to (P) is
(D) maximize bTy
subject to ATy + s = c, s ≥ 0,
where y ∈ Rm and s ∈ Rn. (P) is said to be feasible if a solution satisfying the constraints
of (P) exists. Similarly (D) is said to be feasible if (D) has at least one solution satisfying
the constraints of (D). The following lemma is a wellknown fact of linear programming.
LINEAR PROGRAMMING 173
Lemma 2.1.
a. (P) has an optimal solution if and only if (x∗, y∗,s∗) exists such that
Ax∗ = b, AT y∗ + s∗ = c, cT x∗ = bT y∗, x∗,s∗ ≥ 0.
b. (P) is infeasible if and only if an y∗ exists such that
AT y∗ ≤ 0, bT y∗ > 0. (1)
c. (D) is infeasible if and only if an x∗ exists such that
Ax∗ = 0, cT x∗ < 0, x∗ ≥ 0. (2)
Proof: See [5]. ✷
Hence, (P) has an optimal solution if and only if (P) and (D) are both feasible. Moreover, a
primal and dual optimal solution is a certificate of that the problem has an optimal solution.
In the case the problem is primal or dual infeasible, then any y∗ satisfying (1) and any x∗
satisfying (2) is a certificate of the primal and dual infeasible status respectively.
An LP may be both primal and dual infeasible and in that case both a certificate for the
primal and dual infeasibility exists.
Note that the statements b and c in Lemma 2.1 are nothing but Farkas’s lemma. Also note
that in the case an LP is solved using a column generation method and for example the first
subproblem is infeasible, then any column having a positive inner product with a certificate
y∗ of primal infeasibility is a potential candidate to be included in the next subproblem. If
no such column exists, then the complete problem can be concluded to be infeasible.
Furthermore, by using the socalled homogeneous model and an interiorpoint algorithm
combined with a finite termination method then either an optimal solution or an infeasibility
certificate can be computed in polynomial time, see [7, pp. 159–167, 5]. However, in the case
the problem is both primal and dual infeasible then this method is only guaranteed to compute
one of the primal and dual infeasibility certificates.
Given the assumption A is of full row rank, then a basic partition of the indices of the
variables denoted (B, N ) satisfying
B = m and rank (B) = m
always exists where we use the definition that
B := A:B and N := A:N ·
Also B is denoted the basis.
An optimal basic partition of the indices of the variables is defined by
xB = B−1b ≥ 0, xN = 0, (3)
and
y = B−T (cB − sB), sB = 0, s = c − AT y ≥ 0. (4)
174 ANDERSEN
Subsequently we say a basic partition of the indices of the variables is primal feasible if
it satisfies (3), where the requirement xN = 0 may be relaxed to xN ≥ 0. Similarly, a basic
partition of the indices of the variables is dual feasible if it satisfies (4) possible with sB = 0
relaxed to sB ≥ 0.
It has been proved in [3] that given any primal and dual optimal solution, then an optimal
basic partition of the indices of the variables can be computed in strongly polynomial time.
However, in the case (P) is primal or dual infeasible, then it is undefined what constitutes
an “optimal” basic partition of the indices of the variables. Furthermore, given a definition
of an optimal basic partition of the indices of the variables to an infeasible LP, then it is
unclear whether such a basis can be computed in strongly polynomial time starting from an
arbitrary certificate of the infeasible status.
In the subsequent two sections we will give a definition of an optimal basic partition
of the indices of the variables for a primal and dual infeasible LP. Moreover, we will
present a strongly polynomial procedure to compute such a basic partition starting from
any infeasibility certificate.
