Навигация
0 < |min li(x) | << l1(x).
В этом случае поверхность уровня J(x)=const имеют структуру, сильно отличающуюся от сферической. Такие функции J(x) называются овражными. Степень овражности характеризуется числом
S = l1(x) / |min li(x) |, li(x) ╪ 0.
Если собственные значения удовлетворяют неравенствам |lm(x)| <= … <= |lm-r+1(x)| << lm-r(x) << l1(x) , а отношение | lm-r+1(x) | / | lm(x) | невелико, то число r называется размерностью оврага.»
В отличие от локальных моделей, описывающих функцию и ее производные в малой окрестности заданной точки, овражная модель характеризует глобальные свойства функции.
«Конечно, такое разбиение параметров невозможно для любой функции, которую мог бы задать математик. Однако, для функций, встречающихся в практической деятельности человека (здесь имеются в виду разумные задачи физики, техники), такое разбиение, по-видимому, имеет место в очень значительном числе случаев.» [4]
Р.П. Федоренко [5] отмечает, что овражные функции совершенно закономерно возникают при конечно-разностной аппроксимации функционалов вариационных задач оптимального управления, и эти задачи требуют не общих, а узкоспециальных методов решения.
Простейшим примером овражной функции является квадратичная функция (1.2), где А – плохо обусловленная матрица. Число обусловленности симметрической матрицы является важной характеристикой ее свойств и определяется через собственные значения: k(A)=max lA / min l4. Если k(A) велико, то А представляет собой плохо обусловленную матрицу, а задача (1.2) называется плохо обусловленной задачей минимизации. В этом случае f(x) определяет многомерную поверхность прямым (неизогнутым) оврагом.
Для неквадратичных функций вводится обобщение этого определения [6]: обусловленностью точки минимум х называется число
m = lim(sup||x-x’||²(inf||x-x’||²), xÎL, L = {x:f(x)=f(x’)+d}.
Если m велико, функция имеет овражный характер.
Для наглядности опишем овражную функцию в графических терминах. Дно оврага можно представить как русло реки, образующая которого определяет направление течения. Овраг характеризуется крутизной стенок, шириной дна, а также пологостью – степенью понижения дна оврага вдоль образующей. Особо отметим, что дно оврага может быть прямым или извилистым. Дно оврага – это такое подмножество точек, где деление на существующие и несуществующие переменные исчезает, по любому направлению функции изменяется медленно.
Известно, что минимизация овражных функций связана с большими вычислительными трудностями. Поэтому Р.П. Федоренко [5] предлагает при разработке первичной постановки задачи избегать тех способов формализации, которые приводят к появлению овражных функций.
Необходимость в овражной модели появляется тогда, когда исследователь не видит возможности рассматривать минимизируемую функцию как некоторую специальную, менее общую модель. Далеко не всегда практическая задача допускает преобразования, позволяющие перейти к сранительно просто решаемому частному случаю. В общем случае мы имеем овражные функции, которые заслуживают как внимания, так и специального исследования.
1.2 Численные методы в задачах без ограничений
1.2.1 Общая схема методов спуска
Будем рассматривать задачу безусловной минимизации, т.е. задачу минимизации целевой функции f на всем пространстве R. Сущность всех методов приближенного решения этой задачи состоит в построении последовательности точек х1, х2, х3, …, хk, …, монотонно уменьшающих значение целевой функции:
f(x0) >= f(x1) >= f(x3) >= … >= f(xk) >= … (1.3)
Такие методы (алгоритмы) называют методами спуска. При использовании этих методов применяют следующую схему.
Пусть на k-й итерации имеется точка хk. Тогда выбирают направление спуска pk Î R и длину шага вдоль этого направления ak > 0. Следующую точку последовательности вычисляют по формуле:
xk+1 = xk + ak*pk, k = 0, 1, 2, …
Согласно этой формуле, величина продвижения из точки xk в xk+1 зависит от как ak, так и от pk. Однако ak традиционно называют длиной шага.
Формально различают методы спуска отличные друг от друга способом выбора числа ak и вектора pk. Если для определения ak и pk требуется вычислять только значения целевой функции, соответствующий метод называют методом нулевого порядка или методами поиска. Методы первого порядка требуют, кроме того, вычисления первых производных целевой функции. Если же метод предполагает использование и вторых производных, то его называют методом второго порядка и т.д.
С помощью метода нулевого порядка можно решать задачи более широкого класса, чем с помощью методов первого и второго порядков. Однако методы нулевого порядка, как правило, требуют больших вычислений для достижения заданной точности , поскольку использование только значений целевой функции не позволяет достаточно точно определять направление на точку минимума.
Важнейшей характеристикой любых методов спуска является их сходимость. Сходимость здесь понимается в том смысле, что последовательность {xk} должна сходиться к точке глобального (локального) минимума. Однако точки минимума могут составлять целое множество и многие алгоритмы позволяют построить последовательность {xk}, которая сама не является сходящейся, но любая ее сходящаяся последовательность имеет в качестве предельной некоторую точку минимум (см. рис. 3).
В этом случае говорят, что каждая предельная точка последовательности {xk} является точкой минимума. С помощью подобных алгоритмов можно строить последовательности точек, сколь угодно близко приближающихся ко множеству точек минимума.
 |  |
Возможен случай, когда ничего определенного сказать и о сходимости последовательностей нельзя, однако известно, что соответствующая последовательность значений при {f(xk)} сходится к точке минимального значения (локальный или глобальный минимум). Тогда говорят, что последовательность {xk} сходится к минимуму по функции (см. рис. 4). Кроме того, существуют еще более слабые типы сходимости, когда, например, последовательность {xk} (каждая ее последовательность) имеет в качестве предельной стационарную точку (т.е. точку, в которой градиент равен нулевому вектору), являющуюся лишь «подозрительной» на оптимальную.
Как правило, тип сходимости одного и того же метода зависит от конкретного вида целевой функции, т.е. в разных задачах метод может сходится по-разному. При достаточно жестких требованиях к функции f с помощью метода можно строить последовательность, сходящуюся в точке глобального минимума. Если же этот метод применить к функциям, не удовлетворяющим элементарным требованиям, то может быть получена последовательность, сходящаяся только по функции, либо последовательность, не являющаяся сходящейся ни в каком смысле.
Методы спуска в силу условия монотонности 1.3 обычно не приводит к точке локального (глобального) минимума. Отметим, что даже в тех случаях, когда нет сходимости ни в одном смысле, последовательное уменьшение значения целевой функции может представлять практический интерес.
Похожие работы
... сети, позволяющая реализовать автоматическое изменение числа нейронов в зависимости от потребностей задачи, позволяет не только исследовать, но и контролировать процесс воспитания психологической интуиции искусственных нейронных сетей. - Впервые применена выборочная константа Липшица для оценки необходимой для решения конкретной задачи структуры нейронной сети. Практическая значимость ...
... работы со справочной системой работа практикума приостанавливается. 3. Организационно-экономическое обоснование проекта В ходе дипломного проекта был разработан компьютерный лабораторный практикум по курсу «Теория оптимизации и численные методы». В данном разделе рассмотрена экономическая сторона проекта. Рассмотрены следующие вопросы: 1) сетевая модель 2) расчёт ...
0 комментариев