Оптимизация в среде MATLAB
..pdfМинистерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Пермский национальный исследовательский политехнический университет»
А.Л. Гольдштейн
ОПТИМИЗАЦИЯ В СРЕДЕ MATLAB
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
Издательство Пермского национального исследовательского
политехнического университета
2015
УДК 004.422.8:519.873(075.8) Г63
Рецензенты:
д-р физ.-мат. наук, директор по корпоративному обучению и научной деятельности А.Н. Румянцев
(ООО «Парма-Телеком»)
д-р техн. наук, профессор Ю.Н. Хижняков (Пермский национальный исследовательский
политехнический университет)
Гольдштейн, А.Л.
Г63 Оптимизация в среде MATLAB: учеб. пособие / А.Л. Гольдштейн. – Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2015. – 192 с.
ISBN 978-5-398-01361-0
Рассмотрены возможности системы компьютерной математики MATLAB в части решения оптимизационных задач. Достаточно подробно описаны функции пакетов расширения Toolbox Optimization и Toolbox Global Optimization. Приведены многочисленные примеры решения задач оптимизации в режиме командной строки, иллюстрированные двумерными и трехмерными графиками, а также задания для восьми лабораторных работ.
Предназначено для студентов (бакалавров и магистров), изучающих курс «Методы оптимизации». Также может быть полезно тем, кто сталкивается с необходимостью решать задачи оптимизации.
УДК 004.422.8:519.873(075.8)
ISBN 978-5-398-01361-0 |
© ПНИПУ, 2015 |
2
|
ОГЛАВЛЕНИЕ |
|
Введение........................................................................................................ |
5 |
|
1. |
Одномерная минимизация в MATLAB.................................................. |
7 |
2. |
Безусловная минимизация функций многих |
|
переменных................................................................................................. |
11 |
|
|
2.1. Функция fminunc ............................................................................. |
11 |
|
2.2. Функция fminsearch......................................................................... |
17 |
|
Лабораторная работа № 1. Одномерная и безусловная |
|
|
оптимизация............................................................................................ |
20 |
3. |
Условная оптимизация .......................................................................... |
21 |
|
Лабораторная работа № 2. Условная оптимизация............................. |
40 |
4. |
Глобальная оптимизация....................................................................... |
41 |
|
4.1. Метод GlobalSearch ......................................................................... |
41 |
|
4.2. Метод MultiStart............................................................................... |
50 |
|
Лабораторная работа № 3. Исследование методов GlobalSearch |
|
|
и MultiStart .............................................................................................. |
69 |
|
4.3. Метод Direct Search ......................................................................... |
70 |
|
4.4. Метод Simulated Annealing ............................................................. |
87 |
|
Лабораторная работа № 4. Исследование методов |
|
|
прямого поиска и отжига....................................................................... |
98 |
|
4.5. The Genetic Algorithm.................................................................... |
100 |
|
4.6. Сравнительная характеристика решателей................................. |
116 |
|
Лабораторная работа № 5. Генетический алгоритм.......................... |
117 |
5. |
Многокритериальная оптимизация.................................................... |
119 |
|
5.1. Функция gamultiobj ....................................................................... |
119 |
|
5.2. Метод достижения цели. Функция fgoalattain ............................ |
128 |
|
5.3. Функция fminimax ......................................................................... |
135 |
|
Лабораторная работа № 6. Решение многокритериальных |
|
|
задач....................................................................................................... |
137 |
6. |
Линейное программирование. Функция linprog................................ |
139 |
7. |
Целочисленное программирование. Функция bintprog ................... |
148 |
3
8. Квадратичное программирование. Функция quadprog..................... |
152 |
Лабораторная работа № 7. Решение задач математического |
|
программирования ............................................................................... |
157 |
9. Другие функции пакета Toolbox Optimization................................... |
159 |
9.1. Нахождение корней функции одной переменной...................... |
159 |
9.2. Решение системы нелинейных уравнений.................................. |
160 |
9.3. Нелинейная задача наименьших квадратов................................ |
164 |
9.4. Задача аппроксимации.................................................................. |
166 |
9.5. Неотрицательный линейный метод |
|
наименьших квадратов ........................................................................ |
168 |
9.6. Линейная задача наименьших квадратов |
|
с ограничениями................................................................................... |
170 |
Лабораторная работа № 8. Решение уравнений |
|
и метод наименьших квадратов ......................................................... |
172 |
Список рекомендуемой литературы....................................................... |
174 |
Приложение 1. Параметры fminunc........................................................ |
175 |
Приложение 2. Параметры fmincon........................................................ |
177 |
Приложение 3. Параметры GlobalSearch и MultiStart........................... |
180 |
Приложение 4. Параметры Direct Search ............................................... |
182 |
Приложение 5. Параметры Simulated Annealing ................................... |
184 |
Приложение 6. Параметры Genetic Algorithm |
|
(ga и gamultiobj)........................................................................................ |
185 |
Приложение 7. Параметры fgoalattain и fminimax ................................ |
187 |
Приложение 8. Параметры quadprog...................................................... |
189 |
Приложение 9. Параметры fsolve ........................................................... |
190 |
4
ВВЕДЕНИЕ
MATLAB (MATrix LABoratore) – одна из наиболее мощных сис-
тем компьютерной математики, построенная на расширенном применении матричных вычислений. Она включает пакеты расширения Simulink, Toolbox и Blockset, ориентированные на самые разнообразные задачи, где требуются математические расчеты, глубокий анализ и моделирование.
MATLAB имеет развитый высокоуровневый язык программирования и прекрасную двумерную и трехмерную графику, позволяющую наглядно представлять результаты расчетов, экспериментов и процессы моделирования.
Пакеты расширения Toolbox (ящик инструментов) специализируются на решении задач в различных предметных областях: в физике
иастрономии, в специальных разделах математики и математическом моделировании, в проектировании и управлении технических систем
ит.д. Основным инструментом MATLAB являются функции, которые реализуют определенные операции и алгоритмы. Имеются встроенные функции, в том числе все элементарные, и внешние, оформленные в виде так называемых m-файлов. Внешние функции могут пополняться собственными функциями пользователя.
Врасширения Toolbox входят два пакета, предназначенные для решения задач оптимизации: Toolbox Optimization и Toolbox Global Optimization. Настоящее пособие посвящено описанию этих пакетов.
Первый пакет включает набор функций, в которых реализованы методы и алгоритмы одномерной и многомерной безусловной и условной минимизации, линейного, булевого и квадратичного программирования, наименьших квадратов и решения уравнений, а также алгоритмы многокритериальной оптимизации.
Функции пакета Global Optimization ориентированы на поиск глобального минимума или многих минимумов. Здесь используются методы прямого поиска, мультистарта, моделирования отжига, генетический алгоритм. В этот пакет также включена функция многокритериального генетического алгоритма.
Пакеты предлагают два способа решения задач: с использованием командной строки и с использованием графического пользовательско-
5
го интерфейса (GUI). Второй способ проще, но уступает первому в гибкости и функциональности. Режим командной строки предоставляет пользователю всю мощь системы MATLAB, поэтому в пособии описывается использование именно этого режима решения задач. При умении решать задачи в командном окне использование GUI не вызовет никаких затруднений (для обращения к нему в меню соответствующего Toolbox следует выбрать Optimtool).
MATLAB, включая рассматриваемые пакеты, имеет мощную и удобную систему помощи, содержащую многие тысячи страниц документации. Для быстрого доступа к интересующему объекту достаточно набрать help и имя объекта, например оператора или функции.
В пособии рассматриваются функции обоих пакетов, приводятся многочисленные примеры их использования, во многих случаях они сопровождаются наглядным графическим представлением результатов. Для практического освоения и использования методов оптимизации, реализованных в пакетах, предлагается выполнить восемь лабораторных работ, охватывающих большинство функций пакетов.
Для тех, кто не работал с MATLAB, обратим внимание на два варианта некоторых арифметических операторов: традиционный оператор (*, ^, /), определяющий матричную операцию, и оператор с точкой впереди (.*, .^, ./), задающий поэлементные действия с операндами.
6
1. ОДНОМЕРНАЯ МИНИМИЗАЦИЯ В MATLAB
Toolbox Optimization содержит специальные функции, каждая из которых ориентирована на определенный тип задачи оптимизации. Для одномерной минимизации непрерывных функций предназначена функция пакета fminbnd. Решаемая задача имеет вид
min f(x), a < x < b.
Алгоритм минимизации базируется на методах золотого сечения и квадратичной аппроксимации (параболической интерполяции).
Варианты обращения к функции fminbnd:
x = fminbnd(fun,x1,x2)
x = fminbnd(fun,x1,x2,options) x = fminbnd(problem)
[x,fval] = fminbnd(...) [x,fval,exitflag] = fminbnd(...) [x,fval,exitflag,output] = fminbnd(...)
Слева от знака равенства записываются выходные величины, и если их больше одной, то они перечисляются через запятую в квадратных скобках. Справа от имени функции в круглых скобках указываются входные величины (аргументы функции). В приведенных записях приняты следующие обозначения:
x – значение x, соответствующее локальному минимуму функции f(x); fval – значение f(x) в точке найденного локального минимума; exitflag – признак, идентифицирующий причину завершения алгоритма, его возможные значения:
1 – сходимость алгоритма к минимуму;
0 – число итераций превысило максимально установленное; –1 – причина в функции вывода (решение не достигнуто); –2 – границы несовместны.
Output – структура, содержащая информацию о процессе, имеет поля: Iterations – число итераций;
funcCount – число вычислений целевой функции; algorithm – используемый алгоритм;
message – конечное сообщение.
7
Входные аргументы:
fun – целевая функция, может быть определена как m-файл (m-фун-
кция), например:
function f = myfun(x) f = sin(x^2);
(файл сохраняется под именем myfun.m), и тогда на месте fun записывается @myfun, где myfun – имя функции и соответствующего ей m-файла; также fun можно представить непосредственно формулой (без использования имени) как конструкцию @(x)sin(x^2) или как строковое выражение ‘sin(x^2)’;
x1,x2 – значения левой и правой границ переменной x;
options – опции алгоритма, исходно все установлены по умолчанию; применяетcя, если необходимо изменить какие-либо параметры оптимизации; при этом перед обращением к функции fminbnd вносятся изменения в настройки опций options с помощью функции optimset, аргументами которой являются пары «имя параметра, устанавливаемое значение параметра», например установка
options=optimset(‘Display’, ‘off’)
исключит вывод на экран (в командное окно) промежуточных данных. При значении 'iter' будут выводиться результаты каждой итерации. Другие значения параметра – 'final' и 'notify' (вывод итогов и вывод только при отсутствии сходимости). Указание параметра 'Outputfcn', в качестве значения которого записывается имя функции, приводит к вызову этой функции на каждой итерации алгоритма. Значение параметра 'PlotFcn' определяет функцию вывода графики. В пакете это функции @optimplotx (рисует текущую точку), @optimplotfunccount (выводит количество вычислений функции), @optimplotfval (выводит текущее значение целевой функции). Функции вывода и графики могут быть написаны пользователем. При включении параметра FunValCheck ('on') выводится сообщение при возврате целевой функцией комплексного значения или Inf и NaN.
Problem – сохраненное из GUI Optimization Tool описание зада-
чи, а именно:
f – целевая функция, x1 – левая граница, x2 – правая граница,
8
solver – 'fminbnd',
options – структура параметров, создается optimset.
Результатом выполнения функции fminbnd является локальное решение (локальный минимум).
Пример 1.
Найти минимум функции y = x + 25/x в интервале 2 < x < 9. Для решения задачи в командное окно записываем программу: >> x=2:0.1:9;y=x+25./x; plot(x,y);xlabel('x'); ylabel('y');...
title('Minimization by fminbnd');hold on; ...
options=optimset('Outputfcn', @outmy);...
[x,fval,exitflag,output]=fminbnd('x+25./x',2,9,options)
Примечание. Многоточие позволяет перейти на следующую строку, иначе при нажатии Enter выполнится введенная перед ним часть программы. Также многоточие позволяет разрывать выражение для переноса на следующую строку.
Пояснения к программе: в 1-й строке выводится график функции и обозначения осей, во 2-й выводится заголовок и дается указание на удержание графического окна, в 3-й функция outmy во время работы алгоритма выводит точки, соответствующие итерациям, в то же графическое окно. Эта функция записана в виде m-файла
function stop = outmy(x,optimValues,state) stop = false;
switch state case 'init'
hold on case 'iter'
y=x+25./x;
plot(x,y,'red.');
% Label points with iteration number. text(x,y+.15,num2str(optimValues.iteration+1)); case 'done'
hold off
end
end
Результаты выполнения программы, выводимые в командное и графическое окна, представлены ниже и на рис. 1.
9
Рис. 1. Поиск минимума одномерной функции
x =
5.0000 fval =
10.0000 exitflag =
1 output =
iterations: 9 funcCount: 10
algorithm: 'golden section search, parabolic interpolation' message: [1x112 char]
10