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**,

and

where .

By defining

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 1Recall 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 assumptionA1andA2, we have for all ,

and

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 .

立君你好棒呀😊

LikeLiked by 1 person