EE364a, Winter 2007-08 Prof. S. Boyd
EE364a Homework 4 solutions
4.11 Problems involving ℓ
1
- and ℓ
∞
-norms. Formulate the following problems as LPs. Ex-
plain in detail the relation between the optimal solution of each problem and the
solution of its equivalent LP.
(a) Minimize kAx − bk
∞
(ℓ
∞
-norm approximation).
(b) Minimize kAx − bk
1
(ℓ
1
-norm approximation).
(c) Minimize kAx − bk
1
subject to kxk
∞
≤ 1.
(d) Minimize kxk
1
subject to kAx − bk
∞
≤ 1.
(e) Minimize kAx − bk
1
+ kxk
∞
.
In each problem, A ∈ R
m×n
and b ∈ R
m
are given. (See §6.1 for more problems
involving approximation and constrained approximation.)
Solution.
(a) Equivalent to the LP
minimize t
subject to Ax − b t1
Ax − b −t1.
in the variables x ∈ R
n
, t ∈ R. To see the equivalence, assume x is fixed in this
problem, and we optimize only over t. The constraints say that
−t ≤ a
T
k
x − b
k
≤ t
for each k, i.e., t ≥ |a
T
k
x − b
k
|, i.e.,
t ≥ max
k
|a
T
k
x − b
k
| = kAx − bk
∞
.
Clearly, if x is fixed, the optimal value of the LP is p
⋆
(x) = kAx −bk
∞
. Therefore
optimizing over t and x simu ltaneously is equivalent to the original problem.
(b) Equivalent to the LP
minimize 1
T
s
subject to Ax − b s
Ax − b −s
with variables x ∈ R
n
ands ∈ R
m
. Assume x is fixed in this problem, and we
optimize only over s. The constraints say that
−s
k
≤ a
T
k
x − b
k
≤ s
k
1