Метод штрафных функций excel
АННОТАЦИЯ: В СТАТЬЕ РАССМОТРЕНЫ ОСНОВНЫЕ МЕТОДЫ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ, ПРИВЕДЁН ПРИМЕР РЕАЛИЗАЦИИ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ (МЕТОДА ПОКООРДИНАТНОГО СПУСКА) В СРЕДЕ EXCEL. КЛЮЧЕВЫЕ СЛОВА: МНОГОМЕРНАЯ ОПТИМИЗАЦИЯ, УСЛОВНАЯ ОПТИМИЗАЦИЯ, БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.
Содержимое публикации
Лазаренко Виктория Сергеевна студент, Ставропольский государственный педагогический институт, РФ, г. Ставрополь Кузина Наталья николаевна научный руководитель, Старший преподаватель кафедры математики и информатики, Ставропольский государственный педагогический институт, РФ, г. Ставрополь
« РЕАЛИЗАЦИЯ МНОГОМЕРНЫХ ЗАДАЧ ОПТИМИЗАЦИИ В excel » Аннотация: В статье рассмотрены основные методы многомерной оптимизации, ПРИВЕДЁН ПРИМЕР РЕАЛИЗАЦИИ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ (МЕТОДА ПОКООРДИНАТНОГО СПУСКА) В среде Excel . КЛЮЧЕВЫЕ СЛОВА: многомерная оптимизация, условная оптимизация, БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.
Исследование задач многомерной оптимизации сводится к поиску точек минимума функции многих переменных на всем пространстве соответствующей размерности. Такая задача сложнее задачи минимизации функции одной переменной, так как с ростом размерности пространства переменных возрастают объем вычислений и сложность алгоритмов, затрудняется анализ поведения целевой функции.
В этой статье мы рассмотрим численные методы оптимизации,т.е. методы построения алгоритмов нахождения оптимального (минимального или максимального) значения некоторой функции.
Численные методы многомерной оптимизации
Численные методы оптимизации различаются по характеру изменения целевой функции: если нет никаких ограничений ни на изменение независимых переменных, ни на значения целевой функции, то это методы безусловной оптимизации. Сущность методов безусловной оптимизации состоит в поиске минимуму функции Y = D х) путем многократных вычислений, при различных значениях параметров х = , k = 0, 1, 2, . причем на каждом k-м шаге вычислений контролируют выполнение условий. При наличии каких-либо ограничений используются методы условной оптимизации. Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации.
Кроме того, методы многомерной оптимизации классифицируются по возможности использования частных производных от целевой функции: если производные не используются, то это - методы прямого поиска,основанные на вычислении только значений целевой функции; градиентные методы, в которых используются точные значения первых производных функции.
Существуют различные методы безусловной и условной оптимизации:
Безусловная оптимизация: Метод покоординатного спуска;
Безусловная оптимизация: метод наискорейшего спуска;
Безусловная оптимизация: подпрограмма EXCEL “Поиск решения”;
Условная оптимизация: метод штрафных функций;
Условная оптимизация: подпрограмма EXCEL “Поиск решения”;
Условная оптимизация: линейное программирование.
Рассмотрим наиболее подробно безусловную оптимизацию, её методы и реализацию примера в Excel .
Метод покоординатного спуска (метод прямого поиска), в котором используются только значения целевой функции. Чтобы воспользоваться этим методом, необходимо иметь следующие исходные данные:
а) формулу целевой функции f(X1,X2, . , Xn),
б) Е - точность нахождения значений независимых переменных, при которых функция достигает минимума,
Необходимо отметить, что метод покоординатного спуска сводит многомерную задачу оптимизации к многократному решению одномерных задач по каждой независимой переменной.
Приведём пример, чтобы показать наглядно суть метода и его разрешение.
Условие задачи: число независимых переменных равняется двум. Ограничения отсутствуют. Требуется найти минимум функции
из начальной точки (0,5;0,5) c точностью 0,0001. Проанализировав функцию, заметим, что она будет иметь минимум, равный нулю. Для чего и первое, и второе слагаемое тоже должны быть равны нулю. Откуда координаты точки минимума (1;1).
Решим эту задачу на EXCEL. Откроем новый рабочий лист, где столбец А -значения X1, столбец В - значения X2, а столбец С - значения целевой функции и, наконец, столбец D - значения погрешности D.
Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.
Опишем первую итерацию пошагово:
1 шаг. Скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X 1выполним с помощью подпрограммы EXCEL Поиск решения. Вызовем эту подпрограмму командой меню Сервис- Поиск решения.
2 шаг. Скопируем содержимое ячейки А4 в ячейку А5. Сделаем текущей ячейку С5. Дадим команду меню Сервис- Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки - адрес В5. В результате в ячейке В5 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С5 по координате X2.
3 шаг. Занесем в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5) для вычисления погрешности решения на первом шаге. На этом заканчивается первая итерация.
Вторая и все последующие итерации проводятся аналогично, но с учетом соответствующих адресов ячеек.
Можно построить диаграмму изменения на каждой итерации, на которой видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.
Реализация метода покоординатного спуска представлена в Excel на рисунке 1.
Рисунок 1. Метод покоординатного спуска
Сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях техники [1]. К навыкам математического обоснования принятия решений относятся навыки математического моделирования оптимизационных задач, выбора адекватного математического обеспечения (метода, алгоритма, программной системы) с необходимым обоснованием.
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Реальные прикладные задачи дискретной оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.
Список литературы
1. Корнеенко В. П. Методы оптимизации: Учебник / В. П. Корнеенко. - М.: Высш. шк., 2007.
2. Пантелеев А. В. Методы оптимизации в примерах и задачах: Учеб. пособие / А. В. Пантелеев, Т. А. Летова. - М.: Высш. шк., 2005.
3. Батищев Д. И. Оптимизация в САПР: Учебник / Д. И. Батищев, Я. Е. Львович, В. Н. Фролов. - Воронеж: Изд-во ВГУ, 1997.
Лазаренко Виктория Сергеевна студент 4 курса, Ставропольский государственный педагогический институт, РФ, г. Ставрополь Кузина Наталья николаевна научный руководитель, Старший преподаватель кафедры математики и информатики, Ставропольский государственный педагогический институт, РФ, г. Ставрополь
« РЕАЛИЗАЦИЯ МНОГОМЕРНЫХ ЗАДАЧ ОПТИМИЗАЦИИ В excel» Аннотация: В статье рассмотрены основные методы многомерной оптимизации, ПРИВЕДЁН ПРИМЕР РЕАЛИЗАЦИИ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ (МЕТОДА ПОКООРДИНАТНОГО СПУСКА) В среде Excel. КЛЮЧЕВЫЕ СЛОВА: многомерная оптимизация, условная оптимизация, БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.
Изучение задач многомерной оптимизации заключается в нахождении точек минимума функции почти всех переменных на всем промежутке определенной размерности.
Такая задача сложнее задачи минимизации функции одной переменной, в связи с тем, что с увеличением размерности места переменных, растёт размер вычислений и возникает трудность в построении алгоритмов, тем самым возникают трудности в изучении поведения мотивированной функции.
В данной статье мы рассмотрим численные методы оптимизации, т.е. способы построения алгоритмов нахождения оптимального (минимального или максимального) познания некой функции и для наглядности реализуем пример многомерной оптимизации в Excel. Ведь Excel – это одна из наиболее узнаваемых и известных программ, возможности которой разрешают стремительно отыскивать действенное решение, начиная с математических задач и заканчивая применением оптимизации в самых различных сферах работе человека.
Численные методы многомерной оптимизации
Существуют разные методы безусловной и условной оптимизации. К безусловной оптимизации относятся методы: покоординатного спуска, метод наискорейшего спуска и подпрограмма EXCEL “Поиск решения”. Линейное программирование, метод штрафных функций и подпрограмма EXCEL “Поиск решения” – это условная оптимизация.
Суть методов безусловной оптимизации состоит в поиске минимуму функции методом неоднократных вычислений, при разных значениях характеристик х = k>, где k = 0, 1, 2, . Методы условной оптимизации применяются при наличии ограничений. Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах. Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений x1, …,xn на каждой итерации.
Рассмотрим более подробно безусловную оптимизацию, её методы и реализацию примера в Excel.
Метод покоординатного спуска (метод прямого поиска), в котором используются лишь значения целевой функции. Чтобы воспользоваться этим методом, необходимо иметь такие исходные данные, как: формулу целевой функции, имеющую вид f(X1,X2, . , Xn); Е - точность нахождения значений независимых переменных, при которых функция достигает минимума; начальные приближения X10,X20 . , Xn0.
Стоит отметить, что метод покоординатного спуска сводит многомерную задачу оптимизации к многократному решению одномерных задач по каждой независящей переменной.
Приведём пример, чтобы показать наглядно сущность метода и его разрешение.
Условие задачи: число независимых переменных равняется двум. Ограничения отсутствуют. Требуется найти минимум функции
из начальной точки (0,5;0,5) c точностью 0,0001. Проанализировав функцию, заметим, что она будет иметь минимум, равный нулю. Для чего и первое, и второе слагаемое тоже должны быть равны нулю. Откуда координаты точки минимума (1;1).
Решим эту задачу на EXCEL. Откроем новый рабочий лист, где столбец А -значения X1, столбец В - значения X2, а столбец С - значения целевой функции и, наконец, столбец D - значения погрешности D.
Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.
Опишем первую итерацию, для этого скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X1 выполним с помощью подпрограммы EXCEL «Поиск решения». Вызовем эту подпрограмму командой меню Сервис - Поиск решения.
Теперь скопируем содержимое ячейки А4 в ячейку А5. Сделаем текущей ячейку С5. Зададим команду меню Сервис - Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки - адрес В5. В результате в ячейке В5 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С5 по координате X2.
Вычислим погрешности решения на первом шаге, для этого внесём в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5). На этом заканчивается первая итерация.
Вторая и все последующие итерации проводятся аналогично, но с учетом соответствующих адресов ячеек.
Можно построить диаграмму изменения на каждой итерации, на которой видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.
Реализация метода покоординатного спуска представлена в Excel на рисунке 1.
Рисунок 1. Метод покоординатного спуска в Excel
Можно сказать, что сегодня оптимизационные задачи и задачи принятия решений моделируются и решаются в самых различных областях[1], в связи с этим растёт необходимость развития математического аппарата оптимизации. Решение задач с помощью Excel, позволяем наглядно разобраться с задачей и решить её.
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев.
Список литературы
1. Корнеенко В. П. Методы оптимизации: Учебник / В. П. Корнеенко. - М.: Высш. шк., 2007.
2. Пантелеев А. В. Методы оптимизации в примерах и задачах: Учеб. пособие / А. В. Пантелеев, Т. А. Летова. - М.: Высш. шк., 2005.
3. Батищев Д. И. Оптимизация в САПР: Учебник / Д. И. Батищев, Я. Е. Львович, В. Н. Фролов. - Воронеж: Изд-во ВГУ, 1997.
ЛАБОРАТОРНАЯ РАБОТА №4
ИЗУЧЕНИЕ МЕТОДОВ УСЛОВНОЙ ОПТИМИЗАЦИИ
2 ПРАКТИЧЕСКАЯ ЧАСТЬ
2.1 Подпрограмма EXCEL "Поиск решения”
Подпрограмма Поиск решения имеет модификацию методов сопряженных градиентов и Ньютона для решения задач условной оптимизации. Следует отметить, что эта модификация работает успешно лишь для некоторых видов целевой функции - линейной и квадратичной и лишь для некоторых видов ограничений, например, типа шара, координатного параллелепипеда, гиперплоскости или полиэдра. После вызова подпрограммы командой меню Сервис- Поиск решения появляется диалог, в котором кроме уже знакомых Вам полей Установить целевую ячейку и Изменяя ячейки, следует обратить внимание на поле Ограничения и кнопки управления ограничениями Добавить, Изменить и Удалить. Например, чтобы задать новое ограничение следует щелкнуть по кнопке Добавить. В открывшемся новом диалоге Добавить ограничение нужно внести адрес одной или блока ячеек в поле Ссылка на ячейку, а затем указать тип ограничения и его условия. После этого нужно щелкнуть по кнопке ОК. Работа с другими кнопками управления не вызывает затруднений.
Выбор параметров подпрограммы вызывается щелчком по кнопке Параметры. Продемонстрируем работу подпрограммы решением задачи примера 1.
Выделим ячейку А35 под переменную Х1, ячейку В35 - под Х2, в ячейку С35 запишем формулу целевой функции в обозначениях EXCEL
=(B35-A35^2)^2+(1- A35)^2, в ячейку D35 запишем формулу ограничений
=0,68 - (A35^2+B35^2). Сделаем ячейку С35 текущей и дадим команду меню Сервис- Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С35, в поле Изменяя ячейки - адрес блока А35:В35. Теперь щелкнем по кнопке Добавить и в открывшемся новом диалоге в поле Ссылка на ячейку занесем адрес D35, выберем вид ограничения >= и правую часть ограничения - 0 (ноль). Щелкнув по кнопке ОК, вернемся к первоначальному диалогу.
Далее щелкнем по кнопке Параметры и выберем следующие переключатели: оценка - квадратичная, производные - прямые, метод - сопряженных градиентов. Щелкнув по кнопке Выполнить получим новый диалог Результаты поиска решения, в котором щелкнем по кнопке ОК. Результаты расчетов представлены в таблице. Особый интерес вызывает числовое значение в ячейке D35. Оно очень близко к нулю, но все же отрицательно, т.е. независимые переменные находятся в запрещенной области.
2.2 Решение задач
Пример 1. Решим задачу примера 5.1 методом штрафных функций. Как известно, координаты точки минимума есть (1;1). Введем ограничение типа неравенства (Х12+Х22)= 0 .
Вернемся к рабочему листу EXCEL, на котором проведено решение примера 5.1 методом покоординатного спуска. Там столбцы А и В отведены под независимые переменные, столбец С - под функцию f, столбец D - под значения погрешности D. Проведем подготовительный этап для метода штрафных функций. Для этого выделим блок А5:D17 и уничтожим его содержимое, нажав на клавиатуре клавишу "Delete”. В ячейку D3 занесем формулу = 0,64-(A3^2+B3^2), в ячейку Е3 - формулу =D3^2*(1- ЗНАК(D3)), где функция ЗНАК соответствует знаковой функции sign. Если теперь в ячейку F3 занести 1, то в ячейке G3 можно сформировать формулу расширенной целевой функции =C3+F3*G3. На этом подготовительный этап заканчивается.
1 итерация. Скопируем формулы блока С3:G3 в блок С4: G30. Следует заметить, что заранее неизвестно, сколько итераций потребуется для получения решения. Поэтому может случиться, что формулы из 3 строки придется скопировать и ниже 30 строки. Сделаем ячейку А4 пустой, а в ячейку В4 занесем 0,5. Теперь определим ячейку G4 текущей и проведем первый шаг метода покоординатного спуска так, как это описано в примере 6.1. Продолжим шаги метода покоординатного спуска до тех пор, пока модуль чисел в столбце Е не уменьшится на порядок по сравнению с числом в ячейке Е3.
2 итерация. Изменим значение величины коэффициента штрафа, занеся число 100 в соответствующую ячейку столбца F, и вновь продолжим покоординатный спуск до тех пор, пока модуль чисел в столбце Е снова не уменьшится еще на порядок.
После этого следует опять увеличить В на два порядка и так до тех пор, пока какое-нибудь число в строке Е не станет меньше по модулю заданного значения Е. Числа в соответствующей строке в столбцах А и В и есть координаты точки минимума.
Пример 2. Пусть некоторое предприятие может изготавливать изделия 4 типов. Для изготовления изделий требуются ресурсы 3 видов: трудовые ресурсы, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска одной единицы изделия каждого типа, называется нормой расхода. Пусть все нормы расхода известны и приведены в таблице
ресурсы изделие1 изделие2 изделие3 изделие4
трудовые 1 1 1 1
сырье 6 6 4 3
финансы 4 5 10 13
Пусть известна также прибыль, получаемая от реализации каждого типа изделия
изделие1 изделие2 изделие3 изделие4
прибыль 60 70 120 130
и располагаемое количество ресурсов
ресурсы наличие
трудовые 16
сырье 110
финансы 100
Необходимо найти такие количества изделий каждого типа, чтобы прибыль предприятия была максимальной.
Введем некоторые обозначения.
Пусть
аj - прибыль, получаемая от реализации единицы изделия j-го типа,
bi - располагаемое количество i-го ресурса,
сij - норма расхода i-го ресурса для изготовления единицы j-го изделия,
xj - неизвестное количество изделий j-го типа.
Целевую функцию - суммарную величину прибыли предприятия - можно записать так
u = а1x1+а2x2+а3x3+а4x4 max.
Зная нормы расхода и располагаемое количество каждого ресурса, можно составить систему ограничений:
Откроем новый рабочий лист и подготовим его к решению задачи. Внесем исходные данные так, как это показано на рисунке.
Теперь надо подготовить таблицы, связанные с решением задачи, ячейки для целевой функции и ограничений
Далее внесем необходимые формулы для расчета:
ячейка формула
D19 =CУММПРОИЗВ(В18:Е18;В10:Е10)
A22 =CУММПРОИЗВ(В18:Е18;В5:Е5)
A23 =CУММПРОИЗВ(В18:Е18;В6:Е6)
A24 =CУММПРОИЗВ(В18:Е18;В7:Е7)
A25 =B18
A26 =C18
A27 =D18
A28 =E18
После этого вызовем подпрограмму Сервис - Поиск решения. В появившемся диалоге внесем в окно Установить целевую ячейку адрес D19, в окно Изменяя ячейки адреса блока В18:Е18. Если в окне Ограничения оставлены какие-либо формулы от решения предыдущей задачи, их следует удалить по одному, выделяя каждое мышью и нажимая мышью кнопку Удалить. Затем следует внести нужные нам ограничения по одному, нажимая мышью кнопку Добавить. Каждый раз будет появляться новое диалоговое окно. Для первого ограничения в окно Ссылка на ячейку следует внести адрес А22, знак ограничения выбрать мышью из ниспадающего списка, а в правое окно занести адрес С22. Затем щелкнуть по кнопке Добавить и продолжить внесение ограничений.. Закончив ввод ограничений, щелкнем по кнопке ОК и снова попадем в окно Поиск решения.
Теперь щелкнем по кнопке Параметры. В открывшемся диалоге надо включить параметр Линейная модель. Щелкнув по кнопке ОК, возвратимся в окно Поиск решения.
Проверим, что переключатель указывает на поиск максимального значения и щелкнем по кнопке Выполнить. Появится новое диалоговое окно Результаты поиска решения. Если все формулы и ограничения были внесены правильно, то в этом окне будет написано "Решение найдено, Все ограничения и условия оптимальности выполнены”. Щелкнем по кнопке ОК и перейдем к анализу решения. Если же появится надпись "Поиск не может найти подходящего решения”, то щелкнем по кнопке Отмена и проверим правильность внесения исходных данных.
Результаты решения задачи примера приведены в таблице
изделие1 изделие2 изделие3 изделие4
кол-во 10 0 6 0
Значение целевой функции = 1320.
Анализ задачи линейного программирования на устойчивость и по пределам, который обычно проводят после получения решения, выходит за рамки данного пособия.
3 СОДЕРЖАНИЕ ОТЧЕТА
Отчет должен содержать:
1. титульный лист;
2. постановку задачи (согласно варианту);
3. краткое описание методов расчета нелинейных уравнений;
4. программную реализацию данных методов;
5. выводы о проделанной работе.
4 КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ
1. Какие методы условной оптимизации вы знаете?
2. Какой из методов условной оптимизации, в вашем случае, оказался наиболее быстрым и медленным?
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Бурляев В.В. Численные методы в примерах на EXCEL. Методическое пособие по дисциплине "Применение информационных технологий в химии и химической технологии”, 2 изд., испр. и доп., МИТХТ, 1999, с.63.
2. Антонов А.В. Системный анализ: учебник. – М.: Высш. шк., 2008. – 454 с.
3. Рапопорт Э.Я. Оптимальное управление системами с распределенными параметрами: учебное пособие. – М.: Высш. Шк., 2009. – 677 с.
Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной. Задачу минимизации можно сформулировать следующим образом:
Функцию удобно записать следующим образом:
где r – положительная величина.
Тогда функция принимает вид
Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача: Минимизировать при ограничениях ,.
Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку ∈, для которой , , скаляр и . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:
- параметр, значения которого убывают с каждой итерации при ; - положительные весовые коэффициенты.
Примерами штрафных функций являются:
1) обратная функция
2) логарифмическая функция
Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
Если , то остановиться. Решение является искомым.
В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.
Метод барьерных функций
Изложение метода
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек . Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать при ограничениях
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
- непрерывные функции, которые удовлетворяют условиям: , если и , если , , если и , если .
Типичными являются следующие выражения для функций :
, , где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции: минимизировать , где - штрафной коэффициент.
Пусть α– непрерывная функция. Обозначим .
Подход, связанный с барьерной функцией состоит в решении задачи вида:
максимизировать при ограничении
Алгоритм метода барьерных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях ,, где функции .
Начальный этап Выбрать Выбрать начальную точку , параметр штрафа и число . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При начальной точке и параметре штрафа решить следующую задачу:
Положить равным оптимальному решению задачи и перейти ко второму шагу.
Если , то остановиться.
В противном случае положить . Заменить k на k+1 и перейти к первому шагу.
Пример реализации
Рассмотрим задачу Розена-Сузуки и реализуем её решение с помощью метода штрафных функций. Задача Розена-Сузуки заключается в следующем: необходимо минимизировать функцию
со следующими ограничениями
Ниже приведена таблица промежуточных результатов алгоритма.
Число итераций | Значение миимизируемой функции | Координаты первой точки | Координаты второй точки | Координаты третьей точки | Координаты четвертой точки |
---|---|---|---|---|---|
0 | nfmin=-43.739500 | x1=-0.010000 | x2=0.990000 | x3=1.990000 | x4=-0.990000 |
10 | nfmin=-43.762449 | x1=-0.009498 | x2=0.990302 | x3=1.991304 | x4=-0.990502 |
20 | nfmin=-43.785381 | x1=-0.008996 | x2=0.990604 | x3=1.992607 | x4=-0.991004 |
30 | nfmin=-43.808298 | x1=-0.008494 | x2=0.990906 | x3=1.993910 | x4=-0.991506 |
40 | nfmin=-43.831199 | x1=-0.007993 | x2=0.991208 | x3=1.995212 | x4=-0.992007 |
50 | nfmin=-43.854084 | x1=-0.007491 | x2=0.991509 | x3=1.996514 | x4=-0.992509 |
Оптимальную точку мы получаем на 114й итерации с оптимальным значением функции
Рекомендация программисту
Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой , .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации дискретных шагов около границы возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции , т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции ,.
На эффективность метода барьерных функций существенно влияют выбор начального значения и метод сокращения значений в процессе минимизации, а также выбор весовых коэффициентов . Если в функции значение , выбирают слишком малым, то уже на начальной стадии процесса приходят к минимуму функции , который вряд ли окажется вблизи действительного условного минимума в точке ,. С другой стороны, если значение , выбирается слишком большим, то на первых итерациях вычислительного процесса текущая точка неизбежно окажется слишком далеко за пределами допустимой области, и поиск из-за необходимости возврата в пределы допустимой области окажется весьма затяжным.
Метод штрафных функций является одним из наиболее простых и широко применяемых методов решения нелинейных задач оптимизации. Идея метода основана на преобразовании исходной задачи с ограничениями в одну или последовательность задач безусловной оптимизации. Суть такого преобразования заключается в следующем. С помощью функций, задающих ограничения, строится так называемый штраф, который добавляется к целевой функции исходной задачи так, чтобы нарушение какого-нибудь ограничений становилось невыгодным с точки зрения полученной задачи безусловной оптимизации.
Рассмотрим задачу определения максимального значения вогнутой функции
где g(x) – выпуклая функция.
В соответствии с идеей метода штрафных функции исходную задачу условной оптимизации преобразуем в задачу безусловной оптимизации
Штрафная функция H(x) определяется ограничениями исходной задачи и имеет вид
где параметры αi(x) играют роль весовых коэффициентов. Излишне говорить, что штраф желателен только в недопустимых точках, поэтому
Процесс нахождения оптимального решения исходной задачи состоит в использовании штрафной функции для последовательного перехода из одной точки к другой, пока не получат приемлемое решение. Координаты последующей точки находят по формуле
(5.18)
где λ ∈ [0; 1]. Из этого выражения следует, что если предыдущая точка находится в области допустимых решений исходной задачи, то второе слагаемое в квадратной скобке равна нулю и переход к последующей точке определяется только градиентом целевой функции. Если же эта точка не принадлежит области допустимых решений, то за счет этого слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом чем меньше αi, тем быстрее находится приемлемое решение, однако точность его определения снижается. Поэтому итерационный процесс обычно начинают при малых αi и продолжая его αi постепенно увеличивают.
Укрупненный алгоритм метода штрафных функций состоит из следующих шагов.
Шаг 0. Определение исходного допустимого решения.
Шаг 1. Выбирают шаг вычислений.
Шаг 2. Находят частные производные от целевой функции f(x) и функции g(x).
Шаг 3. По формуле (5.18) находят координаты точки, определяющей возможное новое решение задачи.
Шаг 4. Новую точку проверяют на допустимость по ограничениям исходной задачи. Если нет, то переход на шаг 5. При допустимости найденного решения исследуется необходимость перехода к следующему допустимому решению. При необходимости такого перехода возврат на шаг 1. В противном случае найдено приемлемое допустимое решение исходной задачи.
Шаг 5. Устанавливают значения αi и переходят на шаг 3.
Пример 5.3. Необходимо максимизировать целевую функцию
(5.19)
(x1 – 7) 2 + x2 – 7) 2 ≤ 18, x1, x2 ≥ 0. (5.20)
Решение. Целевая функция данной задачи – отрицательно-определенная квадратичная функция и, следовательно, вогнута, а область допустимых решений – выпукла. Следовательно, эта задача является задачей выпуклого программирования для уяснения процесса поиска оптимального решения дадим геометрическую интерпретацию этой задачи. Построим область допустимых решений (рис. 5.1), определяемой ограничениями (5.20) и линии уровня, определяемые целевой функцией (5.19). Этими линиями служат окружности с центром в точке (0; 0). Точка касания одной из этих окружностей с областью допустимых решений в виде круга с центром в точке Е и является искомой точкой максимального значения целевой функции.
Рис. 5.1. Геометрическая интерпретация задачи
Для решения этой задачи воспользуемся методом штрафных функций.
Шаг 0. За исходное допустимое решение примем x 0 = (6; 7).
Шаг 1. Шаг вычислений выберем равным λ = 0,1.
Шаг 2. Представив функцию ограничения в виде
и определим частные производные от f(x) и g(x)
Теперь используя формулу (5.18) приступим к построению последовательности точек.
Шаг 3. Так как x0 = (6; 7) принадлежит области допустимых решений, то второе слагаемое в квадратной скобке формулы (5.18) равен нулю. Тогда координаты следующей точки x1 вычисляем по усеченной формуле (5.18)
Шаг 4. Полученное решение проверяем на допустимость по ограничениям исходной задачи
g(x 1 ) = (4,8 – 7) 2 + (5,6 – 7) 2 = (–2,2) 2 + (–1,4) 2 = 6,8 < 18.
Полученное решение является допустимым, а значение целевой функции.
g(x 2 ) = (3,84 – 7) 2 + (4,48 – 7) 2 < 18; f = –34,816.
g(x3) = (3,072 – 7)2 + (3,584 – 7)2 > 18.
Итерация 4. Полученное на итерации 3 решение не является допустимой, поэтому для определения нового решения используем формулу (5.18) с учетом второго слагаемого квадратной скобки
Здесь возникает вопрос о выборе числа α. Существует два подхода такого выбора. В первом случае надо взять значение α таким, чтобы точка x (4) не слишком далеко удалилась от границы области допустимых решений и вместе с тем принадлежала этой области. Такой достаточно произвольный выбор α зачастую увеличивает число итераций. Во втором случае используется формула Эрроу – Гурвица
i = 1, …, m,
где в качестве начального значения α берут любое неотрицательное число.
Воспользуемся вторым подходом, тогда
и по формуле (5.18) получим
При этом g(x (4) ) ≈ –8,181.
Продолжая таким образом находим приемлемое решение, когда, либо ограничение будет выполняться почти как равенство, либо, когда значения целевой функции для соседних итераций будут отличаться между собой на незначительную величину.
Читайте также: