Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании icon

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании




Скачать 489.84 Kb.
НазваниеМетодические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании
страница1/3
Дата конвертации20.05.2013
Размер489.84 Kb.
ТипМетодические указания
источник
  1   2   3




Министерство общего и профессионального образования

Российской Федерации


Ростовский ордена Трудового Красного Знамени

государственный университет


Л.Н. Землянухина, И.Ю.Виноградова


МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для студентов

механико-математического факультета


УСЛОВИЯ ОПТИМАЛЬНОСТИ

В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ


г.Ростов-на-Дону

1996


Методические указания рекомендованы к печати заседанием кафедры исследования операций механико-математического факультета РГУ,

ПРОТОКОЛ № 2 от 3 октября 1996 г.


СОДЕРЖАНИЕ



1. Выпуклые множества и функции . . . . . . . . . . . . . . . . . . . . . .


2. Основные понятия и определения теории оптимизации . . . . . . . . .


3. Задача безусловной минимизации . . . . . . . . . . . . . . . . . . . . .


4. Задача минимизации в общей постановке . . . . . . . . . . . . . . . . .


5. Задача минимизации с ограничениями-равенствами . . . . . . . . . . .


6. Задача минимизации с ограничениями-неравенствами. . . . . . . . . .


7. Задания для индивидуальной работы . . . . . . . . . . . . . . . . . . .


Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


4


8


9


10


13


18


29


30


При изучении любого типа задач оптимизации важное место занимает вопрос об условиях оптимальности. Различают необходимые и достаточные условия оптимальности. В простых случаях эти условия позволяют явно решить задачу. Кроме того эти условия используются при построении и обосновании численных методов решения задач оптимизации. В методических указаниях рас­смат­ри­вают­ся две темы из курса "Методы оптимизации": выпуклый анализ, ус­ло­вия оптимальности. Понятия и факты выпуклого анализа играют важную роль в теории и численных методах оптимизации.


1. Выпуклые множества и функции


Определение 1. Выпуклой комбинацией точек n-мерного ев­кли­дова прос­т­ран­с­тва называется сле­­дую­щая линейная комбинация

, где ; .

В случае = 2 при фиксированных выпуклая комбинация геометрически есть некоторая точ­ка отрезка , соединяющего .

Определение 2. Полная совокупность всех выпуклых комбинаций точек называется выпуклую оболочку, натянутой на эти точки .

Геометрически при = 2 вы­пуклая оболочка - это отрезок, соединяющий .

Можно дать и другие определения выпуклой комбинации двух точек (все они эквивалентны).

Определение 3. Выпуклой комбинацией двух точек на­зы­вается линейная комбинация , где .

Определение 4. Выпуклой комбинацией двух точек назы­вается точка , где .

Определение 5. Множество называется выпуклым, если оно со­дер­жит любую выпуклую комбинацию любых двух своих точек , т.е.



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


Рис.1. Пример выпуклого (слева) и невыпуклого (справа) множеств











Лемма 1. Пусть — гиперплоскость n-мерного пространства:

,

— полупространство n-мерного пространства: .

Тогда и — выпуклые множества.


Лемма 2. Пусть - конечное или бесконечное множество индексов, - выпуклые множества. Тогда их пересечение выпукло.


Определение 6. Линейной комбинацией множеств называется множес­тво

где - любые числа.

Лемма 3. Линейная комбинация выпуклых множеств есть выпуклое мно­жество.


Определение 7. Точка называется внутренней точкой множества , если существует такое , что , где - единичный шар радиуса с центром в начале коорди­нат. Множество внутренних точек множества называется внутренностью множества и обозначается int.


Лемма 4. Замыкание и внутренность выпуклого множества выпуклы.


^ Теорема 1 (критерий выпуклости множества). Множество выпукло тогда и толь­ко тогда, когда оно содержит любую выпуклую комбинацию любого конеч­но­го числа своих точек.


Определение 8. Пусть непустое множество. Крайней точкой этого множества называется такая точка , которую нельзя представить в виде выпуклой комбинации двух различных и отличных от нее точек этого множества.


^ Теорема 2 (о представлении выпуклого множества). Любую точку вы­пук­ло­го,

