Seberapa “sulit” untuk memaksimalkan fungsi polinomial yang tunduk pada batasan linear?

Masalah umum

Misalkan kita memiliki fungsi polinomial multivariat , dan beberapa fungsi linear . Apa yang diketahui tentang kompleksitas penyelesaian masalah pengoptimalan berikut? $f(\mathbf{x})$ $\ell_i(\mathbf{x})$

\begin{aligned} Maximize & f (x) \\ Subject to: & ℓ_{i} (x) \leq 0 for all i \end{aligned}

$\begin{align*} \text{Maximize} & \;\; f(\mathbf{x}) \\ \text{Subject to: } & \;\, \ell_i(\mathbf{x}) \le 0\text{ for all } i \end{align*}$

Kita dapat mengasumsikan bahwa wilayah yang ditentukan oleh kendala dibatasi.

Terkait, tetapi Lebih Spesifik, Masalah

Misalkan kita memiliki polytope terbatas (direpresentasikan sebagai persimpangan dari set ketidaksetaraan linear). Saya ingin menghitung volume maksimum dari hyperrectangle (paralel sumbu) sepenuhnya terkandung dalam polytope. Apa kompleksitas memecahkan masalah ini?

Bantuan untuk salah satu dari masalah ini sangat kami hargai.

cc.complexity-theory complexity-classes time-complexity linear-programming polynomials Naysh
sumber

Anda mungkin ingin melihat makalah ini .

Rodrigo de Azevedo

Anda mungkin ingin menanyakan masalah kedua secara terpisah, di pos yang terpisah.

Jawaban:

Masalah Anda NP-keras, bahkan untuk polinomial tingkat 2. Referensi penting adalah

Theodore Motzkin dan Ernst Strauss (1965)
"Maxima untuk grafik dan bukti baru teorema Turan"
Canadian Journal of Mathematics 17, pp 533-540

$G=(V,E)$ $V=\{1,2,\ldots,n\}$ $1/\omega$ $\omega$ $G$

\begin{array}{rcl} max & \sum_{i j \in E} x_{i} x_{j} \\ s . t . & \sum_{i \in V} x_{i} = 1 \\ 0 \leq x_{i} \leq 1 for all i \in V \end{array}

$\begin{eqnarray*} \max &&\sum_{ij\in E} x_ix_j \\[2ex] s.t. &&\sum_{i\in V} x_i=1 \\[1ex] && 0\le x_i\le 1~~~ \text{ for all $i\in V$} \end{eqnarray*}$

Karena menghitung angka klik adalah NP-hard, ini menyiratkan NP-hardness untuk memaksimalkan fungsi polinomial multivariat yang tunduk pada batasan linear.

Gamow
sumber

x_{v}

$x_v$

1 / ω

$1/\omega$

v

$v$

0

$0$

(1 - 1 / ω) / 2

$(1-1/\omega)/2$

1 / ω

$1/\omega$

(ω^{2} - ω) / 2

$(\omega^2-\omega)/2$

1 / ω^{2}

$1/\omega^2$ memilih. Generalisasi alami dari perhitungan yang sama ini menunjukkan bahwa ini optimal.

Yonatan N