MDM-АЛГОРИТМ И ЗАДАЧА СИЛЬВЕСТРА

При разработке численных методов решения нелинейных минимаксных задач возникла следующая вспомогательная задача: в выпуклой оболочке некоторого конечного множества в евклидовом пространстве найти точку, имеющую наименьшую норму. В 1971 г. Б. Митчелл, В. Демьянов и В. Малоземов предложили нестандартный алгоритм решения этой задачи, который в дальнейшем получил название MDM-алгоритма (по заглавным буквам фамилий авторов). В данной статье рассматривается конкретная минимаксная задача: найти шар наименьшего объема, содержащий заданное конечное множество точек. Она называется задачей Сильвестра и является частным случаем задачи о чебышевском центре множества. Задаче Сильвестра сопоставляется выпуклая задача квадратичного программирования с симплексными ограничениями. Для решения этой задачи в статье предлагается использовать вариант MDM-алгоритма. С его помощью строится минимизирующая последовательность планов, такая, что у соседних планов различаются только две компоненты. Номера этих компонент выбираются на основе некоторых условий оптимальности. Доказывается слабая сходимость полученной последовательности планов, из которой следует сходимость по норме соответствующей последовательности векторов к единственному решению задачи Сильвестра. Приводятся четыре характерных примера на плоскости. Библ. 10. Фиг. 23.

задача Сильвестра, квадратичное программирование, MDM-алгоритм