Ograniczenia dotyczące

16

Przypuszczać

\begin{aligned} min A & v e c (U) \\ subject to U_{i, j} \leq max {U_{i, k}, U_{k, j}}, i, j, k = 1, \dots, n \end{aligned}

$\begin{align*} \min A &\mathrm{vec}(U) \\ &\text{subject to } U_{i,j} \leq \max\{U_{i,k}, U_{k,j}\}, \quad i,j,k = 1, \ldots, n \end{align*}$

gdzie jest symetryczną macierzą , a przekształca w jednowymiarowy wektor z wejściami. $U$ $n\times n$ $\mathrm{vec}(U)$ $U$ $n^2$

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!

optimization linear-programming

— 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

. 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.

U_{i, j} \leq min {U_{i, k}, U_{k, j}}

$U_{i,j} \leq \min\{U_{i,k}, U_{k,j}\}$

i, j, k

$i, j, k$

— Geoff Oxberry

@ N21: Jak duży oczekujesz

być dla problemów, które chcesz rozwiązać?

n

$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

mniejszą niż, powiedzmy 100, a nawet 10.

n

$n$

n

$n$

— N21

Dzięki za wyjaśnienie @GeoffOxberry, nie do końca przemyślałem to przed opublikowaniem.

— Aron Ahmadia

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):

Nie ma oczywistej przeformułowania problemu, który byłby oczywiście gładki, wypukły lub liniowy.
Nie jest gładka.
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 , w którym ograniczenie takie jak jest zastępowane przez dwie równoważne nierówności: $\max$ $\min$

U_{i j} \leq min_{k} {U_{i k}, U_{k j}}

$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$

U_{i j} \leq U_{i k}, \forall k

$U_{ij} \leq U_{ik}, \quad \forall k$

Przeformułowanie nie jest idealne, każde

ograniczenie zostało zastąpione

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.

U_{i j} \leq U_{k j}, \forall k .

$U_{ij} \leq U_{kj}, \quad \forall k.$

min

$\min$

2 n

$2n$

$\max$ $\max$ $n^2$ $\max$ $2n$

$\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ść

$\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$

U_{i j} - max_{k} {U_{i k}, U_{k j}} \leq 0, \forall i, j, k .

$U_{ij} - \max_{k}\{U_{ik}, U_{kj}\} \leq 0, \quad \forall i,j,k.$

Te funkcje są wklęsłe.

$-U_{ij}$ $\max_{k}\{U_{ik}, U_{kj}\}$

$\mathbf{g}$

Opcje rozwiązania problemu

$U_{i j} \leq max_{k} {U_{i k}, U_{k j}}, \forall i, j, k$ $U_{ij} \leq \max_{k}\{U_{ik}, U_{kj}\} , \quad \forall i,j,k$ $U_{i j} \leq min_{k} {U_{i k}, U_{k j}}, \forall i, j, k,$ $U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\} , \quad \forall 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) \leq 0

$\mathbf{g}(x) \leq \mathbf{0}$

g

$\mathbf{g}$

g (x) \leq 0

$\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$

g

$\mathbf{g}$

1

x \leq max {y, z}

$x \le \max\{y,z\}$

(x, y, z)

$(x,y,z)$

1

max {y, z}

$\max\{y,z\}$

3

$-\infty$

U = (\begin{matrix} 1 & \dots & 1 \\ ⋮ & ⋮ \\ 1 & \dots & 1 \end{matrix}) .

$U=\left(\begin{matrix} 1&\cdots &1\\ \vdots & & \vdots\\1&\cdots&1\end{matrix}\right).$

A \cdot vec (U)

$A\cdot\mbox{vec}(U)$

U

$U$

t

$t$

\pm U

$\pm U$

min_{V} (A \cdot vec (V)) \leq m i n_{t} (A \cdot vec (t U)) = - \infty

$\min_V(A\cdot\mbox{vec}(V)) \le min_{t}(A\cdot \mbox{vec}(tU))=-\infty$

— Oddech śmierci
źródło

U

$U$

- \infty

$-\infty$

U

$U$

\leq 0

$\le 0$

2 tr ({\hat{A}}^{*} U) = ‖ \hat{A} - U ‖^{2} - ‖ \hat{A} ‖^{2} - ‖ U ‖^{2}

$2\mbox{tr}(\hat{A}^\ast U)=\|\hat{A}-U\|^2-\|\hat{A}\|^2-\|U\|^2$

2

$f \le \max \{ f_1, f_2,...,f_n \}$ $n$ $b_i \in \{0,1\}$ $1 \le i \le n$ $M$ $f$

$f \le f_i + (1-b_i) M, \forall i$

$\sum_i b_i = 1$

$M := max_i f_i - min_i f_i$ $f_i$

— Kevin
źródło

1

x_{i} <= max (a_{i 1}, a_{i 2}, . . ., a_{i n})

$x_i <= \max(a_{i1}, a_{i2}, ..., a_{in})$

x_{i} <= s_{i}

$x_i <= s_i$

s_{i} >= a_{i 1}

$s_i >= a_{i1}$

s_{i} >= a_{i 2}

$s_i >= a_{i2}$

. . .

$...$

s_{i} >= a_{i n}

$s_i >= a_{in}$

c * max (s_{i} - max (a_{i}), 0)

$c*\max(s_i-\max(a_i), 0)$

s_{i} - max (a_{i})

$s_i-\max(a_i)$

c

$c$

$s_i>=\max(a_i)$ $x_i=s_i$ $s_i-\max(a_i)$ 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

a_{i j}

$a_{ij}$

(x_{i}, a_{i 1}, a_{i 2}, . . ., a_{i n})

$(x_i,a_{i1},a_{i2},...,a_{in})$

(x_{i}, s_{i}, a_{i 1}, a_{i 2}, . . ., a_{i n})

$(x_i,s_i,a_{i1},a_{i2},...,a_{in})$

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

x^{2} + y^{2} < 5

$x^2+y^2<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

U_{i j} \leq min_{k} {U_{i k}, U_{k j}}

$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$

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

$-\infty$ $0$

$U \ge 0$ $A$ $n$ $-\infty$ $0$

$a \le b \le c$ $c \le \max(a,b)$ $b=c$ $i,j,k$

$U_{ij} < U_{jk} = U_{ik}$
$U_{ik} < U_{jk} = U_{ij}$
$U_{jk} < U_{ik} = U_{ij}$
$U_{ij} = U_{jk} = U_{ik}$

$t$ $G(t)$ $U_{ij}=t$ $U_{ij}=U_{j k}=t$ $\ell$ $U_{j \ell}=t$ $U_{i\ell}=U_{k\ell}=t$ $G(t)$

— ps
źródło