Реферат по методам оптимизации Теоремы о необходимых и достаточных условиях локального минимума. Реферат "Теоремы о необходимых и достаточных условиях локального минимума."
 Скачать 164.79 Kb.
|
|
Реферат: "Теоремы о необходимых и достаточных условиях локального минимума." Выполнили: Бетехтина М, Прасолова А. 10 апреля 2022 г. 1 Введение. Во многих областях науки и в практической деятельности часто приходится сталкиваться с задачами поиска экстремума функции. Дело в том, что многие технические, экономиче- ские и т.д. процессы моделируются функцией или несколькими функциями, зависящими от переменных – факторов, влияющих на состояние моделируемого явления. Требуется найти экстремумы таких функций для того, чтобы определить оптимальное (рациональное) состоя- ние, управление процессом. Так в экономике, часто решаются задачи минимизации издержек или максимизации прибыли - микроэкономическая задача фирмы. При изучении любого типа задач оптимизации важное место занимает вопрос об условиях оптимальности, или, как еще говорят, условиях экстремума. Различают • условия оптимальности, т. е. условия, которым должна удовлетворять точка, являюща- яся решением задачи, • достаточные условия оптимальности, т. е. условия, из которых следует, что данная точка является решением задачи. Целью данной работы является формулировка теорем о необходимых и достаточных усло- виях локального минимума. Постановка задачи оптимизации Стандартная математическая задача оптимизации формулируется таким образом. Среди эле- ментов x, образующих множество X, найти такой элемент x ∗ , который доставляет минималь- ное значение f(x ∗ ) заданной функции f(x). Для того, чтобы корректно поставить задачу оптимизации, необходимо задать: 1. Допустимое множество - множество X = {⃗x| g i (⃗ x) ≤ 0, i = 1, . . . , m} ⊂ R n 2. Целевую функцию - отображение f : X → R 3. Критерий поиска (max или min). Теорема о существовании решения Теорема 1 Пусть X - компакт в R n (т.е. замкнутое ограниченное множество), f - непрерывная функция на X. Тогда точка глобального минимума функции f на X (глобальное решение задачи f (x) → min, x ∈ X (1) существует). Также представим другую формулировку данной теоремы: Пусть X - замкнутое множество в R n , f - непрерывная функция на X, причем при некото- ром x 0 ∈ X множество N(x 0 ) = {x ∈ X | f (x) ≤ f (x 0 )} ограничено. Тогда точка глобального минимума функции f на X существует. Доказательство Из замкнутости X и непрерывности f следует, что множество N(x 0 ) замкнуто и поэтому является компактом. По теореме 1 точка минимума f на N(x 0 ) существует. Из определения N (x 0 ) ясно, что она же будет точкой минимума f на x. Теорема доказана. Задача (1) представляет собой общую постановку задачи оптимизации. Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида функ- ции f и множества X. Задача безусловной оптимизации Задача (1) называется задачей безусловной оптимизации, есхи x = R n , т.е. если она имеет вид f(x) → min, x ∈ R n (5) Пусть f ′ (x ∗ ) = df dx 1 (x ∗ ), . . . , df dx n (x ∗ ) 2 - вектор первых частных производных (градиент) функции f в точке x ∗ ∈ R n ; f ′′ (x ∗ ) = d 2 f dx i dx j (x ∗ ) i,j=1,...,n - матрица вторых частных производных (гессиан) функции f в точке x ∗ ∈ R n Теорема 2 Пусть функция f : R n → R дифференцируема в точке x 0 ∈ G . Если f достигает в x 0 ∈ G локального минимума на G, то ▽f (x 0 ) ′ z ≥ 0 ∀z ∈ T (x 0 ) Доказательство Для z = 0 имеем ▽f(x 0 ) ′ z = 0 . Пусть z ∈ T (x 0 ) , z ̸= 0. Тогда существуют λ ∈ R + и z ∗ ∈ T (x 0 ), ∥ z ∗ ∥= 1, такие, что z = λz ∗ Пусть, далее, x k ⊂ G − последовательность, для которой x k z ∗ −→ x 0 Так как функция f достигает в x 0 локального минимума на G, то для достаточно большого k выполняется неравенство f(x k ) ≥ f (x 0 ). Отсюда с учётом предыдущей теоремы следует lim k→∞ f (x k ) − f (x 0 ) ∥ x k − x 0 ∥ = ▽f (x 0 ) ′ z ∗ ≥ 0, а потому и ▽f(x 0 ) ′ z ≥ 0. Теорема 3 Пусть функция f : R n → R дважды дифференцируема в точке x 0 ∈ G . Если f достигает в x 0 локального мининмума на G и ▽f(x 0 ) = 0, то z ′ ▽ 2 f (x 0 )z ≥ 0 ∀z ∈ T (x 0 ) Доказательство Пусть {x k } ⊂ G - последовательность такая, что x k z − → x 0 В силу соотношений ▽f(x 0 ) ′ (x k − x 0 ) = 0 и f(x k ) − f (x 0 ) ≥ 0 с учетом первой теоремы для достаточно большого k имеем lim k→∞ f (x k ) − f (x 0 ) − ▽f (x 0 ) ′ (x k − x 0 ) ∥ x k − x 0 ∥ 2 = 1 2 z ′ ▽ 2 f (x 0 )z ≥ 0. Итог В данной работе мы сформулировали теоремы о необходимых и достаточных условиях ло- кального минимума и привели доказательства этих теорем. 3 |