Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных

Содержание

Введение

1. Пояснительная записка

1.1 Нелинейное программирование

1.2 Численные методы в задачах без ограничений

1.2.1 Общая схема методов спуска

1.2.2 Градиентные методы

1.2.3 Метод наискорейшего спуска

2. Инструментальные программные средства

3. Блок-схема алгоритма моделирования

4. Операционная среда

5. Контрольная задача

Заключение

Литература

Приложение

Введение

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

Численное решение оптимизационных задач на ЭВМ сводится к поиску экстремума функции многих переменных. Таковы задачи оптимального управления и идентификации, задачи супервизорного управления, оптимизационного проектирования и планирования.

Среди различных типов оптимизационных задач особое место занимают задачи оптимизирования невыпуклых детерменированных функций с единственной точкой экстремума.

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

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

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

При этом, число работ, посвященных унимодальным задачам, сравнительно не велико. Аналитические методы исследования невыпуклых задач не разработаны из-за принципиальной сложности, численные методы, как правило, ориентированы на более простые классы задач.

1. Пояснительная записка

1.2.1 Общая схема методов спуска

Будем рассматривать задачу безусловной минимизации, т.е. задачу минимизации целевой функции f на всем пространстве R. Сущность всех методов приближенного решения этой задачи состоит в построении последовательности точек х1, х2, х3, …, хk, …, монотонно уменьшающих значение целевой функции:

f(x0) >= f(x1) >= f(x3) >= … >= f(xk) >= … (1.3)

Такие методы (алгоритмы) называют методами спуска. При использовании этих методов применяют следующую схему.

Пусть на k-й итерации имеется точка хk. Тогда выбирают направление спуска pkÎR и длину шага вдоль этого направления ak > 0. Следующую точку последовательности вычисляют по формуле:

xk+1 = xk + ak*pk, k = 0, 1, 2, …

Согласно этой формуле, величина продвижения из точки xk в xk+1 зависит от как ak, так и от pk. Однако ak традиционно называют длиной шага.

Формально различают методы спуска отличные друг от друга способом выбора числа ak и вектора pk. Если для определения ak и pk требуется вычислять только значения целевой функции, соответствующий метод называют методом нулевого порядка или методами поиска. Методы первого порядка требуют, кроме того, вычисления первых производных целевой функции. Если же метод предполагает использование и вторых производных, то его называют методом второго порядка и т.д.

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

Важнейшей характеристикой любых методов спуска является их сходимость. Сходимость здесь понимается в том смысле, что последовательность {xk} должна сходиться к точке глобального (локального) минимума. Однако точки минимума могут составлять целое множество и многие алгоритмы позволяют построить последовательность {xk}, которая сама не является сходящейся, но любая ее сходящаяся последовательность имеет в качестве предельной некоторую точку минимум (см. рис. 3).

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

Возможен случай, когда ничего определенного сказать и о сходимости последовательностей нельзя, однако известно, что соответствующая последовательность значений при {f(xk)} сходится к точке минимального значения (локальный или глобальный минимум). Тогда говорят, что последовательность {xk} сходится к минимуму по функции (см. рис. 4). Кроме того, существуют еще более слабые типы сходимости, когда, например, последовательность {xk} (каждая ее последовательность) имеет в качестве предельной стаци

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать