Минимизация кусочно-квадратичной функции многих переменных

[Nik0las]

Стоит задача в минимизации кусочно-квадратичной функции многих переменных.
Функция имеет вид:

$F(x) = b^Tx - \frac {1} {2} |(A^T x - c)|^2 $,

здесь A - сильно разреженная матрица размера m на n, m << n; x, b - вектор размера m; c - вектор размера n.

Сейчас используется метод Ньютона, однако, из-за того что функция кусочно-квадратичная, он сходится не за одну итерацию, и на каждой итерации приходится решать систему линейных уравнений. Для решения разреженных СЛАУ используется метод Холецкого и не удается хорошо распараллелить задачу. Использование итерационных методов для решения СЛАУ медленнее на 1-2 порядка по сравнению с методов Холецкого, их также неудается распараллелить из-за необходимости вычисления предобуславливателя. Метод сопряженных градиентов без предобуславливателя работает на несколько порядков медленнее.

Хотелось бы найти какой-нибудь альтернативный метод, который бы работал возможно не так быстро, но хорошо бы параллелился.

Методы скорейшего спуска и сопряженных градиентов дают очень медленную сходимость, число итераций как минимум на 6 порядков больше, чем у метода Ньютона.

Есть ли какие-то альтернативные методы поиска минимумов?

[Null]

А можно узнать по подробнее ограничения на функцию:
Непрерывность, выпуклость, ограничение на количество кусков, способ задания кусков?

По идее надо найти минимум в каждой области и на каждой границе всех размерностей и взять общий минимум.

[мат-ламер]

Nik0las в сообщении #487666 писал(а):

Сейчас используется метод Ньютона, однако, из-за того что функция кусочно-квадратичная, он сходится не за одну итерацию

А за сколько?

Nik0las в сообщении #487666 писал(а):

Хотелось бы найти какой-нибудь альтернативный метод, который бы работал возможно не так быстро, но хорошо бы параллелился

Метод альтернативный какому? Методу Ньютона? Методу Холецкого?

[Nik0las]

Null
Прошу прощенья, описался в задании функции, вид функции такой:

$F(x) = b^T x - \frac {1} {2} |(A^T x - c)_+|^2$

Оператор "+" означает что если значение больше нуля, оно остается без изменений, а если меньше - зануляется.
Соответственно функция непрерывна, всюду имеет первую производную, ограничения на количество кусков нет, способ задания - через нелинейный оператор "+", модуль означает норму вектора L2.

Области в которых ищется минимум неизвестны, да и когда число строк в матрице порядка 10e6-10e7 перебор всех координат очень дорогое занятие.

мат-ламер

Цитата:

А за сколько?

В зависимости от размерности задачи по-разному. Для одних и тех же матриц сильно зависит от параметра c.
Например сейчас взял тестовую задачу с матрицей 41x136, 691 ненулевой элемент, сходится где-то за 10-30 итераций (зависит от некоторых параметров в методе Ньютона). Эта же задача используя скорейший спуск и сопряженные градиенты вообще практически несходится, что-то близкое к решению возникает где-то на 10e5 -10e6 итерациях.

Цитата:

Метод альтернативный какому? Методу Ньютона? Методу Холецкого?

Вообще, Ньютону.

С решением СЛАУ уже перекопал все что только можно, сейчас уже опробовано порядка 10 библиотек с разными методами. Холецкий пока быстрее всех на 1-2 порядка. Даже распараллеливание не спасает.

[Nik0las]

Еще хотел добавить, что при такой записи функции необходимо найти максимум.

[мат-ламер]

Во-первых, можно ознакомиться с трудами Н.З.Шора. У него была книга "Методы минимизации недифференцируемых функций и их приложения". Киев. 1979. Но вряд ли эта книга Вас удовлетворит, поскольку методы из этой книги не приспособлены для задач с разреженными матрицами. Но после этой книги у него были статьи как раз для таких задач. Подозреваю, что его методы используются в пакете http://www.openopt.org. Там, кстати, есть форум. Можете и там свой вопрос задать.
Во-вторых, посмотрите книгу http://www.math.kemsu.ru/kmk/subsites/Krutikov_RelaxMeth/index.htm (третью и четвёртую главу).
В-третьих, почитайте вот эту статью http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=775&option_lang=rus. Они исходят из задачи линейного программирования. Строят для неё модифицированную функцию Лагранжа, которая выглядит как и Ваша целевая функция. Затем минимизируют её методом Ньютона. Там внизу есть статьи, ссылающиеся на эту статью. См. статью Гаранжа и др. Там рассмотрена параллельная реализация этого метода. Но в сети (на http://www.mathnet.ru) её пока нет.
В-четвёртых, посмотрите книгу Бертсекаса "Convex Analysis and Optimization" последнюю главу.

[Nik0las]

Спасибо за ссылки, посмотрю, может что-то получится.

[mserg]

А кто в этой задаче «куски»?
Видимо, еще имеет смысл посмотреть метод внутренней точки. Разработан в 80-х годах, хорошо себя зарекомендовал на громоздких задачах. Если задача не учебная, то имеет смысл читать аннотации к готовым программам (например, IPOPT)
Никак не могу сообразить, имеет ли место выпуклость …

[Aleksandr Pavlovich]

Nik0las в сообщении #487952 писал(а):

Null
Прошу прощенья, описался в задании функции, вид функции такой:

$F(x) = b^T x - \frac {1} {2} |(A^T x - c)_+|^2$

Насколько я понял c - это вектор, основное слагаемое -квадрат нормы вектора с положительными компонентами: $|(A^T x - c)_+|^2$

Идея:
0. $A_1 = A, c_1 = c; i=1;
1. Минимизируем $F(x) = b^T x - \frac {1} {2} |(A_i^T x - c_i)|^2$.
Получаем x_i

2. Выбрасываем из A строки (столбцы?), из c - компоненты с номерами, которым соответствуют отрицательные компоненты в $(A^T x_i - c)$.
Получаем $A_{i+1}, c__{i+1} = c;
i=i+1;

3. Если нашлось, что выбрасывать, то переходим к 1.
Иначе стоп.

Идея №2: использовать сглаживание функции $(y)_+$ с праметром $\varepsilon > 0$, решать сглаженные задачи, устремлять $\varepsilon$ к нулю.

[vjung]

Задачу можно привести к обычному квадратичному виду (без оператора $+$):

maximize $b^Tx-y^Ty$
s.t.
$Ax-c \leq y$
$0 \leq y$

а дальше батарея обычных методов для QP

[monochromer]

Если еще нужны параллельные версии некоторых алгоритмов решения СЛАУ, то можете посмотреть их тут