[Numpy-discussion] routine for linear least norms problems with specifiable accuracy

Dmitrey tmp50@ukr....
Mon Jul 16 12:35:09 CDT 2012




hi all,


I have wrote a routine to solve dense / sparse problems 
min {alpha1*||A1 x - b1||_1 + alpha2*||A2 x - b2||^2 + beta1 * ||x||_1 +
beta2 * ||x||^2}
with specifiable accuracy fTol > 0: abs(f-f*) <= fTol (this parameter is
handled by solvers gsubg and maybe amsg2p, latter requires known good
enough fOpt estimation). Constraints (box-bound, linear, quadratic) also
could be easily connected.


This problem is very often encountered in many areas, e.g. machine
learning, sparse approximation, see for example
http://scikit-learn.org/stable/modules/ ? lastic-net


First of all solver large-scale gsubg is recommended. Some hand-tuning of
its parameters also could essentially speedup the solver. Also you could
be interested in other OpenOpt NSP solvers - ralg and amsg2p (they are
medium-scaled although).


You can see the source of the routine and its demo result here.


You shouldn't expect gsubg will always solve your problem and inform of
obtained result with specifiable accuracy - for some very difficult, e.g.
extremely ill-conditioned problems it may
* fail to solve QP subproblem (default QP solver is cvxopt, you may
involve another one, e.g. commercial or free-for-educational cplex)
* exit with another stop criterion, e.g. maxIter has been reached, or
maxShoots have been exceeded (usually latter means you have reached
solution, but it cannot be guaranteed in the case)


First of all I have created the routine to demonstrate gsubg abilities; I
haven't decided yet commit or not commit the routine to OpenOpt, with or
without special class for this problem; in either case you can very
easily create problems like this one in FuncDesigner (without having to
write a routine for derivatives) to solve them by gsubg or another NSP
solver; however, IIRC FuncDesigner dot() doesn't work with sparse
matrices yet
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/numpy-discussion/attachments/20120716/b5ae13a1/attachment.html 


More information about the NumPy-Discussion mailing list