Размещено на http://www.allbest.ru/

Министерство образования и нaуки Российской Федерации

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУ ВПО «Северо-Кавказский государственный тeхнический унивeрситет»

Факультет информационных технологий и телекоммуникаций

КУРСОВАЯ РАБОТА

Нa тему:

Исследование алгоритмов многомерной оптимизации

Специальность 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Автор дипломного проекта

Ворнавской Евгений Юрьевич

Группа БАС-081

Обозначение курсового проекта

КР-СевКавГТУ-081022-11

Проектировал Е.Ю. Ворнавской

Руководитель работы Р. А. Воронкин

Ставрополь, 2011

Содержание

Введение

1 Методы многомерной оптимизации

2 Градиентный метод

2.1 Метод наискорейшего спуска

2.2 Метод покоординатного спуска

2.3 Метод сопряженных градиентов

2.4 Градиентный спуск

3 Симплекс-метод

3.1 Алгоритм симплекс-метода

3.1 Алгоритм. Начало

3.2 Двухфазный симплекс-метод

3.3 Фазы решения

4 Метод активных множеств

4.1 ASA против CG

4.2 Оптимизатор функций общего вида

Заключение

Список использованных источников

Приложение 1

Введение

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

· Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

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

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

1. детерминированные;

2. случайные (стохастические);

3. комбинированные.

По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методы многомерной оптимизации, о последней как раз и поговорим.

Методы многомерной оптимизации

Дана целевая функция f (x) =?, которая графически представляет собой поверхность параболоида вращения(рис1).

Проведем сечения поверхности равно отстоящими плоскостями, которые параллельны плоскости изменения переменных x1 и x2. Линии этих сечений проецируем на плоскость изменения переменных. Получим концентрические окружности(рис.2). Эти линии называются линиями уровня или линиями постоянных значений. Основная характеристика любой из линий это то, что в любой точке этой линии значение функции постоянно.

Рис.1 Методы многомерной оптимизации. Параболоид вращения

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

Тогда линии уровня будут представлены уравнениями:

 ;

или окружностями с соответствующими радиусами:

;

Рис.2 Методы многомерной оптимизации. Концентрические окружности

Все методы многомерной оптимизации делятся на два класса:

1) Градиентные

2) Безградиентные

Градиентный метод

Градиентом называется вектор равный сумме произведений частных производных на соответствующие орты. Орта - единичный связанный вектор, направленный вдоль координатной оси

Основные свойства градиента:

1) Норма градиента определяет скорость изменения функции в направление градиента.

2) Градиент всегда направлен в сторону наиболее быстрого возрастания функции, т.е. в этом направлении норма вектора градиента максимальна.

Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :

где л^[j] выбирается

· постоянной, в этом случае метод может расходиться;

· дробным шагом, то есть длина шага в процессе спуска делится на некое число;

· наискорейшим спуском:

Метод наискорейшего спуска

Выбирают

,

где все производные вычисляются при , и уменьшают длину шага л^[j] по мере приближения к минимуму функции F.

Для аналитических функций F и малых значений f_i тейлоровское разложение F(л^[j]) позволяет выбрать оптимальную величину шага

(5)

где все производные вычисляются при . Параболическая интерполяция функции F(л^[j]) может оказаться более удобной.

Алгоритм

1. Задаются начальное приближение и точность расчёта

2. Рассчитывают

,

где

3. Проверяют условие останова:

Если

,

то j = j + 1 и переход к шагу 2.

Иначе и останов.

Метод покоординатного спуска

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

Алгоритм

1. Задаются начальное приближение и точность расчёта

2. Рассчитывают

многомерная оптимизация алгоритм программный

, где

3. Проверяют условие останова

Если

, то

и переход к шагу 2.

Иначе и останов.

Метод сопряженных градиентов

Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации -- метода сопряжённых направлений.

Применение метода к квадратичным функциям в определяет минимум за n шагов.

Алгоритм

1. Задаются начальным приближением и погрешностью:

2. Рассчитывают начальное направление:

3. 

Если или , то и останов.

Иначе

если (j + 1) < n, то j = j + 1 и переход к 3;

иначе и переход к 2

Градиентный спуск

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

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



Рис.3 Иллюстрация последовательных приближений к точке экстремума в направлении наискорейшего спуска (красн.) в случае дробного шага. Синим отмечены линии уровня.

Пусть целевая функция имеет вид:

.

И задача оптимизации задана следующим образом:

Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :

где л^[j] выбирается

· постоянной, в этом случае метод может расходиться;

· дробным шагом, т.е. длина шага в процессе спуска делится на некое число;

· наискорейшим спуском:

Алгоритм

1. Задают начальное приближение и точность расчёта

2. Рассчитывают

,

где

3. Проверяют условие остановки:

Если или (выбирают одно из условий), то j = j + 1 и переход к шагу 2.

Иначе и останов.

Пример

Применим градиентный метод к функции

.

Тогда последовательные приближения будут выглядеть так:



Симплекс-метод

Симплекс-метод -- алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом в 1947 году.

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) -- максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку -- требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке.

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

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

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

1. нахождение исходной вершины множества допустимых решений,

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

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

Алгоритм симплекс-метода

Усиленная постановка задачи

Рассмотрим следующую задачу линейного программирования:

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

Здесь x -- переменные из исходного линейного функционала, x_s -- новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c -- коэффициенты исходного линейного функционала, Z -- переменная, которую необходимо максимизировать. Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно : .

Алгоритм

Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:



где c_B -- коэффициенты вектора c соответствующие простым переменным (переменным x_s соответствуют 0), B -- столбцы , соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг.

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

Второй шаг

Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+x_s=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' -- простые, а x ' ' -- непростые переменные на данной итерации. Уравнение Ax+x_s=b можно переписать, как Bx '+Dx ' '=b. Умножим его на B ^{? 1} слева: x' + B ^{? 1}Dx'' = B ^{? 1}b. Таким образом мы выразили простые переменные через непростые, и в выражении B ^{? 1}Ax + B ^{? 1}x_s, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству Z ? c^Tx = 0 равенство , то в полученном равенстве все простые переменные будут иметь нулевой коэффициент -- все простые переменные вида x сократятся, а простые переменные вида x_s не войдут в выражение .

Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение

.

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

Третий шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами -- входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор c_B в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу. x''

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

Двухфазный симплекс-метод

Причины использования

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

Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация. Из изложенного выше не прозвучало отчетливо почему если ограничения отличается от <= не всякий 0-вектор будет допустимым решением. В самом деле пусть i - уравнение имеет вид Ai1X1+...AinXn >=Bi но просто можно изменить знаки записав -Ai1X1- ... AinXn<=-Bi и тем самым привести все неравенства к канонической форме. Это было бы нельзя сделать если бы на вектор B было наложено условие неотрицательности Bi>=0 Но в формулировке выше ограничения вектор B отсутствуют. (это очевидная неточность для теоретической статьи в энциклопедии, где все предпосылки должны формулироваться полно) Если бы все было так просто и легко, непонятно зачем изобретали двухфазный метод... Кроме того по этой же причине классический симплекс метод не годится для решения задачи Min F (точнее не годится в случае положительности всех коэфф целевой функции, т.к. тогда метод не сделает ни одной итерации)

Модификация ограничений

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

· ограничения типа «?» переводятся на равенства созданием дополнительной переменной с коэффициентом «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис.

· ограничения типа «?» дополняются одной переменной с коэффициентом «?1». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1».

· ограничения типа «=» дополняются одной вспомогательной переменной.

Соответственно, будет создано некоторое количество дополнительных и вспомогательных переменных. В исходный базис выбираются дополнительные переменные с коэффициентом «+1» и все вспомогательные. Осторожно: решение, которому соответствует этот базис, не является допустимым.

Различия между дополнительными и вспомогательными переменными

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

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

· вспомогательные переменные сообщают, насколько данное условие далеко от допустимого (относительно конкретного ограничения). Если значение вспомогательной переменной больше нуля, то данное решение не выполняет определённое ограничение, а значит не является допустимым.

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

Фазы решения

После того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как y_i, i?{1, .., k}, то вспомогательную функцию определим, как

.

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

Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:

· оптимальное значение z' больше нуля. Это значит, что как минимум одна из вспомогательных переменных осталась в базисе. В таком случае можно сделать вывод, что допустимых решений данной задачи линейного программирования не существует.

· оптимальное значение z' равно нулю. Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым.

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

Метод активных множеств

ASA-алгоритм

Метод активных множеств (ASA) - это общее название семейства алгоритмов для решения задачи оптимизации с ограничениями вида g_i (x) ? 0. Название метода происходит от используемой классификации ограничений, в соответствии с которой они делятся на активные и неактивные в текущей точке. Ограничение неактивно, если g_i (x) > 0. Если же g_i (x)=0, то ограничение может быть как неактивным, так и активным (в зависимости от выбора множества активных ограничений).

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

