Курс лекци Русакова по методам оптимизации (1083216), страница 8

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

Текст из файла (страница 8)

и станет равной651340+5,75=1345,75 руб. При этом числа, стоящие в столбце векторацы14,показывают,чтоуказанноеувеличениеобщейтабли-стоимостиизготовляемой продукции может быть достигнуто за счет увеличениявыпуска изделий В на 5/8 ед. и сокращения выпуска изделий Сна 1/4 ед.Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точнотак же увеличение на 1 кг сырья III вида позволит найти новый оптимальныйплан производства изделий, при котором общая стоимость изготовляемойпродукции возрастет на 1,25 руб.

и составит 1340+1,25=1341,25 руб. Этобудет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. иуменьшения изготовления изделий В на 1/8 ед., причем объем используемогосырья II вида возрастет на 5/8 кг.Продолжимрассмотрениеоптимальныхдвойственныхоценок.Вычисляя минимальное значение целевой функции двойственной задачивидим, что оно совпадает с максимальным значением целевой функцииисходной задачи.При подстановке оптимальных двойственных оценок в системуограничений двойственной задачи получаемПервое ограничение двойственной задачи выполняется как строгоенеравенство. Это означает, что двойственная оценка сырья, используемого напроизводство одного изделия вида А, выше цены этого изделия и,следовательно, выпускать изделия вида А невыгодно. Его производство и непредусмотрено оптимальным планом прямой задачи.

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

Поэтому, чтобы проводитьэкономический анализ с использованием двойственных оценок, нужно знатьих интервал устойчивости.Глава 2 Безусловная оптимизация (многомерныефункции)2.01 Безусловная оптимизация. Основные понятияТребуется найти min f(x), на всём X = Rn, то есть минимизация на всемпространстве.ОпределениеМинимизация функции на множестве, заданном неравенствами,равенствами и другими ограничениями называется условной.Пусть:67X = Rn (евклидово n-мерное пространство);Функция f дифференцируема хотя бы один раз, тогда в точке минимумавыполняется равенство:∇f(x)=0, где (вектор частных производных по каждому аргументу)∇f ( x ) = (∂ f ∂ f...)∂ x1 ∂ x nВ большинстве случаев это приводит к решению системы нелинейныхуравнений, что само по себе проблема.

Существуют релаксационныеметоды, в основе которых лежит построение последовательности {xi}, xi∈Xсо следующими свойствами:f(x0)>f(x1)>...;xi→x* = argmin{ f(x), x∈X}.Рассмотрим методы нахождения локального минимума (т.е. корняуравнения ∇f(x) =0). Все рассматриваемые методы делятся на несколькогрупп в зависимости от того, какой максимальный порядок производнойфункции f используется для вычисления последовательности. Порядокметода равен порядку старшей производной f, вычисляемый пр реализацииэтого метода.

