CVXOPT, по-видимому, дает неоптимальный результат для этой простой программы quadrati c - PullRequest
Новая
       51

CVXOPT, по-видимому, дает неоптимальный результат для этой простой программы quadrati c

1 голос
/ 27 мая 2020

Я пытаюсь решить простую программу quadrati c, используя CVXOPT, и меня беспокоит тот факт, что я могу угадать возможное решение лучше, чем оптимальное, предоставляемое решателем. Оптимизация имеет вид:

enter image description here

В конце я приведу определения P, q, G, h, A и b. Когда я импортирую и запускаю: 

from cvxopt import matrix, spmatrix, solvers
# Code that creates matrices goes here
sol = solvers.qp(P, q, G, h, A, b)

, результат будет: 

   pcost       dcost       gap    pres   dres
 0:  0.0000e+00 -5.5000e+00  6e+00  6e-17  4e+00
 1:  0.0000e+00 -5.5000e-02  6e-02  1e-16  4e-02
 2:  0.0000e+00 -5.5000e-04  6e-04  3e-16  4e-04
 3:  0.0000e+00 -5.5000e-06  6e-06  1e-16  4e-06
 4:  0.0000e+00 -5.5000e-08  6e-08  1e-16  4e-08
Optimal solution found.

Objective = 0.0

Однако я могу определить другое решение guessed_solution, которое выполнимо и дополнительно минимизирует цель: 

guessed_solution = matrix([0.5,0.5,0.0,0.0,0.0,0.0,0.5,0.5,0.0,0.0,1.0])

# Check Ax = b; want to see zeroes
print(A * guessed_solution - b)
>>>
[ 0.00e+00]
[ 0.00e+00]
[ 2.78e-17]

# Check Gx <= h; want to see non-positive entries
print(G * guessed_solution - h)
>>>
[-5.00e-01]
[-5.00e-01]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[-5.00e-01]
[-5.00e-01]
[-1.00e+00]
[-1.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[-1.00e+00]

# Check objective
print(guessed_solution.T * P * guessed_solution + q.T * guessed_solution)
>>>[-6.67e-01]

Это приводит к цели, равной -2/3, что явно меньше 0. Я предполагаю, что ошибка 2,78e-17 в тесте Ax = b не имеет значения.

Любая помощь в решении этой проблемы будет оценена! А ниже - определение соответствующих матриц в коде (самая большая матрица - 11 на 11). 

P = matrix([[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0],[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0/3.0, 0.0, 2.0/3.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0/3.0, 2.0/3.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -1.0, 0.0, 0.0],[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -1.0, 0.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -1.0/3.0, 0.0, -2.0/3.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -1.0/3.0, -2.0/3.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]]).T
q = matrix([0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])

A = matrix([[0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0],[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],[0.0, 1.0, 1.0/3.0, 2.0/3.0, 0.0, -1.0, -1.0/3.0, -2.0/3.0, 0.0, 0.0, 0.0]]).T
b = matrix([1.0, 1.0, 0.0])

G = spmatrix([-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.0, -1.0], [0,1,2,3,4,5,6,7,8,9,10,11,12,13], [0,1,2,3,4,5,6,7,8,9,10,8,9,10])
h = matrix([0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0])

1 Ответ

1 голос
/ 31 мая 2020

Ваша форма quadrati c недействительна в отношении предположений.

Это должен быть PSD (и симметричный c).

Изготовление it symri c: 

P = (P + P.T) / 2

приведет к тому, что cvxopt покажет ошибку, которая связана с неопределенным значением P: 

import numpy as np

np_matrix = np.array(P)
print(np.linalg.eigvalsh(np_matrix))

#[-8.16496581e-01 -7.45355992e-01 -5.77350269e-01 -2.40008780e-16 -6.33511351e-17 -4.59089160e-17 -3.94415555e-22  5.54077304e-17  5.77350269e-01  7.45355992e-01  8.16496581e-01]

У вас есть решатель, предназначенный для задач выпуклой оптимизации (если и только если P - PSD) подпитывается некоторой невыпуклой задачей оптимизации. Это не сработает (в общем).

...