Кто-нибудь реализовывал метод отсечений?

[Telepuz]

Народ кто реализовывал или по крайне мере пытался реализовать метод отсечений (речь идет о выпуклом программировании)??? У кого есть ссылки или на крайний случай прога:) Буду весьма признателен за помощь!!!!!

[Vassil]

Попробуйте перелистать например книгу А. А. Корбута и Ю. Ю. Финкельштейна "Дискретное программирование", изд. "Наука", Москва, 1969.
Там на стр 23 описана идея метода, а дальше со стр. 118 до 212 все посвещено методу отсечения.

[Vassil]

Для более общего случая выпуклого программирования (а не только для случая дискретного программирования) можете посмотреть скажем:
Ж. Сеа, Оптимизация, Теория и алгоритмы, "Мир", Москва, 1973
В главе 4, Минимизация с ограничениями, § 1, Приближенное решение в пункт 5.2 рассматривается Метод отсекающих плоскостей Келли. В библиографиии по этому методу цитируется одна из начальных публикаций
Kelly I. (?J) E., The cutting plane method for solving convex programs, J. SIAM, 6 (1958), 15-22
а так-же и еще
Wolfe P., Accelerating the cutting plane method for non linear programming, J. SIAM, 9 (1961), 481-488
и добавленное для русского издания еще
Булатов В. П., О некоторых методов аппроксимации для задач выпуклого программирования, в сборнике "Методы математического моделирования в энергетике", Восточно-сибирское книжное издательство, 1966

В книге Г. Вагнера Основы исследования операций, том 2, изд. "Мир", Москва, 1973, в §§ 13.3 и 13.4 обсуждается метод отсекающих плоскостей (метод отсечения) для решения задач целочисленного программирования

В книге
David G. Luenberger, Introduction to linear and nonlinear programming, Addison-Wesley Publishing Company, Reading Massachusetts, 1965
в разделе 13 Cutting Plane and Dual Methods тоже рассматривается алгоритм отсекающей плоскости Келли для общего выпклого случая, а так-же и его модификации. В литературе по вопросу уже цитируется следующая публикация Келли
Kelly, J. E., The Cutting Plane Method for Solving Convex Programs, J. Soc. Indus. Appl. Math., VIII, 4, 1960, pages 703-71

[Vassil]

В книге "Итеративные методы в теории игр и программировании", под редакции В. З. Беленького и В. А. Волконского, изд. "Наука", Москва 1974, задачы выпуклого программировании рассматриваются как сведенные на их основе игры.
Глава вторая в начале книги "Итеративные процесы в общей форме" обсуждает функцию Ляпунова как критерий сходимости итертивного процесса.
В разделе ІІІ об итеративных алгоритмах, в § 23 обсуждается построение более точного алгоритма на базе алгоритма малой точности. Там в пункте 2 "Схема отсечения" и до конца параграфа есть описание одного метода, его тестовой реализации и оценки на небольших задачах.

[Telepuz]

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

[Vassil]

Пусть $V$ - гильбертово пространство, и предположим, что на $V$ определены $k$ выпуклых функций со значениями в $\textbf{R}$ : $v\to J_{i} (v)$ , $i= 1, ..., k$ . Определим замкнутое выпуклое множество $U$ , положив

$$v\in U \Leftrightarrow J_{i} (v) \leq 0, i= 1, ..., k $$

.
Пусть задан линейный непрерывный функционал

$$J(v)=(c,v)_{V}$$

(Введя новую переменную, всегда можно свести задачу к эквивалентной задаче, но с линейной функцией цели).
Найдем минимальное значение $J$ на множестве $U$ .

Краткое описание алгоритма
1) Выбирается $u_{0}\in V$ .
2) Линеаризируются ограничения. Вводится множество $U_{0}$ , такое, что

$$v\in U_{0} \Leftrightarrow v\in V , J_{i} (u_{0}) +(G_{i}(u_{0}), v-u_{0})\leq 0, i= 1, ..., k $$

,
где $G_{i}(v)$ - градиент $J_{i}(v)$ , вычисленный в точке $v$ . Тогда $u_{1}$ является решением задачи

$$u\in U_{0} $$

,

$$J(u_{1}) \leq J(v) \forall v \in U_{0}$$

3) Переход от $u_{m}$ к $u_{m+1}$ произходит следующим образом. Для поиска $u_{m}$ было определено открытое множество $U_{m-1}$. Определим теперь множество $U_{m}$. Пусть значение индекса $I$ таково, что $J_{I}(u_{m})=\max \limits_{i=1, ..., k} J_{i}(u_{m})$ . Тогда $U_{m}$ определяется с помощью замены в определении $U_{m-1}$ ограничения, связанного с $J_{I}$ , на ограничение

$$J_{I} (u_{m}) +(G_{I}(u_{m}), v-u_{m})\leq 0$$

.
Таким образом, $u_{m+1}$ определяется как решение задачи

$$u_{m+1}\in U_{m} $$

,

$$J(u_{m+1}) \leq J(v) \forall v \in U_{m}$$

.

При подходящих предположениях (в основном о выпуклости) Келли показал сходимость описанной схемы.

Замечания.
1) При $m\to +\infty $ выпуклое множество $U_{m}$ все больше и больше приближается к выпуклому множеству $U$ в той его части, где находится решение.
2) Может случиться, что $u_{m}$ не будеть определено (так как в этом случае $U_{m-1}$ не ограничено). Тогда достаточно добавить неравенство, которое ограничивает $U_{m-1}$ , например $\| v \| \leq c<+\infty $ , где $c$ "достаточно велико".
3) Еще не найден (!1971-1973) "оптимальный" вариант этого метода. Возможны вариации в выборе ограничений, определяющих $u_{m-1}$ .
4) Преимущества метода следующие:
- каждая подзадача является задачей линейного программирования;
- необязательно выбирать начальное приближение из множества $U$ .
5) В заключение отметим, что этот метод не работает в случае, когда ограничения и функция цели не выпуклы или когда желательно, чтобы $u_{m}$ находилось в $U$ .
Аналогичный метод предложен А. А. Капланом. $^{1})$ .

----------------
$^{1})$ Для случая V=\textbf{R}^{n}$ В. П. Булатовым разработан метод аппроксимации границ области, примыкающий по своей основной идее к методу, изложенному выше. - Прим. ред.

[maxal]

Есть либа Arageli, в которой есть реализация методов Гомори.