автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Свойства приближенных решений и схемы их построения в задачах математического программирования

На правах рукописи

Волошинов Владимир Владимирович

СВОЙСТВА ПРИБЛИЖЕННЫХ РЕШЕНИЙ И СХЕМЫ ИХ ПОСТРОЕНИЯ В ЗАДАЧАХ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Специальность 05.13.01 — Системный анализ, управление и обработка информации (информационно-вычислительное обеспечение)

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

003470689

Москва, 2009

003470689

Работа выполнена в Учреждении Российской академии наук Институте системного анализа РАН в Центре Грид-технологий и распределенных вычислений

Научный — доктор физико-математических наук, профессор

руководитель Афанасьев Александр Петрович

Официальные оппоненты

— доктор физико-математических наук Антипин Анатолий Сергеевич

— кандидат физико-математических наук Швецов Владимир Иванович

Ведущая организация

Учреждение Российской академии наук Институт проблем управления им. В.А. Трапезникова РАН

Защита диссертации состоится июня 2009 года в _Ц_ часов на заседании диссертационного совета Д 002.086.02 при Учреждении Российской академии наук Институте системного анализа Российской Академии наук, по адресу: 117312, Москва, проспект 60-летия Октября, 9.

С диссертацией можно ознакомиться в научной библиотеке Учреждения Российской академии наук Институте системного анализа Российской Академии наук (г. Москва, проспект 60-летия Октября, 9).

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 117312, Москва, проспект 60-летия Октября, 9, диссертационный совет Д 002.086.02.

Автореферат разослан "_7_" мая 2009 года.

Учёный секретарь диссертационного совета доктор технических наук, профессор

Пропой А. И.

Общая характеристика работы

Актуальность темы диссертации. В теории и практике численных методов оптимизации часто приходится иметь дело не с точными, а с приближенными решениями, которые удовлетворяют ограничениям задачи и критерию оптимальности с некоторой погрешностью. Поэтому для разработки формальных критериев остановки итерационных процедур, а также при анализе устойчивости решений относительно погрешностей в исходных данных или выполнения ограничений, было бы очень полезно располагать обоснованной характеризацией приближенных решений, независящей от специфики используемого численного метода. В работе строится теория необходимых и достаточных условий приближенной оптимальности в задачах математического программирования, обобщающая известные необходимые и достаточные условия точного оптимума.

Далее, большинство существующих численных методов оптимизации эффективны только для выпуклых задач оптимизации, хотя, при математическом моделировании сложных систем, часто возникают невыпуклые задач. В работе предлагаются схемы поиска приближенного решения таких задач в результате, также, возможно, приближенного решения аппроксимирующих выпуклых задач. Областью приложений предлагаемого подхода являются оптимизационные модели, в которых отказ от учета некоторых взаимосвязей или их упрощенное описание, приводит к более простым выпуклым задачам математического программирования.

Необходимость в приближенных решениях также может возникнуть при разработке систем управления автономными техническими системами в режиме реального времени. В работе рассматривается пример подобной задачи, связанной с разработкой алгоритма управления двигателями коррекции движения космических аппаратов.

Цели работы:

- получение конструктивно проверяемых необходимых и достаточных условий приближенного оптимума в задачах математического программирования;

- описание классов задач математического программирования, допускающих аппроксимацию выпуклыми задачами (разной степени приближения);

- разработка и исследование схем построения приближенных решений задачи на основе, также приближенного, решения аппроксимирующих выпуклых задач;

- разработка алгоритма приближенного решения одного класса задач линейного программирования в режиме реального времени.

Используемые методы являются типичными для теории и численных методов конечномерной оптимизации: функции Лагранжа и теория двойственности; свойства регулярности ограничений; понятия теоретически точных и приближенных численных методов; некоторые идеи численных методов линеаризации; аппарат линейного программирования. В основном, методика исследования базируется на опыте асимптотической теории возмущений задач математического программирования.

Научная новизна. Представленные в работе и опубликованные по теме диссертации результаты являются новыми.

Научная и практическая значимость работы. Предложенные конструктивно проверяемые необходимые и достаточные условия приближенных решений, а также, схемы построения этих решений, могут быть использованы в разработке численных методов анализа широкого класса оптимизационных моделей. Представленный алгоритм приближенного решения задачи линейного программирования использовался в программных системах поддержки начальных этапов проектирования космических аппаратов.

Результаты, выносимые на защиту:

- необходимые условия приближенного оптимума первого порядка для гладких задач, обобщающие правила множителей Лагранжа для точных решений;

- достаточные условия приближенного оптимума для гладких задач, на основе предположений о выпуклости или остроте минимума функции Лагранжа;

- классы невыпуклых и, вообще говоря, негладких задач, близких, в оптимизационном смысле, к выпуклым задачам математического программирования;

- методы построения приближенных решений невыпуклых задач на основе решения аппроксимирующих выпуклых задач (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]. Семинаре ИСА РАН по численным методам и распределенным вычислениям. Апробация алгоритма построения приближенного решения задачи линейного программирования проводилась в исследовательских проектах Европейского космического агенства (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] - предложение использовать параметрический симплекс метод в сочетании со специальным алгоритмом определения начального базиса для построения приближенного решения одного класса задач линейного программирования; программная реализация численного метода и анализ результатов вычислительных экспериментов.

Структура и объем диссертации. Диссертация изложена на ¡40 стр. и состоит из оглавления, введения, пяти глав, разбитых на параграфы (с автономной нумерацией внутри главы), заключения, списка литературы из (64_ позиции, упорядоченные по алфавиту) и списка из JJ_ рисунков. В основном, используется двойная нумерация: вначале - номер параграфа (внутри главы), затем - номер формулы, определения, условия или утверждения в этом параграфе. Для следствий или замечаний к теоремам используется тройная нумерация - двойной номер теоремы и номер следствия или замечания. В номерах формул и определений Введения используется буква "В". При ссылках, выходящих за рамки главы, указывается номер главы, содержащей эту ссылку. Нумерация рисунков двойная: номер главы и номер рисунка.

Краткое содержание работы

