CVXOPT 似乎为这个简单的二次程序提供了非最优结果

Question

我正在尝试使用 CVXOPT 求解一个简单的二次规划，但我很困扰，因为我可以猜测出比求解器提供的最优解更好的可行解。优化的形式为：

我会在最后给出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 并进一步最小化 objective:

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]

这导致 objective 为 -2/3，明显小于 0。我认为 Ax=b 测试中的 2.78e-17 错误不相关。

如能帮助解决此问题，我们将不胜感激！下面是代码中相关矩阵的定义（最大矩阵是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])

Answer 1

您的二次型在假设方面无效。

它需要是 PSD（并且是对称的）。

使其对称：

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），由一些非凸优化问题提供。这不会起作用（通常）。

CVXOPT 似乎为这个简单的二次程序提供了非最优结果

CVXOPT seemingly provides non-optimal result for this simple quadratic program

python

cvxopt

quadratic-programming