Matlab: Optimierung mit Ungleichungsbedingung

[xornado]

Hallo Ihr lieben,

ich sitz gerade vor einem - für mich verzwicktem - Problem:

Ich möchte mit Matlab eine funktion f(.) von sagen wir zwei variablen (x,y) optimieren (max oder min, egal), wobei im Optimum gelten soll: x<y (oder x<=y, auch ok).

Bisher hatte ich die zielfunktion f(.) so geschrieben, dass in der letzten zeile steht

if y>=x f=-1*10^20 (bei einer maximierung),

da hatte ich also sozusagen einen strafterm eingefügt.

Nun meine Frage: kennt jemand von euch eine Matlabfunktion / eine user-defined-function, wo ich solche restriktionen wie x<y oder so mit in der optimierungszeile verbauen kann? bzw weiss jemand, wie ich das mit matlab boardmitteln schaffe?

vielen dank für euren support,
X

 

[mfb]

Du kannst es ähnlich umsetzen wie eindimensionale Beschränkungen oft gemacht werden: Direkt in der Parameterwahl beschränken.

Hier beispielsweise: Optimiere f(x,x+z^2)
x+z^2 >=x, somit ist deine Randbedingung direkt erfüllt. Und am Ende rechnest du y=x+z^2 aus.

 

[TealC]

Wenn Du Zugang zur Optimisation Toolbox hast, ist fmincon die Antwort auf Dein Problem:

http://www.caspur.it/risorse/softappl/doc/matlab_help/toolbox/optim/fmincon.html

Für Dein Beispiel, würde man einfach A = [-1, 1] und b = 0 wählen. Für lineare Nebenbedingungen ist das im Normalfall effizienter als Strafterme oder Reparametrisierungen.

 

[ROOT]

Kenn mich jetzt mit Matlab-Optimierern im speziellen nicht aus, normalerweise bringt man die NB aber einfach in eine Form g(x,y,...) < 0 bzw. h(x,y,...) = 0, in deinem Fall also einfach x-y < 0.
Das kannste da sicher irgendwo eingeben, und dann isses nur noch ein Standardproblem mit linearen NB.

 

[xornado]

@mfb: danke für den trick, daran hatte ich noch gar nicht gedacht, hihi. gut für die toolbox

@tealc: genau so was habe ich gesucht, danke dir. also bedeutet das

Ax<=b ? Ich dachte immer da steht Ax=b..nagut, wer lesen kann..dann kann ich das ja einfach so einbringen merci!
aber gleich noch hinterher: bekomme ich dann auch so sachen wie x^2<y mit rein, also über diese nebenbedingung? danke dir!

@root: merci merci, das hatte tealc oben geschrieben. mir fallen nur immer nicht die technischen begriffe für derlei dinge ein

merci an euch!

 

[TealC]

Nichtlineare Bedingungen kannst Du bei fmincon auch eingeben ueber den nonlcon Term. Siehe ein wenig weiter unten in der oben verlinkten Dokumentation.

Ich weiß allerdings nicht, was fmincon da tut und ob es eine effiziente Implementierung ist. Optimierung unter nichtlinearen Nebenbedingungen ist ein sehr komplexes Thema und je nach Problemstellung führen unterschiedliche Ansaetze zum Erfolg.

In jedem Fall, lohnt es sich, wie auch fuer die Zielfunktion die Gradienten mitzuliefern.
options = optimset('GradConstr','on')

Also fuer das Beispiel, x^2 - y <= 0, koennte @mycon so aussehen:

function [c,ceq,GC,GCeq] = mycon(x)
c = x(1)^2 - y % Nonlinear inequalities at x
ceq = 0 % Nonlinear equalities at x
if nargout > 2 % nonlcon called with 4 outputs
GC = [2 * x(1), 1] % Gradients of the inequalities
GCeq = [0, 0] % Gradients of the equalities
end

Wenn Du so etwas machst, auf jeden Fall immer die exit flag checken. Sonst kann es sein, dass er Unsinn ausspuckt und Du denkst es waere die Loesung.


Edit: Noch eine kleine Anmerkung. Normalerweise ist es keine sonderlich gute Idee ueberhaupt zu versuchen unter nichtlinearen Nebenbedingungen zu optimieren. Wenn Dein Problem fuer den Computer nicht sowieso trivial ist und es irgendwie geht, ist es besser die Kuhn-Tucker Bedingungen abzuleiten und mit Slacks in ein nichtlineares Gleichungssystem umzuschreiben.

 

