Методы поиска минимума функции многих переменных

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ТАМБОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Г.Р. ДЕРЖАВИНА»

Институт математики, естествознания и информационных технологий

Кафедра математического моделирования и информационных технологий

Курсовая работа

Методы поиска минимума функции многих переменных

Студент 3 курса (3.1 группы)

Драб Елена Александровна

Научный руководитель

Зенкова Н.А.

Тамбов - 2016



Содержание

1. Основные сведения

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

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

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

3.2 Метод покоординатного спуска

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

3.4 Метод оврагов

3.5 Сопряженные направления

3.6 Случайный поиск

4. Разработка программного обеспечения

4.1 Выбор инструментальных средств

4.2 Описание программы

Заключение

Список использованных источников

программирование нелинейный компьютерный координатный



1. Основные сведения

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

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

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

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

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

Цель: Изучение различных методов поиска минимума функции многих переменных для случая овражной целевой функции.

Задачи:

· Изучение литературы по нелинейному программированию.

· Изучение литературы по методам оптимизации и по численным методам.

· Поиск методов минимизации овражных функций.

· Составление кода программы на языке программирования С++ для поиска минимума овражной целевой функции.

· Использование в качестве примера овражной функции функцию Розенброка.

Использование метода покоординатного спуска и метода оврагов для нахождения минимума функции Розенброка.



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

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

Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если f(x) - квадратичная функция, то имеем дело с задачей квадратичного программирования; если f(x) есть отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения[3].

В краткой форме задачу нелинейного программирования можно записать так: F (x) > max при условиях g (x) ? b, x ? 0, где x -- вектор искомых переменных; F (x) -- целевая функция; g (x) -- функция ограничений (непрерывно дифференцируемая); b -- вектор констант ограничений (выбор знака ? в первом условии здесь произволен, его всегда можно изменить на обратный).

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

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

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

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

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

Среди вычислительных алгоритмов нелинейного программирования большое место занимают градиентные методы. Универсального же метода для нелинейных задач нет и, по-видимому, может не быть, поскольку они чрезвычайно разнообразны. Особенно трудно решаются многоэкстремальные задачи [7].

В начале 60-х годов И.М. Гельфондом и М.Л. Цетлиным был дескриптивно задан класс невыпуклых функций многих переменных. Элементы класса характеризуются следующей структурой: в любой точке некоторого подмножества области определения функции существует такой базис, что все независимые переменные можно разделить на две группы. Первая группа состоит из тех аргументов, изменение которых приводит к значительному изменению целевой функции (в [4] они названы несущественными переменными). Изменение переменных второй группы (существенных переменных) приводит к незначительному изменению функции. При этом для любой точки подмножества вторая группа содержит лишь небольшое число параметров. Функция, допускающая такое разбиение переменных в некоторой области, называется хорошо организованной (овражной) функцией в этой области, а число существенных переменных определяет размерность оврага [4]. Характерное свойство овражной функции - скорость изменения функции существенно зависит от направления, вдоль которого производится измерение скорости, и от точки, в которой производится измерение[1].

Р.П. Федоренко [5] отмечает, что овражные функции совершенно закономерно возникают при конечно-разностной аппроксимации функционалов вариационных задач оптимального управления, и эти задачи требуют не общих, а узкоспециальных методов решения.



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

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

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

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

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

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

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

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

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

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

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

Рис. 3.1

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

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

Рис. 3.2

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

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

3.2 Метод покоординатного спуска

Изложение метода представим на примере функции трех переменных Ф(х, у, z). Выберем нулевое приближение х_0, у₀, z₀. Фиксируем значения двух координат у=у₀, z=z₀. Тогда функция будет зависеть только от одной переменной х; обозначим ее через f₁(x)=Ф(х, у₀, z₀). Найдем минимум функции одной переменной f₁(x) и обозначим его через х₁. Сделаем шаг из точки (х_0, у₀, z₀) в точку (х_1, у₀, z₀) по направлению, параллельному оси х; на этом шаге значение функции уменьшилось.

