Методы минимизации функций нескольких переменных
Из курса математического анализа известны следующие условия минимума функции n переменных. 1. Если в точке х0 Î En функция f (x) дифференцируема и достигает локального минимума, то f ¢(х0) = 0 или , j = 1,…, n (3.12) (необходимое условие минимумa). Точки, в которых выполнено условие (3.12), называются стaционaрными точкaми дифференцируемой функции f (x). 2. Если в стационарной точке х0 Î En, функция f (x) дважды дифференцируема и матрица ее вторых производных f ¢¢(х0) положительно определена, то х0 есть точка локального минимума f (x) (достаточное условие минимумa).
Классический метод Шаг 1. Решив систему уравнений (3.12), найти все стационарные точки функции f (x). Шаг 2. Используя достаточные условия минимума, среди стационарных точек функции f (x) найти точки локального минимума и, сравнивая значения функции в них, определить точки глобального минимума. Минимизация по правильному симплексу Правильным симплексом в пространстве En называется множество из п + 1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса. В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, в E3 – правильного тетраэдра. Шаг 0. Выбрать параметр точности e, базовую точку х0, ребро a и построить начальный симплекс по формулам где d1 , d2 , a– длина ребра.. Вычислить f (х0). Шаг 1. Вычислить значения f (х) в вершинах симплекса х1,.., xn. Шаг 2. Упорядочить вершины симплекса х0,.., хn так, что бы f (х0) £ …£ £f (х1) £ f (хn–1) £ f (хn). Шаг 3. Проверить условие (3.38) Если оно выполнено, то вычисления прекратить, полагая х*» х0, f *» f (x0). В противном случае перейти к шагу 4. Шаг 4. Найти и выполнить отражение вершины хn: =2xc – хn.Если f () <f (xn), то положить хn= и перейти к шагу 2. Иначе – перейти к шагу 5. Шаг 5. Найти и выполнить отражение вершины хn–1: = 2x c – хn–1. Если f () < f (хn–1), то положить хn–1 = и перейти к шагу 2. Иначе – перейти к шагу 6. Шаг 6. Перейти к новому правильному симплексу с вдвое меньшим ребром, считая базовой вершиной х0. Остальные п вершин симплекса найти по формуле хi = (хi + х0)/2, i=1,.., п. Перейти к шагу 1. Геометрическая иллюстрация работы алгоритма в пространстве показана на рис., где точки х0, х1, х2 – вершины начального симплекса, а пунктиром указаны процедуры отражения.
Метод циклического покоординатного спуска Этот метод заключается в последовательной минимизации целевой функции f (x) сначала по направлению первого базисного вектора е1, затем второго – е2 и т.д. После окончания минимизации по направлению последнего базисного вектора еn цикл повторяется. Шаг 0. Выбрать х Î En, критерий достижения точности (например, r(хk+1, хk) < e1; или |f (xk+1)–f (xk)| < e2);величину e. Найти f (x), положить j= 1. Шаг 1. Решить задачу одномерной минимизации Ф(a) = f (х + aеj)® min, a Î R, т.е. найти a*. Положить = х +a*еj, вычислить f (х). Шаг 2. Если j < п, то положить х = , j=j+1 и перейти к шагу 1, иначе – перейти к шагу 3. Шаг 3. Проверить условие достижения точности ||х– || < e или | f (x) – f ()| <e. Если оно выполняется, то положить х* = , f *=f () и закончить поиск. Иначе – положить х = , f (х) = f (), j = 1 и перейти к шагу 1.
МЕТОДЫ СЛУЧАЙНОГО ПОИСКА: Алгоритм 1 (с возврaтом при неудaчном шaге). Шаг 0. Выбрать параметр точности e > 0, начальный шаг a >0, коэффициент уменьшения шага g >1, предельное число неудачных попыток N, начальную точку х. Вычислить f (х). Шаг 1. Положить счетчик числа неудачных попыток j= 1. Шаг 2. Получить реализацию случайного вектора x. Шаг 3. Найти пробную точку y=x+ax/||x||, вычислить f (у). Шаг 4. Если f (у)< f (х), то положить х = у, f (х) = f (у) и перейти к шагу 3. Иначе – перейти к шагу 5. Шаг 5. Положить j =j + 1. Если j < N, то перейти к шагу 2, иначе к шагу. Шаг 6. Проверка условия достижения точности. Если a < e, то поиск завершить, полагая х*=х, f *= f (х). Иначе – положить a = a/у и перейти к шагу 1. Иллюстрация построения последовательности (3.41) с помощью описанного алгоритма для функции двух переменных приведена на рис. 3.10, где пунктиром показаны неудачные попытки определения хk+1 из (3.41), не приводящие к уменьшению f (х). Рис. 3.10. Иллюстрация работы алгоритма 1 в пространстве Е2. Замечание. На практике предельное число неудачных попыток N обычно полагают равным 3п, где п – число переменных целевой функции. Алгоритм 2 (наилучшей пробы). Этот алгоритм отличается от предыдущего только шагами 2 и 3: Шаг 2. Получить т реализации случайного вектора x: x1, …, xm Шаг 3. Найти пробные точки yi = , i = 1,.., т, выделить f (уi). Найти уk из условия f (уk)= и положить у= уk. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ, ИСПОЛЬЗУЮЩИЕ ПРОИЗВОДНЫЕ ФУНКЦИИ Пусть функция f (x) дифференцируема в En. В этом разделе рассматриваются итерационные процедуры минимизации вида X k = x k–1 + ak p k, k =1,.., x0 Î En, (3.48) где направление убывания рk определяется тем или иным способом с учетом информации о частных производных функции f (x), а величина шага а^>0 такова, что f (x k) < f (x k–1), k =1,2,.. (3.49) Так как функция предполагается дифференцируемой, то в качестве критерия останова в случае бесконечной итерационной последовательности {хk}, как правило, выбирается условие (3.30): ||f '(xk)|| <e, хотя, разумеется, могут быть использованы и другие критерии. метод градиентного спуска. Шаг 0. Задать параметр точности e > 0, начальный шаг a > 0, подобрать х Î En. Вычислить f (х). Шаг 1. Найти f '(x) и проверить условие достижения точности: ||f '(x)|| < e. Если оно выполнено, вычисления завершить, полагая х* = х, f *=f (х). Иначе – перейти к шагу 2. Шаг 2. Найти y=x–af '(x) и f (у). Если f (у) < f (х), то положить x =у, f (х) = f (у) и перейти к шагу 1, иначе – перейти к шагу 3. Шаг 3. Положить a=a/2 и перейти к шагу 2. МЕТОД НЬЮТОНА Пусть функция f (x) дважды дифференцируема в En. Тогда для нее можно записать разложение по формуле Тейлора в окрестности точки xk: f (x) = f (хk) + < f '(хk), x–xk > + < f ¢¢(хk)(x–xk), x–xk > +o (|| x–xk ||2) Отсюда видно, что поведение функции f (x) с точностью до величины порядка o(|| x–xk ||2) может быть описано квадратичной функцией Фk(x) = < f ¢¢(хk)(x–xk), x–xk > + < f '(хk), x–xk > + f (хk). (3.68) Минимизируем функцию Фk(x) вместо f (x). Найдем ее точку минимума xk+1 из условия Ф¢k(x) = 0: Ф¢k(x) = f ¢¢(хk)(x–xk) + f ¢(хk) = 0. (3.69) Пусть матрица Гессе f ¢¢(хk) положительно определена при всех xÎEn и, следовательно, невырождена (det f ¢¢(хk) > 0). Тогда существует обратная матрица [f ¢¢(хk)]–1. Отметим, что квадратичная функция (3.68) с положительно определенной матрицей f ¢¢(хk) сильно выпукла и уравнение (3.69) определяет единственную точку глобального минимума функции Фk(x). Умножим слева обе части равенства (3.69) на матрицу [f ¢¢(хk)]–1 и найдем точку минимума xk+1 квадратичной функции (3.68), аппроксимирующей f (x) в окрестности точки x=xk: xk+1 = xk – [f ¢¢(хk)]–1× f ¢(хk), k = 0, 1, … (3.70) Итерационный процесс –, начатый из произвольной точки x0ÎEn, называется методом Ньютона минимизации функции многих переменных. Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида[2]: при условиях , . Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений[3]: , Основную задачу можно свести к канонической путём введения дополнительных переменных. Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств. Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.
|