Во Введении обоснована актуальность работы, сформулированы основные цели работы и обоснована се научная новизна. Параллельно с этим вводятся основные понятия и обозначения. Предметом исследования являются приближенные решения задач математического программирования следующего вида (в евклидовом пространстве К"):

где X - выпуклое замкнутое множество, I и Л - конечные множества индексов ограничений, ,7, /,-, д, - непрерывные числовые функции на X. Введем обозначения: - для значения "точного" оптимума и множества оптимальных решений в задаче (V)

- функций нарушения ограничений и нарушения оптимума в задаче (Р), опредс-

ленных на X (для уеК1,у*-«^1, У~=У+~У, Л+(*)=[Л(*)]\ /Г(*)-Л+(*)-Л(*)):

Д(х)=^тах-| тах/4+(1),щах|^(1)| > ,<г(х)= тах{(,7(а:)-Д)+, Д(х)} . (1)

Исходными данными задачи (Р) назовем набор {£ (г'е1), щ (;/е.Т), X], задающий целевую функцию и ограничения. Свойства исходных данных используются для классификации исследуемых типов задач (V). Выпуклыми будут называться задачи с выпуклыми данными; гладкими - задачи, исходные данные которых являются непрерывно дифференцируемыми с липшицевыми производными, причем, и т.п.

Для ¿>0, множествами 6-допустимых и 5-оптимальных решений (Р) являются:

<?4= {хсХ : Д(х)«<5}, Мг= {хед{ : = {хсХ : <т(1)«:5}. (2)

Данное определения приближенного решения является содержательным только если значение минимума в задаче (V) является устойчивым относительно нарушения ограничений. Если положить ^(х):хеС2}}, то это означает, что 1|тД((5)=Д.

В теории возмущений экстремальных задач, используется важное понятие нормальности ограничений задачи, которое, в частности, гарантирует устойчивость оптимального значения. Рассмотрим для этого семейство множеств <2[(] и функций нарушения Д[£](х), зависящих от векторного параметра (= ({&}«=[, {т^}^) :

Будем говорить, что ограничения задачи (V) являются нормальными на некотором множестве МсХ, с константой С (зависящей, вообще говоря, от исходных данных задачи и множества М), если для некоторого <1>0 для всех хеМ и С>||С1Н^> выполнена оценка расстояния: (^(г, С?[С]) ^ СД[С](э:). Для конструктивного задания условий, гарантирующих нормальность ограничений, в работе используются различные модификации условий Слейтера. Иногда, удобнее использовать более слабое свойство равномерной оценки расстояния на множестве Мс:Х, с константой С: ЧхеМ,<1ы(х,С1)г£СА(х).

1 Стандартное условие об отсутствии "переопределенное™" ограничений-равенств, т.е. |^ < п, всегда предполагается выполненным без дополнительных оговорок

J(x)—nmn,xeQ, где д= {геЛсК" : /¡(х)$0 (ге1), 0 О'е.))}

(Г)

Д= {: ге(Э}, М= {геС? : J{x) = Д};

<3[С]= {хеХ:/,(х)+^0 (ге1), а(х)+%=0 (¿еЛ)};

Отмечается, что хотя проводимое исследование и базируется на опыте асимптотической теории возмущений в параметрических задачах оптимизации, развитой в работах Е.С. Левитина (в 80-х годах), его целью является построение конструктивно проверяемых критериев приближенной оптимальности и оценок точности в случае малых, но не "бесконечно малых" нарушений ограничений или возмущений исходных данных задачи (Р) , которые могут и не иметь явного параметрического представления. Например, в Гл. I для конструктивного вычисления множителей Лагранжа, соответствующих точке, исследуемой на приближенный экстремум для гладких задач, предлагается решать специальную задачу квадратичного программирования, где применимы конечные численные методы. В главах II-IV для оценки точности решения невыпуклой задачи на основе ее выпуклых аппроксимаций, используются не точные, а приближенные решения аппроксимирующих задач. В главах II и III предлагается специальная уточненная форма известного модифицированного условия Слейтера, допускающая проверку в результате приближенного решения вспомогательных выпуклых задач.

Далее, формулируется проблема характеризации приближенных решений, исследуемая в Гл. I. Речь идет о необходимых условиях 5-оптимума, т.е. выполнения для некоторой точки хеХ включения хеМз, а также, о возможности для некоторой g-допустимой точки xeQe гарантировать включение xeMg, S^g (достаточные условия 5-оптимума) для ненулевых значений погрешностей д,5. В Гл. I приводится аналоги известных необходимых и достаточных условий точного оптимума на случай приближенных решений, как в самой задаче (Р), так и в двойственной к ней. Основные результаты Главы I были анонсированы в работе [3].

Во введении приводятся определения двух классов, вообще говоря, негладких задач, допускающих аппроксимацию выпуклыми задачами, найти решение в которых, тем более - приближенное, существенно проще, чем в исходной невыпуклой задаче.

Скажем, что функции J, /; обладают выпукло-аддитивным представлением с выпуклыми на X функциями Fi(x) и некоторыми возмущениями Fi(x) (iel°), а функции gj - аффинно-аддитивным представлением с аффинными на X функциями Gj(x) и возмущениями Gj{x) (jeJ), если J(x)=F0(x) +F0(z), Ji(x)=Fi(x) +Fi(x) (iel), gj(x)-Gj{x) +Gj{x) (je.I), где функции Fi(-),Fi(-) и Gj(-),Gj(-) непрерывны на R" для всех значений индексов iel"= {0}(jl и jeJ- Для краткости будем говорить, что в этом случае исходные данные (Р) допускают выпукло-аддитивное представление. В этом случае естественной аппроксимацией (Р) является следующая выпуклая задача:

{хеХ : 0 (iel), g<°>(х)=0 (jeJ)}, где (0)

^°>(х)^(х)Л°:(х)^(х) (ге1),д?>(х)^(х) (jeJ). '

Задача (pio)) далее называется задачей нулевого приближения для (Р). Результаты оценок оптимума задачи (р) по приближенному решению задачи нулевого и более высоких степеней приближения приводятся в Гл. II.

Класс задач (Р) с выпукло-аддитивным представлением исходных данных, рассматриваемый в Гл. II, не охватывает многие невыпуклые задачи, где возмущения некоторых ограничений входят через суперпозицию с негладкими выпуклыми функциями типа нормы или максимума по конечному или бесконечному множеству параметров. Например, одно из функциональных ограничений может иметь вид fi(x)=\\P(x) + где Р-Ж1—>U, линейный оператор со значениями из некоторого нормированного пространства U, а значения малы по норме V для хеХ. Поэтому в Гл. III исследуется значительно более общий, по сравнению с указанным выше, класс оптимизационных задач,

близких к выпуклым.

Скажем, что функции J, обладают выпукло-суперпозиционным представлением с функциями J~i{x, Uij и операторами u,{-) (¿el"), а функции gj обладают аффинно-суперпозиционным представлением с функциями Gj(x,Vj) и операторами Vj(-) (jeJ), если:

- указанные функции имеют вид J(x)=Jr0(x,u0{x)), /¡(x)=^(i,Ui(i)) (rél), aj{x)=Q0(x,Vj(x)) (jeJ), где функции Ti являются непрерывными на XxUit геГ, Çj - непрерывными в XxVj для всех jeJ, а и Vj(-) - непрерывные операторы из М" в нормированные пространства {/, и V^ соответственно;

- существуют малые положительные числа ç™ такие, что для любых фиксированных векторов Uielti (геГ), t^eV,- (ieJ), где

Vj^ iOvJufaeVj : Ы^, vj=vj(x), хеХ), функции fi(-,Ui) являются выпуклыми на Л?, а функции^-, и,-) на множестве Л1 совпадают с некоторыми аффинными функциями на R". В этом случае задача (Р) близка (по исходным данным) к следующей задаче выпуклого программирования: JM(x)±?0(x, 0[/„) - min, xeQla), где (2<°>={теЛГ: ^(x.O^O (fei), (jeJ)} , >

которую мы также назовем задачей нулевого приближения для задачи (Р). Для этого класса задач (Р), результаты оценок оптимума по приближенному решению задачи нулевого, и более высоких степеней, приближения приводятся в Гл. III.

В четвертой главе приводится несколько примеров задач, на которых иллюстрируется применение схем построения приближенных решений, изложенных а главах II и III.

Основные результаты глав 1I-IV были опубликованы в работах [ 1,2,4,5].

В Гл. V описывается алгоритм нахождения хотя бы приближенных решений для одного класса задач линейного программирования в режиме реального времени. Хотя исходной задачей оптимизации здесь является задача ЛП с непрерывными переменными не очень большой размерности, необходимость получить "технически" приемлемое решение в условиях ограниченной вычислительной мощности и лимита времени не позволяет непосредственно применить стандартные вычислительные процедуры типа симплекс-метода. А известные быстрые эвристические алгоритмы, например, Martel F. (2003), используют слишком грубое упрощении исходной задачи. При том, что примененный аппарат (теория и методы линейного программирования) кардинально отличается от того, что использовался в главах II-IV, поиск приближенного решения также сводился к решению упрощенной (за счет отказа от части ограничений) вспомогательной задачи. Содержание главы отражает часть результатов, опубликованных в статьях [6], [7].

В первой главе, "Условия приближенного оптимума", приводятся необходимые и достаточные условия приближенных решений, основанные на использовании функции Лагранжа задачи (Р) и соответствующей двойственной задачи. Введем вектор множителей Лагранжа и= (ос, ß), cxeRl1', ßeR|Jl (оц соответствует ограничению /¡(i)^0, a ßj -ограничению дДэ:)=0) и функцию Лагранжа задачи (Р)

L(x,u>)±J(x) + LX/.W +

tel je J

В этих обозначениях двойственная задача имеет вид

v(u) max, wei), где П={ш: a,>0(ieI),ßeMlJl}, u(u)=min{L(x,u) : хеХ}. ( '

Обозначим: ¿>i sup {v(ui) : o>efi} - оптимальное значение задачи (P') (легко видеть, что всегда П - множество точных решений; П{== {и«Л : г)(ш)^г>-5} - множество 5-оптимальных решений (Р'). Вектора двойственных переменных а/еП трактуются как элементы конечномерного пространства с нормой (напомним, что а ^ 0)

Mi-E«< + Elfcl=Mi + IPIi-

ге[ jeJ

Для конструктивных оценок важно, чтобы множества i)j были бы ограниченными с некоторыми параметрами d^O, W^O : flwHj^W VweHj, S^d. Для выпуклой конечномерной задачи (Р') это свойство выполнено если множество П ограничено. В работе это обеспечивается условиями Слейтера.

В Параграфе 1.1 для обобщения известных необходимых и достаточных условий оптимальности в форме седловых точек функции Л агранжа, вводится функция (ниже, чтобы подчеркнуть зависимость множителей oq и от рассматриваемого вектора и, используются обозначения и ВДш])

£(X,UJ)=L(X,UJ) -v(u) +2Х[о;]/Г(а:). (3)

¡el v '

Непосредственно из определений следует, что для всех (x,ui)eXxQ: £{х,

£{x,w) = л^-^М+Е^М/^М+ЕР МэЛхУ, •el jeJ

vM-lwljAixJiJi^^t'M+^.^+IPHIIi^)-

Если для задачи (Р) выполнено соотношение двойственности (Д=г>), то £(х'о,шо)=0, V (x0,u0)eMxQ.

В теоремах 1.1, 1.2 и 1.3 показано, что малость значения неотрицательной функции £(х, ш) является характеристикой 5-оптимума на прямом произведении QgxQ в задачах (Р) и (Р) . Это позволяет указать необходимые и достаточные условия ¿-оптимума, аналогичные условиям известным теоремам о седловых точках функции Лагранжа. Теорема 1. (необходимые условия 5-оптимума) Пусть в задаче (Р) выполнено соотношение двойственности и, для некоторых 5^0,5'^0, известны xseMs,oJi'SVlsi. Тогда £(xs,us-)^ (l+llwyflj) 5+5'. Если, к тому же, задача (Р') является ограниченной с параметрами d,VJ и S'^d, то £{xs,us>(1 + W) 5 + 5'.

Следующее утверждение далее используется для получения достаточных условий приближенного оптимума в случае гладких задач, которому посвящены параграфы 1.21.5. Заметим, что соотношение двойственности не требуется. Дана упрощенная формулировка, для случая ?1Ф0.

Теорема 2. (достаточные условия 5-оптимума) Пусть р>0 - некоторое, вообще говоря, малое число, xeQp, ш= (а, (3) efl. Далее, пусть для некоторого cj0efl известно число W, причем ^„¡j^W, и для некоторого, необязательно малого, е^О, выполнено неравенство £(X,CJ)^E.

Тогда xeMs, шейр и J(x)-p.^.-(р.-Р)-5'-р\\и>[|,, где 5=max{p,£+p[|P[|l}, 5'=е+р (IPI^+VK). Если, к тому же, xeMaQp и для множества М известны следующие константы: С - из оценки расстояния dist(x, Q)^CA(x) и Аа - константа Липшица целевой функций J на рС-окрестности М, то зазор двойственности допускает оценку (i - ¡/^ЛоСр+е+рЦЗ^.

Будем называть задачу (V) гладкой, если (отсутствуют нефункциональные

ограничения), а все функции J, f{ (iel), gj (js J) непрерывно дифференцируемы на некоторой окрестности точек, проверяемых на оптимальность. Поскольку нас интересуют приближенные решения, то речь в дальнейшем будет идти о некотором множестве Mi, где величина d задает максимально допустимую погрешность оптимального решения.

Параграф !.2 посвящен общей схеме необходимого условия ¿-оптимума в "дифференциальной форме" для гладких задач в условиях равномерной оценки расстояния на Mi с некоторой константой С. Ставилась цель получить обобщение известной теоремы Каруша-Джона (W. Karush (1939), F. John (1948))'. Согласно этой теореме, если точка х„ является решением задачи (Р) и в некоторой окрестности этой точки все функции J, fi (¿el), gj (jeJ) непрерывно дифференцируемы, то существуют число 0 и вектор ы„еП, «o+|iiVj|i=1. такие, что, во-первых,

«оЧ7(х0) + XXK]v/,(x0) + £ №„N.,(0 = 0 (4ч

И jeJ ' '

и, во-вторых, выполнены условия дополняющей нежесткости

= 0. (5)

iel 4 '

Иногда, учитывая сходство этого утверждения с теоремой Куна-Таккера для выпуклого программирования, и ряд исторических причин (см. первый том монографии А. Схрсй-вера (1991)) теорему Каруша-Джона называют теоремой Каруша-Куна-Таккера.

Практический интерес представляет регулярный случай, когда вуравнении(4)мож-но гарантировать, что <хо^0, иначе, это равенство является лишь признаком вырожденности ограничений в точке х0. В литературе приводятся различные дополнительные предположения о регулярности ограничений задачи (Р) . Обычно, для гладких задач, в исследуемой на экстремум точке хеQ, предполагают выполненным т.н. условие регулярности ограничений, т.е. линейную независимость векторов градиентов щ{х) (jeJ) и существование вектора г.,, {г,||=1, для которого (vfi(x),xa}<0 (для всех ¿si, где U[x)=0) и (щ(х),хв)=0 (jeJ). В этом случае из теоремы Каруша-Джона следует хорошо известное необходимое условие локального оптимума первого порядка:

47[¡»'о]УЛ(х0) + 2 Pi[^о](lo) = =0, £аф<,]Л(£») = 0. (6%

¿el jel iel 4 '

В начале Параграфа 1.2 приводится вариант теоремы об условиях точной оптимальности первого порядка (Теорема 1.2.2), отличающийся от теоремы Каруша-Джона более сильными предположениями о гладкости функций J, /; (¿el), gj (jeJ) (локальная лип-шицевость градиентов) и явным предположением о равномерной оценке расстояния в окрестности оптимального решения (вместо условия регулярности ограничений). Теорема демонстрирует новую форму необходимого условия оптимальности и другой способ доказательства, которые далее используется для приближенных решений. Показано, что если точка х„ является точным решением (Р), и на некоторой се окрестности выполнена оценка расстояния с некоторой константой С, а все функции J, /¿, gу непрерывно-дифференцируемы с липшицевыми производными, то существуют вектор u^efi, для которого 2

(io)=0 (7)

l£l

' Несмотря на то, что теорема Каруша-Джона была сформулирована для нелинейных невыпуклых задач в 1939 году, исследованиями в этой области продолжаются до сих пор (Ыешшиег А., БсЫсЫ Н. (2003))

Важно, что этот вектор множителей Лагранжа соответствует точному решению следующей задачи квадратичного программирования (сходной с основной вспомогательной задачей численного метода линеаризации Б.Н. Пшеничного):

(vj(x0),x) + i¡|x||2 -> min.xeR" ~/Г W + <^(х„),(¿el), (щ(ха),x) = 0 (jeJ), W

двойственной к которой является, также квадратичная, задача

- 5ХМ/Г(хо) max, weíl, (9)

¿el

Заметим, что для x0eQ равенство (7) эквивалентно необходимому условию локального точного оптимума (6). Теорема 1.2.2 указывает конструктивный способ определения множителей Лагранжа, соответствующих точному оптимуму (Р), в результате решения вспомогательной выпуклой задачи квадратичного программирования (9), для которой известны конечные точные численные методы.

Вид утверждения и общая схема доказательства приведенной теоремы используется для формулировки необходимых условий приближенного оптимума. В качестве количественной характеристики í-оптимальности предложено использовать функцию е(х), определенную для любой точки х и равную оптимальному значению в следующей задаче квадратичного программирования

+ (Ю)

всегда имеющей непустое множество решений П0[х], е(х) конечно и неотрицательно.

В Теореме 1.2.3 показано, что функция е(х) позволяет обобщить известные необходимые условия точного локального минимума (в форме (6)) на случай приближенных решений. Приведем упрощенную формулировку.

Теорема 3. Пусть для некоторых d>0, г> 0 имеет место равномерная оценка расстояния для ограничений задачи (Р) на множестве Md (с константой С) и равномерная локальная липшицевость производных функций J, f¡ (¿el), g¡ (je J) на B(Af¿, r) (r-окрестности множества Md).

Тогда, если <5< min{f, ¿g}, то для произвольной точки x¡eMs выполнена следующая оценка

е(х,)«сЕ (d,r)S, (11)

где константа Е(d,r) зависит только от значения С и параметров гладкости исходных данных задачи (V) на В (Md, г).

Таким образом, если точка x¡ является ¿-оптимальным решением задачи (Р), то значение e(x¡) имеет порядок малости 0(<5), т.е. существует вектор множителей Лагранжа й0[х^]еП0[хл]сП, такой, что

¿КЛи.еф,])!2 +Z«i[¡D„[xí]]/r(s() = 0(6). (12)

«el

В случае точных решений х0еМ, когда 5=0, указанное необходимое условие эквивалентно классическим условиям оптимальности первого порядка (6). В следствиях к Теореме 2.3, приводится обобщение свойств дополняющей нсжесткости (5) и понятия "активных" ограничений на случай приближенных решений.

Следствие 3.1. Пусть в условиях Теоремы 3 известны числа Л; (tel) такие, что для любой точки хеМв ||v/;(x)|i.A;. Определим для точки х5 подмножество "приближенно активных" индексов ограничений-неравенств l[xs,5]= {tel: Тогда Vief!0[ii] => сф]=0 Щ[х&> <$].

Теорема 3 использует предположение о равномерной оценке расстояния до множества Q для точек из Mi с некоторой константой С. В §1.3 формулируются условия, позволяющие оценить значение С. Для этого известное условие регулярности ограничений, обобщается на случай приближенно-допустимых решений.

Скажем, что в точке х выполнено обобщенное условие регулярности с параметрами es>0,6,>0, если существует вектор такой, что

-fi~{x)+(vfi(x),xs)^-ct (iel), {vgj(x),ïs)= 0 (jc.I), а строки "горизонтальной" |J|xn-матрицы Г(х)=({щ(х) (j'eJ)})T линейно-независимы, причем норма пссвдообратной пх|,1|-матрицы Г#(х)=Г(х)т(Г(х)Г(х)т)-1 не превосходит числа 63.

Для xeQ это условие эквивалентно "обычному" условию регулярности. В работе отмечается, что новое условие слабее другого, приведенного в книге Евтушенко Ю.Г. (1982), обобщения условия регулярности для точек x£Q. Если эти условия выполняются на некотором множестве M с общими оценками параметров е, и 93, то будем говорить о равномерной регулярности ограничений на М.

Рассмотрим для некоторого d>0 множество d-допустимых решений, Qd и некоторое McQi- В Теореме 1.3.1, в предположениях о равномерной регулярности ограничений (Р) на M и равномерной гладкости функций-ограничений на окрестности множества М, получена равномерная оценка расстояния для точек из M до Q с некоторой константой.

В Теореме 1.3.2 и её следствиях устанавливается равномерная ограниченность множества П„[х] (решений вспомогательной задачи (10)) для всех хе Ai. В Теореме 1.3.3 доказано, что выполнение обобщенного условия регулярности в некоторой точке xeQ гарантирует свойство ограниченности приближенных решений двойственной задачи (V). Далее, в Параграфе 1.5, эти результаты используются для получения достаточных условий ¿-оптимальности.

В Параграфе 1.4 приводится понятие и некоторые свойства остроты минимума в задачах математического программирования, а также, понятие и свойства сильной выпуклости функций, далее используемые для получения достаточных условий приближенного оптимума, а также для свойств устойчивости приближенных решений.

Для фиксированного вектора шей введем обозначение .MH=Argmm {L(x, ш) : хеХ]. Пусть .Ми#0. Скажем, что на множестве X функция Лагранжа L(x,ui) обладает квадратичной остротой минимума с

константой j > 0, если L(x,u)^v(w) + 7^dist^x,M[tJ\j j VxeX.

В теории и численных методах оптимизации, часто предполагается сильная-выпуклость функции Лагранжа по х при данном и. Функция называется

сильно-выпуклой наХ с константой н>0, если для любых х', х"еХ и числа te[0,1]

L(tx' + (l~t)x",u) ïÇi£(x» + (l-i)£(x", ш) - ¿(l-iHzj-x;,!2.

В Параграфе 1.5 (теоремы 5./, 5.2), введенные выше функции £{x,cJ) и е(х), позволяют дать достаточные условия приближенного оптимума для гладкой задачи (V) , обобщающие известные достаточные условия точного оптимума, в условиях выпуклости, остроты минимума или сильной-выпуклости функции Лагранжа по переменной х.

Основной является Теорема 5.2. Она опирается на результаты §1.3 об ограниченности множеств решений вспомогательной задачи (10) и множества решений двойственной задачи (V) в условиях равномерной гладкости и регулярности ограничений задачи (Р). Ниже приведена упрощенная формулировка. Заметим, что использование вспомогательной задачи квадратичного программирования (10) придает конструктивный характер приведенным достаточным условиям приближенной оптимальности. Теорема 4. Рассмотрим некоторое множество MczQd, такое, что ограничения задачи (V) являются равномерно регулярными на М и равномерно гладкими на некоторой окрестности М.

Пусть xeMfiQp, где pt^d, и в результате решения вспомогательной задачи (10) найдены значение е(х) и некоторый вектор двойственных переменных ö0ei20[x]. Далее, пусть число W есть общая оценка норм вектора w0sü0[x] и некоторого вектора w„eQ. Тогда справедливы следующие утверждения.

(i). Если, для некоторого R>0, distal, и функция Лагранжа Ь(-,ш0) выпукла по х на шаре В(х, R), то xeMs и ¡даейр, где

5 = max jp, max |Я-^/2«{х),2е(х)|| + p-VJ, 8' = max ^R^/2e{x), 2ф)| +2p-W, (13)

(ii) Если функция Лагранжа Ь(-,ш0) выпукла по х и ее множество минимума .Мы имеет квадратичную остроту с константой у, то xeMs и ш„ейу, где

5 = max |p,max |l, c(x)j + р ■ W,J' = maxjl, ф)+2р ■ W; (14)

(iii). Если функция Лагранжа L(-,00) сильно выпукла по переменной х с константой х, то xeMs и ш0ей$>, где

8 = max {р, max {l, ¿} е(х)} + р ■ W,6' = max {l, е(х)+2р • W; (15)

В последнем Параграфе 1.6 приводится ряд утверждений, устанавливающих оценки точности приближенных решений по норме пространств переменных прямой и двойственных задач. Часть результатов используется далее в главах II, 111 и IV.

Во второй главе рассматривается класс задач (Р), исходные данные которых имеют вид "аддитивного возмущения" выпуклых или аффинных функций. Если задача (Р), в оптимизационном смысле, близка к выпуклой задаче 0-го приближения Р<0) (стр. 4), то приближенное решение Р^ позволяет оценить неизвестное оптимальное значение (Р) и локализовать множество ее оптимальных решений в окрестности xf \ В Параграфе II. 1 формулируются строгие условия, обеспечивающие такую возможность. Ниже, для пересечения окрестностей радиуса г произвольной точки х с множеством X используется обозначение Вx(x,r)±{x?eX : ||х-х'||<г}.

Условие II.1.1. Существуют числа ке[0,1), х^О такие, что значение (1—к)~1х является малой величиной и для всех хеХ верны следующие импликации

Я(х)>0=» П(х)&-кЯ(х)-х, геI, (16)

В диссертации приводятся примеры, показывающие, что такое условие более слабым, чем предположение о малости возмущений F¡, в, на всем множестве X.

Стандартное модифицированное условие Слейтера для ограничений выпуклой задачи Т^ дано в форме уточненного модифицированного условия Слейтера, удобной для проверки численными методами выпуклой оптимизации. Рассмотрим для этого в пространстве 4'1' шар единичного радиуса относительно нормы Этот, т.н. крестовый многогранник, является выпуклой оболочкой 2|Л| векторов ск (¿=1,2,.. .,2|Л|), совпадающих с точностью до знака с элементами стандартного ортонормированного базиса в пространстве М^1.

Условие II. 1.2. Для ограничений задачиР^ существуют числа г, <; > 0 и набор точек хкеХ (к=1,2,.. .,2\3\),хеХ такие, что

^'(х^ге*, А:=1,2,.. .,2|Л| и /¡"'(х)^ — ге1, 4°>(х)=0,

Условие 11.1.3. Оптимальное значение задачи конечно, множество ее оптимальных решений непусто и состоит из единственной точки, т.е.

{^0){х) : хе<2<°'} >-оо, : хе<Э<°>} Ф0 и {х'"»}.

Это условие гарантирует устойчивость решений задачи при нарушении ее ограничений в следующем смысле: для всех определена функция

р(5)=8ир{||х-х(<,)||: хеМ{р) , причем Нтр((5)=0. (17)

Пусть для найдена (и зафиксирована) некоторая точка х^еМи указано некоторое, необязательно малое, число г>0. Сформулируем предположения о малости возмущений О'еЛ) (вместе с их константами Липшица) на Влг(х^), г).

Условие 11.1.4. Существуют малые числар^О (геГ), р^О (ге1)и<^,д^0 (,?еЛ) такие, что для произвольных точек х, (х+х)бВЛ'(х^>, г) выполнены неравенства

геГ, ¿еЛ,

|^(х+х)-^;(х)|^р;||х||, ге1, |5,(х+х)-<5;(х)| ¿еЛ.

Удобно ввести обозначения для характеристик малости возмущений ограничений задачи:

^ = тах |^. тах {р,}, ш |; сг'= шах |тах {р',}, тах

Й}}- (»8)

Условий II. 1.1-4 достаточно, чтобы далее в Параграфе 11.4 получить оценки точности оптимума в исходной задаче (V) по приближенному решению задачи .

Далее, в Параграфе 11.1, для более точной аппроксимации вводится еще одно Условие 11.1.5. Существует малое неотрицательное число такое, что для произвольных точек х, (х+х)еВх(х'(\г) выполнено неравенство

\р„(х+х)-]?о(х)\^А\\Щ-

Положим _ J<1'(i)=F0(i)+f'1'«,)> Я'Ч^ад+^'Ю (¿ei), gf\x)^Gj(x)+Gf)(x£') (jeJ) и сформируем следующую задачу выпуклого программирования, названную задачей первого приближения.

J<»{x)-*iш, xeQ<1'= {жеА': (fei), Sf (х)=0, (jeJ)}. (Р<1>)

Как показано далее, условия II. 1.1-5 гарантируют, что при малых значениях jfQ, d и d' множество допустимых решений задачи Vне пусто и, для достаточно малого <5] множество ее приближенных решений МJ1' содержится в некоторой окрестности xfK В этой окрестности погрешности аппроксимаций исходных данных задачи (Р) функциями Ja\ (iel") и g'1* (jsJ) малы по сравнению с величиной |х-х£' J и приближенное решение задачи (Ра>), вообще говоря, дает более точную оценку оптимума (Р), чем задача (Р(0)). Точные формулировки приведены в §11.5.

Далее, в Параграфе II. 1 приводится еще одно Условие И. 1.6. Функции Fi(-) (г'еГ), Cj(-) (jeJ) дифференцируемы, а причем их градиенты удовлетворяют условию Липшица на множестве Bx(xfJ, г) с малыми константами, т.е. существуют малые неотрицательные числа и 4\ такие, что для произвольной пары точек х, (х+х)еВх(хг) выполнены неравенства

|jvFi(x+x)-v^(x)|s:p;'fx| ,геГ, ||vG,-(x+x)-vGj JsJ.

Если выполнено это условие, то еще одним параметром малости возмущений, входящим далее в оценки Параграфа II.6, является величина

Приведенное условие гарантирует, что при любом хеВд^х^г)

« fei0.

^ ЫЦх-x^f, jeJ.

Выполнение Условия II. 1.6 позволяет указать аппроксимации 2-порядка. Положим: J^(x)=F0(x) + F„(x£>)+(vF„(x£>), х-х<°>) ,

+ (iel),

g?(х)Щ(х) +Gj(xZ>)+(vGj(x<;;),x-x£>) (jeJ). И сформируем выпуклую задачу второго приближения

Jcl\x)^min, xeQ<2>= {хеХ : /f'(x)<0 (iel), flf(x)=0 (jeJ)} . (Pf>) Обозначим через pi2) и Л4(5> оптимальное значение и множество оптимальных решений в задаче Р£2). В §11.6 будет показано, что если числа 50, d и d' достаточно малы, то из условий II. 1.1-5 следует, что Q<2V0, /¿(2)>-оо и

Ее приближенное решение (точка ¿2^0), как будет показано, позволяет получить, вообще говоря, более точные оценки оптимума в исходной невыпуклой задаче (Р) по сравнению с результатами первого приближения.

Обсуждению основных предположений посвящен Параграф II.2. В нем также приводится ряд утверждений о конструктивном способе оценки параметров регулярности ограничений задачи Р'°> в виде уточненного условия Слейтера (Условие II. 1.2) в результате приближенного решения специальных вспомогательных выпуклых задач.

Решающими для практического использования предлагаемого подхода являются, во-первых, получение оценок расстояния до множеств допустимых решений исходной и аппроксимирующих задач ((} и <2(1), С}[2)) в окрестности Вл-^'.г) и, во-вторых, количественная характеристика устойчивости приближенных решений этой задачи.

Получение требуемых оценок расстояния проводится в Параграфе П.З. Для конечномерного случая и Д"=К" подобные результаты имеются в книге Е.С. Левитина (1992). Однако, для замкнутости изложения и удобства читателя приводятся новые, более конструктивные результаты в конечномерном случае при Х^И", основанные на использовании уточненных условий Слейтера (Условие П. 1.2). Показано, что если выполнены условия 11.1.2, II.1.4 и 11.6, причем числа (I, ¿' (18) и в." (19) достаточно малы, то в указанной окрестности выполнена оценка расстояния до множеств С2(0), (3(1), <Зс2) и <2 с некоторыми, конструктивно определяемыми константами С(0), С(,), С<2) и С.

Устойчивость решений задачи 0-го приближения обеспечивается Условием II. 1.3 (единственность сеточного решения), а функция р(5) (17) используется для оценки диаметра множеств М1р для различных значений 8.

Оценки точности получения решения задачи (Р) в результате приближенного решения задач нулевого, первого и второго приближений приводятся, соответственно, в параграфах 11.4, II.5 и П.6(теоремы 11.4.1, II.5.1, П.6.1). Все доказательства проводятся по единой схеме. Поясним ее на примере задачи нулевого приближения, приведя упрощенную формулировку Теоремы 11.4.1. Обозначим через Д, константу Липшица выпуклой функции Р„(х) на .

Теорема 5. Пусть выполнены условия 11.1.1-3, 0 и для некоторого х^еМ^ справедливо Условие П.1.4. Далее, пусть значения р0, к, р[ (г'е1), qj, ^ О'еЛ), и 5„ (а, значит, и зависящие от них значения ¿ив.' см. (18)) достаточно малы. Тогда справедливы следующие утверждения: (I). Для величины р. имеет место верхняя оценка

где^=<р0+А0С{50+<1)-

(И). Выполнены включения г), где <?=(1-к)~' {¿„+х+£"(0)| и

г = р{50)+р{я).

(Ш). Выполнено неравенство г^ги для значения р. верна нижняя оценка

А>•Я°)Сгг!,)-=ч> = &о+Ро+А„0°Ч.

Таким образом задача нулевого приближения дает оценки точности "порядка" <50+0(р„+^) по (неизвестному) оптимальному значению Д в исходной задаче и "порядка" г=р{50+р0+й) по точности локализации неизвестного множества М-

В Теореме II.5.1 показано, что решение задачи первого приближения (с малой погрешностью ¿1), вообще говоря, повышает порядок точности по функционалу до (51+г-0 (напомним, что величина г, в свою очередь мала).

Аналогично, для задачи Т^в Теореме И.5.2 показано, что ее приближенное решение (с малой погрешностью <52), дает еще больший порядок точности по функционалу до

В третьей главе, рассматривается значительно более общий, по сравнению с Гл. II, класс оптимизационных задач, исходные данные которых допускают выпукло-суперпозиционное представление.

Общая структура изложения, формулировки утверждений и схемы доказательств Гл. III, в целом, аналогичны Гл. II с тем отличием, что для построения аппроксимирующих выпуклых задач используются различные аппроксимации операторов щ(-) и «,•(■), су-перпозицяонно входящих в ограничения (V).

В дальнейшем мы будем использовать следующие обозначения для окрестностей (радиуса р или q) нуля в нормированных пространствах С/;, Vj, а также для пересечения окрестностей радиуса г произвольных точек хеХ с множеством X : Bl',(p)= {uieUi: ||и;|| « р], Ву,(ч)= {VjeVj : М«:«?}, В*(х, г) = {х'еХ : Цг-х^г}. Все функции Ti,Gj предполагаются липшицевыми на множествах Вд;(:е,г) хВи,(р), Вх(х,т) хВц(?), для всех геГ, jej. Обозначим соответствующие константы Липшица функции Fi по переменным х и щ через AilX(x, г,р) и (ж, г, р) и, аналогично, константы Липшица функции Gj по переменным х и Vj обозначим через Bj)X(x,r,q) и Bj щ (х, r,q). Это означает, что для произвольных векторов х', х"еВх(х, г), и/, иА'еВиАр)

<Л,х(х,г,р)¡x"-x'||+A,„,(x,r,p)iUj'-tH'l, 15,(1", О -S, (¡f, v/)\ ß;>(x, г, q) |x"-x'||+ß^(x, г, q) Ц«/-VII-В Параграфе III.l вводятся необходимые определения и формулируются условия, необходимые для дальнейшего изложения. Рассматриваются задачи (Р) с выпукло-суперпозиционным представлением исходных данных, где операторы щ(-) (fei®), Vj(-) (jeJ) малы в некотором смысле. Например, их значения могут быть малы по норме нз всем X и локально удовлетворять на X условию Липшица с малыми константами (такое требование малости также является слишком жестким, и ниже, в Условии III. 1.1, оно существенно ослаблено).

Как и в Гл. II, все условия, используемые для формирования аппроксимирующих выпуклых задач и последующих оценок точности "выстроены вокруг" соответствующей выпуклой задачи 0-го приближения (на стр. 5). Предполагается, что оптимальное значение //01 в этой задаче достигается на некотором множестве Л41°>.

Условие III.1.1. Функции J, ft допускают выпукло-суперпозиционное представление с функциями Fi(x,Ui) и операторами и,(-) (fei®), а функции gj допускают аффинно-суперпоэиционное представление с функциями Gj(x, Vj) и операторами vj(-) (jeJ), причем функции Ti и Gj являются липшицевыми на любом ограниченном подмножестве.

Кроме того, существуют числа ке[0,1), х^О и множество Q такие, что QaQaX и для любого xeQ справедливы следующие импликации

Г,Ах, 0,л) >p<0^TJx, u0(x)) -;F0(x, Ос.) =5 -к [^(х,0у„) -/i<°>] -х,

Ti{x, 0^) >0=>Ti(x, щ(х)) -Ti{x, Oy,) > 0Vi) ~х, (fei), (20)

Gj(x, 0Vj) v,(x)) -Gj(x, Oy,) | €.k\G,{x, 4-х, O'eJ).

причем величина (1—к)~]х мала.

Условия III. 1.2 (уточненноеусловие Слейтера для ограничений выпуклой задачи PJ0)) и III. 1.3 (о единственности решения P'f> ) повторяют аналогичные условия Гл. II.

Пусть для некоторого малого числа 0 найдена (и зафиксирована) некоторая точка х'^еМ^ - приближенное решение задачи Р<">. Далее, пусть г>0, р™">0 (геГ), qj">О (je J) - некоторые, вообще говоря, малые числа. Сформулируем теперь предположения, связанные с малостью возмущений щ(-) (fei®), ^j(-) (jeJ) в окрестности точки

Условие III. 1.4. Существуют неотрицательные числа р,е[0,Р1"] (геГ), (i'el) и qje[0,<Ç™], q'j (jeJ) такие, что для произвольных точек x,(x+x)eBx(x(s°\r) выполнены неравенства

kWNPi fiel"). Ы^ШЯз O'eJ). т)

Ых+х)-щ(х)\\ ¿рЩхЦ (fei), ¡ц(х+х)-ч(х)1 < фЦ (jeJ), ^

причем величины р{, г,рг) Pi (tel*), , г,РГ) PÎ (fei)

и bj=Bj<Vj (х£\ г, <j]~) gj, Vj=BjiVj (x£, r, cf™) (jj (jeJ) являются малыми.

Как показано в Параграфе III.4, условия III. 1.1-III. 1.4 обеспечивают оптимизационную близость исходной задачи (Р) и выпуклой задачи 0-го приближения Т"-°] ■

Для того, чтобы на основе приближенного решения задачи Р<0) построить выпуклую задачу первого приближения (более точную аппроксимацию задачи (V) в окрестности точки ) используется следующее

Условие 111.1.5. Оператор и0(-) на множестве Вд^х^.г) является липшицевым с константой р/0, причем значение т!0мало, и для всех iel°,jeJ

существуют операторы vf':X-*Vj, со следующими свойствами:

uf>(xg)=u,(x<s% ^'Ю-чЮ. (22)

функции J\(x, ир(х)) являются выпуклыми на X, а функции Qj(x, ^''(х)) совпадают на X с аффинными;

существуют малые числа а['\ Ьр такие, что при любых хеВ* г) г.РГ) h(i)-aS,'(x)|«oS1'|i-xW|,

оператор uJ/'Q удовлетворяет на множестве Вх(х^,г) условию Липшица с константой L[u£''(-)] такой, что величина произведения

Ли .№,Г,РГ) 1№(-)]мала.

Условие III. 1.5 позволяет сформировать задачу первого приближения вида

J"ll)(x)=Tj(x, и£](х)) —» min, xeQ(1), где ц

gt1^ {хеЛ* : «i1'^)) «О (iel), öi (г, и^Ч^)) =0 D'eJ)} .

приближенное решение которой позволяет получить, вообще говоря, более точные оценки оптимума в исходной задаче (V) по сравнению с оценками по задаче Vf1.

Для дальнейшего повышения точности оценки fi необходимо иметь более точную аппроксимацию исходных данных задачи (Р) в окрестности точки xfj, что позволило бы сформировать выпуклую аппроксимирующую задачу 2-го приближения.

Условие III. 1.6. Оператор ис(-) является липшицевым на множестве г)

с константой р'0, причем значение r,p:jfa мало, и для всех ieГ, jeJ

существуют операторы up:X->Ui, vp:X~*Vj со следующими свойствами:

функции Ti(x, uf)(x)) являются выпуклыми на X, а функции Gj{x, vf\x)) совпадают на X с аффинными;

существуют малые числа af\ Ь?1 такие, что при любых хеВх(х{£, г)

г,РГ) h(x)-Uf (x)||^x-<f, 25

оператор «¡,2)(-) удовлетворяет на множестве условию

Липшица с константой L[uJ,2)(-)] такой, что величина произведения

А„„(<\л,рГ) LK2»(-)] мала.

При выполнении последнего условия задача 2-го приближения имеет вид

J<?>(x)±F0(x,u<2'(x)) -min,xeQ@\ где й

<Э(2>= {хеХ : ^(x,uf>(х)) $0 (¿61), =0 (jeJ)} . К ' '

В Параграфе Ш.2 обсуждаются основные предположения и условия Параграфа III. 1, относящиеся к выпукло-суперпозиционному случаю. Приводятся примеры функций, допускающих соответствующее представление. Отмечается, что во многих случаях исходные данные задачи (Р) могут быть приведеЕШ, как к суперпозиционному, так и к аддитивному виду. Выбор того или иного представления является неформальной процедурой. Способ аппроксимации операторов щ(-), »,•(■) также, вообще говоря, неоднозначен.

Здесь же приводятся примеры выбора операторов uf'(-) (¿еР). vf\-) (je.I) и (геР), O'eJ), соответственно, для задач 1-го и 2-го приближений. Например, когда в некоторой окрестности х(/> возмущения (i'el°), Vj(-) (jeJ) удовлетворяют условию Липшица с малыми константами, то все операторы и(/'(-), v^(') могут быть постоянными: и?(х)=щ(х£) (Й=Г); v?\x)^vj(xg) (jeJ). .

Далее, например, если для всех iel", jeJ функции Ti(x,Ui) являются выпуклыми по {х, и4} на X х Ui, функции Qj(x, v}) совпадают на множестве X х Vj с некоторыми аффинными функциями по {х, Vj}, а операторы щ(-), vj(-) дифференцируемы с липшицевыми производными vui(-), Wj(.) на некоторой окрестности х(г°', то в задаче 2-го приближения можно использовать линеаризованные в точке х1Р операторы:

t42,(x)^x£>)+vt^)(x-x£) vf (х)^(х£>)+™;Ю (х-х£>) (jeJ).

Результаты Параграфа III.3 обобщают результаты Параграфа II.3 об оценках расстояния для ограничений исходной и аппроксимирующих задач на случай выпукло-суперпозиционного представления. Как и в Главе II здесь, фактически, устанавливается нормальность ограничений исходной задачи (Р) и наличие соответствующих оценок расстояния, в т.ч. для аппроксимирующих задач Pf>, P'l) и Pf. Показано, что если выполнены условия II. 1.2, II. 1.4-6, причем соответствующие параметры малости возмущений достаточно малы, то в окрестности (указанной в этих условиях) выполнена

оценка расстояния до множеств Qco), Qt2) и Q с некоторыми, конструктивно определяемыми константами С(0>, С'1', С'2> и С.

В Параграфе Ш.4 показано, что при выполнении условий III. 1.1-4, приближенное решение задачи Р£0), вектор позволяет оценить оптимальное значение (Р) н

