O que exatamente é um "solucionador" de otimização?

Estou realmente confuso com o uso do solver na otimização computacional. Eu olhei em volta por um mês dentro e fora, para ver se consigo entender bem o que esse termo significa, mas ainda não o entendo bem.

Parece que, se eu gostaria de resolver um problema de otimização no aprendizado de máquina ou em outro lugar, me referiria ao procedimento computacional exato como um algoritmo e não como um solucionador. Por exemplo, se eu tivesse um programa quadrático, usaria a função Quadprog do MATLAB para resolver o QP.

Pessoalmente, não me referiria à função Quadprog como um solucionador de QP, porque é apenas uma função MATLAB ou um script. Eu não me referiria ao algoritmo exato por trás do Quadprog como um solucionador de QP, não me importo se é descida de gradiente, método de ponto interior, Newton Raphson ... todos eles são algoritmos para mim. Finalmente, não me referiria ao MATLAB como um solucionador de QP, porque esse não é o único objetivo do MATLAB. Parece que a palavra "solucionador" está faltando no meu vocabulário cotidiano, apesar de ter que trabalhar rotineiramente com otimização, isso me confunde bastante, apenas parece que não estou atualizado com o jargão.

Então, pelo meu raciocínio, algoritmos e MATLAB não são solucionadores. Mas suponha que eu tenha baixado alguns softwares como Gurobi ou YALMIP para resolver problemas de otimização, esses softwares são chamados de solucionadores? Muitas vezes ouvi pessoas referenciando o "solucionador" que você está usando no mesmo tom que o "software" que você está usando. O que diferencia softwares e solucionadores de otimização?

Sei que isso soa como uma pergunta realmente rudimentar, mas só fiz otimização no MATLAB.

Sugiro que um solucionador é:

• um pacote de software
• que incorpora um ou mais algoritmos
• para encontrar soluções para uma ou mais classes de problemas

As classes de problema fazem parte disso. É um solucionador de X.

assim

• Eu chamaria Gurobi de "um solucionador de MIP / LP" .
• E eu diria "O Matlab incorpora um solucionador de QP, que é exposto pela função Quadprog". Nesse caso, o "QP solver" real pode ou não existir como um produto independente.
• Concorde é um solucionador de TSP
• Concorde incorpora QSopt, que é um solucionador de LP

Eu acho que esse uso está alinhado com (por exemplo) a documentação do JuMP

JuMP é uma linguagem de modelagem específica de domínio para otimização matemática incorporada na Julia. Atualmente, ele suporta vários solucionadores de código-fonte aberto e comerciais (veja abaixo) para uma variedade de classes de problemas, incluindo programação linear, programação com números inteiros mistos, programação cônica de segunda ordem, programação semidefinida e programação não-linear.

Aqui está uma lista de coisas que o JuMP chama de solucionadores . Nenhum deles é algoritmo, todos são programas específicos

Um solucionador é uma rotina para encontrar respostas numéricas exatas para determinados sistemas. Por exemplo, ao usar Newton-Raphson para encontrar raiz (s). Quando um sistema é superdeterminado , geralmente se usa soluções aproximadas, por exemplo, regressão. Geralmente, não se referiria à regressão como um solucionador, embora, previsivelmente, a linguagem possa ser mal utilizada e muitas rotinas aproximadas sejam vagamente denominadas solucionadoras . Por exemplo, o pacote de software de otimização CUTEr contém algoritmos, pelo menos alguns dos quais para sistemas sobredeterminados, e outros que são solucionadores, por isso é fácil dizer que estou baixando um "solucionador". Os métodos de resolução e de regressão são exemplos de métodos de otimização.

Normalmente, ouço o "solucionador" usado para descrever o software, o que significa que ele se aplica a uma implementação específica de um algoritmo. Por exemplo, isso parece se aplicar à maioria das perguntas do SciComp.SE com a tag solver .

Geralmente, o termo parece ser reservado para problemas matemáticos com uma "solução bem definida". Uma solução única se qualificaria como suficiente "bem definido", conforme observado pela Sycorax nos comentários. (Os solucionadores de Gurobi parecem ser os problemas desta classe; pelo que vale Gurobi parece-me uma suíte ou biblioteca de solucionadores).

