• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 2 fuera de 13 páginas
Examen

AA/CSE/EE/ME 578 Convex Optimization Homework 7 Solutions (Winter 2024) | Lagrange Duality, SDP Matrix Completion, QCQP, Worst-Case Probability and Processor Scheduling – Step-by-Step Solutions with MATLAB/Python Code

Document preview thumbnail
Vista previa 2 fuera de 13 páginas

INSTANT PDF DOWNLOAD. This document provides step-by-step solutions for Homework 7 in AA/CSE/EE/ME 578 Convex Optimization from Winter 2024. It covers Lagrange duality, semidefinite programming (SDP) matrix completion, quadratically constrained quadratic programming (QCQP), worst-case probability, and processor scheduling. The solutions include MATLAB and Python code to support computational problem-solving and demonstrate approaches to convex optimization problems.

Vista previa del contenido

AA/CSE/EE/ME 578 Univ. of Washington, Winter 2024

Homework 7



1. Consider the optimization problem
Σm
minimize i=1 h( Aix + bi 2) − cT x

with variable x ∈ Rn, where c ∈ Rn, Ai ∈ R3×n, bi ∈ R3, and

(u − 1)2/2, u ≥ 1
h(u) =
0, otherwise.
Derive the Lagrange dual of the equivalent problem
Σ
minimize mi=1 h( yi 2) − cT x
subject to Aix + bi − yi = 0, i = 1, . . . , m,

with variables x ∈ Rn and yi ∈ R3.
Solution. The Lagrangian is
m m
Σ Σ
L(x, y, z) = (h( yi 2) − zT y
i i) − cT x + zTi (Aix + bi).
i=1 i=1
Σm
Minimizing over x gives condition i=1 ATi zi = c. Minimizing over yi gives
inf(h( yi 2) − zT yi) = inf(h( yi 2) − zi 2 yi 2)
yi i yi
= inf (h(u) — zi 2u)
u≥0
2
= −1/2 zi 2 − zi 2.
The dual problem is
Σ
maximize Σmi=1 2
m (b zi − zi 2 /2 − zi 2)
iT
subject to i=1 AT z = c. i
i

2. Fix S ∈ S+
n and λ > 0. Consider the following optimization problem:

Σ
maximize log det X − Tr(SX) − λ i,j tij
subject to |Xij| ≤ tij,

where the domain of log det is Sn++ . Show that if the optimal solution is a block diagonal
matrix, then |Sij| ≤ λ whenever the (i, i) entry and the (j, j) entry are in two different
blocks.
(Note that you should solve this without using subgradients (which we have not covered in
our course). This is a very useful result in learning Gaussian graphical models in statistics,
used as a “screening test”.)
1

, Solution. Rewrite the problem as:
Σ
maximize log det X − Tr(SX) − λ i,j ti,j
subject to −ti,j ≤ Xi,j ≤ ti,j

The Lagrangian L : Sn++ × Rn×n × Rn×n '→ R is:

Σ Σ
L(X, η, γ) = log det X − Tr(SX) + ti,j(−λ + ηi,j + γi,j) + Xi,j(−ηi,j + γi,j)
i,j i,j


Since the problem is strictly feasible, by KKT, if X is an optimal solution, there exists (η, γ)
such that:


X −1 + S + η − γ = 0
T
−λ11 + η + γ = 0
−ti,j ≤ Xi,j ≤ ti,j
ηi,j ≥ 0, γi,j ≥ 0
ηi,j(Xi,j − ti,j) = 0, γi,j(Xi,j + ti,j) = 0

Since ηi,j ≥ 0, γi,j ≥ 0 and ηi,j + γi,j = λ, we have |ηi,j − γi,j| ≤ λ. If i and j belong to
different blocks then Xi,j = Xi,j−1 = 0. That implies |Si,j| = |γi,j − ηi,j| ≤ λ.

3. Minimum norm positive semidefinite matrix completion. Given some entries of a matrix, we
want to find a “completion” for it such that the completed matrix is positive semidefinite,
and has the smallest possible matrix norm (maximum singular value).
(a) Express this problem as an SDP. (b) Using CVX find the smallest norm PSD completion
for the following matrix:

50 6 ? 4 ?
6 ? ? ? −15
A= ? ? 46 ? 17
4 ? ? ? −13
? −15 17 −13 70

Solution.

(a) Note that for a matrix X ∈ Sn+, the spectral norm of X is equal to the largest eigenvalue
of X, X = λmax(X). To complete the X with the smallest spectral norm, we
formulate the following problem,

minimize X
subject to X ⪰ 0
Xij = Aij, ij ∈ Ω



2

Información del documento

Subido en
13 de noviembre de 2026
Número de páginas
13
Escrito en
2026/2027
Tipo
Examen
Contiene
Preguntas y respuestas
$22.99

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
Stuviahero01
3.9
(47)
Vendido
269
Seguidores
9
Artículos
7103
Última venta
2 días hace




Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes