Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Методы минимизации функций нескольких переменных





Из курса математического анализа известны следующие условия минимума функции 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, называется методом Ньютона минимизации функции многих переменных.
35. Задача линейного программирования

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

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

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида[2]:

при условиях

,

.

Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений[3]:

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

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

 

 







Дата добавления: 2015-04-19; просмотров: 3685. Нарушение авторских прав; Мы поможем в написании вашей работы!




Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...


Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


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


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Закон Гука при растяжении и сжатии   Напряжения и деформации при растяжении и сжатии связаны между собой зависимостью, которая называется законом Гука, по имени установившего этот закон английского физика Роберта Гука в 1678 году...

Характерные черты официально-делового стиля Наиболее характерными чертами официально-делового стиля являются: • лаконичность...

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

Сосудистый шов (ручной Карреля, механический шов). Операции при ранениях крупных сосудов 1912 г., Каррель – впервые предложил методику сосудистого шва. Сосудистый шов применяется для восстановления магистрального кровотока при лечении...

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

Мелоксикам (Мовалис) Групповая принадлежность · Нестероидное противовоспалительное средство, преимущественно селективный обратимый ингибитор циклооксигеназы (ЦОГ-2)...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия