Java知识分享网 - 轻松学习从此开始!    

Java知识分享网

Java1234官方群25:java1234官方群25
Java1234官方群25:838462530
           Java最新职位

GIT视频教程(结合github,码云)免费领取

SpringBoot打造全栈在线教育平台实战课程

毕设代做论文包查重联系人QQ:1982956321毕设大神

66套java实战课程无套路领取

Java1234 VIP课程

领取微信扫码登录Java实现视频教程

Java1234至尊VIP(特价活动)
当前位置: 主页 > Java文档 > Java基础相关 >

Certificates of Primal or Dual Infeasibility PDF 下载


分享到:
时间:2020-10-17 09:32来源:http://www.java1234.com 作者:转载  侵权举报
Certificates of Primal or Dual Infeasibility PDF 下载
失效链接处理
Certificates of Primal or Dual Infeasibility  PDF 下载


 
本站整理下载:
提取码:28ch 
 
 
相关截图:
 
主要内容:

. 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 infea￾sible. One reason is optimization software may produce incorrect results, so it advanta￾geous 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 large-scale 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 interior-point methods have emerged as an efficient alternative to simplex based
solution methods for LPs. Unfortunately some of these methods such as the primal-dual
algorithm discussed in [6] do not handle primal or dual infeasible LPs very well [6, p. 177].
However, interior-point methods based on the homogeneous model (or equivalently the self￾dual embedding) detects a possible infeasible status both in theory and practice [1, 5]. These
interior-point methods generates an infeasibility certificate using Farkas’s lemma. This leads
to the question about the relation between an “interior-point” certificate of infeasibility and
the certificate of infeasibility generated by the simplex method. Moreover, in the case an
optimal interior-point 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 “interior￾point” 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 interior-point 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 well-known 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 so-called homogeneous model and an interior-point 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.

 

------分隔线----------------------------
锋哥公众号


锋哥微信


关注公众号
【Java资料站】
回复 666
获取 
66套java
从菜鸡到大神
项目实战课程