Latest revision as of 08:33, 18 April 2017

Resumen

Este artículo presenta un algoritmo nuevo basado en una extensión del método algorítmico simplex de Nelder Mead para la identificación de al menos un óptimo local cuando se usa en problemas no lineales enteros mixtos irrestrictos. Este método algorítmico, denominado Algoritmo Simplex Entero Mixto (ASEM) por el autor, se basa en una doble estructura de símpleces que está compuesta por una estructura simplex real de dimensión n (simplex real) y otra estructura simplex entera de igual dimensión n (simplex entero). Las operaciones propuestas originalmente por Nelder Mead se ejecutan sobre el simplex real. Por otra parte, un grupo de nuevas operaciones presentadas en este artículo se emplean en el simplex entero. Este conjunto de nuevas operaciones junto con las operaciones originales del método de Nelder Mead garantizan que en cada iteración del ASEM se arroje un nuevo punto de prueba definido en el campo numérico de dimensión 2n   enteros mixtos ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ , con el objetivo de garantizar la identificación del óptimo local entero mixto, sin convertir las variables enteras en variables reales.

Abstract

This article presents a new algorithm based on the Nelder-Mead simplex algorithmic method for identifying a local optimum, at least on unconstrained nonlinear mixed-integer problems. The algorithmic method, Integer Mixed Simplex Algorithm (IMSA), so called by the author, is based on a double simplex structure, which is composed of a real n -dimensional simplex structure (real simplex) and an integer n -dimensional simplex structure (integer simplex). The original Nelder-Mead operations are applied on the real simplex. Meanwhile, a novel group of operations are applied on the integer simplex. This new set of operations, together with the original Nelder-Mead operations, guarantee a new trail point at each IMSA iteration in the search of the local optimum in the integer real mixed 2n   -dimensional numerical field ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ without the need of integer to real conversions.

Palabras clave

Método simplex ; Método de Nelder Mead ; optimización entera mixta ; búsqueda directa

Keywords

Simplex method ; Nelder-Mead method ; Mixed-integer optimization ; Direct search

1. Introducción

El desarrollo de métodos de optimización para su empleo en la búsqueda de soluciones a problemas enteros mixtos ocupa un lugar importante en diversos campos de la ingeniería, debido a las amplias posibilidades de aplicación en problemas de diseño óptimo, cuando en este tipo de problemas las variables enteras no pueden ser relajadas a variables reales, que suelen ser abordados con el propósito de emplear algún método algorítmico de optimización desarrollado para variables reales. Además, esta situación de inconvertibilidad de las variables enteras a variables reales se presenta con frecuencia cuando la función objetivo del problema de optimización es representada mediante la función de desempeño del sistema bajo estudio, la cual es medida mediante algún modelo de simulación que depende tanto de variables reales como de variables enteras. Bajo estas circunstancias es inconveniente transformar el problema de optimización entero mixto (OEM) a un problema de optimización de variables reales, debido al hecho de que existen variables de decisión que no pueden ser tratadas como variables reales. Como ejemplo de sistemas que son definidos por variables enteras mixtas se tienen: el número de cajeros en un supermercado y su respectiva tasa de atención; la capacidad de clientes que pueden aguardar a ser atendidos en cada cola correspondiente a su taquilla de una agencia bancaria y la tasa de servicio de cada cajero; el número de dientes de cada engranaje que conforman una caja reductora y la dimensión de cada engranaje; el número de etapas de un sistema amplificador de señales y la ganancia de cada etapa de amplificación entre otros.

Es en esta situación donde los métodos de búsqueda directa, llamados así por primera vez por Hooke y Jeeves [1] , pueden brindar una solución a este tipo de problemas de optimización, bien sea por no disponer de una expresión matemática de la función objetivo o por no contar con el gradiente de esta, principalmente cuando se requiere optimizar un proceso que depende tanto de variables reales como de variables enteras, lo que exige la aplicación de estrategias de exploración que permitan avanzar a un mejor punto de prueba en cada iteración, con el fin de identificar la solución óptima del problema.

En este artículo se presenta una extensión del método simplex de Nelder Mead (MSNM) [2] a problemas OEM cuando la función objetivo es no lineal y no está sujeta a restricciones. El Algoritmo Simplex Entero Mixto (ASEM), denominado así por el autor debido a que se basa en el patrón de búsqueda conocido como simplex, se fundamenta en las operaciones definidas por el MSNM y en un conjunto de nuevas operaciones propuestas por Brea [3] , que son ejecutadas únicamente sobre las variables enteras.

De acuerdo con Brandts et al. [4] , puede decirse que un simplex (d   -simplex) definido en el espacio euclidiano ${\textstyle {\mathbb {R} }^{d}}$ , siendo d un entero positivo, es un casco o envoltorio convexo de d  + 1 puntos, los cuales no todos pertenecen al mismo hiperplano definido en el espacio ${\textstyle {\mathbb {R} }^{d}}$ , y cuyos puntos son denominados vértices del simplex.

En consecuencia, un 1-simplex es un segmento de recta en el espacio ${\textstyle {\mathbb {R} }^{1}}$ ; un 2-simplex es un triángulo en el espacio ${\textstyle {\mathbb {R} }^{2}}$ ; un 3-simplex es un tetraedro en el espacio ${\textstyle {\mathbb {R} }^{3}}$ , y así sucesivamente.

Debido a que los problemas de optimización enteros mixtos son abordados en esta investigación mediante estructuras de simplex, se hace necesario definir 2 símpleces: uno para las variables reales, denominada aquí simplex real y otro que es empleado en el campo entero, denominado en este artículo simplex entero. Sobre estos símpleces es definido un conjunto de operaciones a fin de explorar en el espacio de búsqueda entero mixto y así poder identificar la solución óptima local del problema.

El ASEM ha mostrado ser lo suficientemente eficiente a problemas OEM irrestrictos [3] . No obstante, también ha sido probado con problemas no lineales enteros mixtos bajo restricciones a través de funciones de penalización, lo cual ha permitido comprobar que el ASEM es lo suficientemente eficaz en la identificación de óptimos locales en problemas de OEM bajo restricciones.

Mediante la ejecución de un número importante de ejemplos numéricos, Brea [5] ha comprobado el buen desempeño del MSNM cuando la función objetivo está sujeta a ruido, y además cuando el problema está sujeto a restricciones lineales. Sin embargo, existen condiciones particulares en donde el método algorítmico que él desarrolló [5] converge muy lentamente al óptimo.

Por otra parte, Barton e Ivey [6] y Humphrey y Wilson [7] han estudiado los parámetros que ofrecen el mejor desempeño del MSNM, cuando la función objetivo de un problema de optimización irrestricto está influenciada por ruido.

Estos hechos han motivado al autor a desarrollar un método algorítmico basado en el MSNM en el campo de los números enteros mixtos.

El resto de este artículo está estructurado como sigue: en la sección 2 se describe matemáticamente el tipo de problema de OEM que hay que resolver mediante el ASEM; en la sección 3 se enuncian un conjunto de definiciones preliminares que permitirán exponer claramente las proposiciones que definen las nuevas operaciones que se deben emplear sobre el simplex entero, además de facilitar la explicación del algoritmo; en la sección 4 se enuncian las proposiciones que definen las nuevas operaciones que son aplicadas sobre el simplex entero; en la sección 5 son establecidos los procedimientos empleados en el ASEM; en la sección 6 se ofrece una explicación del ASEM mediante una inédita representación basada en grafo; en la sección 7 se presenta un modo de flexibilizar el ASEM con el propósito de emplearlo en la optimización de problemas, en donde el número de componentes reales es diferente al número de componentes enteras de las variables de decisión; la sintonización o los ajustes de los parámetros del ASEM se muestran en la sección 8 ; en la sección 9 se muestra un conjunto de experimentos numéricos con el objeto de mostrar la eficacia del ASEM; una comparación del ASEM con otros algoritmos de optimización en el problema de diseño óptimo de un tanque presurizado se presenta en la sección 10 ; finalmente, se presentan conclusiones y propuestas de futuras investigaciones en la sección 11 .

2. El problema

Problema 1.

Sean ${\textstyle {\boldsymbol {\mbox{x}}}\in {\mathbb {R} }^{n}}$ el conjunto de n   variables reales independientes e ${\textstyle {\boldsymbol {\mbox{y}}}\in {\mathbb {Z} }^{m}}$ el conjunto de m variables enteras independientes. Entonces, el problema de minimización irrestricto entero mixto puede ser expresado por:

donde ${\textstyle f({\boldsymbol {\mbox{x}}},{\boldsymbol {\mbox{y}}}):{\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}\rightarrow \mathbb {R} }$ es una función objetivo no lineal.

3. Definiciones preliminares

En esta sección se establecerá un conjunto de definiciones que facilitarán la explicación del método algorítmico desarrollado.

Definición 1 Espacio euclidiano entero mixto.

Se entenderá por espacio euclidiano entero mixto de dimensión n  + m   el conjunto de puntos definidos por el producto cartesiano ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ , donde ${\textstyle \mathbb {R} }$ es el conjunto de los números reales y ${\textstyle \mathbb {Z} }$ es el conjunto de los números enteros.

Es importante señalar que, debido a la naturaleza del problema, el espacio de exploración donde deben ejecutarse las operaciones matemáticas es el espacio euclidiano entero mixto ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ , cuya dimensión corresponde a n  + m , indicando respectivamente así el número de variables reales y enteras que conforman el problema.

Definición 2 Vector precedente.

Sea una función ${\textstyle f({\boldsymbol {\mbox{w}}}):W\rightarrow \mathbb {R} }$ y sean a y b 2 vectores cualesquiera definidos en un dominio ${\textstyle W}$ . Se dice que a precede o es igualmente precedente a b , y se denota mediante a  ⪯ b , si f (a ) ≤ f (b ).

La definición 2 también se puede entender en el sentido estricto, esto es: un vector precede estrictamente a otro si la relación entre los valores de la función es estrictamente menor, es decir, a  ≺ b si f (a ) < f (b ).

Definición 3 Vector subsecuente.

Sea una función ${\textstyle f({\boldsymbol {\mbox{w}}}):W\rightarrow \mathbb {R} }$ y sean a y b 2 vectores cualesquiera definidos en un dominio ${\textstyle W}$ . Se dice que a es subsecuente o es igualmente subsecuente a b , y se denota como a  ⪰ b , si f (a ) ≥ f (b ).

También la definición 3 se puede entender en su sentido estrictamente subsecuente. En este caso se dice que el vector a es estrictamente subsecuente al vector b , y se denota como a  ≻ b , si f (a ) > f (b ).

Definición 4 Vector entero mixto.

