Solusi titik tengah untuk program linier

Ada sebuah program linier yang saya inginkan bukan hanya solusi tetapi solusi yang sangat sentral di muka polytope yang mengasumsikan nilai minimal.

Secara apriori, kami berharap wajah meminimalkan harus berdimensi tinggi karena berbagai alasan, termasuk bahwa fungsi objektif yang diminimalkan adalah maksimum dari banyak kendala:

Minimalkan dengan dengan linear dan $\epsilon$ $f_i(\bar x) \leq \epsilon < 0$ $f_i$ $x_i > 0$ untuk semuadan. $i$ $\sum_i x_i = 1$

Kami tidak akan pernah mendapatkan properti seperti sentralitas dari algoritma simpleks saja. Namun, apakah ada algoritma titik interior biasa yang menunjukkan properti seperti itu? Apakah ada jaminan bahkan mereka akan menghindari simpul atau wajah dimensi yang lebih rendah bila memungkinkan?

Bahkan, saya mungkin puas dengan program kuadratik mudah yang menemukan titik tengah seluruh polytope karena sentralitas lebih penting daripada minimalitas, hanya sedikit ingin tahu apakah algoritma pemrograman linier lain menawarkan properti yang relevan.

Pembaruan: Saya telah mengurangi masalah mendasar menjadi masalah minimalisasi terbatas yang dapat dipecahkan dengan pengganda Lagrange, tetapi pertanyaan di atas tetap menarik.

ds.algorithms linear-algebra linear-programming Jeff Burdges
sumber

bukan pertanyaan Anda tetapi: menghitung centroid adalah # P-hard; Saya tidak yakin apa perkiraan terbaik, tetapi untuk beberapa aplikasi menempatkan polytope di posisi isotropik dan mengambil rata-rata banyak sampel seragam polinomal dari (cukup) polytope mencukupi. lihat catatan ini, Lemma 15 misalnya: cc.gatech.edu/~vempala/acg/notes.pdf

Sasho Nikolov

apakah ini lebih merupakan pertanyaan teoretis atau lebih praktis? mungkin akan layak untuk menghasilkan semua simpul dari wajah optimal dan kemudian menggunakan beberapa kombinasi cembung yang sesuai dari mereka.

Anonim

Jawaban:

Saya punya beberapa pengamatan yang terlalu panjang untuk dikomentari. Berikut ringkasannya.

Algoritma apa pun untuk menyelesaikan masalah Anda secara tepat dapat digunakan untuk menyelesaikan program linier dengan tepat (yaitu, "pemrograman linear yang kuat", yang digunakan dalam solusi Sariel, dan saat ini tidak memiliki algoritma waktu polinomial).
Tindak lanjut alami adalah jika solusi perkiraan (yaitu, "pemrograman linear lemah") dapat memberikan solusi. Walaupun jawabannya adalah ya, tampaknya kondisi berhenti untuk prosedur ini membutuhkan jumlah yang, setahu saya, tidak dapat dihitung dalam waktu polinomial. (yaitu, algoritma menemukan sesuatu yang baik, tapi sertifikasi ini sulit.) Saran utama saya di sini adalah untuk membuat definisi bermakna dari " solusi -optimal" untuk masalah Anda, dalam hal pendekatan ini adalah penurut. (Strategi ini secara efektif mengusir wajah-wajah kecil dari polyhedron.) $\epsilon$

Secara umum, sambil memikirkan pernyataan masalah Anda saat ini, saya terus mempertimbangkan efisiensi. Tapi ada intuisi yang masuk akal untuk ini: benda-benda yang kita lempar - simpul, wajah, dll. - terpisah, dan berlimpah secara eksponensial.

(1.) Misalkan kita memiliki algoritma yang secara tepat menyelesaikan masalah Anda. Perhatikan bahwa titik terbuka dari wajah apa pun yang berisi titik tengah yang disediakan akan menjadi solusi tepat untuk program linier asli. Jadi lanjutkan sebagai berikut. Tambahkan batasan linear baru yang mengatakan bahwa nilai obyektif asli harus sama dengan yang optimal (yang sekarang kita ketahui), dan tetapkan pepatah obyektif baru untuk memaksimalkan koordinat pertama dari solusi. Ulangi prosedur ini satu kali untuk setiap dimensi, setiap kali menambahkan kendala dan memilih koordinat baru untuk memaksimalkan. Proses ini akan mengurangi dimensi solusi setiap kali; tentu saja, ketika proses selesai, kami memiliki set affine 0-dimensi, yang berarti satu titik. Jadi dengan $\mathcal O(d)$ iterasi dari algoritma penyelesaian titik tengah Anda (dan hanya meningkatkan deskripsi masalah dengan jumlah polinomial dalam setiap kali), pemrograman linier yang kuat diselesaikan. Ini menunjukkan bahwa sementara solusi Sariel memerlukan pemrograman linier yang kuat, solusi tepat untuk pertanyaan Anda tidak dapat menghindarinya. ( Sunting : perhatikan bahwa bukti saya mengandaikan polihedron kecil (polytope) sebagai input; jika tidak, ia harus bekerja sedikit lebih keras untuk menemukan simpul.) $d$

(2.) Berikut ini adalah skema iteratif, menggunakan pemecah cembung penuh di setiap iterasi, yang solusinya akan menyatu dengan gagasan ringan solusi titik tengah. Pilih urutan parameter penalti yang positif namun menurun ; masuk akal untuk memiliki ini turun secara geometris, yaitu . Sekarang, untuk setiap , kira-kira meminimalkan fungsi cembung $\{\lambda_i\}_{i=1}^\infty\downarrow 0$ $\lambda_i = 2^{-i}$ $i$

