9892

Классические методы безусловной оптимизации

Реферат

Математика и математический анализ

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

Русский

2013-03-18

101 KB

10 чел.

Классические методы безусловной оптимизации

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

Определение 1.1. Функция f(x) одной переменной имеет локальный минимум в точке x, если существует , такая, что  для всех , то есть если существует некоторая окрестность точки , в которой значение функции в любой ее точке больше, чем .

Определение 1.2. Функция имеет глобальный минимум в точке , если  для всех x из области определения f(x).

     

0

      

   

Из рисунка 1 видно, что в точках и касательная к графику функции будет параллельна оси OX, а это означает, что производная функции в этих точках будет равна нулю. Следовательно, и будут решениями уравнения .

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

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

Надежное основание для полученных результатов дает разложение функции в ряд Тейлора в окрестности точки ( , ).

 

Если - точка минимума, то для любого достаточно малого .

Если , то отрицательное h сделает отрицательной разность , что невозможно в точке минимума. Если, то произойдет то же самое, если выбрать положительное h. Следовательно,  - это необходимое условие существования минимума в точке .

Так как всегда, то при  и  всегда выполняется , то есть   - точка минимума, а при ,  (h - любое) и - точка максимума. Следовательно, это достаточные условия.

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

Это позволяет сформулировать следующее правило:

Теорема 1(необходимое и достаточное условие существования экстремума функций одной переменной). 

Если функция и ее производные непрерывны, то точка является точкой экстремума (максимума или минимума) тогда и только тогда, когда порядок ее первой, не обращающейся в ноль в точке производной есть четное число. При этом, если , то - точка максимума, если , то - точка минимума.

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

Рассмотрим функцию   действительных переменных. Введем матричные обозначения для точки в n-мерном пространстве, градиента (вектора частных производных первого порядка функции f) и гессиана (матрицы частных производных второго порядка):

 - точка в n-мерном пространстве,

- градиент,

- гессиан (матрица Гессе).

- элемент -  частная производная второго порядка.

Напомним, что - симметрическая матрица.

Определение 3. Функция имеет локальный минимум в точке , если существует окрестность точки , такая, что во всех точках этой окрестности, то есть существует такая >0, что для всех  справедливо .

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

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

Запишем разложение функции в ряд Тейлора:

=  .   H = (h1, h2, . . . , hn)T.

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

Следовательно, необходимое условие существования минимума в точке :

  .

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

Достаточное условие минимума:

- положительно определена.

Достаточное условие максимума:

- отрицательно определена.


Пример:

, тогда

положительно определена при любом Х,

поэтому точка (2, 4, 6) является точкой локального минимума, а так как это единственная стационарная точка, то она же является и точкой глобального минимума.

Таким образом, для решения задачи оптимизации классическим методом необходимо решить систему уравнений , что невозможно сделать аналитически за исключением очень узкого класса таких систем (например, система линейных уравнений невысокого порядка). Затем придется еще устанавливать определенность гессиана, что тоже является совсем нетривиальной задачей в случае больших размерностей. Все это приводит к необходимости разрабатывать итерационные процедуры решения задач оптимизации.

 


 

А также другие работы, которые могут Вас заинтересовать

34379. Прогнозирование валютного курса 38 KB
  Если большое количество стран конкурирует в экспортировании товаров и услуг тогда величина экспорта будет очень чувствительна даже к небольшим изменениям обменного курса. Это не изменит курса обмена. Процесс формирования валютного курса можно подразделить на два этапа: определение валютного курса который отражает реальную стоимость национальной валюты по аналогии с себестоимостью товара формирование рыночного валютного курса который отражает цену национальной валюты образующиеся на основе реального валютного курса под воздействием...
34380. Прогнозирование развития рынка ценных бумаг 57 KB
  Cpitl mrket это составная часть финансового рынка на котором осуществляются операции куплипродажи ценных бумаг. Финансовый рынок состоит из: Денежный рынок который в свою очередь состоит из: учётный рынокдоля денежного рынка где осуществляется перераспределение краткосрочных денежных средств между кредитными институтами путем куплипродажи векселей и ценных бумаг. Основа рынка учетные и переучетные операции банков межбанковскийсегмент рынка ссудных капиталов где временно свободные денежные ресурсы кредитных учреждений...
