We consider global conditioning property of Linear Program (LP) here. Let’s first define the problem. The standard form of LP is
where and . The dual of the standard form is
Now suppose we add perturbation to Program (2) in the term, we have
Let be the optimal value of Program (3) and be an optimal solution to the same program. We would like to ask the following question:
Such questions are called the conditioning of Program (2). It asks under some perturbation, how does the solution and optimal value changes accordingly. In general, we hope that Program (1) and (2) to be stable in the sense that small perturbation in the data, i.e., , only induces small changes in the optimal value and solution. The reason is that in real application, there might be some error in the coding of or even . If Program (1) and (2) are not stable with respect to the perturbation, then possibly either more costs need to be paid to the encoding of the data or the LP is not worth solving. At first sight, it is actually not even clear that
- Whether will be always finite?
- Whether is actually unique? If is not unique, then the Lipschitz property of does not even make sense.
To address the first issue, we make our first assumption that
A1: Program (2) has a solution and the optimal value is finite.
Under A1, by strong duality of LP, we have that Program (1) also has a solution and the optimal value is the same as the optimal value of Program (2). This, in particular, implies that (1) is feasible. We now characterize the region where is finite. Let the feasible region of Program (1) be denoted as
the set of vertices of be and the set of extreme rays be . Using our assumption A1, we know
Now according to the Resolution Theorem of the primal polyhedron, we have
Using this representation, the fact that the primal of Program (3) is
and strong duality continue to hold for (3) and (5) as (5) is feasible by A1, the value of is
Thus it is immediate that the region where is finite is
In particular, if is bounded, then we have to be always finite.
To address the issue whether is unique, we make the following nondegenerate assumption on vertices.
A2: All the basic feasible solution of (1) are non-degenerate, i.e., all vertices of the feasible region of Program (1) have exactly positive entries.
Under this condition, and the definition of basic feasible solution, we know if is a basic feasible solution, then where has all column independent. Here is the submatrix of having columns with indices in . By complementarity of LP (3) and (5), we thus know that if is a baisc feasible solution and it is a solution to Program (5), then
is the unique solution to Program (3) where . What we have done is that under A1 and A2,
which is a polyhedron, we may write the above compactly as
Then it is easy to see that the Lipschitz condition of is
where is the dual norm of . We note here is arbitrary.
Similarly, by using the theorem in this post, we see that is also Lipschitz continuous with Lipschitz property
where and are arbitrary norms. We conclude the above discussion in the following theorem.
Theorem 1 Recall is the set of extreme points of the feasible region of (1), is the set of extreme points of the feasible region of (1) and . Under assumption A1 and A2, we have for all ,
where are arbitrary norms. Here is the submatrix of having columns with indices in .
How might one bound the Lipschitz constants
The former might be done by giving a bound of the diameter of the feasible region of Program (1) and the later might be done through some restricted isometry property of .
One thought on “LP Conditioning”
LikeLiked by 1 person