Регрессия квадратичного полинома

[Alex Krylov]

Кстати... о неединственности оптимального решения задачи $\min\limits_{x} \left\lVert A x - b\right\rVert_1$, которая выше была приведена к равносильной форме:
$\min\limits_{} \mathbf{1}^T t$
$\begin{bmatrix}A&-E \\ -A&-E \end{bmatrix} \begin{bmatrix}x \\ t \end{bmatrix} \leqslant \begin{bmatrix}b \\ -b \end{bmatrix}$

Как известно, если оптимальное решение задачи линейного программирования не единственно, то множество оптимальных решений образует выпуклый многогранник. Для задач небольшой размерности этот "многогранник решений" можно найти, перейдя от исходного H-представления многогранника $\begin{bmatrix}A&-E \\ -A&-E \end{bmatrix} \begin{bmatrix}x \\ t \end{bmatrix} \leqslant \begin{bmatrix}b \\ -b \end{bmatrix}$ к V-представлению: $\begin{bmatrix}x \\ t \end{bmatrix} = \sum\limits_{i=1}^{N} \lambda_i \begin{bmatrix}x \\ t \end{bmatrix}_i + \sum\limits_{j=1}^{M} \nu_j \begin{bmatrix}x \\ t \end{bmatrix}_{N+j}$, где $\lambda_i \geqslant 0 \forall i, \sum\limits_{i=1}^{N} \lambda_i = 1, \nu_j \geqslant 0 \forall j$. Тут (в общем случае неограниченный) выпуклый многогранник задается при помощи $N$ вершин и $M$ лучей. Лучи соответствуют неограниченной части многогранника. Минимум целевой функции достигается на ограниченной части многогранника, т.е. коэффициенты при лучах берутся равными нулю. Далее отбираются вершины $\begin{bmatrix}x \\ t \end{bmatrix}_i$, на которых целевая функция достигает своего минимального значения. И далее для этих вершин (посредством симплекса) задается их выпуклая оболочка! Это и есть искомое множество оптимальных решений (представленное в форме симплекса).

Естественно, есть куча программ (свободного ПО) для перехода между $H$- и $V$-представлениями (http://www.uic.unn.ru/~zny/skeleton/, http://www.cs.unb.ca/~bremner/docs/recommend/). Однако:

Цитата:

For unbounded polyhedra, the problem is known to be NP-hard

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

Для примера выше решения задаются симплексом из двух вершин. Для данного примера V-представление состоит из порядка 1600 вершин и (ЕМНИП) 2000 лучей, и только на 2 вершинах из 1600 достигается минимум.

[Missir]

Alex Krylov в сообщении #1647631 писал(а):

Есть ли более эффективные алгоритмы отыскания "многогранника оптимальных решений", мне неизвестно

вот с этого можно было бы и начать, этим и закончить

[Alex Krylov]

-> Missir

Но одно дело многогранник, как таковой, а другое - его аналитический центр или центр масс! Тут вроде не все так плохо. Или я ошибаюсь?

[Alex Krylov]

Как то проглядел очевидное...

Если $\min\limits_{x} \left\lVert A x - b\right\rVert_1=s_0$, то на этом основании можно сформировать дополнительное ограничение вида (с учетом эффектов арифметики с плавающей запятой, чтобы сохранялась совместность системы):

$\mathbf{1}^T t = s_0+\varepsilon$, где $\varepsilon\geqslant 0$

и добавить его к исходному ограничению:
$\begin{bmatrix}A&-E \\ -A&-E \end{bmatrix} \begin{bmatrix}x \\ t \end{bmatrix} \leqslant \begin{bmatrix}b \\ -b \end{bmatrix}$

Таким образом перед нами искомый "многогранник решений" или некторое его приближение.

Далее для этого "многогранника решений" можно сформулировать дополнительную оптимизационную задачу определения аналитического центра или центра масс... и рассматривать подобное центрированное решение, как решающее проблему неединственности (ЕМНИП, где-то я подобный подход видел).

$\min\limits_{x} \left\lVert A x - b\right\rVert_2$
$\mathbf{1}^T t = s_0+\varepsilon$, где $\varepsilon\geqslant 0$
$\begin{bmatrix}A&-E \\ -A&-E \end{bmatrix} \begin{bmatrix}x \\ t \end{bmatrix} \leqslant \begin{bmatrix}b \\ -b \end{bmatrix}$

[Missir]

где то, кто то, что то видел ...
хватит нам уже лапшу на уши вешать, про $\varepsilon$ задачу здесь и так всем давно известно,
сначала разберитесь в ней, если сможете, а потом пишите

и вам кажется уже писали, что так формулировать ЗЛП для МНМ не нужно, что это вообще за самодеятельность?

[Alex Krylov]

Цитата:

и вам кажется уже писали, что так формулировать ЗЛП для МНМ не нужно, что это вообще за самодеятельность?

Да что вы [1]?

Цитата:

где то, кто то, что то видел...

Абсолютно с вами согласен! Если вы ознакомитесь с [2], то увидете, что, то, что вы пытаетесь тут излагать - это немного из другой оперы... из оперы приведения ЛП к так называемому стандартному виду.

Напомню также, что выше в данной ветке вами уже делалось не соответствующее действительности утверждение:

Цитата:

и требует для решения гораздо меньше итераций

1. Boyd S., L. Vandenberghe, Convex Optimization, Cambridge University Press 2009, стр. 617
2. Boyd S., L. Vandenberghe, Convex Optimization, Cambridge University Press 2009, стр. 147

P.S. После ознакомления с материалом по ссылкам задайтесь вопросом, как стоит относиться к исходящей от вас информации! Как к авторитетной и заслуживающей доверия?

[Missir]

предложите таким же как сами, я такую ахинею не читаю

-- 29.07.2024, 20:32 --

Alex Krylov в сообщении #1647767 писал(а):

то, что вы пытаетесь тут излагать - это немного из другой оперы

я вообще ничего не пытаюсь излагать, а указываю на то что вы не владеете предметом и при этом пытаетесь кого то учить

вот например этому

Alex Krylov в сообщении #1647644 писал(а):

Но одно дело многогранник, как таковой, а другое - его аналитический центр или центр масс! Тут вроде не все так плохо. Или я ошибаюсь?

вот это например что за бред? какую смысловую нагрузку несёт это предложение?

[Alex Krylov]

Друг мой, давайте по порядку! Выше вами были сделаны некие утверждения, которые были разоблачены, как не соответствующие действительности. Разоблачены с приведением ссылок на конкретные места в авторитетном источнике. Аргументирированных возражений от вас не последовало! А я их жду!

Давайте начнем с этого утверждения:

Цитата:

и вам кажется уже писали, что так формулировать ЗЛП для МНМ не нужно, что это вообще за самодеятельность?

Ссылочку, опровергающую это ваше утверждение я вам привел! У вас есть, что ответить по сути, аргументированно, со ссылочками?

[Missir]

Alex Krylov в сообщении #1647169 писал(а):

Решатель Mosek в любом из вариантов требует ровно 5 итераций, встроенный решатель linprog в обоих случаях - 8 итераций!

это вот тоже что за популизм? если вы такой крупный теоретик и сыпете направо и налево 3-х этажными формулами, в надежде произвести впечатление на неискушенного читателя, то приведите конкретные алгоритмы а не какие то решатели, с непонятным внутренним содержанием. В linprog можно например указать разные алгоритмы, по умолчанию там кажется interior point, а ваша цифра относится к какому? сами не знаете? В mosek вообще непонятно что напихано, но раз уж вы разбираетесь то приведите какой вы имели в виду алгоритм? Итерации то ведь весят сильно по разному, и порой быстрее выполнить 100 итераций симплекс-алгоритма, чем 5 итераций interior point. На малых задачах как эта, симплекс-алгоритм как правило вне конкуренции. Или вы и этого не знали? Не ужели в вашей мукулатуре упустили из виду это немаловажный факт?

вы тут пишите что я привожу какие то недостоверные сведения, а какие именно можете указать?

-- 29.07.2024, 21:06 --

Alex Krylov в сообщении #1647775 писал(а):

Друг мой

это вот действительно недостоверный факт, порочащий мою честь и достоинство, выбирайте друзей себе под стать

какую ссылочку вам привести?, вам же объяснили выше почему так делать не нужно, вы читать что ли не умеете?

[Alex Krylov]

Друг мой, вы опять прыгаете с темы на тему! Давайте быть последовательны и разберемся сначала с одним. Вот с этим вашим недостоверным утверждением:

Цитата:

и вам кажется уже писали, что так формулировать ЗЛП для МНМ не нужно, что это вообще за самодеятельность?

С нетерпением продолжаю ждать от вас аргументированного ответа, желательно со ссылочками!

[Missir]

Довожу до сведения уважаемых читателей, что не имею ничего общего с этим сомнительным персонажем, чего бы он про меня не писал. Приношу глубочайшие извинения, что имел неосторожность с ним пообщаться. Обещаю, что больше этого не повториться, а в знак деятельного раскаяния обязательно съем кусок хозяйственного мыла.