Minimierung einer quadratischen Funktion mit nichtlinearen Einschränkungen

8

Was wären gute Methoden (und / oder Softwarepakete), um ein Problem zu lösen, das eine quadratische Funktion minimiert? , st 0 x i1 und Es gibt mehr Einschränkungen, von denen einige nicht linear (und nicht differenzierbar) sind, z. B. i x i 1 x i > a < b ?f(x)=ich=1N.(xich- -yich)20xich1ichxich1xich>ein<b

Ich denke an . FWIW, Matlab verwendet offenbar eine "Active-Set-Methode, ähnlich der von Gill et al.", Die eine etwas ungleichmäßige Leistung aufweist.N.100

laxxy
quelle
Update: Der Link in Arnolds Antwort unten ist nützlich. Für dieses spezielle Problem war es jedoch hilfreich, es als gemischtes ganzzahliges Problem umzuschreiben (Indikatoren als neue Variablen zu definieren) und einen gemischten ganzzahligen Löser zu verwenden (ich konnte CPLEX jedoch nicht zum Laufen bringen, da die Einschränkung anscheinend nicht "quadratisch genug" war " dafür).
laxxy

Antworten:

5

Sie sagen im Kommentar, dass Sie es nicht zum Laufen bringen können, da es nicht quadratisch genug ist. Ich sehe keinen Grund dafür. Das Problem kann leicht als quadratisches Programm mit gemischten ganzen Zahlen codiert werden.

Wenn ich Ihre Problemdefinition verstehe, möchten Sie die Summe der Variablen einschränken, die größer als ein Schwellenwert sind. Führen Sie eine binäre Variable ein, die angibt, ob x größer als a ist, und führen Sie eine weitere Variable z ein, die gleich x sein sollte, wenn dies gilt, und ansonsten null, und verwenden Sie die Summe der neuen Variablen.

Mit der MATLAB-Toolbox YALMIP zur Schnittstelle von CPLEX (oder Gurobi oder einem anderen MIQP-Solver) wird das Problem in Bruchteilen von Sekunden trivial gelöst. Hier ein zufälliges Beispiel, das sowohl mit einem manuell abgeleiteten Modell als auch mit einem Modell implementiert wurde, das die allgemeinen Modellierungsfunktionen in YALMIP nutzt

% Create random data
N = 100;
y = rand(N,1);
a = rand(N,1);
b = rand(1);

% Decision variables
x = sdpvar(N,1);
z = sdpvar(N,1);
d = binvar(N,1);

% Define objective
Objective = (x-y)'*(x-y)

% High-level model
Con1 = [0 <= x <= 1,0 <= z <=1];
Con2 = [implies(x-a>=0,d), implies(d,z==x), implies(1-d,z==0)]
Con3 = [sum(z) <= b];

% Solve problem
solvesdp([Con1,Con2,Con3],Objective)

% display solution
[double(x) a double(z)]

% Manually derived model
Con1 = [0 <= x <= 1,0 <= z <=1];
Con2 = [x-a <= d, -(1-d) <= x-z <= 1-d, z <= d];
Con3 = [sum(z) <= b];
Objective = (x-y)'*(x-y)
solvesdp([Con1,Con2,Con3],Objective)
[double(x) a double(z)]
Johan Löfberg
quelle