Wie „schwer“ ist es, eine Polynomfunktion unter linearen Bedingungen zu maximieren?

Allgemeines Problem

Angenommen, wir haben eine multivariate Polynomfunktion $f(\mathbf{x})$ und mehrere lineare Funktionen . Was ist über die Komplexität der Lösung des folgenden Optimierungsproblems bekannt? $\ell_i(\mathbf{x})$

\begin{aligned} Maximieren & f (x) \\ Vorbehaltlich: & ℓ_{ich} (x) \leq 0 für alle ich \end{aligned}

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

Wir können davon ausgehen, dass der durch die Einschränkungen bestimmte Bereich begrenzt ist.

Verwandtes, aber spezifischeres Problem

Angenommen, wir haben ein begrenztes Polytop (dargestellt als Schnittpunkt einer Menge linearer Ungleichungen). Ich möchte das maximale Volumen eines (achsparallelen) Hyperrechtecks berechnen, das vollständig im Polytop enthalten ist. Wie komplex ist die Lösung dieses Problems?

Hilfe bei einem dieser Probleme wird sehr geschätzt.

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

Vielleicht möchten Sie sich dieses Papier ansehen .

Rodrigo de Azevedo

Möglicherweise möchten Sie Ihr zweites Problem separat in einem separaten Beitrag stellen.

Antworten:

Ihr Problem ist NP-schwer, selbst für Polynome des Grades 2. Die entscheidende Referenz ist

Theodore Motzkin und Ernst Strauss (1965)
"Maxima für Graphen und ein neuer Beweis eines Satzes von Turan"
Canadian Journal of Mathematics 17, S. 533-540

Motzkin und Strauss betrachten einen ungerichteten Graphen $G=(V,E)$ mit Scheitelpunkt gesetzt $V=\{1,2,\ldots,n\}$ . Sie zeigen, dass der optimale Zielwert des folgenden Optimierungsproblems mit dem Kehrwert übereinstimmt $1/\omega$ der Cliquennummer $\omega$ von $G$ ::

\begin{array}{rcl} max & \sum_{ich j \in E.} x_{ich} x_{j} \\ s . t . & \sum_{ich \in V.} x_{ich} = 1 \\ 0 \leq x_{ich} \leq 1 für alle ich \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*}$

Da die Berechnung der Cliquenzahl NP-hart ist, impliziert dies die NP-Härte der Maximierung einer multivariaten Polynomfunktion, die linearen Einschränkungen unterliegt.

Gamow
quelle

In einer optimalen Lösung ist der Wert von jedem

x_{v}

$x_v$ sollte sein

1 / ω

$1/\omega$ wenn

v

$v$ ist in der Clique (und

0

$0$ anderswo), und der optimale Zielwert stimmt mit überein

(1 - 1 / ω) / 2

$(1-1/\omega)/2$ . Dies liegt daran, Wert zu geben

1 / ω

$1/\omega$ zu jedem Clique Vertex bedeutet, dass jeder der

(ω^{2} - ω) / 2

$(\omega^2-\omega)/2$ Cliquenkanten tragen dazu bei

1 / ω^{2}

$1/\omega^2$ wählen. Die natürliche Verallgemeinerung derselben Berechnung zeigt, dass dies optimal ist.

Yonatan N