Función cuasiconvexa

Función matemática con conjuntos de nivel inferior convexos

Una función cuasiconvexa que no es convexa

Una función que no es cuasiconvexa: el conjunto de puntos en el dominio de la función para los cuales los valores de la función están por debajo de la línea roja discontinua es la unión de los dos intervalos rojos, que no es un conjunto convexo.

La función de densidad de probabilidad de la distribución normal es cuasiconcava pero no cóncava.

La densidad articular normal bivariada es cuasiconcava.

En matemáticas , una función cuasiconvexa es una función de valor real definida en un intervalo o en un subconjunto convexo de un espacio vectorial real , de modo que la imagen inversa de cualquier conjunto de la forma es un conjunto convexo . Para una función de una sola variable, a lo largo de cualquier tramo de la curva, el punto más alto es uno de los puntos finales. El negativo de una función cuasiconvexa se dice que es cuasiconcava . ${\displaystyle (-\infty ,a)}$

La cuasiconvexidad es una propiedad más general que la convexidad, ya que todas las funciones convexas también son cuasiconvexas, pero no todas las funciones cuasiconvexas son convexas. Las funciones unimodales univariadas son cuasiconvexas o cuasiconcavas, sin embargo, este no es necesariamente el caso de las funciones con múltiples argumentos . Por ejemplo, la función Rosenbrock bidimensional es unimodal pero no cuasiconvexa y las funciones con conjuntos de subniveles convexos en estrella pueden ser unimodales sin ser cuasiconvexas.

Definición y propiedades

Una función definida en un subconjunto convexo de un espacio vectorial real es cuasiconvexa si para todos y tenemos ${\displaystyle f:S\to \mathbb {R} }$ ${\displaystyle S}$ ${\displaystyle x,y\in S}$ ${\displaystyle \lambda \in [0,1]}$

${\displaystyle f(\lambda x+(1-\lambda )y)\leq \max {\big \{}f(x),f(y){\big \}}.}$

En otras palabras, si es tal que siempre es cierto que un punto directamente entre otros dos puntos no da un valor de la función mayor que el de los otros dos puntos, entonces es cuasiconvexo. Nótese que los puntos y , y el punto directamente entre ellos, pueden ser puntos en una línea o, más generalmente, puntos en un espacio n -dimensional. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle y}$

Una función cuasilineal es a la vez cuasiconvexa y cuasiconcava.

La gráfica de una función que es a la vez cóncava y cuasiconvexa en los números reales no negativos.

Una forma alternativa (ver introducción) de definir una función cuasi-convexa es requerir que cada conjunto de subniveles sea un conjunto convexo. ${\displaystyle f(x)}$ ${\displaystyle S_{\alpha }(f)=\{x\mid f(x)\leq \alpha \}}$

Si además

${\displaystyle f(\lambda x+(1-\lambda )y)<\max {\big \{}f(x),f(y){\big \}}}$

para todos y , entonces es estrictamente cuasiconvexo . Es decir, la cuasiconvexidad estricta requiere que un punto directamente entre otros dos puntos debe dar un valor de la función menor que el de uno de los otros puntos. ${\displaystyle x\neq y}$ ${\displaystyle \lambda \in (0,1)}$ ${\displaystyle f}$

Una función cuasiconcava es una función cuyo negativo es cuasiconvexo, y una función estrictamente cuasiconcava es una función cuyo negativo es estrictamente cuasiconvexo. De manera equivalente, una función es cuasiconcava si ${\displaystyle f}$

${\displaystyle f(\lambda x+(1-\lambda )y)\geq \min {\big \{}f(x),f(y){\big \}}.}$

y estrictamente cuasicóncava si

${\displaystyle f(\lambda x+(1-\lambda )y)>\min {\big \{}f(x),f(y){\big \}}}$

Una función (estrictamente) cuasiconvexa tiene conjuntos de contornos inferiores (estrictamente) convexos , mientras que una función (estrictamente) cuasiconcava tiene conjuntos de contornos superiores (estrictamente) convexos .