локализовать множество ее оптимальных решений. Соответствующая Теорема Ш.4.1 по формулировке и по способу доказательства аналогична приведенной выше Теореме 5.

В Параграфе III.5 приводятся оценки оптимума в исходной задаче (Р) по приближенному решению задачи Р'1', т.е. в результате нахождения вектора xf^eM^. Далее в

этом параграфе рассматривается вопрос о повышения точности оценки оптимума задачи (V) при переходе к задаче I -го приближения. Дело в том, что все эти оценки, указанные в следствиях к теоремам III.4.1 и III.5.1 являются лишь мажорантами погрешностей - |А—и Поэтому даже если выполнены неравенства

е<"<£<">, то это еще не означает, что \ß-J(>)В Теореме III.5.2 приводятся простые достаточные условия повышения точности оценок при переходе к задаче (Р(1)). Приведем се сокращенную формулировку.

Теорема 6. Пусть е(1)>0 и при некотором 7„е(0,1) выполнено неравенство

(1+7тогда |А-J'^Dl Содержательный смысл этого утверждения в том, что если в результате решения задачи 1-го приближения значение целевой функции "достаточно заметно" отличается от результатов решения задачи 0-го приближения, то это гарантирует улучшение точности оценок оптимума исходной задачи (Р).

В заключительном Параграфе Ш.6 приводятся результаты оценок точности по задаче 2-го приближения (Теорема III.6.1 и ее следствия). В Теореме III.6.2 формулируется достаточные условия повышения точности оценок оптимума (Р) по задаче Р® по сравнению с результатом приближенного решения задачи 1-го приближения, аналогичные по форме и содержательному смыслу приведенной выше теореме 6 (нужно проверить насколько сильно отличаются значения JT1'1^') и , .

В четвертой главе предлагаемые схемы построения приближенных решений в задачах, близких к выпуклым, демонстрируется на нескольких примерах.

Пример из Параграфа IV. 1 относится к случаю возмущений аддитивного типа. Рассматривается задача проектирования точки в евклидовом пространстве на невыпуклое множество, близкое к выпуклому - "слабо деформированнный" параллелепипед. Задача нулевого приближения декомпозируется на простые "одномерные" задачи, точные решения которых находятся в явном виде. Задача второго приближения является задачей квадратичного программирования минимизации квадрата евклидовой нормы.

В примере из Параграфа IV.2 исходная задача (Р) получена в результате певыпуклого и несепарабельного возмущения выпуклой блочно-сепарабельной задачи со связывающим линейным ограничением. Содержательной интерпретацией примера является известная в теории исследования операций вероятностная модель обнаружения некоторого объекта при ограничениях на время или иные ресурсы поиска (Морозов В.В., Сухарев А.Г., Федоров В.В. (1986)). Задачи нулевого и первого приближения имеют единственные решения, определяемые в явном виде при помощи необходимых условий минимума в выпуклом программировании. Количественная оценка свойства устойчивости приближенных решений задачи нулевого приближения использует свойство остроты минимума ее функции Лагранжа.

Два последних примера относятся к теории наилучших приближений и связаны с безусловной минимизацией негладкой невыпуклой функции, близкой к выпуклой, и демонстрирует результаты параграфов 4-6 Гл. III, когда Х=Х, I=J=0, т.е. Q=X. В этих примерах функция 3(х) является малым невыпуклым возмущением суперпозиционного типа выпуклой функции, причем это возмущение, вообще говоря, не имеет подходящего выпукло-аддитивного представления.

В Параграфе IV.3 рассматривается минимизация на X нормы близкого к аффинному оператора Ф(х), действующего из в нормированное пространство U, т.е. ^(аг) = ||Ф(а:)||(/. Предполагается, что оптимальное значение в соответствующей задаче

нулевого приближения равно нулю и выполнено простое условие, при котором единственный минимум задачи нулевого приближения является острым. Приводится вид аппроксимирующих задач первого и второго приближений.

В Параграфе IV.4 целевая функция J(x) есть чебышевское отклонение числовой функции <E>(i), непрерывной на отрезке [—1, +1], от параметрического семейства

Ф(М)= S xki<k(t)+w(xj), к=1

где ipk(-) (fc=l).. .,n) — линейно независимые элементы пространства С [—1,+1], удовлетворяющие условию Хаара, т.е. образующие систему Чебышева на [-1, +1], а функция w(x, t) порождает малый гладкий оператор и(х)= •), te[—1, +1]} из К" в пространство С [—1, +1]. Таким образом

