Ograniczenia dotyczące

16

Przypuszczać

minAvec(U)subject to Ui,jmax{Ui,k,Uk,j},i,j,k=1,,n

gdzie jest symetryczną macierzą n × n , a v e c ( U ) przekształca U w jednowymiarowy wektor z n 2 wejściami.Un×nvec(U)Un2

Część powyższego programu, która sprawia mi problemy, to . (Ograniczanie rozwiązań nieujemnych macierzy symetrycznych wydaje się proste).max{,}

Z góry dziękuję za wszelką pomoc lub referencje!

N21
źródło
z jakiegokolwiek powodu, dla którego nie można dodać obu ograniczeń?
Aron Ahmadia
1
@AronAhmadia: Nie może dodać obu ograniczeń, ponieważ byłoby to równoważne dla wszystkich i , j , k . Nie wydaje mi się, żeby można było przeformułować LP tego problemu, ale może być przeformułowanie MILP, nawet jeśli prawdopodobnie spowoduje to, że jego rozwiązanie będzie droższe. Ui,jmin{Ui,k,Uk,j}i,j,k
Geoff Oxberry
@ N21: Jak duży oczekujesz być dla problemów, które chcesz rozwiązać? n
Geoff Oxberry
@Geoff: Dzięki! Ostatecznie mam nadzieję, że będę mieć duże , ale teraz najbardziej martwię się o wstępne rozwiązanie z n mniejszą niż, powiedzmy 100, a nawet 10.nn
N21
Dzięki za wyjaśnienie @GeoffOxberry, nie do końca przemyślałem to przed opublikowaniem.
Aron Ahmadia

Odpowiedzi:

14

Edycja: Spróbujmy ponownie tego wyjaśnienia, tym razem, gdy bardziej się obudzę.

Istnieją trzy duże problemy z sformułowaniem (w kolejności ważności):

  1. Nie ma oczywistej przeformułowania problemu, który byłby oczywiście gładki, wypukły lub liniowy.
  2. Nie jest gładka.
  3. Niekoniecznie jest wypukły.

Brak wyraźnego przeformułowania gładkiego / wypukłego / liniowego

Po pierwsze, nie ma standardowego, oczywistego przeformułowania każdego ograniczenia. Sugestia Arona dotyczy bardziej powszechnego ograniczenia min , w którym ograniczenie takie jak U i jmin k { U i k , U k j } jest zastępowane przez dwie równoważne nierówności: U i jU i k ,maxmin

Uijmink{Uik,Ukj}
U i jU k j ,
UijUik,k
Przeformułowanie nie jest idealne, każde minimalne ograniczenie zostało zastąpione 2 n wiązaniami liniowymi, ale przekształca nie gładki nieliniowy program w program liniowy, który jest o rząd wielkości szybszy do rozwiązania.
UijUkj,k.
min2n

maxmaxn2max2n

max

Brak gładkości

max

Brak gładkości jest ogromnym problemem, ponieważ:

  • natychmiast sprawia, że ​​twój problem jest nieliniowy
  • większość nieliniowych solverów programistycznych przyjmuje dwa razy ciągle zmienne funkcje

max

Możliwa niewypukłość

g(x)0

Uijmaxk{Uik,Ukj}0,i,j,k.

Te funkcje są wklęsłe.

Uijmaxk{Uik,Ukj}

g

