ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

Оптимизация. Построение минимального охватывающего эллипсоида

Константин Ловецкий Ноябрь 2011

Кафедра систем телекоммуникаций

1

Охватывающий эллипсоид

Введение. Постановка задачи.

Пусть в пространстве Rn даны m точек

a1 , a2 ,..., am Rn

Требуется построить эллипсоид минимального объема, содержащий внутри себя все эти точки.

Обозначим через A матрицу размерности n m , столбцы которой являются векторами a1 , a2 ,..., am Rn .

A: a1 | a2 | ... | am .

Определение эллипсоида:

Эллипсоид с центром в точке c определяется как

EQ,c : x Rn | (x c)T Q(x c) 1 ;

7/1/19

2

Охватывающий эллипсоид

7/1/19

3

Охватывающий эллипсоид

7/1/19

4

Охватывающий эллипсоид

7/1/19

5

Dual Reduced Newton Algorithm

In this section, we describe and derive our basic algorithm for the minimum- volume covering ellipsoid problem; we call this algorithm the “dual reduced Newton” algorithm for reasons that will soon be clear.

Newton Step

7/1/19

6

Dual Reduced Newton Algorithm

7/1/19

7

Dual Reduced Newton Algorithm

7/1/19

8

Dual Reduced Newton Algorithm

7/1/19

9

Dual Reduced Newton Algorithm

7/1/19

10