Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных (стр. 1 из 4)
Введение
1. Пояснительная записка
1.1 Нелинейное программирование
1.2 Численные методы в задачах без ограничений
1.2.1 Общая схема методов спуска
1.2.2 Градиентные методы
1.2.3 Метод наискорейшего спуска
2. Инструментальные программные средства
3. Блок-схема алгоритма моделирования
4. Операционная среда
5. Контрольная задача
Заключение
Литература
Приложение
Проблема выбора оптимального варианта решения относится к числу наиболее актуальных технико-экономических проблем. В математической постановке она представляет собой задачу минимизации (максимизации) некоторого функционала, описывающего те или иные характеристики системы.
Численное решение оптимизационных задач на ЭВМ сводится к поиску экстремума функции многих переменных. Таковы задачи оптимального управления и идентификации, задачи супервизорного управления, оптимизационного проектирования и планирования.
Среди различных типов оптимизационных задач особое место занимают задачи оптимизирования невыпуклых детерменированных функций с единственной точкой экстремума.
Эти задачи представляют интерес с различных точек зрения. Прежде всего не выпуклость порождает большие аналитические сложности при разработке методов решения унимодальных задач. Как известно, аналитические методы развиты для значительно простых задач.
Для линейных, квадратичных, выпуклых задач разработаны различные численные методы решения, доказана сходимость методов, получены оценки скорости сходимости.
Ничего подобного не сделано для унимодальных задач общего вида, исключая задачи минимизации функции одной переменной. На практике класс унимодальных задач не является чем-то необычным. Имеются многочисленные примеры, когда в интересующей нас области определения функции существует лишь один экстремум. Если при этом оптимизируемая функция имеет сложный вид или задана неявно, то ее выпуклость ничем не гарантируется. В этой ситуации естественно применим метод оптимизации, ориентированный на худший случай, т.е. на не выпуклость функции.
При этом, число работ, посвященных унимодальным задачам, сравнительно не велико. Аналитические методы исследования невыпуклых задач не разработаны из-за принципиальной сложности, численные методы, как правило, ориентированы на более простые классы задач.
1.1 Нелинейное программирование
Унимодальные функции. Выделим класс функций, обладающих, с вычислительной точки зрения, важным свойством. А именно: функция f называется унимодальной на отрезке [a,b], если она имеет на этом отрезке единственную точку глобального минимума Xmin и слева от этой точки является строго убывающей, а справа строго возрастающей (см. рис. 1). Другими словами, функция fунимодальная, если точка Xmin существует и единственна, причем для любых двух точек х1, х2 Î [a,b] таких, что х1<x2 из неравенства х1>Xmin всегда следует f(x1)<f(x2), а из неравенства x2<Xmin необходимо вытекает неравенство f(x1)>f(x2).
 |
Самого факта унимодальности недостаточно для получения аналитических результатов или построения эффективных числовых методов. В тоже время «распространенная трактовка выпуклых задач как хорошего модального объекта для задач одноэкстримальных теоретически не состоятельна - сложность классов выпуклых задач несравненно ниже, чем унимодальных.» [1]
Информационная сложность (нижняя граница оценки трудоемкости) задач минимизации непрерывных функций общего вида крайне велика, причем именно унимодальность (а не многоэкстремальность) является причиной такой сложности. В работе [2] отмечено, что информационная сложность класса унимодальных задач «фантастически велика». С точки зрения авторов книги [1], поиск универсальных методов решения унимодальных задач бесперспективен. Поэтому остается один путь – разработка специализированных методов для более узких классов задач.
Задача безусловной минимизации унимодальной функции многих переменных записывается обычно таким образом:
f(x)®min, xÎR (1.1)
Далее будем полагать, что f(x) –достаточное число раз дифференцируемая функция, которая в некотором диапазоне, разумном с точки зрения содержания задачи, имеет один экстремум. Точка X, в которой достигается минимум, называется решением задачи. Известно, что Ñf(x) = 0, где Ñf(x) – градиент f(x) в точке Х, а гессиан, если он существует в точке Х, является положительно определенной матрицей.
Наиболее изучен класс квадратичных функций многих переменных:
F(x) = (Ax,x)/2 + (b,x) + e, (1.2)
здесь А – симметрическая, положительно определенная матрица; b – вектор. Задача минимизации такой функции в принципе может быть решена аналитически, дифференцирование F(x) и приравнивание нулю производных дают систему линейных уравнений. В силу невырожденности матрицы система имеет единственное решение.
Квадратичные одноэкстримальные функции (1.2) принадлежат к более широкому классу строго выпуклых функций. Функция f(x) называется строго выпуклой, если для любых точек х1 и х2 из области ее определения имеет место неравенство:
F(lx1+(1-l)x2)< lf(x1)+(1-l)f(x2), lÎ(0,1).
Строго выпуклые функции унимодальные и обладают достоинством, облегчающим исследование и процесс численной минимизации, - это строгая выпуклость, а следовательно, одноэкстримальность вдоль любого направления. Более широким классом является класс линейно унимодальных функций [3]. Характерное свойство этого множества – унимодальность функций вдоль любой прямой в допустимой области. Функции, унимодальные по любому направлению, если это направление происходит через точку минимум, образуя класс строго унимодальных функций [3].
На рисунке 2 представлены : А – строго выпуклая; Б – линейно-унимодальная; В – строго унимодальная функции.
Специфика каждого из описанных классов может быть использована при построении методов минимизации.
В случае, когда свойства выпуклости, линейной или строгой унимодальности неверны или не могут быть проверены, при выборе метода решения целесообразно воспользоваться заведомо невыпуклой моделью минимизируемой функции.
В начале 60-х годов И.М. Гельфондом и М.Л. Цетлиным [4] был дескриптивно задан класс невыпуклых функций многих переменных. Элементы класса характеризуются следующей структурой: в любой точке некоторого подмножества области определения функции существует такой базис, что все независимые переменные можно разделить на две группы. Первая группа состоит из тех аргументов, изменение которых приводит к значительному изменению целевой функции (в [4] они названы несущественными переменными). Изменение переменных второй группы (существенных переменных) приводит к незначительному изменению функции. При этом для любой точки подмножества вторая группа содержит лишь небольшое число параметров. Функция, допускающая такое разбиение переменных в некоторой области, называется хорошо организованной (овражной) функцией в этой области, а число существенных переменных определяет размерность оврага [4]. Иными словами, для овражной функции точность линейного приближения
f(x) + Ñf(x) * Ñx в значительной степени зависит от Ñx [5].
В математическом энциклопедическом словаре под редакцией Ю.В. Прохорова дано строгое определение овражной функции.
Пусть «ограниченная снизу функция многих переменных
J * (x) = J(x1, x2, …, xm) Î c²(D), DÌR,
обладает той особенностью, что в исследуемой области собственные значения матрицы Гессе
, i, j = 1, 2, …, m,
упорядоченные в любой точке xÎD, удовлетворяют неравенствам
0 < |minli(x) | << l1(x).
В этом случае поверхность уровня J(x)=const имеют структуру, сильно отличающуюся от сферической. Такие функции J(x) называются овражными. Степень овражности характеризуется числом
S = l1(x) / |minli(x) |, li(x) ╪ 0.
Если собственные значения удовлетворяют неравенствам |lm(x)| <= … <= |lm-r+1(x)| << lm-r(x) << l1(x) , а отношение | lm-r+1(x) | / | lm(x) | невелико, то число r называется размерностью оврага.»
В отличие от локальных моделей, описывающих функцию и ее производные в малой окрестности заданной точки, овражная модель характеризует глобальные свойства функции.
«Конечно, такое разбиение параметров невозможно для любой функции, которую мог бы задать математик. Однако, для функций, встречающихся в практической деятельности человека (здесь имеются в виду разумные задачи физики, техники), такое разбиение, по-видимому, имеет место в очень значительном числе случаев.» [4]
Р.П. Федоренко [5] отмечает, что овражные функции совершенно закономерно возникают при конечно-разностной аппроксимации функционалов вариационных задач оптимального управления, и эти задачи требуют не общих, а узкоспециальных методов решения.
Простейшим примером овражной функции является квадратичная функция (1.2), где А – плохо обусловленная матрица. Число обусловленности симметрической матрицы является важной характеристикой ее свойств и определяется через собственные значения: k(A)=maxlA / minl4. Если k(A) велико, то А представляет собой плохо обусловленную матрицу, а задача (1.2) называется плохо обусловленной задачей минимизации. В этом случае f(x) определяет многомерную поверхность прямым (неизогнутым) оврагом.