Подобные функции J{x) могут возникать при идентификации по чебышевскому критерию вектора параметров Ж" в нелинейной модели регрессии, близкой к линейной. Для анализа устойчивости оптимума в соответствующей задаче нулевого приближения используется чебышевский критерий оптимальности - теорема об альтернансе.

Пятая глава посвящена технической задаче управления двигателями коррекции ( ДК) движения космического аппарата (КА). Большинство современных КА, помимо т.н. маршевых двигателей, оснащены некоторым количеством (до трех десятков) сравнительно маломощных двигателей коррекции пространственной ориентации КА. Предметом исследования был алгоритм управления этими двигателями, обеспечивающий экономию топлива в ходе выполнения различных маневров КА и пригодный к исполнению бортовым вычислительным устройством.

В первом параграфе главы приводится техническая постановка задачи и ее формализация в виде задачи линейного программирования. В такой постановке (хотя и несколько упрощенной, но используемой на практике в работах: Bergmann E.V., etc. ( 1979); Crawford В. S. (1969); Martel F. (2003); Paradiso J. A. (1988)) функционирование системы управления системой из N двигателей, на каждом такте управления, сводится к решению задач ЛП следующего вида

стх —» min fx : Ах = uei5,0SxSl), (261

xeX" v '

где вектор с>0 и матрица А остаются постоянными, а и, вообще говоря, произвольный вектор, "заказываемый" системой управления верхнего уровня. Важно, что технические условия не гарантировали, что вектор и принадлежит множеству "реализуемых" управлений U= {ueR6 : u=Ах, О S х ä 1} •

В следующем параграфе формулируется эвристическая схема получения приближенного решения для задачи (26). Приближенного в следующем смысле: если система ограничений (26) несовместна или истек лимит времени, отпущенный на ее решение, то вместо решения (26) предъявляется оптимальное решение следующей задачи:

стх -» min {х : Ах = su, О S х g 1}, (27)

где величина скалярного параметра se[0,1] является критерием качества приближения.

Практическая эффективность схемы основана на весьма быстром (что подтверждено экспериментами и обсспечепо принципом работы) алгоритме, созданном соавторами [6, 7] и позволяющим очень быстро найти решение x<,[u] упрощенной задачи

стх -» min (х : Ах = u,x ä 0}. (28)

Однако, для относительно больших по норме и, простое масштабирование х„[и] максимальным значением s, для которого sx„[u]äl (F. Martel (2003)), не позволяло получить приемлемое приближенное решение исходной задачи (26).

Для "улучшения" найденного решения задачи (28), автором было предложено использовать известную итеративную процедуру параметрического симплекс метода, применяя се к задаче (27), где параметром является число s. На каждой итерации происходит целенаправленная (с целью увеличения s) смена базисов исходной задачи (26), причем начальный базис легко строится по найденному решению х„[и]. Результатом итерации является оптимальное решение задачи (26) для некоторого sku, sk^sk+l. Итерации совершаются до тех пор, пока, либо не будет исчерпан лимит времени, отводимый на построения приближенного решения, либо не будет найдено точное решение исходной задачи (st=1), либо не будет установлена ее несовместность. В последнем случае, алгоритм построит оптимальное решение задачи (26) для вектора shu (правой части ограничений), лежащего на границе множества реализуемых управлений U.

В третьем параграфе главы приводятся результаты вычислительных экспериментов, подтверждающих эффективность предложенного алгоритма на реальных конфигурациях существующих и проектируемых КА.

Основные результаты работы.

В диссертации проведено исследование свойств и схем построения приближенных решений для конечномерных задач математического программирования общего вида. Также рассматривалась проблема построения приближенного решения для одного класса задач линейного программирования в режиме реального времени. Были получены следующие основные результаты.

1. Для задач математического программирования общего вида даны необходимые и достаточные условия приближенного оптимума, обобщающие известные условия точного оптимума в терминах седловых точек функции Лагранжа.

2. Для гладких задач математического программирования сформулированы новые необходимые и достаточные условия приближенного оптимума, конструктивно проверяемые с помощью решения вспомогательной выпуклой задачи квадратичного программирования и обобщающие известные условия для точных решений (правила множителей Лагранжа и достаточные условия второго порядка).

3. Даны определения двух классов задач математического программирования, исходные данные которых имеют т.н. выпукло-аддитивное или выпукло-суперпозиционное представление, что обеспечивает их обоснованную аппроксимацию выпуклыми задачами различной степени приближения.

4. Для указанных классов задач сформулированы и исследованы схемы построения приближенного решения по результатам приближенного решения выпуклых аппроксимирующих задач (0-го, 1 -го и 2-го приближения) с конструктивными оценками точности нахождения оптимума в исходной невыпуклой (и, возможно, негладкой) задаче.

5. Общая идея использовать для поиска приближенного решения упрощенную вспомогательную задачу, для которой известен эффективный алгоритм решения, продемонстрирована на примере технической задачи выбора режимов работы двигателями коррекции движения космического аппарата, в результате, для одного класса задач линейного программирования предложена схема эффективного численного алгоритма получения приемлемого приближенного решения в режиме реального времени.

Список публикаций по теме диссертации

[ 1] Волошинов В.В., Левитин Е.С. Приближенная глобальная минимизация невыпуклых функций, близких к выпуклым // ЖВМ и МФ, 1997, Т.37, N7, С.771-784.

[2] Волошинов В.В., Левитин Е.С. Приближенный поиск глобального минимума в задачах математического программирования, близких к выпуклым // В сб. Труды 11-й международной Байкальской школы-семинара, Иркутск, Байкал, 5-12 июля 1998г. Том 1. - Иркутск, 1998, С. 192-105.

[3] Волошинов В.В., Левитин Е.С. Характеризация ¿-оптимальных решений в задачах математического программирования// В сб. Труды 11-й международной Байкальской школы-семинара, Иркутск, Байкал, 5-12 июля 1998г. Том I. - Иркутск, 1998, С. 69-70.

[4] Волошинов В.В. Левитин Е.С. Приближенный поиск глобального минимума в задачах математического программирования, близких к выпуклым // ЖВМ и МФ, 1999, Т.39, №3, с.386-417

[5] Волошинов В.В. Левитин Е.С. Построение приближенных решений в задачах математического программирования, близких к выпуклым. Препринт. ИСА РАН, Москва, 1999.88с.

[6] Ankerscn F., Wu S.-F., Aleshin A., Vankov A., Volochinov V., On Optimization oi Spacecraft Thruster Management Function (AIAA-2004-5133) AIAA Guidance, Navigation, and Control Conference and Exhibit, Providence, Rhode Island, USA, Aug. 16-19,2004.11 pp.

[7] Aleshin A., Ankersen F., Vankov A., Voloshinov V., Wu S. Optimization of Spacecraft Thruster Management Function. // AIAA Journal of Guidance, Control, and Dynamics, Vol. 28, No. 6, Nov.-Dec., 2005, pp. 1283-1290

Подписано в печать:

04.05.2009

Заказ № 1994 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение.

Цели работы.

Краткая характеристика содержания работы.

Сравнительный обзор содержания работы.

I Условия приближенного оптимума.

1.1 Условия приближенного оптимума на основе соотношений двойственности

1.2 Необходимое условие приближенного оптимума в дифференциальной форме для гладких задач.

Еще один способ доказательства необходимых условий 1-го порядка

Необходимые условия приближенного оптимума первого порядка.

1.3 Условия регулярности ограничений гладкой задачи.

Ограниченность множества приближенно-оптимальных множителей Лагранжа для равномерно гладкой и регулярной задачи (V)

1.4 Вспомогательные сведения об остром и квадратичном оптимуме.

1.5 Достаточные условия приближенного оптимума для гладких задач.

1.6 Свойства устойчивости 5-оптимальных решений.

Устойчивость множества приближенных решений для выпуклых задач . 52 Устойчивость множества приближенных решений относительно возмущения исходных данных

II Построение приближенных решений для случая аддитивных возмущений

II. 1 Основные предположения и общая схема поиска приближенного решения задачи ('Р).

Аппроксимация задачи (V) выпуклой задачей нулевого приближения.

Аппроксимация задачи (V) выпуклой задачей первого приближения.

Аппроксимация задачи (V) выпуклой задачей второго приближения.

11.2 Обсуждение основных предположений.

11.3 О регулярности выпуклых и близких к ним невыпуклых систем ограничений

11.4 Оценки точности по задаче нулевого приближения.

11.5 Оценки точности по задаче первого приближения.

11.6 Оценки точности по задаче второго приближения

III Построение приближенных решений для случая суперпозиционных возмущений 78 III. 1 Основные предположения и общая схема поиска приближенного решения задачи (V).А.

Аппроксимация задачи (V) выпуклой задачей нулевого приближения.

Аппроксимация задачи (V) выпуклой задачей первого приближения.

Аппроксимация задачи (V) выпуклой задачей второго приближения.

111.2 Обсуждение основных предположений и примеры классов невыпуклых оптимизационных задач, близких к выпуклым.

О классах функций, имеющих выпукло-суперпозиционпое или аффинносуперпозиционное представление.

Обсуждение предположения о "малости" суперпозиционных возмущений

О выборе операторов u^1^-), в задаче первого приближения.

О выборе операторов в задаче второго приближения.

О некоторых классах невыпуклых задач математического программирования, близких к выпуклым.

111.3 О регулярности систем выпуклых ограничений и их невыпуклых возмущений суперпозиционного типа.

111.4 Оценки точности по задаче нулевого приближения.

111.5 Оценки точности по задаче первого приближения.

111.6 Оценки точности по задаче второго приближения.

IV Иллюстративные примеры.

IV. 1 Проектирование точки на невыпуклое множество - "слабо деформированный" параллелепипед.

IV.2 Невыпуклая задача, близкая к выпуклой блочно-сепарабельной со связывающим линейным ограничением.

IV.3 Минимизация на выпуклом множестве в Еп нормы нелинейного оператора

IV.4 Выбор параметров в слабо нелинейной регрессии по чебышевскому критерию.

V Приближенное решение задачи линейного программирования в режиме реального времени.

V. 1 Краткая техническая постановка задачи и ее формализация.

Данная работа посвящена исследованию свойств приближенных решений в задачах оптимизации следующего вида

J(x) -> min, xeQ, . .

Q= {xeX : fi(x)^0 (iel), 9j(x) = 0 (ieJ)} 1 '

Здесь Л' - замкнутое выпуклое множество в евклидовом пространстве М"; I и J - конечные множества индексов, J, fi,gj - непрерывные функции на М™. Предполагается, что

2= inf {J{x) : xeQ} >-oo, ,M=Argmin {J(x) : xeQ} Ф0.

Выделение в задаче (P) нефункциональных ограничений вида хеХ связано с тем, что при поиске приближенных решений некоторые из ограничений xeQ должны выполняться точно (согласно содержательному смыслу задачи). Обычно, множество X задается простыми ограничениями на компоненты вектора х вида х^О или х™ш^хг^х™ах.

Исходными данными задачи (V) назовем набор {J, fi (ге1), gj (je J), X}, задающий целевую функцию и ограничения. Свойства исходных данных используются для классификации исследуемых типов задач (V). Выпуклыми будут называться задачи с выпуклыми данными; гладкими - задачи, исходные данные которых являются непрерывно дифференцируемыми с липшицевыми производными, причем, и т.п.

Введем для задачи (V) функцию нарушения ограничений xeQ, определенную на X :

Д(ж)=тах< тах[/г(ж)]+ ,max|gj(a;)| > (B.l) iel jeJ J здесь и ниже для числа у, [у]+ = тах{?/, 0}).

