Исследование систем оптимизации ЭВМ. Этапы процесса решения оптимизационных задач

Министерство образования Российской Федерации Волгоградский государственный технический университет Кафедра «ЭВМ и системы» ИССЛЕДОВАНИЕ СИСТЕМ ОПТИМИЗАЦИИ ЭВМ И СИСТЕМ Методические указания к практическим занятиям по курсу «Методы оптимизации» Волгоград 2007 Исследование систем оптимизации ЭВМ и С: Методические указания к практическим занятиям по курсу «Методы оптимизации» / Сост. Коптелова И. А., Коптелов Е. В.; ВолгГТУ. – Волгоград, 2007. – 28 с. В методических указаниях содержатся сведения, необходимые для изучения студентами методов одномерной и многомерной оптимизации. Приведены подробные алгоритмы, примеры решения задач и варианты заданий к практическим занятиям. Предназначены для студентов, обучающихся по направлению «Информатика и вычислительная техника» и специальности «Вычислительные машины, комплексы, системы и сети» всех форм обучения. 1. МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ ОПТИМИЗАЦИИ Каждый человек время от времени оказывается в ситуации, когда достижение некоторого результата может быть осуществлено не единственным способом. В таких случаях приходится отыскивать наилучший способ. Однако в различных ситуациях наилучшими могут быть совершенно разные решения. Все зависит от выбранного или заданного критерия. Этапы процесса решения оптимизационных задач На практике оказывается, что в большинстве случаев понятие «наилучший» может быть выражено количественными критериями – минимум затрат, минимум отклонений от нормы, максимум скорости, прибыли и т. д. Поэтому возможна постановка математических задач отыскания оптимального (optimum - наилучший) результата, так как принципиальных различий в отыскании наименьшего или наибольшего значения нет. Задачи на отыскание оптимального решения называются оптимизационными задачами. Оптимальный результат, как правило, находится не сразу, а в результате процесса, называемого процессом оптимизации. Применяемые в процессе оптимизации методы получили название методов оптимизации. В простейших случаях мы сразу переводим условие задачи на математический язык и получаем ее математическую формулировку. Однако на практике процесс формализации задачи достаточно сложен. Пусть, например, требуется распределить различные виды обрабатываемых в данном цехе изделий между различными типами оборудования таким образом, чтобы обеспечить выполнение заданного плана выпуска изделий каждого вида с минимальными затратами. Весь процесс решения задачи представляется в виде следующих этапов: 1. Изучение объекта. При этом требуется понять происходящий процесс, определить необходимые параметры (например, число различных и взаимозаменяемых типов оборудования, его производительность по обработке каждого вида изделий и т. д). 2. Описательное моделирование – установление и словесная фиксация основных связей и зависимостей между характеристиками процесса с точки зрения оптимизируемого критерия. 3. Математическое моделирование – перевод описательной модели на формальный математический язык. Все условия записываются в виде соответствующей системы ограничений (уравнения и неравенства). Любое решение этой системы называется допустимым решением. Критерий записывается в виде функции, которую обычно называют целевой. Решение задачи оптимизации состоит в отыскании на множестве решений системы ограничений максимального или минимального значения целевой функции. 4. Выбор метода решения задачи. Так как задача уже записана в математической форме, ее конкретное содержание уже не важно. Совершенно разные по содержанию задачи часто приводятся к одной и той же формальной записи. Поэтому при выборе метода решения главное внимание обращается не на содержание задачи, а на полученную математическую структуру. Иногда специфика задачи может потребовать какой-либо модификации уже известного метода или даже разработки нового. 5. Выбор или написание программы для решения задачи на ЭВМ. Подавляющая часть задач, возникающих на практике из-за большого числа переменных и зависимостей между ними, могут быть решены в разумные сроки с помощью ЭВМ. Для решения задачи на ЭВМ прежде всего следует составить (или использовать уже готовую, если аналогичная задача уже решалась на ЭВМ) программу, реализующую выбранный метод решения. 6. Решение задачи на ЭВМ. Вся необходимая информация для решения задачи на ЭВМ вводится вместе с программой. В соответствии с программой решения ЭВМ производит необходимую обработку введенной числовой информации, получает соответствующие результаты, которые выдает человеку в удобной для него форме. 7. Анализ полученного решения. Анализ решения бывает двух видов: формальный (математический), когда проверяется соответствие полученного решения построенной математической модели (в случае несоответствия проверяются программа, исходные данные, работа ЭВМ и т. д.), и содержательной (экономический, технологический и т. п.), когда проверяется соответствие полученного решения тому объекту, который моделировался. В результате такого анализа в модель могут быть внесены изменения или уточнения, после чего весь процесс повторяется. модель считается построенной и завершенной, если она с достаточной точностью характеризует деятельность объекта по выбранному критерию. Только после этого модель может быть использована для расчетов. Применение методов оптимизации в инженерной практике Методы оптимизации эффективно применяются в самых различных областях человеческой деятельности. Особенно значительные успехи достигнуты при проектировании и анализе больших технических систем. Ускоренные темпы внедрения теоретических разработок в инженерную практику в существенной степени обусловлены широким распространением и интенсивным совершенствованием средств вычислительной техники. В настоящее время для инженера знание методов оптимизации является столь же необходимым, как знание основ математического анализа, физики, химии, теории сопротивления материалов, радиоэлектроники и ряда других дисциплин, ставших традиционными. В наиболее общем смысле теория оптимизации представляет собой совокупность фундаментальных математических результатов и численных методов, ориентированных на нахождение и идентификацию наилучших вариантов из множества альтернатив и позволяющих избежать полного перебора и оценивания возможных вариантов. Процесс оптимизации лежит в основе всей инженерной деятельности, поскольку классические функции инженера заключаются в том, чтобы, с одной стороны, проектировать новые, более эффективные и менее дорогостоящие технические системы и, с другой стороны, разрабатывать методы повышения качества функционирования существующих систем. Эффективность оптимизационных методов, позволяющих осуществить выбор наилучшего варианта без непосредственной проверки всех возможных вариантов, тесно связана с широким использованием достижений в области математики путем реализации итеративных вычислительных схем, опирающихся на строго обоснованные логические процедуры и алгоритмы, на базе применения вычислительной техники. Поэтому для изложения методологических основ оптимизации требуется привлечение важнейших результатов теории матриц, элементов линейной алгебры и дифференциального исчисления, а также положений математического анализа. Поскольку размерность инженерных задач, как правило, достаточно велика, а расчеты в соответствии с алгоритмами оптимизации требуют значительных затрат времени, оптимизационные методы ориентированы главным образом на реализацию с помощью ЭВМ. Теория оптимизации находит эффективное применение во всех направлениях инженерной деятельности, и в первую очередь в следующих четырех областях: 1) проектирование систем и их составных частей; 2) планирование и анализ функционирования существующих систем; 3) инженерный анализ и обработка информации; 4) управление динамическими системами. Оптимизация – всего лишь один этап в процессе формирования оптимального проекта или условий эффективного функционирования системы. Указанный процесс (рисунок 1) является циклическим и включает синтез (определение) структуры системы, построение модели, оптимизацию параметров модели и анализ полученного решения. При этом оптимальный проект или новый план функционирования системы строится на основе решения серии оптимизационных задач, способствующего дальнейшему совершенствованию структуры системы. Рисунок 1. Этапы процесса инженерного проектирования Структура оптимизационных задач Несмотря на то, что прикладные задачи относятся к совершенно разным областям инженерной практики и представляют различные системы, они имеют общую форму. Все эти задачи можно классифицировать как задачи минимизации вещественнозначной функции f(x) N-мерного векторного аргумента x=(x1, x2, …, xn), компоненты которого удовлетворяют системе уравнений hk(x)=0, набору неравенств gj(x)0, а также ограничены сверху и снизу, т. е. . Функцию f(x) будем называть целевой функцией, уравнения hk(x)=0 – ограничениями в виде равенств, а неравенства gj(x)0 – ограничениями в виде неравенств. При этом предполагается, что все фигурирующие в задаче функции являются вещественнозначными, а число ограничений конечно. Задача общего вида: минимизировать f(x) при ограничениях hk(x)=0, k=1, …, K, gj(x)0, j=1, …, J, , i=1, …,N называется задачей оптимизации с ограничениями или задачей условной оптимизации. Задача, в которой нет ограничений, т. е. J = K = 0 и , i = 1, …, N, называется оптимизационной задачей без ограничений или задачей безусловной оптимизации. Задачи оптимизации можно классифицировать в соответствии с видом функции f, hk, gj и размерностью вектора x. Задачи без ограничений, в которых x представляет собой одномерный вектор, называются задачами с одной переменной и составляют простейший, но вместе с тем весьма важный подкласс оптимизационных задач. Задачи условной оптимизации, в которых функции hk и gj являются линейными, носят название задач с линейными ограничениями. В таких задачах целевые функции могут быть либо линейными, либо нелинейными. Задачи, которые содержат только линейные функции вектора непрерывных переменных x, называются задачами линейного программирования; в задачах целочисленного программирования компоненты вектора x должны принимать только целые значения. Задачи с нелинейной целевой функцией и линейными ограничениями иногда называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если f(x) – квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если f(x) есть отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т. д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку, специфические особенности тех или иных задач играют важную роль при разработке методов их решения. 2. ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ Метод деления интервала пополам Методы поиска, которые позволяют определить оптимум функции одной переменной путем последовательного исключения подынтервалов и, следовательно, путем уменьшения интервала, носят название методов исключения интервалов. Унимодальность функций является исключительно важным свойством. Фактически все одномерные методы поиска, используемые на практике, основаны на предположении, что исследуемая функция в допустимой области, по крайней мере, обладает свойством унимодальности. Полезность этого свойства определяется тем фактом, что для унимодальной функции f(x) сравнение значений f(x) в двух различных точках интервала поиска позволяет определить, в каком из заданных двумя указанными точками подынтервалов точка оптимума отсутствует. Теорема. Пусть функция f унимодальна на замкнутом интервале axb, а ее минимум достигается в точке x*. Рассмотрим точки x1 и x2, расположенные в интервале таким образом, что af(x2), то точка минимума f(x) не лежит в интервале (a, x1), т.е. x* (x1, b) (рисунок 2). 2. Если f(x1)f(105)=25 f(127,5)=756,25>f(105) Таким образом исключаются интервалы (60; 82,5) и (127,5;150). Длина интервала уменьшается с 90 до 45. Итерация 2 a=82,5, b=127,5, xm=105 L=127,5-82,5=45 x1=82,5+(45/4)=93,75 x2=127,5-(45/4)=116,25 f(93,75)=39,06>f(105)=25 f(116,25)=264,06>f(105) Таким образом, интервал неопределенности равен (93,75; 116,25). Итерация 3 a=93,75, b=116,25, xm=105 L=116,25-93,75=22,5 x1=99,375, x2=110,625 f(x1)=0,39 f(w2) и w3w2, интервал ww2 исключается. В результате получен следующий интервал неопределенности: 0,382w0,618 для переменной w, или 94,4x115,6 для переменной x. Метод последовательного оценивания с использованием квадратичной аппроксимации Простейшим вариантом полиномиальной интерполяции является квадратичная аппроксимация, которая основана на том факте, что функция, принимающая минимальное значение во внутренней точке интервала, должна быть, по крайней мере, квадратичной. Если же функция линейная, то ее оптимальное значение может достигаться только в одной из двух граничных точек интервала. Таким образом, при реализации метода оценивания с использованием квадратичной аппроксимации предполагается, что в ограниченном интервале можно аппроксимировать функцию квадратичным полиномом, а затем использовать построенную аппроксимационную схему для оценивания координаты точки истинного минимума функции. Если задана последовательность точек x1, x2, x3 и известны соответствующие этим точкам значения функции f1, f2, f3, то можно определить постоянные величины a0, a1, a2 таким образом, что значения квадратичной функции q(x)=a0+a1(x-x1)+a2(x-x1)(x-x2) совпадут со значениями f(x) в трех указанных точках. Перейдем к вычислению q(x) в каждой из трех заданных точек. Прежде всего, так как f1=f(x1)=q(x1)=a0 имеем a0=f1. Далее, поскольку f2=f(x2)=q(x2)=f1+a1(x2-x1), получаем a1=(f2-f1)/(x2-x1). При x=x3 f3=f(x3)=q(x3)=f1+(f2-f1)/(x2-x1)+a2(x3-x1)(x3-x2). Решая последнее уравнение относительно a2, получаем a2= Таким образом, по трем заданным точкам и соответствующим значениям функции можно оценить параметры a0, a1, a2 аппроксимирующего полинома с помощью приведенных выше формул. Если точность аппроксимации исследуемой функции в интервале от x1 до x3 с помощью квадратичного полинома оказывается достаточно высокой, то в соответствии с предложенной стратегией поиска построенный полином можно использовать для оценивания координаты точки оптимума. Стационарные точки функции одной переменной определяются путем приравнивания к нулю ее первой производной и последующего нахождения корней полученного таким образом уравнения. В данном случае из уравнения можно получить . Поскольку функция f(x) на рассматриваемом интервале обладает свойством унимодальности, а аппроксимирующий квадратичный полином также является унимодальной функцией, то можно ожидать, что величина окажется приемлемой оценкой координаты точки истинного оптимума x*. Метод, разработанный Пауэллом, основан на последовательном применении процедуры оценивания с использованием квадратичной аппроксимации. Схему алгоритма можно описать следующим образом. Пусть x1 – начальная точка, - выбранная величина шага по оси x. Шаг 1. Вычислить x2=x1+. Шаг 2. Вычислить f(x1) и f(x2). Шаг 3. Если f(x1)> f(x2), положить x3=x1+2. Если f(x1) f(x2), положить x3=x1-. Шаг 4. Вычислить f(x3) и найти Fмин = min, Xмин = точка xi, которая соответствует Fмин, Шаг 5. По трем точкам x1, x2, x3 вычислить , используя формулу для оценивания с помощью аппроксимации. Шаг 6. Проверка на окончание поиска. Является ли разность Fмин - f() достаточно малой? Является ли разность Xмин - достаточно малой? Если оба условия выполняются, закончить поиск. В противном случае перейти к шагу 7. Шаг 7. Выбрать «наилучшую» точку (Xмин или ) и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти к шагу 4. Пример 3. Минимизировать f(x) = 2x2+16/x. Пусть начальная точка x1=1 и длина шага =1. Для проверки на окончание поиска используются следующие параметры сходимости: , Итерация 1 Шаг 1. x2=x1+=2. Шаг 2. f(x1)=18 и f(x2)=16. Шаг 3. f(x1)> f(x2), следовательно, положить x3=1+2=3. Шаг 4. f(x3)=23,33, Fмин=16, Xмин=x2. Шаг 5. Шаг 6. Проверка на окончание поиска: следовательно, продолжаем поиск. Шаг 7. Выбираем как «наилучшую» точку, а x1=1 и x2=2 – как точки, которые ее окружают. Обозначаем эти точки в естественном порядке и переходим к итерации 2, которая начинается с шага 4. Итерация 2 Шаг 4. x1=1, f1=18, x2=1,714, f2=15,210=Fмин, Xмин=x2, x3=2, f3=16. Шаг 5. Шаг 6. Проверка на окончание поиска: Шаг 7. Выбираем как «наилучшую» точку, а x1=1 и x2=1,714 – как точки, которые ее окружают. Итерация 3 Шаг 4. x1=1, f1=18, x2=1,65, f2=15,142=Fмин, Xмин=x2, x3=1,714, f3=15,210. Шаг 5. Шаг 6. Проверка на окончание поиска: Следовательно поиск закончен. Методы с использованием производных Метод Ньютона – Рафсона В рамках схемы данного метода предполагается, что функция f дважды дифференцируема. Работа алгоритма начинается в точке x1, которая представляет начальное приближение координаты стационарной точки, или корня уравнения =0. Затем строится линейная аппроксимация функции в точке x1, и точка, в которой аппроксимирующая линейная функция обращается в ноль, принимается в качестве следующего приближения. Если точка xk принята в качестве текущего приближения к стационарной точке, то линейная функция, аппроксимирующая функцию в точке xk, записывается в виде Приравняв правую часть уравнения нулю, получим следующее приближение: Рисунок 6. Метод Ньютона – Рафсона (сходимость и отсутствие сходимости) Рисунок иллюстрирует основные шаги реализации метода Ньютона. В зависимости от выбора начальной точки и вида функции алгоритм может как сходиться к истинной стационарной точке, так и расходиться, что отражено на рисунке. Если начальная точка расположена правее x0, то получаемые в результате последовательных приближений точки удаляются от стационарной точки z. Пример 4. Минимизировать f(x) = 2x2+16/x. Для того, чтобы определить стационарную точку функции f(x), воспользуемся методом Ньютона – Рафсона, положив x1=1: , Итерация 1 x1=1, =-12, =36, x2=1-(-12/36)=1,33. Итерация 2 x2=1,33, =-3,73, =17,6, x3=1,33-(-3,73/17,6)=1,54. Итерации продолжаются до тех пор, пока не будет выполняться неравенство , где - заранее установленная величина допустимого отклонения. Метод секущих Метод секущих, являющийся комбинацией метода Ньютона и общей схемы исключения интервалов, ориентирован на нахождение корня уравнения =0 в интервале (a, b), если такой корень существует. Предположим, что в процессе поиска стационарной точки функции f(x) в интервале (a, b) обнаружены две точки L и R, в которых знаки производной различны. В этом случае алгоритм метода секущих позволяет аппроксимировать функцию секущей прямой и найти точку, в которой секущая графика пересекает ось абсцисс. Таким образом, следующее приближение к стационарной точке x* определяется по формуле . Если , поиск следует закончить. В противном случае необходимо выбрать одну из точек L или R таким образом, чтобы знаки производной в этой точке и точке z были различны, а затем повторить основной шаг алгоритма. Например, в ситуации, изображенной на рисунке, в качестве двух следующих точек должны быть выбраны точки z и R. Рисунок 7. Метод секущих Пример 5. Минимизировать f(x) = 2x2+16/x в интервале 1x5. Итерация 1 Шаг 1. R=5, L=1, , . Шаг 2. . Шаг 3. =7,62>0; положить R=2,53. Итерация 2 Шаг 2. . Шаг 3. =3,51>0; положить R=1,94. Итерации продолжаются до тех пор, пока не будет выполняться неравенство . 3. ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ Рассмотрим многомерную задачу безусловной оптимизации, в которой требуется минимизировать f(x), , при отсутствии ограничений на x, где x – вектор управляемых переменных размерности N, f – скалярная целевая функция. Обычно предполагается, что xi (для всех значений i=1,2,3, …, N) могут принимать любые значения, хотя в ряде практических приложений область значений x выбирается в виде дискретного множества. Кроме того, часто оказывается удобным предполагать, что функция f и ее производные существуют и непрерывны всюду, хотя известно, что оптимумы могут достигаться в точках разрыва f или ее градиента Следует напомнить, что функция f может принимать минимальное значение в точке , в которой f или претерпевают разрыв. Методы, ориентированные на решение задач безусловной оптимизации можно разделить на три широких класса в соответствии с типом используемой при реализации того или иного метода информации. 1. Методы прямого поиска, основанные на вычислении только значений целевой функции. 2. Градиентные методы, в которых используются точные значения первых производных f(x). 3. Методы второго порядка, в которых наряду с первыми производными используются вторые производные функции f(x). 3.1 Критерии оптимальности Критерии оптимальности необходимы для распознавания решений и, кроме того, составляют основу большинства используемых методов поиска решений. Рассмотрим разложение Тейлора для функции нескольких переменных , где - точка разложения из пространства RN; - величина изменения x; - N-мерный вектор-столбец первых производных f(x), вычисленных в точке ; - симметрическая матрица порядка NN вторых частных производных f(x), вычисленных в точке . (Эту матрицу часто называют матрицей Гессе. Ее элемент, расположенный на пересечении i-ой строки и j-го столбца, равен .) - сумма всех членов разложения, имеющих порядок по выше второго. Пренебрегая членами высших порядков, определим величину изменения целевой функции f(x), соответствующего произвольному изменению x: . По определению во всех точках из окрестности точки минимума целевая функция принимает значения, которые превышают минимальное, т. е. имеет место неравенство . Точка является точкой глобального минимума, если неравенство выполняется для всех ; такие точки будем обозначать через x**. Если неравенство справедливо лишь в некоторой - окрестности точки , т. е. для всех x, таких, что при заданном >0, то есть точка локального минимума, или x*. Если же , то есть точка максимума (локального или глобального в соответствии с данными выше определениями). Метод поиска Хука – Дживса Шаг 1. Определить: начальную точку x(0), приращение , i=1, 2, 3, …, N, коэффициент уменьшения шага , параметр окончания поиска . Шаг 2. Провести исследующий поиск. Шаг 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением целевой функции)? Да: перейти к шагу 5. Нет: продолжать. Шаг 4. Проверка на окончание поиска. Выполняется ли неравенство ? Да: прекратить поиск; текущая точка аппроксимирует точку оптимума x*. Нет: уменьшить приращение по формуле , i=1, 2, 3, …, N. Перейти к шагу 2. Шаг 5. Провести поиск по образцу: . Шаг 6. Провести исследующий поиск, используя в качестве базовой точки; пусть - полученная в результате точка. Шаг 7. Выполняется ли неравенство ? Да: положить , . Перейти к шагу 5. Нет: перейти к шагу 4. Пример 6. Минимизировать Итерация 1 Исследующий поиск Поиск по образцу Итерация 2 Исследующий поиск Поиск по образцу Итерация 3 Исследующий поиск Поиск по образцу Поиск завершен . Метод Коши В основе простейшего градиентного метода лежит формула , где - заданный параметр. Метод обладает двумя недостатками: во-первых, возникает необходимость выбора подходящего значения , и, во-вторых, методу свойственна медленная сходимость к точке минимума вследствие малости в окрестности этой точки. Таким образом, целесообразно определять значение на каждой итерации . Значение вычисляется путем решения задачи минимизации вдоль направления с помощью того или иного метода одномерного поиска. Рассматриваемый градиентный метод носит название метода наискорейшего спуска, или метода Коши. Поиск вдоль прямой в соответствии с данной формулой обеспечивает более высокую надежность метода Коши по сравнению с простейшим градиентным методом, однако скорость его сходимости при решении ряда практических задач остается недопустимо низкой. Это вполне объяснимо, поскольку изменения переменных непосредственно зависят от величины градиента, которая стремится к нулю в окрестности точки минимума, и отсутствует механизм ускорения движения к точке минимума на последних итерациях. Одно из главных преимуществ метода Коши связано с его устойчивостью. Метод обладает важным свойством, которое заключается в том, что при достаточно малой длине шага итерации обеспечивают выполнение неравенства . С учетом этого свойства заметим, что метод Коши, как правило, позволяет существенно уменьшить значение целевой функции при движении из точек, расположенных на значительных расстояниях от точки минимума, и поэтому часто используется при реализации градиентных методов в качестве начальной процедуры. На примере метода Коши можно продемонстрировать отдельные приемы, которые используются при реализации различных градиентных алгоритмов. Пример 7. Минимизировать Итерация 1 Счет итераций k = 0 Итерация 2 Счет итераций k = 1 Поиск завершен . Метод Ньютона Метод Коши основывается на последовательной линейной аппроксимации целевой функции и требует вычисления значений функции и ее первых производных на каждой итерации. Для того чтобы построить более общую стратегию поиска, следует привлечь информацию о вторых производных целевой функции. Разложим целевую функцию в ряд Тейлора . Отбрасывая все члены разложения третьего порядка и выше, получим квадратичную аппроксимацию f(x): , где - аппроксимирующая функция переменной x, построенная в точке . На основе квадратичной аппроксимации функции f(x) сформируем последовательность итераций таким образом, чтобы во вновь получаемой точке градиент аппроксимирующей функции обращался в нуль. Имеем , откуда . Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле , использование которого демонстрируется на следующем примере. Пример 8. Минимизировать , , . При получаем и следовательно , что совпадает с точным решением. Пример 9. Метод Марквардта Рассматриваемы метод является комбинацией методов Коши и Ньютона, в которой удачно сочетаются положительные свойства обоих методов. Вместе с тем при использовании метода Марквардта требуется информация о значениях вторых производных целевой функции. Было отмечено, что градиент указывает направление наибольшего локального увеличения функции, а движение в направлении, противоположному градиенту, из точки x(0) , расположенной на значительном расстоянии от точки минимума x* , обычно приводит к существенному уменьшению целевой функции. С другой стороны, направления эффективного поиска в окрестности точки минимума определяются по методу Ньютона. Идея объединения методов Коши и Ньютона была предложена в основу алгоритма, разработанного Марквардтом. В соответствии с этим методом направление поиска определяется равенством . При этом , поскольку параметр позволяет не только изменять направление поиска, но и регулировать длину шага. Символом I обозначена единичная матрица, т. е. матрица, все элементы которой равны нулю, за исключением диагональных элементов, равных +1. На начальной стадии поиска параметру приписывается большое значение (например, 104), так что . Таким образом, большим значениям соответствует направление поиска . При уменьшении до нуля s(x) изменяется от направления, противоположного градиенту, до направления, определяемого по методу Ньютона. Если после первого шага получена точка с меньшим значением целевой функции (т. е. ), следует выбрать и реализовать еще один шаг; в противном случае следует положить , где >1, и вновь реализовать предыдущий шаг. Ниже приведены шаги алгоритма. Шаг 1. Задать - начальное приближение к x*; M – максимальное (допустимое) количество итераций; - параметр сходимости. Шаг 2. Положить k=0, =104. Шаг 3. Вычислить компоненты . Шаг 4. Выполняется ли неравенство ? Да: перейти к шагу 11. Нет: перейти к следующему шагу. Шаг 5. Выполняется ли равенство ? Да: перейти к шагу 11. Нет: перейти к следующему шагу. Шаг 6. Вычислить . Шаг 7. Положить . Шаг 8. Выполняется ли равенство ? Да: перейти к шагу 9. Нет: перейти к шагу 10. Шаг 9. Положить и k=k+1. Перейти к шагу 3. Шаг 10. Положить . Перейти к шагу 6. Шаг 11. Вывод результатов и останов. Метод Марквардта характеризуется относительной простотой, свойством убывания целевой функции при переходе от итерации к итерации, высокой скоростью сходимости в окрестности точки минимума x*, а также отсутствием процедуры поиска вдоль прямой. Этот метод широко используется при решении задач, в которых f(x) записывается в виде суммы квадратов, т. е. . ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 1. Реализуйте процедуру одномерного поиска точки оптимума функции в интервале используя метод деления интервала пополам, метод золотого сечения, метод поиска с использованием квадратичной аппроксимации, метод с использованием производных. 2. Найдите точку минимума функции начальная точка x=2 и длина шага . Воспользуйтесь методом оценивания на основе квадратичной аппроксимации (три итерации). 3. Найдите вещественные корни уравнения (с точностью до одного знака после запятой) используя метод Ньютона – Рафсона, метод секущих. 4. В результате экспериментов установлено, что траектория движения космического тела описывается следующим уравнением . Найдите корень уравнения f(x)=0 с помощью любого из методов с использованием производных. 5. Пользуясь любым из методов одномерного поиска, минимизируйте следующие функции с точность до одного знака после запятой: а) в интервале [0;4]; б) в интервале [0;]; в) в интервале [1;100]. 6. Найдите координаты точек минимума функции с точностью до трех десятичных знаков. Воспользуйтесь методом Хука – Дживса при поиске из следующих начальных точек: , , , , . 7. Заданы функция и две первые точки, полученные в процессе поиска минимума функции f: , . Определите направление поиска из точки , пользуясь методом Коши и методом Марквардта (). 8. Проведите три итерации в соответствии с методом Коши и методом Ньютона для минимизации функции при . СПИСОК ИСПОЛЬЗОВАННОЙ Литературы 1. Монахов, В. М. Методы оптимизации: пособие для учителей [Текст] / В. М. Монахов, Э. С. Беляева, Н. Я. Краснер. – М. : Просвещение, 1978. – 175. 2. Партыка, Т. Л. Математические методы: учебник [Текст] / Т. Л. Партыка, И. И. Попов. – М. : ФОРУМ: ИНФРА-М, 2005. – 464 с. 3. Реклейтис, Г. Оптимизация в технике [Текст]: в 2 т. / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел; перевод с англ. - М. : Мир, 1986. – 670 с. 4. Таха, Х. Введение в исследование операций [Текст]: в 2 т. / Х. Таха. – М. : Мир, 1985. ОГЛАВЛЕНИЕ 1. Методологические основы оптимизации 1 Этапы процесса решения оптимизационных задач 1 Применение методов оптимизации в инженерной практике 4 Структура оптимизационных задач 6 1. Функции одной переменной 7 Метод деления интервала пополам 7 Метод золотого сечения 9 Метод последовательного оценивания с использованием квадратичной аппроксимации 12 Методы с использованием производных 15 Метод Ньютона – Рафсона 15 Метод секущих 16 2. Функции нескольких переменных 17 Критерии оптимальности 18 Метод поиска Хука – Дживса 19 Метод Коши 21 Метод Ньютона 23 Метод Марквардта 24 Задачи для самостоятельного решения 26 Список использованной литературы 27