Consider a minimization problem: <mtable columnalign="right left right left right left right

Hector Petersen

Hector Petersen

Answered question

2022-06-22

Consider a minimization problem:
min i = 1 n | x i | , A x = b ,
where A is an m × n matrix of rank m. I know that the minimum points contains one where at least n m components of x is zero and I have proved this conclusion. My problem is that, I think this should be a developed proposition but I am not familiar with optimization theory, so I don't know where to find a reference. Could anybody help me find a reference like a book or article? Thanks!

Answer & Explanation

alisonhleel3

alisonhleel3

Beginner2022-06-23Added 23 answers

One standard linearization of absolute value is to introduce a new variable y i to represent | x i | , and the resulting linear programming (LP) problem is to minimize i = 1 n y i subject to
A x = b y i x i for all  i y i x i for all  i
This LP has 2 n variables and m + 2 n constraints. A standard result from LP theory is that there exists an optimal solution with at most m + 2 n nonzero values.

A different standard linearization of absolute value is to introduce two new nonnegative variables x i + and x i to represent | x i | , and the resulting LP is to minimize i = 1 n ( x i + + x i ) subject to A ( x + x ) = b. This LP has 2 n variables and m constraints. A standard result from LP theory is that there exists an optimal solution with at most m nonzero values, hence at least 2 n m zero values, hence at least ( 2 n m ) n = n m zero values among the original x i variables. (Note that x i + x i = 0 at optimality because otherwise we can improve the objective value and preserve feasibility by decreasing both x i + and x i by the same amount, but this observation is not required to obtain the desired result.)

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Multivariable calculus

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?