Метод покоординатного спуска 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.
Метод покоординатного спуска является одним из простейших методов многомерной оптимизации и неплохо справляется с поиском локального минимума функций с относительно гладким рельефом, поэтому знакомство с методами оптимизации лучше начинать именно с него.
Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной.
Алгоритм
- , , , . .
- Ищем экстремум функции . Положим, экстремум функции в точке .
- , , , . . Экстремум функции равен
- .
- , , , . .
В результате выполнения n шагов найдена новая точка приближения к экстремуму . Далее проверяем критерий окончания счета: если он выполнен – решение найдено, в противном случае выполняем еще один цикл.
Подготовка
Сверим версии пакетов:
Зададим функцию для отрисовки поверхности либо линий уровня, в которой было бы удобно регулировать границы графика:
В качестве модельной функции выберем эллиптический параболоид
Покоординатный спуск
Метод реализуем в функции принимающей название метода одномерной оптимизации, размерность задачи, желаемую погрешность, начальное приближение, и ограничения для отрисовки линий уровня. Всем параметрам зададим значения по-умолчанию.
Далее опробуем различные методы одномерной оптимизации
Метод Ньютона
Идея метода проста как и реализация
Ньютон довольно требователен к начальному приближению, а без ограничения по шагам вполне может ускакать в неведанные дали. Расчет производной желателен, но можно обойтись и малым варьированием. Модифицируем нашу функцию:
Обратная параболическая интерполяция
Метод не требующий знания производной и имеющий неплохую сходимость
Если взять начальное приближение похуже, метод начнет требовать немеренное количество шагов на каждую эпоху покоординатного спуска. В этом плане у него выигрывает братец
Последовательная параболическая интерполяция
Тоже требует три начальных точки, но на многих тестовых функциях показывает более удовлетворительные результаты
Выйдя из весьма дрянной стартовой точки дошло за три шага! Хорош… Но у всех методов есть недостаток — они сходятся к локальному минимуму. Возьмём теперь для исследований функцию Экли
Метод золотого сечения
Теория. Хоть реализация сложна, метод порой показывает себя хорошо перепрыгивая локальные минимумы
На этом с покоординатным спуском всё. Алгоритмы представленных методов довольно просты, так что имплементировать их на предпочитаемом языке не составит труда. В дальнейшем можно рассмотреть встроенные средства языка Julia, но пока хочется всё, так сказать, пощупать руками, рассмотреть методы посложней и поэффективней, затем можно перейти к глобальной оптимизации, попутно сравнивая с реализацией на другом языке.
Продолжаем знакомство с методами многомерной оптимизации.
Далее предложена реализация метода наискорейшего спуска с анализом скорости выполнения, а также имплементация метода Нелдера-Мида средствами языка Julia и C++.
Метод градиентного спуска
Поиск экстремума ведется шагами в направлении градиента (max) или антиградиента (min). На каждом шаге в направлении градиента (антиградиента) движение осуществляется до тех пор, пока функция возрастает (убывает).
За теорией пройдитесь по ссылкам:
Модельной функцией выберем эллиптический параболоид и зададим функцию отрисовки рельефа:
Зададим функцию реализующую метод наискорейшего спуска, которая принимает размерность задачи, точность, длину шага, начальное приближение и размеры рамки ограничивающей график:
На функции вычисляющей направление градиента можно заостриться в плане оптимизации.
Первое, что идет на ум — это действия с матрицами:
Чем действительна хороша Julia, так это тем, что проблемные места легко можно потестить:
Можно кинуться перепечатывать всё в Сишном стиле
Но как оказывается, оно само и без нас знает, какие типы надо ставить, так что приходим к компромиссу:
А теперь пусть рисует:
А теперь опробуем на функции Экли:
Свалилось в локальный минимум. Сделаем-ка шаги побольше:
Отлично! А теперь что-нибудь с оврагом, например функцию Розенброка:
Мораль: градиенты не любят пологостей.
Симплекс метод
Метод Нелдера — Мида, также известный как метод деформируемого многогранника и симплекс-метод, — метод безусловной оптимизации функции от нескольких переменных, не использующий производной(точнее — градиентов) функции, а поэтому легко применим к негладким и/или зашумлённым функциям.
Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.
Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс.
И сам симплекс метод:
И на десерт какую-нибудь буку… например функцию Букина
Локальный минимум — ну ничего, главное правильно подобрать стартовый симплекс, так что для себя я нашел фаворита.
Бонус. Методы Нелдера-Мида, наискорейшего спуска и покоординатного спуска на С++
На сегодня достаточно. Следующим этапом будет логично попробовать что-нибудь из глобальной оптимизации, набрать побольше тестовых функций, а затем изучить пакеты со встроенными методами.
Минимизация функции методом покоординатного спуска
Приветствую всех, кто зашел в эту тему. Друзья, прошу помочь разобраться с реализацией метода.
Функция-шаблон: вычисление локального экстремума функции методом спуска по градиенту
Создать функцию-шаблон для вычисления локального экстремума функции f(x) методом спуска по.
Из консоли на форму (программа нахождения экстремума функции методом наискорейшего спуска)
Здравствуйте, у меня есть программа нахождения экстремума функции методом наискорейшего спуска в.
Оптимизации методом покоординатного спуска
Есть код: clear all; clc; g = 0.05; % постоянная шага d = 0.01; % дельта % Начальная точка x1.
Добавлено через 43 секунды
Burk, Не могу понять, как составить программу.
Добавлено через 5 часов 12 минут
Вот и я затрудняюсь(((
Добавлено через 1 минуту
как вот это можно записать в программе?
Перевести код из Pascal в VBA - VBA (168408), там было переведено, но не до конца, подделал малость и получилось так (функцию и начальные значения переменных введите свои
Оптимизация методом покоординатного спуска
код программы есть. осталось найти минимизируемую функцию. Бункер для хранения зерна, для его.
Оптимизация методом покоординатного спуска
clear all; clc; format long; g = 0.5; % постоянная шага d = 0.01; % дельта % Начальная точка.
Решение задачи методом покоординатного спуска
Изучаю методики оптимизации, добрался до данного метода. Никак не могу понять его. Можете показать.
Как минимизировать функцию методом покоординатного спуска ?
Подскажите пожалуйста необходимо минимизировать функцию методом покоординатного спуска, ну.
Оптимизация методом покоординатного спуска (Гаусса-Зейделя)
Есть рабочий вариант: clear all; clc; % Значения коэффициентов c1 = -2; c2 = -1; c12 = 1; .
Поиск экстремума функции методом квадратичной интерполяции
поиск экстремума функции методом квадратичной интерполяции для довольно взятой функции
Читайте также: