7
$\begingroup$

I am really confused by the usage of solver in computational optimization. I have looked around for a month on and off in order to see if I can get a good sense of what this term means yet I still do not have any good understanding of it.

It seems that, if I would like to solve an optimization problem in machine learning or elsewhere, I would refer to the exact computational procedure as an algorithm instead a solver. For example, if I had a quadratic program, I would use MATLAB's Quadprog function to solve the QP.

I would personally not refer to Quadprog function as a QP solver, because it is just a MATLAB function, or a script. I would not refer to the exact algorithm behind Quadprog as a QP solver, I don't care if it is gradient descent, interior point method, Newton Raphson...they are all algorithms to me. Finally, I would not refer to MATLAB as a QP solver because that is not MATLAB's sole purpose. So it seems that the word "solver" is missing from my everyday vocabulary despite having to routinely work with optimization, this confuses me quite a bit, it just feels I am not up to date with the lingo.

So by my reasoning, algorithms and MATLAB are not solvers. But suppose I have downloaded some softwares such as Gurobi or YALMIP to solve optimization problems, are these softwares called solvers? I have often time heard people referencing what "solver" you are using in sort of the same tone as what "software" you are using. What differentiate optimization softwares and solvers?

I know this sounds like a really rudimentary question, but I have only done optimization in MATLAB.

$\endgroup$
  • $\begingroup$ I've understood "solver" to mean an optimizer for problems with unique solutions, but perhaps I'm misinformed. $\endgroup$ – Sycorax says Reinstate Monica Oct 20 '16 at 0:24
  • $\begingroup$ In general, a solver to optimization is similar as an engine is to driving. I would call Gurobi a solver, it's like an engine. MATLAB is like a car brand, it's the name for the overall environment. $\endgroup$ – Matthew Gunn Oct 20 '16 at 0:26
  • $\begingroup$ I usually hear "solver" used to describe software, meaning it applies to an implementation of an algorithm. Generally the term will be reserved for mathematical problems with a "well-defined solution". A unique solution is sufficient, as @Sycorax says, and the Gurobi solvers seem to be for problems in this class. But I do not think unique is necessary, for example both local and global optimization problems can have well-defined but non-unique solutions. $\endgroup$ – GeoMatt22 Oct 20 '16 at 6:48
4
$\begingroup$

I suggest a solver is:

  • a software package
  • that incorporates one or more algorithms
  • for finding solutions to one or more classes of problem

The classes of problem is part of it. It is a X solver.

So

  • I would call Gurobi "a MIP/LP solver".
  • And I would say "Matlab incorperates a QP solver, that it exposes via the Quadprog function.", In this case the actual "QP solver" may or may not exist as a stand alone product.
  • Concorde is a TSP solver
  • Concorde incorporates QSopt, which is a LP solver

I think this usage is in line with (for example) the JuMP documentation

JuMP is a domain-specific modeling language for mathematical optimization embedded in Julia. It currently supports a number of open-source and commercial solvers (see below) for a variety of problem classes, including linear programming, mixed-integer programming, second-order conic programming, semidefinite programming, and nonlinear programming.

Here is a list of things that JuMP calls solvers. None of them are algorithms, all are specific programs

$\endgroup$
5
$\begingroup$

A solver is a routine for finding exact numerical answers for determined systems. For example, when using Newton-Raphson to find root(s). When a system is overdetermined then one generally uses approximate solutions, for example, regression. One would generally not refer to regression as a solver, although, predictably language can be misused, and many routines that are approximate are loosely called solvers. For example, the CUTEr optimization software package contains algorithms at least some of which are for overdetermined systems, and some of which are solvers, so it becomes easy to say, I am downloading a "solver". Both solvers and regression methods are examples of optimization methods.

