Методические указания к лабораторной работе по дисциплине "Численные методы оптимизации сложных систем". Тема: Безусловная минимизация сложной функции многих переменных градиентными методами в среде MATLAB

 Одной из актуальных математических и инженерных задач, как известно, является проблема поиска оптимальных значений сложных функций многих переменных.

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

 Целью работы является исследование возможностей СКМ MATLAB для решения практической задачи поиска численного минимума целевой функции двух переменных с применением "градиентного метода наискорейшего спуска Коши".

                                                         Теоретическая часть

    Далее будем говорить о минимизации функций , поскольку максимизация , очевидно, эквивалентна минимизации функции .

Получившие широкое распространение градиентные методы относятся к методам первого порядка, поскольку для определения направления оптимального поиска в них используется лишь информация о первых частных производных целевой функции (ЦФ) .

 К методам первого порядка относятся градиентные методы с постоянным и переменным шагом, в частности, градиентный метод с фиксированным шагом и метод наискорейшего спуска Коши.

 Метод наискорейшего спуска (МНС) Коши относится к градиентным методам оптимизации с изменяемым шагом. Данный алгоритм хорошо зарекомендовал себя и широко применяется на практике.

 Итерации метода наискорейшего спуска Коши строятся по формуле

                                       

где  - переменный шаг поиска на - м этапе вычислений выбирается оптимальным образом из условия минимизации по неотрицательной переменной k целевой функции при движении в направлении антиградиента , т.е.:

                 

 Согласно алгоритму МНС, процесс поиска идет в направлении вектора антиградиента ЦФ из точки , в которой ЦФ принимает наименьшее значение. Таким образом, проблема определения оптимальной величины шага  сводится к задаче поиска минимума функции одной переменной.

 Вычисления с использованием рассмотренного метода прекращаются, когда выполняется одно из следующих условий:

                       

где  - заданные малые числа, характеризующие точность нахождения минимума (для дифференцируемой функции в точке минимума  для всех ).

 

 Однако, методы первого порядка обладают рядом недостатков.

 В окрестности точки минимума компоненты вектора градиента малы, и процесс вычислений существенно замедляется, в особенности, когда ЦФ является «овражной» (для нее характерны резкие отличия частных производных по величине и направлению).

 Поскольку свойство наискорейшего спуска локально, МНС может "зациклиться" из-за резкой и частой смены направлений антиградиента для существенно "овражных" ЦФ.

 Преимущества метода наискорейшего спуска – простота вычисления градиента и сходимость независимо от выбора начальной точки, а главный недостаток – медленная сходимость в окрестности точки оптимума. Кроме того, алгоритм неприменим в тех случаях, когда линии уровня ЦФ имеют точки излома, где целевая функция недифференцируема. 

Блок-схема алгоритма метода наискорейшего спуска Коши представлена на рисунке 1.

               

                  Рисунок 1 - Блок-схема алгоритма метода наискорейшего спуска Коши

 

 Траектория спуска представляет собой ломаную, состоящую из отрезков прямых, параллельных координатным осям x₁, x₂ (см. Рисунок 2). 

                         

Рисунок 2 - Геометрическая интерпретация метода наискорейшего спуска на плоскости x₁ O x₂ .

 

                                                          Практическая часть

Постановка задачи

 Для заданной в варианте функции двух переменных из начальной точки выполнить поиск численного значения безусловного минимума ЦФ с заданной точностью вычислений  и сравнить результаты, полученные с использованием стандартных средств СКМ MATLAB.

Порядок выполнения работы

1. Изучить теоретический материал.
2. Составить программу, реализующую оптимизационный алгоритм МНС Коши.
3. Произвести запуск и отладку программы.
4. Выполнить численные расчеты с помощью разработанной процедуры и сравнить результаты безусловной минимизации заданной целевой функции с использованием стандартных средств СКМ MATLAB. Расхождения оценить при помощи вычислений абсолютных погрешностей по значениям целевых функций, полученных при запуске программы МНС и стандартных оптимизационных методов СКМ MATLAB (функций fminsearch, fminunc).
5. Построить график целевой функции, отметить на нем начальную и оптимальную точки решения задачи.
6. Оформить отчет по лабораторной работе и защитить ее.

Содержание отчета по работе

1. Титульный лист лабораторной работы.
2. Блок-схемы оптимизационного алгоритма МНС.
3. Тексты программ, реализованных в СКМ MATLAB.
4. Результаты проведенных расчетов в виде Workspace - скрипта и графика ЦФ.
5. Выводы по работе.
6. Список использованной литературы и источников.

