Поиск минимума в 30мерном кубике

[Simply me]

Добрый день! Помогите, пожалуйста! Есть уравнение $A\overline{X}= B$, $A$ - матрица, размер $m\cdotn$, $B$ и $\overline{X}$ - вектора размером $m$.
В прямой задаче нужно найти вектор $\overline{X}$, матрица $A$ и вектор $B$ - это экспериментальные данные. Известно, что в них есть погрешности. Из $A$ и $B$ можно получить правильные данные $A'$ и $B'$ умножением их поэлементно на некоторые поправочные коэффициенты $\gamma$ и $\delta$.
$A'=\begin{pmatrix}\gamma_{11}a_{11} & ... & \gamma_{1m}a_{1m}\\ ... & ... & ...\\ \gamma_{m_1}a_{m_1} & ... & \gamma_{mm}a_{mm}\end{pmatrix}$ $B'=\begin{pmatrix}\delta_1 b_1 \\ ... \\ \delta_m b_m\end{pmatrix}$
Я решаю обратную задачу, то есть мне известны компоненты матрицы $A$, вектора $B$ и и модельного вектора $\overline{X}$. Нужно найти поправочные коэффициенты $\gamma$ и $\delta$ и минимизируемую функцию $\xi$ (предельно допустимая погрешность аппроксимации экспериментальных данных). Также дан заданный порог точности в уравнениях $A\overline{X} = B$. Обозначается $\tau$.

$\xi \rightarrow \min$
$|A'\overline{X}-B'| \leq \overline{\tau}$
$|\delta_i-1| \leq \xi, i=\overline{1,m}$
$|\gamma_{ij}-1| \leq \xi, i,j = \overline{1,m}$
$\delta_i \geq 0, \gamma_{ij} \geq 0, \xi \geq 0, i,j = \overline{1,m}$
$\xi = \max \left\lbrace\max\limits_i |\delta_i - 1|; \max\limits_{ij} |\gamma_{ij} - 1| \right\rbrace$

Из этой системы нашла $\xi$ (использую LPSolve - ПО для решения задач линейного программирования (ЗЛП)). Обозначила найденное $\xi$ как $\xi^*$. Добавила в ЗЛП уравнение $\xi = \xi^*$ (найденное на предыдущем шаге значение). Вместо оптимизируемой функции указала каждый из параметров $\gamma$ и $\delta$. Устремляла их к минимуму и максимуму. Таким образом, нашла минимальные и максимальные значения каждого коэффициента $\gamma$ и $\delta$.
$\gamma_{ij} \rightarrow \min (\gamma_{ij} \rightarrow \max, \delta_i \rightarrow \min, \delta_i \rightarrow \max), i,j=\overline{1,m}$
$|A'\overline{X}-B'| \leq \overline{\tau}$
$|\delta_i-1| \leq \xi^*, i=\overline{1,m}$
$|\gamma_{ij}-1| \leq \xi^*, i,j = \overline{1,m}$
$\delta_i \geq 0, \gamma_{ij} \geq 0, i,j = \overline{1,m}$

Т.е. в результате для каждого параметра $\gamma$ и $\delta$ получила интервалы значений $[ymin_{ij}; ymax_{ij}]$, $i=\overline{1,m}, j=\overline{1,n}$. Всего 30 интервалов (размерность - 5, 30 параметров: 25 $\gamma$ и 5 $\delta$).

Посоветуйте, пожалуйста, как дальше уточнять эти интервалы, по какому алгоритму. Мне кажется, что это 30мерный кубик, в котором ищется решение. Перебор не подходит. Потому что даже если задать 2 узла на каждом ребре (что вообще очень мало), получится $2^{30}$ (миллиард) наборов. Может, какие-то параметры фиксировать по какому-то принципу, а какие-то варьировать?

[Sender]

Может, метод главных компонент попробовать?

[Simply me]

Sender, спасибо, попробую.

[vpb]

1) Метод главных компонент --- это, кажется, что-то из статистики. В статистике, да, есть оптимизационные задачи. Но это что-то не то. Я не большой специалист по оптимизации, но мне использование этого термина применительно к методам условной оптимизации неизвестно.

2) Очень многое зависит от самой целевой функции. В общем случае, даже если целевая функция --- квадратичная, но не выпуклая (т.е. у нее собственно квадратичная часть не является неотрицательно определенной), задача NP-полна, т.е., грубо говоря, не решается иначе как каким-то перебором (для строго вогнутой квадратичной функции --- конкретно перебором по всем вершинам).

[Simply me]

СЛАУ.
Саму задачу линейного программирования я не сама решаю. А с помощью lp_solver. Подаю в него набор из 30 параметров и вызываю экзешник в программе. Он рассчитывает целевую функцию. Я могу в программе найти минимальное $\xi$ и по какому набору оно рассчитано из нескольких наборов. Но вот вопрос, по какому принципу подставлять эти наборы, если множество значений, которые может принимать каждый из 30 параметров, - интервал (континиум).

[vpb]

Simply me
В Вашем последнем сообщении я понимаю разве что отдельные слова. Может объяснить подробнее и аккуратнее?

[Simply me]

Ну то есть у меня есть, скажем так, чёрный ящик, в который, если я подам значения каждого параметра, для этого набора из 30 параметров рассчитается соответствующее $\xi$. От этого черного ящика я бы не хотела отказываться. Нормально работает. Но вопрос, какие значения каждого параметра подавать, какие значения из интервалов выбрать, как осуществлять обход. Потому что сделать полный перебор всех значений 30 параметров очень проблематично. Количество моделей (рассчитанных $\xi$) получится $2^{30}$ (миллиард) для 2 узлов на каждой стороне кубика, $3^{30}$ для 3 узлов и т.д.

[vpb]

Увы, более понятно не стало... Может, Вам кто другой из участников форума поможет эту задачу более понятно сформулировать ? Вы, позвольте спросить, по образованию то кто ?

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы/обозначения (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- условие действительно нужно сформулировать более внятно.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Simply me]

vpb в сообщении #1421744 писал(а):

Увы, более понятно не стало... Может, Вам кто другой из участников форума поможет эту задачу более понятно сформулировать ? Вы, позвольте спросить, по образованию то кто ?

Программист по образованию.

[martell]

Попробуйте метод роя частиц. Один из оптимизационных алгоритмов для поиска минимума, когда градиент минимизируемой функции неизвестен. Я если честно не совсем тоже понял задачу, если не поможет, и как выше сказали что решать только перебором, то есть генетические алгоритмы, оптимизированный перебор, позволяет найти решение не переберая все пространство решений.

[podih]

Simply me в сообщении #1421721 писал(а):

Может, какие-то параметры фиксировать по какому-то принципу, а какие-то варьировать?

Вначале чистый рандом. Он позволит определить порядок переменных. Проще всего перемешивать переменные и шаги (если такая функция в ЯП есть) - а затем последовательно их совмещать.
Дальше фиксируем 29 переменных, варьируем одну. Так по очереди со всеми 30 переменными.
Если целевая функция считается быстро - секунды - то можно варьировать две, а то и три переменных. Но уже с одной нащупается минимум. Пробуйте как с фиксированными значения ранее обработанных переменных, так и с их новыми вариациями по ходу перебора.

Simply me в сообщении #1421721 писал(а):

Известно, что в них есть погрешности

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

[mserg]

На первый беглый взгляд - это задача линейного программирования.
От максов и абсов вроде как можно избавиться:
http://lpsolve.sourceforge.net/5.1/absolute.htm

[Simply me]

Спасибо!)