Quadratic Programming Solver

ipop solves the quadratic programming problem :
\(\min(c'*x + 1/2 * x' * H * x)\)
subject to:
\(b <= A * x <= b + r\)
\(l <= x <= u\)

ipop(c, H, A, b, l, u, r, sigf = 7, maxiter = 40, margin = 0.05,
     bound = 10, verb = 0)

Arguments

c: Vector or one column matrix appearing in the quadratic function
H: square matrix appearing in the quadratic function, or the decomposed form \(Z\) of the \(H\) matrix where \(Z\) is a \(n x m\) matrix with \(n > m\) and \(ZZ' = H\).
A: Matrix defining the constrains under which we minimize the quadratic function
b: Vector or one column matrix defining the constrains
l: Lower bound vector or one column matrix
u: Upper bound vector or one column matrix
r: Vector or one column matrix defining constrains
sigf: Precision (default: 7 significant figures)
maxiter: Maximum number of iterations
margin: how close we get to the constrains
bound: Clipping bound for the variables
verb: Display convergence information during runtime

Details

ipop uses an interior point method to solve the quadratic programming problem.
The \(H\) matrix can also be provided in the decomposed form \(Z\) where \(ZZ' = H\) in that case the Sherman Morrison Woodbury formula is used internally.

Value

An S4 object with the following slots

primal: Vector containing the primal solution of the quadratic problem
dual: The dual solution of the problem
how: Character string describing the type of convergence

all slots can be accessed through accessor functions (see example)

References

R. J. Vanderbei
LOQO: An interior point code for quadratic programming
Optimization Methods and Software 11, 451-484, 1999
https://vanderbei.princeton.edu/ps/loqo5.pdf

Author

Alexandros Karatzoglou (based on Matlab code by Alex Smola)
alexandros.karatzoglou@ci.tuwien.ac.at

Examples

## solve the Support Vector Machine optimization problem
data(spam)

## sample a scaled part (500 points) of the spam data set
m <- 500
set <- sample(1:dim(spam)[1],m)
x <- scale(as.matrix(spam[,-58]))[set,]
y <- as.integer(spam[set,58])
y[y==2] <- -1

##set C parameter and kernel
C <- 5
rbf <- rbfdot(sigma = 0.1)

## create H matrix etc.
H <- kernelPol(rbf,x,,y)
c <- matrix(rep(-1,m))
A <- t(y)
b <- 0
l <- matrix(rep(0,m))
u <- matrix(rep(C,m))
r <- 0

sv <- ipop(c,H,A,b,l,u,r)
sv
#> An object of class "ipop"
#> Slot "primal":
#>   [1] -0.59718844  5.19843661 -0.50415704 -0.51348030 -0.32580980 -0.51141127
#>   [7]  5.23945755 -0.50284952  5.28652931  4.90622092  5.19854341 -0.41563671
#>  [13]  5.23918924 -0.55335189  5.23942547 -0.51879340 -0.48185181 -0.48757252
#>  [19] -0.48063012 -0.48540304 -0.47211565 -0.49359031  0.24588067  5.02069536
#>  [25] -0.49059153  5.18812293  5.23319911 -0.43206440  5.20900049  5.03679765
#>  [31]  5.22293834 -1.38519048  5.23065915 -0.31862790 -0.49668455 -0.49943528
#>  [37]  5.17009432 -0.33283483 -0.50326566  5.17652207  5.22064948 -0.30547910
#>  [43]  5.20939462 -0.43045452 -0.47571754  5.26526060 -0.47204948  5.13779225
#>  [49]  4.90720228 -0.46490716  5.22704139  5.15422220 -0.44838135  5.21144802
#>  [55]  5.16561079 -0.47323293  5.13119613 -0.48229817 -0.06921847 -0.55643043
#>  [61]  5.23665145 -0.53058120 -0.48238273  5.19985405  5.22009537 -0.62065290
#>  [67]  5.19946600 -0.54499763 -0.47214767 -0.33566926 -1.52161831  5.19479041
#>  [73] -0.55492130  5.26365304 -0.49357036  5.11442860 -0.46857327  5.12482498
#>  [79]  5.17854924 -0.50767715 -1.03399125  5.23732149  5.21219361  5.35126223
#>  [85]  4.55675790 -0.47147718  5.06711846  5.22243046  0.03562613 -0.50133159
#>  [91]  4.93488254 -0.56536270  0.15864650  5.22639999 -0.67781538  1.35499986
#>  [97] -0.66832180 -2.03562842 -0.50693012 -0.51045526  5.20989823  5.32066910
#> [103] -0.45193709 -0.43668723 -0.52018916 -0.71671419  5.16890793 -0.39910417
#> [109]  5.06362851  5.27787455 -0.48918031  5.11322941  5.14779436 -0.55816954
#> [115]  5.36753604  5.24631974 -0.44067238  5.31752563  5.15854258 -0.49910860
#> [121]  0.11160581  5.18459381  4.78560876  5.01465194 -0.48299640 -0.67297395
#> [127]  5.65210462  5.18404848  5.14616192 -0.49866856 -0.59444587  5.07693782
#> [133] -0.50543675 -0.19433911  5.22448470 -0.38640601 -0.41150337 -0.38007689
#> [139] -0.32446169 -0.52112868 -0.12178742 -0.51623182 -0.15994793 -0.50925828
#> [145] -0.57025229 -0.49894112 -0.77874629 -0.51603555 -0.52163034  5.17722482
#> [151]  5.05512209 -0.47175801  4.83976545  5.21189982  5.01104262  4.83318961
#> [157]  5.22843929 -0.42152699 -0.34056462 -0.57425440  5.20788330  5.31698073
#> [163] -0.63745325  5.59612972 -0.45043431  5.22238618 -0.47712738 -0.47591814
#> [169]  1.14405049  4.36076413 -0.54639458  5.15368472 -0.54656037  5.19057863
#> [175] -0.46324736 -0.59184654  0.27312811 -0.29671747  5.32856863 -0.47917662
#> [181]  5.11346931 -0.49316871  5.13694946  5.22914129  1.58865885  5.23789820
#> [187]  5.11374619 -0.51378763  4.79805361  4.91433708 -0.22290375  5.24903084
#> [193] -0.35508671  4.77692022  5.33164527 -0.54913480  4.78210054  5.10187833
#> [199] -0.44065910 -0.55851832  5.13940318  0.37705619 -0.51390606  5.11109673
#> [205] -0.66414583 -0.36451774 -0.45662654 -0.32675857 -0.51112964  5.32091191
#> [211]  5.37961280 -0.46124379 -0.43628182 -0.29432582 -0.28405029  5.14249733
#> [217] -0.56744228 -0.53608581 -0.13953976  5.24690408  5.15460960 -0.42809442
#> [223] -0.28092954 -0.50447784  5.19671455 -0.48781173  5.31426857 -0.51633628
#> [229] -0.55009314 -0.49643861 -0.48121290 -0.50879301  5.44729671 -0.57439321
#> [235] -0.31682620  5.18160360  0.17988968 -0.50158552 -0.54229061  5.20581506
#> [241] -0.49190359 -0.47909757 -0.76228428 -0.04296386  5.19399913  5.19074507
#> [247] -0.45133848  5.14640926 -0.51112848 -0.48636902 -0.49512513 -0.52806067
#> [253]  5.20002809 -0.48398246 -0.48520757  5.21551076 -0.50831865  5.37055823
#> [259] -0.48307466 -0.63066798 -0.53872328  5.21797615 -0.48407863 -0.49302811
#> [265]  5.29540621 -0.54743287  5.24531678  5.07269073  5.22436654 -0.45669661
#> [271] -0.55020794 -0.50159925  5.25552918 -0.48787928  5.20589540 -0.50257148
#> [277] -0.49860838  5.12558803 -0.63842455 -0.47998984 -0.50314831 -0.56485688
#> [283] -0.52394910  5.04423405 -0.49812051  5.21470686 -0.49941471  5.26937305
#> [289]  5.25265593 -0.49120039 -0.39033848  5.23274095  5.19189415  5.16710755
#> [295] -0.54592127 -0.50366146  5.18276479  5.18891301 -0.59110197  5.18747196
#> [301] -0.54334989 -0.55671923 -0.51010962  5.21766260 -0.60338845  5.21068257
#> [307] -0.49903235  5.17606056  5.30198894  5.18535267 -0.52354752  5.31933548
#> [313] -0.58694442 -0.54396303 -0.59880569 -0.41299443  5.28191767 -0.56429317
#> [319]  5.30750382 -0.63449168 -0.62307492  5.17760935 -0.54521511  5.18709531
#> [325] -0.46850920 -0.45742753  5.32302731  5.18884211 -0.53069341 -0.47269270
#> [331]  5.22426527 -0.67889805 -0.51543241  5.21353125 -0.45093232 -0.69172880
#> [337]  5.21149028 -0.60056121  5.19812635 -0.60392703  5.12261647  5.13520551
#> [343] -0.51308785 -0.55828437  5.20115335 -0.49541809 -0.49320811 -0.36805855
#> [349] -0.37976861 -0.49056277 -0.48714768 -0.45884090  5.20480475  5.47092148
#> [355] -0.52631707 -0.59152816 -0.68653292  5.16953214 -0.57769625 -0.59877962
#> [361]  5.19856117 -0.64093440  5.14511697  5.15775630 -0.47661229 -0.47271059
#> [367] -0.50148105  5.12353661 -0.51267857  4.89989196 -0.48659141  5.23931107
#> [373] -0.77621760 -0.66580011 -0.62228047  5.16868565  5.20038783  4.09528949
#> [379] -0.48377072 -0.44854763 -0.44248432 -0.48062931 -0.47874848  5.15318681
#> [385]  5.10474324  5.01250422 -0.58154337 -0.59907859 -0.48512330 -0.51678311
#> [391]  5.39722448 -0.50194944  5.18502643 -0.71448260 -0.55480265 -0.57888018
#> [397] -0.42993597  4.88655041  5.24477887 -0.49175634  5.11999866  5.23692324
#> [403] -0.48489188 -0.49297966  5.20833255 -0.52997124  5.40711630 -0.52102943
#> [409] -0.51051595  5.51918520  5.19843661 -0.49077303 -0.35247201 -0.53395457
#> [415] -0.24883762 -0.58372707  5.37675279 -0.43615217 -0.31327933  5.21474184
#> [421] -0.44848335 -0.53971103  5.31602943  5.30546269  5.27088701 -0.65282173
#> [427] -0.15543507 -0.48722791  4.94041690 -0.51707550  5.88499409 -0.48725797
#> [433]  5.19208986 -0.26510967 -0.48407731 -0.67923693 -0.60849758  5.31565710
#> [439] -0.55104752 -0.31851093  5.20220544  5.48601579 -0.57593919 -0.80347203
#> [445]  5.19843562 -0.61052156 -0.52940948  5.20150449 -0.29962045  5.22059324
#> [451]  4.96843318 -0.48413519 -0.43384852  5.92877835  5.09795020 -0.48269453
#> [457] -0.53770006 -0.46921015  5.21485847 -0.53386917 -0.56130734 -0.46692407
#> [463]  5.63091145 -0.50376891 -0.48276734  5.19644657  5.31639336 -0.50128310
#> [469] -0.54255790  5.20163115 -0.55089789 -0.51599796  5.22869469 -0.50706928
#> [475]  5.25577530 -0.56738937 -0.61081176 -0.48407730 -0.63148411 -0.48190165
#> [481] -0.60197421 -0.55391542 -0.43261576  5.19889766 -0.52048523  5.19084427
#> [487]  5.13401559  5.18853344 -0.63086995  5.36394769  5.07874871  5.32229212
#> [493]  5.23032705 -0.48407731 -0.52740217 -0.61861684 -0.52823350 -0.61329883
#> [499] -0.55358123  5.17455450
#> 
#> Slot "dual":
#> [1] -125.6753
#> 
#> Slot "how":
#> [1] "slow convergence, change bound?"
#> 
dual(sv)
#> [1] -125.6753