Я читал ответ на пост здесь,
Найти, если точка находится внутри выпуклой оболочки для набора точек без вычисления самой оболочки https://stackoverflow.com/a/11731437
, которая заявляетлинейная программа с перечисленными условиями будет иметь решение тогда и только тогда, когда конкретная проверяемая точка является частью выпуклого набора данных.Я пытался запрограммировать это с помощью решателя 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.
Is 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 (нижний регистр), ноЯ не уверен в этом, и я не уверен, как А должен выглядеть как структура данных.
Я думаю, мне нужно знать,
- как проверяется точкавведено в решатель
- как данные, с которыми проверяется точка, введено
- есть предположения о данных, которые неявно присутствуют в ограничениях (диапазон, масштабирование и т. д.)
это один пример(в 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 (clp), если я когда-нибудь смогу точно определить, что я пытаюсь запрограммировать.Я мог бы использовать другой решатель для тестовых целей, если это рекомендуется.
Может кто-нибудь помочь с этим?
Спасибо,
LMH