Sean ${\textstyle {\boldsymbol {\mbox{x}}}\in {\mathbb {R} }^{n}}$ e ${\textstyle {\boldsymbol {\mbox{y}}}\in {\mathbb {Z} }^{m}}$ 2 subvectores que conforman un vector ${\textstyle {\boldsymbol {\mbox{v}}}={\left[{\boldsymbol {\mbox{x}}}^{t}\quad {\boldsymbol {\mbox{y}}}^{t}\right]}^{t}}$ . Se dice que el vector v es un vector entero mixto en el espacio euclidiano entero mixto de dimensión n  + m   , para indicar respectivamente la dimensión de las componentes reales y enteras, si el vector ${\textstyle {\boldsymbol {\mbox{v}}}\in {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ .

Definición 5 Subvector real.

Sea ${\textstyle {\boldsymbol {\mbox{v}}}\in {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ un vector entero mixto. Se dice entonces que ${\textstyle {\boldsymbol {\mbox{x}}}\in {\mathbb {R} }^{n}}$ es el subvector real de dimensión n , si sus componentes representan las cantidades reales del vector entero mixto v .

Definición 6 Subvector entero.

Sea ${\textstyle {\boldsymbol {\mbox{v}}}\in {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ un vector entero mixto. Se dice que ${\textstyle {\boldsymbol {\mbox{y}}}\in {\mathbb {Z} }^{m}}$ es el subvector entero de dimensión m , si sus componentes representan cantidades enteras del vector entero mixto v .

Debido a que el método algorítmico desarrollado para resolver problemas enteros mixtos requiere que las operaciones sobre cada subvector se ejecuten de forma independiente, es decir, que los nuevos puntos sean definidos por operaciones sobre los subvectores reales y sobre los subvectores enteros de forma separada, y que se permita así la coexistencia de ambos conjuntos de subvectores sin que ellos cambien sus condiciones en cuanto al espacio numérico que lo definen, se hacen necesarias las definiciones de operaciones sobre los subvectores pertenecientes a un mismo campo numérico.

Como consecuencia de las exigencias impuestas, se estudiará el caso particular donde n  = m   , quedando entonces las siguientes definiciones en el espacio euclidiano ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ . No obstante, se propondrá una adecuación a los problemas en el espacio euclidiano entero mixto ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ para cuando n  ≠ m , y de esta forma poder aplicar el algoritmo desarrollado a situaciones en donde el número de variables reales y enteras son distintos.

Definición 7 Centroide.

Sea un conjunto de k   puntos ${\textstyle {\boldsymbol {\mbox{p}}}_{i}={\left({\boldsymbol {\mbox{x}}}_{i}^{t}\quad {\boldsymbol {\mbox{y}}}_{i}^{t}\right)}^{t}}$ definidos en el espacio euclidiano entero mixto ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ para cada i  = 1, … k   . Se dice que el centroide ${\textstyle {\overline {\boldsymbol {\mbox{p}}}}}$ es el centro de masa de los k puntos, si a cada uno de los puntos se le ha considerado una masa m_i . En el caso de que la masa de cada uno de los puntos p_i sea igual, el centroide es determinado por

Observación 1.

Nótese que el punto ${\textstyle {\overline {\boldsymbol {\mbox{p}}}}}$ no necesariamente pertenece al espacio euclidiano ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ . Más aún, ${\textstyle {\overline {\boldsymbol {\mbox{p}}}}=}$${\displaystyle {\left({\overline {\boldsymbol {\mbox{x}}}}^{t},{\overline {\boldsymbol {\mbox{y}}}}^{t}\right)}^{t}}$ , donde

Definición 8 Simplex entero mixto.

Se dice que un q   -ésimo simplex entero mixto en el espacio euclidiano entero mixto ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ es un conjunto de diferentes puntos ${\textstyle {\boldsymbol {\mbox{v}}}_{i}={\left[{\boldsymbol {\mbox{x}}}_{i}^{t}\quad {\boldsymbol {\mbox{y}}}_{i}^{t}\right]}^{t}}$ para todo i  = 1, …, ν   , donde ${\textstyle {\boldsymbol {\mbox{x}}}_{i}\in {\mathbb {R} }^{n}}$ corresponde al i -ésimo subvector real de dimensión n   , ${\textstyle {\boldsymbol {\mbox{y}}}_{i}\in {\mathbb {Z} }^{n}}$ denota cada i -ésimo subvector entero de dimensión n , ν  = n  + 1 representa el número de vértices del simplex entero mixto, los cuales no todos pertenecen a la misma hipercara definida en el espacio euclidiano ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ , y cada uno es representado por un vector de dimensión n  + n . El q   -ésimo simplex entero mixto puede entonces ser representado en notación matricial como ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}=}$${\displaystyle [{\boldsymbol {\mbox{v}}}_{1}^{\left[q\right]}\quad ;{\boldsymbol {\mbox{v}}}_{2}^{\left[q\right]}\quad ;\cdots \quad ;{\boldsymbol {\mbox{v}}}_{\nu }^{\left[q\right]}]}$ .

De acuerdo con la definición 8 , se establece que

donde ${\textstyle {\boldsymbol {\mbox{X}}}_{\nu }^{\left[q\right]}\in {\mathbb {R} }^{n\times (n+1)}}$ e ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}\in {\mathbb {Z} }^{n\times (n+1)}}$ representan respectivamente el simplex real y el simplex entero.

Un concepto importante que debe conocerse es el referente al significado de simplex colapsado o degenerado, el cual se identifica cuando todos los vértices del simplex pertenecen a un mismo hiperplano.

Definición 9 Menor simplex entero.

Sea la matriz ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}=}$${\displaystyle [{\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}\quad ;{\boldsymbol {\mbox{y}}}_{2}^{\left[q\right]}\quad ;\cdots \quad ;{\boldsymbol {\mbox{y}}}_{\nu }^{\left[q\right]}]}$ un q   -ésimo simplex entero. Se dice que ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ es el más pequeño simplex entero no colapsado contenido en ${\textstyle {\mathbb {Z} }^{n\times (n+1)}}$ , si existe un vértice que equidista de sus otros vértices del simplex entero ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ en 1.

Definición 10 Aristas de ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ .

Una p -ésima matriz de aristas de un q   -ésimo simplex entero mixto ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ en el espacio euclidiano entero mixto ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ se define como una matriz de dimensión 2n  × n , cuya j   -ésima columna representa la arista del simplex entero mixto ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ entre un vértice referencial v_p y v_j para todo j  = 1, …, ν y j  ≠ p , es decir,

Nótese que de acuerdo con la definición 10 , una matriz ${\textstyle {\boldsymbol {\mbox{A}}}_{p}^{\left[q\right]}}$ representa el conjunto de aristas del q   -ésimo simplex entero mixto ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ que comparten un mismo p -ésimo vértice, es decir, son todas las aristas que se intersectan en el p -ésimo vértice del q   -ésimo simplex ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ .

Definición 11 Aristas de ${\textstyle {\boldsymbol {\mbox{X}}}_{\nu }^{\left[q\right]}}$ .

Una p -ésima submatriz de aristas de un q   -ésimo simplex real ${\textstyle {\boldsymbol {\mbox{X}}}_{\nu }^{\left[q\right]}}$ en el espacio euclidiano ${\textstyle {\mathbb {R} }^{n}}$ se define como una matriz de dimensión n  × n , cuya j   -ésima columna representa la arista del simplex real ${\textstyle {\boldsymbol {\mbox{X}}}_{\nu }^{\left[q\right]}}$ entre un vértice referencial x_p y x_j para todo j  = 1, …, ν y j  ≠ p , es decir,

De igual manera puede ser definida la matriz de aristas del simplex entero, la cual se puede enunciar como:

Definición 12 Aristas de ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ .

