Maksymalizacja funkcji wypukłej z wiązaniem liniowym

maximize f (x) subject to A x = b

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

gdzie

f (x) = \sum_{i = 1}^{N} \sqrt{1 + \frac{x_{i}^{4}}{{(\sum_{i = 1}^{N} x_{i}^{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}$ i . $\mathbf{A} \in \mathbb{R}^{M\times N}$

Widzimy, że jest wypukły i ma postać . Można również wykazać, że jest ograniczone w . Wiem, że problem maksymalizacji wypukłej jest ogólnie trudny do NP. $f$ $\sqrt{1+y^2}$ $f$ $[\sqrt{2}, 2]$

Czy jednak, korzystając ze specyfiki problemu, można go rozwiązać za pomocą dowolnego standardowego oprogramowania / pakietu do optymalizacji wypukłych?

optimization

— Sooraj
źródło

Istnieją dwa podsumowania, jedno w drugim, które używają tej samej „zmiennej pętli” . Z kontekstu wydaje się jasne, które zastosowania są, ale proszę, popraw to dla jasności.

i

$i$

i

$i$

— j_random_hacker

Tak, Optymalizacja wypukła z ograniczeniem równości jest ogólnie NP-trudna. Istnieją jednak dojrzałe techniki, które znajdują bardzo ładne przybliżone rozwiązania problemów optymalizacji wypukłej, takie jak zejście współrzędnych.

Załóżmy, że używasz opadania współrzędnych, a macierz A ma rangę . Możesz naprawić współrzędne nk-1 swojego wykonalnego rozwiązania a następnie wektory rozwiązania w przestrzeni rozwiązania są jednoznacznie określone przez jedną współrzędną, na przykład . W takim przypadku możesz po prostu pobrać pochodną w odniesieniu do aby znaleźć maksimum w tej iteracji. $k$ $x = (x_1, x_2, x_3, ..., x_n)$ $x_i$ $f(\cdot)$ $x_i$

Następnie iteracyjnie naprawiamy współrzędną nk-1 i poprawiamy rozwiązanie, aż zostanie znaleziona w przybliżeniu optymalna.

— Strin
źródło

@RodrigodeAzevedo: Nie jest sprzecznością ani zaskoczeniem, że LP, szczególny przypadek optymalizacji wypukłej, jest łatwiejszy niż ogólny przypadek.

— j_random_hacker