4551
правка
Компоновка схемы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
Квадратичная компоновка (только по размерности x) задается формулой | Квадратичная компоновка (только по размерности x) задается формулой | ||
(1) <math>\Phi(x) = \sum_{i,j} w_{ij} [(x_i - x_j)^2] = \frac{1}{2} x^T | (1) <math>\Phi(x) = \sum_{i,j} w_{ij} [(x_i - x_j)^2] = \frac{1}{2} \mathbf{x}^T \mathbf{Q}\mathbf{x} + \mathbf{c}^T \mathbf{x} + const</math>. | ||
Глобальный минимум | Глобальный минимум <math>\Phi (x) \;</math> можно найти, решив разреженную систему линейных уравнений с симметричной положительно определенной матрицей <math>\mathbf{Q} \mathbf{x} + \mathbf{c} = 0 \;</math> (предполагая, что имеется более одной фиксированной вершины), которая поддается эффективному решению с достаточной точностью при помощи любого числа итеративных алгоритмов решения. Квадратичная компоновка может иметь различные оптимумы в зависимости от модели (клика либо звезда), используемой для представления гиперребер. Однако для k-точечного гиперребра имеет место следующий факт: если вес 2-точечных ребер задается равным <math>W_c \;</math> в модели с кликой и <math>kW_c \;</math> в модели со звездой, то для случая квадратичной компоновки эти модели эквивалентны [7]. | ||
Линеаризованная квадратичная компоновка | '''Линеаризованная квадратичная компоновка''' | ||
Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя wij = 1/jxi — xjj на каждой итерации. Другим вариантом может быть решение единичной /S-регуляризованной задачи оптимизации, заданной формулой Ф^(х) = minx Pi;j wij(xi - xj)2 + fi, /3 > 0 – например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1]. | Качество компоновки при помощи квадратичных алгоритмов может оказаться невысоким. Для аппроксимации линейной целевой функции можно итеративно решить уравнение (1), вычисляя wij = 1/jxi — xjj на каждой итерации. Другим вариантом может быть решение единичной /S-регуляризованной задачи оптимизации, заданной формулой Ф^(х) = minx Pi;j wij(xi - xj)2 + fi, /3 > 0 – например, с использованием прямо-двойственного метода Ньютона с квадратичной сходимостью [1]. | ||