Затем из новой точки сделаем спуск по направлению, параллельному оси у, то есть рассмотрим f₂(у)=Ф(х₁, у, z₀), найдем ее минимум и обозначим его через у₁. Второй шаг приводит нас в точку (х₁, у₁, z₁)завершает цикл спусков.

Будем повторять циклы. На каждом спуске функция не возрастает, и при этом значения функции ограничены снизу ее значением в минимуме =Ф(, , ). Следовательно, итерации сходятся к некоторому пределу ?.

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

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

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

Рис. 3.3

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

(3.2)

Ф_хха 0, Ф_ууb 0, ¦Ф_ху¦ с, ab (3.3)

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

Значения функции вдоль траектории спуска не возрастают; поэтому траектория не может выйти из области G, и неравенства (3.3) будут выполняться на всех шагах. Рассмотрим один из циклов, начинающихся в точке А (рис. 3.3, а). Предыдущий из циклов окончился поиском минимума по направлению к у, следовательно, (Ф_у)_А=0 и ¦Ф_х¦_А= о₁ 0. Первый шаг нового цикла спускает нас по направлению х в точку В, в которой Ф_х = 0 и ¦Ф_у¦=з 0. Поскольку вторые производные непрерывны, можно применить теорему о среднем; получим:

где через с обозначены расстояния между точками. Отсюда получаем

со₁ аз. Выполним второй шаг цикла - спуск по направлению у в точку С, после которого (Ф_у)_С = 0 и ¦Ф_х¦_С = о₂. Объединяя эти неравенства, найдем

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

Значит, когда число циклов n > , то все первые производные линейно стремятся к нулю:

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

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

Фактическая скорость сходимости будет неплохой при малых q, когда линии уровня близки к эллипсам, оси которых параллельны осям координат. Для эллипсов, сильно вытянутых под значительным углом к осям координат, величина q 1 и сходимость очень медленная.

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

Метод спуска по координатам несложен и легко программируется на ЭВМ. Но сходится он медленно, а при наличии оврагов - очень плохо. Поэтому его используют в качестве первой попытки при нахождении минимума[2].

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

Спускаться можно не только параллельно осям координат. Вдоль любой прямой r = r₀ + at функция зависит только от одной переменной, Ф(r₀ + at) = ц(t).

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

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

Если функция является положительно определенной квадратичной функцией

(3.4)

то формулы наискорейшего спуска приобретают несложный вид. Вдоль прямой r = r_n + at функция (3.4) квадратично зависит от параметра t:

(3.5)

Из уравнения (dц/dt) = 0 легко находим ее минимум

(3.6)

дающий нам следующую точку спуска:

(3.7)

Направление наискорейшего спуска определяется градиентом квадратичной функции (3.4):



(3.8)

Подставляя это значение в формулы (3.6)-(3.7), получим окончательные выражения для вычисления последовательных спусков.

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

(3.9)

здесь л - собственные значения положительно определенной матрицы А (они вещественны и положительны). Если л_minл_max, что соответствует сильно вытянутым эллипсам - линиям уровня, то q 1 и сходимость может быть очень медленной. Есть такие начальные приближения (рис. 3.4), когда точно реализуется наихудшая возможная оценка, то есть в (3.9) имеет место равенство.

Рис. 3.4

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

Для улучшения метода наискорейшего спуска предлагают «кухонные» поправки к алгоритму - например, совершают по каждому направлению спуск не точно до минимума. Наиболее любопытным представляется такое видоизменение алгоритма. Будем делать по направлению, противоположному градиенту, только бесконечно малый шаг и после него вновь уточнять направление спуска. Это приводит к движению по кривой r(t), являющейся решением системы обыкновенных дифференциальных уравнений:

(3.10)

Вдоль этой кривой dФ/dt = (dФ/dr)(dr/dt) = (gradФ)² 0, т.е. функция убывает, и мы движемся к минимуму при t> +.

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