34381. Трудовые ресурсы (ТС), их состав. Рынок труда. Проблема занятости 50.5 KB
  Критериями для выделения из общей численности населения трудовых ресурсов являются границы трудоспособного возраста которые устанавливаются государством и зависят от общественного строя продолжительности жизни людей других социальноэкономических факторов и принятых в связи с этим официальных государственных актов. В состав трудовых ресурсов включаются: трудоспособное население в трудоспособном возрасте; работающие подростки до 16 лет; население старше рабочего возраста принимающее участие в общественном производстве. В зависимости от...
34382. Прогнозирование ТС и их использования. Сводный баланс ТС, его содержание и методика разработки 73.5 KB
  Сводный баланс ТС его содержание и методика разработки Прогнозирование трудовых ресурсов является составной частью процесса разработки демографических прогнозов служащих для решения следующих задач: определение перспективной численности населения и его половозрастной структуры; оценка численности населения трудоспособного возраста основного источника трудовых ресурсов; обоснование перспектив социальноэкономического развития; разработка концепции демографического развития согласованной с концепцией...
34383. Социальная политика. Показатели, характеризующие уровень жизни населения 77.5 KB
  Показатели характеризующие уровень жизни населения Социальная политика государства это комплекс организационных экономических и других мероприятий по улучшению материального благосостояния духовному и физическому развитию населения оказанию поддержки инвалидам и малообеспеченным членам общества. Учитывая комплексный характер определения социальная политика ее обычно расчленяют на следующие составные части: политика доходов населения; социальная защита граждан; развитие системы здравоохранения образования культуры...
34384. Социальные нормы и нормативы. Минимальный потребительский бюджет и минимальная заработная плата 61.5 KB
  Минимальный потребительский бюджет и минимальная заработная плата Переход к рыночной модели хозяйствования неизбежно привносит в жизнь общества хронические болезни капиталистической системы: безработицу резкое имущественное расслоение бедность многочисленных слоев населения. Необходимость проведения активной социальной политики направленной на поддержание уровня жизни населения и обеспечение социальной защиты наиболее нуждающихся граждан обусловливает широкое использование в прогнозировании и планировании социальных нормативов. Это...
34385. Баланс денежных доходов и расходов населения, его роль и методика разработки 72 KB
  Политика доходов была направлена на сохранение в условиях инфляции определенного уровня заработной платы низкооплачиваемым слоям населения и реальной стоимости социальных выплат путем их периодических централизованных повышений или индексаций. Их успешная реализация стала важным этапом в обеспечении устойчивого экономического роста и повышении уровня жизни населения. Реальные денежные доходы населения повысились на 72 их рост по отношению к 1990 г.
34386. Прогнозирование и планирование оплаты труда 66 KB
  Основная цель оплаты труда обеспечить объективно необходимое воспроизводство рабочей силы в соответствии с ее стоимостью и повысить уровень мотивации исполнителей к эффективному труду. Фонд оплаты труда по народному хозяйству это сумма денежных средств предназначенных для распределения между рабочими и служащими в зависимости от количества и качества затраченного труда. Источниками фонда оплаты труда является национальный доход который распределяется на фонд потребления и фонд накопления.
34387. Реальные доходы населения. Методы их прогнозирования 55 KB
  Методы их прогнозирования Важнейшим обобщающим показателем социального развития и уровня жизни населения являются реальные доходы. Основным источником формирования реальных денежных доходов и стимулирования трудовой деятельности являются зарплата повышение производительности труда и эффективности хозяйствования во всех звеньях экономики рост инвестиционного потенциала населения снижение налоговой нагрузки на фонд зарплаты субъектов хозяйствования всех форм собственности что будет способствовать созданию новых рабочих мест...