Finden einer Reihe maximal unterschiedlicher Lösungen mithilfe linearer Programmierung oder anderer Optimierungstechniken

Traditionell wird die lineare Programmierung verwendet, um die optimale Lösung für eine Reihe von Einschränkungen, Variablen und einem Ziel zu finden (alle als lineare Beziehungen bezeichnet). Manchmal, wenn das Ziel parallel zu einer Einschränkung ist, gibt es unendlich viele oder viele gleich gute optimale Lösungen. Ich frage nicht nach diesem letzteren Fall.

Ich bin mehr daran interessiert, viele Lösungen zu finden, die in der realisierbaren Region liegen, die durch meine Einschränkungen erzeugt wird. Ich möchte jedoch, dass die Lösungen, die ich finde, in der realisierbaren Region in dem Sinne „verstreut“ sind, dass sie maximal weit voneinander entfernt sind. Gibt es eine bekannte Möglichkeit, ohne mehrmals einen Solver auszuführen, mehrere Lösungen zu generieren und mithilfe der Zielfunktion zu erzwingen, dass die Lösungen getrennt werden sollten?

Beispielsweise kann jedes lineare Programm mit den Entscheidungen a und b und den Einschränkungen w <= a <= x und y <= b <= z 'dupliziert' werden, um zwei Lösungen zu finden. Unser neues lineares Programm hat die Variablen a1, a2, b1 und b2 und die Bedingungen w <= a1 <= x und w <= a2 <= x und ähnliche für b1, b2. Wenn es jedoch darum geht, eine objektive Funktion zu bilden, stoßen wir auf Schwierigkeiten, da wir keine anderen Normen als die L1-Norm verwenden können, ohne die Linearität zu verwerfen, und wir können die L1-Norm nicht wirklich verwenden, weil dies nicht möglich ist (soweit ich weiß) ), um absolute Werte zu codieren.

Vielleicht sollte ich mich mit konvexer Optimierung oder semidefiniter Programmierung befassen oder so?

Gibt es eine bekannte Möglichkeit, eine Reihe von Lösungen für ein lineares Programm zu generieren und ein Ziel zu verwenden, das den "Abstand" zwischen den Lösungen erzwingt?

Eine Heuristik mit linearer Programmierung

Ein Ansatz könnte darin bestehen, eine zufällige Zielfunktion auszuwählen und zu maximieren. Wiederholen Sie diesen Vorgang jedes Mal mit einem anderen Satz von Zielfunktionen.

$x_1,x_2,\dots,x_n$$\mathcal{C}$$c_1,c_2,\dots,c_n \in \mathbb{R}$$c_1 x_1 + \dots + c_n x_n$$\mathcal{C}$

Ich würde erwarten, dass diese Heuristik oft eine etwas verstreute Reihe von Lösungen findet - nicht unbedingt maximal gestreut (maximal weit voneinander entfernt), aber wahrscheinlich auch nicht zu nahe beieinander.

Maximierung des durchschnittlichen paarweisen L2-Abstands mithilfe quadratischer Programmierung

$x,y$$L_2$

$d(x,y)^2 = (x_1-y_1)^2+\cdots+(x_n-y_n)^2$$x$$y$$x$$y$

$k$$x^1,\dots,x^k \in \mathbb{R}^n$

dh die Funktion

$\mathcal{C}$$x^i$

$k$$k+1$$k$

Quadratische Programmierung ist schwieriger als lineare Programmierung, aber es gibt Selbstlöser, die quadratische Programmierprobleme für Sie lösen.

Maximierung des minimalen paarweisen L2-Abstands mithilfe von QCQP

$k$$t$$k$$x^1,\dots,x^k \in \mathbb{R}^n$$t$$d(x^i,x^j) \ge t$$i<j$. Dann kann dies als quadratisches Optimierungsprogramm mit quadratischen Einschränkungen, dh QCQP , formuliert werden . QCQP ist noch schwieriger, aber es gibt handelsübliche Löser für QCQP, die Sie auch ausprobieren können.

Ich habe einen Ansatz gefunden, um absolute Werte zu generieren.

$a_1$$a_2$$b_1$$b_2$$|a_1 - a_2| + |b_1 - b_2|$

Wir können "Slack-Variablen" abs_a und abs_b und die Einschränkungen einführen:

$b_1$$b_2$$\mathrm{abs_a}$$a_1$$a_2$$\mathrm{abs_a}$$a_1$$a_2$

$\mathrm{abs_a} + \mathrm{abs_b}$