Введение к работе
Актуальность темы диссертации. В теории и практике численных методов оптимизации часто приходится иметь дело не с точными, а с приближенными решениями, которые удовлетворяют ограничениям задачи и критерию оптимальности с некоторой погрешностью. Поэтому для разработки формальных критериев остановки итерационных процедур, а также при анализе устойчивости решений относительно погрешностей в исходных данных или выполнения ограничений, было бы очень полезно располагать обоснованной характеризацией приближенных решений, независящей от специфики используемого численного метода. В работе строится теория необходимых и достаточных условий приближенной оптимальности в задачах математического программирования, обобщающая известные необходимые и достаточные условия точного оптимума.
Далее, большинство существующих численных методов оптимизации эффективны только для выпуклых задач оптимизации, хотя, при математическом моделировании сложных систем, часто возникают невыпуклые задач. В работе предлагаются схемы поиска приближенного решения таких задач в результате, также, возможно, приближенного решения аппроксимирующих выпуклых задач. Областью приложений предлагаемого подхода являются оптимизационные модели, в которых отказ от учета некоторых взаимосвязей или их упрощенное описание, приводит к более простым выпуклым задачам математического программирования.
Необходимость в приближенных решениях также может возникнуть при разработке систем управления автономными техническими системами в режиме реального времени. В работе рассматривается пример подобной задачи, связанной с разработкой алгоритма управления двигателями коррекции движения космических аппаратов.
Цели работы:
получение конструктивно проверяемых необходимых и достаточных условий приближенного оптимума в задачах математического программирования;
описание классов задач математического программирования, допускающих аппроксимацию выпуклыми задачами (разной степени приближения);
разработка и исследование схем построения приближенных решений задачи на основе, также приближенного, решения аппроксимирующих выпуклых задач;
разработка алгоритма приближенного решения одного класса задач линейного программирования в режиме реального времени.
Используемые методы являются типичными для теории и численных методов конечномерной оптимизации: функции Лагранжа и теория двойственности; свойства регулярности ограничений; понятия теоретически точных и приближенных численных методов; некоторые идеи численных методов линеаризации; аппарат линейного программирования. В основном, методика исследования базируется на опыте асимптотической теории возмущений задач математического программирования.
Научная новизна. Представленные в работе и опубликованные по теме диссертации результаты являются новыми.
Научная и практическая значимость работы. Предложенные конструктивно проверяемые необходимые и достаточные условия приближенных решений, а также, схемы построения этих решений, могут быть использованы в разработке численных методов анализа широкого класса оптимизационных моделей. Представленный алгоритм приближенного решения задачи линейного программирования использовался в программных системах поддержки начальных этапов проектирования космических аппаратов.
Результаты, выносимые на защиту:
необходимые условия приближенного оптимума первого порядка для гладких задач, обобщающие правила множителей Лагранжа для точных решений;
достаточные условия приближенного оптимума для гладких задач, на основе предположений о выпуклости или остроте минимума функции Лагранжа;
классы невыпуклых и, вообще говоря, негладких задач, близких, в оптимизационном смысле, к выпуклым задачам математического программирования;
методы построения приближенных решений невыпуклых задач на основе решения аппроксимирующих выпуклых задач (0-го, 1-го и 2-го приближений);
схема алгоритма построения приближенного решения одного класса задач линейного программирования в режиме реального времени.
Апробация работы. Результаты работы докладывались на 11-й Международной Байкальской школе-семинаре, Иркутск, Байкал, 5-12 июль 1998 г., [2,3]; конференции "AIAA Guidance, Navigation, and Control Conference and Exhibit", Providence, Rhode Island, USA, Aug. 16-19,2004, [6]. Семинаре ИСА РАН no численным методам и распределенным вычислениям. Апробация алгоритма построения приближенного решения задачи линейного программирования проводилась в исследовательских проектах Европейского космического агенства (European Space Agency, ESA): Spacecraft thruster management subsystem design and analysis software tool, ESA Contract Number: 15789/02/NL/LvH, 2002-04; High integrity autonomous multi-range rendezvous & docking control system (HARVD), первый этап HARVD trade-off and preliminary performances, 2006-07.
Публикации. По теме диссертации опубликованы работы [1, 2, 3, 4, 5, 6, 7], общим объемом 159 страниц, где автору принадлежат следующие результаты: [1, 2,4] - участие в формулировках условий оптимизационной близости исходной невыпуклой и аппроксимирующих выпуклых задач; формулировка достаточных условий гарантированного улучшения оценок точности по задачам 1-го и 2-го приближений; доказательства теорем, сформулированных совместно с соавтором;
[3] - предложение использовать для характеризации приближенного оптимума в гладких задачах оптимизации вспомогательную задачу квадратичного программирования; формулировки и доказательства условий оптимальности для гладких задач; [5] - доказательства утверждений, сформулированных в результате совместной работы с соавтором; иллюстративный пример задачи обнаружения "уклоняющегося" объекта; [6,7] - предложение использовать параметрический симплекс метод в сочетании со специальным алгоритмом определения начального базиса для построения приближенного решения одного класса задач линейного программирования; программная реализация численного метода и анализ результатов вычислительных экспериментов.
Структура и объем диссертации. Диссертация изложена на 140 стр. и состоит из оглавления, введения, пяти глав, разбитых на параграфы (с автономной нумерацией внутри главы), заключения, списка литературы из (64_ позиции, упорядоченные по алфавиту) и списка из JJ_ рисунков. В основном, используется двойная нумерация: вначале - номер параграфа (внутри главы), затем - номер формулы, определения, условия или утверждения в этом параграфе. Для следствий или замечаний к теоремам используется тройная нумерация - двойной номер теоремы и номер следствия или замечания. В номерах формул и определений Введения используется буква "В". При ссылках, выходящих за рамки главы, указывается номер главы, содержащей эту ссылку. Нумерация рисунков двойная: номер главы и номер рисунка.
