A pesquisa Operacional e os Recursos Renováveis4 a 7 de novembro de 2003, Natal-RN

RELAXAÇÃO LAGRANGEANA, PROGRAMAÇÃO SEMIDEFINIDA E APLICAÇÕES À

COMBINATÓRIA

Paulo Roberto Oliveira, Professor titular poliveir@cos.ufrj.br Colaboradores Ronaldo Gregório, Mestrando rgregor@cos.ufrj.br Sérgio Assunção Monteiro, Doutorando pastor@cos.ufrj.br Programa de Engenharia de Sistemas e Computação COPPE Universidade Federal do Rio de Janeiro Mini-curso apresentado no XXXV Simpósio Brasileiro de Pesquisa Operacional SOBRAPO UFRN 4 a 7 de novembro de 2003

2840

INTRODUÇÃO

A programação semidefinida é um capítulo da otimização convexa em que os objetos são matrizes simétricas, no lugar dos usuais vetores de dimensão finita. Problemas deste tipo são conhecidos há mais de um século, entretanto apenas nos últimos dez anos têm merecido a atenção de muitos pesquisadores. Hoje há cerca de 1000 referências, a maior parte de data posterior a 1990. As principais motivações para este crescimento estão em dois elementos. Um é a variedade de aplicações, isto é, problemas que, através de transformações adequadas, produzem um problema de programação semidefinida. A lista inclui a obtenção de cotas, em geral melhores do que as tradicionalmente conhecidas, para diversos problemas de otimização combinatória (“hard”), verificação de estabilidade em inclusões diferenciais, em problemas de controle e teoria de sistemas, e otimização estrutural. Uma das técnicas mais úteis e eficientes na obtenção de modelos de programação semidefinida, em particular os provenientes da combinatória é a relaxação lagrangeana. Ela é conhecida por seu uso na obtenção de cotas em problemas de programação inteira, assim como na decomposição de problemas de grande porte, contínuos e inteiros. Em nosso texto, introduziremos aquela técnica como um instrumento para a obtenção de modelo de programação semidefinida. Embora a extensão do texto nos limite a um exemplo, o problema do corte máximo, as referências bibliográficas permitirão que o leitor interessado possa avaliar outros casos. O outro elemento é a descoberta de várias famílias de algoritmos para a programação semidefinida, cujo desenvolvimento chegou hoje ao estágio em que problemas de grande porte, sobretudo os advindos da combinatória, podem ser resolvidos eficientemente. Antecipando nossa apresentação, veremos que há duas classes principais de métodos. Os primeiros, de pontos interiores, tinham seus fundamentos pré-estabelecidos nos trabalhos de Nesterov and Nemirovski, que desenvolveram a teoria de métodos polinomiais para a programação convexa (a programação semidefinida está aí incluída), através da utilização do conceito, por eles criado, de funções autoconcordantes. Isto permitiu que os algoritmos de pontos interiores, largamente utilizados na programação linear e não-linear, fossem estendidos à programação semidefinida, produzindo uma variedade de métodos polinomiais. A segunda classe é de natureza bem diversa: através de determinadas transformações aplicadas ao problema original, é gerado um problema de programação não-linear, que é então resolvido por técnicas tradicionais daquela área da otimização. Nosso texto é, em sua maior parte, introdutório. O primeiro capítulo, motivado pelo problema do corte máximo, trata da técnica de relaxação lagrangeana. O pré-requisito é um conhecimento mínimo de programação não-linear. Segue-se uma introdução à programação semidefinida, que repete idéias comuns a um curso de programação linear ou não-linear (dualidade fraca, dualidade forte, condições de otimalidade de Karush-Kuhn-Tucker). Ao fim deste capítulo, retornamos ao problema de corte máximo, obtendo uma nova formulação de programação semidefinida, a partir de uma operação de dualização. O terceiro capítulo trata de algoritmos de pontos interiores, extensões dos obtidos para a programação linear. Nele, incluímos um trabalho em andamento, um algoritmo dual de centros, com alguns resultados computacionais para alguns problemas de corte máximo. As idéias principais dos métodos tratados serão mais bem compreendidas por aqueles que possuam alguma base em algoritmos de pontos interiores para a programação linear. No quarto capítulo descrevemos, sucintamente, três grupos de algoritmos, derivados da abordagem da programação não-linear. O terceiro é uma contribuição dos autores, um algoritmo proximal, que é também um trabalho em andamento. O quinto capítulo apresenta referências para outras aplicações e softwares disponíveis. Finalmente, para facilitar a leitura, adicionamos um apêndice com os resultados da álgebra linear que foram utilizados no texto.

2841

ÍNDICE INTRODUÇÃO

2

Capítulo 1 – INTRODUÇÃO À RELAXAÇÃO LAGRANGEANA 5 1.1 O problema de corte máximo (“max-cut”) e sua versão contínua

5

1.2 Relaxação lagrangeana

6

1.2.1 Função de Lagrange ou lagrangeana

6

1.2.2 Problema dual

6

1.3. Aplicação da relaxação lagrangeana ao problema de corte máximo

7

1.3.1 Relaxação quadrática do problema de corte máximo

7

1.3.2 Relaxação por programação semidefinida do problema de corte máximo 8 Capítulo 2 - ELEMENTOS DE PROGRAMAÇÃO SEMIDEFINIDA

9

2.1. O problema dual

9

2.1.1 Salto de dualidade e teorema de dualidade forte

9

2.2. Condições de otimalidade

11

2.2.1 Dualização do modelo de corte máximo

11

Capítulo 3 - MÉTODOS EM nS +

13

3.1 Introdução

13

3.2 Métodos seguidores de trajetória

15

3.2.1 Família de Monteiro-Zhang

16

3.2.2 Um algoritmo dual de centros [Monteiro and Oliveira, 2003]

18

3.3 Métodos de redução de potencial

20

Capítulo 4 - MÉTODOS DA PROGRAMAÇÃO NÃO-LINEAR

21

4.1 Método de feixes espectral

21

4.2 Métodos de fatorização

22

4.3 Método de fatorização - ponto proximal [Gregório and Oliveira, 2003] 22

2842

4.3.1 Algoritmo de ponto proximal em nS+

23

4.3.2 Algoritmo de ponto proximal em nR+ 24 4.3.3 Aplicação à PSD

26

Capítulo 5 - OBSERVAÇÕES FINAIS

28

APÊNDICE 29 Referências Bibliográficas

31

2843

Capítulo 1