⟨ c, x ⟩ - λ_{i} \sum_{j = 1}^{m} \ln (⟨ a_{j}, x ⟩ - b),

$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$

$\langle c,x\rangle$ $j$ $m$ $\lambda_i$ $\tau$ $\lambda_i$ berkurang, tujuan linier asli pada akhirnya akan mendominasi beberapa hambatan rumit yang membuat Anda dari wajah yang sesuai, tetapi tidak akan berdampak pada hambatan yang membuat Anda dari batas-batas lain, khususnya yang dari wajah target.

$\lambda$ $\lambda$

Semua kondisi yang dapat saya hentikan memiliki kesulitan komputasi semacam ini. (Selain itu, banyak lagi yang dapat digunakan untuk mengubah ini menjadi pemecah pemrograman linier yang kuat.)

$\epsilon$ $\lambda$ $\tau$ $\epsilon$

(Beberapa komentar terakhir.) Tampaknya gagasan tentang "titik tengah" sangat penting; Komentar Sasho menunjukkan bahwa centroid (pusat massa?) Adalah masalah yang sangat sulit, sedangkan menemukan, katakanlah, bola bertulis terbesar adalah mudah. Hambatan logaritmik yang saya sarankan di atas secara umum tidak akan konsisten dengan salah satu dari konsep titik tengah ini. Di sisi lain, untuk penghalang dan bola, Anda bisa mendapatkan batas bawah pada jarak dari centroid ke batas relatif wajah; mungkin ini lebih bermanfaat untukmu?

Terakhir, dari uraian Anda, saya yakin maksud Anda adalah "wajah target" untuk memiliki dimensi setinggi mungkin? Ini didefinisikan dengan baik, namun ada juga wajah solusi untuk semua dimensi yang mungkin lebih kecil juga. Bagaimanapun, baik pendekatan Sariel dan pendekatan penghalang di atas akan bekerja dengan wajah dimensi terbesar.

matus
sumber

\sum_{i} f_{i} (x)^{2} + \sum_{j} x_{j}^{2}

$\sum_i f_i(x)^2 + \sum_j x_j^2$

\sum_{j} x_{j} = 1

$\sum_j x_j = 1$

x

$x$

ϵ

$\epsilon$

ϵ

$\epsilon$ diminimalkan untuk membantu kendala berkembang lebih cepat. Terimakasih Meskipun! :)

Jeff Burdges

x

$x$

Saya tidak mengerti poin tentang "pemrograman linear yang kuat" dan saya belum pernah mendengar ungkapan ini sebelumnya. tidak diketahui bagaimana menyelesaikan LP dalam waktu polinomial yang kuat. tetapi memecahkan LP dalam polinomial waktu dalam deskripsi input (yaitu waktu polinomial lemah) tentu saja diketahui. jika OP menginginkan algoritma berjalan dalam waktu polinomial yang lemah maka solusi Sariel + algoritma titik interior poli-waktu akan melakukan pekerjaan, bukan?

Sasho Nikolov

τ

$\tau$

τ

$\tau$

@SashoNikolov, sekarang saya berpikir tentang hal itu, gagasan optimalitas yang sama (dengan masalah yang sama) dapat diterapkan ke dalam solusi Sariel, misalnya dengan memperlakukan kendala yang berada dalam beberapa toleransi kecil untuk benar-benar ketat, dan menyetel nilai ini dengan tepat. Saya akan memperbarui solusi saya malam ini.

matus

Pertama temukan solusi optimal, kemudian tambahkan batasan linier bahwa solusi harus memiliki nilai yang sama dengan optimal yang Anda inginkan, dan nyatakan kembali LP Anda sebagai orang yang mencari bola terbesar di dalam wilayah yang layak. Selesaikan LP yang dimodifikasi ini, dan Anda mendapatkan apa yang Anda inginkan.

Mengapa masalah kedua dapat diselesaikan dengan menggunakan LP adalah masalah lucu stnadard di Computational Geometry ...

==============

$h \equiv cx = \alpha$ $\min c x$ $P$ $P \cap h$

$v$ $v$ $v$ $\alpha$

Jadi, untuk musim panas: (A) pecahkan LP untuk menemukan nilai optimal. (B) Hitung subruang dimensi terkecil yang berisi solusi layak dengan nilai optimal. (C) Tulis ulang LP asli dalam subpsace affine ini (yaitu, menjatuhkan semua dimensi yang tidak relevan), menambahkan variabel, dan mengubahnya menjadi LP untuk menemukan bola terbesar di dalam polytope ini.

Sariel Har-Peled
sumber

Apa yang dimaksud dengan "bola terbesar" dalam polyhedron bukan dari dimensi penuh?

Kristoffer Arnsfelt Hansen

@KristofferArnsfeltHansen polyhedron pasti adalah cembung yang terletak di subruang affine dari beberapa dimensi.

Sasho Nikolov

Agar ini berfungsi, Anda harus menentukan batasan yang membatasi Anda pada wajah yang Anda temukan di langkah pertama. Anda juga perlu tahu bahwa solusinya konstan di seluruh wajah ini (mungkin kelonggaran komplementer akan mengungkapkan ini)

Suresh Venkat

Apakah ada cara untuk melakukan langkah-langkah setelah optimasi awal dalam waktu polinomial? Seperti yang tertulis, tampaknya memerlukan pertimbangan semua simpul di wajah target, yang mungkin ada banyak secara eksponensial.

matus

d

$d$

v

$v$