Einschränkungen mit in einem linearen Programm?

16

Annehmen

\begin{aligned} Mindest EIN & v e c (U) \\ unterliegen U_{ich, j} \leq max {U_{ich, k}, U_{k, j}}, ich, 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*}$

wo $U$ eine symmetrische $n\times n$ Matrix und $\mathrm{vec}(U)$ Reshapes $U$ in einen eindimensionalen Vektor mit $n^2$ Einträge.

Der Teil des obigen Programms, der mir Probleme ist $\max\{⋅,⋅\}$ . (Das Einschränken von Lösungen auf nichtnegative symmetrische Matrizen scheint unkompliziert zu sein.)

Vielen Dank im Voraus für jede Hilfe oder Hinweise!

optimization linear-programming N21
quelle

Aus irgendeinem Grund können Sie nicht beide Einschränkungen hinzufügen?

Aron Ahmadia

1

@AronAhmadia: Er kann nicht beide Bedingungen hinzufügen, da dies für alle

äquivalent wäre zu

. Ich glaube nicht, dass es eine LP-Neuformulierung dieses Problems gibt, aber es könnte eine MILP-Neuformulierung geben, auch wenn die Lösung dadurch wahrscheinlich teurer wird.

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: Wie groß soll

n

$n$ für die zu lösenden Probleme sein?

Geoff Oxberry

@Geoff: Danke! Ich hoffe letztendlich, ein großes

zu haben

n

$n$ , aber im Moment bin ich am meisten besorgt, eine vorläufige Lösung mit

n

$n$ kleiner als, sagen wir 100 oder sogar 10.

N21

Danke, dass du @GeoffOxberry geklärt hast. Ich habe mir das vor dem Posten nicht genau überlegt.

Aron Ahmadia

14

Bearbeiten: Lassen Sie uns diese Erklärung noch einmal versuchen, diesmal wenn ich wacher bin.

Es gibt drei große Probleme mit der Formulierung (in der Reihenfolge des Schweregrads):

Es gibt keine offensichtliche Neuformulierung des Problems, das offensichtlich glatt, konvex oder linear ist.
Es ist nicht glatt.
Es ist nicht unbedingt konvex.

Keine offensichtliche glatte / konvexe / lineare Neuformulierung

Zunächst einmal gibt es keine offensichtliche Neuformulierung jeder Einschränkung. Arons Vorschlag gilt für die allgemeinere Einschränkung , bei der eine Einschränkung wie durch die folgenden zwei äquivalenten Ungleichungen ersetzt wird:Die Neuformulierung ist nicht ideal. Jede Bedingung wurde durch lineare Bedingungen ersetzt, aber sie konvertiert ein nicht glattes nichtlineares Programm in ein lineares Programm, das um Größenordnungen schneller zu lösen ist. $\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$

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

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

min

$\min$

2 n

$2n$

Wolfgang weist darauf hin, dass es möglich sein könnte (er schließt keinen Beweis ein), die Einschränkungen durch Hinzufügen von Slack-Variablen linear und glatt umzuformulieren. Für jede Einschränkung in der ursprünglichen Formulierung muss eine Slack-Variable hinzugefügt werden. Dies bedeutet, dass wir in dieser Neuformulierung Einschränkungen hinzufügen . Außerdem wird jede Einschränkung durch (oder so) lineare Einschränkungen ersetzt. Der wahre Mörder ist, dass die Nichtglätte von den Randbedingungen zum Ziel verschoben wird, sodass die Formulierung von Wolfgang immer noch ein nichtglattes nichtlineares Programm ergibt. $\max$ $\max$ $n^2$ $\max$ $2n$

Es gibt keine Standard-Neuformulierung von Einschränkungen in einem mir bekannten Minimierungsproblem, nachdem ich mein Lehrbuch zur linearen Programmierung überprüft und eine Literaturrecherche durchgeführt habe. Dies bedeutet nicht, dass eine solche Neuformulierung nicht existiert. es bedeutet nur, dass ich nicht darauf gestoßen bin. Wenn ich raten müsste, würde ich sagen, dass es keine LP-Formulierung gibt. $\max$

