Algoritma yang tepat untuk pemrograman kuadratik non-cembung

Pertanyaan ini adalah tentang masalah pemrograman kuadratik dengan kendala kotak (kotak-QP), yaitu masalah optimasi formulir

meminimalkan $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}$ tunduk pada $\mathbf{x} \in [0,1]^n$ .

Jika positif semi-pasti, maka semuanya akan bagus dan cembung dan mudah, dan kita bisa menyelesaikan masalah dalam waktu polinomial. $A$

Di sisi lain, jika kita memiliki kendala integralitas , kita dapat dengan mudah menyelesaikan masalah dalam waktu dengan kekerasan. Untuk keperluan pertanyaan ini, ini cukup cepat. $\mathbf{x} \in \{0,1\}^n$ $O(2^n \cdot \mathrm{poly}(n))$

Tetapi bagaimana dengan kasus kontinu non-cembung? Apa algoritma yang paling cepat diketahui untuk QP kotak umum?

Sebagai contoh, dapatkah kita menyelesaikannya dalam waktu yang cukup eksponensial, misalnya, , atau apakah kompleksitas kasus terburuk dari algoritma yang paling dikenal adalah sesuatu yang jauh lebih buruk? $O(3^n \cdot \mathrm{poly}(n))$

Latar Belakang: Saya memiliki beberapa QP kotak yang cukup kecil yang sebenarnya ingin saya selesaikan, dan saya sedikit terkejut melihat betapa buruknya beberapa paket perangkat lunak komersial, bahkan untuk nilai sangat kecil . Saya mulai bertanya-tanya apakah ada penjelasan TCS untuk pengamatan ini. $n$

ds.algorithms optimization exp-time-algorithms Jukka Suomela
sumber

Bisakah Anda memecahkan bahkan untuk PSD

? Solusinya bisa irasional, bukan? Jika Anda ingin kehilangan aditif

mungkin seseorang bisa mendapatkan algoritma waktu eksponensial dengan melakukan pencarian brute-force pada grid yang cukup bagus. Hanya saran yang tidak jelas.

A

$A$

ϵ

$\epsilon$

Chandra Chekuri

Kelemahannya adalah bahwa "pangkalan" eksponen akan menjadi sekitar

, tetapi mungkin rekayasa jaringan yang cerdas dapat membantu untuk "kecil" dan

1 / ϵ

$1/\epsilon$

n

$n$

Suresh Venkat

@ChandraChekuri: Perkiraan baik-baik saja jika Anda dapat mencapai, misalnya,

. Namun, pemaksaan kasar pada grid yang halus tidak layak.

ϵ = 10^{- 9}

$\epsilon = 10^{-9}$

Jukka Suomela

Dengan eliminasi quantifier pada bidang tertutup nyata, selalu mungkin untuk menyelesaikan sistem ini dengan tepat.

Jika

diizinkan, Anda dapat mengoptimalkan fungsi pada setiap permukaan kubus hanya dengan menuliskan kriteria optimalitas orde pertama.

O (3^{n})

$O(3^n)$

Yoshio Okamoto

Jawaban:

Solusi optimal terletak pada beberapa wajah. Jadi, kita bisa melihat semua wajah kubus, dan menemukan semua titik stasioner pada masing-masing wajah.

Ini prosedur yang lebih konkret. Permukaan kubus dapat ditandai dengan dua set indeks disjoint dan . Untuk , kami memperbaiki , dan untuk kami memperbaiki . Misalkan terdiri dari entri yang belum diperbaiki yang tersisa dari $I_0$ $I_1$ $i \in I_0$ $x_i = 0$ $i \in I_1$ $x_i = 1$ $\tilde{x}$ . Perbaikan ini mengubah fungsi tujuan menjadi bentuk berikut: $x$

{\tilde{x}}^{⊤} \tilde{A} \tilde{x} + {\tilde{c}}^{⊤} \tilde{x} + d,

$\tilde{x}^{\top} \tilde{A} \tilde{x} + \tilde{c}^{\top} \tilde{x} + d,$

dengan dan , dan beberapa konstanta , dan kami ingin menemukan titik-titik stasioner dari fungsi ini dalam kondisi $\tilde{A}$ $\tilde{c}$ $d$ . $0 < \tilde{x} < 1$

Untuk tujuan ini, kami mengambil diferensiasi dari fungsi tujuan untuk memperoleh

\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.

$\frac{1}{2} \tilde{A} \tilde{x} + \tilde{c} = 0.$

Memecahkan sistem persamaan linear ini memberi Anda poin stasioner, kandidat untuk solusi optimal. Kami memeriksa semuanya, memeriksa kondisinya, dan memilih satu dengan nilai objektif minimum.

Kompleksitas waktu keseluruhan adalah sesuatu seperti karena jumlah wajah dari kubus adalah dan sistem persamaan linear dapat diselesaikan dalam waktu polinomial. Kompleksitas ruang adalah polinomial dalam $O(3^n \text{poly}(n))$ $n$ $3^n$ $n$ .

Yoshio Okamoto
sumber

f

$f$

@cody: Itu karena setiap polytope adalah penyatuan wajah yang terputus-putus.

Yoshio Okamoto

f

$f$

@cody: Properti masih berlaku, tetapi kita perlu menyelesaikan persamaan aljabar derajat lebih dari satu. Saya khawatir ini bukan hal sepele untuk kasus multivariat.

Yoshio Okamoto