Основным достоинством метода является простота его реализации для задачи с ограничениями вида a_i ? x_i ? b_i . Активация ограничений состоит в "замораживании" компонент x, что позволяет использовать практически любой алгоритм оптимизации без ограничений. Итерации метода могут быть очень дешевыми, т.к. отсутствует необходимость строить сложные квадратичные модели функции и ограничений.

Реализация в пакете ALGLIB

В пакете ALGLIB реализована незначительная модификация алгоритма, описанного в 'A new active set algorithm for box constrained optimization' (William W. Hager and Hongchao Zhang). Этот алгоритм чередует итерации нелинейного метода сопряженных градиентов и метода проекции градиента. Первый алгоритм позволяет добиться хорошей сходимости после того, как найдено подходящее множество ограничений. Второй алгоритм используется для активации или деактивации ограничений и позволяет активировать за одну итерацию сразу несколько ограничений. Метод обладает глобальной сходимостью при условии, что grad(f) непрерывен по Липшицу на множестве L = { x : f(x) ? f(x₀ )} Одним из достоинств является сравнительно низкая стоимость итераций, умеренно отличающаяся от стоимости итераций метода сопряженных градиентов без ограничений.

ASA против CG на задачах без ограничений

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

· минимизируемая функция: f(x) = x0 ⁴ + 2·x1 ⁴ + ... + (n+1)·xn ⁴.

· стартовая точка: xs = [10, ..., 10].

· ограничения: -100 ? x_i ? +100, т.е. в минимуме все ограничения неактивны.

· размерность задачи n: в диапазоне 10...100 с шагом 10.

· алгоритмы: CG и ASA

Для тестирования использовался компьютер с процессором Intel Core 2, тактовой частотой 2.4 GHz. По итогам тестирования были получены следующие результаты:



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

Метод Левенберга-Марквардта - хороший выбор, если вам требуется минимизировать функцию вида F=f₁ ²(x₁ ,...,x_n )+ ... +f_m ²(x₁ ,...,x_n ). Алгоритм удачно сочетает в себе метод наискорейшего спуска (т.е. минимизации вдоль градиента) и метод Ньютона (т.е. использование квадратичной модели для ускорения поиска минимума функции). От метода наискорейшего спуска алгоритм позаимствовал стабильность работы, от метода Ньютона - ускоренную сходимость в окрестностях минимума. Ниже приведено обсуждение стандартной реализации алгоритма Левенберга-Марквардта, её недостатков, и улучшенной версии алгоритма, входящей в пакет ALGLIB. Перед чтением этого раздела рекомендуется ознакомиться с описанием алгоритма в Википедии или в Numerical Recipes. Далее мы предполагаем, что читающий понимает общие принципы работы алгоритма Левенберга-Марквардта.

Солвер для нелинейного МНК

Наиболее часто встречающееся применение метода Левенберга-Марквардта - решение задач нелинейной регрессии. В принципе, ничто не мешает вам использовать для этого интерфейс, представляемый субпакетом minlm, и рассмотренный ниже. Однако в пакете ALGLIB существует специальный интерфейс для решения таких задач, входящий в состав субпакета lsfit. Использование специализированного интерфейса обычно более удобно, чем работа с методом оптимизации напрямую.

Оптимизатор функции, представленной в виде суммы квадратов

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

Хотя минимум такой F(x) может быть найден с использованием алгоритмов для функций общего вида (нелинейный CG или L-BFGS), метод Левенберга-Марквардта позволяет использовать знание внутренней структуры для более быстрой сходимости к минимуму.

Оптимизатор функции обшего вида

Последним, менее известным применением метода Левенберга-Марквардта является оптимизация функций общего вида, т.е. функций, которые не разлагаются на сумму квадратов более простых функций. Метод Левенберга-Марквардта имеет смысл применять, если нам доступен Гессиан функции F(x) и мы хотим использовать его для оптимизации.

Выбор режима оптимизации

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

· V (function vector). Функция F(x) представлена, как сумма квадратов. Доступен только вектор функций f. Якобиан вычисляется с использованием численного дифференцирования и метода секущих.

· VJ (vector+Jacobian). Функция F(x) представлена, как сумма квадратов. Доступны вектор функций f и Якобиан J.

