Помощь по Теле2, тарифы, вопросы

В основе метода лежит следующая итерационная модификация формулы

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), где

a - заданный положительный коэффициент;

Ñ f(x k) - градиент целевой функции первого порядка.

Недостатки:

необходимость выбора подходящего значения ;

медленная сходимость к точке минимума ввиду малости f(x k) в окрестности этой точки.

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

Свободен от первого недостатка простейшего градиентного метода, т.к. a k вычисляется путем решения задачи минимизации Ñ f(x k) вдоль направления Ñ f(x k) с помощью одного из методов одномерной оптимизации x k+1 = x k - a k Ñ f(x k).

Данный метод иногда называют методом Коши.

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

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

Общая задача нелинейного программирования без ограничений сводится к следующему: минимизировать f(x), x E n , где f(x) является целевой функцией. При решении этой задачи мы используем методы минимизации, которые приводят к стационарной точке f(x), определяемой уравнением f(x *)=0. Метод сопряженных направлений относится к методам минимизации без ограничений, использующим производные. Задача: минимизировать f(x), x E n , где f(x) является целевой функцией n независимых переменных. Важной особенностью является быстрая сходимость за счет того, что при выборе направления используется матрица Гессе, которая описывает область топологии поверхности отклика. В частности, если целевая функция квадратичная, то можно получить точку минимума не более чем за количество шагов, равное размерности задачи.

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

Метод Ньютона

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

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

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

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), где

a k - параметр, выбираемый таким образом, чтобы f(x k+1) min.

2. Нахождение экстремума функции без ограничения

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

Определение exst. Функция f(x) заданная на интервале (а, в) имеет в точке x * max(min), если эту точку можно окружить таким интервалом (x * -ε, x * +ε), содержащимся в интервале (а, в), что для всех ее точек х, принадлежащих интервалу (x * -ε, x * +ε), выполняется неравенство:

f(x) ≤ f(x *) → для max

f(x) ≥ f(x *) → для min

Это определение не накладывает никаких ограничений на класс функций f(x), что, конечно, очень ценно.

Если ограничится для функций f(x), достаточно распространенным, но все же более узким классом гладких функций (под гладкими функциями мы будем понимать такие функции, которые непрерывны вместе со своими производными на интервале изменения аргумента), то можно воспользоваться теоремой Ферма, которая дает необходимые условия существования exst.

Теорема Ферма. Пусть функция f(x) определена в некотором интервале (а, в) и в точке "с" этого интервала принимает наибольшее (наименьшее) значение. Если существует в этой точке двухсторонняя конечная производная , то существования необходимоexst .

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

* В случае имеет местоmin, а при →max. Наконец, если при х=х 0 , то использование 2-ой производной не помогает и нужно воспользоваться, например, определением exst.

При решении задачи I необходимые условия exst (т.е. теорема Ферма) используется очень часто.

Если уравнение exst имеет вещественные корни, то точки, соответствующие этим корням, являются подозрительными наexst (но не обязательно самыми экстремумами, ибо имеем дело с необходимыми, а не с необходимыми и достаточными условиями). Так, например, в точке перегиба Х п имеет место , однако, как известно, это не экстремум.

Заметим ещё, что:

из необходимых условий нельзя сказать, какой вид экстремума найден max или min: для определения этого нужны дополнительные исследования;

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

Поэтому, когда находят точки подозрительные на exst, их дополнительно исследуют, например, на основе определения exst или 2-ой производной.

Данное учебное пособие подготовлено на основе курса лекций по дисциплине «Нейроинформатика», читавшегося с 1994 года на факультете Информатики и вычислительной техники Красноярского государственного технического университета.

по данному курсу,

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

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

учебный план

задания на лабораторные работы

#AutBody_14DocRoot

#AutBody_15DocRoot

Нейроучебник

#AutBody_16DocRoot

проект стандарта нейрокомпьютера

Данное пособие является электронным и включает в себя программы, необходимые для выполнения лабораторных работ.

Книга:

Разделы на этой странице:

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

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

1. Вычислить_оценку О2
2. О1=О2
3. Вычислить_градиент
4. Оптимизация шага Пустой_указатель Шаг
5. Вычислить_оценку О2
6. Если О1-О2<Точность то переход к шагу 2

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

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

Этот метод работает, как правило, на порядок быстрее методов случайного поиска. Он имеет два параметра - Точность, показывающий, что если изменение оценки за шаг метода меньше чем Точность, то обучение останавливается; Шаг - начальный шаг для оптимизации шага. Заметим, что шаг постоянно изменяется в ходе оптимизации шага.

Рис. 6. Траектории спуска при различных конфигурациях окрестности минимума и разных методах оптимизации.

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

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

kParTan