Una p -ésima submatriz de aristas de un q   -ésimo simplex entera ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ en el espacio euclidiano ${\textstyle {\mathbb {Z} }^{n}}$ , se define como una matriz de dimensión n  × n , cuya j   -ésima columna representa la arista del simplex entero ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ entre un vértice referencial y_p e y_j para todo j  = 1, …, ν y j  ≠ p , es decir,

Observación 2.

Nótese que un simplex real ${\textstyle {\boldsymbol {\mbox{X}}}_{\nu }^{\left[q\right]}}$ es colapsado si la matriz de arista ${\textstyle {\boldsymbol {\mbox{A}}}_{x_{p}}^{\left[q\right]}}$ es singular para todo j  = 1, …, ν   . De igual modo se puede afirmar que un simplex entero ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ es colapsado o degenerado si la matriz ${\textstyle {\boldsymbol {\mbox{A}}}_{y_{p}}^{\left[q\right]}}$ es singular para todo j  = 1, …, ν .

Definición 13 Simplex ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ jerarquizado.

Se dice que un q   -ésimo simplex entero mixto ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ es jerarquizado de acuerdo con f (v ) si v₁  ⪯ v₂  ⪯ ⋯ ⪯ v_ν , lo que significa que f (v₁ ) ≤ f (v₂ ) ≤ ⋯ ≤ f (v_ν ), en el espacio euclidiano entero mixto ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{n}}$ .

Observación 3.

Cuando el simplex no esté jerarquizado según algún criterio, esto se indica con el símbolo tilde, es decir, como ${\textstyle {\tilde {\boldsymbol {\mbox{Y}}}}_{\nu }^{\left[q\right]}}$ . Por otra parte, nótese que cuando un q   -ésimo simplex mixto está jerarquizado, tanto su correspondiente simplex real ${\textstyle {\boldsymbol {\mbox{X}}}_{\nu }^{\left[q\right]}}$ como su simplex entero ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ están jerarquizados de acuerdo con f (v ).

Definición 14 Función signo de un entero.

Sea un número entero ${\textstyle k\in \mathbb {Z} }$ . Entonces la función signo entero de k y que es denotada por sgnd (k ) adquiere el valor de 1, si k  > 0; 0, si k  = 0; o −1, si k  < 0.

4. Proposiciones de nuevas operaciones

Debido a que el ASEM requiere contar con un conjunto de operaciones que han de ser aplicadas sobre la submatriz de elementos enteros ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ , se requiere establecer un conjunto de proposiciones que formarán parte de los operadores que actuarán sobre el simplex entero mixto jerarquizado de acuerdo con f (v ), junto con las ya conocidas operaciones de Nelder Mead [2] , las cuales son aplicadas sobre el simplex ${\textstyle {\boldsymbol {\mbox{X}}}_{\nu }^{\left[q\right]}}$ .

Proposición 1 Punto reflejado entero.

Sea un q   -ésimo simplex entero jerarquizado ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ de acuerdo a f (v ), en el espacio euclidiano entero ${\textstyle {\mathbb {Z} }^{n}}$ . Si el punto reflejado entero v_r a través del centroide de su hipercara ${\textstyle H_{\nu }^{\left[q\right]}=\lbrace {\boldsymbol {\mbox{v}}}_{i}\in {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}\vert \quad i=}$${\displaystyle 1,\ldots ,\nu -1\rbrace }$ opuesta al ν -ésimo vértice v_ν es calculado por

donde para un ${\textstyle {\alpha }_{e}\in \mathbb {N} (\geq 2)}$ , el cual es el denominado coeficiente de reflexión entero, ${\textstyle \mu =\lceil \parallel {\overline {\boldsymbol {\mbox{y}}}}-}$${\displaystyle {\boldsymbol {\mbox{y}}}_{\nu }\parallel \rceil }$ es el valor entero próximo superior de la distancia entre y_ν e ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}}$ , dado que el operador ⌈· ⌉ aproxima el resultado a su próximo superior entero, e ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}}$ es determinado por ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}=}$${\displaystyle {\frac {1}{\nu -1}}{\sum }_{i=1}^{\nu -1}{\boldsymbol {\mbox{y}}}_{i}}$ . Entonces, se cumple que:

• y_r es vector definido en el espacio entero ${\textstyle {\mathbb {Z} }^{n}}$ ;
• y_r e y_ν están a sendos lados de la hipercara ${\textstyle H_{\nu }^{\left[q\right]}}$ .

Demostración Parte I) Denote (y_1,ν , …, y_{n ,ν} )^t el vértice y_ν , es decir, y_ν  = (y_1,ν , …, y_{n ,ν} )^t . Entonces, de acuerdo con la ecuación (8) , se tiene que

donde k_i  ∈ { −1, 0, 1} para todo i  = 1, …, n debido a la función signo discreta que es aplicada sobre cada elemento del vector. En consecuencia, cada una de las componentes de y_r es entera, en virtud de que y_{i ,ν} , α_e , μ y k_i son todos números enteros, y para cada i  = 1, …, n su operación arroja un número entero.

Parte II) Si tanto el vértice y_ν como el punto y_r están ubicados en sendos lados de la hipercara ${\textstyle H_{\nu }^{\left[q\right]}}$ , entonces el ángulo entre los vectores formados por ${\textstyle {\boldsymbol {\mbox{y}}}_{\nu }-}$${\displaystyle {\overline {\boldsymbol {\mbox{y}}}}}$ e ${\textstyle {\boldsymbol {\mbox{y}}}_{r}-{\overline {\boldsymbol {\mbox{y}}}}}$ debe ser obtuso.

Este hecho se demuestra cuando, al realizar el producto escalar ${\textstyle {\left({\boldsymbol {\mbox{y}}}_{\nu }-{\overline {\boldsymbol {\mbox{y}}}}\right)}^{t}({\boldsymbol {\mbox{y}}}_{r}-}$${\displaystyle {\overline {\boldsymbol {\mbox{y}}}})}$ , este es negativo. De esta manera se tiene que de la ecuación (8) se puede escribir

Entonces, al premultiplicar la ecuación (9) por ${\textstyle {\left({\boldsymbol {\mbox{y}}}_{\nu }-{\overline {\boldsymbol {\mbox{y}}}}\right)}^{t}}$ , se obtiene que