Если производные не используются, то методы нулевогопорядка, затем - первого и так далее.Общая схема безусловной оптимизацииОсновная итерационная формула:xk+1 = xk+ tkSk ,где Sk — вектор, определяющий направление изменения xktk — скаляр, определяющий длину шага.Sk может зависеть от xk: Sk = ϕ(xk), а может от (xk ,xk-1), от (xk ,xk-1, xk-2)и т.д..68В зависимости от этого критерия методы делятся на:1. одношаговые (ϕ(xk));2. многошаговые (ϕ(xk, xk+1)).Одношаговыеидвухшаговыеметодыимеютосновноераспространение.2.02 Методыпервогопорядкаметоды).Градиентныйметод(градиентныеспостояннымшагомДля вычисления t и S используются значение функции и перваяпроизводная.Известно,чтоградиентфункциивточкедаетнаправлениенаибольшего возрастания функции в точке. Направление наибольшегоубывания - это направление антиградиента.Пусть Sk = -∇f(xk), tk > 0 - длина шага.Пусть tk = t (т.е.

не зависит от к)xk+1 = xk - t∇f(xk)Видно, что останавливаемся в любой точке, где ∇f(xk)=0.Пример:f(x) = ax2, a>0, x-скалярxk+1=xk - 2taxk = (1- 2at)xkОтсюда1-2at<1⇒ at<1- необходимое и достаточное условие существованияпределаЕсли 0<tk<1/a - сходится,69tk>1/a - расходится,tk=1/a - зацикливается.( tk=1/a⇒ x1=x0-2x0= -x0 x2=x1-2x1= -x1=x0 ит.д.)Выбор постоянного шага приводит к осложнениям, так как a заранеечасто не известно, а при малом значении a – много шагов; при большом –есть риск потери сходимости.Оценим сходимость этого метода в общем случае.Теорема (о сходимости метода градиентов)Пусть f(x)- дифференцируема на Rn, ∇f(x) удовлетворяет условиюЛипшица:∃L>0, ∀x, y верно || ∇f(x)-∇f(y) ||≤ L ||x-y || (*)(||x2|| = Σxi2 ), f(x) - ограничена снизу: ∃ f* такая, что f(x)≥ f* >-∞ (**)и 0< t< 2/L (***)Тогда при xk+1= xk - t∇f(xk), справедливо:- ∇f(xk) → 0, при k→∞ (градиент стремится к нулю),- функция f(x) монотонно убывает (f(xk+1)≤f(xk)),- f(xk+1) ≤ f(xk)-t(1-tL/2)||∇f(xk) ||2 .Замечание:Сходимость градиента к нулю не гарантирует сходимости к минимуму.Пример:f(x) =1, градиент сходится к нулю, но функция не имеет1 + x2локальных минимумов.Равенство градиента нулю - необходимое условие минимума; еслик нему добавить положительность второй производной, то будетдостаточное условие локального минимума.70Таким образом доказана сходимость метод при определенныхусловиях.

Оценить скорость сходимости в общем случае можно для болееузкого класса функцииОбщая схема методов: xk+1 = xk - γ*∇f ( x k )2.03 Градиентный метод с дроблением шага.Как известно выбор постоянного шага может привести к осложнениям.Схема градиентного метода имеет вид xk+1 = xk - tk*∇f ( x k ). Если шагвыбрать с условием, что f(xk+1) - f(xk) ≤ -ε* tk * || ∇f(xk)|| (*), где 0 ≤ ε < 1, торезультат будет значительно лучше.Иллюстрация:Необходимо двигаться к х*. В начальной точке проводим касательнуюк линии уровня и делаем по перпендикуляру к касательной в этой точке, шагсоответствующей величины. Если оказываемся «далеко», то делим шагпополам, проводим линию уровня, касательную и шагаем по перпендикуляруи т.д.Алгоритм:1.Выбираем t=const.2.Проверяем выполнение соотношения (*).3.Если выполняется, то вычисляем следующую точку; если невыполняется, тогда длину шага t делим на 2, проверяем (*) и так далее.Там, где ∇f ( x ) = 0- останавливаемся.Теорема (о градиентном метоле с дроблением шага)71Градиентный метод с дроблением шага обеспечивает следующеенеравенство: || xk –x*|| ≤ const.*qk, где 0<q<1.Без доказательства.2.04 Метод наискорейшего спуска.Определяет оптимальное значение шага на каждом такте.t k = argmin t >0 f(x k − t∇f(x k ))Значение функции, полученное этим методом, меньше чем впредыдущем методе.Характерная черта метода: градиенты функции в соседних точкахортогональны.df(x k − t∇f(x k )) t = t k = 0 = (∇f(x k − t k ∇f(x k )),−∇f(x k )) = (∇f(x k +1 ), ∇f(x k )) = 0dtДоказать самостоятельно.Графическая интерпретация:В начальной точке проводим касательную к линии уровня и делаем шагоптимальной величины в направлении перпендикуляра к касательной вданной точке.

Получив новую точку, повторяем действия и так далее.Теорема (о скорости сходимости метода наискорейшего спуска)Скорость сходимости метода наискорейшего спуска - геометрическая.xk − x* ≤ const * q k , гдеБез доказательства72q=L−l(L - указана ранее)L+l2.05 Масштабированиеnимеет вид: f(x) = ∑ a i x i2 , где ai>0Пусть f(x)сильно различаютсяi =1между собой. Поверхности уровней функции вытянуты вдоль тех осей xi,которым соответствуют малые ai.Дляболееэффективногопримененияградиентныхметодовнеобходимо превращение поверхностей уровня в кругиx0Заменой переменных xi = µi y i можно добиться того, чтобы в новыхпеременных yi поверхности уровней стали сферами.

Для этого достаточно−принять µi = ai12 (тогдавсе коэффициенты квадратичной формы единицы).В случае, когда f(x) не квадратичная, а достаточно гладкая функцияобщего вида выбирают :µi = (∂ 2f r -1/2( x))∂ xi ∂ xiЭто диагональные элементы матрицы вторых производных. Этопреобразование не превратит поверхности уровня в сферы, но в некоторыхслучаях позволит уменьшить их вытянутость. Гарантировано исправить видфункции f(x) можно, если учесть все, а не только диагональные элементыматрицы вторых производных и преобразования координат вида:1rv − ry = ( f ′′( x )) 2 * x732.06 Метод Ньютона.Разложим f(x) в ряд Тейлора до 2-го слагаемого включительно:12f ( x ) = f ( xk ) + (∇f ( x k ), x − xk ) + (∇ 2 f ( xk ) ⋅ ( x − xk ), x − x k ) + o( x − x k )2(*)∇f ( x k ) = (∂ f ∂ f...) – вектор∂ x1 ∂ xn∇ 2 f ( x k ) - матрица Гессе, матрица вторых производных.Будем рассматривать квадратичную аппроксимацию f(x), тогда2получим (*) без o( x − xk ) то есть предполагаем, что f(x) квадратичнаяформа.

Эта форма имеет единственную точку min, который является корнемуравнения f ’(x)=0.В данном случае:f ′( x ) = 0 = ∇f ( xk ) + ∇2 f ( xk )( x − xk ) ⇒xk +1 = xk − [∇2 f ( xk )]−1 ∇f ( xk )Метод НьютонаПример:Сделаем одну итерацию метода Ньютона для квадратичной функции1f ( x ) = ( Ax, x ) − (b, x )2∇f ( x ) = Ax − b∇f ( x ) = 0 ⇒ x = A−1bЭтот пример показывает связь решения системы уравнений Ax-b = 0 ипоиска минимума соответствующей функции f(x).∇2 f ( xk ) = A - матрица вторых производных.Одна итерация метода Ньютона:x1 = x 0 − A−1 ( Ax 0 − b) = A−1b74Но это точка минимума квадратичной функции. Таким образом дляквадратичной функции метод Ньютона сходится за один шаг (матрица Адолжнабытьположительноопределенаисимметрична,значениясобственных чисел (растянутость) не играют роли).Точка х1 гораздо ближе к х* , чем в градиентных методах, но надовычислить матрицу Гессе и обратить ее.

Градиентный метод медленнее, нобез дополнительных вычислений.Оценим скорость сходимости метода Ньютона:Теорема (о скорости сходимости метода Ньютона):Пусть f(x) дважды дифференцируема, матрица ∇2 f ( x ) удовлетворяетусловиюЛипшица с константой L : ∇ 2 f ( x ) − ∇ 2 f ( y ) ≤ L ⋅ x − yf(x) сильно выпукла: 0< l I ≤∇2 f(x) и начальное приближениеудовлетворяет условию:L ⋅ l −2q=() ∇f ( x0 ) ≤ 12(есть требования к начальным условиям)Тогда метод Ньютона сходится к х* с квадратичной скоростью2l kxk − x* ≤ q2LДоказательство:Известно, что:11) g ( x + y ) = g ( x ) + ( g ′( x ), y ) + ∫ ( g ′( x + ty ) − g ′( x ), y )dt0Если на g’(x) удовлетворяет условию Липшица g ′(u ) − g ′( v ) ≤ L u − v ,то75Ly2g ( x + y ) − g ( x ) − g ′( x ), y ≤∇f ( x + y ) − ∇f ( x ) − ∇ 2 f ( x ), y ≤2Ly2Применим это отношение к ∇22f(x), тогдаПусть x = xk иy = −[∇ 2 f ( xk )]−1 ∇f ( xk ),т.к.( x k + y = xk +1метод Ньютона )∇f ( x k +1 ) − ∇f ( xk ) + ∇ 2 f ( x k )[∇ 2 f ( x k )]−1 ∇f ( xk ) ≤≤L[∇ 2 f ( x k )]−1 ∇f ( xk )22≤2L[∇ 2 f ( x k )]−1 ⋅ ∇f ( xk )22Дано ∇ 2 f ( x k ) ≥ lI (см.

Характеристики

Список файлов лекций