Trajetória Central e Método do Ponto Proximal em Otimização
Semidefinida
João Xavier da Cruz Neto,
Depto. de Matemática - DM, CCN, UFPI,
E-mail: [email protected],
Paulo Roberto Oliveira,
Orizon Pereira Ferreira,
Instituto de Matemática e Estatı́stica - IME, UFG,
[email protected],
Roberto Cristóvão Mesquita Silva∗
Programa de Engenharia de Sistemas e Computação - COPPE/UFRJ,
E-mail: [email protected],
Seja o problema de programação semidefinida
(P )
min{C • X : AX = b, X 0}
e seu dual associado
(D)
max{bT y : A∗ y + S = C, S 0}
[email protected].
3) trajetória de ponto proximal
Xk+1 = argminx∈S n {hC, Xi + λk Df (X, Xk ) : AX = b}
+
onde Df :
n
S+
n
→ IR,
× S++
Df (X, Y ) = f (X) − f (Y ) − hf 0 (Y ), X − Y i
onde C ∈ S n , b ∈ IRm , X ∈ S n ( variável primal), é a distância generalizada com respeito à barreira
(S, y) ∈ S n × IRm (variáveis duais) e a aplicação considerada.
linear A : S n → IRm , é dada por
Usando alguns elementos da geometria Riemmanniana provamos que a trajetória central primal é
T
AX = (hA1 , Xi, ..., hAm , Xi) .
limitada. Sob algumas condições mostramos que as
m
∗
O operador adjunto de A é dado por A : IR → três trajetórias coincidem. Provamos também que
todo ponto limite da trajetória central é solução do
Sn;
m
problema original (P ). Estamos estudando a conX
A∗ v =
vi Ai , v ∈ IRm .
vergência da trajetória central primal com respeito
i=1
à barreira f (X) = tr(Xln(X)).
S n - espaço das matrizes simétricas de ordem n.
n
- cone das matrizes simétricas semidefinidas posS+
Referências
itivas.
n
n
S++ - interior de S+ , é o cone das matrizes
[1] M. Doljansky and M. Teboule, An Interior
simétricas definidas positivas.
Proximal Algorithm and the Exponencial MulProduto Interno em S n
tiplier Method for Semidefinite Programming,
SIAM J. Optim. Vol 9, No. 1, pp. 1-13 (1998).
hA, Bi = tr(AB).
Neste trabalho consideramos as funções barreiras
n
f : S++
→ IR, dadas por f (X) = tr(Xln(X)) [1]
e f (X) = −ln det(X), e estudamos três trajetórias
relacionadas ao problema (P ):
1) trajetória central
X(t) = argminX {thC, Xi+f (X) : AX = b}, t ∈ IR+ ;
2) trajetória de Cauchy com respeito à barreira
f : é a curva Z : [0, β) → F 0 (P ) dada por
0
Z (t) = −grad φ| S (Z(t)),
Z(0) = Z0 ,
para um ponto inicial Z0 dado, algum β > 0 e φ ∈
F 0 (P ), onde F 0 (P ) = {X ∈ S n : AX = b, X ∈
n
S++
};
∗ Bolsista
PICDT/UFAM-CAPES
[2] A.N. Iusem, R.D.C. Monteriro (2000). On dual
convergence of the generalized proximal point
method with Bregman distance. Mathematics
of Operations Research 25 606-624.
[3] A.N. Iusem, B.F. Svaiter , J.X. Cruz
Neto(1999).Generalized proximal point methods and Cauchy trajectories in Riemannian
manifolds. SIAM Journal on Control and Optimization 37 566-588.