Simplificando la ecuación (10) , se tiene que

Si se denota a ${\textstyle {\left({\boldsymbol {\mbox{y}}}_{\nu }-{\overline {\boldsymbol {\mbox{y}}}}\right)}^{t}=}$${\displaystyle {\left(d_{1},d_{2},\ldots ,d_{n}\right)}^{t}}$ se tiene que

Sustituyendo la ecuación (12) en la ecuación (11) se puede afirmar que

Dado que ${\textstyle \mu =\lceil \parallel {\overline {\boldsymbol {\mbox{y}}}}-}$${\displaystyle {\boldsymbol {\mbox{y}}}_{\nu }\parallel \rceil \geq \vert d_{i}\vert }$ para todo i  = 1, …, n , y que α_e  ≥ 2 se puede asegurar que ${\textstyle d_{i}^{2}-{\alpha }_{e}\quad \mu \quad \vert d_{i}\vert <0}$ para todo i  = 1, …, n   , y en consecuencia ${\textstyle {\left({\boldsymbol {\mbox{y}}}_{\nu }-{\overline {\boldsymbol {\mbox{y}}}}\right)}^{t}({\boldsymbol {\mbox{y}}}_{r}-}$${\displaystyle {\overline {\boldsymbol {\mbox{y}}}})<0}$ . Solo cuando α_e  = 1 el producto escalar ${\textstyle {\left({\boldsymbol {\mbox{y}}}_{\nu }-{\overline {\boldsymbol {\mbox{y}}}}\right)}^{t}({\boldsymbol {\mbox{y}}}_{r}-}$${\displaystyle {\overline {\boldsymbol {\mbox{y}}}})}$ puede ser igual a cero, lo cual provocaría el colapso del simplex entero. □

Lema 1.

Sean: un vector y  = (y₁ , …, y_n )^t de componentes enteros definido en el espacio euclidiano ${\textstyle {\mathbb {Z} }^{n}}$ , ξ   un número entero positivo, y ${\textstyle {\tilde {\boldsymbol {\mbox{k}}}}_{n}=}$${\displaystyle {\left(k_{1},\ldots ,k_{n}\right)}^{t}}$ un vector cuyas componentes k_i  ∈ { −1, 0, 1}, para todo i  = 1, …, n   . Entonces, ${\textstyle {\boldsymbol {\mbox{y}}}+\xi {\tilde {\boldsymbol {\mbox{k}}}}_{n}}$ también pertenece al espacio euclidiano entero ${\textstyle {\mathbb {Z} }^{n}}$ , y su distancia a y es de ${\textstyle \xi {\sqrt {n-l}}}$ , donde l  ≤ n   es el número de componentes nulas en el vector ${\textstyle {\tilde {\boldsymbol {\mbox{k}}}}_{n}}$ .

Demostración.   En virtud de que ${\textstyle {\boldsymbol {\mbox{y}}}={\left(y_{1},\ldots ,y_{n}\right)}^{t}\in {\mathbb {Z} }^{n}}$ , entonces,

Debido al hecho de que cada i -ésima componente de y_k indicada en la ecuación (14) , es decir, y_i  + ξk_i para todo i  = 1, …, n   es un número entero, puede asegurarse que ${\textstyle {\boldsymbol {\mbox{y}}}_{k}\in {\mathbb {Z} }^{n}}$ . Por otra parte, la norma euclidiana del vector definido por la diferencia entre y_k e y es

en virtud de que para todo i  = 1, …, n los números escalares k_i  ∈ { −1, 0, 1}. La ecuación (15) determina la distancia de y a un punto vecino y_k . □

Proposición 2 Punto expandido entero.

Sea ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ un q -ésimo simplex entero jerarquizado de acuerdo con f (v ), definido exclusivamente en el espacio euclidiano entero ${\textstyle {\mathbb {Z} }^{n}}$ . Si el punto expandido entero y_e es definido por

donde ${\textstyle {\beta }_{e}\in \mathbb {N} (>0)}$ representa el coeficiente de expansión entero e y_r es determinado por la ecuación (8) . Entonces, se cumple que:

• y_e es un punto en el espacio de los números enteros ${\textstyle {\mathbb {Z} }^{n}}$ ;
• con respecto al vértice y_ν , y_e nunca está más cerca de y_ν , de lo que está y_r de y_ν .

Demostración. Parte I) Represente y_r  = (y_1,r , …, y_{n ,r} )^t un punto reflejado producto de la operación definida por la ecuación (8) . Entonces

donde k_i  ∈ { −1, 0, 1} para todo i  = 1, …, n debido a la función signo discreta. En consecuencia, cada una de las componentes de y_e es entera, debido al hecho de que y_{i ,r} , β_e y k_i son todos números enteros, para cada i  = 1, …, n su operación arroja un número entero.

Parte II) Claramente el vector ${\textstyle sgnd\quad ({\overline {\boldsymbol {\mbox{y}}}}-}$${\displaystyle {\boldsymbol {\mbox{y}}}_{\nu })}$ tiene la misma orientación del vector ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}-}$${\displaystyle {\boldsymbol {\mbox{y}}}_{\nu }}$ , y este último va desde el punto y_ν hasta el punto ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}}$ . Como resultado de esto, el vector ${\textstyle sgnd\quad ({\overline {\boldsymbol {\mbox{y}}}}-}$${\displaystyle {\boldsymbol {\mbox{y}}}_{\nu })}$ tiene como orientación un vector que va desde el punto ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}}$ hasta un punto que se encuentra en la región discreta entre ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}}$ e y_r , y la norma euclidiana de ${\textstyle {\beta }_{e}\quad sgnd\quad ({\overline {\boldsymbol {\mbox{y}}}}-}$${\displaystyle {\boldsymbol {\mbox{y}}}_{\nu })}$ , según el lema 1 , es ${\textstyle {\beta }_{e}\quad {\sqrt {n-l}}\not <0}$ , lo cual, al sumarse con y_r , se ubica en un punto que no está más cerca de lo que está y_r de y_ν .

Proposición 3 Punto contraído entero.

Sea un q   -ésimo simplex entero jerarquizado ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ de acuerdo a f (v ), definido únicamente en el espacio euclidiano entero ${\textstyle {\mathbb {Z} }^{n}}$ . Si el punto contraído entero y_c es determinado por

