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) является точкой локального минимума, а так как это единственная стационарная точка, то она же является и точкой глобального минимума.

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

 


 

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

25837. Аудит операций на расчетном, валютном и других счетах банка 37.5 KB
  Целью аудиторской проверки операций по расчетному валютному и других счетам в банке является формирование мнения о достоверности бухгалтерской отчетности по разделу Денежные средства и соответствии применяемой методики учета денежных средств на счетах в банке действующим в Российской Федерации нормативным документам. Аудитор при проверке операций по счетам в банке должен учитывать основные нормативные документы регулирующие порядок проведения операций на расчетном валютном и других счетах в банках и бухгалтерский учет этих операций....
25838. Аудит прочих доходов и расходов 58.5 KB
  Целью аудиторской проверки прочих доходов и расходов является формирование мнения о правильности учета прочих доходов и расходов. Задача аудиторской проверки прочих доходов и расходов состоит из следующих вопросов на которые должен ответить аудитор: Бухгалтерский учет прочих доходов и расходов соответствует положениям нормативных актов Данные аналитического и синтетического учета по счету 91 Прочие доходы и расходы соответствуют данным главной книги и баланса Корреспонденция счетов по счету 91 Прочие доходы и расходы составлена в...
25839. Учет расчетов по авансам выданным и полученным 36.5 KB
  Согласно положениям Плана счетов Инструкции по применению Плана счетов бухгалтерский учет сумм полученных и или выданных авансов организуется на балансовых счетах связанных с расчетами за отгруженную продукцию выполненные работы оказанные услуги. Для учета сумм авансовых платежей предварительной оплаты к балансовым счетам открываются обособленные субсчета учета. В частности суммы выданных поставщикам и подрядчикам авансов учитываются обособленно на балансовом счете 60 Расчеты с поставщиками и подрядчиками суммы полученных...
25840. Аудит расчетов по авансам выданным 27.5 KB
  Так например выдавая авансы поставщику предприятие изымает из оборота денежные средства до момента поступления ТМЦ выполнения работ оказания услуг также возрастает вероятность непоступления данных ценностей на предприятие вопреки договору поставки. На счете 61 Расчеты по авансам выданным обобщается информация о расчетах по выданным авансам под поставку продукции либо под выполнение работ а также по оплате продукции и работ принятых от заказчиков по частичной готовности. Суммы выданных авансов а также произведенной оплаты и работ...
25841. Аудит расчетов по претензиям 30 KB
  Можно выделить несколько видов претензий: при выявлении ошибок в счетах поставщиков неправильно указаны тарифы и цены арифметические ошибки и др. Аудитору необходимо проверить: обоснованность своевременность и правильность оформления документов несоблюдение сроков предъявления претензий может быть использовано для сокрытия фактов хищения материальных ценностей так как при отказе в удовлетворении претензий числящиеся суммы списываются на издержки производства; обоснованность претензий предъявляемых к проверяемому предприятию в случае...
25842. Аудит расчетов по совместной деятельности 32.5 KB
  Внесенное товарищами имущество а также произведенная в результате совместной деятельности продукция и полученные от такой деятельности плоды признаются как правило их общей долевой собственностью. Прибыль полученная товарищами в результате их совместной деятельности распределяется пропорционально стоимости вкладов в общее дело если иное не предусмотрено договором или другим соглашением товарищей. Исходя из описанного подхода к организации деятельности простого товарищества в новом Плане счетов поиному решена схема учета операций...
25843. Структура и свойства сталей и чугунов 74 KB
  В углеродистых сталях углерод является основным элементом, определяющим структуру и свойства стали. С увеличением содержания углерода в стали возрастают твердость и предел прочности (НВ, ств), уменьшаются относительное удлинение, относительное сужение и ударная вязкость.
25844. Аудит расчетов с зависимыми (дочерними) обществами 29 KB
  ; организован ли бухгалтерский учет совместной деятельности у одного из участников по доверенности сторон раздельно от его собственного учета раздельный учет раздельный баланс; правильность отражения в учете операций по совместной деятельности; правильность отражения в учете разницы между договорной и балансовой стоимостью имущества переданного в совместную деятельность; правильность распределения прибыли и начислений а также уплаты налогов по результатам совместной деятельности. Проверяя учет внутрихозяйственных расчетов счет 79...
25845. Аудит расчетов с органами социального страхования и обеспечения, внебюджетными фондами 28 KB
  Основными задачами проверки расчетов по социальному страхованию и обеспечению является установление правильности начисления сумм платежей своевременности взносов перечислений причитающихся сумм правильность отражения в бухгалтерском учете этих операция и составления отчетности. Исходя из вышеизложенного необходимо проверить: правильность определения фонда оплаты труда для начисления страховых взносов; правильность применения тарифов страховых взносов; своевременность и обоснованность начисления пособий пенсий и т. выплачиваемых из средств...