Однако от идеи метода еще далеко до надежного алгоритма. Фактически систему дифференциальных уравнений (3.10) надо численно интегрировать. Если интегрировать с большим шагом, то численное решение будет заметно отклоняться от линии градиента. А при интегрировании малым шагом сильно возрастает объем расчетов. Кроме того, если рельеф имеет извилистые овраги, то трудно ожидать хорошей сходимости этого метода.

Алгоритмы наискорейшего спуска и всех его видоизменений сейчас недостаточно отработаны. Поэтому метод наискорейшего спуска для сложных нелинейных задач с большим числом переменных (m 5) редко применяется, но в частных случаях он может оказаться полезным[2].

3.4 Метод оврагов

Рассмотрим задачу Ф(r) = min. Выберем произвольно точку с₀ и спустимся вниз из нее (например, по координатам), делая не очень много шагов, т.е. не требуя высокой точности сходимости. Конечную точку спуска обозначим r₀. Если рельеф овражный, эта точка окажется вблизи дна оврага (рис. 3.5).

Рис. 3.5

Теперь выберем другую точку с₁ не слишком далеко от первой. Из нее также сделаем спуск и попадем в некоторую точку r₁. Эта точка тоже лежит вблизи дна оврага. Проведем через точки r₀ и r₁ на дне оврага прямую - приблизительную линию дна оврага, передвинемся по этой линии в сторону убывания функции и выберем новую точку

с₂ = r₁ (r₁ r₀)h, (3.11)

h = const 0.

В формуле (3.11) выбирается плюс, если Ф (r₁) (r₀), и минус в обратном случае, так что движение направлено в сторону понижения дна оврага. Величина h называется овражным шагом и для каждой функции подбирается в ходе расчета.

Дно оврага не является отрезком прямой, поэтому точка с₂на самом деле лежит не на дне оврага, а на склоне. Из этой точки снова спустимся на дно и попадем в некоторую точку r₂. Затем соединим точки r₁и r₂ прямой, наметим новую линию дна оврага и сделем новый шаг по оврагу. Продолжим процесс до тех пор, пока знаения функции на дне оврага, т.е. в точках r_n, убывают. В случае, когда Ф(r_n+1)Ф(r_n), процесс надо прекратить и значение r_n+1не использовать.

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

Методом оврагов удается находить минимумы достаточно сложных функций от 5-10 переменных. Но этот метод довольно капризен. Для каждой функции приходится подбирать свой овражный шаг, визуально наблюдать за ходом расчета и вносить коррективы. Программирование этого метода на ЭВМ несложно[2].

3.5 Сопряженные направления

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

(3.12)

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

Положительно определенная матрица позволяет ввести норму вектора следующим образом:

(3.13)

Определение (3.13) означает, что под скалярным произведением двух векторов x и у теперь подразумевается величина (х, Ау). Векторы, ортогональные в смысле этого скалярного произведения

(х, Ау) = 0 (3.14)

называют сопряженными (по отношению к данной матрице А).

На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и другие.

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

Сначала рассмотрим, как применяется этот метод к квадратичной форме (3.12). Для этого нам потребуются некоторые свойства сопряженных векторов.

Пусть имеется некоторая система попарно сопряженных векторов х_i. Нормируем каждый из этих векторов в смысле нормы (3.14), тогда соотношения между ними примут вид

(3.15)

Докажем, что взаимно сопряженные векторы линейно-независимы. Из равенства



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

Пусть нашли некоторый спряженный базис х_i, 1 in. Выберем произвольную точку r₀. Любое движение из этой точки можно разложить по сопряженному базису

(3.16)

Подставляя это выражение в правую часть формулы (3.12), преобразуем ее с учетом сопряженности базиса (3.15) к следующему виду:

(3.17)

Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (3.16). Это означает, что движение по одному из сопряженных направлений х_i меняет только один член суммы (3.17), не затрагивая остальных.