Пример выполнения лабораторной работы

 Пусть задана целевая функция двух переменных, начальная точка поиска, точность решения задачи и предельное количество итераций алгоритма МНС в следующем виде:

                          

 Составим для заданной ЦФ программу в редакторе Editor СКМ MATLAB с переменным набором выходных значений, в составе которых могут быть значение ЦФ, ее градиент (вектор первых частных производных) и матрица вторых частных производных (гессиан) функции:

function [f,g,H] = fun2(x)
f=(3.456*x(1)^2-65.32)^2+(2.537*x(2)^2-77.43)^2;
if nargout > 1
    g=[(13.824*(3.456*x(1)^2-65.32))*x(1);(10.148*(2.537*x(2)^2-77.43))*x(2)];
end
if nargout > 2
    H = [143.327232*x(1)^2-902.98368 0; 0 77.236428*x(2)^2-785.75964];
end

 Разработаем программу алгоритма МНС Коши согласно приведенной выше блок-схеме
(Рисунок 1):

function [XX,FF, iter_count, modgr,T] = SteepestDescent(f, x0, eps, MM, T0)
% Инициализируем номер итерации алгоритма МНС:
iter_count = 0;
% Задаем начальный вектор, транспонируем его:
XX = x0';

[~, grad] = f(x0);
format long;
% Вычисляем модуль градиента:
modgr = norm(grad, 2);
% Инициализируем длину шага спуска:
T = T0;

while ((modgr > eps) && (iter_count < MM))
    iter_count = iter_count + 1;
    arg = @(t) f(XX - t*grad);
    options = optimset('MaxFunEvals',3000, 'TolX', 1e-22);
    % Вычисляем оптимальный шаг спуска:
    T = fmincon(arg,T,-1,0,[],[],[],[],[],options);
    % Выполняем итерацию алгоритма МНС:
    XX = XX - T*grad;
    [FF, grad] = f(XX);
    % Пересчитываем модуль градиента:
    modgr = norm(grad, 2);
end

XX = XX';

Напишем скрипт вызова метода Коши:

X0=[-.81 -.81];
eps0 = 1e-3; 
[XX, FF, iter_count, modgr] = SteepestDescent(@fun2, X0, eps0,50,0.01);

Реализуем вызов стандартных оптимизационных методов СКМ MATLAB и расчет абсолютных разностей полученных значений с запрограммированным нами численным алгоритмом МНС:

[x,y] = fminsearch(@fun2,X0);
options = optimset('MaxFunEvals',3000, 'TolX', eps0);
[x1,y1] = fminunc(@fun2,X0,options);

delY11 = abs(FF-y); delY12 = abs(FF-y1);

 После запуска скрипта на выполнение были получены следующие результаты в Workspace:

X0 = [-0.81 -0.81];

eps0 = 0.001;

XX = [-4.34746620824486 -5.5245180316083653];

FF = 3.4157388825249043E-12;

delY11 = 1.3307230166066404E-6;

delY12 = 3.81282585334422E-6;

iter_count = 8;

modgr = 0.00011097610958758026;

x = [-4.3474453757120148 -5.5244835154603287];

x1 = [-4.34750923101793 -5.52457030118019];

y = 1.3307264323455229E-6;

y1 = 3.8128292690831027E-6;

Построим график ЦФ и отметим на нем начальную точку (зелёным цветом) и конечный оптимальный вектор (красным цветом).

Примечание

В ряде случаев численные алгоритмы и стандартные процедуры MATLAB могут сойтись к разным локальным минимумам  ЦФ с близкими величинами (в случае мультимодальной овражной целевой функции), в зависимости от заданных начальных условий поиска, что является допустимым для градиентных алгоритмов.

Вывод:

В ходе лабораторной работы проведена безусловная минимизация функции 2-х переменных методом наискорейшего спуска Коши и стандартными процедурами СКМ MATLAB. 

Для заданных начальных условий за 8 итераций МНС достигнута приемлемая точность решения оптимизационной задачи, которая получилась выше, чем у методов fminsearch, fminunc.

 

Литература

1. Медынский М. М., Дьячук А. К. Численные методы оптимизации с использованием системы Maple 11. – М.: Изд-во МАИ-ПРИНТ, 2009. 287 c., ил.
2. Дьяконов В. П. MATLAB. Полный самоучитель.– М.: ДМК Пресс, 2012. – 768 с., ил.
3. Конспект лекций по курсу «Численные методы оптимизации сложных систем». Автор: доцент, к.т.н.  Дьячук А.К.