INTRODUÇÃO À RELAXAÇÃO LAGRANGEANA A relaxação lagrangeana é uma técnica extensamente utilizada na programação matemática contínua e discreta. É bem conhecida sua aplicação na obtenção de cotas inferiores, no caso de problemas primais de minimização, assim como na decomposição de problemas de grande porte. Neste capítulo, introduzimos a citada técnica, procurando motivar sua aplicação à programação semidefinida através do problema de corte máximo. 1.1 O problema de corte máximo (“max-cut”) e sua versão contínua Seja G=(V,E) um grafo não-orientado com conjunto de vértices V e de arestas E, onde as cardinalidades são |V|=n e |E|=m. Uma aresta com nós i e j é representada por (i,j). Assumimos que os grafos não possuem laços, ou seja, Eii ∉),( para qualquer Vi∈ . Dado VS ⊆ , o subgrafo G[S] induzido por S possui o conjunto de arestas SjiEji ∈∈ ,|),( . Denotamos por )(Sδ o conjunto SjSiEji ∉∈∈ ,:, , o corte determinado por S. Dado um vetor não-negativo ( ) ( )GE

ij Rpp +∈= ,

associamos ao corte o peso ( ) ∑ ∈=

)(,:)(

Sji ijpSpδ

δ . Admitimos que o grafo é completo (cada nó é

adjacente a todos os outros), representando esta propriedade através dos pesos por 0, =jip , para todas as arestas inexistentes, e pi,i = 0, para todo i. O problema é encontrar o corte de maior peso. Trata-se de um problema NP difícil, para o qual há algoritmos, heurísticas, e aleatórios, veja Poljac and Tuza, 1995, para uma revisão; mais recentemente, a metodologia da relaxação por programação semidefinida, Goemans and Williamson, 1995, permitiu uma melhoria significativa nas cotas obtidas. Com a finalidade de obter um modelo de programação matemática para o problema de corte máximo, usamos a variável x ∈ Rn, com ,1=ix se Si∈ , e 1−=ix , no caso contrário. Decorre, facilmente, que 1−=ji xx , exclusivamente quando ( )Sji δ∈, , valendo +1 em caso contrário. Seja, agora a matriz simétrica W, definida da seguinte maneira:

∑−=≠=j ijiiijij pwjipw 4/ e para ,4/ , para todo i.

Então

( )( ) ( ) ( ) WxxxxpxxpSp t

i jjiij

j jijiij −=−=−= ∑∑∑∑

<

1411

21δ .

Decorre o problema de corte máximo, expresso por

( ) nixWxxP i

txcm ,...,1 ,1,1:min =−∈

É fácil ver que (Pcm) é equivalente ao seguinte problema contínuo:

( ) nixWxxP it

xcmc ,...,1 ,1:min 2 == Temos assim um problema quadrático-quadrático, claramente não-convexo. É evidente que a transformação que acabamos de realizar não altera o grau de dificuldade em relação ao problema original. Entretanto este último, (Pcmc), permite abordagens da otimização contínua. Forneceremos

2844

duas, ambas baseadas na técnica de relaxação lagrangeana, que descreveremos, sucintamente a na próxima seção. 1.2 Relaxação lagrangeana Limitamo-nos aos problemas de minimização com restrições de igualdade, visto ser este o caso em que se enquadra (Pcmc). Seja o problema, denominado primal

( ) ( ) ( ) ni RUxmixhxfP ⊆∈== ,,...,1,0:min

Em (P), U é um conjunto suposto não-vazio, f: U → R é a função custo ou objetivo, e hi: U → R, i=1,...,m são as funções de restrição. A hipótese abaixo garante a resolubilidade de (P): Hipótese 1.1:

Todas as funções envolvidas são finitas em U, e o conjunto primal viável V:=x∈U: hi(x)=0 ≠∅ 1.2.1 Função de Lagrange ou lagrangeana Denotando por h(x)=(h1(x),..., hm(x)) ∈ Rm, e para y ∈ Rm, o produto escalar em Rm, por yth=∑i=1,...,myihi, a lagrangeana é a função

L: Rn x Rm → R, definida por L(x, y) = f(x) + yth(x), y ∈ Rm, x ∈ U.

A idéia de relaxar (P) se traduz pelo seguinte: em lugar da resolução do problema (difícil) (P), propomos, para cada y ∈ Rm, o problema relaxado

(Pr) ϕ(y) = inf L(x,y), x ∈ U.

ϕ é denominada função dual, e y é a variável dual ou multiplicador de Lagrange. Sobre (Pr), notamos que:

i.se U = Rn, temos a função de Lagrange tradicional, em que todas as restrições são levadas em conta; ii. yth(x) pode ser interpretado como um termo de penalização: caso alguma restrição hi seja violada em um ponto x, tem-se um custo yihi(x) a pagar, desde que yi ≠ 0. iii. a validade prática da relaxação está em que a resolução de (Pr) deve ser significativamente mais simples do que a de (P); isto tem a ver com a escolha do que é U face ao conjunto das demais restrições, aqui representadas por x ∈ Rn: h(x) = 0. iv. a resolubilidade de (P) não implica na de (Pr), a qual deve ser verificada em cada aplicação.

1.2.2 Problema dual Passamos agora à determinação do multiplicador y. Claramente, o ideal é obter y tal que ϕ(y) = inf

f(x) + yth(x), x ∈ U = f(x(y)) + yth(x(y)), onde x(y), simultaneamente, resolve (Pr) e (P). Em geral, isto não é possível, e um passo no sentido de caracterizar y é dado pelo chamado teorema da dualidade fraca, que mostramos a seguir:

Teorema 1.2. (Dualidade fraca) Para todo y ∈ Rm e todo z primal viável (z ∈ V, definido na hipótese acima), ϕ(y) ≤ f(z). Em particular, ϕ(y) é um minorante do valor ótimo de (P). DEMONSTRAÇÃO: ϕ(y) = inf f(x) + yth(x), x ∈ U ≤ f(z) + yth(z) ≤ f( z). Além do uso imediato deste teorema na obtenção de minorantes para o valor de (P), ele sugere que y deva ser tal que ϕ(y) seja o maior possível, o que leva à definição natural do problema dual:

2845

( ) ( ) nRyyD ∈:sup ϕ Salto de dualidade (‘duality gap”)

A diferença entre os valores ótimos primal e dual, quando não-nulo é o chamado salto de

dualidade:

inf f(x): h(x) = 0, x ∈ U - sup ϕ(y), y ∈ Rm . Devido ao teorema da dualidade fraca, este valor é sempre não-negativo. Sua estrita positividade implica na inexistência de x primal tal que o problema relaxado (Pr) seja solúvel para algum y. Em particular, problemas convexos (em que f é convexo, U é convexo e h é afim), entre os quais a PL, são a família típica em que os custos primal e dual podem ser idênticos (salto nulo). A função dual e, por conseqüência, o problema dual, possui uma forte propriedade, que demonstra o caráter regularizador da relaxação lagrangeana, conforme se vê a seguir:

Teorema 1.3. A função dual ϕ é côncava. DEMONSTRAÇÃO: sejam y1 e y2 em Rm, e, para 0 ≤ s ≤ 1, um ponto do segmento que une y1 a y2, dado por y = s y1 + (1-s)y2. Temos ϕ(y) = inf f(x) + yth(x), x ∈ U = f(z) + yth(z), onde z = x(y) é solução de (P)r. Agora, dada a definição de ϕ, obtemos ϕ(y1) ≤ f(z) + y1

t h(z) e, analogamente, ϕ(y2) ≤ f(z) + y2

t h(z). Multiplique a primeira desigualdade por s, e a segunda por 1-s, e some, para chegar ao resultado desejado:

sϕ(y1) + (1-s) ϕ(y2) ≤ f(z) + [sy1 + (1-s)y2] h(z)

= f(z) + yth(z) = ϕ(y).

Deste modo, o problema dual é côncavo, independentemente de propriedades de convexidade ou diferenciabilidade das funções envolvidas, e do conjunto U, que em particular, pode ser discreto. Por outro lado, ϕ não é, em geral, diferenciável, o que exige, para a solução de (D), técnicas apropriadas. 1.3. Aplicação da relaxação lagrangeana ao problema de corte máximo

A título de exemplificação, empregaremos, inicialmente, a técnica da relaxação lagrangeana ao

problema (Pcmc), obtendo um problema não-linear quadrático irrestrito. Nosso objetivo é verificar que esta abordagem leva a dificuldades técnicas que não existirão no caso da programação semidefinida. 1.3.1 Relaxação quadrática do problema de corte máximo

Defina a função de Lagrange: ( ) ( )∑ =

−+=n

i iit xyWxxyxL

12 .1, . Observe que nRU = . Temos,

então, a função dual dada por ( ) ( )yxLynRx

cm ,min∈

=ϕ . Sendo este um problema irrestrito, sabe-se que

uma condição necessária para um ponto de mínimo de ϕ é que o gradiente de L, em relação a x seja nulo, isto é, ( ) 0=+ iii xyWx , para cada ni ,...,1= . Em notação matricial, escreve-se ( ) 0=+ xYW , onde ( )nyyY ,....,diag 1= é a matriz diagonal cujos elementos diagonais são as coordenadas do vetor y. É claro que este sistema só terá solução se W+Y for uma matriz singular, isto é, se tiver algum auto-valor nulo (Ap). Fica evidente a dificuldade de se garantir esta hipótese, que, sendo W um dado do problema, atua de fato sobre o vetor y. Ainda que se assuma, teremos uma infinidade de soluções, gerando a necessidade de uma análise das que minimizam L.

2846

1.3.2 Relaxação por programação semidefinida do problema de corte máximo Com a notação acima para a função de Lagrange, temos ainda a função dual dada por ( ) ( )xYWxyey t

Rx

tcm n

++−=∈

minϕ . Como W+Y é simétrica, a única possibilidade de que este

problema de minimização tenha solução finita é que W+Y seja semidefinida positiva (Ap), isto é, seu menor autovalor é nulo. Denotaremos, a partir de agora, por Sn , o conjunto das matrizes simétricas

nn× , e, por nS+ o subconjunto das semidefinidas positivas (Ap). Usaremos, indistintamente, nSB +∈ , ou 0≥B (o contexto deixará claro quando se tratar de escalares ou vetores não-negativos).

Temos, por conseguinte, por definição, que ( ) 0≥+ xYWxt , para qualquer nRx∈ , sendo 0 valor mínimo desta última expressão. Logo ( ) yey t

cm −=ϕ , desde que 0≥+YW . Em conseqüência, o problema dual se escreve:

( ) ( ) yYYWyeD t

ycm diag ,0:max =≥+− Temos, neste exemplo, o que caracteriza um problema de PSD: os dados, e, na função custo, e W, nas restrições, são matrizes simétricas, enquanto a restrição é uma condição de semidefinição positiva. Ressalvamos que esta não é a formulação de Goemans and Williamsom, que será obtida no próximo capítulo, após fornecermos elementos da teoria da PSD. Entretanto, a fim de compararmos com a relaxação obtida na seção anterior, o resultado abaixo é expressivo por mostrar o caráter regularizador da transformação:

Proposição 1.4.[Lemaréchal and Oustry, [99]](resolubilidade de (Dcm)) O conjunto viável

( ) 0:diag ≥+= YWyY é não-vazio, e (Dcm) possui um conjunto compacto de soluções ótimas.

2847

Capítulo 2

ELEMENTOS DE PROGRAMAÇÃO SEMIDEFINIDA

Necessitamos da definição de produto escalar no espaço de matrizes. Sejam A e B duas matrizes quadradas nn× ; o produto escalar define-se por ( ) ∑ ∑= =

==•n

i

n

j ijijt baBABA

1 1tr , onde tr(C)

representa o traço da matriz C, dado por ( ) ∑ ==

n

i iiCCtr1

. Este nada mais é do que o produto escalar

usual em espaços de dimensão finita quando se reescreve cada matriz como um vetor de 2nR , com as

colunas se sucedendo umas às outras. A forma padrão do problema de programação semidefinida é como se segue:

( ) 0 ,,...,1 ,:min ≥==•• XmibXAXCPSD ii

onde X,C, e Ai são matrizes quadradas reais e simétricas, e a matriz incógnita X é, além disto, semidefinida positiva (X ≥ 0). Como em qualquer problema de otimização contínua, estamos naturalmente interessados em obter condições de otimalidade e o problema dual, entre outros, de modo a termos condições de estabelecer algoritmos adequados. Dado o caráter elementar deste texto, evitaremos todas as demonstrações que ultrapassem aquele objetivo. Observamos que o (PSD) pode ser comparado com um problema de programação linear na forma padrão, em que o cone das matrizes simétricas semidefinidas positivas corresponde ao ortante positivo. Pode-se, aliás, ver a programação linear como um caso particular da PSD, em que X,C, e Ai são expressos na forma diagonal. Entretanto, é essencial que se tenha em mente o caráter não-linear, mais precisamente convexo, da PSD. Esta propriedade se verifica facilmente. A função custo é linear, portanto convexa. Da mesma forma, as restrições de igualdade são também lineares. Já as restrições de desigualdade verificam a propriedade de convexidade (temos, na verdade, um cone convexo): ( ) 01 ≥−+ ZttX , se

10 para ,0, ≤≤≥ tZX . 2.1. O problema dual Aproveitaremos a técnica mostrada no capítulo anterior para a obtenção do dual do problema de PSD. Para isto, defina a função de Lagrange

( ) ( ) mm

i iii RyXXAbyXCyXL ∈≥•−+•= ∑ = ,0 ,,

1 .

É óbvio que, com a notação do capítulo anterior, temos 0: ≥= XXU . Conseqüentemente, a

função dual resulta em ( ) ( ) XAyCbyy m

i iiXt •−+= ∑ =≥ 10minϕ , onde b é o vetor de componentes

bi. Como X ≥ 0, verifica-se que este problema de minimização (compare com a PL), só fornecerá resultado finito (nulo) se a matriz coeficiente também for semidefinida positiva (Ap). Temos, por conseguinte, o problema dual dado por:

( ) 0 ,y:maxm

1ii,

≥=+∑=

SCSAybPSD it

Syd

2.1.1 Salto de dualidade e teorema de dualidade forte Obteremos a seguir o teorema da dualidade fraca. Considere a diferença entre os custos primal e dual, supondo que as variáveis primal X, e duais y e S, são respectivamente, primal e dual viáveis. Temos, então,

2848

XSXAyXCybXCbyXCm

iii

m

iii

t •=•−•=−•=−• ∑∑== 11

Teorema 2.1. (dualidade fraca) Suponha que ambos os problemas primal e dual possuam soluções viáveis. Então os valores das funções objetivo verificam ( ) ( )dPSDvPSDv ≥ , sendo XS • a diferença. Mais uma vez, é interessante verificar a similaridade com a PL. A diferença entre os custos primal e dual é, aqui também, a expressão da complementaridade: XS • é o produto escalar das matrizes S e X, que, como já vimos, pode ser considerado como o produto escalar em

2nR , com a semidefinição positiva na PSD associada à não-negatividade dos vetores na PL. Um outro ponto de semelhança é a necessidade de um lema do tipo Farkas, para obter o teorema da dualidade forte. Lema 2.2 (Farkas) Sejam Ei, i = 1,...,m, e B matrizes simétricas nn× dadas. O sistema

01∑=

>−m

i ii BEy não tem solução y=(y1,...,ym) se e somente se existe uma matriz simétrica Z não-

nula tal que 0 Z,0B ,,...,1 ,0 ≥≥•==• ZmiZEi . Demonstração: veja, e.g. Alizadeh, 1995. Teorema 2.3 (dualidade forte) Se o problema dual (resp.primal) tiver uma solução estritamente viável (tal que S > 0) (resp. X > 0), então o ótimo primal (resp.dual) é atingido, e v(PSD) = v(PSDd) . Em particular se ambos os problemas tiverem soluções estritamente viáveis, então o supremo e o ínfimo, respectivamente das funções primal e dual, são atingidos. DEMONSTRAÇÃO: mostraremos apenas para o primeiro caso. Considere o sistema em nRy∈ ,

dado por ( ) ∑∑ ==≤−>

m

1i10y , CAPSDvyb ii

m

i dii . Devido à definição do problema dual, este

sistema não possui solução. A fim de utilizarmos o lema de Farkas, reescrevemos estas desigualdades através da seguinte notação, para i = 1,...,m:

( )

−

=

−

=C

SPDvB

Ab

E d

i

ii 0

0 ,

00

Então o sistema 0

1∑=>−

m

i ii BEy não tem solução y. De acordo com o lema de Farkas, isto implica

na existência de uma matriz semidefinida positiva não-nula tal que

0 Z,0B ,,...,1 ,0 ≥≥•==• ZmiZEi .

Para retornarmos à notação inicial, escreva

=

Xuu

Ztα

obtendo ( ) 0 ,,...,1 ,0 ≥•−==•− XCSDPvmiXAb dii αα . Mostraremos agora que 0≠α . Por absurdo, suponha que 0=α . Como Z é semidefinida e não-nula, deve-se ter u = 0, e, portanto

0≠X . Teríamos, em conseqüência, 0 ,,...,1,0 ≥•−=−== XCmiXAZE ii , e, pelo lema de

Farkas, inexiste solução para o sistema 01∑=

>+−m

i ii CAy , o que é falso, devido à hipótese de

2849

existência de uma solução dual estritamente viável. Logo, 0≠α , de fato positivo. Como o sistema é homogêneo, podemos definir 1=α . Temos, finalmente,

( )dii SDPvXCmibXAX ≤•==•≥ ,,...,1 , ,0 ,

isto é, X é primal viável, e o custo correspondente é inferior ao do dual. O uso do teorema da dualidade fraca completa a demonstração. Observação: A condição do tipo Slater, de existência de uma solução estritamente viável, é comum em problemas de programação não-linear. Deveríamos, portanto, admiti-la como natural, por ser, como vimos acima, a programação semidefinida um problema convexo (não-linear). 2.2. Condições de otimalidade Como conseqüência dos teoremas 2.1 e 2.3, e do fato que XSSX =•=0 , (Ap), mostra-se que Corolário 2.4. Sejam X e (y, S) soluções viáveis dos problemas primal e dual, respectivamente. Então v(PSD) = v(PSDd), e ambos são soluções ótimas se e somente se 0==• XSSX .

Passemos às condições de otimalidade. Facilita a apresentação a introdução da notação seguinte: seja o operador aplicado ao conjunto das matrizes simétricas:

mn RS →:A , definido por ( ) miSXXAX n

ii ,...,1 , ,: =∈•=A . Neste caso, o operador adjunto nm SR →:*A se escreve ∑=

∈=m

im

ii RyAyy1

,*A . De fato,

*A é adjunto de A devido a que

( ) ( ) ( )∑∑∑===

•=•=•=Α=m

iii

m

iii

m

iii XyXAyyXAyXyX

111*, AA .

Com isto, as condições de otimalidade, determinadas no corolário acima, são:

( )KKT

0 ,0

*

≥==+=

SXXS

CSybX

AA

2.2.1 Dualização do modelo de corte máximo

Na seção 3.2 do capítulo anterior, obtivemos a formulação (Dcm) de relaxação por PSD para o

problema de corte máximo. Vamos agora reaplicar o processo de dualização, portanto uma bi-dualização em relação à primeira formulação. A função de Lagrange associada é

( ) ( )YWXyeXyL t +•+−=, ,

onde X ≥ 0 é a matriz multiplicador de Lagrange associada à restrição de desigualdade. Antes de obtermos a função dual, é útil verificar que o produto YX • se reduz, devido a ser Y uma matriz

2850

diagonal, a ( ) yXYX td=•diag , onde denotamos por dX o vetor formado pela diagonal de X.

Temos, assim, a função dual dada por ( ) ntd RyyXeXW ∈+−+• ,max , que, claramente, só é

finita quando e = Xd. Conseqüentemente, o dual se escreve

( ) 0 ,diag:min ≥=• XeXXWX

A fim de chegarmos à formulação de Goemans and Williamson, utilizamos a propriedade (Ap) de que podemos representar os elementos de X por j

tiij vvx = , para alguma matriz V. Temos então

∑<=•

n

ji jtiij vvwXW e diag (X) = e, esta última igualdade significando que 1=iv . Assim,

chegamos a

( ) ∑<

==n

jiij

tiijGW nivvvwCM ,...,1 ,1:min

Goemans and Williamson chegaram a este modelo através da seguinte construção geométrica: dado um grafo (V,E), associa-se a cada nó i ∈ V, um ponto vi, da esfera unitária em Rn, e, em seguida,

minimiza-se a energia ponderada ( )∑∑ ∈∈−−=−−

n

Eij jtiij

n

Eij jiij vvwvvw 122

, que, a menos de

constante, é o modelo (CMGW) que vimos de obter. Terminamos esta seção com o seguinte resultado: Teorema 2.5 (Goemans and Williamson, 1995) Sejam v(Pcm) o valor ótimo do problema de corte máximo (cap. 1,seção 1) e v(CM) o valor ótimo de (CM). Então se tem

( )

( ) θθ

πα

πθ cos12min

0 −=≥

≤≤GW

cm

CMvPv

sendo α estimado por 0,87856 < α < 0,87857. Notemos que o valor típico da relação de v(Pcm) com o valor ótimo obtido por algoritmos que não usam a PSD, veja Poljak, 1992.

2851

Capítulo 3

MÉTODOS EM nS +

3.1 Introdução Denominamos métodos no espaço das matrizes simétricas semidefinidas positivas aqueles em

que os cálculos com as variáveis, originalmente em nS+ , são realizados em nS+ . Eles se contrapõem aos algoritmos que transformam o problema de PSD em um problema de programação não-linear, objeto do próximo capítulo. Basicamente, os métodos em nS+ são algoritmos interiores primais, duais e primais-duais, obtidos como extensão dos respectivos algoritmos da PL. Esta generalização foi possível, sobretudo, graças ao trabalho de Nesterov and Nemirovskii, 1998, 1990 e 1994, que desenvolveram, profundamente, a teoria de métodos polinomiais para a programação convexa, através do conceito de função barreira autoconcordante, e, além deles, e independentemente, Alizadeh, 1995. Nossa exposição será sucinta, aqueles que desejem aprofundar os resultados, vejam, além dos citados acima, alguns trabalhos mais recentes, onde se poderá obter uma bibliografia mais completa: o Handbook of Semidefinite Programming, de Saigal et. al. 2000 e Monteiro and Zhang, 1998. A próxima seção trata de algoritmos seguidores de trajetória, e entre eles, escolhemos a família de primais-duais de Monteiro-Zhang, 1998, e um algoritmo dual, extensão do método de centros, Monteiro and Oliveira, 2003.

Com o objetivo de obtermos algoritmos de pontos interiores, é natural que, supondo X e S definidas positivas (o conjunto das matrizes definidas positivas é o interior de nS+ , que denotamos por nS ++ ; equivalentemente dizemos que X > 0, veja Ap). Define-se, portanto, para 0>µ , o seguinte sistema de equações da trajetória central:

( )µKKT

( ) 0 ,

*

>==+=

SXIXS

CSybX

µA

A

onde as restrições de desigualdade para X e S são implícitas para indicar que qualquer solução (X,S) deste sistema é interior. É claro que com µ = 0 recuperamos (KKT), que apresentamos na seção 2.2. Conclui-se, deste fato, que qualquer que seja o algoritmo, a seqüência dos µk deverá convergir para zero. Outrossim, da mesma forma que na PL, uma forma de mostrar existência e unicidade de solução para o sistema KKT µ-perturbado é através da associação ao problema primal, e também ao dual, de uma família de problemas µ-dependentes, que nada mais é do que a aplicação do método de barreira ao problema (PSD), ou seu dual. No problema primal, associa-se às restrições X ≥ 0 a função ( ) XX detln−=ψ . Esta é, na verdade, definida apenas para matrizes definidas positivas (X > 0), e

tende para +∞, quando qualquer seqüência de matrizes definidas positivas (em nS ++ ) tende para uma matriz semidefinida positiva (em nS+ ): algum autovalor positivo tenderá para 0. Sejam, portanto, o problema de barreira primal:

( ) ( ) 0 :detln min >=−• XbXXXCPSD X Aµµ

e o dual:

2852

( ) ( ) 0 ,y :detln maxm

1ii,

>=++ ∑=

SCSASybPSD it

Syd µµ

Passemos á análise destes problemas. A proposição abaixo mostra que a função barreira é estritamente convexa para X > 0, garantindo assim a unicidade da solução de (PSDµ) e de (PSDdµ). Proposição 3.1 A função ψ(X) = – det ln X é estritamente convexa para X > 0. DEMONSTRAÇÃO: Lembramos, inicialmente, que se pode sempre ter em mente a analogia com funções reais definidas em espaços de dimensão finita, entretanto, trata-se de operação de derivação de operadores. Claramente, se mostrarmos que a hessiana de ψ(X) é definida positiva, teremos obtido o resultado desejado. Partimos da fórmula da derivada do determinante, que aplicada em uma matriz V é:

( ) ( ) VXXVXdXd t •×=• −detdet ,

a qual, para matrizes simétricas é igual a ( ) VXX •× −1det . Logo, ( ) 1−−=′ XXψ . Passemos agora à derivada desta função, a hessiana, que é um operador auto-adjunto. Temos, já levando em conta a simetria de X, que

( ) ( ) ( )[ ] ( ) ( )( ) 121111111 −−−−−−−− +−−=+−=+−=+−=+′ XtOVtXIXVtXIVtXIXtVXtVXψ( ) ( )211 tOVXtXX ++′= −−ψ ,

em que utilizamos a expansão de Taylor da inversa de uma matriz. Conseqüentemente, a segunda derivada de ψ, aplicada também em V é ( ) 11 −−=′′ VXXVXψ . A definição positiva vem da positividade da forma quadrática associada:

( ) ( ) ( ) 211111 tr F

VXVVXXVXXVVXV −−−−− ==•=′′•ψ ,

onde utilizamos a definição da norma de Frobenius (Ap). Esta última expressão é positiva para todo V≠0, e, portanto ψ’’(X) é definida positiva, para todo X, e ψ é estritamente convexa. Vemos que as condições de otimalidade de primeira ordem para (PSDµ) e (PSDdµ), que são necessárias e suficientes devido à convexidade de ψ , são dadas por (KKTµ). Com efeito, chamando de y ∈ Rm o multiplicador associado às igualdades em (PSDµ), obtemos 0*1 =−− − yXC Aµ . Basta, agora, substituir S=µX-1, para identificar (KKTµ). Podemos então definir, para cada µ > 0, a solução única de (KKTµ), (X(µ), y(µ), S(µ)) em nmn SRS ++++ ×× , que é também, com a notação que vimos de usar, solução única de (PSDµ). Analogamente, se chega ao mesmo resultado para (PSDdµ).

Os métodos primais-duais de pontos interiores são baseados na resolução aproximada, pelo método de Newton, daquelas equações. Entretanto, a justificativa teórica para aquela família depende ainda de que a trajetória seja continuamente diferenciável, veja Fiacco and McCormick, 1990. A obtenção deste resultado tem uma dificuldade que é inexistente na PL, onde temos, para problemas no formato padrão, um sistema quadrado em nnm RRR ×× : as variáveis e sua imagem, que geram o sistema, estão neste mesmo espaço produto. Diferentemente, na PSD, as variáveis

( ) nmnnmn SRSSRSSyX ××⊂××∈ ++++,, ,

2853

enquanto a imagem gerada por (KKTµ) é um ponto de nnmn RRS ××× . Isto se deve a que o produto de duas matrizes simétricas não é, em geral, simétrico, portanto apenas se garante que XS ∈ Rnxn, espaço de dimensão n2, enquanto Sn tem dimensão n(n+1)/2. Observe que se tivéssemos usado

µ=• SX no lugar da última equação, é a dimensão 1 que se compararia a n(n+1)/2, e o obstáculo se manteria. A abordagem usual para resolver este problema é a substituição da equação de complementaridade por alguma forma equivalente, que seja simétrica, isto é, com valores em nS ++ . O sistema passa então a ser quadrado. Diga-se a propósito que os algoritmos primais-duais seguidores de trajetória, tema da próxima seção, se diferenciam basicamente pelas diversas formas de se realizar aquela substituição. Por outro lado, a maioria dos métodos daquela classe pode ser incluída como um caso particular da família descoberta por Monteiro-Zhang, em que se substitui XS = µI por

( )[ ] IBXSBBXSB tµ=+ −− 2/11 , para alguma matriz invertível B. Sendo esta uma transformação de

similaridade (Ap), é claro que se mantém os autovalores, que são elementos inerentes à proposição dos algoritmos. Acrescentamos ainda a proposta de Monteiro and Tsuchiya, 1999, que substituem a equação final em (KKTµ) por X1/2SX1/2 = µI, que resulta da pré-multiplicação por X-1/2, e pós-multiplicação por X1/2, da citada equação, havendo, portanto, aqui também, uma transformação de similaridade. Com qualquer destas propostas, podemos, agora apresentar o resultado teórico que garante a existência e diferenciabilidade da trajetória central. Teorema 3.2 Suponha que (PSD) e (PSDd) tenham soluções estritamente viáveis. Então as soluções de (KKTµ) geram uma trajetória diferenciável (X(µ), y(µ), S(µ)), µ > 0, denominada trajetória central. Para cada µ > 0, X(µ) é estritamente primal viável, e (y(µ), S(µ)) é estritamente dual viável, com o salto de dualidade ( ) ( ) ( ) ( ) µµµµµ nSXybXC t =•=−• . Comentário sobre a polinomialidade O trabalho fundamental de Nesterov and Nemirovski tem no conceito de barreira autoconcordante o principal fundamento para a obtenção da polinomialidade dos algoritmos de pontos interiores. Acrescente-se que a teoria lá desenvolvida compreendia uma ampla classe de problemas, convexos, entre os quais se inclui a PSD. Uma função barreira RS n →++:ψ é ν-autoconcordante em

nS ++ se satisfaz duas propriedades. Denotando ( ) ( )tYXtf +=ψ , então deve-se ter

( ) ( )[ ] 2/3020 ff ′≤′′′ , e a direção de Newton, ( ) ( )[ ] ( )XXXd ψψ ′′′= −1 , verificará

( ) ( ) νψ ≤′• XXd , para algum ν > 0. Nesterov and Nemirovski mostraram que a função ( ) ( )XX detln−=ψ é n – autoconcordante, o mesmo valor encontrado para a barreira logarítmica

aplicada em algoritmos de pontos interiores em nR+ . Estas propriedades da função barreira permitem mostrar que, se desde o ponto inicial, a seqüência de iterações se mantiver próximo à trajetória central, então, com ( )( )ενν /lnO iterações se obtém uma ε - solução (tolerância em relação ao custo ótimo). 3.2 Métodos seguidores de trajetória Reproduzindo as idéias básicas da metodologia de pontos interiores na PL, um elemento determinante na obtenção da propriedade de polinomialidade para os algoritmos é que, fixado µ, o sistema de KKT perturbado não é resolvido exatamente (caso se o faça, seriam necessárias

( )( )ε/1ln−O iterações para atingir uma ε - solução, sob determinadas condições). Devido a isto, torna-se necessário estabelecer algum critério que declarará satisfatória a direção de Newton ( )SyX ∆∆∆ ,, obtida no processo iterativo (com µ fixo) definido, por exemplo, por alguma medida de T(XS)-µI. Há, essencialmente, duas categorias de testes: uma baseada no conceito de vizinhança da

2854

trajetória central, e a outra, que utiliza alguma função potencial associada ao problema. Esta seção é dedicada à primeira. 3.2.1 Família de Monteiro-Zhang Seja T(U) = (BUB-1+B-tUt Bt)/2, onde B é uma matriz invertível qualquer. Citemos alguns casos particulares: B = I, Alizadeh et al., 1998, B = S-1/2, Helmberg et al., 1996,e Kojima et al., 1997, e Monteiro, 1997, e B = X-1/2, Kojima et al., 1999, B = S1/4(S1/2XS1/2)-1/4S1/4, Nesterov and Todd, 1998. Nosso objetivo é aplicar o método de Newton ao seguinte sistema, onde apenas o terceiro grupo de equações, nas variáveis X e S, é não-linear:

( )'µKKT

( ) IXST

CSybX

*

µ==+=

A A

Denominando SyX ∆∆∆ ,, as direções correspondentes a, respectivamente, X, y, S, o método de Newton é definido por:

( )SN

( ) ( )XSTIXSXSTSyCSy

XbX

−=∆+∆−−=∆+∆

−=∆

**

µAAAA

Neste ponto se diferenciam duas categorias de algoritmos: os viáveis e os inviáveis. Nos viáveis, cada iteração k verifica bX k = A , Xk > 0, CSy kk =+*A , Sk > 0, em particular, a inicial k = 0. Neste caso o sistema acima se escreve

( ) ( )XSTIXSXSTSyX

−=∆+∆=∆+∆=∆

0*0

µA

A

Como estes últimos não simplificam especialmente aapresentação, optamos pelos algoritmos inviáveis, para os quais, é claro, não é necessário um ponto interior viável. Partimos da definição de distância, ou semidistância, à solução ótima do sistema KKT. Relembremos antes, que as normas, euclidiana e a de Frobenius, de uma matriz simétrica M se relacionam aos respectivos autovalores (Ap), de acordo com:

[ ] ( )( )[ ] 2/1

12

2/1

,2 ∑∑ =

==n

i iji ijFMbM λ , e ( )MM ini 1max λ≤≤= .

Utilizando além disto o resultado do teorema 3.2, façamos ( ) nSXSX /, •== µµ ; podemos assim definir as seguintes medidas, ditas de centralidade para nSSX +∈, :

( )( )( )

∞−∞−

∞

−=

−=

−=

ISXXSXdISXXSXd

ISXXSXdFF

, ,

,

2/12/1

2/12/1

2/12/1

µµ

µ

2855

onde ( )( )XSISXX ini 12/12/1 max: λµµ −=− ≤≤∞−

. Observe que, devido à ortogonalidade das

transformações, as matrizes XS, X1/2SX1/2, assim como T(XS), possuem todas os mesmos autovalores. Destarte, vale para as medidas, que

( ) ( )( )[ ] 2/1

12

, ∑ =−=

n

i iF XSSXd µλ , ( ) ( ) µλ −= ≤≤∞ XSSXd ini 1max, ,

( ) ( )( )XSSXd ini 1max, λµ −= ≤≤∞− .

Em conseqüência definimos as respectivas vizinhanças, para 0 < θ < 1,

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) SXSXdPSDVPSDVV

