Как исследовать множество неотрицательных векторов в соответствии с набором проекций?

Question

Я пытаюсь вывести неизвестный вектор x в многомерном пространстве (тысячи измерений), и у меня хорошие измерения его проекций на несколько (15) направлений - то есть, если столбцы v[i,j] сформировать основу для пространства, я знаю v[,j]*x = v[1,j]*x[1]+...+v[n,j]*x[n] для 1<=j<=15, с хорошим представлением об ошибке.

Я также знаю, что x[i]>=0 для всех i. Я хотел бы найти способ найти неотрицательные оценки x с проекциями, близкими к наблюдаемым значениям.

Я попытался использовать минимизацию наименьших квадратов с линейными ограничениями (оптимизация квадратичной задачи с линейными ограничениями с использованием пакета quadprog в R). Тем не менее, результат не так близок к наблюдаемым проекциям, как они должны быть, основываясь на моих знаниях об ошибке наблюдения. Я хотел бы оценить, так ли это, потому что лучшего решения не существует или алгоритм не смог найти его по численным причинам.

Какой хороший метод для такого рода вещей? Или есть хитрости для выпуклой оптимизации в многомерном пространстве?

Answer 1

У вас есть набор линейных ограничений на равенство вида

a_i * x = b_i

И набор ограничений позитивности

x >= 0

Или в матричной форме

A x = b
x >= 0

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

Если все, что вам нужно, чтобы найти подходящую точку , вы можете сделать это, запустив Фаза 1 Симплексного алгоритма . Тысячи измерений не должны быть большой проблемой, поскольку линейное программирование действительно быстрое и должно обрабатывать ввод такого рода. Вы можете выбрать свой любимый решатель линейной оптимизации ^{1 2} здесь.

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

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

Answer 2

Итак, если я правильно понимаю, вам дается xp, проекция вектора x на подпространство P, которое определяется набором базисных векторов {p[i]}. Вы хотите найти некоторый неотрицательный вектор, который проецирует туда. Проблема тривиальна, если вы пропустите неотрицательное условие - просто выберите ваш спроецированный вектор:

x = sum(xp[i]*p[i])

Просто чтобы уточнить, длина xp - это размерность подпространства P и равна числу строк в p. Длина каждого p [i] равна размерности исходного многомерного пространства (именно это делает их базисными векторами).

Тот факт, что вы не выполняете вышеизложенное, говорит мне, что проекция не неотрицательна, поэтому вам нужно добавить некоторый вектор, ортогональный к P, чтобы получить желаемый результат. Проблема в том, что вы действительно не знаете, существует ли такой вектор. Например, представьте, что исходное пространство - это плоскость, а P - это линия alpha*(1,1). Если у вас отрицательная проекция (-1,-1), то независимо от того, какой вектор формы a*(1,-1) вы добавите, вы не сможете получить положительный результат. То же самое относится к любому измерению и любой проекции, которая является отрицательной в более чем одном базисе (я предполагаю, что ваши базисы ортогональны. Если это не так, все становится немного более волосатым).

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