Математические модели и методы нелинейного программирования. Численные оптимизационные методы переменной метрики - Курсовая работа

Для каждой задачи строится определенная математическая модель и в зависимости от нее происходит выбор соответствующего алгоритма (метода) оптимизации. Цель работы: Изучение теории численной оптимизации переменной метрики и создание программы, демонстрирующей работу некоторых методов данного типа оптимизации. Для таких задач, как правило, строится математическая модель, благодаря которой происходит выбор метода оптимизации, состоящего из определенных операций (сам метод тоже является операцией). Операция есть всегда управляемое мероприятие, то есть от лица, принимающего решение (ЛПР) зависит, каким способом выбрать некоторые параметры, характеризующие ее организацию. Если шаги определяются последовательно путем минимизации в направлении , то все методы, с помощью которых вычисляют симметрическую матрицу , удовлетворяющую (1.4в), дают направления, являющиеся взаимно сопряженными (в случае квадратичной целевой функции).В ходе курсовой работы был написан модуль, содержащий реализацию методов переменной метрики (метод Бройдена, метод Дэвидона - Флетчера - Пауэлла), а также реализована программа для работы с данным модулем.

Оглавление

Введение

Основные понятия

Оптимизационные методы переменной метрики

Метод Бройдена (??(k) имеет ранг 1)

Метод Дэвидона - Флетчера - Пауэлла

Алгоритмы Пирсона

Метод Флетчера

Инструкция пользователя

Заключение

Список литературы

Когда говорят о задачах математического программирования (планирования), то имеют в виду класс задач оптимизации, возникших ближе к концу Второй мировой войны в связи с попытками повысить эффективность промышленных, транспортных, военных систем за счет улучшений в работе координирующих и управляющих органов. Несмотря на разнообразие смыслового содержания таких задач, все они с формальной точки зрения сводятся к одной общей постановке: найти значения переменных, доставляющие максимум (минимум) некоторой скалярной функции при некоторых условиях. Для каждой задачи строится определенная математическая модель и в зависимости от нее происходит выбор соответствующего алгоритма (метода) оптимизации.

Объектом исследования данной курсовой работы стали численные оптимизационные методы переменной метрики.

Цель работы: Изучение теории численной оптимизации переменной метрики и создание программы, демонстрирующей работу некоторых методов данного типа оптимизации.

Для достижения поставленной цели были решены следующие задачи: 1. Изучение теории численной оптимизации переменной метрики;

2. Написание модуля, включающего реализацию некоторых методов.

3. Реализация программы, демонстрирующей работу модуля.

Основные понятия

Исследование операций (ИО) - дисциплина, зародившаяся в 40-е - 50-е года 20 столетия, занимающаяся разработкой и применением методов нахождения оптимальных решений на основе математического моделирования, статистического моделирования и различных эвристических подходов в различных областях человеческой деятельности.

Часто возникает необходимость решения задач, проблема которых состоит в оптимизации расходов сырья, денежных расходов и т.п. Для таких задач, как правило, строится математическая модель, благодаря которой происходит выбор метода оптимизации, состоящего из определенных операций (сам метод тоже является операцией).

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели. Операция есть всегда управляемое мероприятие, то есть от лица, принимающего решение (ЛПР) зависит, каким способом выбрать некоторые параметры, характеризующие ее организацию. «Организация» в данном случае понимается в широком смысле слова, включая набор технических средств, применяемых в операции.

Всякий определенный выбор зависящих от ЛПР параметров называется решением. Решение может быть как удачным, так и неудачным. Оптимальным называется решение, которое по тем или иным признакам предпочтительнее других.

Математическое моделирование - замена реального изучаемого объекта объектом заменителем - математической моделью - и, в дальнейшем - изучение модели с помощью реализуемых на персональном компьютере вычислительно-логических алгоритмов. Соответственно, математическая модель - это модель, которая, с помощью некоторых математических законов, описывает основные интересующие исследователя стороны исследуемого объекта.

Основным делением по классам задач математического моделирования является деление по характеру взаимосвязи между переменными: * Линейные - задачи, в основе которых лежат линейные зависимости;

* Нелинейные - задачи, учитывающие нелинейные связи между факторами.

Задачами нелинейного программирования называются задачи, общая постановка которых следующая: Найти неотрицательные значения переменных х1, x2, ... , xn, удовлетворяющие каким-то ограничениям произвольного вида, например:

(1.1) и обращающие в максимум (минимум) произвольную нелинейную функцию этих переменных:

(1.2)

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

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

Оптимизационные методы переменной метрики

Класс методов, называемых методами переменной метрики, также называют квазиньютоновскими или градиентными с большим шагом. Эти методы аппроксимируют матрицу Гессе или обратную к ней, но используют для этого только первые производные.

- градиент или вектор столбец из первых частных производных f(x) по x, значения которых берутся в данной точке x.

При использовании методов переменной метрики новый вектор x вычисляется по вектору предыдущего шага с помощью уравнения: , (1.3) где матрица , которую иногда называют матрицей направлений, представляет собой аппроксимацию .