Opcje rozwiązania problemu

  • Uijmaxk{Uik,Ukj},i,j,k
    Uijmink{Uik,Ukj},i,j,k,
  • Spróbuj szczęścia na swoim sformułowaniu, tak jak w przypadku solvera pakietów dla programów niepłynnych. Nie mam dużego doświadczenia z tego typu rozwiązaniami. (Mój kolega wykorzystuje je w swoich badaniach.) Prawdopodobnie są one powolne, ponieważ nie mogą wykorzystywać informacji pochodnych. (Myślę, że zamiast tego używają uogólnionych lub uogólnionych informacji gradientowych Clarke'a). Jest również mało prawdopodobne, że będziesz w stanie rozwiązać duże problemy z rozwiązaniem pakietu.

Geoff Oxberry
źródło
1
Geoff, dobre rzeczy; uderza to w kluczowe punkty i oferuje wiele konstruktywnych informacji i sugestii. Głosowałem za tym. Ale wydaje się, że traktujesz niekonwersję jako coś odrębnego od faktu, że, jak to ujmujesz, „nie ma standardowego przeformułowania maksymalnych ograniczeń w znanym mi problemie minimalizacji”. Ale tak naprawdę to pierwsze jest właśnie tym, dlaczego drugie nie jest możliwe. Ograniczeń niewypukłych nie można wyrazić w programowaniu liniowym --- kropka! Jest to problem niewypukły i należy go przeformułować jako problem z mieszaną liczbą całkowitą lub zastosować inną heurystykę.
Michael Grant
g(x)0gg(x)0g
1
xmax{y,z}(x,y,z)
1
max{y,z}
3

U=(1111).
Avec(U)Ut±UminV(Avec(V))mint(Avec(tU))=
Oddech śmierci
źródło
U
U02tr(A^U)=A^U2A^2U2
2

fmax{f1,f2,...,fn}n bi{0,1}1inMf

ffi+(1bi)M,i

ibi=1

M:=maxifiminififi

Kevin
źródło
1

xi<=max(ai1,ai2,...,ain)
xi<=si
si>=ai1
si>=ai2
...
si>=ain
cmax(simax(ai),0)
simax(ai)c

si>=max(ai)xi=sisimax(ai) w przypadku problemów, które trafiają do nieosiągalnego regionu).

Wolfgang Bangerth
źródło
To dobry pomysł. Zakładając, że twój dowód przejdzie, kwestia staje się następnie przesuwaniem nieliniowości i nieuporządkowania z ograniczeń do celu, z których oba są wciąż niepożądanymi cechami w sformułowaniu.
Geoff Oxberry
aij(xi,ai1,ai2,...,ain)(xi,si,ai1,ai2,...,ain)
1

Nie mogę znaleźć przycisku komentarza ...

log(x)<5

Jeśli jest to zestaw wypukły, możesz wykonać opadanie gradientu na swojej funkcji celu, używając czegoś takiego jak algorytm_projektu Dykstry, aby rzutować z powrotem na przestrzeń ograniczeń.

Tim
źródło
Głosowano za komentarz na temat funkcji wklęsłych; Powinienem był więcej przemyśleć moje wyjaśnienie. Możliwe jest rzutowanie na wykonalny zestaw, choć nie jestem pewien, czy potrafiłbyś zastosować te algorytmy z ograniczeniami niepłynnymi.
Geoff Oxberry
x2+y2<5
„Problemy nie wypukłe są trudne dla NP, jeśli mają NP możliwe rozwiązania”. NP oznacza „niedeterministyczny wielomian”. Jestem całkowicie zagubiony w tym, o czym mówisz. Po drugie, wspomniałem o wklęsłości, ponieważ funkcje liniowe są wklęsłe i wypukłe; funkcja nie jest wypukła. Tylko dlatego, że funkcja nie jest gładka, a fragmentarycznie liniowa, nie wyklucza natychmiast możliwości istnienia przeformułowania LP.
Geoff Oxberry
Uijmink{Uik,Ukj}
Przepraszam, musiałem skrócić komentarz, więc użyłem NP dla wielomianu, a P dla wielomianu. Chodziło o to, że nie wypukła optymalizacja nie zawsze jest NP-trudna. Jest to trudne NP, jeśli liczba możliwych rozwiązań jest gorsza niż wielomianowa. Przepraszam za zamieszanie :) Masz rację co do przeformułowania jako liniowej. Wydaje się, że powiedziałeś „W związku z tym nie ma możliwości przeformułowania swojego programu jako programu liniowego”, z powodu niewypukłości, właśnie zauważyłem, że nie jest on związany z wypukłością, ale z liniowością.
Tim
0

0

U0An0

abccmax(a,b)b=ci,j,k

  1. Uij<Ujk=Uik
  2. Uik<Ujk=Uij
  3. Ujk<Uik=Uij
  4. Uij=Ujk=Uik

tG(t)Uij=tUij=Ujk=tUj=tUi=Uk=tG(t)

ps
źródło