Минимум суммы модулей

[Lex060770]

Здравствуйте, возник вопрос,как найти минимум в явном виде такого выражения,

$$\sum\limits_{i=1}^{n}\left\lvert\\a_i-b_ix\right\rvert$$

Если $\\a_i$ и $\\b_i$ больше 0? И минимум существует(т.к. это выпуклая функция), да и выглядит несложно, но пока закономерности не нашел.

-- 29.03.2019, 01:34 --

[mihaild]

Попробуйте вынести $b_i$ за знак модуля, отсортировать слагаемые по $\frac{a_i}{b_i}$ и посмотреть на производную на каждом отрезке.

Lex060770 в сообщении #1384689 писал(а):

это выпуклая функция

А почему?

[Pphantom]

Это нужно аналитически или как-нибудь?

Если второе, то вы, по-видимому, пытаетесь изобрести "метод наименьших модулей". Погуглите это название, ответ найдется почти сразу.

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

Как уже было сказано, это метод наименьших модулей. Некогда он конкурировал с МНК, но простой аналитический подход к минимизации, приравнивание нулю производных, для МНК приводящий к системе линейных уравнений, которые и в XVIII веке можно было решить вручную (а когда появился метод Гаусса, то стало совсем легко), а для МНМ получаем после дифференцирования выражения с сигнумами, разрывные. И интерес возобновился не ранее, чем с появлением ЭВМ, позволивших решать численно, причём обусловлен он был прежде всего требования робастности, грубые ошибки в данных на решение МНМ влияли меньше, чем на МНК. Однако у него проявились и недостатки.
МНК даёт однозначный ответ, у МНМ возможна неоднозначность. Если поставить простейшую задачу на МНМ, $\min!_m |x_i-m|$, получим в качестве оценки медиану, а для чётного числа наблюдений она определяется неоднозначно, любое значение между $n/2$ и $n/2+1$ элементами вариационного ряда доставляет одинаковое значение функционалу (на практике берут обычно среднее, жертвуя тем, что медиана равна реальному числу в ряду, в теории могут полагать, что выбирается любое случайно). Для более сложной постановки со многими параметрами также неоднозначность реальна. Также, для многомерной постановки, возможна нестабильность в смысле при очень малых возмущениях данных немалые изменения ответа (зато большие возмущения не действуют так сильно, как на МНК)
Полный перебор, который был основным методом в начале использования, экспоненциально сложен и практически не применяется. Среди методов решения:
1. Линейное программирование.
$\min \Sigma u_i$
$u_i\ge y-\Sigma a_j x_{i,j}$
$u_i\ge -(y-\Sigma a_j x_{i,j})$
Из свойств ЛП ясно, что n ограничений обратятся в равенства, и можно их просто вручную перебрать (что, собственно, и было техникой расчёта "300 лет тому назад")
2. Взвешенный МНК.
Начинают с простого МНК, затем вводят веса так, чтобы взвешенные квадраты были близки к модулям:
$w_i=\frac 1 {|y_i-\Sigma a_j x_{i,j}|}$
И так "до полного удовлетворения"
3. Покоординатная оптимизация.
Предлагались и иные методы.
https://web.wpi.edu/Pubs/E-project/Avai ... Report.pdf
(Аппендикс А).
https://www.sciencedirect.com/science/a ... via%3Dihub