Como calcular o elipsóide máximo em um determinado poliedro

Estou enfrentando o problema de encontrar o elipsóide ( é uma matriz definida positiva simétrica) de volume máximo dentro de um conjunto convexo dado como um conjunto de desigualdades lineares . Eu entendi como é formalizado como um problema de otimização convexa $B$ $B$ $C$ $C=\{x| a_i^T x \leq b_i, i=1,\dots,m\}$ como é apresentado em "Otimização convexa, Stephen Boyd e Lieven Vandenberghe, Cambridge University Press, 2004"[versão em pdf]. Minha abordagem seria usar métodos de pontos interiores, introduzir um parâmetro de precisão e incorporar as restrições ao objetivo por meio de uma função de barreira logarítmica, conforme explicado no capítulo 11 do livro acima, e tentar minimizar o problema não controlado resultante

min_{B, d} [\log det B^{- 1}] s.t.: | | B a_{i} | |_{2} + a_{i}^{T} d \leq b_{i}, i = 1, \dots, m

$\min_{B,d}\quad[\log\det B^{-1}]\\ \mbox{s.t.:}\quad ||Ba_i||_2+a_i^Td\leq b_i, \qquad i=1,\dots, m$

t > 0

$t>0$

Portanto, eu usaria derivadas parciais de

min_{B, d} \underset{= f (B, d)}{\underset{⏟}{[\log det B^{- 1} - \frac{1}{t} \sum_{i = 1}^{m} \log (b_{i} - | | B a_{i} | |_{2} - a_{i}^{T} d)]}} .

$\min_{B,d}\quad \underbrace{\left[\log\det B^{-1} - \frac{1}{t}\sum_{i=1}^m\log(b_i-||Ba_i||_2-a_i^Td)\right]}_{= f(B,d)}.$

f

$f$

que é uma matriz e

\frac{\partial f}{\partial B} = B^{- 1} + \frac{1}{t} \sum_{i = 1}^{m} (\frac{\frac{B a_{i} a_{i}^{T}}{| | B a_{i} | |}}{b_{i} - | | B a_{i} | |_{2} - a_{i}^{T} d})

$\frac{\partial f}{\partial B} = B^{-1}+\frac{1}{t}\sum_{i=1}^m\left(\frac{\frac{Ba_ia_i^T}{||Ba_i||}}{b_i-||Ba_i||_2-a_i^Td}\right)$

que é um vetor. E, a partir de um ponto inicial (viável)

eu atualizaria iterativamente a solução real

acordo com os derivados parciais negativos:

\frac{\partial f}{\partial d} = \frac{1}{t} \sum_{i = 1}^{m} (\frac{a_{i}}{b_{i} - | | B a_{i} | |_{2} - a_{i}^{T} d})

$\frac{\partial f}{\partial d}=\frac{1}{t}\sum_{i=1}^m\left(\frac{a_i}{b_i-||Ba_i||_2-a_i^Td}\right)$

(B^{0}, d^{0})

$(B^0,d^0)$

(B^{k}, d^{k})

$(B^k,d^k)$

onde

B^{k + 1} = B^{k} - s_{B} \frac{\partial f (B^{k}, d^{k})}{\partial B} d^{k + 1} = d^{k} - s_{d} \frac{\partial f (B^{k}, d^{k})}{\partial d}

$B^{k+1} = B^k - s_B \frac{\partial f(B^k,d^k)}{\partial B}\\ d^{k+1} = d^k - s_d \frac{\partial f(B^k,d^k)}{\partial d}$

s_{B} > 0

$s_B>0$

s_{d} > 0

$s_d>0$ são parâmetros de tamanho da etapa até que um critério de parada predefinido seja preenchido. \ Não tenho certeza se essa é uma maneira correta de resolver o problema? Parece-me muito estranho e não muito elegante. Não sou especialista em técnicas de otimização e não sei se reuni todos os ingredientes (derivadas parciais, método de ponto interior, minização sem restrições etc.) da maneira correta. Gostaria de saber como um especialista resolveria esse problema. No livro acima mencionado, esta tarefa foi mostrada como um exemplo de um problema convexo, mas, tanto quanto posso ver, havia um algoritmo explícito para resolver a tarefa. Embora eu ache que o Sr. Boyd tenha em algum lugar um script do Matlab em suas páginas para resolver a tarefa, mas quero entender as técnicas básicas antes de usar um algoritmo de "caixa preta". Parece haver outras abordagens em " Algoritmos polinomiais de pontos interiores em programação convexa; Yurii Nesterov e Arkadii Nemirovskii, SIAM estudam matemática aplicada; vol.13, 1994 "e" Sobre a complexidade de aproximar o elipsóide máximo inscrito para um politopo, Leonid G. Khachiyan e Michael J. Todd, Programação Matemática 61 (1993), 137-159 ", mas não os compreendo porque eles são escritos para técnico para mim.

A propósito: Como é o problema duplo do primeiro problema? E como é derivado?

desde já, obrigado

optimization convex-optimization Denis K.
fonte

Existem solucionadores que farão todas essas coisas por você. Existe alguma razão para você querer fazer isso sozinho? Falando como alguém que, a certa altura, aprendeu sobre métodos de pontos interiores, trabalhou em um laboratório de otimização e codificou alguns dos métodos no MATLAB (para tarefas de casa), eu ainda usaria o solucionador de caixa preta .

Geoff Oxberry

Eu mantenho o princípio de entender / implementar pelo menos uma versão básica de um método antes de usar rotinas prontas para uso. Eu acho que esse princípio vem com dois aspectos favoráveis: 1) Ele vem com um imenso efeito de aprendizado e uma compreensão mais profunda dos métodos. 2) Na maioria dos aplicativos, uma versão básica de um algoritmo matemático é suficiente (pelo menos para os aplicativos com os quais me confronto). Portanto, você pode manter seu código pequeno e simples e não precisa se preocupar com itens de licença (caso queira ganhar algum dinheiro com ele).

Denis K.

Bem, você está no caminho certo. Não há mágica em resolver esses problemas usando métodos de pontos interiores, eles são iterativos por natureza e baseados em linearizações etc.

No entanto, um algoritmo típico de ponto interior para esses problemas não daria um passo na direção do gradiente, mas também computaria informações de segunda ordem e, portanto, daria um passo de Newton. Portanto, uma pesquisa de linha é realizada na direção de Newton, uma etapa ideal é executada e o procedimento é repetido. Uma vez convergidos (também com alguma precisão definida adequadamente), o parâmetro de barreira é diminuído (com algum fator adequado) e o procedimento é repetido novamente.

Para que ele funcione na prática, você precisa pensar cuidadosamente sobre como atualizar os parâmetros e, na maioria das vezes, faria tudo no espaço dual-primal.

Se você pesquisar no sillysdp, encontrará uma implementação simples de um solucionador de SDP implementando, essencialmente, o exemplo 11.9 na referência de Boyd & Vandenberghe que você está lendo. Talvez um começo de inspiração (uma vez que a programação semidefinida é uma generalização de um SOCP que você está resolvendo, negligenciando o termo logdet no objetivo, o que realmente não complica as coisas)

Johan Löfberg
fonte

Como calcular o elipsóide máximo em um determinado poliedro

Respostas: