Рефотека.ру / Математика

Лабораторная работа: Методы оптимизации функций многих переменных

Кафедра: ИТ


МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ

МНОГИХ ПЕРЕМЕННЫХ


Екатеринбург 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), то


grad f (x*) =0. (2)


Пусть функция f (x) дважды дифференцируема в точке х*Методы оптимизации функций многих переменныхRn. Тогда

а) если х* - точка локального минимума в задаче (1), то матрица Гессе Н (х*) неотрицательно определена, т.е. Методы оптимизации функций многих переменныхрМетоды оптимизации функций многих переменныхRn выполняется неравенство (Н (х*) р,р) ≥0;

б) если х* - точка локального минимума в задаче (1), то матрица Н (х*) неположительно определена, т.е. Методы оптимизации функций многих переменныхрМетоды оптимизации функций многих переменныхRn выполняется неравенство (Н (х*) р,р) ≤0.

Пусть функция f (x) дважды дифференцируема в точке х*Методы оптимизации функций многих переменныхRn и


grad f (x*) =0. Тогда


а) если матрица Н (х*) положительно определена, т.е. Методы оптимизации функций многих переменныхрМетоды оптимизации функций многих переменныхRn, р≠0, (Н (х*) р,р) >0, то х* - точка строгого локального минимума функции f (x) на Rn;

б) если матрица Н (х*) отрицательно определена, т.е. Методы оптимизации функций многих переменныхрМетоды оптимизации функций многих переменныхR, р≠0, (Н (х*) р,р) <0, то х* - точка строгого локального максимума функции f (x) на Rn.

Если grad f (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-tkgrad f (xk), k=0,1,… (4)

Начальная точка х0 и начальный шаг t0 задаются пользователем. Величина шага t0 не изменяется до тех пор, пока функция убывает в точках последовательности. Это контролируется путем проверки выполнения условия f (xk+1) - f (xk) <0 (или <-ε). Если условие убывания не выполняется, то величина шага уменьшается, как правило, вдвое, т.е. tk=tk/2.

Метод наискорейшего градиентного спуска

Как и в предыдущем методе, точки релаксационной последовательности {xk}, k=0,1,… вычисляются по правилу (4). Точка х0 задается пользователем; величина шага tk определяется из условия минимума одномерной функции φ (tk) =f (xk-tkgrad f (xk)). Задача минимизации функции φ (tk) может быть решена с использованием необходимого условия минимума Методы оптимизации функций многих переменных=0 с последующей проверкой достаточного условия минимума Методы оптимизации функций многих переменных>0 или с использованием численных методов.

Метод сопряженных направлений (Флетчера - Ривса).

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

Определение. Векторы p и q называются сопряженными относительно матрицы Q, если выполняется равенство pQq=0.

Точки релаксационной последовательности {xk}, k=0,1,… вычисляются по правилу


xk+1=xk-tkdk, k=0,1,…;

dk = - grad f (xk) +βk-1 dk - 1; (5)

d0= - grad f (x0);

βk-1=║grad f (xk) ║2∕║grad f (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) grad f (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: Alternating sign

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: Alternating sign

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-r<n},


где среди функций f (x) и gi (x) могут быть нелинейные.

Активные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде равенства.

Пассивные ограничения - неравенства в точке х* ─ это ограничения, которые выполняются в данной точке в виде строгого неравенства.

Если градиенты активных ограничений-неравенств и ограничений-равенств в точке х* линейно независимы, то говорят, что в оптимальной точке выполнено условие регулярности.

Обобщенная функция Лагранжа для задачи со смешанными ограничениями задается как


L (x,λ0,λ) =λ0f (x) +Методы оптимизации функций многих переменныхλigi (x). (7)


При выполнении условия регулярности λ0≠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 - 96. Екатеринбург, 1996.

Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. М.: Высшая школа, 1993.335 с.

Аттетков А.В. Методы оптимизации / А.В. Аттетков, С.В. Галкин,

В.С. Зарубин. М.: МГТУ, 2004.432 с.

Васильев В.П. Численные методы решения экстремальных задач / В.П. Васильев. М.: Наука, 1980.518 с.

Габасов Р. Методы оптимизации / Р. Габасов, Ф.М. Кириллова. Минск: БГУ, 1981.350 с.

Дьяконов В. Matlab: учебный курс / В. Дьяконов. СПб.: Питер, 2001.560 с.

Еремин И.И. / И.И. Еремин, Н.Н. Астафьев. М.: Наука, 1976.192 с.

Пантелеев А.В. Методы оптимизации в примерах и задачах /

А.В. Пантелеев, Т.А. Летова. М.: Высшая школа, 2005.544 с.

МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ: методические указания к лабораторным работам / сост. С.Д. Чернина. Екатеринбург: УГТУ-УПИ, 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.


1 Лабораторная работа выполнена студентом Коневым С.

Похожие работы:

  1. • определение внешних спецификаций уравнений
  2. • Применение экономико-математических методов в ...
  3. • Минимум функции многих переменных
  4. • Минимизация функции многих переменных. Приближённые численные ...
  5. • Экзаменационные билеты по методам оптимизации за весенний ...
  6. • Поиск максимума одной функции многих переменных ...
  7. • Сравнительный анализ методов оптимизации
  8. • Математический обзор
  9. • Сравнительный анализ методов оптимизации
  10. • Функция многих переменных
  11. • Классические методы безусловной оптимизации
  12. • Экстремумы функций многих переменных
  13. • Экстремумы функций многих переменных
  14. • Функции нескольких переменных
  15. • Экстремумы функций
  16. •  ... нелинейных "овражных" функций двух переменных
  17. • Методы синтеза и оптимизации
  18. • Билеты математические методы исследования экономики
  19. • Экзаменационные вопросы и билеты по предмету МАТЕМАТИЧЕСКИЕ ...
Смотреть все похожие работы
Рефетека ру refoteka@gmail.com