wiki:OfficialTolArchiveNetworkNonLinGloOpt

Context Navigation

close Warning: Can't synchronize with repository "(default)" (/var/svn/tolp does not appear to be a Subversion repository.). Look in the Trac log for more information.

Version 6 (modified by Víctor de Buen Remiro, 14 years ago) (diff)
--

Package NonLinGloOpt

Package NonLinGloOpt

Este paquete TOL una API para usuario final al sistema de optimización global no lineal NLopt de Steven G. Johnson.

Definición del problema

El tipo de problemas que resuelve este sistema se puede formular matemáticamente del siguiente modo generalizado:

Se quiere maximizar una función objetivo arbitraria:

$\underset{x\in\Omega}{\min}f\left(x\right)\wedge f:\Omega_f\subset\mathbb{R}^{n}\longrightarrow\mathbb{R} \wedge n\geq1$

Sujeta a las

restricciones opcionales de intervalo:

$-\infty\leq l_{i}\leq x\leq u_{i}\leq\infty\wedge i=1\ldots n$

Si una variable no tuviera cota inferior entonces sería $l_{i} = -\infty$ y si no tuviera cota superior entonces sería $u_{i} = \infty$
restricciones opcionales de desigualdad arbitrarias:

$g_{j}\left(x\right)\leq0 \wedge g_j:\Omega_{g_j}\subset\mathbb{R}^{n}\longrightarrow\mathbb{R} \forall j=1\ldots n_{D} \wedge n_{D} \ge 0$
restricciones opcionales de igualdad arbitrarias:

$h_{k}\left(x\right)=0 \wedge h_k:\Omega_{h_k}\subset\mathbb{R}^{n}\longrightarrow\mathbb{R} \forall k=1\ldots n_{I} \wedge n_{I} \ge 0$

A la región del espacio $\Omega\subset\mathbb{R}^{n}$ de los puntos que cumplen todas las restricciones del problema le llamaremos región de factibilidad del problema. A los puntos de dicha región les llamaremos factibles o interiores y al resto no factibles o exteriores.

Hay una condición que se suele sobreentender por su obviedad, pero que es a veces la causa de que no funcionen los algoritmos: un punto factible debe pertenecer al dominio de la función objetivo, y al de las funciones de restricción, o sea:

$\Omega\subset\Omega_{f}\cap\underset{j=1}{\overset{n_{D}}{\bigcap}}\Omega_{g_{j}}\cap\underset{k=1}{\overset{n_{I}}{\bigcap}}\Omega_{h_{k}}$

Por ejemplo, si en la función objetivo aparece el logaritmo de una variable se debe incluir alguna restricción o conjunto de ellas que obligue a que dicha variable sea positiva. Evidentemente, si no hay restricciones el dominio de la función objetivo debe ser todo el espacio $\Omega_f = \Omega = \mathbb{R}^{n}$ . Obsérvese que si lo que se quiere es minimizar la función objetivo basta con tomar la función opuesta $-f(x)$ .

Nótese que a ninguna de las funciones se le ha exigido ser diferenciable y ni tan siquiera continua, aunque como se verá más tarde el usuario deberá informar de qué clase analitica es el problema para poder saber qué métodos son aplicables.

Guia del usuario

Formulación de funciones objetivo y de restricción

Tanto si se calcula el gradiente como si no, las funciones objetivo y las de restricción deben tener la API TOL general común a todas ellas:

Real eval (Matrix x, Matrix gradient)

En el caso de que se quiera usar un método que precise el gradiente, no se necesariamente se exigirá calcular el mismo cada vez que se quiera evaluar la función. En tales casos se le pasará la matriz vacía para indicar que no se haga el cálculo. Podría pensarse si no sería mejor hacer una función para la evaluación de la función y otra para el gradiente, pero resulta que muy a menudo el cálculo del gradiente utiliza en parte las mismas componentes que la propia función, por lo que resulta más eficiente que se calculen de forma conjunta. La función de evaluación debería por tanto tener este aspecto:

Real eval (Matrix x, Matrix gradient)
{
  ...
  Real y = ...;
  Real If(Rows(grad), {
    ...
    Matrix grad := ...;
    True
  });
  y
};

Si el problema no es diferenciable o el cálculo del gradiente es muy costoso y se van a usar sólo algoritmos que no requieren el cálculo del gradiente, entonces se puede hacer caso omiso del argumento Matrix gradient y calcular sólo el valor de la función.

Tutorial

