оптимизация выпуклости в python/cvxopt

Question

Я пытаюсь выполнить задачу ограниченной оптимизации (максимизации) с линейной целевой функцией и выпуклым ограничением, используя библиотеку cvxopt в python. В настоящее время ограничение квадратично, но я хочу сделать это в конечном итоге с общим выпуклым многочленом. Задача состоит в основном: максимизировать c_1 * x_1 + c_2 * x_2 + c_3 * x_3 при условии ограничения k_1 * x_1^(alpha + 1) + k_2 * x_2^(alpha + 1) + k_3 * x_3^(alpha + 1) < = бюджет, а x_i неотрицательный. Мой код:

import numpy as np 
from cvxopt import solvers, matrix, spdiag, mul 

c = -matrix([1.,2.,3.]) #minimize negative for maximization 
alpha = 1. 
rate_vec = matrix([.1,.2,.3]) 
budget = 1000 
def F(x = None, z = None): 
    if x is None: return 1, matrix([1.,1.,1.]) 
    if min(x) <= 0: return None 
    f = matrix(rate_vec.trans() * x**(alpha + 1.) - budget) 
    Df = matrix((alpha + 1.)*mul(rate_vec, x**alpha)).trans() 
    if z is None: return f, Df 
    H = spdiag(z[0,0]*(alpha + 1.)*alpha*mul(rate_vec, x**(alpha -1.))) 
    return f, Df, H 

t = solvers.cpl(c,F) 

Мой вывод:

pcost  dcost  gap pres dres 
0: -6.0000e+00 -1.0054e+03 1e+00 1e+00 1e+00 
1: -7.3931e+00 -1.7384e+01 2e-02 1e+00 1e+00 
2: -1.1174e+01 -1.1274e+01 4e-04 1e+00 1e+00 
3: -2.1707e+01 -2.1904e+01 8e-06 1e+00 1e+00 
4: -2.2126e+01 -2.2519e+01 2e-07 1e+00 1e+00 
5: -2.2667e+01 -2.3448e+01 3e-09 1e+00 1e+00 
6: -2.3665e+01 -2.5217e+01 6e-11 1e+00 1e+00 
7: -2.5861e+01 -2.8941e+01 1e-12 1e+00 1e+00 
8: -3.1961e+01 -3.8037e+01 2e-14 1e+00 1e+00 
9: -5.9255e+01 -7.0625e+01 5e-16 9e-01 1e+00 
10: -1.0993e+02 -1.2780e+02 9e-18 8e-01 1e+00 
Terminated (singular KKT matrix). 

Любые намеки на то, что происходит wronng?

Answer 1

выглядит как ошибка округления для зазора около 0 (e-12 -14 -16). Чтобы увидеть схождение, положить print в F:

print "f: %.3g x: %s Df: %s" % (f[0], np.squeeze(x), np.squeeze(Df)) 
=> 
... 
6: -2.4088e+02 -2.4485e+02 2e-11 3e-02 4e-02 

f: -33 x: [ 40.1 40.1 40.1] Df: [ 8. 16.1 24.1] 
f: -0.629 x: [ 40.8 40.8 40.8] Df: [ 8.2 16.3 24.5] 
    ... 

7: -2.4487e+02 -2.4495e+02 2e-13 6e-04 8e-04 
f: -0.629 x: [ 40.8 40.8 40.8] Df: [ 8.2 16.3 24.5] 
    ...  

8: -2.4495e+02 -2.4495e+02 2e-15 6e-06 8e-06 
f: -0.00639 x: [ 40.8 40.8 40.8] Df: [ 8.2 16.3 24.5] 
Terminated (singular KKT matrix). 

(немного разные значения, чем у тебя, не знаю, почему). Кроме того, cpl имеет полдюжины parameters, включая «уточнение: количество шагов итеративной доработки при решении уравнений KKT (Karush-Kuhn-Tucker)».