donde ${\textstyle {\gamma }_{e}\in \mathbb {N} (>0)}$ es el llamado coeficiente de contracción entero, y_r es determinado por (8) . Entonces, se tiene que:

• y_c es un punto en el espacio de los números enteros ${\textstyle {\mathbb {Z} }^{n}}$ ;
• con respecto al vértice y_ν está más cerca, de lo que está y_r de y_ν .

Demostración. Aplicando el mismo método empleado en la demostración de la proposición 2 , se demuestra la parte I) y parte II) de la proposición.

Proposición 4 Simplex entero encogido.

Sea un q   -ésimo simplex entero jerarquizado ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ de acuerdo a f (v ), definido solamente en el espacio euclidiano entero ${\textstyle {\mathbb {Z} }^{n}}$ . Si 0 < δ_e  < 1 es el coeficiente de encogimiento entero, y además,

donde ${\textstyle {\boldsymbol {\mbox{A}}}_{1}^{\left[q\right]}}$ es la matriz de arista de ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ , y el operador ⌈· ⌉ aproxima cada elemento de la matriz ${\textstyle {\boldsymbol {\mbox{A}}}_{1}^{\left[q\right]}}$ al próximo entero por encima. Entonces, se cumple que:

• la matriz formada por

es un simplex compuesto de elementos enteros.

• las aristas del simplex ${\textstyle {\tilde {\boldsymbol {\mbox{Y}}}}_{\nu }^{\left[q+1\right]}}$ con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ nunca son mayores a las aristas del simplex ${\textstyle {\boldsymbol {\mbox{Y}}}_{\nu }^{\left[q\right]}}$ con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ , en consecuencia el nuevo simplex es igual o menor en tamaño.

Demostración. Parte I) Del análisis de la operación definida por la ecuación (19) se puede afirmar que esta arroja como resultado una matriz de dimensión n  × n compuesta de elementos enteros, en virtud de que el operador ⌈· ⌉ aproxima cada uno de los elementos de la matrix al próximo entero por encima.

Parte II) Para demostrar esta afirmación, se tiene primero que, de acuerdo con la ecuación (20) , sendas primeras columnas de ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ y ${\textstyle {\tilde {\boldsymbol {\mbox{S}}}}_{\nu }^{\left[q+1\right]}}$ son iguales al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ . Ahora se deberán estudiar las normas de las aristas de sendos símpleces con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ .

Se tiene que la matriz de aristas del simplex ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ está definida por

donde ${\textstyle {\boldsymbol {\mbox{a}}}_{i}^{\left[q\right]}=}$${\displaystyle {\left(a_{1i},a_{2i},\ldots ,a_{ni}\right)}^{t}}$ para todo i  = 1, …, n .

Por otra parte, la matriz de arista del simplex ${\textstyle {\tilde {\boldsymbol {\mbox{S}}}}_{\nu }^{\left[q+1\right]}}$ con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q+1\right]}}$ , de acuerdo a la ecuación (20) viene dada por

Ahora, al comparar la norma euclidiana de cada arista de ambas matrices, es decir, las matrices dadas por las ecuaciones (21) y (22) , se tiene que para todo j  = 1, …, n

Debido al hecho de que 0 < δ_e  < 1, para cada i  = 1, …, n y j  = 1, …, n   , siempre se cumple que ${\textstyle \lceil {\delta }_{e}a_{ij}{\rceil }^{2}\leq a_{ij}^{2}}$ , lo cual permite asegurar que para todo i  = 1, …, n , la norma euclidiana de cada j   -ésima arista del simplex ${\textstyle {\tilde {\boldsymbol {\mbox{S}}}}_{\nu }^{\left[q+1\right]}}$ con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ nunca es mayor a la norma euclidiana para esa misma j   -ésima arista del simplex ${\textstyle {\boldsymbol {\mbox{S}}}_{\nu }^{\left[q\right]}}$ con respecto al vértice ${\textstyle {\boldsymbol {\mbox{y}}}_{1}^{\left[q\right]}}$ . □

Observación 4.

La construcción de un nuevo simplex entero encogido mediante la proposición 4 puede producir un simplex entero colapsado ${\textstyle {\tilde {\boldsymbol {\mbox{S}}}}_{\nu }^{\left[q+1\right]}}$ . Como ejemplo, nótese que la proposición 4 aplicada al simplex entero ${\textstyle {\boldsymbol {\mbox{S}}}_{3}^{\left[q\right]}=}$${\displaystyle [{\boldsymbol {\mbox{y}}}_{1}\quad ;{\boldsymbol {\mbox{y}}}_{2}\quad ;{\boldsymbol {\mbox{y}}}_{3}]=}$${\displaystyle \left[{\begin{array}{ccc}1&2&3\\3&1&1\\&&\end{array}}\right]}$ , con una valor de δ_e  = 1/2, arroja como resultado el simplex entero colapsado ${\textstyle {\tilde {\boldsymbol {\mbox{S}}}}_{3}^{\left[q+1\right]}=}$${\displaystyle \left[{\begin{array}{ccc}1&2&2\\3&2&2\\&&\end{array}}\right]}$ .

La figura 1 muestra las operaciones de reflexión, expansión, contracción y construcción de un simplex encogido que pueden ser ejecutadas sobre un q   -ésimo simplex entero jerarquizado ${\textstyle {\boldsymbol {\mbox{S}}}_{3}^{\left[q\right]}=}$${\displaystyle [{\boldsymbol {\mbox{y}}}_{1}\quad ;{\boldsymbol {\mbox{y}}}_{2}\quad ;{\boldsymbol {\mbox{y}}}_{3}]=}$${\displaystyle \left[{\begin{array}{ccc}1&3&1\\5&2&1\\&&\end{array}}\right]}$ , definido en el espacio ${\textstyle {\mathbb {Z} }^{2}}$ , cuando los coeficientes tomaron los valores α_e  = 2, y β_e  = γ_e  = 1, y δ_e  = 1/2.

Figura 1. Operaciones sobre un simplex entero jerarquizado.

