Linear programming -- checking solution subspace containment

Linear programming -- checking solution subspace containment

Postby Guest » Tue Jul 17, 2012 10:52 am

We have a set of linear constraints, represented by (*) [tex]A\overline{x} \le \overline{b}[/tex], for a matrix [tex]A[/tex] and a vector [tex]\overline{b}[/tex]. I'm looking for a procedure to decide whether the solution subspace of (*) with respect to a subvector [tex]\overline{x}^1[/tex] is contained in the solution subspace with respect to another subvector [tex]\overline{x}^2[/tex] (of the same dimension as [tex]\overline{x}^1[/tex]).
To put it another way: if we project the set of all solutions of (*) to the components of [tex]\overline{x}^1[/tex], is the resulting set contained in the projection to [tex]\overline{x}^2[/tex]? The order of components of [tex]\overline{x}^1[/tex] and [tex]\overline{x}^2[/tex] does matter.

I can imagine that there are standard procedures for answering this question. Are there efficient ones? Where do I have to look? I haven't yet found anything related in textbooks on Linear Programming, using keywords "subspace" and "sub(-)solution" -- maybe I'm using the wrong keywords?

My own attempts:

(1) Eliminate the variables outside [tex]\overline{x}^1[/tex] by computing suitable positive linear combinations of the lines of [tex]A\overline{b}[/tex]. This yields a set of constraints over [tex]\overline{x}^1[/tex] that are implied by (*). If we do the same for [tex]\overline{x}^2[/tex], it just remains to check whether all latter constraints follow from the former, perhaps using the simplex algorithm, which also reveals redundancies. But this seems inefficient to me because, in the worst case, one would have to compute exponentially many linear combinations.

(2) Perhaps it is possible to formulate the above problem as a new linear program, which then can be solved using simplex? I'm still missing a more precise idea here.

Perhaps someone here can put me on the right track?

Thomas
Guest
 

Re: Linear programming -- checking solution subspace contain

Postby 016hnoor » Thu Mar 19, 2015 3:02 am

I can imagine that there are standard procedures for answering this question. Are there efficient ones? Where do I have to look? I haven't yet found anything related in textbooks on Linear Programming,

016hnoor
 
Posts: 3
Joined: Thu Mar 19, 2015 12:41 am
Reputation: 1


Return to Simultaneous Equations, Systems of Equations/Inequalities



Who is online

Users browsing this forum: No registered users and 1 guest