Применение метода линеаризации к задачам большого объема

• Автор: Кирик, Елена Евстафьевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Киев
• Количество страниц: 131 c. : ил

С ОДЕР дА Н И Е

ГЛАВА I. БЛОЧНЫЕ ЗАДАЧИ СО СВЯЗЫВАЮЩИМИ ПЕРЕМЕННЫМИ

§ 1.1. Формулировка проблемы

1.1.1. Процессы, приводящие к задачам со связывающими переменными

1.1.2. Постановка задачи

1.1.3. Процедура расчленения

§ 1.2. Координирующая и вспомогательные задачи ... хр,

1.2.1. Определения

1.2.2. Условия регулярности

1.2.3. Деловая функция координирующей задачи

1.2.4. Локальные координирующие задачи
§ 1.3. Декомпозиционный алгоритм для задачи квадратичного программирования со связывающими переменными
1.3.1. Процедура решения координирующей задачи Критерий оптимальности
1.3.2. Описание алгоритма
1.3.3. Рекуррентные формулы
§ 1.4. Обоснование конечной сходимости
§ 1.5. Случай вырождения
ГЛАВА 2. БЛОЧНЫЕ ЗАДАЧИ СО СВЯЗЫВАВДШ ОГРАНИЧЕНИЯМИ ЗР
§ 2.1. Декомпозиция, использующая механизм множителей
Лагранжа
2.1.1. Реальные процессы, описываемые задачами

со связывающими ограничениями
2.1.2. декомпозиция и двойственность
2.1.3. Двойственная координирующая задача. Основные определения
2.1.4. Максимизация квадратичной функции в регулярной области
2.1.5. Процедура выхода из нерегулярной точки
§ 2.2. Алгоритм для решения блочной задачи квадратичного программирования со связывающими .ограничениями
§ 2.3. Обоснование сходимости
§ 2.4. Задача со слабо связанными блоками
2.4.1. Сведение к задаче со связывающими переменными
2.4.2. Исследование координирующей задачи
2.4.3. Построение локальных координирующих задач
2.4.4. Процедура решения локальных задач
2.4.5. Критерий оптимальности процесса
§ 2.5. Алгоритм для решения задачи квадратичного программирования со слабо связанными блоками
ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ РЕШЕНИЙ ЗАДАЧ СПЕЦИАЛЬНОЙ
СТРУКТУРЫ
§ 3.I.-Компактное хранение информации при решении больших задач
3.1.1. Задачи со слабо заполненными матрицами ограничений
3.1.2. Задачи с двусторонними ограничениями

3.1.3. Задачи с блочно-диагональной структурой
ограничений
§ 3.2. Возможности организации параллельных вычислений на многопроцессорных ЭВМ
3.2.1. Распараллеливание процесса вычислений при реализации декомпозиционных алгоритмов
3.2.2. Обращение симметричной матрицы специального вида
3.2.3. Естественный- параллелизм и параллелизм смежных операций процесса (1.8) ,
§ 3.3. Вычислительный опыт решения задач специальной
структуры
ЗАКЛЮЧЕНИЕ
СПИСОК ОСНОВНОЙ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ

Здесь - {-я строка матрицы , и к,- очередная точка, получаемая в процессе действия алгоритма сопряженных градиентов, -&к+1 - вектор сдвига из этой точки.
сСк-к ~ }
Если ск^+1 - соответствующая длина шага метода сопряжен-
/"V
ных градиентов и выполняется условие 1 < Ж , то
'и1а+ч =• + о(,1&к+‘I и процесс продолжается. Если не
оСи+£ оСь + а , то ЪС = <И ^ <£>к-м
и процесс применения метода сопряженных градиентов окончен. Во втором случае полученную точку выбираем за начальную и работаем с новой точкой так не., как с исходной точкой /Ц0 , начиная с шага 2.
V Точка 'М,, не регулярна, делаем шаг метода наискорейшего спуска, модифицированного с учетом ограничений Ч О Считая полученную точку за начальную, возвращаемся к шагу 2.
Критерием оптимальности служит выполнение в некоторой точке 1Х на шаге 3 или 4 алгоритма соотношений
(/ЬС) < п _ : п
ф ^ У 1 если 'Ы ° — и
0к (и)
Ъ Ч
§ 2.3. Обоснование сходимости
Данная процедура строит такую последовательность допустимых точек двойственной координирующей задачи, вдоль которой значение функции К (та) монотонно возрастает. Рассмот-