ValueError: Rank(A) < p or Rank([P; A; G]) <

[Arnab Ray]

I encountered a very frustrating result on a convex optimization on "Protein-Fold" dataset clustering and the error is given by- 

ArithmeticError Traceback (most recent call last) /usr/local/lib/python3.6/dist-packages/cvxopt/misc.py in factor(W, H, Df) 1428 if type(F['S']) is matrix: -> 1429 lapack.potrf(F['S']) 1430 else: ArithmeticError: 1 During handling of the above exception, another exception occurred: ArithmeticError Traceback (most recent call last)

7 frames

/usr/local/lib/python3.6/dist-packages/cvxopt/coneprog.py in coneqp(P, q, G, h, dims, A, b, initvals, kktsolver, xnewcopy, xdot, xaxpy, xscal, ynewcopy, ydot, yaxpy, yscal, **kwargs) 2064 for rti in W['rti']: rti[::rti.size[0]+1 ] = 1.0 -> 2065 try: f = kktsolver(W) 2066 except ArithmeticError: /usr/local/lib/python3.6/dist-packages/cvxopt/coneprog.py in kktsolver(W) 1980 def kktsolver(W): -> 1981 return factor(W, P) 1982 /usr/local/lib/python3.6/dist-packages/cvxopt/misc.py in factor(W, H, Df) 1443 if type(F['S']) is matrix: -> 1444 lapack.potrf(F['S']) 1445 else: ArithmeticError: 1 During handling of the above exception, another exception occurred: ValueError Traceback (most recent call last) <ipython-input-9-75ef9e078e2d> in <module>() 1 for il in range(len(lambdaset)): ----> 2 [H_normalized8,gamma81,obj81] = myregMKKM(KH,Htrntrn,numclass,lambdaset[il]) 3 res8 = myNMIACC(H_normalized8,Y,numclass) 4 accval8[il] = res8[0] 5 nmival8[il] = res8[1] <ipython-input-7-e79447b3c036> in myregMKKM(K, M, cluster_count, lambd) 267 [H,objective]=myKernelKmeans(KC,cluster_count) 268 obj = obj.append(callObj(H,K,M,gamma0,lambd)) --> 269 [gamma]= updatekernelweightsV2(H,K,M,lambd) 270 gamma0 = gamma 271 if (iter>2 & (np.abs((obj[iter-1]-obj[iter])/(obj[iter-1]))<1e-6)): <ipython-input-7-e79447b3c036> in updatekernelweightsV2(Tm, K, HE0, lambd) 57 ub = np.ones((nbkernel,1)) 58 ---> 59 sol= solvers.qp(matrix(H),matrix(f),matrix(Aeq),matrix(beq)) 60 gamma=np.array(sol['x']) 61 obj=sol['primal objective'] /usr/local/lib/python3.6/dist-packages/cvxopt/coneprog.py in qp(P, q, G, h, A, b, solver, kktsolver, initvals, **kwargs) 4483 'residual as dual infeasibility certificate': dinfres} 4484 -> 4485 return coneqp(P, q, G, h, None, A, b, initvals, kktsolver = kktsolver, options = options) /usr/local/lib/python3.6/dist-packages/cvxopt/coneprog.py in coneqp(P, q, G, h, dims, A, b, initvals, kktsolver, xnewcopy, xdot, xaxpy, xscal, ynewcopy, ydot, yaxpy, yscal, **kwargs) 2065 try: f = kktsolver(W) 2066 except ArithmeticError: -> 2067 raise ValueError("Rank(A) < p or Rank([P; A; G]) < n") 2068 2069 ValueError: Rank(A) < p or Rank([P; A; G]) < n  

How to fix this crap?

[Martin]

The solver requires that Rank(A) < p or Rank([P; A; G]) < n which is a common assumption (see documentation). My guess is that you have redundant constraints.

[Fan Ye]

Hi Martin,

I implemented a nonlinear optimization model and encountered the same ValueError in the first iteration of the primal-dual process. My problem has simple structure: only non-linear objective and non-negativity constraints.  I checked the rank of Hessian of the objective and confirmed it is of full rank (though there are negative eigenvalues but the Hessian is far from singular ); therefore,  Rank([H; A; G]) =n , as A is None and G is the negative identity matrix.

Could you please help me understand how the solver works from the observations below? 

1. When I followed your post elsewhere and switched to kktsolver="ldl",  the solvers.cp actually works and it converges to an optimum.  Do you have an idea how the kktsolver option made a difference here?

2. As mentioned,  the Hessian at the initial point has negative eigenvalues.  It looks solvers.cp could still reach an "optimum", at which its Hessian has  negative eigenvalues that are very close to (or numerically) 0.  In addition, I tried different initial points and the solver would converge to another optimum (or saddle point most likely).   I am wondering if solvers.cp supports solving a non-convex problem and the solution found is a local optimum?

Thank you in advance for your time and help!

Regards,

Fan

[Martin]

Re 1: The KKT solvers differ in how they solve the Newton equations (you can read more about that here). There can be different reasons why it helps to choose another KKT solver. For example, the Cholesky-based KKT solver may fail to detect singularity because of rounding errors.

Re 2: solvers.cp() does not support non-convex problems. 

Martin

[Fan Ye]

Great! Thanks so much for the reference and confirmation.