2
$\begingroup$

Let $P = \{ x \in R^n : Ax \leq b, x\geq 0\}$ and $Q= \{ (x, r)' \in R^{n+m}: Ax + r= b, x \geq 0, r\geq 0\}.$ Show that

$$x \text{ is basic solution of } P \iff (x, b-Ax) \text{ is basic solution of }Q$$

Type: The restrictions in Q are associated to row vectors in $R^{n+m}$

My attempt:

Lets try the first implication. Suppose that we have n linear ative constraints in x and consider the vector (x, b-Ax). Note that this vector satisfies the equaly constraints in Q. The n linear active constraints in P will be equivalent to n active signal constraints in Q. I need, now, to find m more active constraints such that the set of all of those active connstraints is linearly independent. My guess is that those are the vectors corresponding the equaly constraints, but I couldnt show it.

Well, this iswhat I tried. It would be great to recieve some suggestions to improve it.

Thanks in advance!

$\endgroup$
2
+150
$\begingroup$

The main difficulty here is to write out an expressive enough set of notations. Write

$$ \begin{array}{lcl} x^{\sharp} &=& (x,b-Ax) \\ b &=& (b_1,\ldots,b_m) \\ x &=& (x_1,\ldots,x_n) \\ A &=& (a_{ij}) \ (1\leq i \leq m,1\leq j \leq n) \\ \phi_i(x_1,\ldots,x_n) &=& \sum_{j=1}^{n}a_{ij}x_j \\ \xi_j(x_1,\ldots,x_n) &=& x_j \\ \eta_j(x,r) &=& \xi_j(x) \\ \sigma_{i}(x,r) &=& r_i \\ \rho_{i}(x,r) &=& r_i+\sum_{j=1}^{n}a_{ij}x_j \\ \end{array} $$

Then $P$ is defined by the set of $n+m$ inequalities $$ \left\lbrace\begin{array}{lcl} \xi_j\geq 0, \ 1\leq j\leq n & ; &\text{we call these } \xi\text{-inequalities} . \\ \phi_i\leq b_i, \ 1\leq i\leq m & ; & \text{we call these } \phi\text{-inequalities} . \\ \end{array}\right.\tag{1} $$

While $Q$ is defined by the set of $n+2m$ inequalities $$ \left\lbrace\begin{array}{lcl} \eta_j\geq 0, \ 1\leq j\leq n & ; &\text{we call these } \eta\text{-inequalities} . \\ \sigma_i\geq 0, \ 1\leq i\leq m & ; & \text{we call these } \sigma\text{-inequalities} . \\ \rho_i=b_i, \ 1\leq i\leq m & ; & \text{we call these } \rho\text{-equalities} . \\ \end{array}\right.\tag{2} $$

Note that equivalently each equality $\rho_i=b_i$ can be replaced by the set of two inequalities $\rho_i\leq b_i, \rho_i\geq b_i$ ; we call these $\rho$-inequalities.

Suppose that $x$ is basic relatively to $P$. Then there is $I\subseteq[|1..n|],J\subseteq[|1..m|] $ such that $|I|+|J|=n$, ${\cal F}=\lbrace \phi_i \rbrace_{i\in I} \cup \lbrace \xi_j \rbrace_{j\in J}$ is linearly independent, and $\phi_i(x)=b_i$ for $i\in I$, $\eta_j(x)=0$ for $j\in J$. Let ${\cal F}'=\lbrace \rho_i \rbrace_{i\in I} \cup \lbrace \eta_j \rbrace_{j\in J} \cup \lbrace \sigma_i \rbrace_{1\leq i \leq m}$. Then $| {\cal F}' |=n+m$, and all the members of $G$ are active at $x^{\sharp}$. It will suffice therefore to show that $G$ is linearly independent ; suppose then that we have a linear relation

$$ \sum_{i\in I} R_i\sigma_i + \sum_{j\in J} E_j\eta_j + \sum_{i=1}^{m} S_i\rho_i=0 \tag{3} $$

where the $R_i,E_j,S_i$ are scalars. This means for any $(x_1,x_2,\ldots,x_n,r_1,\ldots,r_m)\in R^{n+m}$, we have

$$ \sum_{i\in I} R_ir_i + \sum_{j\in J} E_jx_j + \sum_{i=1}^{m} S_i\bigg(r_i+\sum_{j=1}^{n}a_{ij}x_j\bigg)=0 \tag{4} $$

Rearranging, we obtain

$$ \sum_{i\in I} (R_i+S_i)r_i + \sum_{i\in I} \sum_{j=1}^{n}S_i a_{ij}x_j+ \sum_{j\in J} E_jx_j + \sum_{i\not\in I} S_ir_i + \sum_{i\not\in I} S_i\bigg(\sum_{j=1}^{n}a_{ij}x_j\bigg)=0 \tag{5} $$

We deduce that $R_i+S_i=0$ for $i\in I$, and $S_i=0$ for $i\not\in I$, and hence

$$ \sum_{i\in I} \sum_{j=1}^{n}S_i a_{ij}x_j+ \sum_{j\in J} E_jx_j=0 \tag{6} $$

This is equivalent to $\sum_{i\in I}S_i\phi_i+\sum_{j\in J}E_j\xi_j=0$, which is a linear relation between elements of $\cal F$. Thus $x^{\sharp}$ is basic relatively to $Q$ as wished.

Conversely, suppose that $x^{\sharp}$ is basic relatively to $Q$. Then there is a set $\cal G$ of $n+m$ linearly independent constraints from the list in (2), all active at $x^{\sharp}$. Since $\rho_i$ and $-\rho_i$ are not linearly independent, they are not both in $\cal F$, so $\cal F$ contains at most $m$ constraints of the form $\rho_i\leq b_i$ or $\rho_i\geq b_i$. Throwing those away, we are left with (at least) $n$ linearly independent $\eta$- or $\sigma$- constraints ; the corresponding set of $\xi$- or $\phi$- constraints show that $x$ is basic relatively to $P$.

$\endgroup$
  • $\begingroup$ It is not clear that the constraints are, indeed, linearly independent when we "😕pass" from $R^n$ to $R^{n+m}. I mean, what ensures that this new set, when you add m more vectors, is, indeed, l.i, since we were talking about only n in P? $\endgroup$ – Giiovanna Sep 19 '14 at 12:16
  • $\begingroup$ @Giiovanna I have updated the presentation, taking your comment into account $\endgroup$ – Ewan Delanoy Sep 20 '14 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.