Рассмотрим соотношение, связывающее и , для случая квадратичной целевой функции (или квадратичной аппроксимации целевой функции)

(1.4а)

Умножая обе части этого уравнения на , получаем

(1.4б)

При этом если квадратична, то , то есть постоянная матрица. Уравнение (1.4б) можно рассматривать как систему n линейных уравнений, содержащих n неизвестных параметров, которые нужно оценить для того, чтобы аппроксимировать или при заданных значениях , и на более ранних этапах поиска. Для решения этих линейных уравнений могут быть использованы различные методы, каждый из которых приводит к различным методам переменной метрики.

В довольно большой группе методов аппроксимируется с помощью информации, полученной на k-ом шаге: , (1.5) где ?(x) - матрица, аппроксимирующая . представляет собой определяемую матрицу, а - масштабный множитель, константа, обычно равная единице. Выбор по существу определяет метод переменной метрики. Для обеспечения сходимости должна быть положительно определенной и удовлетворять уравнению (1.4б) в том случае, когда она заменяет .

На (k 1)-м шаге мы знаем , , и и хотим вычислить , так чтобы удовлетворялось соотношение

(1.4в)

Пусть . Тогда уравнение

(1.4г) нужно разрешить относительно . Прямой подстановкой результата можно показать, что уравнение (1.4г) имеет следующее решение: , (1.6) где y и z - произвольные векторы размерности n x 1. Если для ? = 1 выбирается линейная комбинация двух направлений и , а именно

, то используем алгоритм Бройдена; если же берется

, , то матрицу вычисляем с помощью алгоритма Дэвидона - Флетчера - Пауэлла.

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

Метод Бройдена (??(k) имеет ранг 1)

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

. (1.7) где

, .

В простейшем алгоритме этого типа минимизация начинается с выбора начальной точки x(0) и некоторого ?(0) > 0; затем последовательно применяются уравнения (1.3), (1.5), (1.7) до тех пор, пока, к примеру, . Если для каждого направления поиска представляет собой скаляр, минимизирующий в этом направлении, то данный метод дает сопряженные направления поиска. Таким образом, при определенных ограничивающих условиях описанному алгоритму обеспечена сходимость. Одной из интересных особенностей методов ранга 1 является то, что (или ) в уравнении (1.3) не обязательно должно быть параметром, минимизирующим . Бройден показал, что может быть произвольным параметром, пока не возникла сингулярность или знаменатель в правой части уравнения (1.7) не обратился в нуль. Это свойство позволяет отказаться от одномерного поиска, если есть адекватные альтернативные методы определения .

В случае, когда целевая функция не является квадратичной, применение уравнения (1.7) может привести к следующим нежелательным явлениям: 1) Матрица может перестать быть положительно определенной. В этом случае необходимо обеспечить положительную определенность матрицы .

2) Вычисляемая величина может стать неограниченной (иногда даже в случае квадратичных функций вследствие ошибок округления).

3) Если случайно совпадает с направлением предыдущего этапа, матрица становится сингулярной или неопределенной.

Метод Дэвидона - Флетчера - Пауэлла

В методе Дэвидона, модифицированном Флетчером и Пауэллом, выбирается матрица , имеющая ранг 2. В данном методе не нужна операция обращения матрицы, как и в методе Бройдена. Матрица направлений перевычисляется таким образом, чтобы для квадратичной целевой функции в пределе после n шагов она равнялась . Исходная матрица обычно выбирается в виде единичной матрицы (но может быть и любой симметрической положительно определенной матрицей), так что исходное направление минимизации - это направление наискорейшего спуска. Оценка элементов в точке x* (экстремум) тем лучше, чем лучше мы выберем по сравнению с единичной матрицей исходную , однако выбор определенно предпочтительнее приравнивания элементов значениям аналитических частных производных или их конечно-разностных приближений в начальной точке . В ходе оптимизации имеет место постепенный переход от градиентного направления к ньютоновскому; при этом используются преимущества каждого из этих двух методов на соответствующем этапе.

Соотношение для в алгоритме Дэвидона - Флетчера - Пауэлла можно получить путем подстановки и в уравнение (1.6). Тогда имеем

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

Рекуррентное соотношение (1.7а) на практике вполне удовлетворительно, если: 1) Ошибка при вычислении невелика;

2) не становится «плохой».

Роль матрицы в формуле (1.7а) заключается в обеспечении того, чтобы , тогда как матрица обеспечивает положительную определенность на всех этапах и в пределе исключает начальную матрицу . Используем формулу (1.7а) на нескольких этапах, начиная с начальной матрицы:

, , .

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

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

Флетчер и Пауэлл предложили выбирать первую длину из последовательности ?* с помощью следующего уравнения

, где - наименьшее ожидаемое значение ;

либо положить .

Алгоритмы Пирсона

Алгоритм Пирсона №2: Положим в уравнении (1.6) , а . Тогда

, (1.8)

