¿Qué es demasiado grande para los métodos estándar de álgebra lineal / optimización?

Los diferentes métodos de álgebra lineal numérica y de optimización numérica tienen diferentes regímenes de tamaño donde son una 'buena idea', además de sus propias propiedades. Por ejemplo, para problemas de optimización muy grandes, se utilizan los métodos de gradiente, gradiente estocástico y descenso de coordenadas en lugar de los métodos de Newton o Punto Interior porque no tiene que lidiar con el Hesse. Del mismo modo, los métodos densos de resolución lineal dejan de ser factibles después de cierto tamaño.

Entonces, dado que tanto los algoritmos como el hardware de la computadora cambian constantemente, ¿cuál es una buena manera de saber y mantenerse al día, qué tan grande es demasiado grande para el álgebra lineal estándar y los solucionadores de optimización?

(Estoy pensando en esto porque cuando eres un usuario final de algoritmos numéricos es importante tener una idea vaga de cuándo se pueden aplicar esos algoritmos. Parte de eso es la estructura del problema y el tipo de solución deseada, pero parte de ella también es solo el tamaño del problema).

EDITAR: para mayor concreción, lo que me hizo pensar en esto fue variar las reglas generales en los límites superiores de cuán grande podría resolver un problema de algoritmos de punto interior. Los documentos anteriores decían que la dimensionalidad debería ser de alrededor de 1000, mientras que los documentos posteriores se habían revisado a más de 5000 e incluso los documentos más recientes permiten un tamaño aún mayor dependiendo de si se puede aprovechar la escasez. Ese es un rango bastante amplio, así que tengo curiosidad por saber qué es grande para los métodos de punto interior de última generación.

Si se preserva la escasez, los preacondicionadores óptimos están disponibles y las restricciones de desigualdad se pueden resolver mediante un método multiescala (o el número de restricciones activas no es demasiado grande), el algoritmo general puede ser tiempo y espacio. La distribución a través de una máquina paralela agrega un término logarítmico al tiempo. Si hay suficiente escasez disponible, o si se usan métodos sin matriz, se puede resolver del orden de un millón de grados de libertad por núcleo. Eso pone el tamaño del problema para las máquinas más grandes de hoy en día alrededor de un billón de grados de libertad. Varios grupos han ejecutado simulaciones PDE a esta escala.$\mathcal O(n)$

Tenga en cuenta que todavía es posible utilizar la optimización basada en Newton con grandes espacios de diseño, solo necesita resolver de forma iterativa con el Hessian. Hay muchos enfoques para hacerlo de manera eficiente.

Por lo tanto, todo depende de cómo defina los "métodos estándar". Si su definición incluye métodos de preservación de estructuras multinivel, entonces los problemas extremadamente grandes son manejables. Si su definición se limita a métodos densos no estructurados, los tamaños de problema factibles son mucho más pequeños porque los algoritmos no son "escalables" ni en el tiempo ni en el espacio.

El límite está dado principalmente por la memoria que lleva almacenar la representación matricial y el tiempo para recuperarla de la memoria.

Esto hace que unos pocos miles sean el límite para el método de matriz densa en entornos simples. Para problemas dispersos, el límite para los solucionadores directos es mucho más alto, pero depende del patrón de dispersión, ya que debe rellenarse el relleno. El límite para los métodos iterativos para los solucionadores lineales es esencialmente el costo de una matriz vectorial multiplicada.

El límite para resolver los subproblemas lineales se traduce directamente en los límites correspondientes para solucionadores locales para sistemas no lineales de ecuaciones y problemas de optimización.

Los solucionadores globales tienen límites mucho más severos, ya que están limitados por el número de subproblemas que deben resolverse en un marco de ramificación y límite, o por la maldición de la dimensionalidad en los métodos de búsqueda estocástica.

Para una clase dada de problemas, las buenas maneras de descubrir qué constituye qué tan grande es "demasiado grande" son:

• busca la literatura en tu campo; Comprender qué factores limitarán el tiempo de ejecución (estos incluyen el uso de memoria y la comunicación)
• mire los conjuntos de problemas de prueba (mejor para los algoritmos en serie que los algoritmos en paralelo, ya que no conozco muchos conjuntos de problemas de prueba para algoritmos en paralelo)
• divida el algoritmo en partes constitutivas más pequeñas y use lo que sabe sobre las partes para hacer inferencias sobre el todo (ejemplo: los métodos del subespacio de Krylov se reducen a bucles de productos de vectores de matriz, por lo que debe calcular cuántas iteraciones es "demasiados" y lo que hace que un producto matriz-vector sea "demasiado grande")
• pruébelo usted mismo (en una máquina en serie, o si tiene los recursos, una máquina en paralelo). Vea qué tan grande de una instancia puede ejecutar, o ejecute varias instancias de diferentes tamaños, y haga un análisis de escala empírico (tiempo vs. tamaño del problema).

Para dar un ejemplo, en la optimización global, la respuesta concreta es extremadamente dependiente de la estructura. Como señala Arnold Neumaier, los algoritmos deterministas de optimización global tienden a estar limitados por la cantidad de subproblemas que deben resolverse en un marco de bifurcación (o bifurcación y corte). He resuelto programas lineales de enteros mixtos (MILP) que contienen miles de variables binarias, pero sospecho que la razón por la que puedo resolver problemas tan grandes (comparativamente hablando, para MILP) es porque la estructura del problema era tal que se necesitaban pocos subproblemas para resolver algún conjunto crítico de variables binarias, y el resto podría establecerse en cero. Sé que mi problema es "grande"; He construido otros MILP de tamaño similar que resuelven decenas de miles de veces más lentamente.

Hay conjuntos de pruebas de optimización global que le dan una idea de lo que es "normal", y la literatura puede darle ideas de qué problemas son "grandes". Existen tácticas similares para descubrir el estado del arte en tamaños de problemas en otros campos, así es como Jed Brown y Arnold Neumaier pueden citar estas cifras. Es genial obtener estos números, pero es mucho más valioso poder descubrir cómo obtenerlos usted mismo cuando llegue el momento.