Введение к работе
Актуальность проблемы. Задачи выпуклого программирования в общем случае не являются корректными. Поэтому вопрос о построении алгоритмов, устойчивых к малым искажениям информации и вырабатывающих сходящуюся по аргументу минимизирующую последовательность, является чрезвычайно актуальным. При этом важно, чтобы осуществление регуляризации сопровождалось по возможности небольшими вычислительными затратами. Решение этой проблемы имеет не только теоретическое, но и большое практическое значение, поскольку оно позволит выявить методы, наиболее перспективные для приложений.
Целью работы является создание новых устойчивых алгоритмов решения задачи выпуклого программирования на базе единого подхода, основанного на введении процедуры проке-регуляризации в схему метода штрафов. Этот подход позволяет построить эффективные алгоритмы, сходящиеся по аргументу к решению исходной задачи. Исследование сходимости и скорости сходимости осуществляется в предположении, что все промежуточные шаги выполняются приближенно.
Методы исследования. При получении основных результатов диссертации используется аппарат выпуклого анализа и элементы теории предела.
Научная новизна. Одним из способов построения алгоритмов решения некорректных задач математического программирования является введение процедуры прокс-регуляриэащш в базовый метод. В стандартном подходе, использующем в качестве базового меті д штрафов, при каждой фиксированной функции штрафа выполняется одна прокс-итерация, что может повлечь быстрое возрастание параметра штрафов в ситуации, когда решения возникающих вспомогательных задач еще далеки от множества решений исходной задачи. Это приводит к неоправданно большим вычислительным затратам.
Развитый в днесертац. онной работе подход базируется на принципе итеративной проЕС^рсгуляризацин, существенно модифицированном с учетом вычислительных особенностей метода штрафов. Именно, а предложенной схоме при фиксированном значении параметра штрафа вспомогательная задача решается прокс-методом до тех пор, пока это является эффективным, то есть обеспечивается достаточно быстрое убывание мііннмнзируї мой функции. Такой подход позволяет существенно снизить трудоемкость вычислительного процесса.
В рамках укачанного подхода предложены 4 варианта регулярпзо-ванного меюда штрафов (2 - при использовании барьерньг: функций п 2 - для алгоритмов внешней точки). Доказана сходимость всех предложенных методов и получены оценки скорости сходимости по функционалу, неулучг. аемые по порядку на рассматриваемом классе. При некоторых специальных свойствах целевой функции установлена линейная сходимость по аргументу. Вес результаты получены в предположении приближенного решения вспомогательных задач. Проведены экспериментальные расчеты на тестовых примерах.
Практическая ценность. Предложенные методы представляют практический интерес и могут быть использованы для решения задач выпуклого программирования, возникающих в практике управления экономп ісскішп, организационными и промышленными системами, а также для решения обратных задач геоэлоктрнки. В частности, с помощью алгоритма, основанного на методе внешнего штрафа, прочеден расчет обратной задачи об определении источника стороннего тока.
Применение разработанных методов целесообразно в ситуациях, когда достаточно легко оценить область, содержащую множество решений рассматриваемой задачи. В этих случаях может быть достигнута значительная экономия вычислений.
Приведенные в приложении 1 результаты численных экспериментов с тестовыми задачами выпуклого программирования могут в какой-то мере служить показателями эффективности предложенного подхода.
Апробация работы. Основные положения и результаты диссертационной работы докладывались п обсуждались на Всесоюзной конференции "Условно-корректные задачи математической физики и анализа'' (Новосибирск, 1992), XXIII региональной молодежной конференции (Екатеринбург, 1992), международном симпозиуме по вычислительной томографии (Новосибирск, 1993), а также на семинарах математпко-экономнческого отдела и отдела условно-корректных задач Института математики СО РАН.
Публикации. Основные положения диссертации изложены в четырех научных публикациях. Всего по результатам исследований опубликовано шесть работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, двух приложений и списка цитируемой литературы. Объем диссертации — 120 страниц машинописного текста, библиография включает -17 наименований работ советских п зарубежных авторов.