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

Hector Petersen 2022-06-22 Answered
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!
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

alisonhleel3
Answered 2022-06-23 Author has 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.)
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-05-06

Apply Stokes' theorem to evaluate the integral ∫C (5x^2y^2 - 8yz^2)dx + (3x^3y - 4xz^2)dy - 5xyzdz; where C is the curve of intersection of the surface z = x^2 +y^2 with the plane z = 3 + x + y.

asked 2021-09-07
Which interval is wider: (a) the 95% confidence interval for the conditional mean of the response variable at a particular set of values of the predictor variables or (b) the 95% prediction interval for the response variable at the same set of values of the predictor variables?
asked 2020-10-18
Use Green's Theorems to evaluate Cxydx+x2y3dy, where C is the triangle with vertices(0,0),(1,0)and (1,2).
asked 2021-09-05

Use the following linear regression equation to answer the questions.
x1=1.3+3.0x28.3x3+1.6x4
(a) Which variable is the response variable?
(b) Which number is the constant term? List the coefficients with their corresponding explanatory variables.
(c) If x2=8,x3=2,andx4=6 , what is the predicted value for x1? (Use 1 decimal place)
(d) Explain how each coefficient can be thought of as a "slope" under certain conditions.

asked 2020-12-16
Let f=[x2y2,xy2] and R:1x2+y2,+4,x0,yx. Evaluate CF(r)dr counterclockwise around the boundary C of the region R by Green's theorem.
asked 2021-11-13
Find the volume of the solid generated by rotating about the x-axis the region bounded by
y=4x, x=3, x=3
and the x-axis.
asked 2021-02-25
Use Stokes' Theorem to evaluate CFdr where C is oriented counterclockwise as viewed from above.
F(x,y,z)=(x+y2)i+(y+z2)j+(z+x2)k,
C is the triangle with vertices (3,0,0),(0,3,0), and (0,0,3).