Численная оптимизация в Matlab

Здравствуйте, уважаемые читатели. Продолжаем разбираться в Matlab. И сегодня наша тема связанна с численной оптимизацией — нахождением локальных и глобальных экстремумов функций одной или нескольких переменных в среде Matlab.

Общие сведения

Итак, в этом блоке ничего про Matlab не будет, лишь информация о понятии оптимизации. Это понятие сводится к терминам минимума и максимума функции, или, если коротко — экстремумам.

Под минимумом понимают такое значение функции, которое в некоторой окрестности этой функции, принимает наименьшее значение из всех возможных значений в этой окрестности. Соответственно максимум — это наибольшее значение функции в какой-либо окрестности.

Если не понятно — вот простой пример с всеми известной параболой:

У этой функции есть один минимум, и он находится в точке x = 0. Эта точка называется точкой минимума, а само значение этой функции есть минимум (он тоже равен 0). Максимумов у этой функции нет, но если бы функцию перевернули вверх ногами, то он бы появился.

Часто встречаются сложные функции, у которых есть несколько и минимумов и максимумов. И в таком случае, разделяют понятия локального и глобального экстремума. Локальный — это тот экстремум, который определен в некоторой области, а глобальный — на всей области определения функции. На рисунке выше представлен глобальный минимум параболы.

Поиск экстремумов в Matlab

И теперь, когда вы хоть как то познакомились с понятиями оптимизации и нахождения экстремумов функции, можем перейти к нахождению максимумов и минимумов в Matlab. Далее, как обычно мы будем разбирать примеры различной сложности. Часть примеров будет содержать в себе стандартные команды Matlab для нахождения минимума и максимума функции, а другая часть — это реализация метода с нуля.

Стандартные методы Matlab

Разберем 2 задачи нахождения минимума в Matlab:

1 пример. Вычислить минимум функции f(x)=-x^1/x, определив графически интервал его локализации. Вычисления провести с минимальным шагом по аргументу 1*10^-5

Для начала создадим скрипт, который отобразит эту функцию. Вот код для этого:

x = 0.00001:0.00001:10;
y = -x.^(x.^(-1));
plot (x,y);
hold on;
grid on;

Запускаем скрипт и получаем:
По графику функции делаем вывод, что имеется один минимум, и его координаты находятся в интервале 2.5 — 3, то есть мы сократим интервал поиска минимума.

Теперь создадим еще один скрипт, дадим ему название first.m и пропишем в него функцию:

function fun=first(x)
fun = -x.^(x.^(-1));
end

Таким образом в этом m-файле мы определили функцию. Теперь в командном окне мы пропишем следующий код:

>> [x,y] = fminbnd(@first,2.5,3)

И получаем такие значения:
x = 2.7183 — координата точки минимума
y = -1.4447 — значение минимума

В этой части кода мы использовали стандартный метод Matlab для нахождения минимума функции — fminbnd. мы передаем 3 параметра — саму функцию и интервалы для поиска минимума. Стоит отметить, что этот метод подходит только для функций, зависящих от одной переменной.

Итак, для этой задачи мы создали 2 скрипт-файла, которые вы можете скачать в конце статьи.

2 пример. Вычислить минимум функции двух переменных x⁴+y⁴-2x²+4xy-2y²+1 с точность 1*10-5.
Координаты начальной точки поиска [1.0,-1.0].

Для начала построим график функции от двух переменных — для этого создадим новый скрипт и пропишем там этот код:

[x y] = meshgrid(-2:0.1:2, -2:0.1:2);
z = x.^4 + y.^4 - 2*x.^2 + 4 * x.*y - 2*y.^2 + 1;
surf(x,y,z);

Функция surf позволяет строить трехмерные графики и отображать глубину значений функции для лучшего понимания. Запускаем скрипт — в итоге получился такой график:
Как видно из графика, имеется два участка, где присутствует локальный минимум (темно-синие участки), и наша задача найти координаты и значения двух этих точек. Воспользуемся стандартными инструментами Matlab и создадим новый скрипт с именем second.m, в котором и пропишем код:

function fun=second(x)
fun = x(1)^4 + x(2)^4 - 2*x(1)^2 + 4 * x(1)*x(2) - 2*x(2)^2 + 1;
end

После этого, в командной строке, как и для первой задачи, прописываем стандартную функцию Matlab:

>> [z,f,exitflag,output] = fminsearch(@second, [1.0,-1.0], optimset('TolX',1e-5))

Получаем такой вывод:

z = 1.4142   -1.4142
f = -7.0000
exitflag = 1
output = 
    iterations: 40
    funcCount: 74
    algorithm: 'Nelder-Mead simplex direct search'
    message: [1x196 char]

Для нахождение минимумов в Matlab на этот раз мы использовали функцию fminsearch. Эта функция реализует симплекс — метод Нелдера-Мида. В выводе мы получили несколько переменных: в z записались значения координат точек минимума, в f само значение этого минимума. А в переменных exitflag и output помещены условия прерывания процесса поиска и информация об оптимизации соответственно.

В итоге у нас опять получилось 2 m-файла.

Метод Ньютона Matlab

А теперь попробуем сами реализовать метод Ньютона для оптимизации функции.

3 пример. Методом Ньютона найти точку минимума x* и минимальное значение f* функции f(x)=(x-2)⁴-lnx на отрезке xє[2;3] c точностью 10^-7

Начнем с того, что создадим новый скрипт и назовем его Newton.m. Затем пропишем в нем код:

function [Xk, Yk] = Newton(f,diap)
    a = diap(1); % границы
    b = diap(2);
    df = char(diff(sym(f))); % символьно ищем первую 
    ddf = char(diff(sym(df))); % и вторую производные
    F = inline(f); % преобразуем в функции
    F1 = inline(df);
    F2 = inline(ddf);
    eps = 0.0000001; % задаем точность
    if F(a)*F2(a) > 0 % проверка с какой границы начинать искать
        Xk = b;
    else
        Xk = a;
    end
    while abs(F1(Xk)) > eps
        X0 = Xk; % X0 - значение предыдущего шага
        Xk =  X0 - (F1(X0)/(F2(X0))); % расчет нового значения
        Yk = F(Xk);
    end
end

Вполне понятная функция, которая работает с первой и второй производной символьной функции, которую получает в качестве параметра. Также в параметрах принимается диапазон. Эта функция возвращает координаты точки и значение экстремума.
Теперь нам осталось вызвать эту функцию в командном окне:

>> fun = '(x-2)^4 - log(x)';
>> diap = [2,3];
>> [Xk, Yk] = Newton(fun, diap);

В итоге получилось:
Xk = 2.4663
Yk = -0.8554

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

Также, очень важно задавать как можно узкий диапазон поиска, иначе метод может работать некорректно, особенно это проявляется с периодическими функциями по типу cos(x) и т.п.

Заключение

Ну что ж, в этой статье мы рассмотрели некоторые методы для нахождения экстремумов в Matlab. Мы использовали как стандартные методы, так и реализовали метод Ньютона в среде Matlab. Их исходники чуть ниже.
Скачать исходники

На этом сегодня все, оставляйте ваши комментарии и задавайте вопросы.