Obsérvese que el punto ${\textstyle {\overline {\boldsymbol {\mbox{y}}}}=}$${\displaystyle {\left(2,{\frac {7}{2}}\right)}^{t}}$ claramente no pertenece a los números ${\textstyle {\mathbb {Z} }^{2}}$ , sin embargo, el resto de los puntos arrojados por las distintas operaciones sobre el simplex entero ${\textstyle {\boldsymbol {\mbox{S}}}_{3}^{\left[q\right]}}$ sí pertenecen al espacio de los números ${\textstyle {\mathbb {Z} }^{2}}$ .

Por último, nótese además que en la figura 1 se muestra el simplex entero encogido, el cual es denotado por ${\textstyle {\tilde {\boldsymbol {\mbox{S}}}}_{3}^{\left[q+1\right]}=}$${\displaystyle [{\boldsymbol {\mbox{y}}}_{1}\quad ;{\acute {\boldsymbol {\mbox{y}}}}_{2}\quad ;{\acute {\boldsymbol {\mbox{y}}}}_{3}]=}$${\displaystyle \left[{\begin{array}{ccc}1&2&1\\5&4&3\\&&\end{array}}\right]}$ , para lo cual se empleó la proposición 4 , la cual podría arrojar un simplex entero colapsado según la observación 4 . No obstante, el algoritmo propuesto cuenta con etapas, las cuales deben iniciar con un nuevo simplex entero mixto.

5. Procedimientos

El ASEM se basa, entre otros pasos, en 2 procedimientos principales, que se presentan en esta sección. Es importante señalar que el superíndice [q ] es en algunas oportunidades suprimido con el propósito de simplificar la notación, sin que pierda su significado.

El procedimiento mostrado en la figura 2 , llamado Procedimiento de Construcción de un Simplex Entero Mixto (CSEM), permite construir un simplex entero mixto basándose, entre otros parámetros, en los valores de Δ_r y Δ_e que son definidos inicialmente por el usuario del ASEM a los efectos de tener control de los parámetros del algoritmo. Nótese que en la figura se emplea la notación 0_2n , la cual representa un vector nulo de dimensión 2n , es decir, un vector de elementos todos nulos.

Figura 2. Construcción de un Simplex Entero Mixto.

Otro procedimiento empleado en el ASEM es el Mejoramiento de un Simplex Entero Mixto (MSEM), el cual tiene como propósito redefinir el simplex entero mixto inicial a través de la orientación de sus aristas. Este procedimiento se presenta en la figura 3 con el objetivo de buscar la mejor orientación del simplex construido por el procedimiento CSEM. Los experimentos numéricos realizados por Brea [3] probaron la eficacia del MSEM.

Figura 3. Mejoramiento de un Simplex Entero Mixto.

6. El algoritmo

Para iniciar la búsqueda de un mínimo local del problema 1 , el ASEM, mostrado en la figura 4 , arranca con sus parámetros definidos por el usuario, el número de la etapa s  = 1 y un punto de inicio ${\textstyle {\boldsymbol {\mbox{v}}}_{0}\in {\mathbb {R} }^{w}\times {\mathbb {Z} }^{w}}$ , donde ${\textstyle w=max(n,m)}$ . Con el punto de inicio v₀ y los parámetros, el algoritmo construye un simplex entero mixto mediante la ejecución del procedimiento CSEM. Si el ASEM es ejecutado bajo la modalidad de selección del mejor simplex entero mixto construido, el cual se indica con m  = 1, el algoritmo ejecuta el procedimiento MSEM e inicia el contador de iteraciones q en cero.

Figura 4. Diagrama del Algoritmo Simplex Entero Mixto.

Una vez construido un simplex entero mixto inicial, el ASEM evalúa la función objetivo para cada uno de los vértices del simplex actual de los que no se conoce su valor, mediante el paso (3) Evaluación . Seguidamente, se determina el orden de precedencia de sus vértices a través del paso (4) Ordenamiento , lo cual permite determinar el punto de prueba reflejado mediante la ejecución del paso (5) Reflexión . Al final de este último paso, el ASEM selecciona uno de los 4 posibles casos, en función de la precedencia del punto de prueba reflejado, denotado por v_r con relación a: v₁ , v_{ν −1} y v_ν . Si v_r  ≺ v₁ , es decir, si f (v_r ) < f (v₁ ), el ASEM ejecuta una operación de expansión, para luego decidir si el vértice v_ν será sustituido por el punto de prueba v_r o v_e . Por otra parte, si v₁  ⪯ v_r  ⪯ v_{ν −1} , el ASEM reemplaza el vértice v_ν por el punto de prueba v_r . No obstante, si v_{ν −1}  ≺ v_r  ≺ v_ν el algoritmo sustituye el vértice v_ν del simplex actual por el punto de prueba v_r para luego ejecutar el paso (7) Contracción . Finalmente, en el caso de que v_ν  ⪯ v_r , el ASEM ejecuta una contracción del simplex actual por medio del paso (7) Contracción .

Después de que el ASEM tome una de las opciones de acuerdo con la precedencia de v_r con relación a v₁ , v_{ν −1} y v_ν , el algoritmo determina la cualidad del nuevo simplex de acuerdo al diámetro del simplex X , el cual es denotado por ℓ_x . Este valor de ℓ_x es comparado con un criterio de parada ${\textstyle {\kappa }_{x}^{\left[s\right]}}$ de la s   -ésima etapa, el cual adquiere distintos valores según la etapa que se esté ejecutando. Si ${\textstyle {l}_{x}\geq {\kappa }_{x}^{\left[s\right]}}$ , el ASEM ejecuta una nueva iteración. En caso contrario, el algoritmo detiene las iteraciones dentro de la etapa actual para decidir si continúa la búsqueda o no, de acuerdo con el valor de ${\textstyle \Delta =\vert \vert {\overset {\mbox{ˆ}}{\boldsymbol {\mbox{v}}}}^{\left[s\right]}-}$${\displaystyle {\overset {\mbox{ˆ}}{\boldsymbol {\mbox{v}}}}^{\left[s-1\right]}\vert \vert }$ . Si Δ ≥ ɛ   , el ASEM asigna a ${\textstyle {\kappa }_{x}^{\left[s\right]}=}$${\displaystyle \varphi {\kappa }_{x}^{\left[s-1\right]}}$ ; ${\textstyle {\Delta }_{r}^{\left[s\right]}=}$${\displaystyle \rho {\Delta }_{r}^{\left[s-1\right]}}$ y con v₁ va al paso (2) Construcción de un Simplex Entero Mixto a fin de rearrancar una nueva etapa. En caso contrario, el ASEM reporta a ${\textstyle {\overset {\mbox{ˆ}}{\boldsymbol {\mbox{v}}}}^{\left[s\right]}=}$${\displaystyle {\overset {\mbox{ˆ}}{\boldsymbol {\mbox{v}}}}_{1}}$ como el mínimo.