La mejor forma de aprender a usar cualquier cosa es empezar a usarla de forma controlada, para lo cual se dispone de una batería de ejemplos a disposición de los usuairos.

Función objetivo bivariante no lineal con restricciones de desigualdad no lineal

En primer lugar se expondrá el ejemplo proporcionado en el tutorial de NLopt

Función objetivo

////////////////////////////////////////////////////////////////////////////////
//Target function defined as simple code
Real my_function(Matrix x, Matrix grad)
////////////////////////////////////////////////////////////////////////////////
{
  Real y = Sqrt(MatDat(x,2,1));
  Real If(Rows(grad), {
    Matrix grad := Col(0.0,0.5/y);
    True
  });
  y
};

Restricciones de desigualdad

////////////////////////////////////////////////////////////////////////////////
//When a set of constraining functions are part of a parametric family
//of funcitons we can define a class to make an easier definition
Class @my_inequation 
////////////////////////////////////////////////////////////////////////////////
{
  Real a;
  Real b;
  Real constraint(Matrix x, Matrix grad)
  {
    Real x1 = MatDat(x,1,1);
    Real x2 = MatDat(x,2,1);
    Real ax1b = a*x1 + b;
    Real If(Rows(grad), {
      Matrix grad := Col(3 * a * ax1b^2,-1.0);
      True
    });
    Real g = (ax1b^3 - x2);
    g
  }
};

////////////////////////////////////////////////////////////////////////////////
//Inequality constraining functions defined as class instances
////////////////////////////////////////////////////////////////////////////////
@my_inequation ineq1 = [[Real a= 2,Real b=0]];
@my_inequation ineq2 = [[Real a=-1,Real b=1]];

Guía del programador y del usuario avanzado

El sistema NLopt contiene 17 algoritmos principales con 41 variantes que intentan abarcar la mayor parte de los tipos de problemas tipo de la programación matemática no lineal y cuya descripción puede verse aquí de forma detallada.

Existen métodos para optimización local y global, para funciones no lineales arbitrarias, continuas o diferenciables y con restricciones de igualdad y desigualdad no lineal o sin ellas.

El valor añadido del paquete TOL NonLinGloOpt pretende ser un sistema experto que, en el caso de que el usuario no proponga un método específico, busque uno cuyas características sean compatibles con las del problema, a saber:

IsGlobal 0,1 Un método de optimización puede ser global o local, pero no ambas cosas a al vez, luego es determinante saber si se requiere un óptimo local o uno global para la selección del mismo.
AnalyticalClass AR: Arbitrary,
C0: Continuous,
C1: Differentiable,
C2: Twice differentiable Es la clase analítica mínima capaz de tratar un algoritmo debe ser igual o mayor que la clase mínima de las funciones objetivo y de restricciones. Por ejemplo, si una de las funciones del problema es continua pero no diferenciable y todas las demás son diferenciables, la clase analítica del problema es C0 y sólo se podrán usar algoritmos e tipo AR ó C0, pero no los de tipo C1 ó C2. El usuario es el único que puede y debe ofrecer esta información acerca del problema.
NeedsGradient 0,1 Los algoritmos de tipo C1 ó C2 pueden o no necesitar realmente calcular el gradiente. Por otra parte el que un problema sea clase C1 ó C2 no implica que se conozca analíticamente el gradiente, aunque siempre se puede calcular numéricamente, pero en cualquier caso puede que el coste computacional sea excesivo. Así pues, tanto si el gradiente no existe (AR,C0), como si existe pero no tenemos un método rápido de obtenerlo, se debe elegir un algoritmo que no utilice el gradiente. Es responsabilidad del usuario comunicar al sistema esta característica del problema.
NeedsFeasiblePoint 0,1 Unos métodos precisan comenzar por un punto factible y otros no, y no siempre el usuario es capaz de proporcionar un punto adecuado. En estos casos el sistema debería utilizar un método que pueda comenzar por un punto exterior hasta encontrar uno interior y a partir de ahí se podría continuar con otro método cualquiera que fuera más eficiente. El propio sistema comprobará si la solución inicial proporcionada es factible.
NeedsBounds 0,1 En general todos los métodos globales precisan que se dé un intervalo de dominio a cada variable, es decir, que se defina un hiperrectángulo de búsqueda, mientras que los métodos locales no lo necesitan.
SupportsBounds 0,1 La mayoría de los métodos soportan intervalos de dominio pero no siemrpe es así, por lo que hay que tenerlo en cuenta.
SupportsInequalities 0,1 La mayoría de los métodos de optimización no soportan restricciones de desigualdad, aunque siempre existe la posibilidad de utilizar el método especial del Lagrangiano Aumentado para convertir el problema en otro sin restricciones que se pueda tratar con un método subsidiario adecuado.
SupportsEqualities 0,1 Sólo unos pocos métodos soportan restricciones de igualdad, aunque lo mism o que con las desigualdades se puede aplicar el método especial del Lagrangiano Aumentado. Concretamente se puede aplicar sólo a las restricciones de igualdad manteniendo las de desigualdad si hay un método adecuado que lo pueda resolver.
PreferredScale S: Short [1...10],
M: Medium [11...100],
L: Large[101...1000]
E: Extreme[1001...] El número de variables con el que el algoritmo es capaz de tratar de forma eficiente

