7
$\begingroup$

I have a relatively simple convex optimization problem that involves less than 100 variables but contains a terribly ill-conditioned matrix. I have tried CVX and CPLEX; even though both can typically solve the problem in about 1 second, both fail when the condition number of the matrix becomes very large. An arbitrary-precision solver would be able to solve this problem quickly and accurately. Does any such implementation exist?

Note: The conditioning of the problem has been considered in detail and is not part of this question. I'm just asking about software.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ If the matrix is terribly ill-conditioned, there's always the possibility that you're "asking the wrong question"; see if you can reformulate your original problem so that you don't have to deal with ill-conditioned matrices. $\endgroup$
    – J. M.
    Commented Nov 30, 2011 at 6:56
  • $\begingroup$ You are using a penalty method, aren't you? Didn't we have this discussion last week? ;-) Can you build any of your favorite optimization packages with __float128? That would probably be enough to handle your penalty. $\endgroup$
    – Jed Brown
    Commented Nov 30, 2011 at 7:04
  • 1
    $\begingroup$ Instead of penalties, could you use constraints and an active set method? $\endgroup$
    – Matt Knepley
    Commented Nov 30, 2011 at 13:54
  • $\begingroup$ The ill-conditioning is unrelated to the penalty formulation. I originally tried it as a constrained feasibility problem and got worse results. $\endgroup$
    – David Ketcheson
    Commented Nov 30, 2011 at 15:12
  • 1
    $\begingroup$ Have you considered B-splines or radial basis functions for your basis? $\endgroup$
    – rcollyer
    Commented Nov 30, 2011 at 19:41

3 Answers 3

Reset to default
3
$\begingroup$

As far as I know, there is no complete library that does what you are looking for, but parts of it are available. MPMath is an arbitrary precision library for Python that contains a matrix module with linear algebra functionality. It should not be too difficult to implement a convex solver with this library.

Note. I agree with the comments above. If a numerical problem is terribly ill-conditioned, I'd recommend that you understand why, and try to improve the description of the problem to lower the condition number.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I know almost nothing about implementing a convex solver, but if somebody wanted to do it that would be wonderful. $\endgroup$
    – David Ketcheson
    Commented Dec 2, 2011 at 15:23
  • $\begingroup$ I have trouble with this answer only because "implement a convex solver" can range from "let's implement Newton's method" to something like "let's flesh out an SQP algorithm with good initial guess and adaptive step-size heuristics". It's absolutely correct in principle, but nontrivial (and probably slightly time-consuming) in practice. Also, from an optimization perspective, it's probably not research-worthy on its own unless you can demonstrate it on a class of ill-conditioned problems that are important in practice (maybe David's problems would suffice?). $\endgroup$
    – Geoff Oxberry
    Commented Feb 24, 2012 at 3:41
2
$\begingroup$

''I don't know how to choose a polynomial basis that is well conditioned with respect to arbitrary sets of points in the complex plane.''

If the set of points is bounded, a good basis of polynomials of degree $d$ to use is the Lagrange polynomials of $d+1$ reasonably spaced point along an enclosing contour. This will give you far better results than a multiprecision solution of a problem involving a Vandermonde matrix.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks; that's exactly what we're using in order to improve conditioning, but eventually it still gets bad. $\endgroup$
    – David Ketcheson
    Commented Jul 17, 2012 at 14:23
1
$\begingroup$

Here is complete (with the exception of sparse matrices) package for linear algebra in arbitrary precision:

Multiprecision Computing Toolbox for MATLAB

It integrates smoothly with Matlab and provides routines for all common operations from determinants to SVD and eigenvalues.

Actually it also covers other areas - numerical integration, optimization, ode, special functions, etc.

As for function minimization you could try Nelder–Mead simplex method (fminsearch) implemented in the toolbox too.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.