Una función que es a la vez cuasiconvexa y cuasiconcava es cuasilineal .

Un caso particular de cuasi-concavidad, si , es la unimodalidad , en la que hay un valor localmente máximo. ${\displaystyle S\subset \mathbb {R} }$

Aplicaciones

Las funciones cuasiconvexas tienen aplicaciones en el análisis matemático , en la optimización matemática y en la teoría de juegos y la economía .

Optimización matemática

En la optimización no lineal , la programación cuasiconvexa estudia métodos iterativos que convergen a un mínimo (si existe uno) para funciones cuasiconvexas. La programación cuasiconvexa es una generalización de la programación convexa . ^{[1] La programación cuasiconvexa se utiliza en la solución de} problemas duales "sustitutos" , cuyos biduales proporcionan cierres cuasiconvexos del problema primal, que por lo tanto proporcionan límites más estrictos que los cierres convexos proporcionados por los problemas duales lagrangianos . ^[2] En teoría , los problemas de programación cuasiconvexa y programación convexa se pueden resolver en una cantidad de tiempo razonable, donde el número de iteraciones crece como un polinomio en la dimensión del problema (y en el recíproco del error de aproximación tolerado); ^{[3] sin embargo, tales métodos teóricamente "eficientes" utilizan} reglas de tamaño de paso de "series divergentes" , que se desarrollaron por primera vez para métodos de subgradiente clásicos . Los métodos de subgradiente clásicos que utilizan reglas de series divergentes son mucho más lentos que los métodos modernos de minimización convexa, como los métodos de proyección de subgradiente, los métodos de descenso de haces y los métodos de filtro no suave.

Economía y ecuaciones diferenciales parciales: teoremas minimax

En microeconomía , las funciones de utilidad cuasiconvexas implican que los consumidores tienen preferencias convexas . Las funciones cuasiconvexas también son importantes en la teoría de juegos , la organización industrial y la teoría del equilibrio general , en particular para las aplicaciones del teorema minimax de Sion . El teorema de Sion, que generaliza un teorema minimax de John von Neumann , también se utiliza en la teoría de ecuaciones diferenciales parciales .

Preservación de la cuasiconvexidad

Operaciones que preservan la cuasiconvexidad

• El máximo de las funciones cuasiconvexas (es decir, ) es cuasiconvexo. De manera similar, el máximo de las funciones cuasiconvexas estrictas es cuasiconvexo estricto. ^[4] De manera similar, el mínimo de las funciones cuasiconcavas es cuasiconcava, y el mínimo de las funciones estrictamente cuasiconcavas es estrictamente cuasiconcava. ${\displaystyle f=\max \left\lbrace f_{1},\ldots ,f_{n}\right\rbrace }$
• Composición con una función no decreciente: cuasiconvexa, no decreciente, entonces es cuasiconvexa. De manera similar, si es cuasiconcava, no decreciente, entonces es cuasiconcava. ${\displaystyle g:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle h:\mathbb {R} \rightarrow \mathbb {R} }$ ${\displaystyle f=h\circ g}$ ${\displaystyle g:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle h:\mathbb {R} \rightarrow \mathbb {R} }$ ${\displaystyle f=h\circ g}$
• minimización (es decir, conjunto cuasiconvexo, convexo, entonces es cuasiconvexo) ${\displaystyle f(x,y)}$ ${\displaystyle C}$ ${\displaystyle h(x)=\inf _{y\in C}f(x,y)}$

Operaciones que no preservan la cuasiconvexidad

• La suma de funciones cuasiconvexas definidas en el mismo dominio no necesita ser cuasiconvexa: en otras palabras, si son cuasiconvexas, entonces no necesitan ser cuasiconvexas. ${\displaystyle f(x),g(x)}$ ${\displaystyle (f+g)(x)=f(x)+g(x)}$
• La suma de funciones cuasiconvexas definidas en diferentes dominios (es decir, si son cuasiconvexas, ) no necesita ser cuasiconvexa. Dichas funciones se denominan "descompuestas aditivamente" en economía y "separables" en optimización matemática . ${\displaystyle f(x),g(y)}$ ${\displaystyle h(x,y)=f(x)+g(y)}$

