CVXOPT в Python не может решить простую задачу квадратичного программирования

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

Ниже показан очень простой пример ошибки cvxopt.solvers.qp() в одном из трех примеров.

Вы можете видеть, что все примеры очень похожи по своей природе. Может ли кто-нибудь сказать мне, почему CVXOPT не может решить середину трех?

Большое спасибо

import numpy as np
from cvxopt.solvers import qp
from cvxopt import matrix

print '-'*70
print 'Case 1:'
P = np.array([[ 0.0084,  0.003 ],
              [ 0.003,   0.0017]])
q = np.array([[-0.36],
              [-0.02]])
G = np.array([[ 1.,  0.],
              [ 0.,  1.]])
h = np.array([[ 500.],
              [ 500.]])

results = qp(
    matrix(P),
    matrix(q),
    matrix(G),
    matrix(h),
)
print results # Works fine, {'status': 'optimal'}
print results['x']
print 'Works fine'


print '-'*70
print 'Case 2:'
P = np.array([[ 0.0042 ,  0.0015 ],
              [ 0.0015 ,  0.00085]])
q = np.array([[-0.48],
              [-0.06]])
G = np.array([[ 1.,  0.],
              [ 0.,  1.]])
h = np.array([[ 500.],
              [ 500.]])

results = qp(
    matrix(P),
    matrix(q),
    matrix(G),
    matrix(h),
)
print results # Fails, reaches max_iter, {'status': 'unknown'}
print '***Fails***'



print '-'*70
print 'Case 3:'
P = np.array([[ 0.0021  ,  0.00075 ],
              [ 0.00075 ,  0.000425]])
q = np.array([[-0.54],
              [-0.08]])
G = np.array([[ 1.,  0.],
              [ 0.,  1.]])
h = np.array([[ 500.],
              [ 500.]])

results = qp(
    matrix(P),
    matrix(q),
    matrix(G),
    matrix(h),
)
print results # Works fine, {'status': 'optimal'}
print results['x']
print 'Works fine'

python mathematical-optimization quadratic-programming cvxopt
person Gareth Williams    schedule 16.11.2016    source источник
comment
Я не могу сказать вам, почему это не удается, но имейте в виду, что QP не тривиальны, и ни один решатель не совершенен. Всегда будут неприятные случаи, хотя это немного раздражает, если это происходит в такой маленькой проблеме, как эта. Здесь он как-то расходится, так как увеличение количества итераций не помогает. У коммерческого решателя MOSEK вообще нет проблем.   -  person sascha    schedule 17.11.2016

Ответы (1)


arrow_upward
3
arrow_downward

Извините, у меня недостаточно репутации, чтобы отредактировать мой вопрос.

Кто-то в группе Google указал на ответ. Дело в том, что моя проблема плохо масштабируется. Лучше всего, чтобы элементы h были близки к 1.

Таким образом, деление G и h на 500 позволило оптимизатору работать идеально и давать правильный ответ во всех вышеперечисленных случаях.

Странно, я не могу найти упоминания об этом масштабировании в документации CVXOPT.

В любом случае, я надеюсь, что этот вопрос и ответ окажутся кому-то полезными.

print '-'*70
print 'Case 2:'
P = np.array([[ 0.0042 ,  0.0015 ],
              [ 0.0015 ,  0.00085]])
q = np.array([[-0.48],
              [-0.06]])
G = np.array([[ 1.,  0.],
              [ 0.,  1.]])
h = np.array([[ 500.],
              [ 500.]])

# Divide by 500 to get scaling correct
G /= 500
h /= 500

results = qp(
    matrix(P),
    matrix(q),
    matrix(G),
    matrix(h),
)
print results # Works fine, {'status': 'optimal'}
print 'Works fine'
person Gareth Williams    schedule 18.11.2016