, где - произвольная положительно определенная симметрическая матрица. Алгоритм Пирсона №2 обычно приводит к «плохим» матрицам направлений.

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

Алгоритм Пирсона №3. Положим в уравнении (1.6) , а .

Тогда , (1.9) .

Метод Флетчера

, (1.10)

Описываемый алгоритм использует (1.7а). если , и (1.10), если .

Можно также использовать линейные комбинации уравнений (1.10) и (1.7а). Поскольку матрица , вычисленная с помощью уравнения (1.7а), стремится к нулю с увеличением числа шагов, а , вычисленная с помощью соотношения (1.10), стремится к бесконечности, имеет смысл применять оба типа уравнений.

Эффективной процедуру Флетчера делает скорее не метод вычислений , а кубическая интерполяция при отыскании минимума в данном направлении и ограниченная длина шага. При этом скаляр выбирается с помощью уравнения , где - нижняя оценка значений . (Если оказывается ниже, чем , то имеет место окончание процесса.). Для достижения минимума в направлении поиска используется кубическая интерполяция на интервале между и . Поскольку для проведения кубической интерполяции не требуется использование всего интервала, содержащего минимум, и результат интерполяции может оказаться неудовлетворительным, если находится на вогнутой части аппроксимирующего полинома, Флетчер ограничил значение следующим образом: либо оно должно быть меньше, чем , получаемое с помощью кубической интерполяции, либо , где верхний индекс s обозначает номер в последовательности шагов при одномерном поиске.

После каждого шага проводится тест , и если он удовлетворен, то этап считается завершенным. В противном случае продолжается кубическая интерполяция. Окончательно процесс завершается, когда . Во избежание большого влияния ошибок округления или ошибок программ вычисления производных программа останавливается, когда и и (или) .

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

Инструкция пользователя

Программа Project1 написана на языке Object Pascal на платформе Delphi 7.0. Данная программа представляет собой реализацию следующих методов: метод Бройдена, метод Дэвидона - Флетчера - Пауэлла, для функции Розенброка f(x, y) = (1 - x)2 100(y - x2)2 > min.

Основной вид программы:

Рис. 1.: Программа Project1. Основной вид.

Контейнер Method является контейнером выбора соответствующего метода.

· Broyden’s method - метод Бройдена;

· Method Davidon-Fletcher-Powell - метод Дэвидона - Флетчера - Пауэлла.

Для того, чтобы выбрать соответствующий метод, наведите курсором мыши на надпись интересующего вас метода и щелкните по этой надписи. В случае успеха рядом с надписью в белый круг будет вписан черный круг.

Контейнер X[0] содержит значения начального вектора. Для того, чтобы ввести определенное значение, в рамках данного контейнера наведите курсором мыши на поле ввода и введите число.

Контейнер N[0] содержит начальную матрицу направлений. Способ ввода аналогичный приведенному выше.

Контейнер Answer отображает ответ в случае успешного окончания соответствующего метода.

Контейнер w содержит значение масштабного множителя. Данный параметр используется только в методе Бройдена.

Контейнер eps содержит в себе значение точности. То есть это точность данного метода.

Кнопка Click. Запуск выбранного метода. Для запуска метода нажмите на кнопку Click.

В случае успешного завершения метода: рядом с надписью «Колво итераций:» будет показано число шагов, за которое был найден ответ с заданной точностью; рядом с надписью «Значение функции Розенброка:» будет показано значение функции Розенброка от переменных, найденных с заданной точностью по выбранному методу.

В случае неудачного завершения метода:

Рис. 2.: Программа Project1. Метод не нашел минимум функции Розенброка с заданной точностью в 255 шагов.

Надпись «Колво итераций: Количество итераций превысило число 255» означает, что данный метод не нашел ответ с заданной точностью в 255 шагов.

Строка «NONE» в полях ввода Answer и рядом с надписью «Значение функции Розенброка:» означают, что ответ не был найден, а, следовательно, и значение функции Розенброка тоже неизвестно. Это связано с тем, что в программе стоит ограничение: если метод совершает более 255 шагов, то метод завершает свою работу, так и найдя подходящий ответ.

Если вылезло данное окно, то произошел сбой в работе программы. Для того, чтобы избавиться от данного окна, нажмите кнопку «ОК». В таком случае программа Project1 прекратит свою работу.

Рис. 3.: Программа Project1. Сбой в работе программы.

В ходе курсовой работы был написан модуль, содержащий реализацию методов переменной метрики (метод Бройдена, метод Дэвидона - Флетчера - Пауэлла), а также реализована программа для работы с данным модулем. Были рассмотрены основы теории численной оптимизации переменной метрики.

1. Дягтерев Ю.И. Методы оптимизации - М.: Сов. радио, 1980. - 272 с.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. - М.: Наука, 1988. - 208 с.

3. Химмельблау Д. Прикладное нелинейное программирование. - М.: Мир, 1975. - 536 с.

4. Википедия: Свободная Энциклопедия. Статья: Исследование операций. [On-Line]: .

Размещено на