Задача математического программирования

[reader_st]

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

[just_roma]

reader_st писал(а):

just_roma
Чуть позже уточню.

На самом деле проблема не в том, чтоб найти аналитическое решение задачи

\[ y \to \sup \] \[ \left\{ \begin{aligned} &\sum_{i = 1}^{n}a_{i}^{-}x_{i} \leq z \leq \sum_{i=1}^{n}a_{i}^{+}x_{i} \\ &f(z,y) \geq \alpha \\ &x \in X \\ \end{aligned} \right. \]

а показать при каких условиях она устойчиво разрешима. Т.е. параметры $a_{i}^{-}, a_{i}^{+}$ могут иметь некоторые возмущения. Причем их возмущение таково, что $|a^{-}_{i}-a^{-\varepsilon}_{i}| \leq \varepsilon$ и $|a^{+}_{i}-a^{+\varepsilon}_{i}| \leq \varepsilon$, где $a^{+\varepsilon}_{i}$ и $a^{-\varepsilon}_{i}$ - возмущенные величины. Надо показать, что если $y^{*}$ и $y^{*\varepsilon}$ - это решения исходной и возмущенной задач, то $|y^{*}-y^{*\varepsilon}| \leq \varepsilon\mathbf{C}$. (Васильев Линейное программирование). Вот я и подумал, что если удастся найти условия при которых эта задача имеет аналитическое решение в упомянутом выше виде, то можно легко показать, что задача устойчива по результату, т.к. если решение имеет вид $y=g(\sum_{i=1}^{n}a^{*}_{i}x_{i})$, где g удовлетворяет условию Липшица, то (считаем, что x >= 0 и X - ограниченное)

\[ |y^{*}-y^{*\varepsilon}|=\]

\[|g(\sum_{i=1}^{n}a^{*}_{i}x_{i})-g(\sum_{i=1}^{n}a^{*\varepsilon}_{i}x_{i})| \leq \]

\[\mathbf{C}|\sum_{i=1}^{n}a^{*}_{i}x_{i}-\sum_{i=1}^{n}a^{*\varepsilon}_{i}x_{i}| \leq \]

\[\mathbf{C}\sum_{i=1}^{n}|a_{i}^{*}-a_{i}^{*\varepsilon}|x_{i} \]

\[\leq \varepsilon \mathbf{C} \sum_{i=1}^{n}x_{i} \]

и т.к. X ограничено получаем что хотели.

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

незваный гость:

Разбивайте, пожалуйста, длинные цепочки формул. Удобным местом являются, например, равенства и неравенства.

[reader_st]

Вот теперь понятно зачем непрерывное решение. Обычно для устойчивости в ЧМ (числ. метод) рассм. разностный аналог задачи. Посмотрим.

[reader_st]

Уважаемый Роман.
Нашел способ анализа чувствительности полученного решения через множители Лагранжа. Способ описан в книге Г. Реклейтис “Оптимизация в технике” т.2. стр 255. Данный способ позволяет получить информацию о чувствительности целевой функции к различным ограничениям. Также можно посмотреть теорию двойственности.

[just_roma]

reader_st писал(а):

Уважаемый Роман.
Нашел способ анализа чувствительности полученного решения через множители Лагранжа. Способ описан в книге Г. Реклейтис “Оптимизация в технике” т.2. стр 255.

Спасибо, посмотрю

reader_st писал(а):

Также можно посмотреть теорию двойственности.

А как мне может помочь теория двойствености?
Да вот нашел книжку Молодцов Устойчивость методов оптимизации но так и не понял ее содержимого, т.е. саму идею не понял, что автор там хотел написать. Может есть книжки попроще?

[just_roma]

reader_st писал(а):

Способ описан в книге Г. Реклейтис “Оптимизация в технике” т.2. стр 255.

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

[reader_st]

just_roma писал:

Цитата:

Неужели вопросами устойчивости никто не занимается?

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

[reader_st]

Уважаемый Роман.

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

[just_roma]

reader_st писал(а):

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

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

[just_roma]

reader_st писал(а):

just_roma писал:

Цитата:

Неужели вопросами устойчивости никто не занимается?

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

А вот есть книга Молодцова Устойчивость принципов оптимальности, там как я понимаю автор занимается вопросами в общем случае, однако поднять такую книгу уж слишком сложно, написана она уж слишком абстрактно и нет никаких поясняющих примеров. Вобщем сложно разобраться.
Говорят есть очень хорошая монография на эту тему Bonnens J.F. Perturbation Analysis of Optimization Problems. Однако где ее взять

[reader_st]

just_roma писал:

Цитата:

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

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

Насчет книг по операторам --- я не силен в этом разделе, но вот говорят, что больно хорош трехтомник Данфорда.