Um Algoritmo de Ponto Proximal para Programação Semidefinida
Autores
|
4232 |
303,668
|
|
|
4233 |
303,668
|
Informações:
Publicações do PESC
Neste Trabalho, estamos apresentando uma proposta algorítmica para Programação Semidefinida (PSD). Esta aparenta ser a primeira na classe de métodos de ponto proximal, entre os algoritmos que transformam Programação Semidefinida em Programação Não-linear no ortante positivo do espaço euclidiano de dimensão n. Isso representa uma redução significativa no número de variáveis do problema original (um (PSD), em geral, possui dimensão n(n+1) / 2 ). A proposta é implementável e a iteração principal do algoritmo de ponto proximal conceitual é substituída por uma sucessão de problemas Não-lineares em Rn. Estamos motivados por resultados de convergência do algoritmo proximal clássico estendido a Variedades Riemannianas com curvatura seccional não-positiva. Um importante exemplo de tal variedade é o espaço de matrizes simétricas definidas positivas, onde a métrica é dada pela hessiana da barreira padrão - ln det(X). Portanto, observando que o método proximal clássico não depende das geodésicas deste espaço, aplicamos estas idéias para desenvolver um algoritmo de ponto proximal para (PSD).
In this work, we propose a new (proximal) algorithm for Semidefinite Programming (SDP). It appears to be the first in the proximal class on the set of methods that convert Semidefinite Programming in Nonlinear Programming. It is implementable, and each main iteration of the conceptual proximal point algorithm is replaced by a sequence of non-linear programming problems in the positive octant of the real vector space Rn. We are motivated by results of the classical proximal algorithm extended to Riemannian manifolds with non positive sectional curvature. An important example of such manifold is the space of symmetric definite matrices, where the metrics is given by the Hessian of the standard barrier function ¡ln det(X). Then, observing the obvious fact that proximal algorithms do not depend on the geodesics, we apply those ideas to develop a proximal point algorithm for (SDP).