SXSXdPSDVPSDVVSXSXdPSDVPSDVV

d

d

FdF

,, :,, :,, :

00

00

00

θµθθµθθµθ

≤×=≤×=≤×=

∞−∞−

∞∞

Temos agora os elementos necessários para descrever o algoritmo. Antes, visando uma mais ampla classe, o seguinte sistema será resolvido em cada iteração, em lugar de (SN) (a diferença está apenas no parâmetro, denominado de centralização σ):

( )'SN

( ) ( )XSTIXSXSTSyCSy

XbX

−=∆+∆−−=∆+∆

−=∆

**

σµAAAA

Em (SN’), T é, como vimos, definido por ( ) ( )[ ] 2/11 tBXSBBXSBXST −− += . Algoritmo 3.3 (direções MZ) Escolha 0>ε , 10 << θ , e uma vizinhança ( )θV . Seja dado o ponto inicial ( ) ( )θVSyX ∈000 ,, , e faça ( ) nSX /00

0 •=µ . Repita até que 0εµµ ≤k , faça

1. Escolha uma matriz nk SB ++∈ e o parâmetro de centralidade σk ∈ [0, 1]; calcule a solução ( )kkk SyX ∆∆∆ ,, do sistema (SN’), com B = Bk, σ = σ

k e ( ) ( )kkk SyXSyX ,,,, = 2. Faça ( ) ( ) ( )kkk