замкнутого, ограниченного множества можно пред­ста­вить в виде выпуклой ком­бинации конечного числа крайних точек это­го множества.


Определение 9. Пусть дана функция , определенная на вы­пук­лом множестве : . Функция называется выпуклой, если для любых точек и это­го множества и для любых и () вы­пол­няет­ся неравенство:

.


Неравенство, определяющее выпуклую функцию, можно распространить на любое конечное число точек.

Теорема 3. Пусть выпуклая функция на множестве . Тогда для любого конечного числа точек и име­ет место неравенство (неравенство Йенсена)

.


Некоторые свойства выпуклых функций.

1. Пусть — выпуклая функция и — некоторая скалярная величина, тогда множество является выпуклым мно­жес­твом.

2. Пусть — выпуклые функции, определенные на выпуклом множестве , тогда линейная неотрицательная ком­би­на­ция этих функций есть выпуклая функция.

3. Если — выпуклая функция, определенная на выпуклом мно­жестве , то есть выпуклая функция.

4. Линейная функция является выпуклой функцией.


Определение 10. Пусть определена на выпуклом множестве и пусть . Обозначим . Одно­мер­ным сечением в точке в направлении называется функция , .

Пример 1. Найти одномерное сечение функции в точке (1, 1) в направлении (1,-1).

Решение. Построим вектор .

Найдем теперь функцию



Эта функция является решением поставленной задачи.


Теорема 4. Функция выпукла тогда и только тогда, когда вы­пук­лым является любое её одномерное сечение.

Пример 2. Доказать выпуклость функции на .

Решение. Рассмотрим одномерное сечение этой функции в произвольной точке в производьном направлении. Имеем




Эта функция представляет собой линейную комбинацию линейной функции

и функции с коэффициентом . Так как функция выпукла (это нетрудно проверить самостоятельно), то функция — выпукла и, следовательно, — выпукла.


Если функция дифференцируема, то через обозначим ее градиент, а через матрицу вторых производных или гессиан.


Теорема 5 (критерий выпуклости для дифференцируемых функций). Пусть функ­ция определена на выпуклом множестве и дважды непрерывно диф­фе­ренцируема. Для того, чтобы функция была выпуклой, необходимо и дос­та­­точно, чтобы гессиан этой функции, вычисленный в любой точке , являлся неот­­рицательно определенной матрицей (или необходимо и достаточно, чтобы вторая производная любого одномерного сечения была неотрицательной).

Для распознавания определенности матрицы применяется кри­терий Силь­вестра .


^ Теорема 6 (критерий Сильвестра). Симметрическая матрица A является положительно (не­от­ри­ца­тель­но) определенной тогда и только тогда, когда все ее угловые (главные) ми­но­ры положителны (неотрицательны).


Пример 3. Проверить на выпуклость функцию

Решение. Найдем частные производные второго порядка этой функции:





Найдем теперь гессиан данной функции и вычислим все угловые миноры гессиана:

;







Так как среди угловых миноров есть отрицательные, то функция не яаляется выпуклой.


Пример 4. Найти область выпуклости функции: .


Решение. Найдем гессиан данной функции. Имеем:






Для выпуклости функции необходимо потребовать неот­ри­ца­тельность угловых миноров. Итак область выпуклости функции определяется неравенствами:





Упражнения:

1. Применяя неравенство Йенсена к соответствующим функциям, вывести следующие неравенства:

а) , где

б)

в)

2. Проверить выпуклость функций:


а) на ;

б) на .

3. Показать, что функция выпукла на множестве .

4. Построить область выпуклости функции

а) ;

б)

5. Определить, при каких значениях a, b, c функция выпукла на .


2. Основные понятия и определения теории оптимизации


В этом разделе приводится ряд фактов, относящихся к задаче минимизации в общей постановке.

Запишем задачу на минимум в виде




(1)





При этом будем называть целевой функцией, X— допустимым мно­жест­вом, любой элемент — допустимым решением (допустимой точкой) задачи (1).

Определение 11. Точка называется точкой глобального минимума (гло­баль­ным решением) функции на множестве X , если

при всех .

Определение 12. Точка называется точкой локального минимума (ло­каль­­ным решением) функции на множестве X , если существует число такое, что

при всех ,

