Navigator
Norm approximation problem
We consider the unconstrained norm approximation problem
min
∥
A
x
−
b
∥
\min \lVert Ax-b\rVert
min∥Ax−b∥
where
∥
⋅
∥
\lVert\cdot\lVert
∥⋅∥ is any norm.
Reformulation 1:
min
∥
y
∥
s
.
t
.
A
x
−
b
=
y
\min \lVert y\rVert\\ s.t.\quad Ax-b=y
min∥y∥s.t.Ax−b=y
cvx code
%% input data
rng(729);
n = 4;
m = 2*n;
A = randn(m, n);
b = randn(m, 1);
p = 2;
q = p/(p-1);
% reformulation 1: original problem
cvx_begin quiet
variable x(n)
minimize (norm(A*x-b, p))
cvx_end
opt1 = cvx_optval;
yalmip code
%% yalmip
x = sdpvar(n, 1);
obj = norm(A*x-b, p);
F = [];
optimize(F, obj);
Reformulation 2:
max
b
′
v
s
.
t
.
{
∥
v
∥
∗
≤
1
A
′
v
=
0
\max b'v\\ s.t. \begin{cases} \lVert v\rVert^*\leq1\\ A'v=0 \end{cases}
maxb′vs.t.{∥v∥∗≤1A′v=0
cvx code
cvx_begin quiet
variable nu(m)
maximize (b'*nu);
norm(nu, q)<=1;
A'*nu == 0;
cvx_end
opt3 = cvx_optval;
yalmip code
%% yalmip: reformulation 3
nu = sdpvar(m, 1);
F = [norm(nu, q)<=1, A'*nu==0];
obj = b'*nu;
optimize(F, -obj);
Reformulation
The above problem can be reformulated as:
min
(
1
/
2
)
∥
y
∥
2
s
.
t
.
A
x
−
b
=
y
\min (1/2)\lVert y\rVert^2\\ s.t.\quad Ax-b=y
min(1/2)∥y∥2s.t.Ax−b=y
Here we have introduced new variables, and replaced the objective by half its square. The dual of the reformulated problem is
max
−
(
1
/
2
)
∥
ν
∥
∗
2
+
b
T
ν
s
.
t
.
A
T
ν
=
0
\max -(1/2)\lVert \nu\rVert_*^2+b^T\nu\\ s.t.\quad A^T\nu=0
max−(1/2)∥ν∥∗2+bTνs.t.ATν=0
where we use the fact that the conjugate of
(
1
/
2
)
∥
⋅
∥
2
(1/2)\lVert\cdot\rVert^2
(1/2)∥⋅∥2 is
(
1
/
2
)
∥
⋅
∥
∗
2
(1/2)\lVert\cdot\rVert_*^2
(1/2)∥⋅∥∗2
cvx code
cvx_begin
variables x(n) y(m)
minimize (0.5*square_pos(norm(y, p)))
A*x-b==y;
cvx_end
opt4 = (2*cvx_optval).^(0.5);
yalmip code
%% yalmip: reformulation 4
x = sdpvar(n, 1);
y = sdpvar(m, 1);
F = [A*x-b==y];
obj = 0.5*norm(y, p)^2;
optimize(F, obj);
opt4_yal = (2*value(obj))^(0.5);
cvx: dual
%% cvx: reformulation 5
cvx_begin quiet
variable nu(m)
maximize (-0.5*square_pos(norm(nu, q))+b'*nu);
A'*nu == 0;
cvx_end
opt5 = (2*cvx_optval)^(0.5);
yalmip: dual
%% yalmip: reformulation 5
nu = sdpvar(m, 1);
F = [A'*nu==0];
obj = -0.5*(norm(nu, q))^2+b'*nu;
optimize(F, -obj);
opt5_yal = (2*value(obj))^0.5;
Reference
Convex Optimization S.Boyd Page 268