LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 7 (http://book.caltech.edu/bookforum/forumdisplay.php?f=136)
-   -   Question about the constraints in Quadratic Programming (http://book.caltech.edu/bookforum/showthread.php?t=1142)

tadworthington 08-24-2012 12:18 PM

Question about the constraints in Quadratic Programming
 
So I'm trying to do the SVM problems, and I am running into a problem with the package I'm using (CVXOPT in Python) complaining that the rank of the 'A' matrix is less than p, where A is an nxp matrix.

The thing is, the rank of the matrix IS less than p - the 'A' matrix is y^{T}. So y^{T}\alpha = 0 is problematic, since y^{T} is problematic. I don't understand QP well enough to understand why this matrix has to have 'full' rank, but it seems to. Anybody else running into this problem?

patrickjtierney 08-24-2012 01:05 PM

Re: Question about the constraints in Quadratic Programming
 
That's odd. Wouldn't p=1 which is exactly the column rank of Y? Have you tried setting A=Y instead of the transpose. Just guessing though. I'm not familiar with that library.

jiunjiunma@gmail.com 08-24-2012 01:39 PM

Re: Question about the constraints in Quadratic Programming
 
I am also using CVXOPT and python and didn't encounter this problem. However, the result I got from the solver was totally wrong. It even gave me some negative alphas. I suspect I might have set some parameter wrong but couldn't find it after hours of debugging:clueless:. Frustrated, I am posting my small routine to create the qp parameters here to see if extra pairs of eyes help:

Code:

def getDualQuardraticParameters(trainingData, trainingResults):
    n = len(trainingResults)
    quadraticCoefficients = []
    for i in range(n):
        for j in range(n):
            kernel = np.dot(trainingData[j], trainingData[i])
            yjyi = trainingResults[j]*trainingResults[i]
            quadraticCoefficients.append(yjyi * kernel)
    P = matrix(quadraticCoefficients, (n, n), tc='d')
    q = -1.0 * matrix(np.ones((n, 1)), tc='d')
    G = -1.0 * matrix(np.identity(n), tc='d')
    h = matrix(np.zeros((n, 1)), tc='d')
    A = matrix(trainingResults, (1,n), tc='d')
    b = matrix([0.0])

    return P, q, G, h, A, b


tadworthington 08-25-2012 07:43 AM

Re: Question about the constraints in Quadratic Programming
 
Quote:

Originally Posted by patrickjtierney (Post 4391)
That's odd. Wouldn't p=1 which is exactly the column rank of Y? Have you tried setting A=Y instead of the transpose. Just guessing though. I'm not familiar with that library.

I figured it out. It had nothing to do with 'A', and everything to do with a Python error I made :o

tadworthington 08-25-2012 07:47 AM

Re: Question about the constraints in Quadratic Programming
 
Quote:

Originally Posted by jiunjiunma@gmail.com (Post 4396)
I am also using CVXOPT and python and didn't encounter this problem. However, the result I got from the solver was totally wrong. It even gave me some negative alphas. I suspect I might have set some parameter wrong but couldn't find it after hours of debugging:clueless:. Frustrated, I am posting my small routine to create the qp parameters here to see if extra pairs of eyes help:

Code:

def getDualQuardraticParameters(trainingData, trainingResults):
    n = len(trainingResults)
    quadraticCoefficients = []
    for i in range(n):
        for j in range(n):
            kernel = np.dot(trainingData[j], trainingData[i])
            yjyi = trainingResults[j]*trainingResults[i]
            quadraticCoefficients.append(yjyi * kernel)
    P = matrix(quadraticCoefficients, (n, n), tc='d')
    q = -1.0 * matrix(np.ones((n, 1)), tc='d')
    G = -1.0 * matrix(np.identity(n), tc='d')
    h = matrix(np.zeros((n, 1)), tc='d')
    A = matrix(trainingResults, (1,n), tc='d')
    b = matrix([0.0])

    return P, q, G, h, A, b


You want to be careful what you give away in these forums...there is no *ANSWER* in the title of this post, so people who don't want too much information would not be happy seeing code posted here.

anachesa 08-28-2012 11:35 AM

Re: Question about the constraints in Quadratic Programming
 
For more understanding of the math behind this machinery, the free book + lectures to which CVXOPT examples refer, might be useful (provided you have enough time to study it):
http://www.stanford.edu/~boyd/cvxbook/


All times are GMT -7. The time now is 08:30 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.