Это главная страница по методам оптимизаций

Главная страница сайта

Написать письмо автору

Небольшая коллекция методов оптимизаций

• Общие соображения
• Список методов
• Основные моменты в реализации методов
1. Методы реализации "методов оптимизации"
2. Адоптация моей программы к Вашим нуждам
• Интерфейс программы
• Изменение функции
• Изменение антиградиента
3. Переход из мировых координат в экранные, и наоборот
4. Описание одномерной оптимизации (дихотомии)
5. Обсуждение моментов, связанных с построением линий уровня

• Модуль дихотомии (dichotomy.pas)
• Процедура построения линий уровня
• Пример линий уровня для функции Химмельблау

• Исполняемый модуль программы в архиве ZIP
• Исходные тексты на Delphi в архиве ZIP
• Исходные тексты на VBA для Excel.здесь
• Пример применения методов оптимизации. PDF файл

1. Безусловные методы
• Методы первого порядка
  • Градиентного спуска с дроблением шага
  • Наискорейшего спуска
  • Сопряженных направлений
  • Давидона-Флетчера-Ривса (ДФП-метод)
• Методы нулевого порядка
  • Циклического покоординатного спуска
  • Хука-Дживса
  • Розенброка
  • Пауэлла
  • Нелдера-Мида (с помощью нерегулярного симплекса)
2. "Условные" методы или численные методы нелинейного программирования
• Метод условного градиента
• Метод проекции антиградиента

	-Здесь вводится количество линий уровня и точность, с которой они будут выводиться, чем больше число в поле "Точность", тем толще будут получаться линии.
	-Точность, с которой будет производиться минимизация.
	Мировые координаты: x0,y0 - координаты левого нижнего угла. x1,y1 - правого верхнего. Минимизация будет проводиться (если она 2D) по x: x0<x<x1; по y: y0<y<y1. Список внизу - история изменения масштаба. Об этом подробнее ниже.
	Начальная точка минимизации. С этой точки стартует большинство алгоритмов
	Каждая точка очередной итерации помечается маркером. Размер этого маркера можно изменять, введя новое значение в поле "радиус точки" (в пикселях). Некоторые алгоритмы могут предусматривать рестарт после определенного количество итераций, которое можно ввести в поле "Рестарт после".

вверх

function func(x,y:double):double;
var sqrt5:double;
begin
//my function
   sqrt5:=sqrt(5);
   Result:=8*x*x-4*x*y+5*y*y+8*sqrt5*(x+2*y)+64;
   //sample function
 //Result:=2*sqr(x)+2*sqr(y)-2*x*y-4*x-6*y;
   //Jonny's function
 //  Result:=11*sqr(x)+3*sqr(y)+6*x*y-2*sqrt(10)*(x-3*y)-22;
//   Result:=sqr(x)-4*x+sqr(y)-2*y;
//lena's function
//         Result:=2*sqr(x)-4*x*y+5*sqr(y)-4*sqrt(5)*(x-y)+4;
//sonya's function
//    Result:=6*sqr(x)+3*sqr(y)-4*x*y+4*sqrt5*(x+2*y)+22;
//     result:=ln(abs(x*sin(y))+abs(cos(y)));
//     Result:=cos(x)-sqr(y);
 // Result:=8*sqr(cos(x))-4*sin(x)*sin(y)+5*sqr(sin(y))+8*sqrt(5)*(sin(x)+2*cos(Y))+64;
//Функция Розенброка
 //result:=alpha*sqr(sqr(x)-y)+sqr(x-1);
//Функция Химмельблау
//result:=sqr(sqr(x)+y-11)+sqr(x+sqr(y)-7);
end;

Функция Розенброка
Функция Химмельблау

procedure GradientFunc(x,y:double;var grad:TWorldPoint);
//Это антиградиент!!!
var sqrt5:double;
begin
        sqrt5:=sqrt(5);
        grad.x:=-(16*x-4*y+8*sqrt5);
        grad.y:=-(-4*x+10*y+16*sqrt5);
//sample gradient
   // 	grad.x:=-(4*x-2*y-4);
    //    grad.y:=-(4*y-2*x-6);
//Jonny's functions gradient
 //  	grad.x:=-(22*x+6*y-2*sqrt(10));