Определение В.1. Для произвольного S^O.чножеством 5-допустимых и множеством ^-оптимальных решений задачи (V) назовем, соответственно,

M5={xeQ5:J(x)^il+d} = {xeX:a(x)^5}, { где 0-(ж)=тах {\J{x)— р]+ , Д(ж)} - функция нарушения минимума задачи (Р).

Очевидно, что Q0=Q и Л40—Л4. Если 5>0 и хеМ.5, то число 5 будем называть точностью (или погрешностью) приблиоюенного решения задачи ('V) , которую дает точка х. Для дальнейшего полезно заметить, что хеЛ4а(х) УхеХ.

На приведенном ниже рисунке Рис. В.1 иллюстрируются различие между точными и приближенными решениями в случае

Нужно сделать одно замечание относительно приведенного выше определения приближенного оптимума (В.2). Оно учитывает только верхнюю оценку отклонения значения J{x) от точного оптимума Д, и, вообще говоря, является корректным только для случая, когда значение минимума в задаче (V) является устойчивым относительно нарушения ограничений [7,18].

Если оптимальное значение неустойчиво, то такая функция нарушения не отражает возможное сильное уменьшение целевой функции для 5-допустимых решений. Формально, можно было бы определить другую функцию приближенного оптимума jl{d), определенную для неотрицательных значений d по правилу

Стандартное условие об отсутствии "переопределенное™" ограничений-равенств, т.е. |Л| < п, будем всегда предполагать выполненным без дополнительных оговорок

J{x)<fi +S

J(xhP

Точные" решения

Приближенные решения

Рис. В. 1: Точные и приближенные решения (A"=R2

A(d)=inf {J(x) : хеХ, Д(х) ^ d), d ^ 0.

Очевидно, что p(d) ^ р для любого d^ 0 и функция p(d) монотонно неубывает при уменьшении d. Поэтому существует \х= lim p(d) ^ р, причем, вообще говоря, может оказатьd|0 ся, что (X < р (указанное значение р соответствует понятиям обобщенного решения (или минимизирующей последовательности) задачи математического программировали мером простой задачи, где р < р является следующая (здесь хеМ1,1 = {1},Л = 0):

Нетрудно видеть(см. Рис. В.2), что здесь Q = {0} и р = 1, но р = Иmp(d) = 0. В [7,18] d|0 можно найти другие примеры подобных ситуаций.

В теории возмущений экстремальных задач, например, в кииге [18], используется важное понятие нормальности ограничений задачи, которое, в частности, гарантирует устойчивость ограничений. Рассмотрим для этого семейство множеств Q[C] и функций нарушения Д[£](х), зависящих от векторного параметра С= ({&bei> {%bsj) :

Определение В.2. Будем говорить, что ограничения задачи {V) являются нормальными на некотором множестве с константой С (зависящей, вообще говоря, от исходных данных задачи и множества М), если для некоторого d>0 для всех хеМ и С, ЦСЦ^А выполнена оценка расстояния: dist(x, Q[C]) ^ СД[С](^).

Для конструктивного задания условий, гарантирующих нормальность ограничений, в работе используются различные модификации, т.н., условий Слейтера. Иногда, удобнее использовать более слабое свойство равномерной оценки расстояния на множестве М<=Л\ с константой С: VxeM, dist(x, Q) ^ СД (х). ния [7,18].

Q[C]= {xeX:fi(x)+ti^ («el), (jeJ)};

Д[С](х)=шах х[(/»(х)+^)]+,шах|^(х)+^| I

Рис. В.2: Пример неустойчивой задачи, 1 = Д > Д = О

Проверке выполнения свойств нормальности ограничений и оценки расстояния (при сделанных далее предположениях о невырожденности ограничений) будет посвящена значительная часть работы. Поэтому, с учетом сделанных замечаний, далее в работе будем использовать Определение В.1.

Цели работы

В связи с данным определением возникают следующие вопросы, решению которых и была посвящена работа.

Можно ли обобщить на случай приближенных решений известные необходимые и достаточные условия точного оптимума, использующие понятия функции Лагранжа? Мы ограничимся двумя типами таких условий: 1) на основе соотношений двойственности и седловых точек функции Лагранжа; 2) необходимые условия первого порядка "в дифференциальной форме" (правила множителей Лагранжа) и достаточные условия локальной оптимальности 2-го порядка.

В случае приближенных решений, речь идет о необходимых условиях 5-оптимума, т.е. условиях выполнения для некоторой точки хеХ включения хеЛ4$, а также, о возможности для некоторой ^-допустимой точки xeQe гарантировать включение хеМ.5, (достаточные условия 5-оптимума) для ненулевых значений погрешностей g, д.

Указанная проблема "характеризации" приближенных решений важна при анализе различных численных методов оптимизации. Дело в том, что многие численные методы решения задач математического программирования состоят в построении минимизирующих последовательностей ja^e-M^ j при 5^0. При этом, большинство известных автору строгих утверждений о свойствах обобщенных решений сформулированы в терминах предельных свойств таких минимизирующих последовательностей, [25,35,37,38,41]. Например; в книге [35] приводится пример вывода правила множителей Лагранжа, основанный на анализе свойств предельных точек последовательностей минимума модифицированных функций Лагранжа. В работах, посвященных численному методу линеаризации [37,38], теоретическое исследование метода, в частности, сводится к обоснованию выполнения необходимых условий оптимальности первого порядка для предельных точек минимизирующей последовательности.

По темам работ [4,5,13,32,33], можно видеть, что для разработки формальных "критериев останова" итерационных численных методов, а также при анализе устойчивости решений оптимизационных задач относительно погрешностей в исходных данных или выполнения ограничений, было бы очень полезно располагать обоснованной характеризацией 5-оптимума для исходной (и двойственной к ней) задачи математического программирования, независящей от специфики используемого численного метода. Разработке соответствующих условий приближенного оптимума посвящена первая глава диссертации.

Второй вопрос - можно ли предложить общие схемы получения приближенных решений исходных сложных задач в результате решения упрощенных, аппроксимирующих задач, для которых известны эффективные численные методы?

До сих пор, большинство численных методов эффективны только для выпуклых задач оптимизации, хотя, при математическом моделировании сложных систем, часто возникают невыпуклые задач. В работе предлагаются схемы поиска приближенного решения таких задач в результате, также, возможно, приближенного решения аппроксимирующих выпуклых задач. Областью приложений предлагаемого подхода является оптимизационные модели, которые в исходной (детальной или подробной) постановке приводят к невыпуклой задаче математического программирования. Рассматривается ситуация, когда, либо предварительный, вообще говоря - неформальный, анализ, либо физическое или экономическое содержание модели, позволяют, за счет отказа от учета некоторых взаимосвязей, получить упрощенную модель, оптимизация которой приводит к выпуклой задаче.

Дадим характеристику рассматриваемых в работе невыпуклых оптимизационных задач, "близких" к выпуклым задачам. Далее в Главе II. 1 данное определение будет существенно уточнено рядом дополнительных условий.

Определение В.З. Скажем, что функции J, fa обладают выпукло-аддитивным представлением с выпуклыми на X функциями Fi(x) и возмущениями Fi(x) (геГ), а функции gj - аффинно-аддитивным представлением с аффинными на X функциями Gj(x) и возмущениями Gj(x) (jeJ), если

J(x) = F0(x) +Fo(x), ft(x) = Fi(x) +Fi(x) (ieI), 9j(x) = G3(x) +Gj(x) (jeJ), где Fi(-),Fi(-) и Gj(-),Gj(-) - непрерывные функции на E" для всех геГ= {0} (JI и jeJ, функции Fi(-) являются выпуклыми на Х\ функции Gj(-) совпадают на множестве X с некоторыми аффинными функциями на М" (здесь и ниже аффинными будем называть фуикции^(ж) вида д(х) = (х*, х)+с, где ж*еЕ", ceR1).

Ниже предполагается, что функции Fi(-) (^1°), Gj(-) (jeJ) в некотором смысле малы например, малы по модулю и удовлетворяют локальному условию Липшица с малой константой на всем X (такое требование малости является слишком жестким и ниже, в формальных предположениях параграфа II. 1, будет существенно ослаблено).

Если функциональные ограничения задачи ('V) обладают выпукло-аддитивным представлением (с малыми возмущениями), то эта задача близка (по исходным данным) к следующей задаче выпуклого программирования:

F0(x)->mm, xeQw, где (о)

Q^={xeX: Fi(x)^0 (iel), G5(x)= 0 (jeJ)}, K ' которую мы назовем задачей нулевого приближения для задачи (V). В этом случае будем также говорить, что функции Fi(-) и Gj{-) являются малыми возмущениями аддитивного типа исходных данных задачи нулевого приближения.

Пусть для некоторого 6о^0 найден вектор а;^ - некоторое приближенное решение задачи нулевого приближения с точностью 50. Далее, пусть известны некоторые аппроксимации возмущений Fi(-) и Gj(-), соответственно, функциями и такими, что функции являются выпуклыми на X, a - на множестве X совпадают с аффинными, причем в некоторой окрестности точки xf^ погрешности этих аппроксимаций малы по сравнению с величиной Цж—ж^Ц. Тогда можно сформировать задачу выпуклого программирования, которую мы ниже называем задачей первого приближения. Приближенное решение этой задачи, как будет показано, позволяет уточнить значение оптимума в исходной задаче (V). Заметим, что если в некоторой окрестности точки x*gj возмущения Fi(-) (гб1°), Gj(-) {jtJ) удовлетворяют условию Липшица с малыми константами, то можно положить Щ1\х)^(х£), G?{x)=GA*ro) (<6Г, jeJ).

Пусть в некоторой окрестности точки известны аппроксимации возмущений Fi(-) и Gj(-), соответственно, функциями Fj2)(-) и Gf\-) такими, что функции Fi(-)+F^2) (■) являются выпуклыми на X, a - на множестве X совпадают с аффинными, причем в некоторой окрестности точки xf^ погрешности этих аппроксимаций малы по сравнению с величиной ||ж—ж^Ц2. Тогда, рассматривая эту, более точную, аппроксимацию возмущений в окрестности точки xlfj, можно сформулировать еще одну задачу выпуклого программирования, которую мы называем задачей второго приблиоюения. Ее приближенное решение, как будет показано, позволяет получить, вообще говоря, более точные оценки оп-, тимума в исходной невыпуклой задаче ('V) по сравнению с результатами первого приближения. Если, например, в некоторой окрестности точки xfj функции Fi(-), Gj(-) являются гладкими, а их градиенты в этой окрестности удовлетворяют условию Липшица с малыми константами, то можно положить

Ff>{x) = Fi{x%)+(vFi{x%),x-x%) (feH.

Класс задач (V), исходные данные которых обладают выпукло-аддитивным представлением, не охватывает ряд невыпуклых оптимизационных задач, также близких к выпуклым, в которых возмущения некоторых исходных данных выпуклой задачи входят через суперпозицию с негладкой функцией. К таким, в частности, относятся важные для многих приложений невыпуклые задачи полубесконечного и обобщенного полубесконечного программирования ([21]), близкие к выпуклым. Поэтому в работе рассматривается значительно более общий, по сравнению с указанным выше, класс оптимизационных задач, близких к выпуклым.

Определение В.4. Будем говорить, что функции J, ft обладают выпукло-суперпозиционным представлением с функциями х, щ) и операторами щ{-) (геГ), а функции gj обладают аффинно-суперпозиционным представлением с функциями Gj(x, Vj) и операторами Vj(-) (jeJ), если:

- указанные функции имеют вид

J(x) = Р0(х,и0{х)), /{(х) = Ъ(х,щ(х)) (ге!), д^(х) = Go(x,Vj(x)) (jeJ), где функции являются непрерывными на E.nxUi, г'еР, Qj - непрерывными в Enx Vj для всех jeJ, а щ(-) и Vj(-) - непрерывные операторы из Еп в нормированные пространства Ui и Vj соответственно; - существуют малые положительные числа pf, (fj"* такие, что для любых фиксированных векторов UiSUi (г'еР), v3eVj (jeJ), где

Ui={0Ut} \J [щеи{ : КИрГ, щ=щ(х), хеХ},

0v3} U {vjZVj : WvjW^cfp, хеХ] , функции щ) являются выпуклыми на X, а функции Qj(-, vj) на множестве X совпадают с некоторыми аффинными функциями на Еп. Ниже мы рассматриваем такие задачи (V) с выпукло-суперпозициоппым представлением исходных данных, для которых операторы иг(-) (iel°), Vj(-) (jeJ) малы в некотором смысле. Например, эти операторы имеют малую норму на всем X и локально удовлетворяют в X условию Липшица с малыми константами (такое требование малости также является слишком жестким и будет существенно ослаблено в параграфе III. 1). В дальнейшем, для краткости, будем говорить, что в указанной ситуации исходные данные задачи (V) имеют выпукло-суперпозиционное представление (с малыми возмущениями). В Главе III. 1 данное определение будет существенно уточнено рядом дополнительных условий.

Если функциональные ограничения задачи обладают выпукло-суперпозиционным представлением, (с малыми возмущениями), то задача (V) близка (по исходным данным) к следующей задаче выпуклого программирования: о(х, 0[/о) —>min, xeQ{°\ где Q^={xeX: Fi(x,0Ut)^0 (iel), OyJ =0 (jeJ)}, 1 s ' которую мы также назовем задачей нулевого приближения для задачи (V). В указанном случае будем говорить, что исходные данные задачи (V) являются малым возмущением выпукло-суперпозиционного типа исходных данных задачи нулевого приближения.

Пусть для некоторого 6о^0 найден вектор xfj - некоторое приближенное решение задачи нулевого приближения с точностью 6а. Далее, пусть известны некоторые аппроксимации возмущений щ(-) и у3(-), соответственно, операторами и\г)(-) и у^(-), такими, что функции являются выпуклыми на X, a Gj(-, - совпадают на X с аффинными, причем в некоторой окрестности точки погрешности этих аппроксимаций малы по сравнению с величиной Цж—ж^Ц. Тогда можно сформировать еще одну задачу выпуклого программирования, которую мы ниже называем задачей первого приближения. Приближенное решение этой задачи, как будет показано, позволяет уточнить значение оптимума в исходной задаче (V). Заметим, что если, в некоторой окрестности точки xfj возмущения Ui(-) (геР), Vj(-) (jeJ) удовлетворяют условию Липшица с малыми константами, то для аппроксимации первого приближения можно использовать операторы и[1)(х)=щ(х(/}), v^(x)^vj(x^)(ier,jeJ).

Пусть в некоторой окрестности точки xjfj известны некоторые аппроксимации возмущений щ(-) и Vj(-), соответственно, операторами uf\-) и vf\-), такими, что функции являются выпуклыми на X, a Gj(-, vf}(-)) - совпадают на X с аффинными, причем в некоторой окрестности точки х{£ погрешности этих аппроксимаций малы по сравнению с величиной ||ж—ж^'Ц . Тогда, рассматривая эту более тонкую аппроксимацию возмущений в окрестности точки можно сформулировать задачу выпуклого программирования, которую мы называем задачей второго приблиэ/сения. Ее приближенное решение, как будет показано, позволяет получить, вообще говоря, более точные оценки оптимума в исходной невыпуклой задаче (V) по сравнению с результатами первого приближения.

Пусть, например, для всех jeJ функции являются выпуклыми по {х,щ} на Х"х Щ, функции Qj(x,v3) совпадают на множестве X х V3 с некоторыми аффинными функциями по {ж, vj}, а операторы щ(-), v3(-) являются гладкими с липшицевыми производными vui(-), Wj(-) на некоторой окрестности Тогда указанным выше требованиям удовлетворяют линеаризации операторов Ui(-), Vj(-) в точке xfj : х-х%) (геГ), vf\x)=v3{xro)+^T0) (х-х%) (jeJ).

Выпукло-аддитивное представления исходных данных задачи (V) является частным случаем выпукло-суперпозиционного. Действительно, пусть функции J, /;, д3 обладают выпукло-аддитивным представление с выпуклыми функциями Fa, Fi} аффинными функциями Gj и возмущениями F0,Fi, Gj• Тогда, полагая для всех ге 1°, j'eJ

Ui=R\ ^i{xtui)=Fi{x)+uil Ui(-)=Fi(-),

У3=и\ g3(x,v3)=G3(x)+v3, v3(-)=G3(-), получаем выпукло-суперпозиционное представление исходных данных задачи (V).

Важно отметить, что если исходные данные (V) допускают выпукло-суперпозиционное представление с функциями Тг(х, щ), Q3(x, v3) и операторами щ(-), v3(-), то, полагая

Р{(х)=^г(х, Ос/,), Р{(х)=^г(х, щ(х)) 0ai) (геГ),

Gj(x)=Gj(x,0V}) , G3(x)=g3(x,v3(x)) -g3(x,0Vj) (jeJ), кажется возможным, формально, представить эти данные в виде аддитивного возмущения исходных данных соответствующей задачи нулевого приближения. Однако, если одна из функций ^(х,щ) или Qj(x,Vj) не является достаточно гладкой по щ или Vj, то при таком представлении соответствующее возмущение Fi(x) или Gj(x), будучи малым, вообще говоря, не будет локально удовлетворять на X условию Липшица с малой константой Липшица (простой пример приводится в III.2).

Следует отметить, что для конкретной оптимизационной задачи (V), близкой к выпуклой, выбор того или иного представления ее исходных данных в виде малого возмущения данных некоторой выпуклой задачи нулевого приближения не является формальной процедурой и зависит от конкретного вида функций J, д3. Причем использование того или иного представления приводит к различным аппроксимирующим задачам. Пусть, например,

J(x)=F0(x)+ 2 &а,(я)ФоЛ(яО, Mx)=Fi(x)+ t ЫхУЫх), k=l k=1

