Свойства приближенных решений и схемы их построения в задачах математического программирования тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Волошинов, Владимир Владимирович

• Волошинов, Владимир Владимирович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Волошинов, Владимир Владимирович

Введение.

Цели работы.

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

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

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 для одного класса задач линейного программирования предложена схема эффективного численного алгоритма получения приемлемого приближенного решения в режиме реального времени.

Список литературы диссертационного исследования кандидат физико-математических наук Волошинов, Владимир Владимирович, 2009 год

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