kramann.info
© Guido Kramann

Optimierung mittels modifizierter Gradientenverfahren

vorlesung_2013_12_17.zip - Beispiel-Implementierung des modifizierten Gradientenverfahrens mit Java als BlueJ-Projekt.

Als Grundlage zu optimierende Funktion wird im folgenden wirder z = x³-4*x+y³-16*y verwendet.
Zur Orientierung: Das gesuchte lokale Minimum liegt bei [x,y]=[2/sqrt(3),4/sqrt(3)]=[1,154700538,2,309401077].
Der folgende mit Scilab erstellte 3-D-Plot zeigt den Graph dieser Funktion im Bereich -3>x>3, -3>y>3.

Bild 0-1: z = x³-4*x+y³-16*y für -3>x>3, -3>y>3.

Zur Erstellung des Graphen wurde folgendes Scilab-Skript verwendet:
alpha und theta legen dabei den Blickwinke des Betrachters fest.

function z=f(x,y)
    z = x^3-4*x+y^3-16*y
endfunction

x=-3:0.1:3;
y=x;

fplot3d(x,y,f,alpha=5,theta=31);

Code 0-1: Scilab-Skript, um den Graph der Funktion z = x³-4*x+y³-16*y zu erstellen.

Wenn es keine Möglichkeit gibt, für den zu optimierenden Sachverhalt eine Gradientenfunktion zu bilden und ausgehend von einem aktuellen Punkt in die Richtung der Koordinatenachsen gesucht wird, um den Punkt mit dem größten Abstieg zu suchen, dann hat man das Problem, dass man mit größerer Näherung an den Zielpunkt die Suchweite sukkzessive verringern muß.
Folgende Umsetzung in Scilab löst dieses Problem am Beispiel einer speziellen schon mehrfach verwendeten Funktion z = x³-4*x+y³-16*y.
Für jede Suchrichtung wird untersucht, ob es eine Verbesserung bringt, den bisher verwendeten Richtungsvektor in seiner Länge zu halbieren oder zu verdoppeln.
Hierdurch werden die Schritte in der Nähe des gescuhten Wertepaares automatisch kürzer:

function z=f(x,y)
    z = x^3-4*x+y^3-16*y
endfunction

//Suchen ausgehend von einem aktuellen Punkt in Richtung [xricht,yricht] nach dem kleinsten Wert
//für die übergebene Funktion funk.
function alfabest=frichtung(x,y,xricht,yricht,funk)
    alfa = [-2.0,-1.0,-0.5,0.5,1.0,2.0];
    wert_best = funk(x+alfa(1)*xricht,y+alfa(1)*yricht);
    alfa_best = alfa(1);

    for i=2:6
        wert = funk(x+alfa(i)*xricht,y+alfa(i)*yricht);
        if wert < wert_best
            wert_best = wert;
            alfa_best = alfa(i);
        end
    end
    alfabest = alfa_best;
endfunction


//Matrix mit Einheitsvektoren U=[ex,ey] geben zu Beginn
//Suchrichtung vor:
U=[[1;0],[0;1]]

z=[4;4];
znull=z;
for i=1:15
    alfax = frichtung(z(1,1),z(2,1),U(1,1),U(2,1),f);
    alfay = frichtung(z(1,1),z(2,1),U(1,2),U(2,2),f);
    //Neuen Punkt in die Richtung setzen, die den größten Abstieg liefert:
    wertx = f(z(1,1)+alfax*U(1,1),z(2,1)+alfax*U(2,1));
    werty = f(z(1,1)+alfay*U(1,2),z(2,1)+alfay*U(2,2));
    if  wertx < werty
        z(1,1) = z(1,1) + alfax*U(1,1);
        z(2,1) = z(2,1) + alfax*U(2,1);
    else
        z(1,1) = z(1,1) + alfay*U(1,2);
        z(2,1) = z(2,1) + alfay*U(2,2);
    end    
    U(:,1) = alfax*U(:,1);
    U(:,2) = alfax*U(:,2);
    z=z
    fehler = abs(z(1)-2/sqrt(3))+abs(z(2)-4/sqrt(3))
end

Code 0-1: Beispiel für die Anwendung eines konkreten modifizierten Gradientenverfahrens am Beispiel der Funktion z = x³-4*x+y³-16*y.

Eine weitere Verbesserung liefert das Verfahren von Powell.
Gegenüber dem vorangegangenen Beispiel wird hier noch geschaut, welches die mittlere Suchrichtung ist und diese als eine der Suchrichtungen gesetzt.
Da die Gefahr besteht, dass U dadurch mit der Zeit linearabhängig wird, wird immer derjenige Richtungsvektor behalten, dessen Skalaprodukt mit dem neuen möglichst klein ist.
Als mittlere Suchrichtung wird dabei einfach der Differenzvektor zwischen aktueller Position und der Startposition verwendet, da die aktuelle Position die Summe aus allen Richtungen seit Beginn des Algorithmus darstellt.
Um diesen Summenvektor der aktuellen Situation anzupassen, wird er auf die Länge des zuletzt verwendeten Vektors gebracht.
Gegenüber dem vrangehenden Verfahren, ist der Fehler bei gleicher Interationsanzahl bei nachfolgdendem Verfahren etwas besser:

function z=f(x,y)
    z = x^3-4*x+y^3-16*y
endfunction

function alfabest=frichtung(x,y,xricht,yricht,funk)
    alfa = [-2.0,-1.0,-0.5,0.5,1.0,2.0];
    wert_best = funk(x+alfa(1)*xricht,y+alfa(1)*yricht);
    alfa_best = alfa(1);

    for i=2:6
        wert = funk(x+alfa(i)*xricht,y+alfa(i)*yricht);
        if wert < wert_best
            wert_best = wert;
            alfa_best = alfa(i);
        end
    end
    alfabest = alfa_best;
endfunction

U=[[1;0],[0;1]]

z=[4;4];
znull=z;
for i=1:15
    betrag=1.0;
    alfax = frichtung(z(1,1),z(2,1),U(1,1),U(2,1),f);
    alfay = frichtung(z(1,1),z(2,1),U(1,2),U(2,2),f);
    //Neuen Punkt setzen:
    wertx = f(z(1,1)+alfax*U(1,1),z(2,1)+alfax*U(2,1));
    werty = f(z(1,1)+alfay*U(1,2),z(2,1)+alfay*U(2,2));
    if  wertx < werty
        z(1,1) = z(1,1) + alfax*U(1,1);
        z(2,1) = z(2,1) + alfax*U(2,1);
        betrag = norm(alfax*U(:,1));
    else
        z(1,1) = z(1,1) + alfay*U(1,2);
        z(2,1) = z(2,1) + alfay*U(2,2);
        betrag = norm(alfay*U(:,2));
    end    
    U(:,1) = alfax*U(:,1);
    U(:,2) = alfax*U(:,2);

    //Konjugierte Richtung einsetzen:
    if  wertx < werty
        if abs((z-znull)'*U(:,1))<abs((z-znull)'*U(:,2))
            U(:,2)=U(:,1);
        end
        U(:,1) = betrag*(z-znull)/norm(z-znull);
    end        
    
    z=z
    fehler = abs(z(1)-2/sqrt(3))+abs(z(2)-4/sqrt(3))
end

Code 0-2: Implementierung eines modifizierten Gradientenverfahrens unter Verwendung konjugierter Richtungsvektoren nach Powell.