1. Создать_вектор В1
2. Создать_вектор В2
3. Шаг=1
4. Вычислить_оценку О2
5. Сохранить_вектор В1
6. О1=О2
7. N=0
8. Вычислить_градиент
9. Оптимизация_шага Пустой_указатель Шаг
10. N=N+1
11. Если N 12. Сохранить_вектор В2
13. В2=В2-В1
14. ШагParTan=1
15. Оптимизация шага В2 ШагParTan
16. Вычислить_оценку О2
17. Если О1-О2<Точность то переход к шагу 5

Рис. 7. Метод kParTan

Одним из простейших антиовражных методов является метод kParTan. Идея метода состоит в том, чтобы запомнить начальную точку, затем выполнить k шагов оптимизации по методу наискорейшего спуска, затем сделать шаг оптимизации по направлению из начальной точки в конечную. Описание метода приведено на рис 7. На рис 6в приведен один шаг оптимизации по методу 2ParTan. Видно, что после шага вдоль направления из первой точки в третью траектория спуска привела в минимум. К сожалению, это верно только для двумерного случая. В многомерном случае направление kParTan не ведет прямо в точку минимума, но спуск в этом направлении, как правило, приводит в окрестность минимума меньшего радиуса, чем при еще одном шаге метода наискорейшего спуска (см. рис. 6б). Кроме того, следует отметить, что для выполнения третьего шага не потребовалось вычислять градиент, что экономит время при численной оптимизации.

Вкину немного своего экспириенса:)

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

Идея данного метода в том, что поиск происходит в направлении покоординатного спуска во время новой итерации. Спуск осуществляется постепенно по каждой координате. Количество координат напрямую зависит от количества переменных.
Для демонстрации хода работы данного метода, для начала необходимо взять функцию z = f(x1, x2,…, xn) и выбрать любую точку M0(x10, x20,…, xn0) в n пространстве, которая зависит от числа характеристик функции. Следующим шагом идет фиксация всех точек функции в константу, кроме самой первой. Это делается для того, чтобы поиск многомерной оптимизации свести к решению поиска на определенном отрезке задачу одномерной оптимизации, то есть поиска аргумента x1.
Для нахождения значения данной переменной, необходимо производить спуск по этой координате до новой точки M1(x11, x21,…, xn1). Далее функция дифференцируется и тогда мы можем найти значение новой следующий точки с помощью данного выражения:

После нахождения значения переменной, необходимо повторить итерацию с фиксацией всех аргументов кроме x2 и начать производить спуск по новой координате до следующей новой точке M2(x11,x21,x30…,xn0). Теперь значение новой точки будет происходить по выражению:

И снова итерация с фиксацией будет повторяться до тех пор, пока все аргументы от xi до xn не закончатся. При последней итерации, мы последовательно пройдем по всем возможным координатам, в которых уже найдем локальные минимумы, поэтому целевая функция на последний координате дойдет до глобального минимума. Одним из преимуществ данного метода в том, что в любой момент времени есть возможность прервать спуск и последняя найденная точка будет являться точкой минимума. Это бывает полезно, когда метод уходит в бесконечный цикл и результатом этого поиска можно считать последнюю найденную координату. Однако, целевая установка поиска глобального минимума в области может быть так и не достигнута из-за того, что мы прервали поиск минимума (см. Рисунок 1).

Рисунок 1 – Отмена выполнения покоординатного спуска

Исследование данного метода показали, что каждая найденная вычисляемая точка в пространстве является точкой глобального минимума заданной функции, а функция z = f(x1, x2,…, xn) является выпуклой и дифференцируемой.
Отсюда можно сделать вывод, что функция z = f(x1, x2,…, xn) выпукла и дифференцируема в пространстве, а каждая найденная предельная точка в последовательности M0(x10, x20,…, xn0) будет являться точкой глобального минимума (см. Рисунок 2) данной функции по методу покоординатного спуска.

Рисунок 2 – Локальные точки минимума на оси координат

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

Ход выполнения метода покоординатного спуска происходит по алгоритму описанного в блок схеме (см. Рисунок 3). Итерации выполнения данного метода:
Изначально необходимо ввести несколько параметров: точность Эпсилон, которая должна быть строго положительной, стартовая точка x1 с которой мы начнем выполнение нашего алгоритма и установить Лямбда j;
Следующим шагом будет взять первую стартовую точку x1, после чего происходит решение обычного одномерного уравнения с одной переменной и формула для нахождения минимума будет, где k = 1, j=1:

Теперь после вычисления точки экстремума, необходимо проверить количество аргументов в функции и если j будет меньше n, тогда необходимо повторить предыдущий шаг и переопределить аргумент j = j + 1. При всех иных случаях, переходим к следующему шагу.
Теперь необходимо переопределить переменную x по формуле x (k + 1) = y (n + 1) и попытаться выполнить сходимость функции в заданной точности по выражению:

