Santai kendala dalam pengoptimalan

Saya memiliki pertanyaan kelayakan yang dapat dibingkai sebagai berikut. Saya diberi titik dalam ruang vektor dimensional, dan saya ingin mencari titik terdekat ke yang memenuhi seperangkat " kendala" dari formulir $p$ $d$ $q$ $p$ $\ell_0$

Diberikan himpunan , paling banyak dari dapat berupa nol. $S \in [1\ldots d]$ $\{q_j, j \in S\}$

Gagasan kedekatan bervariasi, tetapi untuk saat ini cukup untuk mengasumsikan jarak yang nyaman seperti . $\ell_2^2$

Apakah ada relaksasi yang diketahui untuk kendala linear yang "baik" dalam arti memberikan "cukup dekat" polytope untuk mendekati kendala asli, di mana saya juga cukup fleksibel pada definisi "cukup dekat"

ds.algorithms approximation-algorithms linear-programming Suresh Venkat
sumber

Apakah kendala diperbolehkan untuk bergantung secara non-linear pada ?

p

$p$

Warren Schudy

Bisakah Anda menguraikan jenis polytope apa yang Anda cari? Cembung hull poin layak poin dengan paling banyak satu koordinat non-nol adalah , jadi tidak ada harapan pendekatan polihedral yang baik dari set poin layak .

q

$q$

R^{d}

$\mathcal{R}^d$

q

$q$

Warren Schudy

Jika adalah sebuah konstanta yang dikenal di muka maka untuk setiap jarak konstan Anda dapat dengan mudah menghitung poin layak yang berada dalam dari (melihat kendala tunggal saja). Untuk beberapa metrik, poin yang layak adalah penyatuan polytopes; untuk orang lain, Anda mungkin harus memperkirakannya dengan cara itu atau menggunakan oracle pemisah. Kemudian tulis batasan linear yang menyandikan bahwa ada di dalam cembung lambungnya.

p

$p$

δ

$\delta$

δ

$\delta$

p

$p$

q

$q$

Warren Schudy

@warren: kendala bergantung secara linier pada p, tetapi p itu sendiri bukan konstanta (melainkan, itu input untuk masalah). Kendala adalah dari jenis di atas, atau kendala linier pada q_i.

Suresh Venkat

Jawaban:

Saya tidak yakin apakah saya memahami masalahnya dengan benar, tetapi seperti yang tertulis, masalahnya tampaknya mengakui beberapa penyederhanaan, dan khususnya masalah dalam kasus ₂² setara dengan penutup vertex berbobot minimum jika saya tidak salah.

Tanpa kehilangan sifat umum kita dapat mengasumsikan bahwa | S | = 2 di setiap kendala, karena kendala dengan | S |> 2 setara dengan himpunan kendala di mana S menjalankan semua pasangan elemen dalam himpunan S asli . Oleh karena itu, batasan ℓ ₀ dapat divisualisasikan sebagai grafik G dengan d simpul. Menggunakan grafik G , kendala dapat disajikan kembali sebagai berikut: set simpul sesuai dengan koordinat saya dengan q _i = 0 harus menjadi penutup vertex dari G .
Asumsikan jarak didefinisikan oleh ℓ ₂² atau beberapa norma. Dalam kasus ini, sembarang titik q dapat ditransformasikan menjadi titik q ′ yang memenuhi setiap i , q ′ _i ∈ {0, p _i }, cukup dengan mengatur dan transformasi ini tidak pernah meningkatkan jarak dari titik p . Secara khusus, jika jarak adalah jumlah dari jarak koordinat-bijaksana (seperti dalam kasus jarak ²₂² ), masalahnya persis sama dengan penutup simpul minimum-berat. $q_{i}^{'} = {\begin{cases} p_{i}, & q_{i} \neq 0, \\ 0, & q_{i} = 0, \end{cases}$ $q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases}$

Adapun relaksasi LP masalah penutup verteks, pencarian cepat mengarah ke misalnya catatan kuliah (Kuliah 9) oleh Uriel Feige .

Tsuyoshi Ito
sumber

Cukup menarik. Saya suka pengamatan tentang | S | tidak perlu lebih dari 2

Suresh Venkat

Ada satu hal yang tidak berhasil. Variabel secara umum dapat arbitrer (bukan antara nol dan satu). Jadi, Anda tidak dapat benar-benar menyandikan batasan LP untuk "variabel yang disetel ke nol harus membentuk penutup simpul". Ini menjadi masalah (yang seharusnya saya sebutkan) karena ada kendala (linear) lain pada koordinat yang harus dimasukkan juga.

Suresh Venkat

@ Suresh: Jika Anda benar-benar berpikir bahwa Anda telah menyebutkannya, Anda selalu dapat mengubah pertanyaan.

Tsuyoshi Ito

@ Suresh: Saya bermaksud mengatakan, "Jika Anda benar-benar berpikir bahwa Anda seharusnya menyebutkannya ...."

Tsuyoshi Ito