Cómo generar la base de Groebner
1 Introducción
La teoría y los métodos del diseño de optimización de ingeniería se han desarrollado y mejorado enormemente en los últimos años. Con el rápido desarrollo de la tecnología informática, la tecnología de optimización basada en inteligencia se ha convertido en un aspecto importante de la automatización del diseño. La tecnología de optimización basada en la teoría de la programación no lineal es la base principal del diseño de optimización de ingeniería. Cómo encontrar todas las soluciones óptimas y las soluciones óptimas globales a los problemas siempre ha sido un tema que las personas involucradas en la investigación de tecnologías de optimización se esfuerzan por explorar. El análisis de monotonicidad de los modelos de optimización es una forma de resolver este problema. La idea básica de la tecnología de optimización basada en el análisis de monotonicidad en la literatura [1 ~ 6] es descubrir las restricciones de holgura, rigidez y control del problema mediante el análisis de monotonicidad de la función objetivo y la función de restricción, y descomponer el problema original. en subproblemas más simples y fáciles de resolver, y mejora enormemente la posibilidad de obtener la solución óptima global al problema. La característica del subproblema es que todas las restricciones son estrictas (restricciones de igualdad), por lo que el problema puede reducirse a la solución de un conjunto de ecuaciones algebraicas no lineales (o problemas de restricciones de igualdad).
Powell, Yuan y Vardi, etc. han propuesto algunos métodos para el subproblema de restricción de igualdad anterior [7, 8], pero los métodos propuestos generalmente no pueden obtener todas las soluciones al problema, por lo que es fácil tener problemas útiles. Los subproblemas se tratan como subproblemas redundantes que hacen que se pierda la solución óptima del problema original. Además, el uso tradicional de métodos de iteración numérica para resolver este sistema algebraico no lineal también tiene el problema de la selección del valor inicial y generalmente sólo se puede obtener una solución numérica a la vez. Todos los métodos anteriores solo son aplicables a modelos de optimización numérica y no pueden resolver modelos de optimización simbólicos (es decir, los coeficientes conocidos en el modelo son símbolos en lugar de valores específicos). Obviamente, es de gran valor práctico poder encontrar la solución óptima del modelo simbólico. La expresión simbólica de la solución óptima es una solución universal al problema de diseño de optimización bajo varios valores de parámetros. cada parámetro en la solución. La influencia guía así el diseño real y también simplifica el diseño específico. La solución de modelos simbólicos sólo se puede lograr mediante métodos algebraicos iterativos no numéricos.
El método de bases de Groebner es un método algebraico iterativo no numérico para resolver sistemas algebraicos no lineales. La idea básica es reducir el sistema original dentro del anillo polinómico compuesto por el sistema de álgebra polinómica no lineal original ordenando adecuadamente las variables y los términos polinomiales, y finalmente generar una base estándar que sea equivalente al sistema original y sea fácil de resolver directamente. (Base Groebner). El método tradicional de eliminación consecuencial también puede ser un método algebraico para resolver sistemas algebraicos no lineales simbólicos, pero requiere técnicas de eliminación que dependen en gran medida del problema específico y producirán raíces crecientes.
La literatura [9] y [10] propusieron un método para resolver la solución óptima del problema de optimización del modelo simbólico basado en el análisis de monotonicidad y el método de la base de Groebner. Sin embargo, cuando utilizaron el método de la base de Groebner para resolver subproblemas. , Se adopta el método tradicional de sustitución y eliminación de variables, que no resuelve el importante problema de clasificación del método básico de Groebner, lo que afecta la efectividad del método. Al utilizar el análisis de monotonicidad y el método de base de Groebner para resolver el problema de optimización simbólica, este artículo propone dos términos y reglas de ordenación de variables basadas en las características del sistema de ecuaciones equivalentes del subproblema, para generar la forma simbólica de manera más rápida y efectiva. La base de Groebner de la "triangulación" es la expresión simbólica de la solución al problema de optimización. Los ejemplos de cálculo proporcionados en este artículo ilustran la superioridad y eficacia del método propuesto para encontrar la solución óptima simbólica a los problemas de optimización.
2 Introducción al método de la base de Groebner [11]
El conocimiento sobre el método de la base de Groebner (en adelante abreviado como GB) se puede encontrar en la literatura relevante (como la literatura [11]), Este artículo utiliza un ejemplo simple para ilustrar cómo usar este método para generar el GB de un sistema de álgebra polinomial.
Supongamos que existe un sistema polinomial F＝{f1, f2}, donde:
f1＝ax2＋bxy
f2＝cx2＋dy2 (1)
En la fórmula: x, y——variables;
a, b, c, d——coeficientes en forma simbólica.
Para f1, los términos de f2 se ordenan según el método del diccionario, y el orden de las variables es y f1′=cf1-af2=cbxy-ady2 ( 2) Ahora encuentra el S-polinomio f3 de f1′ y f2: f3=S(f1′, f2)=xf1′-byf2=-adxy2-bdy3 (3 ) Dado que LPP(f2) se puede dividir por LPP(f1′), es decir, LPP(f2)/LPP(f1′)=xy2/xy=y, f3 se puede reducir a f3. ′ relativo a f1′: f3′=cbf3+adyf1′=(-cb2d-a2d2)y3 (4) Luego encuentre el polinomio S f4 de f1′ y f3 ′: f4=S(f1 ′, f3′) = y2 (-cb2d-a2d2) f1′-cbxf3′ = ad (cb2d+a2d2) y4 (5) f4 se puede reducir en relación con f3′ es f4′: f4′=f4+adyf3′=0 (6) De la misma manera, los S-polinomios de f2 y f3′ también se pueden reducir a cero con respecto a f3′. Finalmente, la base de Groebner equivalente (GB) de F se obtiene como G = {g1, g2, g3} = {f3′, f1′, f2}, y G se "triangula", es decir: g1＝f3′＝g1（y） g2＝f1′＝g2（x,y） (7) g3＝f2＝g3（x,y） El sistema de ecuaciones correspondiente a la ecuación (7) es la expresión simbólica de la solución del sistema de ecuaciones correspondiente a F. Si necesita una solución específica, puede encontrar y hasta g1=0 en la ecuación (7) y luego sustituir y en g2=0 y g3=0, entonces la raíz del MCD (máximo común divisor) de g2 y g3 es x solución. Obviamente, la reducción en el ejemplo anterior es muy simple. Solo queremos ilustrar el proceso de reducción de generación de GB. Para sistemas complejos, la reducción y generación de GB se completan automáticamente en la computadora a través de un algoritmo dedicado (como el algoritmo de Buchberger). programa de. 3 Optimización simbólica basada en análisis de monotonicidad y método de bases de Groebner 3.1 Descripción general del método para determinar la solución simbólica óptima Propuesto en la literatura [9, 10] Se propone un método para determinar la solución de optimización simbólica de un diseño óptimo. La idea básica de este método es la siguiente: (1) Convertir el problema original del diseño de optimización en varios subproblemas mediante análisis de monotonicidad y procesamiento simbólico [2, 11]; (2 ) Todas las restricciones de los subproblemas son restricciones estrictas (restricciones iguales), y el conjunto de restricciones estrictas (iguales) de cada subproblema forma un sistema equivalente; (3) Para cada ecuación que consta de El sistema algebraico compuesto por el conjunto de restricciones de la fórmula, determine su GB, y este GB es la expresión simbólica de la solución óptima del subproblema correspondiente; (4) Utilice cualquier El algoritmo numérico tradicional para resolver el problema correspondiente a cada GB con ecuaciones algebraicas "trianguladas" puede obtener todas las soluciones numéricas óptimas para cada subproblema; (5) Debido a la equivalencia de los subproblemas y el original problema, también podemos obtener La expresión simbólica de la solución óptima y se obtienen todas las soluciones numéricas óptimas del problema original. Si no se puede generar GB, se utiliza el método de continuidad de homotopía para obtener la solución numérica. En su estudio, el proceso de reducción de generación de GB utilizó el método tradicional de sustitución y eliminación. 3.2 Modelo matemático de subproblemas Considere el siguiente problema de diseño de optimización (PL): min. f(X) s． t． hj(X)＝0 (j＝1,2,…,q) (8) gi(X)≤0 (i＝1,2,…,r) En la fórmula: (X) - son restricciones de igualdad y desigualdad respectivamente, y las restricciones de límite (límites superior e inferior de las variables) se incluyen en las restricciones de desigualdad. Mediante el análisis de monotonicidad y el procesamiento simbólico, el problema de diseño de optimización (PL) se puede convertir en varios subproblemas (SPL), y su modelo matemático es el siguiente: min. f(X) s． t． hj (X) = 0 (j = 1, 2,..., q) (9) gi (X) = 0 i∈K Donde: K—— original Un conjunto numerado de problemas (PL) correspondientes a restricciones estrictas. Método 3.3 GB para determinar soluciones simbólicas a subproblemas Obviamente, si el GB generado correspondiente al sistema de ecuaciones polinómicas restringidas equivalente del subproblema está "triangulado", entonces este GB expresado por una secuencia de ecuaciones de una sola variable puede considerarse como la expresión simbólica de la solución óptima del subproblema, y también puede considerarse como la expresión simbólica de la solución óptima del problema original (PL). Debido a que un orden diferente de variables y términos conducirá a diferentes reducciones polinómicas del sistema algebraico, el orden de variables y términos es un factor clave que afecta la eficiencia y los resultados de generar GB. Sólo el orden apropiado puede generar GB. . Hasta ahora, el método de clasificación por selección más utilizado es el de prueba y error, lo que limita la eficiencia de generar GB. Al analizar las características del sistema de ecuaciones equivalentes de subproblemas, este artículo propone dos criterios para seleccionar y clasificar. De acuerdo con estos dos criterios, se pueden generar GB "triangulados" de manera rápida y efectiva. Las principales características del sistema de ecuaciones equivalentes del subproblema son: (1) Los polinomios del sistema son polinomios con signo (signomio) y las potencias de algunas de sus variables son enteros negativos; (2) Algunos polinomios de restricciones de límite son polinomios lineales de una sola variable, que se parecen a xi-ximin o xi-ximax; (3) El número de términos en cada ecuación suele ser muy pequeño. Característica 1: Indica que el modelo matemático del sistema debe transformarse para poder aplicar algoritmos existentes como el algoritmo de Buchberger para generar GB. Los polinomios con signo deben convertirse en polinomios equivalentes. Se proponen los siguientes dos criterios de selección y clasificación en función de la Característica 2 y la Característica 3: Criterio 1: Clasificación por diccionario de un elemento determinado. Si el número de variables n ≥ 4, solo se toman n clasificaciones de variables, y en estas n clasificaciones, cada una de las n variables se coloca al final de la clasificación. Cuando el número de variables n es grande, ¡el número de clasificaciones posibles es n! es muy grande y la variable clasificada en último lugar será la variable en el primer polinomio que contenga solo una variable en el GB "triangulado" generado. En este momento, la elección del orden de las variables restantes no afectará la estructura de base generada. . Por lo tanto, el Criterio 1 puede ahorrar (n!-n) clasificaciones sin importancia. Pauta 2: Ordenación del diccionario de un elemento determinado. Supongamos que el número de variables es n, y el número de variables con restricciones de límite superior e inferior es ns, ¡entonces solo tome (n-ns)! clasificación de variables. De hecho, no importa cómo se clasifiquen las variables con restricciones de límite, estas variables son siempre el producto de potencia principal (LPP) de los polinomios correspondientes y, por lo tanto, se pueden usar para reducir otros polinomios. La clasificación no afecta la forma estructural del GB generado. La directriz 2 puede mejorar en gran medida la eficiencia computacional de generar GB cuando n es pequeño y ns es grande. A continuación proponemos un algoritmo para generar GB de subproblemas de diseño óptimo: (1) Para un subproblema, convertir su modelo matemático a una forma compatible con el algoritmo de Buchberger; (2) Clasificación del diccionario de elementos seleccionados; (3) Determinar la clasificación de variables. Si n-ns<4, seleccione ordenar según el criterio 2; de lo contrario, seleccione ordenar según el criterio 1; (4) Utilice el algoritmo de Buchberger para generar GB. Si se han generado GB ("triangulados"), pase a (7); de lo contrario, vaya al siguiente paso; (5) Clasifique los elementos según el método de potencia total y luego use el algoritmo de Buchberger para generar GB; (6) Convertir los GB generados en GB "triangulados"; (7) Generar los resultados y detener. 4 Ejemplo de cálculo El siguiente es un modelo matemático de diseño de optimización simbólica de un reductor de transmisión sin fin cilíndrico ordinario [10]: mín. f(X)=0.25πψx32x3(ux1-3x-11-2)2x-21 s． t． g4: Z2min≤ux1≤Z2max: g5 g6: Mmin≤x2≤Mmax: g7 g8: qmin≤x3≤qmax: g9 p> En la fórmula: x1, x2 y x3——son el número de cabezas, módulo y coeficiente característico del gusano respectivamente; x4——variable intermedia auxiliar configurada para simplificar la proceso de solución; p> T2——Par del eje de salida; u——Relación de transmisión; [σF] y [σH]— —esfuerzo permisible; YF2 - coeficiente de ancho de diente; η - eficiencia de transmisión; K, ψ y q2 - constantes. A través del análisis de monotonicidad y el procesamiento de símbolos por computadora, se obtienen los siguientes diez subproblemas [9, 10]: SPL1: g1, g2, g3, h3 SPL6: g1, g2 , g8 SPL2: g3, g2, g4, h3 SPL7: g2, g4, g8 SPL3: g2, g3, g6, h3 SPL8: g2, g6, g8 SPL4: g1, g2, g7 SPL9: g3, g5, g6, h3 SPL5: g2, g4, g7 SPL10: g5, g6, g8 Para simplificar Por conveniencia, supongamos, Q1=q21,2, F=, A=4q2, B=6q22, C=4q32, D=q42, G=Z2min, H=Mmin, I=Mmax, J=qmin, K=Z2máx, x1=a, x2=b, x3=c, x4=d. El polinomio simbólico del subproblema se puede convertir en el siguiente polinomio: g1＝a3b3c－q0 g4＝ua－G g2＝a2b6＋b6c2－a2Q1 g5＝ua－K g3＝b5c4－Ab5c3＋Bb5c2－Cb5c＋Db5－d g6＝b－H h3＝d2c2－Ea2－Fc2 g7＝b－I g8＝c －J A continuación resolvemos los subproblemas uno por uno. El sistema de ecuaciones equivalente del subproblema 1 (SPL1) no contiene polinomios de una sola variable, por lo que es el más difícil de resolver. Cuando las selecciones se ordenan lexicográficamente, ¡las 4! ＝24 tipos de clasificación de variables no lograron generar GB. Al ordenar por la potencia total de los elementos seleccionados, se puede obtener un GB "no triangulado" ordenando cualquier variable. Por ejemplo, si b . b6a6+coef11. a6＋coef12＝0 (a) b2a4c3+coef21. a4c2+coef22． b2a4c+coef23． b2c+coef24． d+coef25. a4 +coef26． b2a4+coef27． a2+coef28． b5＋coef29＝0 (b) b3c＋coef31． b6a4+coef3． a4＝0 (c) a6c＋coef41． c+coef42． a4＝0 (d) d2＋coef51． a6+coef52=0 (e) (10) Aquí coefij (i=1, 2,…,5; j=1,2,…,9) son todos dado por Los coeficientes simbólicos expresados por los parámetros son conocidos. Debido a limitaciones de espacio, aquí solo enumeramos la expresión de coef11: coef11=(-((-(-Q1)/(-q0)) )) /(-(-1/(q0))) La estructura del polinomio en la ecuación (10) muestra que es fácil convertirlo en una forma "triangulada" mediante sustitución y eliminación. De las fórmulas (a), (b) y (e), obtenemos: (f) c=-coef42. a4(a6+coef41)-1 (g) (h) Sustituyendo las ecuaciones (f), (g) y (h) en las ecuaciones (b) y (c ), se obtienen dos polinomios que contienen sólo la variable a, que junto con las ecuaciones (f), (g) y (h) forman un nuevo GB "triangulado" de SPL1. Este GB es la expresión simbólica de la solución óptima de SPL1. . También nos gustaría señalar que los métodos propuestos en [9, 10] no pueden generar GB para este subproblema. Para el subproblema SPL2, existe un polinomio lineal de una sola variable, a saber: q4=ua-G. En este momento, se puede utilizar el criterio 2, que es la clasificación de opciones del diccionario y (4-1). =Se pueden ordenar seis tipos de variable a en cualquier orden. Para las siguientes cuatro clasificaciones de variables, todos obtenemos el mismo GB "triangulado": a c El GB generado es: a＋coef11＝0 c2＋coef21. c+coef22＝0 b2+coef31． c+coef32＝0 (11) d+coef41． cb＋coef42． b＝0 En la fórmula: coefij (i＝1, 2,..., 4; j＝1, 2) tiene el mismo significado que en SPL1 pero tiene diferentes expresiones, por ejemplo, coef11 ＝-G/u. Para SPL3 a SPL9, hay uno o dos polinomios lineales univariados, y podemos generar el GB correspondiente usando el mismo método que en SPL2. Debido a limitaciones de espacio, los resultados de la solución se omiten aquí. Para SPL10, hay tres ecuaciones lineales de una sola variable, y obtenemos directamente los resultados: a＝-K/u, b＝H, c＝J Los GB "triangulados" de los subproblemas generados SPL1~9 se completaron utilizando el algoritmo Buchberger en una estación de trabajo Sun, utilizando el lenguaje Fortran, y el tiempo de CPU fue de 0,08 segundos respectivamente. a 0,28 segundos. entre.