Description
1. (50 pts) Robust quadratic programming. In the lecture, we have learned about robust
linear programming as an application of second-order cone programming. Now we will
consider a similar robust variation of the convex quadratic program
minimize (1/2)x
T P x + q
T x + r
subject to Ax ⪯ b.
For simplicity, we assume that only the matrix P is subject to errors, and the other parameters (q, r, A, b) are exactly known. The robust quadratic program is defined as
minimize supP ∈E
(1/2)x
T P x + q
T x + r
subject to Ax ≺ b
where E is the set of possible matrices P.
For each of the following sets E, express the robust QP as a convex problem in a standard
form (e.g., QP, QCQP, SOCP, SDP).
(a) A finite set of matrices: E = {P1, …, PK}, where Pi ∈ S
n
+, i = 1, …, K.
(b) A set specified by a nominal value P0 ∈ S
n
+ plus a bound on the eigenvalues of the
deviation P − P0:
E = {P ∈ S
n
| −γI ⪯ P − P0 ⪯ γI}
where γ ∈ R and P0 ∈ S
n
+.
(c) An ellipsoid of matrices:
E =
(
P0 +
X
K
i=1
Piui
| ∥u∥2 ≤ 1
)
.
You can assume Pi ∈ S
n
+, i = 0, . . . , K.
2. (50 pts) Water-filling. Please consider the convex optimization problem and calculate its
solution
minimize −
Pn
i=1 log (αi + xi)
subject to x ⪰ 0, 1
T x = 1,
