# Does there exist an arbitrary-precision convex optimization solver?

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.

• 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. Nov 30, 2011 at 6:56
• 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. Nov 30, 2011 at 7:04
• Instead of penalties, could you use constraints and an active set method? Nov 30, 2011 at 13:54
• The ill-conditioning is unrelated to the penalty formulation. I originally tried it as a constrained feasibility problem and got worse results. Nov 30, 2011 at 15:12
• Have you considered B-splines or radial basis functions for your basis? Nov 30, 2011 at 19:41

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.

• I know almost nothing about implementing a convex solver, but if somebody wanted to do it that would be wonderful. Dec 2, 2011 at 15:23
• 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?). Feb 24, 2012 at 3:41

''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.

• Thanks; that's exactly what we're using in order to improve conditioning, but eventually it still gets bad. Jul 17, 2012 at 14:23

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.