En la hoja de cálculo NLopt_algorithms se muestra un cuadro resumen de las características asociadas a cada variante algorítmica del paquete NLopt.

Se aconseja a los programadores y usuarios avanzados visitar de forma somera el código fuente del paquete que a veces es la mejor forma de familiarizarse con un sistema. Estos son los archivos principales del sistema:

NonLinGloOpt.tol: Fichero raíz del paquete
constant.tol: Constantes de codificación de algorimos, resultados, criterios de parada y otras características de la optimización y la definición de los problemas.
problem.tol: Clase @Problem para la definición de problemas.
opt.tol: Clase @Opt para la optimización de problemas mediante la API con NLOpt.
CppTools.cpp: API C++ con NLOpt.

Download in other formats:

Plain Text

IsGlobal	0,1	Un método de optimización puede ser global o local, pero no ambas cosas a al vez, luego es determinante saber si se requiere un óptimo local o uno global para la selección del mismo.
AnalyticalClass	AR: Arbitrary, C0: Continuous, C1: Differentiable, C2: Twice differentiable	Es la clase analítica mínima capaz de tratar un algoritmo debe ser igual o mayor que la clase mínima de las funciones objetivo y de restricciones. Por ejemplo, si una de las funciones del problema es continua pero no diferenciable y todas las demás son diferenciables, la clase analítica del problema es C0 y sólo se podrán usar algoritmos e tipo AR ó C0, pero no los de tipo C1 ó C2. El usuario es el único que puede y debe ofrecer esta información acerca del problema.
NeedsGradient	0,1	Los algoritmos de tipo C1 ó C2 pueden o no necesitar realmente calcular el gradiente. Por otra parte el que un problema sea clase C1 ó C2 no implica que se conozca analíticamente el gradiente, aunque siempre se puede calcular numéricamente, pero en cualquier caso puede que el coste computacional sea excesivo. Así pues, tanto si el gradiente no existe (AR,C0), como si existe pero no tenemos un método rápido de obtenerlo, se debe elegir un algoritmo que no utilice el gradiente. Es responsabilidad del usuario comunicar al sistema esta característica del problema.
NeedsFeasiblePoint	0,1	Unos métodos precisan comenzar por un punto factible y otros no, y no siempre el usuario es capaz de proporcionar un punto adecuado. En estos casos el sistema debería utilizar un método que pueda comenzar por un punto exterior hasta encontrar uno interior y a partir de ahí se podría continuar con otro método cualquiera que fuera más eficiente. El propio sistema comprobará si la solución inicial proporcionada es factible.
NeedsBounds	0,1	En general todos los métodos globales precisan que se dé un intervalo de dominio a cada variable, es decir, que se defina un hiperrectángulo de búsqueda, mientras que los métodos locales no lo necesitan.
SupportsBounds	0,1	La mayoría de los métodos soportan intervalos de dominio pero no siemrpe es así, por lo que hay que tenerlo en cuenta.
SupportsInequalities	0,1	La mayoría de los métodos de optimización no soportan restricciones de desigualdad, aunque siempre existe la posibilidad de utilizar el método especial del Lagrangiano Aumentado para convertir el problema en otro sin restricciones que se pueda tratar con un método subsidiario adecuado.
SupportsEqualities	0,1	Sólo unos pocos métodos soportan restricciones de igualdad, aunque lo mism o que con las desigualdades se puede aplicar el método especial del Lagrangiano Aumentado. Concretamente se puede aplicar sólo a las restricciones de igualdad manteniendo las de desigualdad si hay un método adecuado que lo pueda resolver.
PreferredScale	S: Short [1...10], M: Medium [11...100], L: Large[101...1000] E: Extreme[1001...]	El número de variables con el que el algoritmo es capaz de tratar de forma eficiente