Mas não acho que único seja necessário . Por exemplo, problemas de otimização local e global podem ter soluções bem definidas, mas não exclusivas (por exemplo, a função$f[x]=\sin[\pi x]^2$ tem um mínimo global $f[k]=0$ para $k\in\mathbb{Z}$)

Discordo dessa resposta , que parece estar discutindo "solucionadores de sistemas de equações" em vez de "solucionadores de otimização". Por exemplo, em mínimos quadrados lineares, o problema de álgebra linear é superdeterminado, mas o problema de otimização é convexo , com uma solução exclusiva (em casos não degenerados). Observe também que a página "solucionador" da Wikipedia vinculada nessa resposta lista "problemas de otimização linear e não linear, problemas de caminho mais curto, problemas mínimos de extensão de árvore" entre seus exemplos.

---

Em resposta ao comentário, vou esclarecer o que quero dizer no caso "regressão".

Dada uma função $F:\mathbb{R}^n\to\mathbb{R}^m$, uma solução para o sistema de equações especificado por

$$F[x]=0$$ é um vetor $x\in\mathbb{R}^n$ de modo que todos $m$ componentes de $F[x]$são zero. Dependendo da função$F$, não pode haver soluções, uma única solução única ou muitas soluções (geralmente muitas infinitas), dependendo da dimensão do espaço nulo de$F$. No caso em que$F$ é linear, ie $F[x]=Ax-b$ para alguns $A\in\mathbb{R}^{m\times{n}},b\in\mathbb{R}^m$, nenhuma solução poderá existir a menos que $m\leq\mathrm{rank}[A]\leq n$.

Por outro lado, para uma determinada função objetiva $E_F:\mathbb{R}^n\to\mathbb{R}$e conjunto viável $\Omega_F\subset\mathbb{R}^n$, que dependem de $F$, uma solução para o problema de otimização especificado por

$$\epsilon=\min_{x\in\Omega_F}E_F[x]$$ é um vetor $x\in\Omega_F$ de tal modo que $E_F[x]\leq E_F[y]$ para todos $y\in\Omega_F$.

Na otimização "mínimos quadrados", a função $E_F$é uma soma de quadrados. Os dois problemas mais comuns de mínimos quadrados são 1)

$$E_F[x]=\|F[x]\|^2 \text{ , } \Omega_F=\mathbb{R}^n$$ onde corresponde a um sistema de equações sobredeterminado e 2) onde corresponde a um sistema de equações sub-determinado .$F$ $$E_F[x]=\|x\|^2 \text{ , } \Omega_F=\{y\in\mathbb{R}^n\ \mid F[y]=0\}$$ $F$

Plataformas comuns de álgebra linear, como o Matlab, podem combinar esses três problemas matemáticos distintos "sob o capô" na função de conveniência, como linsolve () . No entanto, bibliotecas de baixo nível ("solucionador"), como LAPACK , não serão.

Dois pontos finais de esclarecimento:

• Um "solucionador" normalmente corresponde a um problema matemático bem definido, mas abstrato . Por exemplo, "inferência estatística" ou "previsão bem sucedida" não são esses problemas. Na linguagem da Ciência da Computação , você verifica um solucionador, valida um modelo.

  • As idéias de exclusivo / não exclusivo ou exato / aproximado não são totalmente claras. Digamos que nos concentramos apenas no caso de sistemas quadrados de equações, que devem remover a maioria dos pontos de contenção. É onipresente falar de "solucionadores iterativos" nesse campo (por exemplo, ~ 600.000 acessos no Google Scholar ). Portanto, a definição de fato de "solucionador" deve incluir essa classe de algoritmos, que por definição são essencialmente inexatos.

Eu acho que a palavra solucionador provém da funcionalidade semelhante de resolver uma solução viável, como no complemento Solver do Excel a opção "valor de", que tenta encontrar modo que e mais restrições de igualdade e desigualdade. No mathematica, a função resolver faz o mesmo.$X$$f(X) = Y$

O inglês (especialmente graças à mídia dos EUA) tem uma tendência a evoluir com erros sendo copiados como 'cracker' ~ 'hacker'. O Solver pode ser semelhante. É bastante abstrato o suficiente para ocultar os nomes dos algoritmos de otimização reais. Freqüentemente, as implementações reais não são puramente um único algoritmo.