Эвристика для оптимизации

Поскольку это пятница, пришло время для CW вопроса. Я ищу эвристики, которые широко используются в задачах оптимизации. Чтобы ограничить область применения более «дружественной теории» эвристики, вот правила (некоторые произвольные, некоторые нет)

• Это должен быть четко определенный метод без многочисленных параметров и с конкретным временем выполнения (возможно, на одну итерацию)
• Он должен иметь некоторые известные теоретические результаты, связанные с ним (скорость сходимости, границы аппроксимации, если таковые имеются, стационарные свойства и т. Д.)
• Он должен иметь широкое применение и, по крайней мере, одно флагманское приложение, где это либо метод выбора, либо один из немногих.
• это не должно быть вдохновлено природой (хотя это кажется легкомысленным возражением, я пытаюсь исключить генетические алгоритмы, оптимизацию колоний муравьев и тому подобное).

В идеале ответы должны быть в следующем формате: вот пример.

Название : Чередование оптимизаций

Цель : свернуть (обычно невыпуклую) функцию$f(x,y)$

Условия : ассоциированные функции и h (y) = \ min_x f (x, y) являются выпуклыми$g(x) = \min_y f(x,y)$$h(y) = \min_x f(x,y)$

Алгоритм : $i^{\text{th}}$ итерация начинается с $x_i, y_i$ .

1. $x_{i+1} \leftarrow \arg \min_x f(x, y_i)$
2. $y_{i+1} \leftarrow \arg\min_y f(x_{i+1}, y)$

Самое известное приложение : $k$ -means, повторяющаяся ближайшая пара.

Теория : Известные результаты по средним, общие достаточные условия глобальной оптимальности каркаса$k$

ps Вы можете обнаружить, что ваш ответ заканчивается лекцией на семинаре по алгоритмам, который я планирую :)

Название: повторный пересчитанный метод наименьших квадратов.
Цель: минимизировать функцию вида , , , Условия: зависят от случая. Алгоритм: очевидный - фиксировать веса, решать квадратичную задачу, пересчитывать веса. Самое известное приложение: геометрическая медиана, M-оценки, норма, теория сжатого зондирования : доказано на индивидуальной основе.$\sum w(\theta)F(\theta)^2$$\theta\in R^n$$F(\theta) \in R^m$$w(\theta)\in R$


$L_p$