Аппроксимация с нормой L1

[renegator]

Требуется аппроксимировать набор точек нелинейной функцией $y(t) = A+B\cdot\sin^2(t)$ используя норму L1. С нормой L2 все понятно - получается метод наименьших квадратов:
$F = \sum (y_i - A-B\cdot\sin^2(t_i))^2\rightarrow \min$
В случае L1 в производной по коэффициентам получается необходимость учитывать знак и я что-то не соображу, как решать эту систему
$F = \sum |y_i - A-B\cdot\sin^2(t_i)|\rightarrow \min$

Прошу направить, потому что давно не математик

[ИСН]

Начнём с мелочи: ничего нелинейного по существу здесь нет. От коэффициентов зависимость линейная, а значит, это то же самое, что приближать прямой $Ax+B$.
Далее, насчёт как решать, если минимизируем разность модулей. Решается эта штука плохо и неоднозначно.

[mserg]

В принципе задача сводится к линейному программированию: каждый модуль в критерии это пара дополнительных переменных
http://lpsolve.sourceforge.net/5.1/absolute.htm

Тогда задачу можно решить с использованием готовых пакетов (линейное программирование есть даже в Excel). Если количество данных - сотни тысяч или даже миллионы, то метод внутренней точки.

[sup]

Если делать "руками", то я бы не так решал. Фиксируем $B$ и полагаем $x_i = y_i - B \sin^2 t_i$.
Функционал
$G = \sum |x_i - A|\rightarrow \min$
легко минимизируется по $A$. Для этого надо просто найти медиану в множестве $\{x_i\}, i = \overline {0,N}$.
Ну а дальше, что-нибудь типа делением пополам для оптимизации по $B$.
Сложность получится типа
$O(N \ln N |\ln \varepsilon |)$,
где $ \varepsilon$ - допустимая погрешность. Ну а если чуть постараться, то и от $\ln N$ можно избавиться.
По-моему дешево и сердито.

[renegator]

Оказалось, что велосипед носит имя метода наименьших модулей. В англоязычных источниках Least Absolute Deviations. Методы решения базируются в том числе на симплекс-методе и МНК

[ИСН]

МНК служит для того, чтобы посмотреть, как надо, а потом сделать примерно так же?

[renegator]

Не совсем. Это итеративный процесс. Отсылаю к древней книжке Мудров В.И. Кушко. В.Л. Метод наименьших модулей.

[Евгений Машеров]

Там взвешенный МНК используется. Веса подбираются так, чтобы результат минимизации взвешенных квадратов был бы эквивалентен минимизации по модулям.