Exercise 3.27

  • Suppose that we wish to find a vector x ∈ ℝ n that satisfies Ax = 0 and x ≥ 0 , and such that the number of positive components of x is maximized. Show that this can be accomplished by solving the linear programming problem

    maximize ∑ i = 1 n y i subject to A ( z + y ) = 0 , y i ≤ 1 , for all  i , z , y ≥ 0 .
  • Suppose that we wish to find a vector x ∈ ℝ n that satisfies Ax = b and x ≥ 0 , and such that the number of positive components of x is maximized. Show how this can be accomplished by solving a single linear programming problem.

Answers

(a) Let

S = { x ∈ ℝ n ∣ Ax = 0 , x ≥ 0 , and the number of positive components of  x  is maximized } .

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

y i = { 1 , if  x i > 0 , 0 , otherwise.

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

max ⁡ ∑ i = 1 n y i s.t. A ( z + y ) = 0 , z ≥ 0 , y ≥ 0 , y ≤ 1 .

Let this feasible region be denoted by

P = { ( y , z ) ∈ ℝ 2 n ∣ A ( z + y ) = 0 , z ≥ 0 , 0 ≤ y ≤ 1 } .

← Suppose ( y ∗ , z ∗ ) is an optimal solution of the above linear program, and define x ∗ = z ∗ + y ∗ .

Assume, for contradiction, that x ∗ is not optimal for the original problem. Then there exists some feasible x ^ such that

A x ^ = 0 , x ^ ≥ 0 ,

and the number of positive components in x ^ is greater than in x ∗ .

For this x ^ , define ŷ and ẑ = x ^ − ŷ as before. Then ( ŷ , ẑ ) is feasible for the LP and satisfies

∑ i ŷ i > ∑ i y i ∗ ,

which contradicts the optimality of ( y ∗ , z ∗ ) . Hence, x ∗ = z ∗ + y ∗ 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 ∈ ℝ n satisfying

Ax = b , x ≥ 0 ,

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

x = y + z ,

where y i indicates whether x i > 0 , that is,

0 ≤ y i ≤ 1 , ∀ ⁡ i .

However, because the constraint 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 ≥ 0 . This ensures that the resulting x = y + z satisfies x ≥ 0 and Ax = b .

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

max ⁡ ∑ i = 1 n y i s.t. A ( z + y ) = b , y + z ≥ 0 , 0 ≤ y ≤ 1 .

At optimality, x ∗ = y ∗ + z ∗ gives a feasible vector that maximizes the number of positive components among all solutions satisfying Ax = b , x ≥ 0 .

User profile picture
2025-10-23 22:09
Comments