Вопрос о возможной точке линейной программы
Я читал ответ на пост здесь,
Найти, если точка находится внутри выпуклой оболочки для набора точек, не вычисляя саму оболочку /questions/17705482/najti-nahoditsya-li-tochka-vnutri-vyipukloj-obolochki-dlya-nabora-tochek-ne-vyichislyaya-samu-obolochku/17705495#17705495
в котором говорится, что линейная программа с перечисленными условиями будет иметь решение тогда и только тогда, когда конкретная проверяемая точка является частью выпуклого набора данных. Я пытался запрограммировать это с помощью решателя COIN-CLP LP и не могу сопоставить предлагаемый метод с методами, доступными в библиотеке CLP. Мне кажется, что объяснение, данное в ссылочном посте, является неполным, иначе я просто не совсем понимаю проблему линейной программы.
Я не понимаю, заключается ли метод в том, чтобы разработать линейную программу для набора данных и затем определить, является ли данная точка допустимой точкой в этом решении, или же этот метод заключается в попытке сделать линейную программу из данных набор, включающий в себя проверенную точку.
Я также не понимаю, как данные должны быть введены в решатель LP. Первым шагом в инструкциях является объявление структуры данных A,
Set A = (X[1], X[2], ... X[n])
that is, the first column is v1, the second v2, etc.
Находится ли X[1] в обозначениях над первым элементом массива точек для каждой строки или это коэффициент LP для первого элемента? Являются ли данные, которые должны быть введены как векторы, причем каждый столбец является отдельным вектором (имеется в виду транспонирование столбцов для создания входных данных)? Почему в инструкциях упоминается, что первый столбец v1, когда v не появляется ни в одной другой части инструкции? Предполагается, что A - это матрица набора данных, с которой проверяется точка? Должна ли матрица всех данных, включая тестируемую точку? Я предполагаю, что кто-то, кто сделал много моделирования ЛП, уже знал бы это, но мне это не ясно.
Дается набор ограничений, которые относительно ясны,
minimize (over x): 1
s.t. Ax = P
x^T * [1] = 1
x[i] >= 0 \forall i
where,
x^T is the transpose of x
[1] is the all-1 vector
Является ли x, указанный в ограничениях, проверяемой точкой, является ли он тем же самым x, что и X в A = (X[1], это что-то другое? Я думаю, что X в A - это не x в ограничениях, потому что верхний регистр и один нижний, но я не знаю.
Мое лучшее предположение состоит в том, что проверяемые данные вводятся как A, а проверяемая точка вводится как x (нижний регистр), но я не уверен в этом и не уверен, как A должен выглядеть как структура данных.
Я думаю, мне нужно знать,
- как проверяемая точка вводится в решатель
- как данные, по которым проверяется точка, введены
- Существуют ли предположения о данных, которые подразумеваются в ограничениях (диапазон, масштабирование и т. д.)
это один из примеров (в R7) данных, которые я хотел бы проверить,
test point,
-0.9422, 2.02568, -0.86967, 0.855568, -0.601532, 0.323411, 0.596289
test against,
-0.879254, -6.62066, -7.34114, 0.585723, 2.78475, -0.387155, 2.99808
8.42321, -3.20765, -1.0542, -4.1625, 2.92884, -0.327967, 3.50838
10.774, 0.545379, -1.12841, -1.5456, -0.697098, -0.74527, -0.774246
4.94671, 0.26215, -3.77845, -0.191081, 6.03136, 3.66745, -6.22697
8.72006, -4.73847, -0.93998, -3.85806, 3.76628, 0.499046, 2.02952
4.02597, -3.96582, -3.72078, -5.20739, 7.33248, -0.41624, 2.88221
8.16238, -2.51468, -6.8052, -2.9021, 2.28175, -2.72354, -0.313697
-0.0458385, -2.56746, -4.00668, -4.6656, 8.62974, -1.00593, 4.6638
6.81399, -3.65807, -4.21049, -3.78946, 4.7107, -1.2893, 5.65669
-2.03821, -5.98271, -6.61833, -2.62184, 5.20874, -1.79854, 5.31864
5.45169, -6.62274, -0.878738, -5.38384, 4.09504, -0.626197, 5.56643
1.44436, -9.92098, 4.99388, 3.21483, -1.66346, 3.64611, -0.0439071
-2.53507, -3.18565, 6.33243, 5.70343, 5.6815, -5.98565, -0.239556
-1.06284, -6.71054, -7.89752, -1.71425, 5.42546, -1.42733, 5.34596
9.96752, -5.18027, -1.43649, -4.85739, 3.4546, -0.765721, 3.39876
6.14065, -6.80276, -4.45474, -4.45472, 4.96714, -1.12068, 5.68639
0.789644, 4.46502, 0.667421, -0.753405, 11.1041, 5.58855, -2.47415
3.4069, -2.47077, -6.1166, -3.97326, 10.5417, 1.11918, 0.915666
9.90365, -3.71723, -4.98727, -4.18883, 5.12366, -2.19175, 2.14106
7.50469, -6.45069, -1.76295, -5.8613, 4.92941, -1.28936, 5.62019
0.784531, -4.41507, 7.81695, 6.00103, 5.11466, -7.41083, -0.859709
8.76947, -6.89332, -2.22446, -5.56305, 4.37828, -0.904622, 5.32845
10.361, -5.37848, 0.280192, 6.50686, 0.295681, 5.4023, 0.903526
4.23739, -2.91606, -5.48661, -4.01339, -0.250081, -9.08589, -7.44781
10.3283, -2.70868, 2.08743, 9.13842, 0.496487, 4.09732, 0.356068
6.29274, -10.344, 3.09637, 3.86458, 6.52654, -4.4275, 2.03636
2.77549, -5.52054, -10.1449, -5.1293, 5.97665, -5.38324, 2.84052
-1.53211, -8.28862, 5.89797, 8.91702, 5.26826, -7.60942, -1.76916
6.55035, -5.0121, -9.87386, -5.39377, 3.79171, -10.0618, -3.29243
6.16032, -9.05789, -5.40621, 12.851, -0.897329, 8.45366, 2.49965
-2.0535, -7.28366, 8.4009, 10.4692, 8.09746, -13.0538, -2.21631
-0.100108, -2.19943, -5.25283, 0.665639, -2.74879, -1.88559, -2.01111
-6.68807, -2.0858, -1.67507, 1.09343, -0.425115, 1.13627, 1.38262
5.52471, 6.96936, -0.195879, 2.15077, 0.580036, -2.21135, 5.11126
3.03433, -5.15217, -1.53586, -6.28597, 4.69399, -1.2563, 6.01448
0.143787, -1.69845, -3.46485, -3.37431, -1.68215, -8.23386, -7.67879
11.971, 1.98691, -2.03594, 5.68318, -1.72722, 2.49254, 0.985464
7.28228, -12.0396, -4.96597, 14.202, -1.74251, 8.69396, 2.39749
7.82083, -8.19497, -13.3157, -5.08318, 9.88666, -5.91352, 7.07704
0.329034, -11.9767, 9.11734, 15.1535, 12.8102, -17.7227, -2.09866
Для приведенного выше примера контрольная точка не входит в выпуклый набор остальной части данных. Я программирую это с помощью COIN LP solver (clp), если смогу точно определить, что я пытаюсь запрограммировать. Я мог бы использовать другой решатель для целей тестирования, если это рекомендуется.
Может кто-нибудь помочь с этим?
Спасибо,
LMH