Теперь от данного выражения зависит нахождение точки экстремума. Если данное выражение истинно, тогда вычисление точки экстремума сводится к x*= xk + 1. Но часто необходимо выполнить дополнительные итерации, зависящие от точности, поэтому значения аргументов будет переопределено y(1) = x(k + 1), а значения индексов j =1, k = k + 1.

Рисунок 3 – Блок схема метода покоординатного спуска

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

Метод Нелдера - Мида

Стоит отметить известность данного алгоритма среди исследователей методов многомерной оптимизации. Метод Нелдера – Мида один из немногих методов, который основанный на концепции последовательной трансформации деформируемого симплекса вокруг точки экстремума и не используют алгоритм движения в сторону глобального минимума.
Данный симплекс является регулярным, а представляется как многогранник с равностоящими вершинами симплекса в N-мерном пространстве. В различных пространствах, симплекс отображается в R2-равносторонний треугольник, а в R3 - правильный тетраэдр.
Как упоминалось выше, алгоритм является развитием метода симплексов Спендли, Хекста и Химсворта, но, в отличие от последнего, допускает использование неправильных симплексов. Чаще всего, под симплексом подразумевается выпуклый многогранник с числом вершин N+1, где N – количество параметров модели в n -мерном пространстве.
Для того, чтобы начать пользоваться данным методом, необходимо определиться с базовой вершиной всех имеющихся множества координат с помощью выражения:

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

Где xc - центр тяжести (см. Рисунок 1).

Рисунок 1 – Отражение через центр тяжести

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

Алгоритм Нелдера – Мида так же использует эти функции работы с симплексом по следующим формулам:

Функция отражения через центр тяжести симплекса высчитывается по следующему выражению:

Данное отражение выполняется строго в сторону точки экстремума и только через центр тяжести (см. Рисунок 2).

Рисунок 2 – Отражение симплекса происходит через центр тяжести

Функция сжатия вовнутрь симплекса высчитывается по следующему выражению:

Для того, чтобы провести сжатие, необходимо определить точку с наименьшим значением (см. Рисунок 3).

Рисунок 3 – Сжатие симплекса происходит к наименьшему аргументу.

Функция отражения со сжатием симплекса высчитывается по следующему выражению:

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

Рисунок 4 - Отражение со сжатие

Функция отражения с растяжением симплекса (см. Рисунок 5) происходит с использованием двух функций – это отражение через центр тяжести и растяжение через наибольшее значение.

Рисунок 5 - Отражение с растяжением.

Чтобы продемонстрировать работу метода Нелдера – Мида, необходимо обратиться к блок схеме алгоритма (см. Рисунок 6).
Первостепенно, как и в предыдущих примерах, нужно задать параметр искаженности ε, которая должна быть строго больше нуля, а также задать необходмые параметры для вычисления α, β и a. Это нужно будет для вычисления функции f(x0), а также для построения самого симплекса.

Рисунок 6 - Первая часть метода Нелдера - Мида.

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

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

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

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

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

Рисунок 7 - Вторая часть метода Нелдера - Мида.

Вычисленное из предыдущей функции значение необходимо подставить в условие fmin < f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Исследования данного алгоритма показывают, что методы с нерегулярными симплексами (см. Рисунок 8) еще достаточно слабо изучены, но это не мешает им отлично справляться с поставленными задачами.
Более глубокие тесты показывают, что экспериментальным образом можно подобрать наиболее подходящие для задачи параметры функций растяжения, сжатия и отражения, но можно пользоваться общепринятыми параметрами этих функций α = 1/2, β = 2, γ = 2 или α = 1/4, β = 5/2, γ = 2. Поэтому, перед тем как отбрасывать данный метод для решения поставленной задачи, необходимо понимать, что для каждого нового поиска безусловного экстремума, нужно пристально наблюдать за поведением симплекса во время его работы и отмечать нестандартные решения метода.

Рисунок 8 - Процесс нахождения минимума.

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

P.S. Текст полностью мой. Надеюсь кому-нибудь данная информация будет полезной.

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

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

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в фак­торном пространстве изо­бражены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремаль­ное значение функции от­клика у ext .

Если мы выбе­рем какую-либо точку фак­торного пространства в ка­честве исходной (х 1 0 , х 2 0), то наикратчайший путь к вершине функции откли­ка из этой точки – это путь, по кривой, касательная к которой в каждой точке совпадает с нормалью к кривой уровня, т.е. это путь в направлении гради­ента функции отклика.

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и опреде­лить истинное направление градиента.

Согласно методу градиента в какой-то части факторного пространства выбирается исходная точка (исходные уровни) х 1 0 , х 2 0 . Относительно этих исходных уровней строится сим­метричный двухуровневый план эксперимента. Причем интер­вал варьирования выбирается настолько малым, чтобы ли­нейная модель оказалась адекватной. Известно, что любая кривая на достаточно малом участке может быть аппрокси­мирована линейной моделью.

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

