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's gravatar image

Dmitrey
28311126
accept rate: 0%

edited 15 Sep '12, 11:05

fbahr's gravatar image

fbahr ♦
4.6k716

Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×39
×18
×9

Asked: 16 Jul '12, 15:45

Seen: 830 times

Last updated: 15 Sep '12, 11:05

OR-Exchange! Your site for questions, answers, and announcements about operations research.