[ANN] routine for linear least norms problems with specifiable accuracy

 0 hi all, I have wrote a routine in Python language using OpenOpt and its solvers to solve dense / sparse problems min { alpha1 * norm(A1 x - b1, 1) + alpha2 * norm(A2 x - b2, 2)^2 + beta1 * norm(x, 1) + beta2 * norm(x, 2)^2 }  with specifiable accuracy fTol > 0: abs(f-f*) <= fTol (This parameter, fTol, 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/linear_model.html#elastic-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) BTW, you can start/pause/stop solver using a basic OpenOpt GUI. 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, but it could be done. Regards, Dmitrey asked 16 Jul '12, 15:45 Dmitrey 283●1●11●26 accept rate: 0% fbahr ♦ 4.6k●7●16
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: