Pytania otagowane jako optimization

ogólne pytania dotyczące wyboru najlepszego elementu z zestawu dostępnych alternatyw.

1
Jaki jest stan wiedzy w teorii algorytmów pamięci podręcznej?
Niedawno zainteresowałem się ogólnym problemem optymalizacji wykorzystania pamięci w sytuacji, gdy dostępny jest więcej niż jeden rodzaj pamięci, i istnieje kompromis między pojemnością danego segmentu pamięci a szybkością dostępu do niego. Znanym przykładem jest program decydujący, kiedy odczytywać / zapisywać w pamięci podręcznej procesora, pamięci RAM i dysku twardym (za …
1
Czy zerowa luka integralności oznacza zerową lukę dualności dla niektórych problemów?
Wiemy, że jeśli różnica między wartościami programu liczb całkowitych i jego dualności („dualność”) wynosi zero, wówczas liniowe relaksacje programowania programu liczb całkowitych i dualność relaksacji dopuszczają rozwiązania integralne (integralność zerowa) luka"). Chcę wiedzieć, czy konwersacja się utrzymuje, przynajmniej w niektórych przypadkach. Załóżmy, że mam program liczb całkowitych 0-1 , gdzie …
2
Złożoność optymalizacji w stosunku do grupy jednolitej
Jaka jest złożoność obliczeniowa optymalizacji różnych funkcji w grupie jednolitej ?U(n)U(n)\mathcal{U}(n) Typowe zadanie, często wynikające z teorii informacji kwantowej byłoby maksymalizując ilość typu (lub wyższych wielomiany rzędu w U ) w stosunku do wszystkich macierze jednostkowe U . Czy tego rodzaju optymalizacja jest wydajna (być może w przybliżeniu) do obliczenia, …
4
Teoretyczne badanie metod zejścia ze współrzędnymi
Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście współrzędnych odbywa się cyklicznie przez współrzędne, ustalając wszystko oprócz wybranego i minimalizując wzdłuż …
2
Precyzja numeryczna w metodzie sumy kwadratów?
Czytałem trochę o metodzie sumy kwadratów (SOS) z badania Baraka i Steurera oraz notatek z wykładu Baraka . W obu przypadkach zamiatają pod dywan dywaniki o dokładności numerycznej. Z mojego (co prawda ograniczonego) zrozumienia tej metody powinny być spełnione następujące warunki: Biorąc pod uwagę dowolny układ równań wielomianowych EEE względem …
1
Dokładne algorytmy dla niewypukłego programowania kwadratowego
To pytanie dotyczy kwadratowych problemów programistycznych z ograniczeniami pudełkowymi (box-QP), tj. Problemów optymalizacyjnych formularza minimalizuj zastrzeżeniem x ∈ [ 0 , 1 ] n .fa( x ) = xT.A x + cT.xf(x)=xTAx+cTxf(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}x ∈[0,1 ]nx∈[0,1]n\mathbf{x} \in [0,1]^n Gdyby było pozytywnie półokreślone, wtedy wszystko byłoby …
3
Skuteczne zastosowanie metod rozgałęzionych i związanych z problemami trudnymi dla NP
Rozgałęzienie i powiązanie to skuteczna heurystyka dla problemów wyszukiwania, a Wikipedia wymienia wiele trudnych problemów, w których zastosowano rozgałęzienie i powiązanie. Jednak nie udało mi się znaleźć referencji sugerujących, że jest to więcej niż „jedna metoda” rozwiązania tych problemów. Anegdotycznie słyszałem, że jedne z najlepszych heurystyki dla programowania SAT i …
2
Przegląd transformacji związanych z wykorzystaniem solverów SAT
Zaczynam badać możliwość polegania na rozwiązaniu SAT w celu rozwiązania problemu optymalizacji, który mnie interesuje, i obecnie szukam ankiety, która zawierałaby przykłady „sprytnych” przekształceń w warianty SAT (tj. Przekształcenia, które wynikają w problemie o rozsądnej wielkości, ponieważ nie jestem zainteresowany udowodnieniem wyników twardości, ale faktycznym rozwiązaniem problemu), w przybliżeniu w …
2
Jak nazywa się ten wariant problemu z ustawieniem pokrycia zestawu?
Wejściowego, to świat i rodzina podzbiorów , powiedzmy, . Zakładamy, że w podzbiory może obejmować , czyli .UUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Przyrostowe sekwencja Pokrycie jest ciągiem podzbiorów w , powiedzmy, , który spełniafaF{\cal F}ZA= { E1, E2), … , E| ZA|}A={E1,E2,…,E|A|}{\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\} 1) ,∀ E∈ A, …
1
Stabilność numeryczna metody Simplex
Algorytm simpleksowy jest często traktowany albo w ramach rzeczywistej arytmetyki, albo w świecie dyskretnym z dokładnymi obliczeniami. Wydaje się jednak, że jest najczęściej wdrażany za pomocą arytmetyki zmiennoprzecinkowej. Prowadzi to do pytania, czy algorytm simpleks należy traktować jako algorytm numeryczny, w szczególności w jaki sposób błędy zaokrąglenia wpływają na obliczenia. …
2
Minimalne maksymalne rozwiązania LP
Programowanie liniowe jest oczywiście obecnie bardzo dobrze rozumiane. Mamy dużo pracy, która charakteryzuje strukturę wykonalnych rozwiązań i strukturę rozwiązań optymalnych. Mamy silną dualność, algorytmy wielogodzinne itp. Ale co wiadomo na temat minimalnych maksymalnych rozwiązań LP? Lub równoważnie maksymalne minimalne rozwiązania? (To nie jest tak naprawdę pytanie badawcze, ale może możemy …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.