О.В. Хамисов. Аппроксимация меры выпуклого компактного множества ... С. 272-279.

УДК 519.6

MSC: 28А12, 90С25

DOI: 10.21538/0134-4889-2017-23-3-272-279

Полная версия статьи

Работа выполнена при поддержке РФФИ (проект 15-07-08986).

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

Ключевые слова: мера, выпуклое компактное множество, экстремальные параллелепипеды, внешняя и внутренняя аппроксимация.

СПИСОК ЛИТЕРАТУРЫ

1.   Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М: Наука, 1976. 544 c.

2.   Шилов Г.Е., Гуревич Б.Л. Интеграл, мера и производная. М: Наука, 1967. 220 c.

3.   Михайлов Г.А., Войтишек А.В. Численное статистическое моделирование. Методы Монте-Карло. М: Изд. центр “Академия”, 2006. 368 с.

4.   LovДasz L., Simonovits M. Random walks in a convex body and an improved volume algorithm // Random structures & algorithms. 1993. № 4. P. 359–412.

5.   Бронштейн Е.М. Аппроксимация выпуклых множеств многогранниками // Современная математика. Фундаментальные направления. 2007. Т. 22. С. 5–37.

6.   PrДekopa A. Stochastic programming. Dordrecht, Boston: Kluwer Acad. Publ., 1995. 599 p.
ISBN: 0792334825 .

7.   Норкин В.И., Роенко Н.В. α-вогнутые функции и меры и их применения // Кибернетика и системный анализ. 1991. Вып. 6. C. 77–88.

8.   Ащепков Л.Т. О построении максимального куба, вписанного в заданную область // Журн. вычисл. математики и мат. физики. 1980. Т. 20, № 2. С. 510–513.

9.   Хачиян Л.Г. Задача вычисления объема многогранника перечислительно трудна // Успехи мат. наук. 1989. Т. 44, вып. 3. С. 179–180.

10.   Tuy H., Al-Khayyal F., Thach P.T. Monotonic optimization: Branch and cut methods // Essays and Surveys in Global Optimization / eds. C. Audet, P. Hansen, G. Savard. Berlin, etc.: Springer, 2005. P. 39–78. doi: 10.1007/0-387-25570-2_2 .

Поступила 12.05.2017

Хамисов Олег Валерьевич 
д-р физ.-мат. наук, старший науч. сотрудник, зав. отделом
Инcтитут систем энергетики им Л.А. Мелентьева СО РАН, г. Иркутск
e-mail: khamisov@isem.irk.ru

English

O. V. Khamisov. Approximation of the measure of a convex compact set.

We consider an approach to constructing upper and lower bounds for the measure of a convex compact set. The approach is based on extremal inscribed and circumscribed parallelepipeds. It is assumed that the measure of a parallelepiped can be easily calculated. It is shown that the problem of constructing an inscribed parallelepiped of maximum volume is reduced to a convex programming problem with exponential number of constraints. In some particular important cases the exponential number of constraints can be avoided. We suggest an algorithm for the iterative inner and outer approximation of a convex compact set by parallelepipeds. The complexity of the algorithm is estimated. The results of a preliminary numerical experiment are given. The possibility of constructing parallelepipeds that are extremal with respect to measure is discussed. Some advantages of the proposed approach are specified in the conclusion.

Keywords: measure, convex compact set, extremal parallelepiped, inner and outer approximation.

The paper was received by the Editorial Office on May, 12, 2017.

Oleg Valer’evich Khamisov. Dr. Phys.-Math. Sci., Melentiev Energy Systems Institute, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: khamisov@isem.irk.ru