Considere um politopo racional que é definido por meio de um oráculo de separação. Ou seja, pode ser descrito implicitamente como , mas como é muito grande, usamos um oracle, que dado um ponto , quer diz ou retorna uma meia-espaço de tal modo que .P P = { x ∈ R k : A x ≤ b , A ∈ Z m × k , b ∈ Z m } m x ∈ R k x ∈ P x ∉ S
Meu objetivo é encontrar um ponto em ou determinar se está vazio. Eu estou apontando para um tempo de execução polinomial no tamanho representação de e , onde é o maior valor absoluto em . Ou seja, o algoritmo deve fazer apenas polinômios muitas chamadas para o oráculo de separação.P U k U A
Em geral, pode estar contido em um hiperplano de menor dimensão e, portanto, é problemático usar o método elipsóide. Assim, como no truque da Khachiyan, eu alter (e o oráculo separação) para usar , onde é algo como . Intuitivamente, os meios espaços que definem são os mesmos que definem apenas que são traduzidos por . O politopo tem as seguintes propriedades: está vazio se estiver vazio e se não estiver vazio,P P ε ε 1 / L P ε P ε P ε P ε P P P ε é totalmente dimensional.
Minha pergunta é a seguinte: Suponha que o algoritmo encontre um ponto . É possível gerar um ponto em usando ? P p
Se seu objetivo é encontrar um ponto em ou determinar que P está vazio, por que você não faz o seguinte.P P
Seja um conjunto de semi-espaços, inicialmente vazios.H
Seja um ponto, inicialmente igual a 0 k .x 0k
Dê ao oráculo.x
Se o oráculo disse , você já fez.x∈P
Caso contrário, seja o meio espaço violado retornado pelo oráculo. Vamos y ser a projecção ortogonal de x em S .S y x S
Volte para 1.
fonte