/>Кафедра: ИТ
МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ
МНОГИХ ПЕРЕМЕННЫХ
Екатеринбург 2007/>
Оглавление
Введение
Лабораторная работа № 1.
1. Методы безусловной оптимизации
1.1 Теоретический обзор. Исследование функции набезусловный экстремум
1.2 Численные методы минимизациифункции
2. Порядок выполнения лабораторной работы
3. Пример выполнения лабораторнойработы
4. Задания для лабораторного практикума
Лабораторная работа № 2.
1. Методы условной оптимизации
1.1 Теоретический обзор. Решение задачи минимизации сосмешанными ограничениями
1.2 Седловые точки функции Лагранжа
1.3 Решение задач квадратичного программирования методом седловой точки
2. Порядок выполнения лабораторной работы
3. Пример выполнения лабораторнойработы
4. Задания для лабораторного практикума
Библиографический список
Приложение
Введение
Настоящая работа является первой в серии методическихуказаний к лабораторным работам по дисциплинам «Методы оптимизации инелинейное программирование» и «Методы оптимизации». Данныедисциплины читаются студентам 2-го курса специальности 230101 — Вычислительныемашины, комплексы, системы и сети и направления 230100 — Информатика ивычислительная техника (бакалавры).
В указаниях рассматриваются задачи безусловной и условнойнелинейной оптимизации. В теоретической части по каждой теме приводятся базовыепонятия, теоремы и алгоритмы, которые потребуются для выполнения работ. Длявыполнения графической и расчетной частей задач и реализации численных методовоптимизации студенты должны применить знание языков программирования и пакетовMATLAB, MATCAD, EXCEL. Выбор конкретного инструмента предоставляется самомустуденту. Приведены примеры порядка выполнения и оформления лабораторных работ.
Проведенные вычисления, графические работы, анализполученных результатов должны быть оформлены в виде отчета в соответствии состандартными требованиями, предъявляемыми к отчетам и пояснительным запискам [1].Сведения из теории, содержащиеся в данных методических указаниях, в отчетвключать не рекомендуется.
/>Лабораторная работа №1. 1. Методы безусловной оптимизации
Цель лабораторной работы — закрепление навыков исследованияфункций на выпуклость, решение задач на нахождение безусловного экстремумавыпуклой функции аналитически и численными методами, изучение способоввизуализации функций двух переменных в EXCEL и MATLAB./>1.1 Теоретический обзор. Исследование функции набезусловный экстремум
Рассматривается задача
f (x)→ extr, x/>Rn.(1)
Метод поиска безусловного экстремума основывается наследующих утверждениях:
Пусть функция f (x) дифференцируема в точке х*/>Rn.Тогда если х* — локальное решение задачи (1), то
gradf (x*) =0. (2)
Пусть функция f (x) дважды дифференцируема в точке х*/>Rn.Тогда
а) если х* — точка локального минимума взадаче (1), то матрица Гессе Н (х*) неотрицательноопределена, т.е. />р/>Rn выполняется неравенство (Н (х*) р, р) ≥0;
б) если х* — точка локального минимума взадаче (1), то матрица Н (х*) неположительно определена, т.е. />р/>Rn выполняется неравенство (Н (х*) р, р) ≤0.
Пусть функция f (x) дважды дифференцируема в точке х*/>Rnи
gradf (x*) =0. Тогда
а) если матрица Н (х*) положительноопределена, т.е. />р/>Rn,р≠0,(Н (х*) р, р) >0, то х* — точка строгого локального минимума функции f (x) на Rn;
б) если матрица Н (х*) отрицательноопределена, т.е. />р/>R,р≠0,(Н (х*) р, р) х* — точка строгого локального максимума функции f (x) на Rn.
Если gradf (x*) =0, то х*называется стационарной точкой. Для выпуклой (вогнутой) на Rnфункции стационарные точки являются точками ее глобального минимума (максимума).Строго выпуклые (вогнутые) функции имеют единственный глобальный минимум (максимум).
Критерий выпуклости функции. Дважды непрерывнодифференцируемая на выпуклом множестве Х с непустой внутренностью функцияявляется выпуклой (вогнутой) на этом множестве в том и только том случае, когдаматрица Гессе Н (х*) неотрицательно (не положительно) определенадля всех х />Х.
При исследовании на знакоопределенность матрицы вторыхпроизводных функции рекомендуется применять критерий Сильвестра или анализсобственных значений матрицы.
Схема поиска безусловных экстремумов функции:
Составить и решить систему алгебраических уравнений (2).
В стационарных точках (точках, являющихся решением системы (2))исследовать на знакоопределенность матрицу вторых производных; точки, в которыхН (х) >0, являются точками глобального минимума; стационарные точки,в которых Н (х) 0, являются точками глобального максимума.
Исходя из вида исследуемой функции, проанализироватьстационарные точки, в которых матрица вторых производных не является строгознакоопределенной.
Найденные точки локального экстремума исследуются наглобальный экстремум (если это возможно). В частности, если матрица Гессенеотрицательно (не положительно) определена на всем пространстве Еn, то все стационарные точки функции являютсяточками глобального минимума (максимума)./>1.2 Численные методы минимизации функции
Численное решение задачи минимизации (1), как правило,связано с построением минимизирующей последовательности точек x0,x1,x2,…,xn,…,обладающих свойством
f (xk)f (xk-1),k=0,1,… (3)
Общее правило построения минимизирующей последовательностиимеет вид
x k+1=x k+t kd k, k=0,1,…,
где х0 — начальная точка поиска; dk — приемлемоенаправление перехода из точки xkв точку xk+1,которое обеспечивает выполнение условий (3) и называется направлением спуска; tk — величина шага. Начальнаяточка поиска задается исходя из физического содержания решаемой задачи иаприорных данных о существовании и положении точек экстремума.
При решении вопроса о выборе численного метода рекомендуетсяоценить поведение линий уровня целевой функции в окрестностях предполагаемой точкиэкстремума. Число m = L/l, где L и l — максимальное и минимальноесобственные значения гессиана функции f в предполагаемой точкеэкстремума x0(характеризующееразброс собственных значений оператора f (x)), называется числом обусловленности гессиана функции f вточке x0. Если m >> 1,то функция f называется плохо обусловленнойили овражной. Овражность, то естьвытянутость линий уровня вдоль одного направления, приводит к тому, чтоградиентные методы поиска экстремума функции сходятся медленно.
В зависимости от наивысшего порядка частных производныхфункции f (x),используемых для формирования dk и tk, численные методы принято делить на тригруппы:
Методы нулевого порядка, использующие информацию только означениях функции f (x)(методы деформируемого многогранника, конфигураций). Эти методы могутприменяться в тех случаях, когда функция задана неявно или не заданааналитически, но известен ряд значений функции или эти значения вычисляютсянепосредственно в ходе реализации алгоритма. Они также могут быть полезны вслучаях, когда производные функции могут быть заданы аналитически, но ихвыражения очень громоздки.
Методы первого порядка, использующие информацию о значенияхсамой функции f (x) иее первых производных (методы наискорейшего градиентного спуска, дробленияшага, Гаусса-Зейделя, Флетчера-Ривса).
Методы второго порядка, использующие, кроме того, и информациюо вторых производных функции f (x) (метод Ньютона и его модификации).
Метод конфигураций (Хука — Дживса)
Следует выделить два этапа метода конфигураций:
1) исследование с циклическим изменением переменных и 2) ускорениепоиска по образцам.
Исследующий поиск начинается в точке х0,называемой старым базисом. Направления поиска — координатные направления. Покаждому направлению поочередно с шагом +t0(-t0) проверяется выполнение условия(2) и в качестве нового базиса берется точка с координатами, полученными врезультате удачных шагов из начальной точки по каждому направлению.
Направление от старого базиса к новому задает направлениеускорения поиска: в качестве следующей точки минимизирующей последовательностипроверяется точка y1=x0+l(x1-x0).Здесь l — ускоряющий множитель,задаваемый пользователем. Если полученная точка является удачной, то онаберется в качестве следующей точки для исследования. В противном случае исследованиеведется из точки x1.
Метод деформируемого многогранника(Нелдера — Мида).
При решении задачи поиска минимума функции f (x) методомНелдера-Мида строится последовательность множеств из n+1 точек, которыеявляются вершинами выпуклого многогранника. На каждом последующем k+1-м шаге из системы точек xi(k), i=1, …,n+1, полученной на k-мшаге, выводится точка xh (k), в которой функция f (x) имеет наибольшеезначение (худшая точка). Вместо xh (k) в систему вводится новая точка, выбираемая на отрезкепрямой, проходящей через худшую точку и центр тяжести оставшихся n вершин многогранника:
xn+2=/> -центр тяжести;
xn+3= xn+2+a (xn+2 — xh)
новая точка (“растянутое” отражение наихудшей вершины).
Метод дробления шага.
В данном методе строится релаксационная последовательностьточек, т.е. таких точек {xk}, k=0,1,…, что f (xk) f (xk-1), k=0,1,….Точки последовательности {xk}вычисляются по следующему правилу:
xk+1=xk-tkgradf (xk),k=0,1,… (4)
Начальная точка х0 и начальный шаг t0 задаются пользователем. Величина шага t0 не изменяется до тех пор, пока функцияубывает в точках последовательности. Это контролируется путем проверкивыполнения условия f (xk+1)- f (xk)tk=tk/2.
Метод наискорейшего градиентного спуска
Как и в предыдущем методе, точки релаксационной последовательности{xk}, k=0,1,…вычисляются по правилу (4). Точка х0 задается пользователем; величинашага tk определяется из условияминимума одномерной функции φ(tk)=f (xk-tkgradf (xk)).Задача минимизации функции φ(tk)может быть решена с использованием необходимого условия минимума />=0 с последующей проверкойдостаточного условия минимума />>0или с использованием численных методов.
Метод сопряженных направлений (Флетчера- Ривса).
В данном методе используются свойства векторов, сопряженныхотносительно некоторой матрицы.
Определение. Векторы p и q называются сопряженнымиотносительно матрицы Q, если выполняетсяравенство pQq=0.
Точки релаксационной последовательности {xk}, k=0,1,… вычисляютсяпо правилу
xk+1=xk-tkdk,k=0,1,…;
dk =- gradf(xk) +βk-1dk — 1; (5)
d0= — gradf (x0);
βk-1=║gradf (xk) ║2∕║gradf (xk-1) ║2.
Точка х0 задается пользователем; величинашага tk определяется из условияминимума функции φ(t) =f (xk-tdk). Задача минимизации одномерной функцииφ(tk) может быть решенас использованием необходимого условия минимума />=0с последующей проверкой достаточного условия минимума />>0 или с использованиемчисленных методов. Коэффициент βk-1вычисляется из условиясопряженности направлений dk и dk-1.
Метод Ньютона.
Строится последовательность точек {xk},k=0,1,…, таких, что />,k=0,1,… Точки последовательности {xk} вычисляются по правилу xk+1=xk+dk, k=0,1,…Точка х0 задается пользователем с учетом знакопостоянства иневырожденности матрицы Гессе в задаваемой начальной точке и близости выбраннойточки к предполагаемой точке минимума. Направление спуска определяется длякаждого значения k по формуле dk =-H-1 (xk)gradf (xk), где Н — матрица Гессе.
2. Порядок выполнения лабораторной работы
Записать необходимые условия экстремума. Аналитически илииспользуя прикладные пакеты найти стационарные точки.
Проверить выполнение достаточных условий экстремума внайденных стационарных точках. Найти глобальный минимум функции. Оценитьобусловленность задачи в точке минимума и овражность графика в окрестноститочки минимума. Сделать предварительный вывод о работоспособности избранногочисленного метода.
Выбрать пакет, в котором будет строиться график. Рекомендацииприведены в приложении. Построить график функции, задавая пределы изменениякоординат с учетом аналитически найденных точек минимума — максимума.
Выбрать несколько начальных точек для реализации численногометода. Задать критерий завершения итерационного процесса. Найти минимум. Сравнитьрезультаты с аналитически найденным значением глобального минимума. Исследоватьсходимость алгоритма, фиксируя точность определения минимума, количествоитераций метода и количество вычислений минимизируемой функции в зависимости отзадаваемой точности поиска. Результатом выполнения данного пункта должны бытьвыводы об объёме вычислений в зависимости от задаваемой точности и начальногоприближения.
/>3. Пример выполнения лабораторнойработы[1]
Функция: /> min, x0= (-2,-2).
Методы: градиентного спуска и Ньютона.
Решение: 1. Построим график функции и линии уровня (рис.1).
Примечание: при построении графика используется средаMathCAD.
/> />
Рис.1. Графики функции /> илиний уровня
2. Решим задачу минимизации аналитически.
/>
Система для нахождения стационарных точек из условияравенства нулю градиента имеет вид
/>
Если x1x2 =0, тоиз системы следует, что x1 =0 иx2=0.
Первая стационарная точка — A0(0; 0).
Если
x1x2 ≠0, то
/>
Подставим х1 в первое уравнение:
/>
Введем замену
/>:
/>
Обозначим
/>, />.
Получаем остальные стационарные точки:
/>;
/>;
/>;
/>.
Приближенные числовые координаты найденных точек:
А0 (0; 0), А1 (1.068; 1.668),А2 (-1.068; — 1.668), А3 (-0.331; 0.848), А4(0.331;0.848).
Построим и исследуем на знакоопределенность матрицу Гессе вточках А0,…, А4.
/>
/>/>
/>
/>/>;
/>/>/>/>/>.
/>
H (A0(0; 0)) =0
(требуется дополнительное исследование точки).
Анализ поведения функции в окрестности точки A0(0; 0) показывает, что, придавая х1положительное и отрицательное значение при любом х2, можнополучить соответственно положительное и отрицательное значение функции. Такимобразом, A0(0; 0) не являетсяни точкой локального минимума, ни точкой локального максимума.
Н (А1 (1,068; 1,668)) ≈ />, матрица отрицательноопределена, в точке А1 локальный максимум.
Н (А2 (-1,068; — 1,668)) ≈/>, матрица положительноопределена, в точке А2 локальный минимум.
Н (А3 (-0,331; 0,848)) ≈ />, матрица положительноопределена, в точке А3 локальный минимум.
Н (А4 (0,331; — 0,848)) ≈ />, матрица отрицательноопределена, в точке А4 локальный максимум.
Точками глобального экстремума являются А1(1,068; 1,668) — глобальный максимум, f (A1) ≈1,801; А2 (-1,068;- 1,668) — глобальный минимум, f (A2) ≈≈ — 1,801.
3. Остальные задания реализованы на языке СИ, для чегонаписаны классы для работы с векторами и матрицами (Cvectorи Cmatrix) и использующее их приложение. В методенаискорейшего спуска для одномерной минимизации используется метод золотогосечения. Для отыскания собственных чисел матрицы Гессе применяется метод Якоби,для построения обратной матрицы — метод Жордана-Гаусса.
В начале работы программа выводит информацию о стационарныхточках:
Stationary dots:
x1x2f (x1,x2) Extreme
1.0678901.6675661.801131LOC MAX
1.067890-1.667566-1.801131LOC MIN
0.3310770.848071-0.144426LOC MIN
0.331077-0.8480710.144426LOC MAX
GLOBAL MIN: x (-1.067890, — 1.667566)
f (x) = — 1.801131
GLOBAL MAX: x (1.067890, 1.667566)
f (x) = 1.801131
Затем устанавливается начальная точка x0(-2,-2), функция исследуется на выпуклость/вогнутость в этой точке, выводитсячисло обусловленности матрицы Гессе:
x0 (-2.000000, — 2.000000) Hessian: Alternatingsign
f (x0) = — 0.398297
cond H (x0) = 4.751665
Таким образом, квадратичная форма, соответствующая матрице />, является знакопеременной.Функция не является овражной в окрестности точки, и допустимо применение методаградиентного спуска.
Далее запускается метод наискорейшего градиентного спуска, ивыполняются две итерации.
Steepest descent method:
x2 (-1.200031, — 1.706888) Hessian: Convex
grad_f (x2) = (-0.963083, 0.275166)
f (x2) = — 1.741440
В результате двух итераций мы получили точку, достаточноблизкую к точке глобального минимума.
Теперь из точки (-2; — 2) стартует метод Ньютона с поправкойгессиана. Результат двух итераций:
Newton method:
x2 (-2.735431, — 2.306328) Hessian: Alternatingsign
grad_f (x2) = (-0.110421, 0.031948)
f (x2) = — 0.018516
Видно, что метод расходится. Начальная точка выбрананеудачно. Увеличение числа итераций приводит к дальнейшему расхождению метода. Этообъясняется тем, что в начальной точке функция не является выпуклой. Анализируялинии уровня функции, выберем начальную точку ближе к оптимальной. Например, (-1; — 2):
x0 (-1.000000, — 2.000000) Hessian: Convex,
f (x0) = — 1.471518, cond H (x0) = 3.786885
Newton method:
x2 (-1.047041, — 1.722604) Hessian: Convex
grad_f (x2) = (0.379214, — 0.339841)
f (x2) = — 1.787758
Как в начальной, так и в конечной точке функция являетсявыпуклой. За две итерации мы приблизились к точке А2 (-1,068;- 1,668).
Теперь возьмем начальную точку еще ближе к А2,например (-1; — 1,5):
x0 (-1.000000, — 1.500000) Hessian: Convex
f (x0) = — 1.752302
cond H (x0) = 3.857905
Newton method:
x2 (-1.067889, — 1.667566) Hessian: Convex
grad_f (x2) = (0.000000, 0.000000)
f (x2) = — 1.801131
Метод Ньютона достиг точки глобального минимума, об этомговорит практически нулевой вектор-градиент.
Точное значение /> отличаетсяот полученного методом Ньютона /> на 4,729∙10-7(по модулю).
Выводы.
В лабораторной работе проведено исследование заданнойфункции на глобальный экстремум с использованием аналитических преобразований,графика функции и разработанного приложения на языке C++.
С помощью метода градиентного спуска удалось улучшитьцелевую функцию. Выбор точки x0 (-2,-2)в качестве начальной для реализации метода Ньютона оказался неудачным, так какматрица Гессе в ней не является положительно определенной. Замена начальнойточки на более подходящую для данного метода позволила за две итерации прийти вточку глобального минимума. Полученные результаты хорошо согласуются с теорией.
Разработанные классы Cvector и Cmatrix могут применяться вбудущих проектах.
4. Задания для лабораторного практикума
Аналитически найти стационарные точки заданной функции,области выпуклости/вогнутости функции. Найти точку глобального минимума. Оценитьовражность исследуемой функции в окрестности точки минимума.
Построить график функции, используя средства EXCEL илиMATLAB.
Решить задачу минимизации численным методом из несколькихначальных точек. Сделать вывод об эффективности выбранного метода.
При выполнении задания на языке СИ написать классы дляработы с векторами и матрицами.
Задание выбирать в соответствии с порядковым номером фамилиистудента в списке группы.
/>, метод Хука-Дживса.
/>, методнаискорейшего спуска.
/>, метод Хука-Дживса.
/>, методсопряженных градиентов.
/>, методНелдера-Мида.
/>, метод Ньютона.
/>, методНелдера-Мида.
/>, методнаискорейшего спуска.
/>, методсопряженных градиентов.
/>, методХука-Дживса.
/>, метод Ньютона.
/>, метод дробленияшага.
/>, методнаискорейшего спуска.
/>, методНелдера-Мида.
/>, метод дробления шага.
/>, метод Ньютона.
/>, метод Нелдера-Мида.
/>, методсопряженных градиентов.
/>, методнаискорейшего спуска.
/>, метод Ньютона.
/>, метод дробленияшага.
/>, методНелдера-Мида.
/>, методсопряженных градиентов.
/>, метод Ньютона.
/>
Контрольные вопросы:
Объяснить алгоритмы следующих методов
Метод конфигураций (Хука-Дживса).
Метод деформируемого многогранника (Нелдера Мида).
Метод наискорейшего спуска.
Метод сопряженных направлений и его модификации.
Метод Ньютона и его модификации.
Метод дробления шага.
/>Лабораторная работа № 2.1. Методы условной оптимизации
Цель лабораторной работы — закрепление навыков аналитического решения задач оптимизации со смешаннымиограничениями с использованием теоремы Куна-Таккера, нахождение седловой точкифункции Лагранжа, использование теории двойственности для оценкичувствительности решения задачи оптимизации./>1.1 Теоретическийобзор. Решение задачи минимизации со смешанными ограничениями
Общая задача нахождения экстремума функции при наличииограничений — равенств и ограничений — неравенств записывается в следующем виде:
f (x) →extr, (6)
xÎX= {xÎEn: gi (x)≤0, i=1,2,…,r; gi (x) =0, i=r+1,…, m, m-rn},
где среди функций f (x) и gi (x) могут быть нелинейные.
Активные ограничения — неравенства в точке х* ─это ограничения, которые выполняются в данной точке в виде равенства.
Пассивные ограничения — неравенства в точке х* ─это ограничения, которые выполняются в данной точке в виде строгого неравенства.
Если градиенты активных ограничений-неравенств иограничений-равенств в точке х* линейно независимы, то говорят, что воптимальной точке выполнено условие регулярности.
Обобщенная функция Лагранжа для задачи со смешаннымиограничениями задается как
L (x,λ0,λ) =λf (x) +/>λigi (x). (7)
При выполнении условия регулярности λ≠0и можно положить этот коэффициент равным 1.
Теорема Куна — Таккера (дифференциальная форма необходимого условияминимума). Пусть точка х* — точка локального минимума в задачематематического программирования (6), функцииf,gr+1,…,gmдважды непрерывно дифференцируемы в точке х, функции g1,…,grдважды непрерывно дифференцируемы в некоторой окрестности точки x. Тогда существует число /> ивектор /> такие, что выполняютсяследующие условия:
условие стационарности обобщенной функции Лагранжа по х:
gradxL (x*, />,/>) =0;
условие нетривиальности:
/>2+/>2>0, т.е. хотябы один из множителей Лагранжа отличен от нуля;
условие неотрицательности:
/>≥0, />≥0, i=1, …, r,
т.е. множители Лагранжа, соответствующие целевой функции иограничениям — неравенствам, неотрицательны;
условия дополняющей нежесткости:
gi (x*) =0, i=1, 2, …, r.
Если при этом выполнено условие регулярности, то длявыпуклых функций f, gr+1,…,gm и линейныхфункций g1,…, grусловия теоремы Куна — Таккера являются одновременно необходимыми идостаточными условиями глобального минимума.
Достаточное условие минимума первого порядка.
Пусть имеется точка (х*,/>),удовлетворяющая условию стационарности обобщенной функции Лагранжа по хпри />≠0, суммарное числоактивных ограничений-неравенств в точке х* и ограничений-равенствсовпадает с числом переменных n. Если />>0 для всех активныхограничений gj (x),то точка х* — точка условного локального минимума в задаче (6).
Достаточное условие минимума второго порядка.
Пусть имеется точка (х*,/>),удовлетворяющая условию стационарности обобщенной функции Лагранжа по хпри />≠0. Если в этой точкеd2L (х*,/>) >0 для всех ненулевых dx таких, что для активных в точке х*ограничений-неравенств dgj (x*) =0, />>0 и dgj (x*) ≤0,/>=0, то точка х*является точкой локального минимума.
Общая схема решения задачи условной минимизации функции:
Составляется обобщенная функция Лагранжа вида (7).
Выписываются необходимые условия минимума, сформулированныев теореме Куна — Таккера. К этим условиям добавляются ограничения, задающиедопустимое множество Х. Полученная система алгебраических уравнений инеравенств используется для поиска условно-стационарных (подозрительных наэкстремум) точек. Целесообразно проанализировать отдельно случаи λ0=0и λ0=1 (или λ0- любое положительноечисло). Однако если выполнено одно из условий регулярности, то вариант λ0=0рассматривать не надо.
В найденных точках проверяется выполнение достаточныхусловий минимума и проводится анализ на глобальный экстремум.
Чувствительность решения ЗНП.
Множители Лагранжа могут быть использованы для оцениваниявлияния малых изменений правых частей ограничений на оптимальное решение задачинелинейного программирования. Пусть х*=х* (b) — решение ЗНП
f (x)→ min, (8)
xÎX= {xÎEn: gi (x) ≤bi, i=1,2,…, m; х≥0}
при некотором векторе bсвободных членов в ограничениях — неравенствах, а v(b) соответственно значение целевой функциипри этом решении ЗНП, т.е. v (b) =f (x*). Тогда справедлива следующая оценкаизменения целевой функции: ∆v=f (b+∆b) — f (b) при изменении вектора bна некоторый малый вектор-приращение ∆b:
∆f≈ (∆b,λ*), (9)
где λ* — вектор множителей Лагранжа,соответствующий решению х* (b).
1.2 Седловые точки функции Лагранжа
Существование экстремума тесно связано с наличием у функцииЛагранжа (6) так называемой />седловой точки.
Рассматривается задача выпуклого программирования сограничениями-неравенствами
f (x) →min, (10)
xÎX= {xÎEn: gi(x) ≤0, i=1,2,…, m; х≥0}.
Предполагается, что выполнено условие регулярности, т.е. можнорассматривать только вариант λ0=1.
Определение. Точка (х*, λ*), где х*Î Х, />ÎЕm,λ*≥0, называется седловой точкой функции Лагранжа L (x,λ), если
L (x*,λ)≤ L (x*,λ*) ≤ L (x,λ*). (11)
Утверждение 1 (критерий для седловой точки функции Лагранжа).Точка (х*, λ*) — является седловой для функции Лагранжа L (x,λ) в том итолько в том случае, когда выполнены следующие условия:
L (х*, λ*) =min {L(x, λ*) ׀ x Î Х},(12)
L (х*, λ*) =max {L (x*,λ) ׀ λ ≥0}, (13)
/>gi (x*) =0, i=1, 2,...,m, (14)
х*≥0,λ*≥0.
Условие (12) минимума функции Лагранжа по хэквивалентно выполнению в точке (х*, λ*) неравенства
/>≥0.(12′)
Условие (13) максимума функции Лагранжа по λ эквивалентновыполнению в точке (х*, λ*) неравенства
/>≤0.(13′)
Утверждение 2. х* — оптимальное решение задачи (3) втом и только в том случае, когда существует такой вектор λ* ≥0, что(х*, λ*) — седловая точка функции Лагранжа L(x,λ).
1.3 Решение задач квадратичного программированияметодом седловой точки
Рассмотрим задачу квадратичного программирования, т.е.
f (x) = (Сx,x) + (d,x) /> min, (15), g (x) =Ax≤ b,
где С — матрица размера n*n; d, х — векторы-столбцы n*1; А — матрица размера m*n; b — вектор-столбец m*1. Для задачи квадратичного программирования критерий существованияседловой точки приобретает вид задачи решения СЛАУ. Действительно, функцияЛагранжа в этом случае запишется в виде
L = />dkxk+/>/>ckjxkxj+/>λi (/>aijxj-bi),(16)
где ckj- элементы матрицы С; dk — элементы вектора d; bi — элементы векторасвободных членов b; aij- элементы матрицы А; λi- коэффициентыЛагранжа. Необходимые и достаточные условия оптимальности решения х*принимают вид
vj/> dj+2/>ckjxk+/> λiaij, vj≥0, (j=1,…,n), (17)
yi/> />aijxj-bi, — yi≤0, (i=1,...,m), (18)
xjvj=0, xj≥0, (j=1,...,n), (19)
λi(-yi) =0, λi≥0. (20)
Равенства (17), (18) образуют систему n+m линейных уравнений с 2 (n+m) неизвестными x1,…,xn,v1,…,vn, λ1,…, λm,y1,…,ym. Решения этой системы, при которыхвыполняются равенства (19), (20), дают координаты седловой точки (х*,λ*).Соответственно n координат х* даютоптимальное решение задачи (15).
2. Порядок выполнения лабораторной работы
Построить допустимую область задачи и линии уровня.
Записать функцию Лагранжа и необходимые условия экстремума,из которых аналитически или используя прикладные пакеты найти условно-стационарныеточки.
Для каждой точки указать активные и пассивные ограничения. Проверитьвыполнение достаточных условий экстремума в найденных стационарных точках. Найтиглобальный минимум функции. Используя критерий (утверждение 1), проверить, чтонайденная точка является седловой точкой функции Лагранжа.
Проверить справедливость оценки (9), решив задачу при положительныхи отрицательных малых значениях приращения ∆b.
Решить задачу квадратичного программирования методом седловойточки. Для этого записать систему (17) — (18), найти ее решения,удовлетворяющие условиям (19) — (20).
3. Пример выполнения лабораторной работы
Минимизировать нелинейную функцию /> при условиях /> и />, применяя метод функцииЛагранжа. Проверить справедливость оценки изменения целевой функции (9).
/>/> />
/>
Допустимая область — часть сферы />,лежащая в подпространстве
/>, a= (1, 1,1).
/>
Рассмотрим случай />. Еслипри этом />, то />.
Из (21) — (23) ®/>, что противоречит (28).
Если />, то /> (иначе получаемпротиворечия в (21) — (23)).
Из (21) — (23) ®/>. Подставим в (26): />. Отсюда />, что противоречитисходному предположению />.
Рассмотрим теперь случай />.
/>
Если />, тополучаем точку /> (из (1′) …(3′), (7′)).
Остальные «симметричные» точки здесь и далееприводить не будем.
Если />, />, />, то
/>,
/>,
/>.
Далее получаем точки
/> и />. />, />.
Для /> значение
/>, для /> значение />.
/>
Если />, />, то
Если />, то
/> и />.
Следовательно, /> и />. Однако, />, значит, пришли к
противоречию.
Таким образом, />.
Суммирование первых трех уравнений дает уравнение
/>,
в котором последнее слагаемое равно нулю, поэтому
/>.
С другой стороны,
/> и />.
Следовательно, />,
откуда />. Если />, то />.
Разделим равенства на />:/>. Однако, если />, то их произведение неможет быть равно />. Значит, />. Если />, получаем следующую систему:
/>
/>.
Получаем точку
/>
(в силу симметрии переменных х1, х2,х3 координаты можно переставить),
/>, />.
Предположив />,получим те же результаты.
Найдены следующие точки:
/>, />, />;
/>, />, />, />;
/>, />, />, />;
/>, />, />, />.
Запишем второй дифференциал обобщенной функции Лагранжа.
/>/>
/>, />, />;
/>.
/>
является активным ограничением только для точки />.
Применим достаточное условие минимума второго порядка к этойточке:
/>
Подставив /> и /> во второй дифференциалфункции Лагранжа, получим
/>.
Запишем матрицу квадратичной формы относительно приращений:
/>.
Для «верхнего» знака /> матрица
/>.
Для «нижнего» знака элементы матрицы меняют знак. Согласнокритерию Сильвестра, в этой точке нет экстремума.
Сравним значения функции в остальных точках:
/>; />; />.
Точкой глобального минимума является
/>,
значение функции в этой точке
/>-0, 192450. />.
Проверим справедливость оценки /> дляточки />, />.
Возьмем вектор />, емусоответствуют множители Лагранжа
/>.
Следовательно,
/>.
Перепишем условие задачи, введя приращение />:
/>;
/>
/>./>
/>Из первыхтрех уравнений получаем /> и подставимв последнее уравнение:
/>, />.
/>.
/>.
Возьмем, например, />
/>.
С другой стороны,
/>.
Аналогично для />
/> и />.
Решить задачу максимизации квадратичной функции
/> при условиях />15 и />1,2,3.
Перепишем условие следующим образом:
/>
Функция Лагранжа имеет вид
/>.
Необходимые и достаточные условия минимума:
/>,/>, />,
/>,/>,/>.
Получаем систему уравнений и неравенств:
/>
Для решения промежуточной задачи ЛП воспользуемся средствамиMS Excel. Введем формулы, соответствующие системе (рис.2), и начальноеприближение для решения системы уравнений (рис.3).
/>
Рис.2. Ввод данных задачи
/>
Рис.3. Задание начального приближения
Заполним поля диалога «Поиск решения» (рис.4).
/>
Рис.4. Экранная форма «Поиск решения»
В окне «Параметры» установим флажок «Неотрицательныезначения».
В результате решения найдена седловая точка функции Лагранжа
(х*,λ*) = (15; 0; 0; 30) (рис.5).
/>
Рис.5. Результаты поиска решения.
Оптимальное решение задачи: х* (15; 0; 0), f (x*)= 225.
4. Задания для лабораторного практикума
Решить задачу минимизации функции методом множителейЛагранжа.
Решить ЗНП методом седловой точки. Промежуточную задачурешения СЛАУ решить, используя EXCEL.
1. />.
2. />.
3. />.
4. />.
5. />.
6. />.
7. />.
8. />.
Ограничения (для всех вариантов):
/> />.
Контрольные вопросы:
Активные и пассивные ограничения. Регулярная задача.
Теорема Куна-Такера.
Достаточные условия минимума в задачах математическогопрограммирования.
Седловая точка.
Метод седловой точки для задачи квадратичногопрограммирования.
Библиографический список
1. Стандарт предприятия: Общие требования и правила оформления дипломных икурсовых проектов (работ): СТП УГТУ — УПИ 1 — 96. Екатеринбург, 1996.
2. Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич.М.: Высшая школа, 1993.335 с.
3. Аттетков А.В. Методы оптимизации / А.В. Аттетков, С.В. Галкин,
4. В.С. Зарубин. М.: МГТУ, 2004.432 с.
5. Васильев В.П. Численные методы решения экстремальных задач / В.П. Васильев.М.: Наука, 1980.518 с.
6. Габасов Р. Методы оптимизации / Р. Габасов, Ф.М. Кириллова. Минск: БГУ,1981.350 с.
7. Дьяконов В. Matlab: учебный курс / В. Дьяконов. СПб.: Питер, 2001.560 с.
8. Еремин И.И. / И.И. Еремин, Н.Н. Астафьев. М.: Наука, 1976.192 с.
9. Пантелеев А.В. Методы оптимизации в примерах и задачах /
10. А.В. Пантелеев, Т.А. Летова. М.: Высшая школа, 2005.544 с.
11. МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ: методические указания клабораторным работам / сост. С.Д. Чернина. Екатеринбург: УГТУ-УПИ, 2007.36 с.
Приложение
Рекомендации по использованию EXCEL иMATLAB
Построение графиков
Для построения графика функции y=f (x1,x2) могут быть использованы следующиеинструменты:
1. В EXCEL — Мастер диаграмм, подтип Поверхность.
а. Используя автозаполнение, на листе EXCELв столбец А и первую строку с выбранным шагом ввести соответственно значенияпеременных x1 и x2,для которых будут вычисляться значения функции.
б. В ячейку В2 ввести выражение для вычисления функции f (x1,x2) в точках $A2, B$1 (знак $ — признак абсолютной адресации, при которой будутзафиксированы первый столбец — перебор значений переменной x1и первая строка — перебор значений переменной x2)и нажать одновременно три клавиши Ctrl, Shift, Enter, поскольку формулаиспользуется для обработки массивов. В строке формул должны появиться фигурныескобки.
в. Выделить ячейку В2 и, протянув маркер заполнения сначалавниз, пробегая все ячейки, заполненные в столбце А, а затем вправо, пробегаявсе ячейки, заполненные в строке 1, заполнить массив значений функции в узловыхточках области построения графика.
г. На вкладке «Стандартные» Мастера диаграмм выбратьподтип Поверхность. Поверхностная диаграмма дает трехмерное изображениефункции, а контурная диаграмма представляет вид сверху на поверхностнуюдиаграмму и является аналогом линий уровня исследуемой функции.
2. В MATLAB — функции plot3, mesh, surf, surfl.
а. С помощью функции meshgridполучить двумерные массивы координат узловых точек области построения графика: u=a: ∆1: b;v=c: ∆2: d; [x,y] =meshgrid (u,v).
б. Задать исследуемую функцию: f= f (х, у).
в. Применяя указанные выше функции, получить трехмерноеизображение: plot3 (x,y,f) или mesh (x,y,f), surf(x,y,f), surfl (x,y,f).
/>Действияс матрицами
Для нахождения собственных значений и собственных векторовматрицы Гессе могут быть использованы следующие инструменты MATLAB:
λ = eig (a)- функция eig (a) возвращает собственныезначения заданной матрицы a. Пример заданияматрицы 4х4: a = [16 3 2 13; 5 10 11 8; 9 6 7 12;4 15 14 1] ;
[v,d]= eig (a) — при таком обращении функциявозвращает собственные векторы v и собственныезначения как элементы диагональной матрицы d.
Для нахождения матрицы, обратной матрице Гессе, могут бытьиспользованы следующие инструменты:
В EXCEL — функция МОБР возвращает обратную матрицу дляматрицы, хранящейся в массиве.
В MATLAB — функция y=inv (a) возвращает обратнуюматрицу для матрицы a.