Метод центра тяжести

Метод центра тяжести — это теоретический алгоритм выпуклой оптимизации . Его можно рассматривать как обобщение метода деления пополам с одномерных функций на многомерные функции. Это теоретически важно, поскольку достигается оптимальная скорость сходимости. Однако это не имеет практической ценности, поскольку каждый шаг требует очень больших вычислительных затрат.

Вход

Наша цель — решить задачу выпуклой оптимизации вида:

минимизировать f ( x ) st x в G ,

где f — выпуклая функция , а G — выпуклое подмножество евклидова пространства R ^н .

у нас есть «субградиентный оракул»: программа, которая может вычислить субградиент f f в любой заданной точке (если Мы предполагаем, что дифференцируема, то единственным субградиентом является градиент $\nabla f$; но мы не предполагаем, что f дифференцируемо).

Метод

Метод является итеративным . На каждой итерации t мы сохраняем выпуклую область Gt _, которая заведомо содержит искомый минимум. Изначально имеем G ₀ = G . Затем каждая итерация t выполняется следующим образом.

• Пусть xt _​ будет тяжести Gt ​ _. центром
• Вычислите субградиент в точке x _t , обозначенный f '( x _t ).
  • По определению субградиента график f находится выше субградиента, поэтому для всех x в G _t : f ( x ) − f ( x _t ) ≥ ( x − x _t ) ^Т f'( х _т ).
• Если f '( x _t )=0, то из вышеизложенного следует, что x _t является точной точкой минимума, поэтому мы завершаем операцию и возвращаем x _t.
• В противном случае пусть G _{t +1} := {x в G _t : ( x − x _t ) ^Т е'( х _т ) ≤ 0}.

Обратите внимание, что согласно приведенному выше неравенству каждая точка минимума f должна находиться в G _{t +1.}

Конвергенция

Можно доказать, что

$Volume(G_{t+1})\leq \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]\cdot Volume(G_{t})$ .

Поэтому,

$f(x_{t})-\min _{G}f\leq \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]^{t/n}[\max _{G}f-\min _{G}f]$.

Другими словами, метод имеет линейную сходимость остаточного целевого значения со скоростью сходимости $\left[1-\left({\frac {n}{n+1}}\right)^{n}\right]^{1/n}\leq (1-1/e)^{1/n}$. Для получения ε-аппроксимации целевого значения количество необходимых шагов не превышает $2.13n\ln(1/\epsilon )+1$.

Вычислительная сложность

Основная проблема метода заключается в том, что на каждом этапе нам приходится вычислять центр тяжести многогранника. Все известные до сих пор методы решения этой задачи требуют ряда арифметических операций, экспоненциальных по размерности n. Следовательно, метод бесполезен на практике, когда имеется 5 и более измерений.

См. также

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