//        grad.y:=-(6*y+6*x+6*sqrt(10));
//тестоввая функция
//   Result:=sqr(x)-4*x+sqR(y)-2*y;
//     grad.x:=-(2*x-4);
//     grad.y:=-(2*y-2);
//Функция Розенброка
//      grad.x:=-(alpha*4*(sqr(x)-y)*x+2*x-2);
//       grad.y:=-(-alpha*2*(sqr(x)-y));
//Функция Химмельблау
//	grad.x:=-(4*(sqr(x)+y-11)*x+2*(x+sqr(y)-7));
//        grad.y:=-(2*(sqr(x)+y-11)+4*(x+sqr(y)-7)*y);
//
//        grad.x:=-(12*x-4*y+4*sqrt5);
//        grad.y:=-(6*y-4*x+4*sqrt5*2);
{        grad.x:=-16*cos(x)*sin(x)-4*cos(x)*sin(y)+8*sqrt5*cos(x);
        grad.y:=-4*sin(x)*cos(y)+10*sin(y)*cos(y)-16*sqrt5*sin(y);}
end;

type
   TWorldPoint=record   {saves a point in world coord}
        x,y:double;
   end;

вверх

type
   TScreenPoint=record   {saves a point in screen coord}
        x,y:integer;
   end;

procedure World2Screen(Area:TDoubleRect;Window:TRect;world:TWorldPoint;var screen:TScreenPoint);
var M11,M22:double;
begin
with Screen do
begin
    M11:=(Window.Right-Window.Left)/(Area.rx-Area.lx);
    M22:=-(Window.Top-Window.Bottom)/(Area.ry-Area.ly);
    x:=trunc(M11*world.x+Window.Left-M11*Area.lx);
    y:=window.Bottom-trunc(M22*world.y-M22*Area.ly);
end;
end;

procedure Screen2World(Area:TDoubleRect;Window:TRect;screen:TScreenPoint;var world:TWorldPoint);
var M11,M22:double;
begin
    M11:=(Window.Right-Window.Left)/(Area.rx-Area.lx);
    M22:=-(Window.Top-Window.Bottom)/(Area.ry-Area.ly);
    World.x:=(screen.x-(Window.Left-M11*Area.lx))/M11;
    World.y:=(Window.Bottom-screen.y+M22*Area.ly)/M22;
end;

вверх

(*)

,

type T1DFunction=function(x:double):double;

function Pseudo1D(x:double):double;
begin
     Result:=Func(xk.x+x*uk.x,xk.y+x*uk.y);
end;

var curx, grad:TWorldPoint;
    func:T1DFunction;
    cappa:double;
// дальнейшие объявления и операторы
func:=@Pseudo1D;
GradientFunc(curx.x,curx.y,grad);//будем спускаться в направлении антиградиента
xk:=curx;
uk:=grad;		//собственно,направление антиградиента
cappa:=MakeDichotomy(0,1,eps/100,eps/100,func);{eps:double - аргумент функции,
					реализующей тот или иной метод.
					Обратите внимание, что точность 
					дихотомии должна быть значительно 
					выше требуемой от метода точности}

вверх

Выбрасываем отрезок [d,b]	Выбрасываем отрезок [a,c]

вверх

Методы оптимизации

1. В точке вычисляем антиградиент , который и определяет направление спуска на каждом шаге. Если вдруг окажется, что модуль антиградиента равен нулю (или меньше заданного числа-точности), то, значит, мы в искомой точке минимума! Инициализируем некоторую переменную заранее выбранным значением величины шага .
2. Пока не выполняется неравенство
   
   
   
   уменьшаем значение величины шага в заданное количество раз: , где , а также изменяем к-ую точку (она используется в неравенстве, записанном выше)
3. Увеличиваем k на единицу и возвращаемся в пункт 1.

вверх

• Пока не выполнено какое-либо из условий останова (в данном случае нами применялось условие малости разности значений функции в точкаx и ) выполнять следующие действия:
1. Оптимизировать функцию в направлении антиградиента функции в текущей точке. Т.е. вектор u_k - это вектор антиградиента.
2. Положить

вверх

,
,

вверх

.

,
,
.

вверх

вверх

.

вверх

вверх

вверх