где — шар радиуса с центром в точке .

Если указанные неравенства выполняются как строгие при , то говорят, что - точка строгого минимума в гло­баль­ном или локальном смысле.


^ Под оптимальным решением понимают точку глобального минимума.


Теорема 7 (об экстремумах выпуклой функции). Если , — выпуклая функция, то любой ее локальный минимум яв­ляет­ся также и глобальным и множество точек минимума выпукло.


Определение 13. Задача (1) называется задачей безусловной оптимизации, если , т.е. если она имеет вид:




(2)






При исследовании оптимизационных задач часто будет использована следующая

^ Теорема Вейерштрасса. Непрерывная функция на непустом ог­ра­ниченном замк­ну­­том множестве конечномерного пространства достигает своих глобальых ми­ни­му­ма и максимума.

Сформулируем и следствие из этой теоремы, которое будем использовать.


Следствие. Если функция непрерывна на и , то дос­тигает своего глобального минимума на любом замкнутом множестве из .


^ 3. Задача безусловной минимизации

Рассмотрим задачу безусловной минимизации (2).

Пусть — вектор первых частных про­из­водных (градиент) функции f в точке ;

— матрица вторых частных производных (гес­сиан) функции f в точке .

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


Теорема 8. Пусть функция f дифференцируема в точке . Если — локальное решение задачи (2), то .

Теорема 9. Пусть функция f дважды дифференцируема в точке . Если — локальное решение задачи (2), то матрица (гессиан) неотрицательно определена, т.е.

при всех .


^ Достаточное условие локальной оптимальности содержит усиление требований на матрицу .

Теорема 10. Пусть функция f дважды дифференцируема в точке . Если и матрица (гессиан) положительно определена, т.е.

при всех ,

то — строгое локальное решение за­­дачи (2).

Схема решения задачи (2):


1) выписать необходимое условие ;

2) найти стационарные точки, т.е. решения уравнений ;

3) отыскать оптимальные решения среди стационарных точек или доказать, что ре­ше­ния нет.


Пример 5. Рассмотрим задачу



Очевидно, что , а из следствия теоремы Вейерштрасса вы­текает, что глобальный минимум в задаче дости­гает­ся. Используем необ­хо­ди­мые условия:



Решая эту систему, находим стационарные точки (0,0), (1,1), (-1,-1). Теперь выпишем гессианы в этих точках. Так как

,

то , .

С помощью критерия Сильвестра устанавливаем, что матрица не­по­ло­жи­­­тель­но определенная, т.е. не выполняется необ­хо­димое условие минимума, зна­­чит точка (0,0) не является точ­кой локального минимума. Матрицы и поло­жи­тель­но определенные, т.е. выполняется достаточное условие; точ­­ки (1,1) и (-1,-1) являются точками локального минимума. А поскольку , то они доставляют и глобаль­ный минимум, т.е. яв­ляют­ся оптимальными решениями.

Упражнения

Найти все решения следующих задач безусловной оптимизации:

1.

2.

3.

4.


^ 4. Задача минимизации в общей постановке


Рассмотрим задачу минимизации в общей постановке (1)











Условия оптимальности для задачи (1) даны в следующей теореме.

Теорема 11. Пусть в задаче (1) множество X выпукло, функция диф­фе­рен­ци­руема в точке . Тогда для того, чтобы являлось локальным решением за­дачи (1) необходимо, а в случае выпуклости на X и достаточно, чтобы вы­пол­нялось условие

при всех

(3)





Полезно конкретизировать условие (3): если внутренняя точка множества X, то (3) эквивалентно условию




(4)





А это известный результат для задачи безусловной оптимизации.

Пусть теперь множество X имеет вид , где . Тогда (3) эквивалентно условию




(5)




Рассмотрим случай, когда множество X имеет вид . Тогда (3) эквивалентно системе условий:



(6)





В простейших случаях полученные результаты позволяют явно решить задачу.


^ Схема решения задачи (1):


1) выписать необходимое условие ;

2) найти все решения, удовлетворяющие этому условию;

3) отыскать среди них оптимальные решения или доказать, что решения нет.

Пример 6. Пусть требуется найти все (локальные и гло­баль­ные) решения задачи:



Согласно теореме 11 и условиям (5) любое локальное решение () задачи должно удовлетворять следующим условиям:




(7)










(8)




Теперь необходимо составить шесть систем путем попарного комбинирования соот­­ношений (7) и (8), затем найти решения каждой из систем, исследовать их на оп­тимальность. Однако проведем сперва анализ задачи. Функция является квад­ратичной с положительно определенной матрицей вторых производных (ис­поль­зуется критерий Сильвестра); следовательно, она строго выпуклая на . Поэтому локальные и глобальные решения совпадают и задача имеет един­ст­вен­ное решение , удовлетворяющее условиям (7) и (8).


Рассмотрим первую систему





Она несовместна.







Перейдем к рассмотрению второй системы




Ее решением является

(-1/2, 2). Это и есть оптимальное решение задачи.





Просмотр оставшихся четырех систем излишен.


Пример 7. Пусть требуется найти все оптимальные решения задачи:



Воспользуемся необходимым условием оптимальности (6):

.

Имеем 2 точки: и .

Рис. 2. Графическое решение примера 7



Из графика функции (рис.2) видно, что — точка локального максимума, точки глобального максимума не существует, — точка глобального минимума, т.е. оптимальное решение задачи на минимум.

Упражнения

1. При всех значениях вектора с решить задачи:

а) ,

б)

2. При каких значениях числа а точка (0, 0) является решением задачи



3. Решить задачи:

а)

б)


^ 5. Задача минимизации с ограничениями-равенствами

Рассмотрим классическую задачу на условный экстремум




(9)





При исследовании задачи (9) важную роль играет функция Лагранжа




(10)




где .

Определение 14. Стационарной точкой функции Лагранжа называется точка , удовлетворяющая условиям




(11)









(12)






где , ,

при этом , .


Теорема 12 (Лагранжа). Пусть функции непрерывно диф­фе­рен­цируемы в некоторой окрестности точки . Если — локальное ре­шение задачи (9), то существует число и вектор , не рав­ные нулю одновременно и такие, что выполняется условие (11). Если при этом гра­диенты линейно независимы (условие регулярности), то .


Как и в случае безусловной задачи оптимизации, стационарные точки за­да­чи не обязаны быть решениями. Здесь также существуют достаточные условия с прив­лечением вторых производных. Обозначим через



матрицу вторых производных функции Лагранжа по координатам вектора x.

Теорема 13. Пусть функции дважды диф­ферен­ци­руе­мы в точке , удовлетворяющей (12), т.е. . Пред­по­ло­жим, что при некоторых и выполняется условие (11) и, кроме того,



(13)




при всех ненулевых таких, что

.

(14)




Тогда строгое локальное решение задачи (9).


Схема решения задачи (9):

1) составить функцию Лагранжа ;

2) выписать необходимые условия:



3) найти стационарные точки, т.е. допустимые решения системы уравнений п. 2, в которых не все множители Лагранжа равны нулю. При этом следует рассмотреть случаи . Во втором случае мож­но положить равным единице.

4) отыскать оптимальные решения среди стационарных точек или доказать, что решения нет.


Пример 8. Пусть требуется найти все оптимальные решения задачи:



Так как в задаче одно ограничение, то условие регулярности выполняется. Поэтому рассмотрим сразу регулярную функцию Лагранжа :



Поскольку , стационарные точки удов­­­­лет­во­ряют следующей системе:



Эта система имеет три решения:

1)

2) ,

3) .


Теперь проверим достаточное условие минимума для каждой точки. Имеем:



Для указанных решений эта матрица принимает вид

, , .

Условие (14) имеет вид:

Для первого решения получаем 3 =0 , т.е. = 0. Проверим условие (13):

для всех . т.е. условие (13) вы­пол­не­но и, следовательно, точка (0, 1) — строгое локальное решение за­да­чи.

Для второго решения получаем 3= 0, т.е. =0 и условие (13) для всех , отсюда делаем вывод, что точка (1,0) — строгое локальное решение задачи.

Теперь рассмотрим третье решение:

, , для всех , поэтому точка ( ) не является решением зада­чи.

Пример 9. Найти размеры ящика наибольшего объема, у ко­то­ро­го сумма длины и поперечных размеров равна .


Решение. Обозначим через - длину, ширину и глу­би­ну ящика соответственно. Тогда задача нахождение размеров сво­дится к решению следующей оптимизационной задачи:




Множество допустимых значений ограничено, так как и замкнуто, поэтому решение существует. Отбросим условия неот­ри­цательности и найдем локальные максимумы задачи Лагранжа. Так как в задаче одно ограничение, то условие регулярности выпол­няет­ся. Поэтом рассмотрим сразу регулярную функцию Лагранжа ():



Поскольку стационарные точ­­­ки удовлетворяют следующей системе:




Эта система имеет четыре решения:




В силу того, что для первых трех решений значение функции рав­но 0, а для четвертого -, проверим достаточное условие ми­ни­мума для четвертой точки. Имеем:





Для четвертого решения эта матрица принимает вид




Условие (14) имеет вид: , т.е. . Проверим условие (13):




для всех и, следовательно, точка - строгое ло­кальное решение задачи Лагранжа. Но найденная точка удовлет­во­ряет условию неот­ри­ца­тель­ности, поэтому она является оптималь­ным решением задачи.


Пример 10. Найти все оптимальные решения задачи:





Введем функции ограничений :





Так как векторы-градиенты линейно-не­за­висимы, то условие регулярности выполняется. Поэтом рас­смот­рим сразу регу­ляр­ную функцию Лагранжа ():





Поскольку , стационарные точ­ки удовлетворяют следующей системе:



Эта система имеет единственное решение:. Те­перь проверим дос­таточное условие минимума для этой точки. Имеем:

.


Условие (14) имеет вид:




получаем . Проверим условие (13):


, для всех , т.е. ус­ло­вие (13) выпо­лне­но и, следовательно, точка — строгое локальное решение задачи. Покажем, что эта точка является и гло­бальным решением, применив следствие из теоремы Вейер­штрас­са. Для этого преобразуем целевую функцию, исключив перемен­ные с помощью ограничений:





Имеем т.е. решение существует. Итак, точка — оп­ти­маль­ное решение задачи.

Упражнения

Найти все решения следующих задач условной оптимизации с ограничениями-равенствами


1.



2.







3.




4.




5.




6.





  1   2   3

Добавить документ в свой блог или на сайт



Похожие:

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания для студентов механико-математического факультета по курсу «Методы оптимизации» для дневного и вечернего отделений
Методические указания предназначены для студентов механико-математического факультета. Они продолжают серию методических указаний...

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания по курсу "Методы оптимизации" для студентов механико-математического факультета
Методические указания рекомендованы к печати заседанием кафедры исследования операций механико-математического факультета ргу

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания по курсу "Методы оптимизации" для студентов механико-математического факультета
Методические указания рекомендованы к печати заседанием кафедры исследования операций механико-математического факультета ргу

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания по курсу "Методы оптимизации" для студентов механико-математического факультета
Методические указания рекомендованы к печати заседанием кафедры исследования операций механико-математического факультета ргу

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания по курсу "Методы оптимизации" для студентов механико-математического факультета
Основные понятия

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания для студентов 1 и 2 курсов (дневного и вечернего отделений) механико-математического факультета
Методические указания предназначены для поддержки основного курса, связанного с методами программирования, «Системное программирование»....

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания для студентов 2 курса вечернего отделения механико-математического факультета по курсу
Методические указания разработаны сотрудниками кафедры прикладной математики и программирования: доцентом Я. М. Русановой, старшим...

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания для студентов 1 курса вечернего отделения механико-математического факультета по курсу
Методические указания разработаны сотрудниками кафедры прикладной математики и программирования: доцентом Я. М. Русановой, старшим...

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания для студентов дневного и вечернего отделений механико-математического факультета по курсу "Методы оптимизации"
Одновременное решение прямой и двойствен­ной задач

Методические указания для студентов механико-математического факультета условия оптимальности в нелинейном программировании iconМетодические указания к практическим заданиям по с/к «Обратные задачи механики» для студентов механико-математического факультета
Методические указания разработаны доктором физико-математических наук, заведующим кафедры теории упругости, профессором А. О. Ватульяном...

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©ttu.rushkolnik.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы