An Introduction to CVX
Amirpasha Shirazinia
Signals and Systems Division
Department of Engineering Sciences
Uppsala University
November 4, 2014
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
1 / 17
What is CVX ?
• CVX is a MATLAB–based software package for solving convex
optimization problems.
• Feature: CVX is written in a high–level form, i.e., close to
mathematical notations.
• 1748 citations (according to google).
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
2 / 17
What is CVX ?
• CVX is a MATLAB–based software package for solving convex
optimization problems.
• Feature: CVX is written in a high–level form, i.e., close to
mathematical notations.
• 1748 citations (according to google).
• Restriction: can be applied to convex programs,
• What if the problem you are dealing with is non-convex:
• Try to convexify the non-convex problem,
• Try to relax the problem in order to make it convex,
• Go for a sub-optimal locally minimizing approach, e.g., fmincon.
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
2 / 17
What is CVX ?
• CVX is a MATLAB–based software package for solving convex
optimization problems.
• Feature: CVX is written in a high–level form, i.e., close to
mathematical notations.
• 1748 citations (according to google).
• Restriction: can be applied to convex programs,
• What if the problem you are dealing with is non-convex:
• Try to convexify the non-convex problem,
• Try to relax the problem in order to make it convex,
• Go for a sub-optimal locally minimizing approach, e.g., fmincon.
• Download & install CVX .
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
2 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
>> cvx begin
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
>> cvx begin
>> variables x y
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
>> cvx begin
>> variables x y
>> y >= 0
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
>> cvx begin
>> variables x y
>> y >= 0
>> x >= 0
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
>> cvx begin
>> variables x y
>> y >= 0
>> x >= 0
>> x <= 1
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
>> cvx begin
>> variables x y
>> y >= 0
>> x >= 0
>> x <= 1
>> minimize((x + y + 3) b 2)
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Scalar Example
minimize (x + y + 3)2
subject to y ≥ 0
0 ≤ x ≤ 1.
(1)
How to translate Problem (1) into CVX ?
>> cvx begin
>> variables x y
>> y >= 0
>> x >= 0
>> x <= 1
>> minimize((x + y + 3) b 2)
>> cvx end
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
3 / 17
Some Useful Commands & Hints
• cvx status: gives the status of the solution –
solved/infeasible/unbounded,
• cvx optval: gives the optimal value,
• cvx quiet(true): displays off the optimization procedure,
• Affine equality constraints are denoted by ==,
• Flexibility: CVX commands can be used in MATLAB loops,
• Lots of other hints available in CVX user’s guide.
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
4 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
>> N = 10; alpha = rand(1, N)
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
>> N = 10; alpha = rand(1, N)
>> cvx begin
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
>> N = 10; alpha = rand(1, N)
>> cvx begin
>> variable p(N)
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
>> N = 10; alpha = rand(1, N)
>> cvx begin
>> variable p(N)
>> p >= 0
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
>> N = 10; alpha = rand(1, N)
>> cvx begin
>> variable p(N)
>> p >= 0
>> sum(p) == 1
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
>> N = 10; alpha = rand(1, N)
>> cvx begin
>> variable p(N)
>> p >= 0
>> sum(p) == 1
>> minimize(alpha ∗ p)
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.8e (Boyd): Finding optimal probabilities for some weighting
coefficients {αi }N
i=1
minimize
subject to
>> N = 10; alpha = rand(1, N)
>> cvx begin
>> variable p(N)
>> p >= 0
>> sum(p) == 1
>> minimize(alpha ∗ p)
>> cvx end
Amirpasha Shirazinia (UU)
PN
i=1 αi pi
pi ≥ 0 , ∀i
PN
i=1 pi = 1.
An Introduction to CVX
(2)
Internal Seminar
5 / 17
Vector Example
• Problem 4.26 (Boyd):
minimize
subject to
x⊤ x + y + z
x⊤ x ≤ yz
y≥0, z≥0
(3)
• Question 1: Is the objective function convex?
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
6 / 17
Vector Example
• Problem 4.26 (Boyd):
minimize
subject to
x⊤ x + y + z
x⊤ x ≤ yz
y≥0, z≥0
(3)
• Question 1: Is the objective function convex? Yes! ,
• Question 2: Are the constraints convex sets?
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
6 / 17
Vector Example
• Problem 4.26 (Boyd):
minimize
subject to
x⊤ x + y + z
x⊤ x ≤ yz
y≥0, z≥0
(3)
• Question 1: Is the objective function convex? Yes! ,
• Question 2: Are the constraints convex sets? Let’s call CVX first >> N = 10;
>> cvx begin
>> variables x(N, 1) y z
>> y >= 0
>> z >= 0
>> x′ ∗ x − y ∗ z <= 0
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
6 / 17
Vector Example
• Problem 4.26 (Boyd):
minimize
subject to
x⊤ x + y + z
x⊤ x ≤ yz
y≥0, z≥0
(3)
• Question 1: Is the objective function convex? Yes! ,
• Question 2: Are the constraints convex sets? Let’s call CVX first >> N = 10;
>> cvx begin
>> variables x(N, 1) y z
>> y >= 0
>> z >= 0
>> x′ ∗ x − y ∗ z <= 0
Disciplined convex programming error:
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
6 / 17
Vector Example (Cont’d)
• Why the constraint x⊤ x ≤ yz does not form a convex region?
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
7 / 17
Vector Example (Cont’d)
• Why the constraint x⊤ x ≤ yz does not form a convex region?
• convex ≤ ???
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
7 / 17
Vector Example (Cont’d)
• Why the constraint x⊤ x ≤ yz does not form a convex region?
• convex ≤ ???
• ??? should be an affine or concave function.
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
7 / 17
Vector Example (Cont’d)
• Why the constraint x⊤ x ≤ yz does not form a convex region?
• convex ≤ ???
• ??? should be an affine or concave function.
• Now, via the Hessian matrix, check if f (y, z) = yz is concave (Problem
3.16 Boyd).
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
7 / 17
Vector Example (Cont’d)
• Why the constraint x⊤ x ≤ yz does not form a convex region?
• convex ≤ ???
• ??? should be an affine or concave function.
• Now, via the Hessian matrix, check if f (y, z) = yz is concave (Problem
3.16 Boyd).
• How to convexify Problem (2)?
2x
x⊤ x ≤ yz ⇐⇒ (4)
y − z ≤ y + z.
2
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
7 / 17
Vector Example (Cont’d)
• Why the constraint x⊤ x ≤ yz does not form a convex region?
• convex ≤ ???
• ??? should be an affine or concave function.
• Now, via the Hessian matrix, check if f (y, z) = yz is concave (Problem
3.16 Boyd).
• How to convexify Problem (2)?
2x
x⊤ x ≤ yz ⇐⇒ (4)
y − z ≤ y + z.
2
• Now, we have a convex problem ,
minimize
subject to
Amirpasha Shirazinia (UU)
x⊤ x + y +
z
2x
y−z ≤y+z
2
y≥0, z≥0
An Introduction to CVX
(5)
Internal Seminar
7 / 17
Vector Example (Cont’d)
• CVX code:
>> N = 10;
>> cvx begin
>> variables x(N, 1) y z
>> y >= 0
>> z >= 0
>> norm([2x; y − z], 2) <= y + z
>> minimize(x′ ∗ x + y + z)
>> cvx end
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
8 / 17
Matrix Example: Sensing/Measurement Matrix design in a
Bayesian Framework
• Consider the linear Gaussian model y = Ax + n,
• where x ∼ N (0, R), n ∼ N (0, σ 2 I), such that x, y, n ∈ RN and
A ∈ RN ×N .
• The MMSE estimator of x given the noisy measurements y becomes
−1
1
1
bk22 ] = 2 R−1 + 2 A⊤ A
bmmse = arg min E[kx − x
A⊤ y
x
σ
σ
b
x
• The corresponding MSE, to be minimized, is
(
−1 )
1 ⊤
−1
MSE = Tr
R + 2A A
σ
Amirpasha Shirazinia (UU)
An Introduction to CVX
(6)
Internal Seminar
9 / 17
Matrix Example: Sensing/Measurement Matrix design in a
Bayesian Framework
• Consider the linear Gaussian model y = Ax + n,
• where x ∼ N (0, R), n ∼ N (0, σ 2 I), such that x, y, n ∈ RN and
A ∈ RN ×N .
• The MMSE estimator of x given the noisy measurements y becomes
−1
1
1
bk22 ] = 2 R−1 + 2 A⊤ A
bmmse = arg min E[kx − x
A⊤ y
x
σ
σ
b
x
• The corresponding MSE, to be minimized, is
(
−1 )
1 ⊤
−1
MSE = Tr
R + 2A A
σ
• Assume the total available power P > 0, we have
E[kAxk22 ] = . . . = Tr ARA⊤ ≤ P
Amirpasha Shirazinia (UU)
An Introduction to CVX
(6)
(7)
Internal Seminar
9 / 17
Matrix Example (Cont’d)
• The sensing/measurement matrix design problem is posed as
n
−1 o
minimize Tr R−1 + σ12 A⊤ A
subject to Tr RA⊤ A ≤ P
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
(8)
10 / 17
Matrix Example (Cont’d)
• The sensing/measurement matrix design problem is posed as
n
−1 o
minimize Tr R−1 + σ12 A⊤ A
subject to Tr RA⊤ A ≤ P
• Problem (8) is not convex in A, but convex in A⊤ A.
• Let X , A⊤ A, we have an equivalent optimization problem
n
−1 o
minimize Tr R−1 + σ12 X
subject to Tr {RX} ≤ P
X0
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
(8)
(9)
10 / 17
Matrix Example (Cont’d)
• Let’s translate the optimization problem (8) into CVX codes
>> N = 3; rho = 0.5; P = 10; sigma sq = 0.01;
>> R = [1 rho rhob 2; rho 1 rho ; rhob 2 rho 1];
>> cvx begin sdp
>> variable X(N, N) symmetric
>> X == semidefinite(N, N)
>> trace(R ∗ X) <= P
>> minimize(trace inv(R b(−1) + X/sigma sq))
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
11 / 17
Matrix Example (Cont’d)
• Let’s translate the optimization problem (8) into CVX codes
>> N = 3; rho = 0.5; P = 10; sigma sq = 0.01;
>> R = [1 rho rhob 2; rho 1 rho ; rhob 2 rho 1];
>> cvx begin sdp
>> variable X(N, N) symmetric
>> X == semidefinite(N, N)
>> trace(R ∗ X) <= P
>> minimize(trace inv(R b(−1) + X/sigma sq))
>> cvx end
• How to get back A from X?
• For example, use the cholesky factorization; in MATLAB A = chol(X).
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
11 / 17
A Little into Compressed Sensing (CS)
• CS answers the following question:
• In a linear set of equations y = Ax, would it be possible to uniquely
solve the equations if the number of unknowns, i.e. dim(x), is larger
than the number of equations, i.e. dim(y)?
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
12 / 17
A Little into Compressed Sensing (CS)
• CS answers the following question:
• In a linear set of equations y = Ax, would it be possible to uniquely
solve the equations if the number of unknowns, i.e. dim(x), is larger
than the number of equations, i.e. dim(y)?
• Yes! But under the condition that the unknown variables are known
to be sparse (K ≪ N ) plus some mild conditions.
x
A
y
M
N
=
K
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
12 / 17
Optimization framework for CS
• We know that the source, x, is sparse.
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
13 / 17
Optimization framework for CS
• We know that the source, x, is sparse.
• We observe the linear measurements y = Ax.
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
13 / 17
Optimization framework for CS
• We know that the source, x, is sparse.
• We observe the linear measurements y = Ax.
• Goal: Go for the sparsest solution.
minimize kxk0
subject to y = Ax
(10)
• where the ℓ0 –norm kxk0 , card(x) = #non-zero components.
• Check whether or not the optimization problem (10) is convex ...
• Hint: Check the geometry of ℓ0 ...
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
13 / 17
Optimization framework for CS
• We know that the source, x, is sparse.
• We observe the linear measurements y = Ax.
• Goal: Go for the sparsest solution.
minimize kxk0
subject to y = Ax
(10)
• where the ℓ0 –norm kxk0 , card(x) = #non-zero components.
• Check whether or not the optimization problem (10) is convex ...
• Hint: Check the geometry of ℓ0 ...
• NOT CONVEX!
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
13 / 17
Optimization framework for CS (Cont’d)
• How to tackle the problem?
• Standard approach: Relax the objective function to the nearest
convex norm, i.e., ℓ1 –norm, a.k.a. basis pursuit (BP),
minimize kxk1
subject to y = Ax
• where kxk1 =
Amirpasha Shirazinia (UU)
(11)
PN
n=1 |xn |.
An Introduction to CVX
Internal Seminar
14 / 17
Optimization framework for CS (Cont’d)
• How to tackle the problem?
• Standard approach: Relax the objective function to the nearest
convex norm, i.e., ℓ1 –norm, a.k.a. basis pursuit (BP),
minimize kxk1
subject to y = Ax
• where kxk1 =
(11)
PN
n=1 |xn |.
• The miracle happens: Under some conditions, the solutions to (11)
and (10) are the same. CS theory also determines how many
measurements need to be acquired in order for this equivalence to
hold.
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
14 / 17
Optimization framework for CS: Example
>> N = 50; M = 25; K = 5;
>> supp = randsample(N, K)′; x = zeros(N, 1); x(supp) = randn(K, 1);
>> A = randn(M, N); s = sqrt(sum(A. b 2)); S = diag(1./s);
>> A = A ∗ S;
>> y = A ∗ x;
>> cvx begin
>> variable x hat(N, 1)
>> y == A ∗ x hat
>> minimize(norm(x hat, 1))
>> cvx end
>> plot(1 : N, x, 1 : N,′ s′ , x hat,′ o′ )
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
15 / 17
Conclusion
• CVX is cool!
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
16 / 17
References
• S. Boyd and L. Vandenberghe, Convex optimization, Cambridge
University Press, 2004.
• http://cvxr.com/cvx.
• A. Shirazinia, Source and channel coding for compressed sensing and
control, PhD thesis, KTH, 2014.
Amirpasha Shirazinia (UU)
An Introduction to CVX
Internal Seminar
17 / 17
© Copyright 2024 ExpyDoc