Совершим из точки r₀поочередные спуски до минимума по каждому из сопряженных направлений x_i. Каждый спуск минимизирует свой член суммы (3.17), так что минимум квадратичной функции точно достигается после выполнения одного цикла спусков, то есть за конечное число действий.

Сопряженный базис можно построить способом параллельных касательных плоскостей.

Пусть некоторая прямая параллельна вектору х, а квадратичная функция достигает на этой прямой минимального значения в точке r₀. Подставим уравнение этой прямой r = r₀ + бx в выражение (3.12) и потребуем выполнения условия минимума функции

ц(б) = Ф(r₀) + б² + б (x, 2Аr₀ + b),

и положим (dц/dб)_б-0 = 0. Отсюда следует уравнение, которому удовлетворяет точка минимума:

(х, 2Аr₀ + b) = 0. (3.18)

Пусть на какой-нибудь другой прямой, параллельно первой, функция принимает минимальное значение в точке r₁;тогда аналогично найдем (х, 2Аr₁ + b) = 0. Вычитая это равенство из (3.18), получим

(х, А(r₁r₀)) = 0. (3.19)

Следовательно, направление, соединяющее точки минимума на двух параллельных прямых, сопряжено направлению этих прямых.

Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору х. Для этого достаточно провести две прямые, параллельные х, и найти на каждой прямой минимум квадратичной формы (3.12). Вектор r₁r₀, соединяющий эти минимумы, сопряжен х. Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа.

Пусть имеются две параллельные m-мерные плоскости, порожденные системой сопряженных векторов х_i, 1 imn. Пусть квадратичная функция достигает своего минимального значения на этих плоскостях соответственно в точках r₀и r₁. Аналогичными рассуждениями можно доказать, что вектор r₁r₀, соединяющий точки минимума, сопряжен всем векторам х_i. Следовательно, если задана неполная система сопряженных векторов х_i, то этим способом всегда можно построить вектор r₁r₀, сопряженный всем векторам этой системы.

Рассмотрим один цикл процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние m векторов взаимно сопряжены, а первые n-m векторов не сопряжены последним. Найдем минимум квадратичной функции (3.12) в какой-нибудь m-мерной плоскости, порожденной последними mвекторами базиса. Поскольку эти векторы взаимно сопряжены, то для этого достаточно произвольно выбрать точку r₀и сделать из нее спуск поочередно по каждому из этих направлений (до минимума). Точку минимума в этой плоскости обозначим через r₁.

Теперь из точки r₁сделаем поочередный спуск по первым n - m векторам базиса. Этот спуск выведет траекторию из первой плоскости и приведет ее в некоторую точку r₂. Из точки r₂ снова совершим по последним m направлениям спуск, который приведет в точку r₃. Этот спуск означает точное нахождение минимума во второй плоскости, параллельной первой плоскости. Следовательно, направление r₃ - r₁сопряжено последним m векторам базиса.

Если одно из несопряженных направлений в базисе заменить направлением r₃ - r₁, то в новом базисе уже m + 1 направление будет взаимно сопряжено.

Начнем расчет циклов с произвольного базиса; для него можно считать, что m=1. Описанный процесс за один цикл увеличивает на единицу число сопряженных векторов в базисе. Значит, за n - 1 цикл все векторы базиса станут сопряженными, и следующий цикл приведет траекторию в точку минимума квадратичной функции (3.12).

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

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

Благодаря квадратичной сходимости метод сопряженных направлений позволяет находить минимум с высокой точностью. Методы с линейной сходимостью обычно определяют экстремальные значения координат менее точно.

Метод сопряженных направлений является, по-видимому, наиболее эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа - «плато», и при большом числе переменных - до двух десятков[2].

3.6 Случайный поиск

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

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

