Quão "difícil" é maximizar uma função polinomial sujeita a restrições lineares?

8

Problema Geral

Suponha que tenhamos uma função polinomial multivariada e várias funções lineares . O que se sabe sobre a complexidade de resolver o seguinte problema de otimização?i ( x )f(x)i(x)

Maximizef(x)Subject to: i(x)0 for all i

Podemos assumir que a região determinada pelas restrições é limitada.

Problema relacionado, mas mais específico

Suponha que tenhamos um polítopo limitado (representado como a interseção de um conjunto de desigualdades lineares). Desejo calcular o volume máximo de um hiper-retângulo (paralelo ao eixo) completamente contido no politopo. Qual é a complexidade de resolver esse problema?

A ajuda em um desses problemas é muito apreciada.

Naysh
fonte
Você pode dar uma olhada neste artigo .
Rodrigo de Azevedo
3
Convém perguntar ao seu segundo problema separadamente, em uma postagem separada.
DW

Respostas:

22

Seu problema é difícil para NP, mesmo para polinômios de grau 2. A referência crucial é

Theodore Motzkin e Ernst Strauss (1965)
"Maxima para gráficos e uma nova prova de um teorema de Turan"
Canadian Journal of Mathematics 17, pp 533-540

G=(V,E)V={1,2,,n}1/ωωG

maxEujExEuxjs.t.EuVxEu=10 0xEu1    para todos EuV

Como a computação do número de clique é NP-difícil, isso implica a NP-dureza de maximizar uma função polinomial multivariada sujeita a restrições lineares.

Gamow
fonte
Em uma solução ideal, o valor de cada deve ser se estiver na camarilha (e outro lugar), e o valor objetivo ideal coincidir com . Isso ocorre porque atribuir o valor a cada vértice de clique significa que cada uma das arestas clique contribui com para OPT. A generalização natural desse mesmo cálculo mostra que isso é ótimo. xv1/ωv0 0(1-1/ω)/21/ω(ω2-ω)/21/ω2
Yonatan N