Xreferat.com » Рефераты по математике » Методы оптимизации функций многих переменных

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

многих переменных" width="539" height="28" border="0" />, метод Ньютона.

Методы оптимизации функций многих переменных, метод дробления шага.

Методы оптимизации функций многих переменных, метод Нелдера-Мида.

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

Методы оптимизации функций многих переменных, метод Ньютона.


Контрольные вопросы:

Объяснить алгоритмы следующих методов

Метод конфигураций (Хука-Дживса).

Метод деформируемого многогранника (Нелдера Мида).

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

Метод сопряженных направлений и его модификации.

Метод Ньютона и его модификации.

Метод дробления шага.

Лабораторная работа № 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 координаты можно переставить),


Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных.


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

Найдены следующие точки:


Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных;

Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных;

Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных;

Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных, Методы оптимизации функций многих переменных.


Запишем второй дифференциал обобщенной функции Лагранжа.


Методы оптимизации функций
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

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