Выпуклая оптимизация в 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).

Есть намеки на то, что происходит?

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 имеет полдюжины параметров, включая "уточнение: количество итерационных этапов уточнения при решении уравнений ККТ (Каруша-Куна-Такера)" .