Nichtglätte

Ungleichmäßigkeit bedeutet in diesem Zusammenhang, dass mindestens eine der Funktionen in der Formulierung (das Ziel oder die Nebenbedingungen) nicht zweimal kontinuierlich differenzierbar ist. Die nicht glatten Funktionen in dieser Formulierung sind die Funktionen. $\max$

Nichtglätte ist ein großes Problem, weil:

es macht Ihr Problem sofort nichtlinear
Die meisten nichtlinearen Programmierlöser übernehmen zweimal kontinuierlich differenzierbare Funktionen

Da Funktionen nicht einmal kontinuierlich differenzierbar sind, können Sie auch herkömmliche Gradientenabstiegsmethoden nicht ohne Schwierigkeiten anwenden. Nicht glatte nichtlineare Programmieralgorithmen sind langsamer als ihre glatten Gegenstücke. $\max$

Mögliche Nichtkonvexität

Ihr Problem könnte nicht konvex sein, da in "Standardform" für nichtlineare Programme (dh Ausdrücken aller Einschränkungen in der Form ) die lästigen Einschränkungen in Ihrem Formulierung sind $\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.$

Diese Funktionen sind konkav.

Beweis: In diesem Fall sind die Funktionen und beide konvex. Die Summe der konvexen Funktionen ist konvex, und das Multiplizieren einer konvexen Funktion mit -1 ergibt eine konkave Funktion. (QED.) $-U_{ij}$ $\max_{k}\{U_{ik}, U_{kj}\}$

Nur weil nicht konvex ist, heißt das nicht, dass Ihr Problem tatsächlich nicht konvex ist. Wenn Sie jedoch versuchen, ein Optimierungsproblem mit globaler Optimalität zu lösen, können Sie nur garantieren, dass ein konvexer Optimierungslöser dies tut Geben Sie ein globales Optimum zurück, wenn Ihr Problem konvex ist. Wenn Sie wirklich ein globales Optimum wünschen, müssen Sie feststellen, ob Ihre realisierbare Menge konvex ist (oder nicht). Fehlen solche Informationen, müssen Sie davon ausgehen, dass Ihr Problem möglicherweise nicht konvex ist, und Sie müssen Algorithmen verwenden, die nicht auf Konvexitätsinformationen beruhen. Selbst dann sind die Unstetigkeit und das Fehlen einer guten Neuformulierung viel größere Probleme. $\mathbf{g}$

Möglichkeiten zur Lösung des Problems

Geben Sie sich damit zufrieden, eine mögliche Lösung zu finden. In diesem Fall tue, was Aron gesagt hat, und ersetze durch die dann unter Verwendung einer Standard-LP-Neuformulierung als zwei separate Ungleichungen ausgedrückt werden können. Das resultierende Problem ist eine LP-Einschränkung des Problems, das Sie lösen möchten. es sollte sich relativ zu Ihrem ursprünglichen Problem schnell lösen lassen, und wenn es eine Lösung hat, ist diese Lösung für Ihr ursprüngliches Problem durchführbar, und sein Zielfunktionswert ist eine Untergrenze für den optimalen Zielfunktionswert Ihres ursprünglichen Problems.
$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,$
Versuchen Sie Ihr Glück mit Ihrer Formulierung, so wie sie mit einem Bundle-Löser für nicht reibungslose Programme ist. Ich habe nicht viel Erfahrung mit diesen Arten von Lösern. (Ein Kollege von mir verwendet sie für seine Recherchen.) Sie sind wahrscheinlich langsam, da sie keine abgeleiteten Informationen verwenden können. (Ich denke, sie verwenden stattdessen Subgradienten- oder Clarkes allgemeine Gradienteninformationen.) Es ist auch unwahrscheinlich, dass Sie große Probleminstanzen mit einem Bundle-Solver lösen können.

Geoff Oxberry
quelle

1

