Введение 5
Глава 1. Сортировка как алгоритмическая основа для автоматической идентификации экстремумов и нулей функций одной и нескольких переменных 38
1.1. Параллельные алгоритмы сортировки слиянием и модифицированной
сортировки подсчетом 39
1.1.1. Последовательное слияние по матрицам сравнений 41
1.1.2. Числовые параметры сортировки слиянием 42
1.1.3. Сортировка слиянием массива с произвольным числом элементов 43
1.1.4. Модифицированная сортировка подсчетом
1.2. Алгоритм автоматической идентификации экстремальных значений одномерной последовательности на основе сортировки 47
1.3. Схема автоматической идентификации всех экстремумов функции одной действительной переменной на основе сортировки 50
1.4. Инвариантность схемы относительно вида функции и размеров промежутка поиска экстремумов 54
1.5. Схема локализации и вычисления экстремальных значений функции двух переменных 56
1.6. Схема автоматической идентификации экстремумов функций трех и более переменных 62
1.7. Автоматическая идентификация на основе сортировки нулей функций одной и многих переменных 67
1.8. Параллелизм схемы автоматической идентификации экстремумов и нулей функций многих переменных 69
1.9. Сравнение схемы идентификации экстремумов на основе сортировки с известными методами безусловной оптимизации 71
1.10. Выводы 75
Глава 2. Сортировка как алгоритмическая основа для автоматической идентификации экстремумов и нулей разностных решений дифференциальных уравнений 77
2.1. Идентификация на основе сортировки экстремумов разностного решения
обыкновенного дифференциального уравнения (ОДУ) первого порядка 77
2.1.1. Идентификация истинных и исключение ложных экстремумов на границах текущего промежутка при помощи сортировки 80
2.2. Идентификация на основе сортировки экстремумов разностного решения системы дифференциальных уравнений второго порядка з
2.3. Идентификация на основе сортировки экстремумов разностных решений ОДУ в случае схем высшего порядка и формулировка основного предложения 86
2.4. Случаи систем ОДУ из трех и более уравнений с приложением к идентификации экстремумов нормы разностных решений 90
2.5. Автоматическая идентификация на основе сортировки нулей разностных решений дифференциальных уравнений 93
2.6. Алгоритм автоматической идентификации экстремальных значений и нулей разностных решений уравнений в частных производных 94
2.7. О сравнении с известными методами поиска на основе сортировки экстремумов и нулей решений дифференциальных уравнений 99
2.8. Выводы 103
Глава 3. Применение сортировки для многомерной оптимизации с приложениями к решениям систем дифференциальных уравнений в условияхвариации параметров и к задачам условной оптимизации 106
3.1. Применение алгоритма многомерной оптимизации на основе сортировки к поиску экстремумов разностных решений систем линейных ОДУ при вариации параметров 106
3.1.1. Многомерная оптимизация на основе сортировки дискретно представленной функции четырех переменных 107
3.1.2. Приложение к поиску глобального экстремума разностного решения системы линейных ОДУ при дискретной вариации трех параметров 110
3.2. Применение алгоритма многомерной оптимизации к поиску экстремумов нор мы возмущений решений систем нелинейных ОДУ при вариации параметров 118
3.2.1. Компьютерная оценка устойчивости на основе идентификации нулей и особенностей передаточной функции 123
3.3. Обобщенная схема оптимизации при вариации параметров 124
3.4. Применение алгоритма многомерной оптимизации для решения задач линейного программирования 1
3.4.1. Пример численного решения задачи линейного программирования для случая целевой функции двух переменных 129
3.4.2. Примеры численного решения задачи линейного программирования для случая целевой функции трех и четырех переменных 1
3.5. Схема многомерной оптимизации на основе сортировки в случае решения задач нелинейного программирования 133
3.6. Особенности схемы идентификации экстремумов на основе сортировки 138
3.7.Выводы 140
Заключение 142 Литература 145
Приложение 1 155
Приложение! 178
Приложение 3 206
Приложение 4. Идентификация на основе сортировки полюсов передаточных функций и компьютерный анализ экстремального отклоненияот состояния устойчивости линейных динамических систем 255
4.1. Оценка экстремального отклонения отточки покоя решения уравнения состояния при вариации параметров 255
4.2. Компьютерный анализ устойчивости в условиях экстремального отклонения линейной динамической системы от точки покоя 261
4.3. Идентификация устойчивости по корням характеристического многочлена уравнения состояния и по норме преобразованной матрицы коэффициентов 273
4.4. Поиск на основе сортировки корней характеристического уравнения при наличии трансцендентности 279
4.5. Исследование на основе сортировки распределения полюсов передаточной функции на комплексной плоскости 284
Приложение 5. Акты об использовании результатов диссертационной работы 2
Актуальность проблемы. Первые задачи, связанные с отысканием наименьших и наибольших величин, преимущественно геометрического содержания появились в древности. Развитие промышленности в XVII— XVIII веках привело к более сложным задачам на экстремум. В XX веке при развитии производства в условиях ограниченности ресурсов возникли задачи оптимального расхода энергии, материалов, рабочего времени. Приобрели актуальность вопросы наилучшего в том или ином смысле управления различными процессами физики, техники, экономики. В частности, потребовалось организовать производство с целью получения максимальной прибыли при заданных затратах ресурсов. Актуальны задачи управления системой гидростанций и водохранилищ с целью получения максимального количества электроэнергии, построения оптимальной траектории космического перелета с наименьшей затратой энергии. Аналогичные задачи ставятся при нагреве или охлаждении металла до заданного температурного режима и др. В различных разделах математики возникают задачи наилучшего приближения функций, оптимального выбора параметров итерационного процесса, узлов интерполирования, минимизации невязки уравнений и т. д. Все такие задачи могут быть идентифицированы как задачи отыскания экстремума (максимума или минимума) некоторой функции или функционала.
Современное состояние теории оптимизации характеризуется фундаментальными направлениями в области линейного, выпуклого, стохастического программирования, оптимального управления, а также в области численных методов приближенного решения экстремальных задач.
I. При изучении экономического поведения возникают проблемы точного описания стремления индивидуума к извлечению максимальной пользы или прибыли. Постановка и решение таких задач достигаются при помощи математических методов, существенно отличающихся от классических методов решения задач на экстремумы.
Одна из трудностей, возникающих при решении как статических, так и динамических задач на условный экстремум в виде задачи вариационного исчисления, состоит в том, что для получения конкретного ответа необходимо знать конкретный вид исследуемой функции. В тех экономических задачах, где нужны качественные свойства решения, достаточно общего представления о виде функции. Если же необходимо построить модель конкретной практической задачи, то без конкретных функций не обойтись. Для современных приложений разработан подход к задаче оптимизации при ограничениях, относящийся к разделам линейного программирования.
С помощью метода линейного программирования удалось связать два вида решений в теории фирмы, а именно: выбор технологии производства и выбор состава и размеров выпуска, обеспечивающих максимальную прибыль. Для случая, когда целевую функцию нельзя представить в виде линейной функции, была разработана теория нелинейного программирования.
Помимо этого метода для решения задач нелинейного программирования используются методы аппроксимирующего программирования, включая методы линеаризации /94, 100, 101, 115/, и применимые к ним методы линейного программирования /33/, а также метод неопределенных множителей Лагранжа.
Для решения динамических задач вместо вариационного исчисления стали использоваться в основном современные методы динамического программирования и теории оптимального управления. Теорию оптимизации можно рассматривать как особый раздел математики или же, как набор средств, необходимых экономисту-прикладнику для решения вполне определенных прикладных задач, при этом необходимо улучшение перечисленных методов, которые разрабатывались, чтобы находить ответы на вопросы, поставленные более конкретно, чем нужно экономической теории. Таким образом, экономическая теория продолжает оставаться качественной наукой.
П. Один из основных подходов к решению экономических задач дает теория игр /64, 120/. На начальных этапах развития теории игр ее рассматривали как обобщение теории оптимизации на случай двух и более участников экономического процесса. Однако подлинное отличие от традиционной теории заключалось в том, что в теории игр учитывается взаимодействие участников экономического процесса и возможность конфликта между ними. Это отличие нашло выражение в целевой функции, которая определяет размер выигрыша в зависимости от выбранного решения: выигрыш одного участника экономического процесса зависит не только от того, какие альтернативы выберет он сам, но и от того, какие альтернативы выберут другие. Благодаря этому в экономических исследованиях игровой подход применялся преимущественно для изучения таких экономических проблем, как двусторонняя монополия или олигополия. Кроме того, теория простых игр позволила уточнить понятие равновесия в экономике. В играх двух участников с нулевой суммой равновесной стратегией любого участника экономического процесса является такая, которая дает данному участнику наибольший минимальный выигрыш при любой возможной стратегии другого игрока. Такое равновесие консервативно, поскольку участник экономического процесса должен выбирать не ту стратегию, которая приносит ему наибольший выигрыш при неразумном выборе стратегии соперником, а ту стратегию, которая в наибольшей степени предохраняет от потерь в игре с умудренным соперником.
III. Теория игр признана классической наукой, играет значительную роль в ряде прикладных областей, включая военное дело и экономику /1,112-114/. В качестве основного подхода к задачам теории игр используются средства классического анализа и дифференциальные уравнения. В этом контексте рассматривается теория дифференциальных игр, которая исследует игры, где противники принимают целый ряд последовательных решений, которые так логически связаны друг с другом, что эта связь может послужить основой наглядной и численно анализируемой модели.
Примером дифференциальных игр может быть боевая игра, где каждый игрок стремится уничтожить боевые силы противника. Аналогию этой игры можно найти, например, в бизнесе, когда каждая из двух коммерческих фирм старается разорить конкурента. Подобные игры можно рассматривать и как игры степени, где платой является количество уцелевших ресурсов победившей стороны, и как игры качества, цель которых - истребление. Типичными примерами дифференциальных игр также являются сражения, воздушные бои, футбол, преследование судна торпедой, перехват самолета зенитной ракетой, охрана объектов от нападения. Если один из игроков выключается из игры, то получаем обычную задачу максимизации. Она уже относится к вариационному исчислению и составляет основную часть теории оптимального управления.
Дифференциальные игры, описывающие конфликтно-управляемые системы, являются обобщением задач оптимального управления. В теории оптимального управления рассматриваются также задачи, учитывающие запаздывание информации, задачи с параметрами, с дискретным временем, с общим видом целевой функции, задачи для уравнений с частными производными. К решению таких задач сводится большой объем вычислительных задач прикладной математики, теоретической и экспериментальной физики, технической кибернетики.
Помимо принципа максимума Понтрягина в области динамического программирования широко известен принцип оптимальности Беллмана. Описание принципа в содержательном смысле заключается в следующем /20,104 /.
Принцип оптимальности. Оптимальная политика (или стратегия, понимаемая как последовательность допустимых решений) обладает тем свойством, что, каковы бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальную политику относительно состояния, являющегося результатом применения первого решения. Принципа максимума Понтрягина и принцип оптимальности Беллмана находят разнообразное применение при решении задач вариационного исчисления и задач условной оптимизации /68, 104/
V. Для решения задач оптимизации широко используется современные средства вычислительной техники. В процессе использования последовательных компьютеров был накоплен и отработан огромный фонд численных методов и про 14 грамм. Однако оказалось, что современные персональные компьютеры не в состоянии решить за приемлемое время многие задачи, имеющие большой объем вычислений. Использование параллельных компьютеров позволяет минимизировать время реализации алгоритмов. При этом существенно, чтобы параллельная реализация алгоритма имела такие же вычислительные свойства, как и любая другая. В частности, если исходный алгоритм (последовательный) был численно устойчив, то он должен оставаться таким же и в параллельной форме. Как отмечается в /27/, на практике подавляющее большинство алгоритмов оказалось несостоятельным. Огромное число требуемых процессоров, сложные информационные связи между операциями, численная неустойчивость, конфликты в памяти препятствуют применению быстрых параллельных алгоритмов. Перечисленные трудности относятся к существующим задачам оптимизации. Поэтому необходима разработка машинного метода приближенных вычислений, позволяющего экономить время и усилия, затрачиваемые на решение оптимизационной задачи.
В данном аспекте целесообразно принять во внимание схемы использования сортировки для приближенных вычислений /75, 76, 78, 79 /. Алгоритмы ее выполнения позволяют минимизировать количество формул и методов традиционной математики. Применение сортировки опирается на упорядочение информации при вычислениях и включает только операции сравнения. Как следствие, можно ожидать снижения роста погрешности при решении задач с ее применением. На этой основе схемы параллельной сортировки можно рассматривать как одно из средств решения проблем устойчивости параллельных вычислений.
Сортировка /24/ практически присутствует во всех приложениях операционных систем при обработке больших объемов данных. С помощью сортировки решаются задачи "группировки", когда нужно собрать элементы по некоторому признаку. Сортировка используется при поиске с целью его ускорения, с помощью сортировки можно сделать выдачи ЭВМ более удобным для человеческого восприятия. В контексте сортировки рассматриваются многие аспекты программирования.
Сортировки делятся /53/ на внутренние и внешние. Внутренние сортировки выполняются в оперативной памяти. Внешние сортировки приемлемы для файлов данных, которые превосходят размер основной памяти, и поэтому должны в течение процесса сортировки располагаться на устройствах внешней памяти. В процессе внешней сортировки часть файла считывается в основную память, там упорядочивается, а затем переписывается на внешние устройства. Во всех внешних сортировках используются внутренние сортировки. Ниже рассматриваются некоторые примеры сортировок, а также параллельное слияние, приводятся оценки временной сложности.
Временная сложность алгоритмов будет измеряться количеством последовательных шагов их выполнения. В частности, временная сложность сортировки измеряется числом последовательно выполняемых сравнений. Временная сложность параллельных алгоритмов будет оцениваться на модели неветвящихся параллельных программ /2, 19, 77, 93/ без учета обмена. Временная сложность параллельной сортировки будет обозначаться Г(Я) = &г, где т - время бинарного сравнения, к количество последовательных сравнений, R - число используемых процессорных элементов (при описании параллельных сортировок иногда их называют компараторами).
Сортировка вставками /53/. Элементы просматриваются по одному, каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов (временная сложность - Г(1) = 0(N2), где 0(f) - класс функций, растущих не быстрее /). Сортировка Шелла, временная сложность которой Т(\) = 0(N 5),
представляет собой усовершенствование сортировки вставками. Эта сортировка представляет собой многопроходную сортировку, при которой список разбивается на подсписки, каждый из них сортируется отдельно, причем на каждом проходе число подсписков уменьшается, а их длина растет.
Обменная сортировка /53, 83, 84/. Предусматривает систематический обмен местами между элементами пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется. Существуют несколько типов сортировки, для которых обмены являются основной характеристикой. Выделяют обменную сортировку с выбором ("метод пузырька"), поразрядную сортировку, обменную сортировку с разделением ("быстрая сортировка" Хоара), обменная сортировка со слиянием (параллельная сортировка Бэтчера).
Сортировка выбором /53/. Из последовательности выделяется наименьший (наибольший) элемент и каким- либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся, процесс повторяется до тех пор, пока все элементы последовательности не будут отсортированы. На идее выбора основан алгоритм пирамидальной сортировки
Пирамидальная сортировка (T(Y) = 0(N log2 N)) строит бинарное дерево, значение каждого узла в котором превышает значение потомков. В результате наибольший элемент списка помещается в корень, при его удалении и выборе очередной пирамиды в корне оказывается следующий по величине элемент. Процесс повторяется, пока все элементы не окажутся в отсортированном списке.
Сортировка подсчетом /53, 86/. При сортировке подсчетом (T(l) = 0(N2)), каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей.
Для параллельного слияния двух упорядоченных массивов из т и п элементов сравнение всех элементов между собой в матрице сравнений производится одновременно. Временная сложность параллельного слияния Т(т п) = 0(1).
Замечание 1. Вся сортировка слиянием по матрице сравнений в параллельном варианте имеет временную сложность T(N2 /4)=0(log2 N). При этом данная сортировка относится к числу наиболее быстрых и в последовательном варианте r(l)= 9(WIog2AO/80, 81/.
Немаловажным качеством сортировок является их устойчивость. Сортировка называется устойчивой, если она обладает свойством сохранения порядка записей с одинаковыми ключами /53/. К числу устойчивых относятся, например, сортировка вставками, к числу неустойчивых - корневая, пирамидальная, быстрая. В /83, 84/ предложены такие параллельные модификации известных схем сортировок, при которых модифицированные сортировки приобретают устойчивость, включая параллельное видоизменение сортировок подсчетом и слиянием.
В рассматриваемом контексте исследуется применение сортировок для построения схем локализации и устойчивого вычисления экстремумов функций.
VI. Численные схемы безусловной оптимизации. Ниже приводится сравнительная характеристика наиболее часто применяемых методов вычисления экстремумов функций.
Методы численного решения задач многомерной безусловной оптимизации многочисленны и разнообразны. С некоторой нестрогостью их можно разделить на три класса в зависимости от информации, используемой при реализации метода.
1. Методы нулевого порядка, или прямого поиска, стратегия которых основана на использовании информации только о свойствах функции.
2. Методы первого порядка, в которых при построении итерационной процедуры наряду с информацией о функции используется информация о первых производных этой функции. 3. Методы второго порядка, в которых наряду с информацией о значениях функции и ее первых производных используется информация о ее вторых производных.
В литературе /3, 6, 14, 25, 29, 36/ не выделяется универсальный метод, применимость которого была бы оправдана и эффективна во всех случаях. Выбор того или иного метода, его программная реализация должны быть согласованы с конкретными условиями, вытекающими из специфики решаемой задачи безусловной минимизации.
Для функции одной переменной классический подход /6, 20, 40, 47, 50/ при поиске минимума (максимума) функции f(x) состоит в последовательном вычислении функции при возрастающих значениях х до тех пор, пока не будет достигнуто наименьшее (наибольшее) значение функции. Значения дг должны быть заключены в интервале а х Ь. В начале процесса оптимизации интервал имеет длину Ь-а. Вычислив значения функции f{xl) и f(x2) при значениях х, и х2 в
указанном интервале, интервал сужают. В зависимости от способов сужения интервала различают следующие методы оптимизации: метод общего поиска, метод Фибоначчи, метод золотого сечения, метод парабол.
Функция f(x) может иметь на исследуемом множестве более одного локального минимума. В конкретных прикладных задачах далеко не всегда удается заранее исследовать свойства функции. Поэтому желательно, чтобы численный алгоритм позволял определить число минимумов и их расположение.
Метод золотого сечения применим даже к недифференцируемым функциям и всегда сходится; сходимость его линейна. Если на отрезке [а, Ь] функция имеет несколько локальных минимумов, то процесс сойдется к одному из них (но не обязательно к наименьшему). Этот метод применяют в технических или экономических задачах оптимизации, когда минимизируемая (максимизируемая) функция не-дифференцируема, а каждое вычисление функции выполняется по сложному алгоритму.
4.Метод парабол /21,49/. Если f(x) дифференцируема, то можно построить более быстрые методы, основанные на решении уравнения / ( ) = 0. На практике часто f(x) имеет первую и вторую производную. Поэтому для нахождения нулей первой производной применяют метод линеаризации, что приводит к итерацион f(x ) ному процессу хк+] =хк - й . Для успешной работы метода парабол необходи мы дополнительные поправки к алгоритму. В ходе вычислений надо проверять, продвигаются ли вычисления к минимуму. Если функция имеет несколько локальных минимумов, то метод может сойтись к любому из них или не сойтись вовсе. Описанный способ не дает гарантии того, что будут найдены все минимумы (и тем самым, что будет найден абсолютный минимум).
Наилучшими критериями сравнения методов поиска являются их эффективность и универсальность. Под эффективностью алгоритма обычно понимают количество вычислений функции, необходимое для достижения требуемого сужения интервала неопределенности. Лучшим в этом отношении является метод Фибоначчи, худшим — метод общего поиска. Как правило, методы Фибоначчи и золотого сечения, обладающие высокой эффективностью, наиболее подходят для решения одномерных унимодальных задач оптимизации /31,35, 106/.
Универсальность алгоритма означает его применимость для решения самых разнообразных задач. В этом отношении метод Фибоначчи уступает другим, мало 22
эффективный метод общего поиска можно с успехом применять и для не унимодальных функций, если они достаточно гладкие. Нередко заранее не известно, является ли рассматриваемая целевая функция унимодальной. В таких случаях следует воспользоваться несколькими разными алгоритмами и посмотреть, дают ли они все один и тот же оптимум.
Принято считать, что не существует универсального алгоритма, который позволял бы решать любые задачи безусловной оптимизации /6, 95, 96/. При решении сложных задач оптимизации пользуются разными методами, так как это позволяет увеличить долю удачных решений.
Замечание 2. Схема оптимизации, разрабатываемая в диссертационной работе, отличается по построению от существующих методов безусловной оптимизации и инвариантна относительно вида исследуемой функции при том ограничении, что функция на вход схемы поступает после дискретизации.
Функции многих переменных. Численное решение задач безусловной минимизации (максимизации) функций многих переменных, как правило, значительно сложнее, чем решение задач минимизации (максимизации) функций одного переменного. С ростом числа переменных возрастают объемы вычислений и усложняются конструкции вычислительных алгоритмов, более сложным становится анализ поведения функции Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных f{x,y). Она описывает некоторую поверхность в трехмерном пространстве с координатами х, у, f. Задача f{x,y) = min означает поиск низшей точки этой поверхности. Рельеф этой поверхности можно изобразить линиями уровня. Проведем равноотстоящие плоскости / = const и найдем линии их пересечения с поверхностью f(x,y); проекции этих линий на плоскость хОу называют линиями уровня. Направление убывания
функции указывают штрихами, рисуемыми около линий уровня. Полученная картина напоминает топографическое изображение рельефа горизонталями. По виду линий уровня условно выделяют три типа рельефа: котловинный, овражный и неупорядоченный. При котловинном рельефе линии уровня похожи на эллипсы (рис. 5, а). В малой окрестности невырожденного минимума рельеф функции котловинный.
Все эффективные методы поиска минимума сводятся к построению траекторий, вдоль которых функция убывает; разные методы отличаются способами построения таких траекторий. Метод, приспособленный к одному типу рельефа, может оказаться плохим на рельефе другого типа.
5. Метод спуска по координатам /20, 90/. Рассмотрим функцию трех переменных f(x,y,z). Выберем нулевое приближение х0, у0, z0. Фиксируем значения
двух координат у = у0, z = z0. Тогда функция будет зависеть только от одной переменной х, обозначим ее через fx(x) = f(x,y0,z0). Используя методы поиска экстремума для функции одной переменной, находим минимум функции /{(х), обозначив его через х,. Выполнение шага из точки (x0,y0,z0) в точку (xvy0,z0), по направлению, параллельному оси х, уменьшает значение функции.
Метод спуска по координатам несложен и легко программируется, но сходится медленно, а при наличии оврагов - очень плохо. Поэтому его используют в качестве «первой попытки» при нахождении минимума.
6. Наискорейший спуск. Спускаться можно не только параллельно осям ко ординат. Вдоль любой прямой г = r0 + at функция зависит только от одной пере менной, f(rQ + at) = p{t), и минимум на этой прямой находится методами поискаэкстремума для функции одной переменной. Наиболее известным является метод наискорейшего спуска, когда выбирается a = -(grad /)r_r , т. е. направление, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки. Спуск по этому направлению до минимума определяет новое приближение г,. В этой точке снова определяется градиент и делается следующий спуск. Этот
метод сложнее спуска по координатам, требуется вычислять производные и градиент (иногда конечно-разностными методами) и переходить к другим переменным. По сходимости наискорейший спуск не лучше спуска по координатам. При попадании траектории в истинный овраг спуск прекращается, а в разрешимом овраге сильно замедляется /50/.
7. Сопряженные направления /6, 9/. Методы наискорейшего спуска или спуска по координатам требуют бесконечного числа итераций, но можно построить такие направления спуска, что для квадратичной функции f(r) = (r, Ar) + (b,r) + c, (г есть n-мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется к минимуму за конечное число шагов. Вводится норма вектора.
Определение (8) подразумевает скалярное произведение векторов х и у вида (x, Ay). Векторы, ортогональные в смысле скалярного произведения, называют сопряженными (по отношению к матрице А). Поочередный спуск по сопряженным направлениям особенно выгоден при поиске минимума (максимума). На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и др. Для квадратичной функции они применяются с одинаковым успехом, на произвольные функции хорошо обобщается метод сопряженных направлений, у которого детали алгоритма тщательно отработаны. Метод сопряженных направлений относят к наиболее эффективным методам спуска. Он неплохо работает при вырожденном минимуме, при разрешимых оврагах, при наличии слабо наклонных участков рельефа - "плато". Методы спуска неполноценны на неупорядоченном рельефе. Если локальных экстремумов много, спуск из нулевого приближения может сойтись лишь к одному из них, не обязательно абсолютному, в этом случае применяют случайный поиск /50, 90/.
8. Случайный поиск. Предполагают, что минимум (или все минимумы) лежит в некоторой замкнутой области; линейным преобразованием координат помещают ее внутрь единичного п -мерного куба. Выбирают в этом кубе N случайных точек; если о расположении экстремумов заранее ничего не известно. Вероятность, что хотя бы одна точка попадет в небольшую окрестность локального минимума, мала. Поэтому берут небольшое число точек и каждую рассматривают как нулевое приближение. Из каждой точки совершают спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска сильно укорачиваются, его прекращают, не добиваясь высокой точности. Этого достаточно, чтобы судить о величине функции в ближайшем локальном минимуме. Сравнивая окончательные значения функции на всех спусках между собой, можно изучить расположение локальных минимумов функции и сопоставить их величины. Метод случайного поиска зачастую позволяет найти все локальные минимумы функции 10-20 переменных со сложным рельефом. Он полезен при исследовании функции с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Широкая область затрудняет детальное исследование, узкая область влечет потерю экстремумов.
Метод Дэвидона - Флетчера - Пауэлла /106/ представляет собой алгоритм отыскания безусловного минимума целевой функции от нескольких переменных. Необходимы частные производные целевой функции по независимым переменным. В основе метода лежит допущение об унимодальности целевой функции, при нарушении допущения следует брать несколько исходных точек. Метод Дэвидона -Флетчера - Пауэлла позволяет обходить трудности, связанные с разрывами производных в пространстве проектирования. Распространено мнение, что этот метод наиболее эффективен из всех градиентных методов, дает полную информацию о кривизне поверхности целевой функции в точке минимума, однако при этом требуется больший объем памяти и длительность счета. При исследовании унимодальной функции, откуда бы ни начинался поиск, вычисления приведут к нужной точке. На рис. 6 приведены линии уровня функции с двумя локальными минимумами в точках 0] и 02, Сравнивая между собой значения функции в точках Oi и 02, находят, что наименьшее значение функции достигается в точке 02.
Пример функции с двумя локальными минимумами в точках 0{ и Рис. 6. Если начать поиск наименьшего значения с помощью градиентного спуска из точки Ах, поиск приведет в точку 0{, которую ошибочно можно принять за искомый минимум, С другой стороны, если поиск начинается с точки А2, то вычисления приведут в точку 02.
Принято считать /11, 90, 95/, что универсального приема, который бы позволил эффективно справляться с многоэкстремальностью, не существует. Самый простой прием состоит в том, что проводят поиск несколько раз из разных начальных точек. Если при этом получаются разные значения целевой функции, то сравнивая их, выбирают наименьшее /90, 106/, Расчеты останавливают после того, как несколько новых поисков не меняют полученного ранее результата. Выбор начальных точек поиска, обоснованность прекращения расчетов в значительной степени зависят от опыта и интуиции специалистов, решающих задачу. Во многих случаях необходима различная дополнительная информация о характере задачи, которая существенно помогает при выборе метода, начальной точки поиска. Если нет никаких предположений о специальных свойствах целевой функции и о характере рассматриваемой области, это затрудняет анализ. Конкретизация задачи, выделение определенных классов функций и областей позволяет провести более глубокое исследование и разработать специальные методы, которые решают задачу исчерпывающим образом. П. Исследование ландшафтов целевых функций на основе эволюционной оптимизации. В рамках подхода к решению задач оптимизации исследуется возможность применения эволюционных и генетических алгоритмов /10, 13/. При этом строятся новые целевые функции, обеспечивающие получение оптимальных решений для исходных функций /54/. Использование одних и тех же целевых функций в рамках схемы эволюционных алгоритмов часто приводит к достижению локального, но не глобального экстремума. По этой причине возникает идея замены одной целевой функции на другую при условии, что это приводит к эквивалентному результату. Актуальна задача выбора эффективной целевой функции на ранней стадии разработки нового алгоритма. Для выбора такой функции конструируются подходы на основе анализа ландшафтов целевой функции /32, 57/. Разработанные в данном аспекте методы ориентированы на получение интегральных параметров ландшафта целевой функции, которые определённым образом характеризуют её сложность для эволюционных алгоритмов. Чтобы оптимизировать функцию модифицируется алгоритм расчета интегральных параметров на основе барьерных деревьев. На этой основе выделяются компоненты, по которым можно судить об эффективности соответствующих им целевых функций для эволюционных алгоритмов. Метод барьерных деревьев /57/ позволяет оценить глубину каждого локального минимума и степень его влияния на процесс эволюционного проектирования. Основная идея метода заключается в том, что сложность поверхности отражает высота h, на которую необходимо подняться, чтобы попасть из одного локального минимума в другой.
Подход включает следующие затруднения. Сравнивать целые наборы величин затруднительно, поскольку количество локальных оптимумов обычно различно для различных целевых функций. Кроме того, для автоматического сравнения желательно иметь один интегральный параметр. Поэтому необходимо оценить вероятность не возникновения преждевременной сходимости. Для этого достаточно, чтобы генетический алгоритм мог выйти из текущего локального оптимума и найти другой с лучшим значением. В случае успеха он вероятнее найдёт локальный оптимум, который ближе всего находится к текущему локальному оптимуму. Производится /54/ переход от набора параметров локального минимума к единственному параметру оценки области локального минимума. /(х,,х - минимальный
барьер, который необходимо преодолеть, чтобы попасть из локального оптимума / в локальный оптимум j. Барьер - это наивысшая точка некоторого пути. Чтобы
получить только один интегральный параметр для всего ландшафта, достаточно выделить из всех локальных оптимумов тот, выход из которого наиболее сложен. Значение такого оптимума интерпретируется как глубина В ландшафта. Для сравнения ландшафтов берётся отношение глубины к общей высоте ландшафта, которое называется сложностью ц/. Для сравнения ландшафтов используются два параметра - глубина В и сложность у/.
Основная идея определения всех локальных оптимумов состоит в предварительной дискретизации пространства неравномерной сеткой. После этого для определения является ли некоторая точка локальным или глобальным оптимумом достаточно просмотреть соседние для неё точки. В результате получается линейный алгоритм сложности 0(3nN), где yV -количество точек исходной выборки, а п размерность пространства. Положительные результаты достигаются в случае поверхности близкой к классу унимодальных и при достаточных размерах области локализации экстремума /54/. Количество найденных решений зависит от модальности функции.
VII. Предварительная характеристика проблем вычислительных схем оптимизации. Как отмечалось, принята точка зрения /6, 20, 50, 90/, что не существует универсального алгоритма численного решения задач оптимизации. Метод, приспособленный к одному типу рельефа функции, может оказаться непригодным на рельефе другого типа. При решении сложных задач оптимизации пользуются несколькими методами, чтобы увеличить долю удачных решений. Поиск экстремума выполняется несколько раз с различными начальными приближениями, сравнивая значения целевой функции и выбирая наименьшее (наибольшее). Итерации прекращаются, когда несколько повторений не меняют результата.
Можно отметить, что по причинам изложенных затруднений в рамках существующих вычислительных схем безусловной оптимизации не ставится задача автоматического определения всех локальных экстремумов функции в области допустимых значений. Существующие системы компьютерной математики /41/ реализуют разнообразные схемы вычисления экстремальных значений функций. В частности, в Mathcad для определения экстремумов функций реализованы градиентные методы, включая метод сопряженных градиентов, метод Левенберга /41, 106/. В пакете Maple исследование на экстремум функции заключается в нахождении точек, в которых производная исследуемой функции равна нулю /41/. Устойчивая работа математических пакетов зависит от сложности исследуемой функции. Иногда пакеты не могут указать точку экстремума, лишь представляя исследуемую функцию графически. В этом случае не идентифицированы числовые значения, а графически они отображены с малой точностью разрешающей способности графического редактора. Сложности использования пакетов усугубляются для функций многих переменных.
Вычислительные методы безусловной оптимизации глубоко опираются на аналитические критерии экстремумов классической математики. Как отмечалось, для компьютерной идентификации аналитических признаков, основанных на поведении производных, их аналитические выражения заменяются на конечно-разностные приближения значений. Следствием может оказаться потеря точности идентификации экстремумов, иногда - потеря самих экстремумов. С другой стороны, переборные методы могут оказаться неэффективными и быть не чувствительными к сложностям рельефа целевой функции, особенно, в случае функции нескольких переменных.
Рассмотренные схемы (возможно, в виду затруднений), не предполагают автоматической идентификации области экстремумов, требуют начального приближения, игнорируют наличие экстремумов в некоторых сложных случаях, либо не достигают в этих случаях требуемой точности вычислений.
Зачастую трудности решения актуальных задач оптимизации /42, 46/, включая задачи современной теории управления /34, 56/ сводятся к отмеченным трудностям известных методов безусловной оптимизации.
Отсюда актуальна разработка программного метода локализации экстремумов функций, который бы выполнял автоматическую идентификацию области каждого экстремума и отличался бы существенным ограничением роста погрешности при его вычислении.
В качестве основы разработки целесообразно рассмотреть алгоритмы сортировки, поскольку они включают лишь операции сравнения и сами по себе не накапливают погрешности.
Сортировки традиционно применяются для поиска и моделирования методов теоретической информатики /102/. Положительный опыт применения сортировки именно для схем оптимизации описан в /77-79, 71, 75/. При этом необходимо принять во внимание параллелизм сортировки /77, 82/, который влечет возможность построения параллельных схем определения экстремумов в целом.
К одной из целей диссертационной работы относится исследование применимости сортировки для идентификации всех локальных и глобальных экстремумов функций одной и нескольких переменных в области допустимых значений. Конкретно, затрагивается проблема автоматической программной идентификации всех экстремумов произвольной алгебраической и трансцендентной функции одной и нескольких переменных, в произвольно фиксированной части области определения. Требования устойчивости и быстродействия идентификации экстремумов обеспечиваются за счет устойчивости и параллелизма схем на основе сортировки.
На основании изложенного целесообразно исследовать возможность разработки единой схемы оптимизации на общей основе алгоритмов распараллеливаемых сортировок. Более точно, формулируется следующая цель.
Цель диссертационной работы заключается в разработке и исследовании единой алгоритмической схемы решения задач оптимизации на основе применения алгоритмов сортировки. Цель включает разработку и программную отладку схем автоматической программной идентификации всех экстремумов функций в области допустимых значений. Помимо того, аналогичная задача ставится для идентифика-ципи всех экстремумов разностных решений систем обыкновенных дифференциальных уравнений (ОДУ) и уравнений в частных производных, а также для идентификации многомерной точки экстремума нормы решений систем ОДУ при вариации параметров. Наряду с этим исследуется применение схем к приближенному решению задач условной оптимизации.
Предполагается, что конструкция схем идентификации экстремумов и нулей функций должна быть инвариантной относительно вида функции, ее топологических особенностей, а также числа переменных. В частности, схема должна быть инвариантной относительно правой части системы ОДУ, относительно выбора разностных схем, относительно длины промежутка и шага решения. При этом должна достигаться устойчивость работы схем и требуемая точность вычислений, схемы должны эффективно распараллеливаться.
Иными словами, цель состоит в разработке и исследовании схем автоматической программной идентификации экстремумов функций в произвольной части их области определения не на математической, а исключительно на алгоритмической основе. В качестве базового алгоритма выбирается алгоритм устойчивой (сохраняющей порядок равных элементов) распараллеливаемой адресной сортировки (используются параллельные сортировки подсчетом и слиянием).
Для достижения поставленной цели в диссертационной работе ставятся следующие задачи:
1. Разработать и исследовать распараллеливаемые схемы устойчивой программной идентификации всех локальных и глобальных экстремумов, а также нулей функций одной и более переменных на основе сортировки в области допустимых значений. Искомые схемы должны быть инвариантными относительно области поиска и вида функции при условии ее дискретного представления на входе схемы.
2. Исследовать границы применимости схем автоматической идентификации экстремумов на основе сортировки для функций с рельефом значений различной топологической сложности; выполнить оценки временной сложности максимально параллельного варианта предложенных схем.
3. Разработанные на основе сортировки схемы применить для идентификации всех экстремумов и нулей разностных решений систем ОДУ на произвольном промежутке; оценить достоверность идентификации в случае разностных схем различного порядка, включая методы Эйлера, Эйлера - Коши и Рунге - Кутта.
4. Обеспечить инвариантность программной идентификации экстремумов и нулей разностного решения системы ОДУ относительно правой части системы, разностных схем решения, а также относительно числовых параметров из экспериментально устанавливаемого диапазона значений, включая длину промежутка и шаг решения.
5. На той же основе построить схему программной идентификации экстремумов и нулей разностного решения уравнений в частных производных; провести численный и программный эксперимент в условиях меняющихся значений числовых параметров схемы и установить границы параметров, при которых сохраняется достоверность идентификации.
6. Видоизменить основанную на сортировке схему для программной идентификации глобальных и локальных экстремумов нормы разностного решения систем ОДУ при вариации параметров и исследовать связь видоизменения с оценкой устойчивости решения; дать аналоги схемы для случаев вариации параметров трансцендентных, алгебраических уравнений и уравнений в частных производных.
7. Показать применимость схем оптимизации на основе сортировки для задач условной оптимизации, на основе численных экспериментов установить границы применимости схем для задач линейного и нелинейного программирования.
8. Выполнить сравнительный анализ устойчивости, точности, инвариантности и корректности предложенных схем путем проведения программного и численного экспериментов, в рамках эксперимента подтвердить достоверность результатов оптимизации на основе сортировки.
Методы исследования базируются на теории многомерной оптимизации, теории разностных схем решения дифференциальных уравнений, теории сложности, качественной теории устойчивости, включают схемы линейного и нелинейного программирования, алгоритмы параллельных вычислений и параллельных сортировок.
Достоверность результатов вытекает из их математического обоснования, подтверждается оценками временной сложности, а также результатами программного моделирования и численного эксперимента.
Научная новизна диссертационной работы заключается в построении обобщенной схемы применения сортировки для решения задач оптимизации. Как частный случай, в нее включаются схемы автоматической программной идентификации всех экстремумов и нулей дискретно представимых функций общего вида, аналогичные схемы для разностных решений систем ОДУ и уравнений в частных производных, схемы для задач условной оптимизации.
Предложенный подход отличается тем, что не использует аналитическое и конечно-разностное представление производных, не опирается на начальное приближение. Отличие от переборных методов заключается в использовании упорядочения входной информации с помощью сортировки и в циклической идентификации локальных экстремумов на основе подстановки индексов отсортированных элементов.
Конкретно, научная новизна характеризуется следующим образом:
1. На основе сортировки синтезированы схемы идентификации экстремумов функций многих переменных, которые отличаются от известных по построению. Схемы отличаются, помимо того, возможностью автоматической локализации одновременно всех экстремумов и нулей функций из области допустимых значений, вычислительной устойчивостью, параллелизмом с единичным порядком временной сложности максимально параллельной формы.
2. Показано, что схема локализации всех экстремумов функций многих переменных с рельефом различной топологической сложности не включает ограничений на вид входной функции, отличаясь этим от известных методов; от методов перебора схема отличается сортировкой входных данных и идентификацией экстремальных элементов в произвольной окрестности с использованием только подстановки индексов отсортированных элементов.
3. Предложена схема идентификации экстремумов и нулей разностных решений систем ОДУ, которая отличается от известных методов по построению на основе сортировки, инвариантностью относительно правой части системы, а также относительно разностных методов решения и длины промежутка разностного решения.
4. Разработана схема программной идентификации экстремумов и нулей разностных решений уравнений в частных производных, отличающаяся от известных по построению. Схема не включает иных математических операций, кроме сравнения входных дискретных значений, поэтому не вносит дополнительной погрешности, помимо погрешности дискретизации; отличие заключается также в устойчивости и параллелизме схемы, опирающемся на параллельность сортировки.
5. Предложено видоизменение основанной на сортировке схемы для автоматической программной идентификации глобальных и локальных экстремумов нормы разностного решения системы ОДУ при вариации параметров. Схема отличается областью применения численной оптимизации и программной оценкой возмущения решения системы ОДУ при вариации параметров.
6. Дано применение схемы оптимизации на основе сортировки для численного решения задач линейного и нелинейного программирования. Отличаясь единством построения в этих случаях, схема позволяет программно идентифицировать глобальные и локальные экстремумы целевой функции при заданных ограничениях.
7. На основе предложенных схем безусловной оптимизации идентифицируются нули и особенности передаточных функций динамических систем при наличии трансцендентности, выполняется компьютерный анализ их устойчивости, исследуется распределение нулей характеристического многочлена и полюсов передаточной функции на комплексной плоскости для линейного стационарного четырехполюсника.
Основные положения, выносимые на защиту:
1. Инвариантные относительно вида функции схемы оптимизации на основе сортировки, которые программно выполняют идентификацию всех экстремумов и нулей функции произвольного вида от нескольких переменных и отличаются существенным ограничением роста погрешности при вычислении экстремумов.
2. Схемы программной идентификации на основе сортировки всех экстремумов и нулей разностных решений систем ОДУ и уравнений в частных производных в произвольной части области сходимости разностных методов.
3. Схема применения сортировки для программной идентификации экстремумов норм разностных решений систем ОДУ при вариации параметров системы с приложением к компьютерному анализу устойчивости решения.
4. Основанная на сортировке схема численного решения задач условной оптимизации в области линейного и нелинейного программирования, отличающаяся единством построения и позволяющая программно идентифицировать глобальные и локальные экстремумы целевой функции при заданных ограничениях.
Связь с плановыми исследованиями, проводимыми по месту выполнения диссертационной работы. Диссертационная работа выполнялась в рамках госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ в рамках приоритетного направления развития науки и техники в РФ «Информационные и телекоммуникационные системы» в соответствии с перечнем критических технологий РФ «Технологии обработки, хранения, передачи и защиты информации» по направлению фундаментальных исследований «Информатика. Искусственный интеллект, системы распознавания образов, принятие решений при многих критериях».
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных схем численной оптимизации, которые ориентированы на компьютерную реализацию и актуальны для решения научно-технических задач в различных областях, включая проектирование электрических цепей, оптимизацию конструкции летательных аппаратов, задачи об ударах и колебаниях с определением амплитуды резонанса при наличии источников колебаний. Предложенные схемы оптимизации могут найти применение в промышленной технологии, в системах автоматического регулирования, управления и контроля.
Внедрение и использование результатов работы. Полученные в работе результаты использованы
1. В ОАО «Таганрогский завод «Прибой», приняты к использованию в качестве единой алгоритмической схемы оптимизации функционалов при обработке алгоритмов автоматической классификации гидроакустических изображений.
2. В госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО ТГПИ.
3. В учебном процессе кафедры информатики Таганрогского государственного педагогического института в рамках курсов «Информатика», «Информационные технологии в математике», «Численные методы», «Элементы абстрактной и компьютерной алгебры».
Апробация работы. Основные результаты работы докладывались на:
— X, XI международных конференциях «Математические модели физических процессов» (Таганрог, ТГПИ, 2004,2005 гг.);
— V международной научно-практической конференции по программированию УкрПРОГ 2006 (Украина, Киев, 2006 г.)
— VIII международных научно-практических конференциях «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права» (Москва, МГАПИ, 2005 гг.);
— VI научно-практической конференции преподавателей, студентов, аспирантов и молодых ученых (Таганрог, ТИУиЭ, 2005 г.);
— IV-й международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании» (Таганрог, ТИУиЭ, 2005 г.);
— Ill межрегиональной научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века - будущее российской науки» (Ростов, РГУ, 2005г.); — международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.)
Публикации. По материалам диссертационной работы опубликовано 13 печатных работ с общим объёмом 14,3 печатных листов.
Структура и объём работы. Диссертационная работа состоит из введения, 3 глав основного раздела, списка литературы и 5 приложений. Основное содержание работы изложено на 153 страницах, включая список литературы из 120 наименований.
