Exercise 3.27

(a) Let

This is not a linear problem, but we can reformulate it as an auxiliary linear program. $\rightharpoonup$ Let $y$ be a vector that indicates whether each component $x_i>0$ for all $i\in \{1,,n\}$:

Now define a new variable $z=x-y$. Then the problem becomes

Let this feasible region be denoted by

$\leftarrow$ Suppose $(y^{\text{∗}},z^{\text{∗}})$ is an optimal solution of the above linear program, and define $x^{\text{∗}}=z^{\text{∗}}+y^{\text{∗}}$.

Assume, for contradiction, that $x^{\text{∗}}$ is not optimal for the original problem. Then there exists some feasible $\hat{x}$ such that

and the number of positive components in $\hat{x}$ is greater than in $x^{\text{∗}}$.

For this $\hat{x}$, define $ŷ$ and $ẑ=\hat{x}-ŷ$ as before. Then $(ŷ,ẑ)$ is feasible for the LP and satisfies

which contradicts the optimality of $(y^{\text{∗}},z^{\text{∗}})$. Hence, $x^{\text{∗}}=z^{\text{∗}}+y^{\text{∗}}$ is optimal for the original problem, i.e., it maximizes the number of positive components.

(b) Now suppose that we wish to find a vector $x\in {ℝ}^n$ satisfying

such that the number of positive components of $x$ is maximized.

By analogy with part (a), we can again introduce auxiliary variables $y$ and $z$ such that

where $y_i$ indicates whether $x_i>0$, that is,

However, because the constraint $\mathit{Ax}=b$ is not homogeneous, we must modify the feasible region. In particular, we replace the equality $A(z+y)=0$ by $A(z+y)=b$, and the nonnegativity of $z$ by the constraint $y+z\ge 0$. This ensures that the resulting $x=y+z$ satisfies $x\ge 0$ and $\mathit{Ax}=b$.

Hence, the problem can be formulated as the following single linear program:

At optimality, $x^{\text{∗}}=y^{\text{∗}}+z^{\text{∗}}$ gives a feasible vector that maximizes the number of positive components among all solutions satisfying $\mathit{Ax}=b,x\ge 0.$