· FGH (function+gradient+Hessian). Функция F(x) имеет общий вид. Нам доступны значение F(x), градиент G и Гессиан H.

Буквы в названии схемы являются суффиксом, который дописывается к имени подпрограммы minlmcreate, использующейся для создания оптимизатора. Так, пользователям ALGLIB доступны следующие подпрограммы: minlmcreatev, minlmcreatevj, minlmcreatefgh.

Замечание

Также доступен дополнительный вариант алгоритма, который можно использовать для задач с разреженным Якобианом - VGJ (vector+gradient+Jacobian). В этом режиме алгоритм использует вектор функций, Якобиан, а также градиент функции F(x), равный произведению f ^TJ. Этот режим имеет смысл использовать в сочетании со второй стратегией ускорения сходимости (см. ниже).

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

Следующий шаг. Итак, вы убедились, что пакет ALGLIB (и ваш код для вычисления функции) работают нормально. Как мы уже говорили, оптимизация без использования Якобиана очень проста в реализации, но не очень эффективна. Кроме того, численное дифференцирование не позволяет найти минимум с точностью, существенно превышающей шаг дифференцирования. Если вам требуется хорошее быстродействие (или высокая точность), то имеет смысл реализовать вычисление аналитического Якобиана и перейти к схеме VJ.

Замечание Если вы осуществляете оптимизацию функции общего вида (с использованием Гессиана), то вам придется сразу начинать со схемы FGH и реализовать всё - функцию, градиент, Гессиан.

Выбор критериев остановки

Пакет ALGLIB предлагает пользователям четыре критерия остановки:

· после снижения градиента F(x) до заданной величины

· после совершения достаточно малого шага

· после достаточно малого изменения функции на последнем шаге

· по достижению предельного числа итераций

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

Мы настоятельно рекомендуем использовать первый критерий - малое значение градиента F(x). Этот критерий гарантирует, что алгоритм остановится только в достаточно хорошей точке, независимо от того, насколько медленно или быстро мы к ней приближаемся. Критерии, связанные с изменением шага или функции, менее надежны, так как в некоторых случаях алгоритм может совершать небольшие шаги даже вдали от минимума (например, так иногда бывает при оптимизации без использования Якобиана).

Запуск алгоритма и получение результатов

После того, как объект-оптимизатор создан и настроен, вы можете запустить процесс оптимизации путем вызова функции minlmoptimize. Аргументами функции являются оптимизатор и callbacks, вычисляющие оптимизируемую функцию/градиент. Результат работы может быть получен при помощи вызова minlmresults.

Список использованных источников

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. -- М.: Высш. шк., 1986.

2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. -- М.: Мир, 1985.

3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. -- М.: Энергоатомиздат, 1972.

4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. -- М.: МИФИ, 1982.

5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. -- М.: МИФИ, 1980.

6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. -- М.: Наука, 1970. -- С. 575-576.

7. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. -- 7-е изд. -- М.: «Вильямс», 2007. -- С. 95-141. -- ISBN 0-13-032374-8

8. Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. -- М.: Высшая школа, 1986. -- 319 с. -- ISBN 5-06-002663-9

9. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. -- 2-е изд. -- М.: «Вильямс», 2006. -- С. 1296. -- ISBN 5-8459-0857-4

Приложение1

/ Условие сходимости

bool converge(double *xk, double *xkp)

{

for (int i = 0; i < n; i++)

{

if (fabs(xk[i] - xkp[i]) >= eps)

return false;

}

return true;

}

/*

Ход метода, где:

a[n][n] - Матрица коэффициентов

x[n], p[n] - Текущее и предыдущее решения

*/

do

{

for (int i = 0; i < n; i++)

{

double var = 0;

for (int j = 0; j < n; j++)

if (j != i) var += (a[i][j] * x[j]);

p[i] = x[i];

x[i] = (b[i] - var) / a[i][i];

}

}

while (!converge(x, p))

Заключение

Результатом написания данной курсовой работы стала программная реализация одного из алгоритмов многомерной оптимизации. Данный подход является в своей основе достаточно простым, но, не смотря на это, может давать хорошие результаты в ряде случае. Иногда этот подход применяется как первоначальный этап обработки, иногда для решения более сложных задач. Написанная программа носит демонстративный характер, показывая хорошие результаты. Успешная реализация стала возможна после изучения основных алгоритмов многомерной оптимизации, а так же после изучения языка С++.

Размещено на Allbest.ru