9j(x)=Gj(x)+ 2 Vji(x)Tji(x), 1=1 где для геГ, je J функции F{(x), Ф ik(x) (k=l,.,Ki) непрерывны вК"и выпуклы на X, функции Gj(x), Tji(x) (1=1,., Lj) непрерывны в1"и совпадают паХ с аффинными функциями, а функции £ы(х) (к=1,., Ki), т]з1(х) (Z=l,., L3) принимают малые значения на всем X и локально удовлетворяют на X условию Липшица с малыми константами. Полагая для всех ге1°, je J кг l,

Fi(x)= 2 ЫаОФ№(аО, Gj(x)= £ г)з1(х)Тз1(х), к=1 г=1 мы получим выпукло-аддитивное представление. Однако, если для некоторого г*еР функции при всех (к=1,. .,Kiaf) неотрицательны на X, то для fi*(x) имеется и выпукло-суперпозиционное представление с пространством Ui*=M.Ki*, функциkxif ей Fu(x,uu)=Fu(x)+ 2 и оператором к=1,.,К^}. Таfc=i кое представление является более детальным по сравнению с выпукло-аддитивным. Далее, при каждом je J для функции д3 имеется аффинно-суперпозиционное представление с пространством Vj= E'J, функцией 6j(x,v3)=Gj(x)+^VjiTji(x) и оператором i