[xornado]

da war ja mal was... leider ist das problem (aus meiner sicht) irgendwie ugly..aber vvlt kannst du mir ja einen "anstoss" geben:

gegeben:
u(e,w,b)=w-c(e)-a*max[ (e-w) - (w-c(e)), 0] - b*max[ (w-c(e) - (e-w),0]

c ist eine stückweise lineare funktion, definiert zwischen e=0 und 100.
generell geht es hier also darum, gegeben dem LOHN w (exogen) und den verhaltensparametern a,b, den optimalen arbeitseinsatz e* zwischen 0..100 zu berechnen.

sagen wir also, dieser ist e*.

Nun will ich via Maximum Likelihood die nutzenparameter a,b bestimmen, und zwar unter der nebenbedingung a<b. seien also e_i die gemessenen einsatzlevel aus einem experiment, und e* die jeweils "optimalen" gegeben einer kombination aus a,b:

dann also (so nach dem motto): minimiere die summe der quadrierten differenzen aus N gemessenen arbeitseinsätzen und den "optimalen" einsätzen, verändere dabei a,b.

kann ich das denn irgendwie schlank aufstellen? vom gefühl her glaub ich das ja nicht

 

[TealC]

Ohje, ist beides nicht mein Thema, weder der Oekonomie Teil, noch Max Likelihood.

Mein Gefuehl sagt mir, dass das schwierig wird. Geschachtelte Optimierung, beide nichtlinear, das innere Problem ist schon nicht trivial und das aeussere eine Katastrophe (hochdimensional und nicht einmal konkav). Du muesstest schon ziemlich viel Glueck haben, wenn Du das einfach in einen vorgefertigten Optimierer stecken koenntest.

Wie auch immer, probieren kannst Du es natuerlich trotzdem. Einfach beide geschachtelt in fmincon, vielleicht spuckt er ja sinnvolle Parameter aus.

Wenn das nicht passt, musst Du eben anfangen kompliziertere Dinge zu tun.

Am schoensten waere es, wenn Du hinreichende und notwendige Bedingungen fuer das innere Problem bekommen koenntest. Wahrscheinlich muss man dafuer c(e) aendern. Dann kannst die Bedingungen einfach einsetzen. Sollten die Bedingungen nur notwendig sein, ist es auch nicht sonderlich tragisch. Ist dann zwar nicht ganz legal, stoert aber nur selten die Leute so wirklich.

Wenn das nicht geht, koenntest Du auch versuchen, das innere Problem zu approximieren. Also fuer viele verschiedene Werte von a,b und w, e* ausrechnen. Darueber eine Approximation legen und diese in das aeussere Problem einsetzen.

Es gibt sicher zahlreiche andere Ansaetze, wie gesagt, ist nicht mein Thema.

Mein groesseres Problem und das ist wohl eher eine grundsaetzliche Kritik an dieser Art Parameter zu schaetzen, ist, dass Du zwar ein lokales Optimum finden wirst, aber dann nicht weisst, ob es das globale ist. Das bedeutet, der Solver spuckt Dir zwar ein a und b aus, aber Du kannst nie sicher sein, ob das Ergebnis richtig ist.

Zu guter letzt: Bist Du Dir sicher, dass Du Max Likelihood nicht verwechselst? Die Summe der quadrierten Differenzen zu minimieren klingt mir eher nach GMM.

Wie auch immer... zunaechst ist es sicherlich am einfachsten mal fmincon in fmincon einzusetzen. Ich wuerde an Deiner Stelle vielleicht versuchen, das Problem erst einmal zu vereinfachen, zum Beispiel c(e) linear anzunehmen. und zu schauen, ob Du dafuer ein Ergebnis bekommst.

Was ist das ueberhaupt? Eine Diplom-/Masterarbeit?

 

[xornado]

hi tealc, danke für die tips.

die approximationen an c(e) habe ich schon versucht, klappt. die innere optimierung klappt auch, das problem (suche optimales "e*") ist konvex im notwendigen bereich,für alle parameter a,b>0.

und ja, das ist ML. natürlich habe ich noch -n ln(sigma) weggelassen

und zu guter letzt, nein nein, hier geht es nur um ein papier und dass geschrieben wird und ich überlege, wie da die schätzungen so sind.

besten dank nochmal,
x