Los problemas de optimización están en todas partes en ingeniería: equilibrar las compensaciones de diseño es un problema de optimización, como lo son la planificación y la planificación logística. La teoría, y a veces la implementación, de los sistemas de control depende en gran medida de la optimización, y también lo hace el aprendizaje automático, que tienesido la base de los avances más recientes en inteligencia artificial.
Esta semana, en el Simposio IEEE sobre Fundamentos de Ciencias de la Computación, un trío de estudiantes graduados actuales y pasados del MIT ganó el premio al mejor estudiante por un nuevo algoritmo de "plano de corte", un algoritmo de propósito general para resolver la optimizaciónproblemas. El algoritmo mejora el tiempo de ejecución de su predecesor más eficiente, y los investigadores ofrecen alguna razón para pensar que pueden haber alcanzado el límite teórico.
Pero también presentan un nuevo método para aplicar su algoritmo general a problemas específicos, lo que produce enormes ganancias de eficiencia, varios órdenes de magnitud.
"Lo que estamos tratando de hacer es revivir el interés de las personas en el problema general que resuelve el algoritmo", dice Yin-Tat Lee, un estudiante graduado en matemáticas del MIT y uno de los coautores del artículo. "Anteriormente, la gente necesitaba ideardiferentes algoritmos para cada problema, y luego necesitaban optimizarlos durante mucho tiempo. Ahora estamos diciendo que si para muchos problemas tienes un algoritmo, entonces, en la práctica, podemos intentar optimizar más de un algoritmo en lugar de muchos algoritmos, y podemos tener una mejor oportunidad de obtener algoritmos más rápidos para muchos problemas "
Lee se une en el papel a Aaron Sidford, que era un estudiante graduado del MIT en ingeniería eléctrica y ciencias de la computación cuando se realizó el trabajo, pero ahora está en Microsoft Research New England, y por Sam Wong, quien obtuvo una licenciatura y maestría enmatemática e ingeniería eléctrica e informática en el MIT antes de mudarse a la Universidad de California en Berkeley para obtener su doctorado.
círculo interior
Los problemas de optimización generalmente se enmarcan como tratar de encontrar el valor mínimo de una función matemática, llamada "función de costo". En el diseño de automóviles, por ejemplo, la función de costo puede imponer penalizaciones por peso y resistencia, pero recompensa el espacio para las piernas y la visibilidad; enun algoritmo para la detección de objetos, la función de costo recompensaría la clasificación correcta de varios objetos y penalizaría los falsos positivos.
En un nivel muy general, encontrar el mínimo de una función de costo puede describirse como tratar de encontrar un pequeño grupo de valores en medio de un conjunto mucho mayor de posibilidades. Suponga que el rango total de valores posibles para una función de costo está representado porel interior de un círculo. En un problema de optimización estándar, los valores agrupados alrededor del valor mínimo serían representados por un círculo mucho más pequeño dentro del primero. Pero no sabes dónde está.
Ahora elija un punto al azar dentro del círculo más grande. En los problemas de optimización estándar, generalmente es posible determinar si ese punto se encuentra dentro del círculo más pequeño. Si no lo hace, también es posible dibujar una línea que se encuentre entre él yel círculo más pequeño
Dibujar esa línea corta un trozo del círculo, eliminando un rango de posibilidades. Con cada nuevo punto aleatorio que elija, corta otra sección del círculo, hasta que converja en la solución.
Si representa el rango de posibilidades como una esfera en lugar de un círculo, entonces usa un plano, en lugar de una línea, para cortar algunos de ellos. De ahí el nombre de la técnica: el método del plano de corte.
En la mayoría de los problemas de optimización reales, necesita un objeto de mayor dimensión que un círculo o una esfera: necesita una hiperesfera, que corta con un hiperplano. Pero el principio sigue siendo el mismo.
cuestión de tiempo
Los informáticos teóricos miden el tiempo de ejecución de los algoritmos no en segundos u horas, sino en la cantidad de operaciones requeridas, en relación con la cantidad de elementos que se manipulan. Con los métodos de plano de corte, la cantidad de elementos es la cantidad de variables en elfunción de costo: el peso del automóvil, el costo de sus materiales, resistencia, espacio para las piernas, etc. Esa también es la dimensión de la hiperesfera.
Con el mejor método de plano de corte de propósito general, el tiempo requerido para seleccionar cada nuevo punto a probar fue proporcional al número de elementos elevados a la potencia 3.373. Sidford, Lee y Wong lo reducen a 3.
Pero también describen una nueva forma de adaptar los métodos de plano de corte a tipos particulares de problemas de optimización, con nombres como minimización submodular, flujo submodular, intersección matroide y programación semidefinida. Y en muchos de esos casos, informan mejoras dramáticas eneficiencia, desde tiempos de ejecución que escalan con la quinta o sexta potencia del número de variables n5 o n6, en lenguaje informático hasta la segunda o tercera potencia n2 o n3.
Fuente de la historia :
Materiales proporcionado por Instituto de Tecnología de Massachusetts . Nota: El contenido puede ser editado por estilo y longitud.
Cita esta página :