INSTITUTO NACIONAL DE TELECOMUNICAÇÕES
MESTRADO EM TELECOMUNICAÇÕES
OTIMIZAÇÃO CONVEXA – TP542
PROF. DR. DAYAN ADIONEL GUIMARÃES
4ª SÉRIE DE EXERCÍCIOS
ENTREGA NO DIA ____ / ____ / ____
1. Na p. 153 do livro-texto mais uma vez aparece o conceito de pseudo-inversa no contexto da
solução do problema dos mínimos quadrados (least squares). Revisite este conceito e determine
como é calculada a pseudo-inversa de uma matriz Am×n quando rank(A) = m, quando rank(A) =
n e quando A é quadrada e não-singular.
2. Seja a um vetor de variáveis aleatórias e um vetor x ∈ Rn. Mostre que a variância da variável
aleatória z = aTx vale var(z) = var(aTx) = xTΣx, onde Σ é a matriz de covariância de a, ou seja, Σ
= E(a – ā)(a – ā)T.
3. Estabeleça em que condições o problema (4.36), p. 156 do livro texto pode ser escrito sob a
forma de um problema de otimização quadrática com restrições de desigualdade quadráticas
(QCQP). Escreva o problema (4.36) sob forma de um QCQP.
4. Com referência ao problema (4.37), p. 157 do livro texto, explique de forma sucinta porque a
restrição linear robusta aiTx ≤ bi para todo ai ∈ εi pode ser expressa por sup{ aiTx | ai ∈ εi } ≤ bi.
Obs: O que se pretende conhecer aqui é a razão para se utilizar o supremo.
5. Com referência ao item Linear Programming with Random Constraints (p. 157-158), faça um
detalhamento de todos os passos que permitem que o problema
possa ser escrito sob a forma do SOCP
6. No problema (4.38), p. 157 diz-se que η deve ser maior ou igual a 0,5. Justifique esta restrição.
Dica: tal restrição tem a ver com a complexidade de solução do SOCP correspondente descrito
no exercício anterior.
7. No inicio da Subseção 4.5.4, p. 163 do livro texto, no exemplo sobre norma de Frobenius tem-se
que ỹ = DMD−1ũ. Mostre a validade desta simples igualdade.
8. Quando trata do assunto minimizing spectral radius via Perron-Frobenius theory (p. 165 do
livro texto, slide 4.34) na video-aula #6, o Prof. Boyd diz que a solução para inf{λ | Aυ ≼ λυ
para algum υ ≻ 0} = λpf na verdade levará a λpf tal que Aυ = λpf υ. Justifique esta igualdade.
9. Se você já estudou algo referente a Cadeias de Markov, faça uma pesquisa procurando
aplicações para a teoria de Perron-Frobenius (ver p. 165 do livro texto) no equilíbrio de matrizes
de probabilidade de transição (matrizes de Markov). Caso não tenha estudado Cadeias de
Markov, pesquise sobre outra aplicação da teoria de Perron-Frobenius em alguma área de seu
interesse. Registre os conhecimentos adquiridos em duas ou três páginas.
10. Ainda tomando como base a teoria de Perron-Frobenius, determine os modelos de otimização
não-convexa (GP) e convexa que descrevem o problema de estimação do máximo autovalor de
uma matriz de covariância modificada Σm em que todos os elementos são os valores absolutos
dos elementos da matriz de covariância original Σ.
11. Tomando como base a teoria sobre minimização de norma de uma matriz (matrix norm
minimization), determine o modelo de otimização convexa SDP que descreve o problema de
estimação do máximo autovalor de uma matriz de covariância modificada Σm em que todos os
elementos são os valores absolutos dos elementos da matriz de covariância original Σ.
12. Na página 168 do livro texto diz-se que se as matrizes da LMI em (4.50) forem diagonais, tal
LMI se torna equivalente a um conjunto de desigualdades lineares e, portanto, o problema
(4.50) se torna um problema de otimização linear. Justifique esta afirmativa.
13. Tomando por base os comentários no início da subseção 4.4.2, p. 156 do livro texto, justifique
porque o problema (4.36) pode ser expresso no formato de SOCP dado no início da subseção
4.6.3, p. 169 (item second-order cone programming).
14. No início da vídeo-aula #7 do Prof. Boyd ele mostra a equivalência entre os problemas SOCP e
SDP do slide 4-37. Durante sua explicação ele afirma que a matriz em bloco sob análise é
semidefinida positiva somente se o elemento da diagonal principal da matriz localizado mais à
direita for não-negativo. Justifique tal afirmação e em seguida demonstre a equivalência entre o
SOCP e o SDP em questão.
15. No contexto do Exemplo 4.9, p. 176 do livro texto, mostre que: 15(a)
E[(Fy – x)(Fy – x)T] = FFT.
se FA = I; 15(b)
16. No contexto do slide 4-39, mostre que se ||A||2 ≤ t ⇔ ATA ≼ t2I, para t ≥ 0. Dica: para facilitar,
mostre antes que λmax(A) ≤ t ⇔ A ≼ tI.
17. Exercício 4.50 do livro texto.
18. Exercício 4.54 do livro texto.
19. Estude os enunciados dos Exercícios 4.57, 4.59 e 4.62 do livro texto e em seguida tente resolvêlos ou ao menos tente indicar um possível caminho para a solução.