kkkkkkk SyXtSyXSyX ∆∆∆+=+++ ,,,,,, 111 , para algum tk > 0 tal

que ( ) ( )θVSyX kkk ∈+++ 111 ,, 3. Faça ( ) nSX kk

k /111

+++ •=µ e atualize k.

Fim (faça) Fim.

2856

Na bibliografia citada encontrão resultados teóricos relacionados à família de algoritmos 3.3, que estabelecem condições para que (SN’) tenha uma solução única, e também garantindo a polinomialidade do algoritmo, de ( )( )ε/1lnnO iterações, para diversas escolhas de vizinhanças e passo tk. 3.2.2 Um algoritmo dual de centros [Monteiro and Oliveira, 2003] Relembremos o dual de PSD:

( ) 0 ,y:maxm

1ii,

≥=+∑=

SCSAybPSD it

Syd

Substituindo zy −= , nós o reescreveremos como um problema de minimização com restrições, apenas, de desigualdades:

( ) ( ) 0z::minm

1ii

≥+=Ψ ∑=

it

z ACzzbD

Seja ∑ =

≥+∈=m

i iim

D AzCRzV1

0:: o conjunto de soluções viáveis de (D), suposto compacto, e

com interior 0DV não vazio. Associamos a (D) a seguinte função de centros (veja Den Hertog, 1992)

