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

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

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

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

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

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

Найти

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

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

задачами условной оптимизации (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).

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

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

Осер, Франция — 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.