University:
University of California, Berkeley
Course:
MATH 56 Linear Algebra
Academic year:

2022
Views:

260

Pages:

10
Author:

Clint W.

Discussion 3 Absolute Value Tricks Example Suppose we have the problem: min |x1 + 5x2 | x1 ,x2 s.t. x1 − 3x2 ≥ 2 x1 ≥ 0 How can we convert it into a Linear Program? Discussion 3 Absolute Value Tricks Example Suppose we have the problem: min |x1 + 5x2 | x1 ,x2 s.t. x1 − 3x2 ≥ 2 x1 ≥ 0 How can we convert it into a Linear Program? Remember |x| = max{x, −x}. min x1 ,x2 max{x1 + 5x2 , −x1 − 5x2 } s.t. x1 − 3x2 ≥ 2 x1 ≥ 0 Discussion 3 Absolute Value Tricks Form 1 Create a new variable z and make: min z x1 ,x2 ,z s.t. z ≥ x1 + 5x2 z ≥ −(x1 + 5x2 ) x1 − 3x2 ≥ 2 x1 ≥ 0 Discussion 3 Absolute Value Tricks Form 2 Each number can be divided in its positive and negative parts: I 35 = (35) − (0) I −15 = (0) − (15) Or in general x = z + − z − where z + ≥ 0 and z − ≥ 0. Discussion 3 Absolute Value Tricks Form 2 Using this intuition: min x1 ,x2 ,z + ,z − + − s.t. z − z z+ + z− = x1 + 5x2 x1 − 3x2 ≥ 2 x1 ≥ 0, z Why does this work? + ≥ 0, z − ≥ 0 Discussion 3 Absolute Value Tricks General linearization of Abs Given a function g (y , x) increasing with y for any x ∈ X , min g (|f (x)|, x) x∈X is equivalent (in some sense) to min g (z + + z − , x) x∈X s.t. z + − z − = f (x) z + ≥ 0; z − ≥ 0 Discussion 3 Absolute Value Tricks General linearization of Abs Given a function g (y , x) increasing with y for any x ∈ X , min g (|f (x)|, x) x∈X is equivalent (in some sense) to min g (z + + z − , x) x∈X s.t. z + − z − = f (x) z + ≥ 0; z − ≥ 0 Proof by contradiction Discussion 3 Absolute Value Tricks Sketch of proof We will show that for the optimal solution, either z + = 0 or z − = 0. Suppose z̄ + > 0, z̄ − > 0 and x̄ form the optimal solution for the later problem. Then z̄ + − z̄ − = f (x̄). Introduce a = min{z̄ + , z̄ − } and ẑ + = z̄ + − a, ẑ − = z̄ − − a. Observe that (ẑ + , ẑ − , x̄) is a feasible solution: ẑ + − ẑ − = z̄ + − a − z̄ − + a = z̄ + − z̄ − = f (x̄) and that it is better than the optimal one: z̄ + + z̄ − > ẑ + − ẑ − =⇒ g (z̄ + + z̄ − , x̄) > g (ẑ + + ẑ − , x̄), which is a contradiction with the assumption of optimality. Discussion 3 Absolute Value Tricks General Form I Problem: We have the following nonlinear problem: min x∈Rn s.t. n X |xi | i=1 Ax = b. where A ∈ Rm×n and b ∈ Rm . I Description: The objective is a non-smooth non-linear function which seems very hard to be optimized. However, this is not true! Discussion 3 Absolute Value Tricks Tricks Two ways of linearizing the absolute value in an optimization problem: I Trick 1: Introduce new variables zi for i = 1, 2, . . . , n. Add constraints zi ≥ xi andP zi ≥ −xi for i = 1, 2, . . . , n. Then minimize the function ni=1 zi . I Trick 2: Introduce new variables xi+ and xi− for i = 1, 2, . . . , n. Add constraints xi = xi+ − xi− and xi+ ≥ 0, − xP i ≥ 0 for i = 1, 2, . . . , n. Then minimize the function n + − i=1 xi + xi .