Тема: Метод отсечений Булатова

Задачи выпуклого программирования часто встречаются на практике, поэтому разработка HOBBIX И модификация существующих методов остается актуальной задачей.
Есть множество классов методов решения задач выпуклого программирования. Один из таких классов образуют методы отсечений, которые можно раз дел итв на 3 группы: методы отсечений с аппроксимацией надграфика целевой функции, методы отсечения с аппроксимацией области ограничений и, достаточно редко встречающаяся группа методов, использующих аппроксимацию как надграфика так и области ограничений целевой задачи.
В данной работе численно исследуются варианты метода Булатова ([1], с. 28-30) и модифицированного метода отсечений [2] в которых заложена возможности изменения от шага к шагу внутренних вспомогательных точек, участвующих в построении отсекающих плоскостей.
Метод отсечений Булатова и модифицированный метод отсечений используют при построении отсечений произвольную внутреннюю точку(-и) из допустимой области. Обычно эту точку задают на предварительном шаге метода и оставляют зафиксированной на всем протяжении решения задачи. В работе исследуется варианты указанных методов, где вспомогательные точки перемещаются в допустимой области согласно определенному правилу.
Отметим, что существенной проблемой методов отсечений является неограниченное накопление в процессе счета отсекающих плоскостей, которые формируют аппроксимирующее множество, что влечет за собой увеличение вычислительных затрат и накопление ошибок округления. В статье [3], научным руководителем работы и Р.С. Яруллиным был предложен один подход к построению методов отсечений с обновлением аппроксимирующих множеств за счет отбрасывания любого числа отсекающих плоскостей. С использованием этого подхода в упомянутых выше модифицированный метод отсечений была заложена возможность обновления погружающих множеств.
В рамках работы в среде Matlab были реализованы и отлажены программы для исследования вариантов метода отсечений Булатова и вариантов модифицированного метода отсечений.

Купить

В рамках работы были реализованы и исследованы четыре варианта методов отсечений с аппроксимацией допустимой области. На основе полученных результатов можно сделать следующие выводы:
- Вариант метода отсечений Булатова более эффективен (с точки зрения скорости сходимости) чем оригинальны метод отсечений лишь для задач размерность которых превышает 4. Оптимальным значением параметрам является диапазон от 0.2 до 0.45.
- Вариант метода отсечений Булатова с обновлением погружающих множеств становится эффективнее варианта метода отсечений Булатова без обновления погружающих множеств при размерности задачи больше 5. Оптимальным значением параметра а является диапазон от 0 до 0.45, параметра Д и АД, значения 0.1 и 0.0001 соответственно.
- Вариант модифицированного метода отсечений является эффективнее чем модифицированный метод отсечений. Оптимальным значением параметрам является диапазон от 0.2 до 0.5.
- Вариант модифицированного метода отсечений с обновлением погружающих множеств оказался наиболее эффективным из всех рассматриваемых методов. Оптимальным значением параметра м является диапазон от 0 до 0.45, параметра Д и АД, значения 0.1 и 0.0001 соответственно.
В целом можно заключить, что модификация с перемещением вспомогательных точек в допустимой области согласно определенном правилу положительно влияет на скорость сходимости методов отсечений с аппроксимацией допустимой области. Так же, варианты методов отсечений с обновлением погружающих множеств обеспечивают меньшую погрешность вычислении.
Перспективой дальнейшего исследования данных методов являются: доказательство сходимости вариантов методов отсечений и теоретическое исследование оптимальности параметра а.

Купить