и проверяется ее адекватность.

Если для выбранного интервала варьирования линейная мо­дель оказалась адекватной, то может быть определено на­правление градиента:

Таким образом, направление градиента функции отклика определяется значениями коэффициентов регрессии. Это означает, что мы будем двигаться в направлении градиента, если из точки с координатами ( ) перейдем в точку с координатами:

где m – положительное число, определяющее величину шага в на­правлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав ве­личину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .

Затем делаем шаг в направлении градиента, т.е. осу­ществляем опыт в точке с координатами . Если значе­ние функции отклика возросло по сравнению с ее значением в исходном уровне, делаем еще шаг в направлении градиен­та, т.е. осуществляем опыт в точке с координатами:

Движение по градиенту продолжаем до тех пор, пока функция отклика не начнет уменьшаться. На рис. 4.3 движение по градиенту соответствует прямой, вы­ходящей из точки (х 1 0 , х 2 0). Она постепенно отклоняется от истинного направления градиента, показанного штриховой линией, вследствие нелинейности функции отклика.

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

Построив новую линейную модель , осуществляют регрессионный анализ. Если при этом провер­ка значимости факторов показывает, что хоть один коэф

фи­циент , значит, область экстремума функции откли­ка (область оптимума) еще не достигнута. Определяется новое направление градиента и начинается движение к обла­сти оптимума.

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

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

1) исходные уровни факторов (х j 0) следует выбирать воз­можно ближе к точке оптимума, если есть какая-то априор­ная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значе­ние интервала варьирования, при котором функция отклика остается значимой;

3) значение шага (т ) при движении по градиенту выбирают таким образом, чтобы наибольшее из произведений не превышало разности верхнего и нижнего уровней факто­ров в нормированном виде

.

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

Метод Гаусса-Зейделя

Метод заключается в поочерёдном нахождении частных экстремумов целевой функции по каждому фактору. При этом на каждом этапе стабилизируют (k-1) факторов и варьируют только один i-ый фактор

Порядок расчёта: в локальной области факторного пространства на основании предварительных опытов выбирают точку, соответствующую наилучшему результату процесса, и из неё начинают движение к оптимуму. Шаг движения по каждому фактору задаётся исследователем. Вначале фиксируют все факторы на одном уровне и изменяют один фактор до тех пор, пока будет увеличение (уменьшение) функции отклика (Y), затем изменяют другой фактор при стабилизации остальных и т. д. до тех пор пока не получат желаемый результат (Y). Главное правильно выбрать шаг движения по каждому фактору.

Этот способ наиболее прост, нагляден, но движение к оптимуму длительно и метод редко приводит в оптимальную точку. В настоящее время он иногда применяется при машинном эксперименте.

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

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

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

Метод градиента (обычный) осуществляется по следующей схеме:

а) выбирают базовую точку;

б) выбирают шаги движения по каждому фактору;

в) определяют координаты пробных точек;

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

д) по результатам опытов вычисляют оценки составляющих вектор-градиента в т. М для каждого i-го фактора:

где H i -шаг движения по X i .

X i – координаты предыдущей рабочей точки.

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

Достоинства метода: простота, более высокая скорость движения к оптимуму.

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

а) Метод крутого восхождения (Бокса - Уилсона).

б) Принятие решений после крутого восхождения.

в) Симплексный метод оптимизации.

г) Достоинства и недостатки методов.

5.7.3 Метод крутого восхождения (Бокса- Уилсона)

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

Метод крутого восхождения предполагает движение к оптимуму по градиенту.

Где i,j,k-единичные векторы в направлении соответствующих координатных осей.

Порядок расчёта .

Исходными данными является математическая модель процесса, полученная любым способом (ПФЭ, ДФЭ и т.д.).

Расчеты проводят в следующем порядке:

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

где x i -кодированное значение переменной x i ;

X i - натуральное значение переменной x i ;

X i Ц -центральный уровень фактора в натуральном виде;

l i -интервал варьирования фактора x i в натуральном виде.

б) вычисляют шаги движения к оптимуму по каждому фактору.

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

B i *.l I ,

Затем выбирают из полученных произведений максимальное по модулю,а соответствующий этому произведению фактор принимают за базовый фактор(B a l a). Для базового фактора следует установить шаг движения, который рекомендуется задавать меньшим или равным интервалу варьирования базового фактоpa

Знак шага движения l a ’ должен совпадать со знаком коэффициента уравнения регрессии, соответствующего базовому фактору (B a). Величина шагов для других факторов вычисляется пропорционально базовому по формуле:

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

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

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

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

Если Y® max X i =X i ц +gl i ` ’

если Y® min .X i =X i ц -gl i ` . (5.36)