Memaksimalkan fungsi cembung dengan batasan linier

maximize f (x) subject to A x = b

$\text{maximize } f(\mathbf{x}) \quad\text{subject to } \mathbf{Ax} = \mathbf{b}$

dimana

f (x) = \sum_{saya = 1}^{N} \sqrt{1 + \frac{x_{saya}^{4}}{{(\sum_{saya = 1}^{N} x_{saya}^{2})}^{2}}},

$f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{\left(\sum_{i=1}^{N}x_i^2\right)^2}},$

$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$ dan . $\mathbf{A} \in \mathbb{R}^{M\times N}$

Kita dapat melihat bahwa adalah cembung dan dalam bentuk . Dapat juga ditunjukkan bahwa dibatasi dalam . Saya tahu bahwa masalah maksimalisasi cembung NP-keras, secara umum. $f$ $\sqrt{1+y^2}$ $f$ $[\sqrt{2}, 2]$

Namun, dengan menggunakan sifat spesifik masalah, apakah mungkin untuk menyelesaikannya menggunakan perangkat lunak / paket optimasi cembung standar?

optimization Sooraj
sumber

Ada dua penjumlahan, satu di dalam yang lain, yang menggunakan "variabel loop" yang sama

i

$i$ . Tampaknya jelas dari konteks penggunaan

i

$i$ yang mana, tapi tolong perbaiki untuk kejelasan.

j_random_hacker

Jawaban:

Ya, Optimasi Cembung dengan batasan kesetaraan adalah NP-Hard secara umum. Namun, ada teknik matang yang menemukan solusi perkiraan yang sangat bagus untuk masalah optimasi cembung, seperti Koordinat Keturunan.

Misalkan Anda menggunakan penurunan koordinat dan matriks A memiliki peringkat . Anda dapat memperbaiki koordinat nk-1 dari solusi layak Anda dan kemudian vektor solusi dalam ruang solusi ditentukan secara unik oleh satu koordinat, misalnya . Dalam hal ini, Anda bisa mengambil turunan dari sehubungan dengan untuk menemukan maksimum dalam iterasi ini. $k$ $x = (x_1, x_2, x_3, ..., x_n)$ $x_i$ $f(\cdot)$ $x_i$

Kemudian kami memperbaiki koordinat nk-1 secara iteratif dan meningkatkan solusi sampai ditemukan yang optimal.

Strin
sumber

@RodrigodeAzevedo: Ini bukan kontradiksi atau mengejutkan bahwa LP, kasus khusus optimasi cembung, lebih mudah daripada kasus umum.

j_random_hacker