Vj(x)= {г)Ах), 1=1,., Lj), причем это представление является более детальным по сравнению с аффинно-аддитивным.

Заметим, что если - 50—оптимальное решение задачи нулевого приближения, то, вообще говоря, G3{X)+G3{XT0) Ф на множестве X, поскольку нельзя гарантировать, что k=i fc=i z=i i=i

Таким образом, мы получим, вообще говоря, две различные задачи первого приближения.

Краткая характеристика содержания работы

Работа состоит из пяти глав.

Заключение.

В диссертации проведено исследование свойств и схем построения приближенных решений для конечномерных задач математического программирования общего вида. Также рассматривалась проблема построения приближенного решения одной задачи линейного программирования в режиме реального времени. Были получены следующие основные результаты.

В Гл. I сформулированы необходимые и достаточные условий приближенного оптимума в задачах математического программирования, конструктивно проверяемые с помощью решения вспомогательной выпуклой задачи квадратичного программирования и обобщающие известные необходимые и достаточные условия для точных решений. Предложена новая форма условия регулярности для точек, нарушающих точные ограничения задачи, и показано, что выполнение этого условия обеспечивает требуемый конструктивный характер указанных необходимых и достаточных критериев приближенного оптимума.

В Главах II и III даны определения двух классов задач (исходные данные которых имеют, т.н. выпукло-аддитивное или выпукло-суперпозиционное представление), допускающих их обоснованную аппроксимацию выпуклыми задачами (различной степени приближения). Для этих классов задач сформулированы и исследованы схемы построения приближенного решения исходной задачи по результатам приближенного решения аппроксимирующих задач (0-го, 1 -го и 2-го приближения) с конструктивными оценками точности неизвестного оптимума в исходной невыпуклой (и, возможно, негладкой) задаче.

В Гл. IV предлагаемый в главах II и III подход к построению приближенных решений продемонстрирован на примерах.

В Гл. V для одного класса задач линейного программирования предложена схема эффективного численного алгоритма получения приемлемого приближенного решения в режиме реального времени.

1. Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление. М.:Наука, 1979.430с.

2. Белецкий В.В. Движение исскуственного спутника относительно центра масс. М.:Наука, 1965.416с.

3. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Изд-во "Факториал Пресс", 2003. 352 с.

4. Вересков А.И. Оптимизация в выпуклых системах с размытыми исходными данными. Диссерт. на. соиск. к.ф.-м.н., ЦЭМИ. Москва, 1988.

5. Вересков А.И., Мягков В.Н. Анализ приближенных решений задачи линейного программирования с размытыми параметрами. // Экономика и математические методы, 1995 вып 1, с.151-159.

6. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. 510 с.

7. Гольштейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.:Наука, 1971, 352 с.

8. Дмитрук А. В., Милютин А. А., Осмоловский Н. П. Теорема Люстерника и теория экстремума // Успехи мат. наук, 1980, т. 35 №6(216), с.11—46

9. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.:Наука, 1982. 432 с.

10. Еремин И.И, Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.:Наука, 1976, 192 с.

11. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука. 1988. 280с.

12. Кротов В.Ф., Лагоша Б.А., Лобанов С.М. и др. Основы теории оптимального управления. М.:Высш. шк., 1990. 430 с.

13. Куликов А.Н. Фазылов В.Р. Выпуклая оптимизация с заданной точностью // ЖВМ и МФ. 1990. Т.ЗО. N5. С.663-673

14. Левитин Е.С., Милютин А.А., Осмоловский Н.П. Об условиях локального минимума в задаче с ограничениями. В кн.: «Математическая экономика и функциональный анализ», М.: Наука, 1974, с. 139-202.

15. Левитин Е.С. Теория возмущений экстремальных задач с обобщенно-выпуклым образом. // В сб.: Численные методы в задачах оптимального экономического планирования. М.: ВНИИСИ, 1983, вып. 1, С. 34-54.

16. Левитин Е.С. Об асимптотическом методе решения задач оптимизации, содержащих малые параметры. // В сб.: Модели и методы оптимизации. М.:ВНИИСИ, 1990, вып. 7, С. 28-42

17. Левитин Е.С. О локальной липпшцевости функции возмущения бесконечномерных невыпуклых экстремальных задач с операторными ограничениями В сб. Оптимальность управляемых динамических систем. - М.: ВНИИСИ, 1990, вып. 14, С.52-58

18. Левитин Е.С. Теория возмущений в математическом программировании и ее приложения. М.:Наука, 1992, 360 с.

19. Левитин Е.С., Милютин А.А., Осмоловский Н.П. Условия высших порядков локального минимума в задачах с ограничениями. // Успехи математических наук, 1978, том XXXIII, вып.6(204), стр.85-146

20. Левитин Е.С., Милютин А.А., Осмоловский Н.П. Теория условий высших порядков в гладких задачах на экстремум с ограничениями. В кн.: Теоретические и прикладные вопросы оптимального управления. Новосибирск, 1985, с. 4-40.

21. Лейхтвейс К. Выпуклые множества. М.:Наука, 1985, 336 с.

22. Лоран П.-Ж- Аппроксимация и оптимизация. Пер. с франц. М.: Мир, 1975, 496с.

23. Люстерник Л.А., Соболев В,И. Элементы функционального анализа. М.: Наука, 1965, 520 с.

24. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. и предисловие А.И. Штерна, М.;Наука, 1990. - 488с.

25. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследования операций в задачах и упражнениях. М.: Высшая школа, 1986, 288 с.

26. Мордухович Б.Ш. Методы аппроксимаций в задачах оптимизации и управления. М.: Наука, 1986.-360 с.

27. Муртаф Б. Современное линейное программирование. М. Мир, 1984, 224 с.

28. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.

29. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х томах. Том 1. М.: Мир, 1991.-360 с.

30. ОбенЖ--П., Экланд И. Прикладной нелинейный анализ. М.: Мир, 1988, 512 с.

31. Пинягина О.В., Фазылов В.Р. Общий метод выпуклого программирования с заданной точностью//Изв. вузов. Математика. 1995. N12. С.63-73

32. Пинягина О.В.; Фазылов В.Р. Метод выпуклого программирования с заданной абсолютно-относительной точностью //ЖВМ и МФ. 1998. Т.38. N8. С.1247-1254

33. Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого анализа. -М.:ФИЗМАТЛИТ, 2004. 416 с.

34. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. 384 с.

35. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980, 320 с.

36. Пшеничный Б.Н. Метод линеаризации. М.:Наука, 1983, 136 с.38 39 [40 [41 [42 [43 [44 [45 [46 [4748

37. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. -М.:Наука, 1975. 320 с.

38. Шор Н. 3., Стеценко С. И. Квадратичные экстремальные задачи и недифференцируе-мая оптимизация.— Киев: Наукова думка, 1989, 208 с.

39. Boyd Stephen and Vandenberghe Lieven. Convex Optimization. Cambridge University Press, 2004. 716 pp.

40. Encyclopedia of Optimization, 2nd Ed. C. A. Floudas and P. M. Pardalos (Eds.), Springer, 2009, ISBN: 978-0-387-74759-0, 4626 pp.

41. Hoffman A.J. On approximate solutions of systems of linear inequalities. J. Res. Nat.Bur. Stundards, 1952, vol. 49. p. 263-265

42. Neumaier A., Schichl H. Sharpening the Karush-John optimality conditions // каталог электр. изданий Optimization-Online, http://www.optimization-onIine.org, 2003, 8 pp.

43. Levitin E., Tichatschke R. On Smoothing of Parametric Minimax-Functions and Generalizrd Max-Functions via Regularization // Journal of Convex Analysis, Vol. 5, No. 2, 1998, pp. 199-220

44. Levitin E., Tichatschke R. A Branch-and-Bound Approach for Solving a Class of Generalized Semi-infinite Programming Problems // Journal of Global Optimization, Vol. 13, No. 3, 1998, pp. 299-315

45. Crawford В. S. Configuration Design and Efficient Operation of Redundant Multi-Jet Systems. // Proceedings of AIAA Guidance, Control, and Flight Mechanics Conference, AIAA, New York, 1969; also AIAA Paper 69-845, Aug. 1969. pp. 20

46. Bergmann E.V., Croopnick S. R., Turkovich J. J., etc. An Advanced Spacecraft Autopilot Concept// Journal of Guidance and Control, Vol. 2, No. 3, 1979, p. 161.

47. Paradiso J. A. Application of Linear Programming to Coordinated Management of Jets and Aerosurfaces for Aerospace Vehicle Control C. S. Draper Lab., Report CSDL-R-2065, Cambridge, MA, Nov. 1988.

48. Fukuda K. and Terlaky T. Criss-Cross Methods: A Fresh View on Pivot Algorithms. Mathematical Programming, (Series B) 79, 1992, pp. 369-396.

49. Публикации автора по теме диссертации.

50. Волошииов В.В., Левитин Е.С. Приближенная глобальная минимизация невыпуклых функций, близких к выпуклым //ЖВМ и МФ, 1997, Т.37, N7, С.771-784.

51. Волошинов В.В. Левитин Е.С. Построение приближенных решений в задачах математического программирования, близких к выпуклым. Препринт. ИСА РАН, Москва, 1999.88с.

52. Aleshin A., Ankersen F., Vankov A., Voloshinov V., Wu S. Optimization of Spacecraft Thruster Management Function. // AIAA Journal of Guidance, Control, and Dynamics, Vol. 28, No. 6, Nov.-Dec., 2005, pp. 1283-1290