лекция 3. Задача оптимизации формулируется следующим образом заданы множество х (допустимое множество задачи) и функция f(x)
 Скачать 2.35 Mb.
|
|
Нелинейная задача оптимизации. Кольцов С.Н 2014 www.linis.ru Задача безусловной оптимизации Задача оптимизации формулируется следующим образом: заданы множество Х (допустимое множество задачи) и функция f(x) (целевая функция), определенная на Х; требуется найти точки минимума или максимума функции f на Х. Задача оптимизации, в которой целевая функция подлежит минимизации, имеет вид: Точка x * ∈ X называется точкой глобального минимума f(x ) на множестве X, или глобальным решением задачи, если Точка x * ∈ X называется точкой локального минимума f(x ) на множестве X, или глобальным решением задачи, если Задача безусловной оптимизации для одномерной функции Необходимое условие локальной оптимальности. Пусть f (x) дифференцируема в точке x ∗ ∈R1. Если x ∗ − точка локального оптимума (экстремума), то Точки, удовлетворяющие вышеуказанному условию, называются стационарными. Стационарные точки могут быть и точками локального минимума, и точками локального максимума, и точками перегиба. Достаточное условие локальной оптимальности Пусть f(x) k раз, k>1, дифференцируема в точке x ∗ ∈ R1, причем Тогда, если k − четное число, то x ∗ − точка локального минимума (максимума) при f (k ) (x ∗ ) > 0 (при f (k ) (x ∗ ) < 0 ). Если k − нечетное число, то x ∗ − точка перегиба. Принцип определения точек глобального экстремума. Для определения точек глобальных экстремумов вычисляются предельные (при x→∞ и x→−∞) значения f(x). Если то f(x) не имеет конечного глобального максимума . Если то f(x) не имеет конечного глобального минимума . Если f(x) имеет конечный глобальный максимум и (или) конечный глобальный минимум, то для их определения вычисляются также значения f(x) на множестве точек локальных экстремумов. Наименьшее из полученных значений, т.е. Значений f(x) в точках локальных экстремумов и предельных значений f(x), определяет точку глобального минимума, наибольшее из полученных значений − точку глобального максимума f(x). Алгоритм определения точек локальных и глобальных экстремумов функции одной переменной 1. Находится f ′(x) . 2. Вычисляются корни уравнения f ′(x) =0 − стационарные точки x(i) , i ∈ I = { 1,2,...,N }, где N − число стационарных точек. Пусть у нас есть целевая функция f(x): 3. Находится f k (x)., 4. Вычисляются значения f k (x ), то есть, ищем значения полученных функций в стационарных точках. 5. Если f k (x) ≠ 0 то определяется тип стационарной точки x(i), то есть определяем максимум (минимум) или точку перегиба. 7 . Вычисляются предельные (при x →∞ и x→−∞) значения f(x). Пример определения локальных и глобальных экстремумов функции. Пример 1 Пусть есть функция: 1. Находим первую производную f(x): 2. Вычисляем корни уравнения f ′(x) = 0 : Получили одну стационарную точку: Теперь определяем характер стационарной точки. Для этой цели ищем следующие производные нашей целевой функции Пример определения локальных и глобальных экстремумов функции. 3. Находим вторую производную f(x): 4. Вычисляем значение второй производной в стационарной точке x=1. Так как у нас значение второй производной в стационарной точке равно нулю, то ищем следующую производную и определяем значение этой производной в стационарной точке. 5. Значение третьей производной в точке x=1. Так как у нас не нулевая производная нечетная, следовательно точка x=1 является точкой перегиба. Пример определения локальных и глобальных экстремумов функции. Теперь определяем глобальные максимумы (минимумы): Пример определения локальных и глобальных экстремумов функции. Пример 2 Пусть есть функция: 1. Находим первую производную f(x): 2. Вычисляем корни уравнения: 3. Определяем характер стационарной точки. Пример определения локальных и глобальных экстремумов функции. Поскольку характер стационарной точки не определен, то находим четвертую производную f(x): Так как у нас 4 производная (четная) и она положительная в стационарной точке, то наша точка является точкой локального минимума. f(x ) не имеет конечного глобального максимума, и имеется глобальный минимум. Задача безусловной оптимизации для функции двух переменных. Для функции f(x) многих переменных точка x представляет собой вектор, f ′(x) − вектор первых производных (градиент) функции f(x), f ′′(x) − симметричную матрицу вторых частных производных (матрицу Гессе − гессиан) функции f(x). Необходимое условие локальной оптимальности. Пусть f(x) дифференцируема в точке x ∗ ∈ R . Если x ∗ − точка локального экстремума, то Характер стационарной точки x ∗ связан со знакоопределенностью матрицы Гессе f ′′(x ∗ ) . Достаточное условие локальной оптимальности. Пусть f(x) дважды дифференцируема в точке x ∗ ∈R , причем f ′(x∗) = 0 , т.е. x ∗ − стационарная точка. Тогда, если матрица f ′′(x ∗ ) является положительно (отрицательно) определенной, то x ∗ − точка локального минимума (максимума); если матрица f ′′(x ∗ ) является неопределенной, то x ∗ − седловая точка. Если матрица f ′′(x ∗ ) является неотрицательно (неположительно) определенной, то для определения характера стационарной точки x ∗ требуется исследование производных более высокого порядка. Задача безусловной оптимизации для функции двух переменных. Для проверки знакоопределенности матрицы, используется критерий Сильвестра. Согласно этому критерию, симметричная матрица А является положительно определенной в том и только том случае, если все ее угловые миноры положительны. При этом угловым минором матрицы А называется определитель матрицы, построенной из элементов матрицы А, стоящих на пересечении строк и столбцов с одинаковыми (причем первыми) номерами Что такое угловой минор. Алгоритм определения точек локальных экстремумов функции многих переменных. Пусть у нас есть целевая функция F(x1, x2,x3….) 3. Вычисляются стационарные точки 4. Находится f ′′(x), и вычисляем значение производных в стационарных точках. 1. Находится f ′(x) . 2. Решается система 5. Вычисляются угловые миноры матрицы f ′′(x(i )) . Если не все угловые миноры ненулевые, то для определения характера стационарной точки x(i) требуется исследование производных более высокого порядка. Алгоритм определения точек локальных экстремумов функции многих переменных. 6. Анализируются знаки угловых миноров f ′′(x(i)) . Если f ′′(x(i )) является положительно определенной, то x(i) является точкой локального минимума. 7. Вычисляются угловые миноры матрицы [− f ′′(x(i))] и анализируются их знаки. Если [− f ′′(x(i) )] является положительно определенной, то f ′′(x(i )) является отрицательно определенной и x(i) является точкой локального максимума. В противном случае f ′′(x(i )) является неопределенной и x(i) является седловой точкой. Определение точек локальных экстремумов функции многих переменных. Пример. У нас есть следующая функция: 1. Находим первые частные производные f(x): 2 . Решаем систему уравнений: Определение точек локальных экстремумов функции многих переменных. Решением системы уравнения будут следующие точки: Таким образом у нас есть две стационарные точки. 3. Находим вторые частные производные f(x): Определение точек локальных экстремумов функции многих переменных. Составляем матрицу Гессе. И на основании этой матрицы определяем характер стационарных точек. Рассмотрим первую точку (-1,0); Угловые миноры для данной матрицы будут: Определение точек локальных экстремумов функции многих переменных. Поскольку все угловые миноры ненулевые, то характер x(1) определяется с помощью f ′′(x). Поскольку матрица f ′′(x(1) ) не является положительно определенной, то рассматриваем матрицу [− f ′′(x(1) )]: Угловые миноры [− f ′′(x(1) )]: Определение точек локальных экстремумов функции многих переменных. Поскольку матрица [− f ′′(x(1) )] не является положительно определенной, то матрица f ′′(x(1) ) не является отрицательно определенной. Следовательно, матрица f ′′(x(1) ) является неопределенной и x(1) является седловой точкой. Теперь рассмотрим вторую стационарную точку: Теперь рассчитываем матрицу Гессе: Угловые миноры f ′′(x(2) ) : Определение точек локальных экстремумов функции многих переменных. Поскольку все угловые миноры ненулевые, то характер x(2) определяется с помощью f ′′(x). Поскольку матрица f ′′(x(2) ) является положительно определенной, то x (2) является точкой локального минимума. ЗАДАЧА УСЛОВНОЙ ОПТИМИЗАЦИИ. Данная задача записывается в виде: Для решения данной задачи используется метод множителей Лагранжа. Основная идея метода заключается в переходе от задачи на условный экстремум исходной функции f (x) к задаче на безусловный экстремум некоторой специально построенной функции Лагранжа L(x,λ) Необходимое условие локальной оптимальности. Пусть f(x), g1(x), g2 (x),..., gm (x ) дифференцируемы в точке x ∗ ∈R. Если x ∗ − точка локального экстремума, то существует вектор λ= λ * 1 , λ * 2 , λ * 3 λ * n , компоненты которого не равны нулю одновременно. ЗАДАЧА УСЛОВНОЙ ОПТИМИЗАЦИИ. Для определения характера стационарных точек используется достаточное условие оптимальности с привлечением матрицы L ′x′x (x, λ) вторых частных производных функции Лагранжа по x j , j =1,n . Достаточное условие локальной оптимальности ЗАДАЧА УСЛОВНОЙ ОПТИМИЗАЦИИ. Алгоритм определения точек условных локальных экстремумов 1 . Составляется функция Лагранжа L(x,λ). 2. Находим производную: 3. Решаем систему: В результате вычисляются стационарные точки. Далее необходимо определить тип стационарных точек. Алгоритм определения точек условных локальных экстремумов 4. Ищем с целью определения коэффициентов α 5. Находится И составляется квадратичная форма. 6. Находится значения коэффициентов α и производится исследование знаков квадратичной формы. 7. Алгоритм определения точек условных локальных экстремумов. Пример Определить точки локальных экстремумов функции. При условии: Решение. 1. Составляем функцию Лагранжа. 2. Находим частные производные: Алгоритм определения точек условных локальных экстремумов. 3. Решаем систему уравнений Получаем три решения: 3.1. тогда Так как то из второго уравнения следует Таким образом получаем первую стационарную точку: 3.2. Второе решение Алгоритм определения точек условных локальных экстремумов. Так как то для удовлетворения второго уравнения должно выполнятся условие: Таким образом получаем вторую стационарную точку: 3.3 . Третье решение Алгоритм определения точек условных локальных экстремумов. Пусть x1 ≠ 0 и x2 ≠ 0, тогда из первого уравнения следует: Для удовлетворения второго уравнения должно выполнятся условие: Опуская промежуточные выражения, получим третью стационарную точку ( нужно получить этот результат самостоятельно ): Алгоритм определения точек условных локальных экстремумов. 4. Теперь нужно найти коэффициенты α на основе уравнений Вспомним наше ограничение: Теперь построим квадратичную форму на основе производных функции Лагранжа Алгоритм определения точек условных локальных экстремумов. Для того что бы проанализировать тип стационарных точек, нужно подставить значения точек в квадратичную форму. Первая стационарная точка Рассчитываем матрицу Нам нужно искать решение в виде квадратичной форме: Алгоритм определения точек условных локальных экстремумов. Вспомним, что у нас есть уравнение : Таким образом, получим: Решением являются точки: На основании последнего результата можно определить знак квадратичной формы Q. Первая стационарная точка это точкой условного локального минимума. Вторая стационарная точка: Алгоритм определения точек условных локальных экстремумов. Матрицы вторых производных функции Лагранжа: Квадратичная форма: Алгоритм определения точек условных локальных экстремумов. Решаем уравнение для второй стационарной точки: В итоге получим следующее решение: Так как у нас получилось, что квадр. Форма >0 То вторая точка является точкой условного локального минимума. Третья стационарная точка: Алгоритм определения точек условных локальных экстремумов. Матрица вторых производных функции Лагранжа. Алгоритм определения точек условных локальных экстремумов. Квадратичная форма для третьей точки будет. С учетом уравнения Получим, что третья стационарная точка является точкой условного локального максимума. Задача квадратичного программирования. Задачей квадратичного программирования (КП) называется задача оптимизации с квадратичной целевой функцией и линейными ограничениями. Математическая формулировка выглядит следующим образом: Для решения задачи КП используются необходимые условия Куна − Таккера. Рассмотрим принцип решения такой задачи. Задача квадратичного программирования. 1. Составляем уравнение Лагранжа: при условии: Условия Куна – Таккера: Задача квадратичного программирования. Непосредственное решение данной системы очень громоздко. Поэтому используется следующий прием: Неравенства преобразуют в равенства, вводя соответственно две группы дополнительных переменных, затем выделяется базис уравнений, которые собственно используются для решения. Исходная задача эквивалентна задаче нахождения допустимого, т.е. удовлетворяющего требованиям неотрицательности и базисного решения системы линейных уравнений и удовлетворяющего также условиям дополняющей нежесткости Пример решения задачи кв. программирования в Excel. Задача. Предприятие имеет запасы 4-х видов ресурсов (мука, жиры, сахар, финансы), 2 вида продуктов (хлеб и батон). Найти оптимальный план производства, при котором прибыль от реализации произведенной продукции должна быть максимальный. При чем прибыль равна выручка – затраты. Экономико-математическая модель Прибыль =0,99*Хлеб+1,21*Батон –Хлеб^0,7-Батон^0,7 - mах 0,6*Хлеб+0,5*Батон<=120 0,05*Хлеб+0,08*Батон<=70 0,2*Хлеб+0,6*Батон<=65 0,2*Хлеб+0,24*Батон<=50 Хлеб,Батон>=0 Ограничение Пример решения задачи кв. программирования в Excel. Пример решения задачи кв. программирования в Excel. THANK YOU! • Text • Text • Text |