Geoff, gutes Zeug; Dies trifft die Kernpunkte und bietet viele konstruktive Einsichten und Vorschläge. Ich habe dafür gestimmt. Aber Sie scheinen die Nichtkonvexität als etwas zu behandeln, das von der Tatsache getrennt ist, dass es, wie Sie es ausdrückten, "keine Standardumformulierung der maximalen Beschränkungen in einem Minimierungsproblem gibt, von dem ich weiß". Ersteres ist jedoch genau der Grund, warum Letzteres nicht möglich ist. Nicht konvexe Bedingungen können nicht in linearer Programmierung ausgedrückt werden - Punkt! Dies ist ein nicht konvexes Problem, und es muss entweder in ein Problem mit gemischten ganzen Zahlen oder in eine andere angewandte Heuristik umformuliert werden.

Michael Grant

@MichaelGrant: Ich habe dieses Argument in den Revisionen 1 und 2 vor über einem Jahr vorgebracht und bin dann in einen langen Kommentarthread über meine Behauptung geraten, dass das Problem nicht konvex ist. (Siehe Tims Antwort weiter unten.) Wie ich mich erinnere, argumentierte Tim damals, dass eine Ungleichung von mit konkav eine mögliche Menge nicht konvex macht. Ich bin nicht sicher, warum ein konvexes Programm per Definition so ausgedrückt werden muss , dass für konvex ist. Ich hatte es satt, mit Tim darüber zu streiten; Ich sollte einige meiner vorherigen Änderungen rückgängig machen.

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}$

Geoff Oxberry

1

Es ist richtig, dass nichtkonvexe Nebenbedingungsfunktionen konvexe Mengen beschreiben können (tatsächlich deckt der Begriff der Quasikonvexität die meisten dieser Fälle ab). Fakt ist aber, dass eine nicht konvexe Menge in . Tims Behauptung ist für dieses spezielle Problem irrelevant. Es ist auch denkbar, dass der Schnittpunkt nicht konvexer Mengen konvex ist, aber das ist unwahrscheinlich.

x \leq max {y, z}

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

(x, y, z)

$(x,y,z)$

Michael Grant

1

Ja, Sie können diese bestimmte Aussage beweisen, da eine solche Menge das Hypogramm von ist und die Menge, die durch das Hypogramm einer Funktion definiert ist, konvex ist, wenn die Funktion konkav ist.

max {y, z}

$\max\{y,z\}$

Geoff Oxberry

3

Die Lösung für Ihre Frage lautet . $-\infty$

Sei Da und ein Randbedingung ist linear in , jeden positiven multiple von erfüllt die Einschränkungen. Daher ist .

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$

Todeshauch
quelle

Auf jeden Fall eine Lösung für die gestellte Frage. Ich vermute, dass das OP gewisse Einschränkung der Nicht- . In diesem Fall ist der optimale Zielfunktionswert möglicherweise nicht .

U

$U$

- \infty

$-\infty$

Geoff Oxberry

@ GeoffOxberry: Stimmt. Sogar mit Positivitätsbeschränkungen für lautet die Antwort . Die gestellte Form impliziert, dass es sich wirklich um eine Matrixoptimierungsfrage nach .

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$

Death Breath

2

Um die Bedingungen zu formulieren , erstellen wir Binärvariablen , , . Sei die Grenze der Variablen , dann müssen wir nur die folgenden Bedingungen hinzufügen: $f \le \max \{ f_1, f_2,...,f_n \}$ $n$ $b_i \in \{0,1\}$ $1 \le i \le n$ $M$ $f$

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

2) $\sum_i b_i = 1$

Normalerweise setze wenn wir den Wert von schätzen können . $M := max_i f_i - min_i f_i$ $f_i$

Kevin
quelle

1

Können Sie keine Slack-Variable einführen? Um die Bedingung schreiben Sie sie wie folgt: Dies hat eine unmögliche Lösung in Bezug auf das ursprüngliche Problem, wenn Sie s = unendlich wählen. Aber ich bin mir ziemlich sicher, dass Sie zeigen können, wenn Sie der einen Ausdruck hinzufügen (dh Sie möchten, dass so klein ist) wie möglich, vorzugsweise Null) und ausreichend groß ist , dann werden Sie eine machbare Lösung zurück , wenn das ursprüngliche Problem als unendlich machbare Lösungen mit objektivem Wert weniger hat.

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$

(Ein Beweis würde , dass, wenn und wenn , die Lösung nicht realisierbar ist, mit anderen Worten, ein Maß für die Unrealisierbarkeit bezüglich Wenn das Problem stabil ist, sollte es eine endliche Verbesserung des objektiven Funktionswerts für eine endliche Verletzung der Durchführbarkeit geben. Wenn Sie c größer als das Verhältnis zwischen Änderung des objektiven Werts und Verletzung der Durchführbarkeit wählen, dann die modifizierte Zielfunktion würde für Probleme wachsen , die in die unmögliche Region gehen.) $s_i>=\max(a_i)$ $x_i=s_i$ $s_i-\max(a_i)$

Wolfgang Bangerth
quelle

Es ist eine gute Idee. Angenommen, Ihr Beweis geht durch, dann wird das Problem darin bestehen, die Nichtlinearität und Nichtglätte von den Einschränkungen in das Ziel zu verschieben, die beide immer noch unerwünschte Eigenschaften in einer Formulierung sind.

Geoff Oxberry

Ich fürchte, das wird nicht funktionieren. Wenn die Mengen Variablen und keine Konstanten sind, ist Ihre ursprüngliche Einschränkung keine konvexe Menge in . Ihre umformulierte Menge von Bedingungen ist andererseits eine konvexe Menge in . Die beiden Abhängigkeiten können nicht gleichwertig sein.

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})$

Michael Grant

1

Ich kann den Kommentarbutton nicht finden ...

Wie Geoff betonte, handelt es sich um eine konkave Einschränkungsfunktion. Es spielt jedoch keine Rolle, ob die Funktion selbst konkav ist oder nicht. Konkave Funktionen unter linearen Bedingungen können konvexe Mengen sein (z. B. ). $log(x)<5$

Wenn es sich um eine konvexe Menge handelt, können Sie für Ihre Zielfunktion einen Gradientenabstieg durchführen, indem Sie so etwas wie Dykstra's_projection_algorithm verwenden , um zurück auf den Raum der Abhängigkeiten zu projizieren.

Tim
quelle

Upvoted für den Kommentar zu konkaven Funktionen; Ich hätte mehr über meine Erklärung nachdenken sollen. Es ist möglich, auf die realisierbare Menge zu projizieren, obwohl ich mir nicht sicher bin, ob Sie diese Algorithmen mit nicht glatten Einschränkungen anwenden könnten.

Geoff Oxberry

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

$x^2+y^2<5$

"Nicht-konvexe Probleme sind nur dann NP-hart, wenn sie eine NP-Anzahl möglicher Lösungen aufweisen." NP steht für "nicht deterministisches Polynom". Ich bin völlig verloren über das, wovon du sprichst. Zweitens erwähnte ich die Konkavität, weil lineare Funktionen konkav und konvex sind; Die Funktion ist nicht konvex. Nur weil die Funktion nicht glatt und stückweise linear ist, schließt dies die Möglichkeit einer LP-Neuformulierung nicht sofort aus.

Geoff Oxberry

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

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

Tut mir leid, ich musste den Kommentar kurz fassen, also habe ich NP für Nichtpolynom und P für Polynonom verwendet. Der Punkt war, dass nicht-konvexe Optimierung nicht immer NP-hart ist. Es ist nur NP-schwer, wenn die Anzahl der möglichen Lösungen SCHLECHTER als polynomisch ist. Sorry für die Verwirrung :) Du hast recht mit der Neuformulierung als linear. Sie schienen zu sagen: "Folglich gibt es keine Möglichkeit, Ihr Programm als lineares Programm umzuformulieren." Aufgrund der Nicht-Konvexität stellte ich nur fest, dass es nicht mit Konvexität, sondern mit Linearität zusammenhängt.

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
quelle

Einschränkungen mit in einem linearen Programm?

Antworten:

Keine offensichtliche glatte / konvexe / lineare Neuformulierung

Nichtglätte

Mögliche Nichtkonvexität

Möglichkeiten zur Lösung des Problems