7. Flexibilidad del Algoritmo Ximplex Entero Mixto

Una característica particular que tiene el ASEM es su flexibilidad con respecto a problemas en donde el número de componentes reales y enteras son diferentes, es decir, problemas del tipo ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ , donde ${\textstyle n\in {\mathbb {N} }_{+}}$ y ${\textstyle m\in {\mathbb {N} }_{+}}$ pueden ser diferentes.

Para tratar este tipo de problemas se debe convertir el problema de ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ a ${\textstyle {\mathbb {R} }^{max(n,m)}\times {\mathbb {Z} }^{max(n,m)}}$ , para así permitir definir un simplex entero mixto con igual número de componentes reales y enteras.

Es importante destacar que la función objetivo definida en el espacio ${\textstyle {\mathbb {R} }^{n}\times {\mathbb {Z} }^{m}}$ es tratada con su número original de variables. No obstante, el simplex es definido con max(n , m ) + 1 vértices enteros mixtos todos definidos en espacio euclidiano entero mixto ${\textstyle {\mathbb {R} }^{max(n,m)}\times {\mathbb {Z} }^{max(n,m)}}$ .

Esta generalización de los problemas enteros mixtos se muestra a través de las funciones de pruebas presentadas en el apéndice A .

8. Sintonización del Algoritmo Ximplex Entero Mixto

Para el proceso de sintonización del ASEM se consideraron los parámetros obtenidos en la sintonización del Algoritmo Simplex Entero Relajado (ASER) desarrollado por Brea [3] , además de los valores recomendados y apoyados en las investigaciones de Brea sobre el MSNM cuando el problema de optimización no lineal está bajo restricciones lineales [5] (tabla 1 ).

En consecuencia, los parámetros α_r , β_r , γ_r y δ_r indicados en la tabla 1 fueron ajustados de acuerdo a los valores recomendados en Nelder y Mead [2] , mientras los parámetros Δ_e , α_e , β_e , γ_e y δ_e se fijaron de acuerdo con los valores obtenidos en el proceso de sintonización del ASER (véase Brea [3, cap. 5] ). Además, los valores de los parámetros φ   y ${\textstyle k_{x}^{\left[1\right]}}$ mostrados en la tabla 1 se obtuvieron mediante pruebas preliminares, las cuales permitieron mostrar un desempeño satisfactorio del ASEM. Finalmente, el parámetro ɛ representa el criterio de comparación de los resultados obtenidos en 2 etapas sucesivas y, en consecuencia, debe ser fijado por el usuario dependiendo del máximo error que espera obtener en la comparación de 2 etapas sucesivas.

Estas consideraciones permitieron simplificar significativamente la experimentación para la obtención de los valores apropiados de ρ   y ${\textstyle {\Delta }_{r}^{\left[1\right]}}$ . Es importante señalar que durante la realización de los experimentos, el número máximo de iteraciones que se le permitió ejecutar al ASEM por etapa fue de 15.000, debido a que el ASEM podía quedar en un proceso iterativo, sin encontrar un avance significativo en la minimización de la función objetivo.

La tabla 2 muestra el número de evaluaciones (NE) ejecutadas sobre la función objetivo FC${\textstyle \mathbb {R} \mathbb {Z} }$ [d  + d ] con a_i  = b_i  = 1 para todo i  = 1, …, d , de acuerdo con los valores de ρ   y ${\textstyle {\Delta }_{r}^{\left[1\right]}}$ indicados en la tabla.

Además, en la tabla 2 se muestra entre paréntesis el mejor valor de la función objetivo para el NE indicado, siendo en todos los casos el punto óptimo en ${\textstyle {\overset {\mbox{ˆ}}{\boldsymbol {\mbox{x}}}}=}$${\displaystyle {\boldsymbol {0}}_{d}}$ e ${\textstyle {\overset {\mbox{ˆ}}{\boldsymbol {\mbox{y}}}}=}$${\displaystyle {\boldsymbol {0}}_{d}}$ , con un valor de la función objetivo de ${\textstyle f({\overset {\mbox{ˆ}}{\boldsymbol {\mbox{v}}}})=}$${\displaystyle 0}$ .

Como ejemplo de lectura de la tabla 2 se tiene que para d  = 8, ρ  = 0, 8 y ${\textstyle {\Delta }_{r}^{\left[1\right]}=}$${\displaystyle 1}$ el NE fue igual a 7.651 y el valor mínimo obtenido de la función objetivo fue entre 0 y un valor menor a 10⁻⁶ , en particular fue igual a 7.67546044785799 × 10⁻⁸ .

De la tabla 2 se puede apreciar que unos valores adecuados para ρ   y ${\textstyle {\Delta }_{r}^{\left[1\right]}}$ son 0,8 y 1 respectivamente, debido al hecho de que para esos valores el ASEM identificó el punto mínimo de la función objetivo para todos los casos de dimensión entera mixta considerados.

Es importante destacar que estos valores de sintonización del ASEM son referenciales y que no deben tomarse como valores que deben satisfacer la totalidad de los casos de estudio, puesto que fueron obtenidos de casos particulares.

9. Experimentos numéricos

La tabla 3 muestra los valores mínimos obtenidos por el ASEM, el mínimo teórico y el orden ${\textstyle O}$ de magnitud del error e , definido como

donde ${\textstyle {\tilde {f}}({\overset {\mbox{ˆ}}{\boldsymbol {\mbox{v}}}})}$ representa el valor mínimo determinado por el ASEM ${\textstyle f({\overset {\mbox{ˆ}}{\boldsymbol {\mbox{v}}}})}$ representa el valor mínimo teórico para cada una de las funciones de prueba definidas en el Apéndice A .