Даже при миллионе пробных точек вероятность того, что хотя бы одна точка попадает в небольшую окрестность локального минимума, ничтожна мала. В самом деле, пусть диаметр котловины около минимума составляет 10% от пределов изменения каждой координаты. Тогда объем этой котловины составляет 0,1ⁿ часть объема n-мерного куба. Уже при n 6 ни одна точка в котловину не попадает.

Поэтому берут небольшое число точек N (5 - 20)nи каждую точку рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью.

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

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

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

Метод случайного поиска зачастую позволяет найти все локальные минимумы функции от - 10-20 переменных со сложным рельефом. Он полезен и при исследовании функции с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Если зададим слишком широкую область, то ее труднее детально исследовать, а если выберем слишком узкую область, то многие локальные минимумы могут оказаться вне ее. Правда, положение несколько облегчается тем, что при спусках траектории могут выйти за пределы заданной области и сойтись к лежащим вне этой области минимумам[2].



4. Разработка программного обеспечения

4.1 Выбор инструментальных средств

Для реализации программы нахождения минимума функции многих переменных для случая овражной целевой функции был выбран язык программирования С++.

Выбор данного языка обоснован тем, что С++ - чрезвычайно мощный язык, содержащий средства создания эффективных программ практически любого назначения, от низкоуровневых утилит и драйверов до сложных программных комплексов самого различного назначения. В частности:

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

· Пользовательские функции-операторы позволяют кратко и ёмко записывать выражения над пользовательскими типами в естественной алгебраической форме.

· Кроссплатформенность: стандарт языка накладывает минимальные требования на ЭВМ для запуска скомпилированных программ. Доступны компиляторы для большого количества платформ, на языке С++ разрабатывают программы для самых различных платформ и систем.

· Эффективность.

· Имеется возможность работы на низком уровне с памятью, адресами.

· Язык поддерживает понятия физической (const) и логической (mutable) константности. Это делает программу надежнее, так как позволяет компилятору, например, диагностировать ошибочные попытки изменения значения переменной.



4.2 Описание программы

Данная программа предназначена для нахождения минимума овражной целевой функции. В качестве примера была выбрана функция Розенброка - не выпуклая функция, используемая для оценки производительности алгоритмов оптимизации, предложенная Ховардом Розенброком в 1960году. Считается, что поиск глобального минимума для данной функции является нетривиальной задачей. Имеет минимум 0 в точке (1,1).

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

При запуске программы (Рис. 4.1) в первой строчке появляется сообщение «Программа поиска минимума на примере функции Розенброка».

Рис. 4.1

Во второй строчке требуется ввести координату начальной точки (ввести необходимо два значения через пробел) и нажать Enter.

В третьей строчке (Рис. 4.2) выводится найденное значение минимума методом покоординатного спуска. В четвёртой строчке (Рис. 4.2) выводится найденное значение минимума методом оврагов.



Рис. 4.2



Заключение

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

Метод спуска по координатам несложен, но плохо подходит для поиска минимума овражных функций, т.к. попадая на дно оврага, не продолжает свое движение вдоль него.

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



Список использованных источников

1.Ларичев О.И., Горвиц Г.Г. «Методы поиска локального экстремума овражных функций» М.: Наука, 1990.

2.Калиткин Н.Н. «Численные методы» М.: Наука, 1978.

3.Рейзлин В. И. «Численные методы оптимизации» - Томск: Изд-во Томского политехнического университета, 2011.

4.Гельфонд И.М., Цетлин М.Л. «О некоторых способах управления сложными системами». УМН, 2002.

5.Федоренко Р.П. «Об одном алгоритме решения задач математического программирования». Журнал вычислительная математика, 2006.

6.Сухарев А.Г., Тимохов А.В., Федоров В.В. «Курс методов оптимизации»: Учеб. пособие. - 2-е изд. - М.: ФИЗМАТЛИТ, 2005.

7.Лопатников Л. И. «Экономико-математический словарь: Словарь современной экономической науки.» - М.: Дело., 2003.

Размещено на Allbest.ru

...