0 )),(det(ln)ln()( D

t VzzzbqzF ∈Ψ−−−= ρρ para algum D

t Vzzb ∈> :infρ e q inteiro a ser definido adequadamente. Necessitaremos do gradiente e da hessiana de ρF . Lembrando, da proposição 3.1, que a derivada de Xdetln− é X-1, temos o gradiente dado por

( ) ( )[ ]( ) miit Azzb

qbzFg ,...,11: =− •Ψ−

−=∇=ρρρ .

Para o cálculo da hessiana, ainda da proposição 3.1, a derivada segunda de Xdetln− aplicada em uma matriz V é 11 −− VXX ; pode-se então mostrar que

( )( )

( )[ ] ( )[ ]( )mjiijt

t

AzAzzb

qbbzFH,...,1,

112

2=

−− •ΨΨ+−

=∇=ρ

ρρ

Para a formulação do algoritmo, necessitamos de algumas notações: o conjunto de definição da variável em cada iteração é: ( ) 0z ,: >Ψ>=Ω zbz tρρ ; dada uma direção de Newton,

( ) ρρ gHzd 1−−= , temos a norma induzida pela hessiana ρH , ( ) ( ) 2/11ρρρρ

gHgzd t −==∆ , através

da qual se determinará a proximidade à trajetória ( )1<∆ . Implementação Realizamos um conjunto de testes em alguns problemas de corte máximo disponíveis na biblioteca Borchers, 2000. O objetivo foi apenas verificar o comportamento do método, avaliar sua dependência em relação aos diversos parâmetros. Os resultados são promissores, embora haja muito esforço a ser

2857

despendido, no sentido de tornar sua performance similar a outros de pontos interiores. Executamos em uma máquina de processador PENTIUM III, 850MHz, sistema operacional Windows, com 128M de RAM e a implementação foi feita em MatLab 5.0. Algoritmo de Centros para Programação Semidefinida Parâmetros: NTol: número máximo de iterações; atualização da cota ρ : )1,0(∈θ ; proximidade à trajetória central )1,0(∈ε Inicialização: z0 estritamente viável, 00 zct>ρ , tais que a direção de Newton correspondente h verifique ε

ρ<=∆ 0

0 h .

0=k repita )(1 kktkk zc ρθρρ −+=+ Atualizar a cota superior da função custo kzz = repita Cálculo do centro Calcular kH

ρ e 1−

kHρ

i = 1 repita Calcular o gradiente ( )zFg k 1+∇=

ρ

111

++−−= kk gHh

ρρ

1:)(minarg +Ω∈++= kthxthxftρ

thxx += 1+=∆ kh

ρ

i = i+1 Até ε<∆ ou NToli ≥ Até ε<∆

xz k =+1 1+= kk

Até ερ ≤− kt zc Para obter um ponto inicial próximo ao centro analítico, usamos a técnica big-M proposta em Vandenberghe and Boyd, 1994. Pudemos perceber a sensibilidade do método à solução inicial, assim como o tempo excessivo dedicado aos cálculos dos traços, para os quais não utilizamos nenhuma técnica especial. Os resultados estão dados na tabela a seguir. Problema n m Número de

Iterações Passos de Newton

Precisão

mcp100 100 100 30 302 1x10-4 mcp124-1 124 124 34 330 1x10-4 mcp124-2 124 124 32 331 1x10-4 mcp124-3 124 124 36 327 1x10-4 mcp124-4 124 124 37 330 1x10-4

2858

3.3 Métodos de redução de potencial Uma segunda forma de controlar o processo iterativo de Newton, de modo a resolver aproximadamente o sistema (KKTµ), porém garantindo sua polinomialidade, é utilizar uma função potencial associada ao problema. As funções potenciais em pontos interiores foram introduzidas por Karmarkar, 1984, em seu trabalho seminal para um problema em formato primal. Em nosso caso, a noção que vamos descrever pode ser aplicada tanto ao problema primal quanto ao dual, ou à formulação primal-dual (KKTµ). Aqui, no entanto, nos restringiremos ao último. Consideremos então a seguinte função potencial primal-dual, proposta por Tanabe, 1988 e Todd and Ye, 1990, para pontos ( )SyX ,, estritamente viáveis, isto é, pontos em nmn SRS ++++ ×× , verificando bX =A e

CSy =+*A :

( ) ( ) nnSXSXnSyX lndetlndetlnln:,, −−−•+= ρϕρ

Observando esta função, vemos que ela possui a lógica da metodologia de pontos interiores: o primeiro termo leva em conta o fato de que o salto de dualidade SX • deve ser minimizado; o segundo e o terceiro são a barreira usual para as restrições de definição positiva que as variáveis X e S devem satisfazer. Algumas propriedades são simples de serem verificadas. Denotando por i λ o i-

ésimo autovalor de XS , e λ = ( i λ ) ∈ Rn o vetor dos autovalores, temos λλ tn

i i eSX ==• ∑ =1 , e

( ) ∏ =

===+n

i iXSSXSX1 lndetlndetdetlndetlndetln λ .

Portanto, da expressão de ρϕ , se obtém, para 0=ρ , ( ) ( ) ( )∏ =

−=n

i it nenSyX

1 0 ln/ln,, λλϕ .

Aplicando a desigualdade entre as médias aritmética e geométrica, verifica-se que esta expressão é não-negativa. Para 0>ρ , ρϕ aumenta o peso relativo do termo correspondente ao salto de dualidade. Com a finalidade de produzir um algoritmo polinomial, a exigência específica desta metodologia é que se garanta um decréscimo mínimo fixo entre iterações sucessivas, isto é, para todo k, existe

2859

Capítulo 4

MÉTODOS DA PROGRAMAÇÃO NÃO-LINEAR

Exporemos métodos que têm como característica comum a transformação do problema de PSD, em sua forma primal ou dual, em um problema de programação não-linear, ao qual se aplicarão algoritmos adequados da PNL. As três seções em que se divide este capítulo são conformes a diferentes abordagens, ou, se preferirmos, transformações do problema original. Na primeira, se obtém um problema convexo não-suave, ao qual se aplica um algoritmo do tipo feixes; o segundo tipo de transformação gera problemas de programação não-linear e não-convexo, e a terceira abordagem leva a um algoritmo de ponto proximal. 4.1 Método de feixes espectral Retomemos o problema dual:

≥=−∑=

0 , :max1

, SSAyCybm

iii

tSy .

Helmberg and Rendl, 2000, propuseram a seguinte transformação. Inicialmente, observaram que, dada uma matriz simétrica S, a condição 0≥S é equivalente a ( ) 0max ≤− Sλ ( ( ).maxλ é o maior autovalor de (.)), e que, devido à condição de otimalidade XS = 0, S é sempre singular, a menos que X = 0 seja solução. Isto, entretanto, não ocorre se 0≠b . De qualquer modo, os autores fazem esta hipótese da singularidade de S, e o problema dual se reescreve:

=

−∑

=

0:max1

max CAyybm

iii

ty λ .

Preferiremos, por motivo que veremos adiante, a forma equivalente:

=

−− ∑

=

0:min1

max CAyybm

iii

ty λ .

Deste problema derivamos, por via da função de Lagrange, a função dual

−+− ∑

=

CAyybm

iii

ty

1max min αλ ,

onde α é o multiplicador. Sabemos que o valor de α que torna os dois últimos problemas equivalentes é o que resulta da resolução do dual (veja capítulo 1.2). Os autores mostram que ( )Xtraço=α , para qualquer X primal viável. Passam nesse momento à hipótese de que ( ) 1traço =X , definindo o seguinte problema:

−+− ∑

=

CAyybm

iii

ty

1max min λ

2860

Observando que a diferenciabilidade de max λ só ocorre se a multiplicidade do autovalor máximo for 1, vemos agora o motivo da permuta da forma max para min: temos um problema convexo não-suave. Sobre a hipótese de ( ) 1traço =X , os autores mostram ser possível, por meio de algumas operações, transformar um problema primal no formato padrão, em um que possua a restrição do traço unitário. Adicionalmente, há modelos que já têm, na origem, este formato, por exemplo, o problema de corte máximo, na formulação de Goemans and Williamson (veja seção 2.1.2). Uma palavra sobre a categoria de problemas convexos não-suaves. Há algoritmos de pontos interiores, do tipo centro, e os algoritmos de feixes, que estão entre os de melhor performance computacional. Helmberg and Rendl adaptaram a metodologia de feixes, levando em conta a estrutura específica do problema. 4.2 Métodos de fatorização Esta classe de algoritmos utiliza o fato de uma matriz X ser semidefinida positiva é equivalente a tVVX = , para alguma matriz nnRV ×∈ (Ap). Assim, (PSD) é equivalente ao seguinte problema de programação não-convexa:

( ) nntt RVbVVVVC ×∈=• A ,:min Uma propriedade valiosa é que os conjuntos de minimizadores locais e globais são idênticos. Por outro lado, o conjunto de pontos estacionários contém, em geral, estritamente o conjunto de pontos de mínimo. Há variadas versões que se apropriam desta idéia geral, que também é aplicável ao dual de PSD, com a substituição de S por um produto de matrizes em nnR × . Citamos Homer and Peinado, 1997, que resolveram o problema de corte máximo por meio da utilização do modelo original de Goemans and Williamson (CMGW), que vimos na seção 2.1.2, Burer and Monteiro, 2001, que assumiram V como triangular inferior, Burer and Monteiro, 2003 definiram V como uma matriz triangular superior nrRU rn <∈ × , . A vantagem deste último é que se pode ter problemas não-lineares de menor dimensão. Entretanto, é necessário asseverar que o valor de r seja suficiente para que as soluções ótimas do problema transformado forneçam soluções para o problema original. Verifica-se que esta questão é respondida para valores de mr 2≥ . Finalmente, mencionamos Vanderbei and Benson, 1999, que desenvolveram um método em que a variável primal X é substituída pela decomposição ( ) ( )( ) ( )tXLXdXL Diag , onde L(X) é uma matriz triangular inferior unitária, e ( ) nRXd ∈ . A semidefinição positiva de X é substituída pela exigência de que ( ) nRXd +∈ .

Em todos estes trabalhos, os problemas de programação não linear são resolvidos por algoritmos atinentes a esta classe, incluindo pontos interiores e lagrangeano aumentado, entre outros. 4.3 Método de fatorização - ponto proximal [Gregório and Oliveira, 2003] Nesta seção apresentamos uma nova proposta algorítmica para o ( )PSD . É um algoritmo proximal, que se reduz, a cada iteração, a um problema de programação não-linear em nR+ . A metodologia apresentada é motivada por resultados estabelecidos em Ferreira and Oliveira, 2002, onde o algoritmo proximal clássico é estendido a variedades riemanianas de curvatura seccional não positiva. Um importante exemplo deste tipo de variedade é o espaço das matrizes nS ++ , munido da métrica induzida pela hessiana da barreira ( )Xdetln− (ver Rothaus, 1960). Nós nos aproveitaremos também do fato de que o método proximal não depende das geodésicas, apenas da função distância entre pontos do espaço. Não necessitaremos da geometria riemanniana para a compreensão dos resultados, entretanto, aqueles que o desejarem, vejam em Ferreira and Oliveira, bibliografia concernente.

2861

4.3.1 Algoritmo de ponto proximal em nS+ Considere, inicialmente, o problema de minimização no cone nS+ , ( ) nSXXf +∈:min , sendo ƒ geodesicamente convexa, de classe 1C e mínimo finito em nS+ . Posteriormente, trataremos do problema geral da PSD. Com base na distância riemaniana

( )2/1

1

2/12/12ln),(

= ∑

=

−−n

ii YXXYXd λ , para nSYX ++∈, ,

veja Nesterov e Todd, 2002, e Rothaus, 1960, onde ( ). iλ é o −i ésimo autovalor de (.), defina, para

cada nSX ++∈ , a chamada regularização de Moreau-Yosida para f : dado β > 0, seja

( )

+= YXdYfXf Y ,

2)(min)( 2

0β

β f .

Definição 4.1. ( ) )(arg XfXX β= é chamado de ponto proximal de X associado ao parâmetro β ,

com respeito a f e a d2. Como f é convexa, limitada inferiormente e d2 é estritamente convexa (ver Ferreira and Oliveira), a função argumento

( )YXdYfYXg , 2

)(),( 2ββ += ,

tem no máximo um minimizador. Por outro lado, aqueles autores mostram também que ,.)(Xg β é 1-

coerciva. Dessa forma, para cada 0>β existe um único ( )XX , tal que

( ) ( ) ),(minarg),( )( 02 YXgXXXdXXf Y ββ f=+ .

Se f for diferenciável, ( )XX é caracterizado por ( )( ) ( ) ( ) ( ))(,, XXfYXdXXXd XXYY −∇=∇ =β . Nos casos em que ƒ é não-diferenciável, a condição de otimalidade é expressa através do subdiferencial ( ))( XXf∂ de f em ( )XX , a saber, ( )( ) ( ) ( ) ( ))(,, XXfYXdXXXd XXYY −∂∈∇ =β .

A metodologia de ponto proximal consiste em gerar, a partir de um ponto nSX ++∈0 uma

seqüência de minimizadores definida por )(1 kk XXX =+ , com kβ satisfazendo +∞=∑∞

=1 /1

kkβ .

Algoritmo 4.2 (Algoritmo de Ponto Proximal para PSD). Dados 00 >X e 00 >β 1. 0←k ; 2.(critério de parada) 3. Calcular

+= ∑

=

−−>

+n

i

kki

k

Yk XYXYfX

1

21

212

01 )()(ln

2)(minarg λβ

;

atualizar k e retornar ao 2.º passo.

2862

Como conseqüência dos resultados obtidos em Ferreira and Oliveira, podemos garantir que o algoritmo acima converge globalmente para séries kβ divergentes e funções convexas relativamente à métrica determinada pela hessiana de ( )Xdetln− . É evidente que cada iteração do passo 3 é tão ou mais complexa que o problema original. É o objetivo da próxima seção a obtenção de um algoritmo proximal implementável. 4.3.2 Algoritmo de ponto proximal em nR+ A função distância, acima definida, possui a importante propriedade de invariância por transformações não-singulares. Lembremos que ela se aplica ao operador, de nS ++ em nS ++ , dado por

( ) ( ) 21

21

)( −−= kk

XXYXYT k . Por ser invariante por transformações não-singulares, resulta que, para

qualquer matriz invertível kQ , a distância aplicada em

( ) ( ) ( ) ( ) ( ) kkkkkX

k QXYXQQYTQZ k2

12

111: −−−−==

tem o mesmo valor que em ( )YT kX

. Este fato sugere que escolhamos kQ de modo que a matriz Z seja

diagonal. Esta transformação, aplicada à variável nSY ++∈ no subproblema do passo 3 do algoritmo acima, o transformará em um problema na variável ( ) nRzZ ++∈= Diag . Este é o fundamento do algoritmo, que descrevemos a seguir: Algoritmo 4.3 (Algoritmo de Ponto Proximal em nR+ ). Dados 00 >X e 0β > 0 1. 0←k ; 2.(critério de parada) 3. Dado kY0 , calcular a matriz kQ ortogonal tal que

( ) ( ) ( ) ( ) kkkkkTk ZQXYXQ 02

1

02

1=

−−,

onde kZ0 é diagonal definida positiva.

4. Defina kZ0 como ponto inicial, e calcule

( ) ( ) ( ) ( ) ( )

+

= ∑

=

+n

ii

kkTkkk

Zk ZXQZQXfZ

1

221

21

01 ln

2minarg λβ

f .

Faça

( ) ( ) ( ) ( ) 2112

11 kTkkkkk XQZQXX ++ = , atualize k e retorne ao 2.º passo. Para termos uma maior clareza sobre o passo 4, denotemos ( )Zz Diag= , e RRn →++:ϕ por

( ) ( ) ( ) ( )

== 2

12

1)()( kTkkk XQZQXfZz φϕ .

2863

Da definição acima segue que ϕ preserva o conjunto de minimizadores do problema original, a menos de uma transformação de variáveis. Por outro lado, o termo de regularização proximal se escreve

( ) 2

21

2 )(lnln ZZ

n

ii Λ=∑

=

λ , onde )(ln ZΛ é o vetor cuja i -ésima coordenada é iiZln Logo, o passo

4 pode ser rescrito como

( )

∈+= ++=

+ ∑ nn

ii

k

zk Rzzzz ,ln

2)(minarg

1

21 βϕ .

Boa definição do algoritmo

As propriedades obtidas em Ferreira and Oliveira para funções geodesicamente convexas não se transferem automaticamente para o subproblema em nR ++ . Por isto, devemos analisar, per se, o

algoritmo (4.3). Primeiramente, observamos que a função ∑=

n

iiz

1

2ln , definida em nR ++ , tende a ∞+ na

fronteira deste conjunto, logo é uma barreira. É também uma função coerciva: ∑=

∞→n

iiz

1

2ln se

∞→z , e fortemente quasiconvexa. Lembramos que RSf →: ,onde S um subconjunto convexo

e fechado não-vazio de Rn , é dita fortemente quasiconvexa se para cada Sxx ∈21, , com 21 xx ≠ , [ ]21 )1( xttxf −+ < ( ) ( ) 21 ,max xfxf , para )1,0(∈t . Sabe-se que os minimizadores locais e

globais de funções quasiconvexas são os mesmos, veja Bazaraa et al., 1993. A título de ilustração, esboçamos o gráfico de uma parcela da função barreira:

0 100 200 300 400 5000

1

2

3

4

5

6

Figura 4.1 – gráfico da função t2ln .

Uma outra propriedade fácil de ser verificada é que a adição de uma função convexa com uma fortemente quasiconvexa resulta em uma função fortemente quasiconvexa. Portanto, usando a

coercividade de ∑=

n

iiz

1

2ln e supondo que ϕ é convexa em nR+ conclui-se que o algoritmo está bem

definido: o passo 4 define um único ponto em nR ++ . Resolução do subproblema pelo método de Newton Suponha ϕ estritamente convexa, e ))(( ''

min zϕλµ = . Seja µα <<0 . A fim de que o método de Newton seja empregado, exigiremos que a hessiana da função argumento do passo 4 seja definida positiva para todo nRz ++∈ , isto é:

2864

αβϕλβϕλ ≥

−+≥

−+ ≤≤ 21

''min2

''min

ln1min))((

ln1diag)(

i

ini

i

i

zz

zz

zz ,

(veja Ap, para a propriedade utilizada). Isto implica em

µαβ −≥

−≤≤ 21

ln1min

i

ini z

z.

Como 0<− µα , a parte interessante dessa análise restringe-se ao caso em que

)ln1(min1 ini z−≤≤ < 0, isto é quando ezi > . Neste caso, a última desigualdade implica em que ( )( )1ln/)(min 2

1 −−≤ ≤≤ iini zzαµβ . Analisando a função ( )1ln/)( 2 −= ttth , para t > e,

conclui-se que ( ) etthet >== ,minarg2/3 , e que o valor ótimo associado a t é dado por .2)( 3eth = Logo, a escolha de

( )β 32)( eαµβ −≤

permitirá a aplicação do método de Newton.. 4.3.3 Aplicação à PSD Retomemos a formulação primal de programação semidefinida:

( ) 0 ,,...,1 ,:min ≥==•• XmibXAXCPSD ii A iteração principal do algoritmo 4.3 se escreve

( ) ( ) ( )( ) ( )( ) ( )( ) ( ) 0 ,,...,1,diags.a

ln2

diagmin

21

21

1

221

21

0

>==•

+• ∑=∈

zmibXQzQXA

zXQzQXA

ikTkkk

i

n

ii

kkTkkk

Rz n

β

Como a função custo e as restrições são lineares, os termos podem ser agregados de forma que este problema possa ser reescrito no seguinte formato

( ) ( )

>=+ ∑=

0 , :ln2

min1

2 zbzAzzc kn

ii

kTk

zβ

para algum vetor nk Rc ∈ e alguma matriz nmAk × , . As hipóteses necessárias à aplicação do método de Newton podem, como veremos, ser garantidas através do acréscimo de uma regularização quadrática ( )∑ =

n

i iz1

22/ρ . Consideremos, em

conseqüência, o seguinte problema regularizado

( )PPR ( ) ( )

>=++ ∑∑==

.0 , :ln22

min1

2

1

2 zbzAzzzc kn

ii

kn

ii

Tk βρ

2865

Denotando por y o vetor de multiplicadores das restrições de igualdade, temos as seguintes condições KKT para este problema:

( ) ( )0

0 ,0ln

=−

>=+++

bzA

zyAzzzc

k

Tkkk βρ

Seja agora ( )Tyz ∆∆ , a direção de Newton associada a este sistema. É fácil ver que

( ) ( )0

ln ln1

Diag

,...,12

=∆

−−−−=∆

−++∆

=

zA

yAzzzcz

zz

IyA

k

Tkkk

nii

iTk βρρ

Através da expressão da inversa da matriz de coeficientes, se vê, claramente, a necessidade da regularização quadrática. Denote por ( )( )2/ln1Diag ii zzIU −+= ρ o coeficiente de z∆ . Então a inversa da matriz de coeficientes é dada por:

( )( ) ( )

−−+

−−−

−−−−−

111

11111

PUAPPAUUAPAIU

k

TkkTk

onde ( )Tkk AUAP 1−−= . Temos, por conseguinte, o lema, conseqüência da desigualdade ( )β obtida acima, em que µ tem o papel de ρ: Lema 4.4 Suponha que a matriz Ak tenha posto completo. Então, para todo 32/ eβρ > o algoritmo de Newton pode ser aplicado ao problema ( )PPR . Observação 4.5 O algoritmo proximal pode ser estendido ao caso não-diferenciável através da noção de feixes híbrido (ver Hiriart and Lemaréchal, 1993).

2867

APÊNDICE Os conceitos e resultados que serão apresentados, podem ser vistos em diversos textos de álgebra linear, tais como Horn and Johnson, 1982, Lancaster and Tismenetsky, 1985 e Strang, 1980.

A1. Matrizes reais e matrizes simétricas Suponha que A é uma matriz real nn× . 1. Define-se o par autovetor nRv∈ , autovalor λ, real ou complexo, como soluções do sistema Av = λv. Equivalentemente, λ resolve a equação algébrica de grau n, denominada equação característica, dada por det(A - λI) = 0. 2. Define-se o traço de uma matriz como ( ) ∑ =

=n

i iiaA1

tr . O traço satisfaz as seguintes propriedades:

i – ( ) ∑ ==

n

i iA1 tr λ , onde i λ são os autovalores de A.

ii – tr (At) = tr (A) iii – tr (A+B) = tr (A) + tr (B) iv – tr (AB) = tr (BA), denotado também por BA • v – tr (X-1AX) = tr (A), para qualquer matriz X invertível. vi – tr (ABCD) = tr (BCDA) = tr (CDAB) = tr (DABC)

vii – ( ) ∑∑= =

=n

i

n

jijij

t baBA1 1

tr .

Quando A = B, temos a norma de Frobenius de A:

( ) ∑∑= =

==n

i

n

jFij

t AaAA1 1

22 :tr = ( )( )∑ =

n

i i A1

2 λ

3. Além da norma de Frobenius, a norma euclideana é também de largo uso: ( )MM ini 1max λ≤≤= 4. A é uma matriz simétrica se seus elementos verificarem aij = aji, para todo ij, ou A=At. A soma de matrizes simétricas é simétrica, assim como a multiplicação por escalar de uma matriz simétrica a mantém simétrica. O produto de duas matrizes simétricas não é, em geral, simétrico. 5. Se A for simétrica, seus autovalores são reais, e é possível obter um conjunto de n autovetores ortonormais: ijj

ti vv δ= , para todo i, j, δ representando o símbolo de Kronecker.

6.São equivalentes: i - A é simétrica ii - A = BtB, para alguma matriz B iii - A = C2, para alguma matriz simétrica C. iv – A é congruente a uma matriz diagonal. Diz-se que A e B são congruentes se existe uma matriz não-singular C, tal que A = Ct DC. No caso das matrizes simétricas, pode-se ter D diagonal, formada pelos autovalores de A, e C ortogonal (a inversa de C é Ct). 7. A e B são similares se existir uma matriz não-singular X tal que A = X-1BX. Matrizes similares possuem o mesmo traço, determinante, autovalores e equação característica. Toda matriz simétrica é ortogonalmente similar a uma matriz diagonal. Como conseqüência, o traço de uma matriz simétrica é a soma de seus autovalores (propriedade 2.i). 8. Se A for simétrica, então A=0 se e somente se xtAx = 0 para todo vetor x.

2868

9. Seja ( ). iλ o i-ésimo autovalorde (.), i = 1,...,n, ordenados crescentemente. Então

( ) ( ) ( )BABAi 1 1 λλλ +≥+ , para todo i = 1,...,n. A2. Matrizes simétricas definidas positivas e semidefinidas positivas

A é uma matriz simétrica definida positiva se xtAx > 0, para todo x não-nulo; A é semidefinida positiva se 0≥Axxt para todo x. O primeiro conjunto é denotado por nS ++ , e o segundo por nS+ . 1. São equivalentes: i – A é semidefinida positiva ii – A = BtB, para alguma matriz B (não necessariamente quadrada). Se B for quadrado, sendo bi, i=1,...,n, sua colunas, então j

tiij bba = , e A é a matriz de Gram dos vetores bi.

iii – A = C2, para alguma matriz simétrica C iv – Os autovalores de A são não-negativos v – O determinante de todo menor simétrico é não-negativo vi – A é uma combinação linear de matrizes de posto 1 (do tipo xxt). 2. Se A é semidefinida positiva, então, para todo inteiro l > 0, existe uma única matriz semidefinida B, tal que A = Bl, que verifica: i – AB = BA ii – B = p(A), para algum polinômio p(.) iii – posto (B) = posto (A) 3. Sejam A e B semidefinidas positivas. Então ( ) 0tr ≥=• ABBA , a igualdade valendo se e somente se AB=0. 4. C é um cone convexo: se nSBA +∈, , então nSsBtA +∈+ , para todo 0, ≥st . 5. O interior de nS+ é nS ++ : significa que toda seqüência convergente de matrizes em nS ++ converge para alguma matriz de nS+ .

2869

Referências Bibliográficas [1] Alizadeh, F.: Interior point methods in semidefinite programming with applications to

combinatorial optimization. SIAM Journal on Optimization 5(1), 13-51 (1995) [2] Alizadeh, F., Haeberly, J.-P. , Overton, M. L.: Primal-dual interior-point methods for semidefinite

programming: convergence rates, stability and numerical results. SIAM Journal on Optimization 8, 746-768 (1998)

[3] Bazaraa, M. S. Sherati, H. D., Shetty, c. M.: Nonlinear Programming: Theory and Algorithms. John Wiley and Sons Inc. (1993)

[4] Borchers, B.: SDPLIB 1.2, A library of semidefinite programming test problems. The SDPLIB problems, (2000)

[5] Burer, S., Monteiro, R. D. C.: A projected gradient algorithm for solving the Maxcut SDP relaxation. Optimization Methods and Software 15, 175-200 (2001)

[6] Burer, S., Monteiro, R. D. C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical programming, Series B 95, 329-357 (2003)

[7] Burer, S., Monteiro, R. D. C, Zhang, Y.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, Series B 95, 329-357 (2003)

[8] Burer, S., Monteiro, R. D. C., Zhang, Y.: Solving a class of semidefinite programs via nonlinear programming. Mathematical Programming 93, 97-123 (2002)

[9] D. den Hertog. Interior Point Approach to Linear, Quadratic and Convex Programming, Ph.D. Thesis, Dept. of Applied Mathematics, Delft University of Technology, 1992. [10] Ferreira, O. P., Oliveira, P.R.: Proximal point algorithm on Riemannian manifolds. Optimization

51, 2, 257-270, (2002) [11] Fiacco, A., McCormick, G.: Nonlinear programming: Sequential unconstrained minimization

techniques, Wiley, New York, 1968; SIAM Classics in Applied Mathematics Series, reprint, (1990)

[12] Fukuda, M., Kojima, M., Murota, K.,Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: General framework. SIAM Journal on Optimization 11, 647-674 (2001)

[13] Goemans, M. X., Williamsom, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 1115-1145 (1995)

[14] Gregório, R., Oliveira, P. R.: A new nonlinear programming proximal algorithm for semidefinite programming. Working paper. PESC/COPPE, 2003.

[15] Hiriart-Urruty, J-B, Lemaréchal, C.: Convex analysis and minimization II, Advanced theory and bundle methods, Springer-Verlag, Heidelberg (1993)

[16] Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM Journal on optimization 10, 673-696 (2000)

[17] Helmberg, C., Rendl, F, Vanderbei, R. J., Wolkowicz, H.: Na interior-point method for semidefinite programming, SIAM Journal on Optimization 6, 342-361 (1996)

[18] Homer, S., Peinado,M.: Design and performance of parallel and distributed approximation algorithms for max cut. Journal of Parallel and Distributed computing 46, 48-61 (1997)

[19] Horn, R., Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985 [20] Karmarkar, N.: A new polynomial-time algorithm for linear programming, Combinatorica 4, 373-

395 (1984) [21] Kojima, M., Shida, M., Shindoh, S.: Search directions in the SDP and the monotone SDLCP:

generalization and inexact computation. Mathematical Programming 85, 51-80 (1999) [22] Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear

complementarity problem in symmetric matrices. SIAM Journal on Optimization 7, 86-125 (1997)

[23] Lancaster, P., Tismenestky, M.: the Theory of Matrices, Academic Press, Orlando, FL, 1985. [24] Lemaréchal, C, Oustry, F.: SDP relaxations in combinatorial optimization from a Lagrangian

viewpoint, in N. Hadjisavvas and P. M. Pardalos (eds.), Advances in Convex Analysis and Global Optimization, 119-134 (2001)

2870

[25] Monteiro, R. D. C.: Primal-dual path following algorithms for semidefinite programming. SIAM Journal on Optimization 7, 663-678 (1997)

[26] Monteiro, R. D. C.: First and second-order methods for semidefinite programming. Mathematical Programming, Series B 97, 209-244 (2003)

[27] Monteiro, S. A., Oliveira, P. R. A center dual algorithm for semidefinite programming, Working Paper, PESC/COPPE-UFRJ, (2003)

[28] Monteiro, R. D. C., Tsuchiya, T.: Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming. SIAM Journal on Optimization 9, 551-577 (1999)

[29] Monteiro, R. D. C., Zhang, Y.: A unified analysis for a class of path-following primal-dual

interior-point algorithms for semidefinite programming. Mathematical Programming 81, 281-299 (1998)

[30] Nesterov, Y. E., Nemirovskii, A. S.: Polynomial barrier methods in convex programming. Ekonomika i Matem. Metody 24, 1084-1091 (1988)

[31] Nesterov, Y. E., Nemirovskii, A. S.: Optimization over positive semidefinite matrices: Mathematical background and users manual. Technical report, Central Economic and Mathematical Institute, USSR Acad. Sci. Moscow, USSR, (1990).

[32] Nesterov, Y. E., Nemirovskii, A.S.: Interior Point Polynomial Algorithms in Convex Programming: Theory and Applications. Society for Industrial and Applied Mathematics, Philadelphia, (1994).

[33] Nesterov, Y. E, Todd, M. J.: Primal-dual interior-point methods for self-scaled cones. SIAM Journal on Optimization 8, 324-364 (1998)

[34] Nesterov, Y. E, Todd, M. J.: On the Riemannian geometry defined by self-concordant barriers and interior-point methods. Foundations of Computational mathematics 2, 333-361 (2002)

[35] Poljak, S.: Polyhedral and eigenvalue approximations of the max-cut problems, in: G. Halász et al., eds., Sets, Graphs, and Numbers, Colloquia Mathematica Societatis János Bolyai, Vol 60 (North Holland, Amsterdam) 569-581, (1992).

[36] Poljak, S., Tuza, Z.: Maximum cuts and largest bipartite subgraphs, in: W. cook, L. Lovász and P. Seymour, eds, Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (MAS, Providence, RI)(1995)

[37] Rothaus, O. S.: Domains of positivity. Abh. Math. Sem. Univ. Hamburg 24, 189-235, (1960). [38] Saigal, R., Vandenberghe, L., Wolkowicz, H.: Handbook of Semidefinite Programming. Kluwer

academic Publishers, Boston-Dordrecht-London, (2000) [39] Strang, G.: Linear Algebra and its Applications, Second edition, Academic Press, New York,

London, 1980. [40] Tanabe, K. Centered Newton method for mathematical programming. In: System Modeling and

Optimization, Springer-Verlag, NY, 197-206, (1988) [41] Todd, M. J., Ye, Y.: A centered projective algorithm for linear programming. Math. Oper.Res,

15: 508-529 (1990). [42] Vanderbei, R. J., Benson, Y.: On formulating semidefinite programming problems as smooth

nonlinear optimizations problems. Report orfe 99-01, Operations Research and Financial Engineering. Princeton, NJ, 1999