Рефетека.ру / Математика

Реферат: Поиск оптимальных решений

Міністерство освіти і науки України

Національний технічний університет

“ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”


Кафедра “Обчислювальної техніки та програмування”


Реферат з курсу “Введение в численные методы”


Тема: “ПОИСК ОПТИМАЛЬНЫХ РЕШЕНИЙ”


Виконав:

студент групи


Перевірив:


Харків

Содержание


1. Основные понятия оптимизационных задач

2. Итерационные процессы с учетом градиента

3. Функционал для градиентного равенства

4. Функционалы в задачах условной оптимизации

Литература


1.Основные понятия оптимизационных задач


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

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

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


2.Итерационные процессы с учетом градиента


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

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


Поиск оптимальных решений


Это условие соответствует выбору наибольшей скорости убывания функционала, что несложно увидеть, рассмотрев выражение для производной функционала по времени:


Поиск оптимальных решений.


Правую часть можно рассматривать как скалярное произведение двух n-компонентных векторов: вектора градиента


Поиск оптимальных решений


и вектора скорости изменения координат-параметров


Поиск оптимальных решений.

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

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


Поиск оптимальных решений .


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


Поиск оптимальных решений


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

Поиск оптимальных решений,


где Поиск оптимальных решений,Поиск оптимальных решений – вектор-столбец и вектор-строка очередных приращений,

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

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

Поиск оптимальных решений – квадратичная форма с матрицей Гессе,


Поиск оптимальных решений.


Условием достижения локального минимума является положительная определенность квадратичной формы с матрицей Гессе Поиск оптимальных решений в точке остановки, в которой Поиск оптимальных решений. Квадратичная форма положительна тогда и только тогда, когда все главные миноры ее квадратной матрицы, например, матрицы A, положительны:


Поиск оптимальных решений .


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


3. Функционал для градиентного равенства


Функционалом можно считать любую функцию, минимум которой необходимо определить. Вся сложность задачи заключается в ограничениях, накладываемых на переменные и их взаимосвязь. Если ограничения отсутствуют, то говорят о задаче безусловной оптимизации (Пример МНК). К последней сводится и система нелинейных алгебраических уравнений, заданных в неявной форме:


Поиск оптимальных решений


если из системы сконструировать квадратичный функционал такого вида


Поиск оптимальных решений,


где Поиск оптимальных решений – масштабирующие (весовые) коэффициенты.

Подстановка функционала в покомпонентную систему градиентных уравнений приводит к итерационной процедуре с вычислением на каждом шаге следующих выражений:


Поиск оптимальных решений


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

Для нелинейной системы, функционал которой в окрестности точки минимума Поиск оптимальных решений можно аппроксимировать квадратичной функцией с положительно определенной матрицей Гессе, в итерационном выражении


Поиск оптимальных решений


Поиск оптимальных решений и после приравнивания оставшихся слагаемых нулю и сокращения суммы на вектор Поиск оптимальных решений несложно получить соотношение


Поиск оптимальных решений ,


которое приводит к итерационной формуле


Поиск оптимальных решений


идентичной формуле Ньютона в применении к решению системы нелинейных уравнений


Поиск оптимальных решений .


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


4. Функционалы в задачах условной оптимизации


Конструирование выпуклого квадратичного функционала с учетом ограничений рассмотрим для следующей задачи:


Поиск оптимальных решений


В приведенную обобщенную запись задачи минимизации включены:

Минимизируемая функция вектора искомых параметров (функция цели или критериальная функция):


f(x), Поиск оптимальных решений.


Система ограничений типа равенств:


Поиск оптимальных решений


Система ограничений типа неравенств:


Поиск оптимальных решений


Ограничения на изменения самих неизвестных параметров


Поиск оптимальных решений,

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


Поиск оптимальных решений


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


Поиск оптимальных решений, j=1, 2, ... ,J.


Систему неравенств необходимо предварительно преобразовать в систему равенств путем умножения ее на единичную (знаковую) функцию


Поиск оптимальных решений

Поиск оптимальных решений


Теперь система квадратов невязок для неравенств будет представлена в виде квадратов следующих функций


Поиск оптимальных решений.


Аналогично вводятся квадраты невязок и для ограничений на параметры снизу и сверху:

Поиск оптимальных решений


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


Поиск оптимальных решений.

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


Поиск оптимальных решений

Поиск оптимальных решений

Поиск оптимальных решений


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


Литература


Вержбицкий В.М. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. М.: Высш.шк., 2001. - 383с.

Рено Н.Н. АЛГОРИТМЫ ЧИСЛЕННЫХ МЕТОДОВ: МЕТОДИЧЕСКОЕ ПОСОБИЕ ДЛЯ ВУЗОВ. Изд-во: "Книжный дом Университет" (КДУ), 2007. – 24с.

Самарский А.А. Введение в численные методы Учебное пособие для вузов 3-е изд.,стер. ЛАНЬ, 2005. – 288с.

Фаворский А.П., Костомаров Д.П. Вводные лекции по численным методам. Логос, 2006. – 184с.

Шуп Т.Е. Прикладные численные методы в физике и технике. М.: Высш. шк., 1990. - 255с.

Похожие работы:

  1. • Интеллектуальные компьютерные технологии защиты ...
  2. • Решение задачи линейного программирования графическим ...
  3. • Методы исследования операций
  4. • Решение оптимизационных управленческих задач на ...
  5. • Решение оптимизационной задачи линейного программирования
  6. • Решения задачи планирования производства симплекс ...
  7. • Решение задачи оптимального управления
  8. • Решение задач моделирования и оптимизации с помощью ...
  9. • Построение и анализ на чувствительность моделей ...
  10. • Нелинейное программирование
  11. • Анализ и развитие соотношения науки и искусства при ...
  12. • Оптимизация. Методы многомерного поиска
  13. • Оптимальные решения
  14. • Математические методы в решении экономических задач
  15. • Линейное программирование как метод оптимизации
  16. • Интеллектуальные информационные технологии и ...
  17. • Решение многокритериальной задачи линейного программирования
  18. • Имитационное моделирование
  19. • Решение многокритериальной задачи линейного програмирования
Рефетека ру refoteka@gmail.com