Численные методы оптимизации

Примеры алгоритмов и процедур

переменных и обычно включает условия, которые характеризуют их приемлемые значения.

Эти условия называют ограничениями задачи. Еще одной обязательной компонентой описания является скалярная мера «качества», именуемая целевой функцией и зависящая каким-то образом от переменных.
Решение оптимизационной задачи — это приемлемый набор значений переменных, которому отвечает оптимальное значение целевой функции. Под оптимальностью обычно понимают максимальность или минимальность; например, речь может идти о максимизации прибыли или минимизации массы.

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

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

проблем математики, системного анализа, техники, экономики, медицины и статистики. В

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

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

задач. В качестве такой формы мы будем использовать следующую:

Найти

при ограничениях

к стандартному виду. Даже те задачи, которые сами по себе

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

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

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

непрерывными задачами условной оптимизации (NCP).
Ставятся они следующим образом:

Задача

NCP. Найти

при ограничениях

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

Примечание. NCP - Nonlinear Continuous Problem

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

оптимизационных задач

выясним, какими свойствами оно обладает.
Мы будем называть решением NCP точку

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

обозначено
множество

допустимых точек, содержащихся в -окрестности х*.
Определение А. Точка х* является точкой сильного локального
минимума в задаче NCP, если существует число , такое, что
AI. для всех .

Заметим, что под это определение подпадает, в частности, особый случай, когда состоит из единственной точки х*.
Определение В. Точка х* является точкой слабого локального
минимума в задаче NCP, если существует число , такое, что
BI. F(х*) ≤ F (у) для всех ;
В2. х* не удовлетворяет определению сильного локального мини-
мума.

минимума, если в любой ее окрестности найдется допустимая точка с

меньшим значением F.
Определение решения задачи NCP как точки локального минимума на первый взгляд может показаться довольно искусственным — ведь ясно, что наибольший интерес, как правило, представляет
глобальный минимум, т. е. точка, в которой значение целевой функции не хуже, чем в любой допустимой, а не только в близлежащих.
Однако если мы хотим называть рассматриваемые в дальнейшем процедуры методами решения задач NCP, то решение надо определять именно так, поскольку все они являются методами локальной минимизации. Конечно, с их помощью можно искать и точки глобальных минимумов, но, за исключением ряда специальных случаев, когда локальное решение автоматически оказывается глобальным, успеха здесь гарантировать нельзя. Что же касается других методов, которые надежно сходились бы к точкам глобальных минимумов в мало-мальски интересных многоэкстремальных задачах, то их просто не существует.
Последнее, впрочем, не должно удручать практиков, поскольку для большинства прикладных задач удовлетворительные решения все-таки находятся.

Классификация оптимизационных задач

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

дважды непрерывно дифференцируема и х*— точка ее локального минимума, то должны выполняться следующие соотношения:

Необходимые условия минимума в одномерной задаче без ограничений
AI. f'(x*)=0.
А2. f‘’(х*)≥0.

необходимым условием оптимальности первого порядка. Это условие касается только первой

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

Достаточные условия минимума в одномерной задаче без ограничений
Bl. f' (х*)=0.
В2. f’’(x*)>0.

БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ

определённое значение этой функции на заданном отрезке, отвечающее критерию поиска

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

Функции одной переменной

,

Таким образом:

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

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

Предположим, что мы ищем максимум функции f(x), и что нам известно, что максимум лежит между A и B. Чтобы алгоритм был применим, должно существовать некоторое значение x, такое что

для всех a,b, для которых A ≤ a < b ≤ x, выполняется f(a) < f(b), и
для всех a,b, для которых x ≤ a < b ≤ B, выполняется f(a) > f(b).

right are the current bounds; the maximum is between them

if (right-left < absolutePrecision)
return (left+right)/2
leftThird := (left*2+right)/3
rightThird := (left+right*2)/3
if (f(leftThird) < f(rightThird))
return ternarySearch(f, leftThird, right, absolutePrecision)
else
return ternarySearch(f, left, rightThird, absolutePrecision)
end

Алгоритм: обращение к рекурсивной функции

закрашены области притяжения для разных корней. Более тёмные области соответствуют

большему числу итераций

может быть применён и для нахождения нуля функции комплексного переменного.

При этом процедура остаётся неизменной:

Особый интерес представляет выбор начального приближения. Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал Артура Кейли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры.
Ввиду того, что Ньютон применял свой метод исключительно к полиномам, фракталы, образованные в результате такого применения, обрели название фракталов Ньютона или бассейнов Ньютона.

в нем нуждаешься …

Справочник по проблемам оптимизации
Decision Tree for

Optimization Software

http://plato.asu.edu/guide.html

Интернет – наше ВСЕ!

1768, Осер, Франция — 16 мая 1830, Париж), французский математик

и физик.

В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

George Bernard Dantzig (November 8, 1914 – May 13, 2005) was an American mathematician, and the Professor Emeritus of Transportation Sciences and Professor of Operations Research and of Computer Science at Stanford.

линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними

из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

История

Леони́д Вита́льевич Канторо́вич (6 (19) января 1912, Санкт-Петербург — 7 апреля 1986, Москва) — советский математик и экономист, лауреат Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов». Пионер и один из создателей линейного программирования.

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