Ejemplos

• Toda función convexa es cuasiconvexa.
• Una función cóncava puede ser cuasiconvexa. Por ejemplo, es cóncava y cuasiconvexa. ${\displaystyle x\mapsto \log(x)}$
• Toda función monótona es a la vez cuasiconvexa y cuasiconcava. En términos más generales, una función que decrece hasta un punto y aumenta a partir de ese punto es cuasiconvexa (compárese con la unimodalidad ).
• La función de suelo es un ejemplo de una función cuasiconvexa que no es ni convexa ni continua. ${\displaystyle x\mapsto \lfloor x\rfloor }$

Véase también

• Función convexa
• Función cóncava
• Función logarítmicamente cóncava
• Pseudoconvexidad en el sentido de varias variables complejas (convexidad no generalizada)
• Función pseudoconvexa
• Función Invex
• Concavificación

Referencias

1. Di Guglielmo (1977, pp. 287–288): Di Guglielmo, F. (1977). "Dualidad no convexa en optimización multiobjetivo". Matemáticas de la investigación de operaciones . 2 (3): 285–291. doi :10.1287/moor.2.3.285. JSTOR  3689518. MR  0484418.
2. Di Guglielmo, F. (1981). "Estimaciones de la brecha de dualidad para problemas de optimización discretos y cuasiconvexos". En Schaible, Siegfried; Ziemba, William T. (eds.). Concavidad generalizada en optimización y economía: Actas del Instituto de Estudios Avanzados de la OTAN celebrado en la Universidad de Columbia Británica, Vancouver, BC, 4-15 de agosto de 1980. Nueva York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. págs. 281-298. ISBN 0-12-621120-5.Sr. 0652702  .
3. Kiwiel, Krzysztof C. (2001). "Convergencia y eficiencia de los métodos de subgradiente para la minimización cuasiconvexa". Programación matemática, serie A . 90 (1). Berlín, Heidelberg: Springer: 1–25. doi :10.1007/PL00011414. ISSN  0025-5610. MR  1819784. S2CID  10043417.Kiwiel reconoce que Yuri Nesterov fue el primero en establecer que los problemas de minimización cuasiconvexa pueden resolverse de manera eficiente.
4. Johansson, Edvard; Petersson, David (2016). Optimización de parámetros para soluciones de equilibrio de sistemas de acción de masas (tesis de maestría). pp. 13–14 . Consultado el 26 de octubre de 2016 .

• Avriel, M., Diewert, WE, Schaible, S. y Zang, I., Concavidad generalizada , Plenum Press, 1988.
• Crouzeix, J.-P. (2008). "Cuasi-concavidad". En Durlauf, Steven N.; Blume, Lawrence E (eds.). The New Palgrave Dictionary of Economics (Segunda ed.). Palgrave Macmillan. págs. 815–816. doi :10.1057/9780230226203.1375. ISBN 978-0-333-78676-5.
• Singer, Ivan Análisis convexo abstracto . Serie de monografías y textos avanzados de la Sociedad Matemática Canadiense. Una publicación de Wiley-Interscience. John Wiley & Sons, Inc., Nueva York, 1997. xxii+491 pp.  ISBN 0-471-16015-6 

Enlaces externos

• SION, M., "Sobre teoremas generales de minimax", Pacific J. Math. 8 (1958), 171-176.
• Glosario de programación matemática
• Funciones cóncavas y cuasi-cóncavas - por Charles Wilson, Departamento de Economía de la Universidad de Nueva York
• Cuasiconcavidad y cuasiconvexidad: por Martin J. Osborne, Departamento de Economía de la Universidad de Toronto