2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Минимум суммы модулей
Сообщение29.03.2019, 01:32 


19/03/19
4
Здравствуйте, возник вопрос,как найти минимум в явном виде такого выражения, $$\sum\limits_{i=1}^{n}\left\lvert\\a_i-b_ix\right\rvert$$ Если $\\a_i$ и $\\b_i$ больше 0? И минимум существует(т.к. это выпуклая функция), да и выглядит несложно, но пока закономерности не нашел.

-- 29.03.2019, 01:34 --

 Профиль  
                  
 
 Re: Минимум суммы модулей
Сообщение29.03.2019, 01:46 
Заслуженный участник
Аватара пользователя


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

Lex060770 в сообщении #1384689 писал(а):
это выпуклая функция
А почему?

 Профиль  
                  
 
 Re: Минимум суммы модулей
Сообщение29.03.2019, 01:49 
Заслуженный участник


09/05/12
25179
Это нужно аналитически или как-нибудь?

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

 Профиль  
                  
 
 Re: Минимум суммы модулей
Сообщение29.03.2019, 08:49 
Заслуженный участник
Аватара пользователя


11/03/08
10217
Москва
Как уже было сказано, это метод наименьших модулей. Некогда он конкурировал с МНК, но простой аналитический подход к минимизации, приравнивание нулю производных, для МНК приводящий к системе линейных уравнений, которые и в 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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: dgwuqtj, ihq.pl


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group