Как выбрать метод и начальные условия для задачи минимизации в scipy

Question

Я пытаюсь решить следующий вопрос: у меня есть многогранник в 3D с 13 вершинами. Для точки P внутри многогранника P I требуется найти симплекс, содержащий эту точку, я хочу, чтобы симплекс имел наименьшее возможное измерение (имел наименьшее количество вершин). Вершины симплекса являются подмножеством вершин многогранника P. Я понимаю, что может быть более одного решения симплекса.

Решая эту проблему, я изучил пакет оптимизации Python, и похоже, что у меня проблема с методом, начальными условиями или интерпретацией, и мне нужна помощь в этом.

Я попытался решить эту проблему с помощью Scipy в Python. Для этого я сначала приведу 13 точек, которые лежат на их выпуклой оболочке.

import numpy as np
convex_mat = np.array([[[255, 161,   0],
    [ 37,  80, 180],
    [167,   1,  33],
    [ 43,  41,  44],
    [ 42,  41,  45],
    [255, 227,   0],
    [255, 247, 254],
    [ 14,  50,  55],
    [182,  34,  60],
    [ 26,  54, 118],
    [ 42,  37,  54],
    [ 51, 100,  58],
    [212,  34,  32]]]) 

Теперь я создаю проблему минимизации. Точка в многограннике может быть выражена как линейная комбинация из 13 вершин многогранника, и цель состоит в том, чтобы как можно больше коэффициентов было равно нулю. Я также изменяю функцию знака на шаговую функцию с большей ошибкой, чтобы иметь что-то менее чувствительное. Ограничения следующие: поскольку точка X является выпуклой комбинацией вершин, сумма коэффициентов равна 1. Другие ограничения означают, что точка X является линейной комбинацией вершин. Границы заключаются в том, что коэффициенты могут быть только между 0 и 1.

from scipy.optimize import minimize
fun = lambda a: sum(1 - 1*(a < 0.00001))

cons = ({'type': 'eq', 'fun': lambda a: sum(a) - 1},
    {'type': 'eq', 'fun': 
        lambda a: convex_mat[0][:,0].dot(a) - x[0]},
    {'type': 'eq', 'fun': 
        lambda a: convex_mat[0][:,1].dot(a) - x[1]},
    {'type': 'eq', 'fun': 
        lambda a: convex_mat[0][:,2].dot(a) - x[2]}
   )
bnds = ([0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1],
        [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1])

Затем я выбрал метод SLSQP и начальную точку 0. В качестве точки в многограннике я выбрал среднюю точку двух вершин многогранника, поэтому мы знаем, что правильное решение имеет только ненулевые точки.

x = 0.5*(convex_mat[0][0] + convex_mat[0][1])
res = minimize(fun, [0,0,0,0,0,0,0,0,0,0,0,0,0], 
        method='SLSQP', bounds=bnds, constraints=cons)

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