$\endgroup$
  • $\begingroup$ Why does the system have to be determined? Can't it be underdetermined? Eg. calling most any linear system solving routine on $x + y =1$ will return a solution. $\endgroup$ – Matthew Gunn Oct 20 '16 at 1:02
  • $\begingroup$ @MatthewGunn Perhaps, but for $x+y=1$ one could use a random number generator because any random $x$ will generate a $y$. Now I suppose one could call a random number generator a "solver." However, I think you would admit, it is a stretch to do so. Usually, a solver would do something more organic with random numbers, if it uses them at all. $\endgroup$ – Carl Oct 20 '16 at 1:13
  • 2
    $\begingroup$ A solver gives a solution. If the problem is "SOLVE $x+y=1$" then $x=1, y=0$ is a solution and it may return that solution (or any other solution)! To put it another way, is Python's lstsq not a linear system solver because it can solve undetermined systems? $\endgroup$ – Matthew Gunn Oct 20 '16 at 1:50
  • $\begingroup$ @MatthewGunn Besides, iterative methods of regression can be programmed to solve determined systems, but, that would not make them solvers, as their main use is for overdetermined systems. $\endgroup$ – Carl Oct 20 '16 at 1:51
  • 1
    $\begingroup$ yes, I agree I'm being nitpicky and apologize for that. If I were writing the answer, I wouldn't include the text "for determined systems." Otherwise though, excellent answer! (Eg. one other example... solvers for boolean satisfiability problems almost always have a multitude of solutions and the goal is to simply find one of them (in those problems, the systems are almost always undetermined). $\endgroup$ – Matthew Gunn Oct 20 '16 at 2:00
1
$\begingroup$

I usually hear "solver" used to describe software, meaning it applies to a particular implementation of an algorithm. For example, this seems to apply to most of the SciComp.SE questions tagged solver.

Generally the term seems to be reserved for mathematical problems with a "well-defined solution". A unique solution would qualify as "well defined" sufficient, as noted by Sycorax in the comments. (The Gurobi solvers seem to be for problems in this class; for what its worth, Gurobi looks like a suite or library of solvers to me).

But I do not think unique is necessary. For example both local and global optimization problems can have well-defined but non-unique solutions (e.g. the function $f[x]=\sin[\pi x]^2$ has global minimum $f[k]=0$ for $k\in\mathbb{Z}$).

I disagree with this answer, which seems to be discussing "equation-system solvers" rather than "optimization solvers". For example in linear least squares, the linear algebra problem is over-determined, but the optimization problem is convex, with a unique solution (in non-degenerate cases). Note also that the Wikipedia "solver" page linked in that answer lists "Linear and non-linear optimisation problems, Shortest path problems, Minimum spanning tree problems" among its examples.


In response to the comment, I will clarify what I mean in the "regression" case.

Given a function $F:\mathbb{R}^n\to\mathbb{R}^m$, a solution to the system of equations specified by $$F[x]=0$$ is a vector $x\in\mathbb{R}^n$ such that all $m$ components of $F[x]$ are zero. Depending on the function $F$, there can be no solutions, a single unique solution, or many solutions (typically infinitely many), depending on the dimension of the null-space of $F$. In the case where $F$ is linear, i.e. $F[x]=Ax-b$ for some $A\in\mathbb{R}^{m\times{n}},b\in\mathbb{R}^m$, then no solution can exist unless $m\leq\mathrm{rank}[A]\leq n$.

On the other hand for a given objective function $E_F:\mathbb{R}^n\to\mathbb{R}$ and feasible set $\Omega_F\subset\mathbb{R}^n$, which depend on $F$, a solution to the optimization problem specified by $$\epsilon=\min_{x\in\Omega_F}E_F[x]$$ is a vector $x\in\Omega_F$ such that $E_F[x]\leq E_F[y]$ for all $y\in\Omega_F$.

In "least squares" optimization, the function $E_F$ is a sum of squares. The two most common least squares problems are 1) $$E_F[x]=\|F[x]\|^2 \text{ , } \Omega_F=\mathbb{R}^n$$ where $F$ corresponds to an overdetermined system of equations, and 2) $$E_F[x]=\|x\|^2 \text{ , } \Omega_F=\{y\in\mathbb{R}^n\ \mid F[y]=0\}$$ where $F$ corresponds to an underdetermined system of equations.

Common linear algebra platforms, such as Matlab, may combine these three distinct mathematical problems "under the hood" in convenience function such as linsolve(). However low-level ("solver") libraries, such as LAPACK, will not.

Two final points of clarification:

  • A "solver" will typically correspond to a well-defined but abstracted mathematical problem. For example, "statistical inference" or "sucessful prediction" are not such problems. In the language of Computational Science, you verify a solver, you validate a model.

    • The ideas of unique/non-unique or exact/approximate are not fully clear cut. Say we focus just on the case of square systems of equations, which should remove most points of contention. It is ubiquitous to talk of "iterative solvers" in this field (e.g. ~600,000 hits on Google Scholar). So the de facto definition of "solver" must include this class of algorithms, which by definition are essentially inexact.
$\endgroup$
  • $\begingroup$ Yet for linear ordinary least squares $OLS(x)\neq OLS(y)$. The solution may be unique, but yields a least error estimate of $y$, which is often inappropriate and generally does not agree with a bivariate generating equation using Monte Carlo simulation whereas the more poorly correlated Deming regression would recover that generating line plus or minus the regression error. $\endgroup$ – Carl Oct 20 '16 at 13:47
  • $\begingroup$ I feel that it is a disservice to call linear OLS in $y$; an approximation only valid under restrictive conditions that are usually ignored to be a "solution" as it perpetuates a mythos that is misleading. $\endgroup$ – Carl Oct 20 '16 at 15:01
  • $\begingroup$ @Carl I updated to try and clarify. I do not understand your comments fully, but they seem to be referring to solving "applied science" problems, such as statistical inference or machine-learning prediction. In my experience (pretty broad in computational science), "solver" is used to refer to software for solving a purely mathematical problem. You can verify a solver, but this is not the same as validating a model. If your applied science problem does not satisfy the assumptions of the chosen mathematical problem, validation failure is not due to the solver. $\endgroup$ – GeoMatt22 Oct 20 '16 at 19:56
  • $\begingroup$ You are one smart cookie! Never doubt that. I will read through your answer and contribute if I can. In your comment above, Solvers can be validated easily, regression not so easily. You imply a paradox, "What is science that is not applied?" Science is the result of testing hypotheses, be that by proof or trial and error. Answer, all science is applied. $\endgroup$ – Carl Oct 20 '16 at 21:18
  • $\begingroup$ V&V terms are standard, e.g. Verification, validation, and predictive capability in computational engineering and physics "Briefly, verification is the assessment of the accuracy of the solution to a computational model. Validation is the assessment of the accuracy of a computational simulation by comparison with experimental data. In verification, the relationship of the simulation to the real world is not an issue. In validation, the relationship between computation and the real world, i.e., experimental data, is the issue." $\endgroup$ – GeoMatt22 Oct 20 '16 at 21:49
0
$\begingroup$

I think that the word solver comes from the similar functionality of solving some feasible solution, as there is in Solver add-on of Excel the option "value of", which tries to find $X$ such that $f(X) = Y$ and some more equality and inequality constraints. In mathematica the function solve does the same.

English (especially thanks to the media of US) has a tendency to evolve by mistakes being copied like 'cracker'~'hacker'. Solver could be similar. It is nicely abstract enough to hide the names of actual optimisation algorithms. Often the actual implementations are not that purely a single algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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