INSTITUTO NACIONAL DE TELECOMUNICAÇÕES
MESTRADO EM TELECOMUNICAÇÕES
OTIMIZAÇÃO CONVEXA – TP542
PROF. DR. DAYAN ADIONEL GUIMARÃES
5ª SÉRIE DE EXERCÍCIOS
ENTREGA NO DIA ____ / ____ / ____
1. Justifique porque a função dual de Lagrange é sempre côncava, independente do problema de
otimização original ser ou não ser convexo.
2. Com relação ao problema two-way partitioning, p. 219 do livro texto, escreva xTWx como um
somatório onde fiquem explícitos os elementos da matriz W, ou seja Wij. Procure fornecer uma
interpretação para tais elementos.
3. Ainda com relação ao problema two-way partitioning, justifique a passagem matemática:


inf  xTWx + ∑ υi ( xi2 − 1) = inf xT [W + diag (υ )]x − 1T υ
x
x
i


{
4. Usando o Matlab ou o Mathcad, construa matrizes A
T
0eB
}
0 de ordem 2 e plote as funções
T
x Ax e x Bx. Altere as matrizes A e B de forma que não sejam mais semidefinidas positivas,
observe ou infira sobre o mínimo das correspondentes funções e comente sobre suas
observações no que diz respeito aos valores dos mínimos e suas relações com o fato das
matrizes serem ou não serem semidefinidas positivas.
5. Com relação ao problema dual de Lagrange do problema LP na forma de desigualdade (veja p.
225 do livro texto), mostre que
 −bT λ , AT λ + c = 0
inf cT x + λ T ( Ax − b) = 
x
 −∞ , em caso contrário.
6. Com relação ao Slide 5-13, mostre os detalhes da igualdade
g (λ ) = − 14 λ T AP −1 AT λ − bT λ
7. Uma maneira interessante de entender a primeira expressão da Subseção 5.5.1, p. 241 é através
de uma figura contendo uma função convexa qualquer e os valores de f0(x) para um valor de x
qualquer, p⋆, g(λ, υ), x, x⋆, (f0(x) – p⋆) e [f0(x) – g(λ, υ)]. Faça um esboço de uma figura como
esta para x ∈ R.
8. O Exemplo 5.2, p. 245 do livro texto, tem grande aplicação em telecomunicações. Basicamente,
ele procura encontrar a distribuição ótima de potência de transmissão em um conjunto de canais,
cada um sujeito a uma determinada relação sinal-ruído, de forma que seja atingida a máxima
taxa de transmissão total (chamada de capacidade), sujeito a uma restrição de potência total
máxima. Este problema se aplica, por exemplo, na alocação de potência nos sub-canais de
modems com tecnologia ADSL que operam com múltiplas portadoras. No livro Digital
Transmission do Prof. Dayan, na subseção 8.1.7.3, p. 719, aborda-se justamente este problema,
porém com uma notação mais apropriada ao contexto de sistemas de comunicação, diferente
daquela utilizada pelo Prof. Boyd no Exemplo 5.2. Lá o problema de otimização pode ser
escrito da seguinte maneira:
U

P 
maximize − ∑ log 2  1 + u2 
u =1
 σu 
T
sujeito a P 0, 1 P = PT
onde U é o número de canais; P = (P1, P2, ..., PU) representa a variável do problema e é o vetor
com os valores de potência alocada em cada canal; σu2 é a variância de ruído no u-ésimo canal e
PT é a potência total de transmissão. Utilizando o Exemplo 5.2 do Prof. Boyd como referência,
resolva analiticamente o problema de otimização acima descrito e interprete-o à luz do conceito
de water-filling. Implemente o código CVX para o problema. Entregue a sua solução para o
professor.
9. Exercício 5.1 do livro texto.
10. Exercício 5.5 do livro texto.
11. Estude com bastante atenção o enunciado do Exercício 5.13 do livro texto. Muitos problemas de
otimização não convexa podem ser convertidos em problemas convexos usando algum tipo de
relaxação (relaxation) nas restrições. Neste exercício os elementos de x só podem ter os valores
0 e 1, o que torna o problema não convexo. Na verdade trata-se de um problema de otimização
inteira (integer programming), outro grande ramo da otimização matemática. Mas o problema
pode ser transformado em um problema de otimização convexa através da relaxação desta
restrição para x. Se tiver oportunidade, procure ler um pouco mais sobre esta técnica, pois ela é
de fato muito útil do ponto de vista prático (estude o artigo “Integer Programming - Lagrangian
Relaxation.pdf” disponibilizado na pasta da disciplina na Internet).
12. Exercício 5.21 do livro texto.
13. Exercício 5.26(a) e 5.26(b) do livro texto.
14. Exercício 5.27 do livro texto.
15. Exercício 5.28 do livro texto. Dica: verifique as condições KKT.
============================== FIM =====================================