Модели и постановки задач оптимизации в различных предметных областях.

Для применения теории оптимизации к решению конкретных задачи нужно выполнить определённую последовательность действий, которая называется постановкой задачи оптимизации. Она включает этапы:

1. установление границ подлежащей оптимизации системы;

2. выбор количественного критерия, позволяющего выявить наилучший вариант (характеристического критерия);

3. определение внутрисистемных переменных, через которые выражается характеристический критерий;

4. построение модели, которая описывает взаимосвязь внутрисистемных переменных.

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

Укрупненно можно выделить следующие методы:

- классический анализ (включая метод множителей Лагранжа);

- линейное программирование;

- динамическое программирование;

- дискретное программирование;

- нелинейное программирование;

- стохастическое программирование.

 

Методы минимизации функций одной переменной.

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

найти min f(x)=f(x*), (1.1)

a£x£b

 

где x*-искомая точка минимума на [a, b].

Заметим, что

max f(x)= min f(-x), (1.2)

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

Методы и алгоритмы одномерной минимизации занимают важное место в теории оптимизации в связи с тем, что:

q в инженерной практике достаточно часто встречаются самостоятельные задачи одномерной минимизации;

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

Методы исключения интервалов.

Метод деления пополам. Изучаемые в данном разделе методы одномерного поиска можно применять только для унимодальных функций. В связи с этим алгоритм одномерного поиска включат в себя две основные части: алгоритм установления границ интервала унимодальности [a, b] и алгоритм локализации точки минимума.

Для установления границ интервала унимодальности [a, b] обычно используют эвристические процедуры, в которых выбираются некоторые пробные точки функции f, а затем, путем сравнения значений f находится точка, в которой функция начинает возрастать.

Метод золотого сечения.

Полиномиальная аппроксимация

Квадратичная аппроксимация. Основная идея методов аппроксимации заключается в том, что исходная функция f(x) описывается в виде некоторого полинома fa(x), достаточно хорошо приближающего исходную функцию. Затем ищется точка минимума x* полинома fa(x), которая является оценкой истинной точки минимума. Ясно, что точность такой оценки определяется тем, насколько хорошо подобрана аппроксимирующая функция.

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

Методы с использованием производных

Метод Ньютона-Рафсона. Все методы, рассмотренные в предыдущем разделе основываются на предположениях об унимодальности и в ряде случаев о непрерывности исследуемой целевой функции. Видимо, мы можем предположить, что если в дополнение к условию непрерывности ввести требование дифференцируемости функции, то эффективность поисковых процедур может быть существенно повышена за счет привлечения дополнительной информации о производной в пробных точках. Конечно, наиболее простым способом минимизации является аналитическое решение уравнения f’(x)=0. Но в случае сложной f(x) непосредственное получение такого решения бывает затруднительным, и поэтому нужно применять некоторые поисковые схемы.

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

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

 

 

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

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

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

методы нулевого порядка используют только значения функции f(x); например, поиск по многраннику (симплексу), или S²-метод; метод поиска Хука-Дживса; метод сопряженных направлений Пауэлла. Первые два из перечисленных методов относятся к категории эвристических, хотя и реализуют принципиально различающиеся стратегии поиска. Алгоритм Хука-Дживса

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

Метод Пауэлла основан на теоретических результатах и для квадратичных форм сходится за конечное число итераций

методы первого порядка используют значения первой производной функции f’(x); Оптимальный градиентный метод (Указанные методы также носят итеративный (или шаговый) характер, так как компоненты градиента оказываются нелинейными функциями управляемых переменных)., Метод Ньютона, методы сопряженных градиентов, Метод Дэвидона-Флетчера-Пауэлла (метод ДФП) методы переменной метрики или квазиньютоновскими методами,

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

Еще одним методом минимизации является Метод циклического покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениям x₁ и x₂.

УСЛОВНАЯ НЕЛИНЕЙНАЯ МИНИМИЗАЦИЯ МНОГОМЕРНЫХ ФУНКЦИЙ: Метод множителей Лагранжа и его модификация

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

Прямой метод минимизации

Методы штрафных функций

Предполагается, что для вектора x*, являющегося решением этой задачи, известно некоторое начальное приближение x⁰ возможно и недопустимое, т.е. неудовлетворяющее ограничениям исходной постановки. С помощью рассматриваемых далее методов в пространстве переменных находится конечная последовательность точек x^k, k=1,2, …,К, которая начинается в точке x⁰ и заканчивается точкой x^K, дающей наилучшее приближение к искомой x* среди всех точек найденной последовательности. В качестве каждой x^k, k=1,2, …,К находятся стационарные точки так называемой штрафной функции, которая играет роль целевой функции вспомогательной задачи безусловной минимизации. С помощью штрафной функции исходная задача условной минимизации преобразуется в задачу безусловной минимизации, которая и является k-й подзадачей, решение которой дает соответствующую стационарную точку x^k. Конкретные способы преобразования исходной (условной) задачи во вспомогательную (безусловную) определяются видом штрафной функции.

Способ преобразования исходной условной задачи в безусловную определяется видом штрафной функциии. Методы штрафной функции можно классифицировать по способу учета ограничений-неравенств, поскольку ограничения-равенства учитываются во всех методах более или менее одинаково. В зависимости от того, являются ли точки последовательности x*^(k) допустимыми или нет, говорят о методах внутренней или внешней точки соответственно. Если x*^(k) содержит точки обоих типов, метод называют смешанным.