Метод ломаных (метод Пиявского)

Метод ломаных разработан для оптимизации одномерных липшицируемых функций. Функция называется липшицируемой на [a, b], если существует такое число L (константа Липшица), что для любых x, y из [a, b] верно неравенство |f(x)-f(y)| <= L*|x-y|. Любая липшицируемая функция непрерывна, но обратное не верно. Достаточным условием липшицируемости является существование ограниченной непрерывной производной.

Идея метода такова: записав условие Липшица для некоторой точки g, в которой f(g) = h, получим: |f(x)-h| <= L|x-g|. Т.е. получено ограничение сверху и снизу на функцию f(x) в каждой точке x отрезка [a, b]. Записав пересечение этих условий для k вычисленных значений функции в k точках, получим на плоскости (x, y) область D, ограниченную сверху и снизу ломаными, в которой должен находиться график функции f. Новое, (k+1)-ое значение функции вычисляется в самой нижней точке области D. Затем процесс повторяется до выполнения условия останова. По окончании процесса берется лучшая из вычисленных точек.

Достоинством метода является то, что он всегда сходится к глобальному минимуму. К недостаткам метода можно отнести то, что он малоэффективен при минимизации значения функции, близкой к константе. Метод наиболее эффективен на функциях, которые в каждой точке графика или быстро растут или быстро убывают (в идеале - со скоростью, близкой к константе Липшица).

Если нашли ошибку в алгоритме - сообщите!

Реализации алгоритма на различных языках:

Реализация алгоритма на AlgoPascal:

unit Pijavsky;

declaration
    function F(X:Real):Real;

interface PijavskyOptimize;

implementation

(*********************************************************************
Процедура минимизации значения функции методом Пиявского (ломаных).

Параметры:
    A,B   - отрезок [A,B], на котором ведётся поиск.
    N     - число шагов поиска, >0;
    L     - константа Липшица для функции F, >0
    
Результат:
    Абсцисса лучшей точки из найденных.
    
Алгоритм вычисляет значение функции N+2 раза.
*********************************************************************)
function PijavskyOptimize(
    const A:Real;
    const B:Real;
    const N:Integer;
    const L:Real):Real;
var
    Points         : array of Real;
    Values         : array of Real;
    Ratings        : array of Real;
    
    I              : Integer;
    J              : Integer;
    
    T              : Real;
    
    MaxRating      : Real;
    MaxRatingPos   : Integer;
    
    MinPoint       : Real;
    MinValue       : Real;
begin
    SetBounds(Points,  [0,N+1]);
    SetBounds(Values,  [0,N+1]);
    SetBounds(Ratings, [1,N+1]);
    
    Points[0] := A;
    Points[1] := B;
    Values[0] := F(A);
    Values[1] := F(B);
    
    //добавляем новые точки
    for I:=2 to N+1 do
    begin
        //считаем рейтинги
        for J:=1 to I-1 do
            Ratings[J] := L/2*(Points[J]-Points[J-1]) -
                              1/2*(Values[J]+Values[J-1]);

        //выбираем максимальный рейтинг
        MaxRating    := Ratings[1];
        MaxRatingPos := 1;
        for J:=2 to I-1 do
            if Ratings[J]>MaxRating then
            begin
                MaxRatingPos := J;
                MaxRating    := Ratings[J];
            end;
            
        //вычисляем точку и функцию
        Points[I] := 1/2*(Points[MaxRatingPos]+Points[MaxRatingPos-1]) -
                         1/2/L*(Values[MaxRatingPos]-Values[MaxRatingPos-1]);
        Values[I] := F(Points[I]);
        
        //сортируем массив точек по возрастанию вставками
        for J:=I downto 2 do
            if Points[J]<Points[J-1] then
            begin
                T           := Points[J];
                Points[J]   := Points[J-1];
                Points[J-1] := T;
                
                T           := Values[J];
                Values[J]   := Values[J-1];
                Values[J-1] := T;
            end
            else
            begin
                //точка перемещена до своей позиции
                Break;
            end;
    end;
    
    //выбираем лучшую точку
    MinPoint := Points[0];
    MinValue := Values[0];
    for I:=1 to N+1 do
        if Values[I]<MinValue then
        begin
            MinValue := Values[I];
            MinPoint := Points[I];
        end;
        
    Result := MinPoint;
end;

end.

Бочканов Сергей, Быстрицкий Владимир
Copyright © 1999-2004
При поддержке проекта MANUAL.RU