Função quasiconvex - Quasiconvex function

Uma função quase convexa que não é convexa

Uma função que não é quase-convexa: o conjunto de pontos no domínio da função para os quais os valores da função estão abaixo da linha vermelha tracejada é a união dos dois intervalos vermelhos, que não é um conjunto convexo.

A função de densidade de probabilidade da distribuição normal é quase côncava, mas não côncava.

A densidade normal bivariada da articulação é quase côncava.

Em matemática , uma função quase-convexa é uma função com valor real definida em um intervalo ou em um subconjunto convexo de um espaço vetorial real de forma que a imagem inversa de qualquer conjunto da forma seja um conjunto convexo . Para uma função de uma única variável, ao longo de qualquer trecho da curva, o ponto mais alto é um dos pontos finais. Diz-se que o negativo de uma função quase-convexa é quase-convexa . ${\ displaystyle (- \ infty, a)}$

Todas as funções convexas também são quase-convexas, mas nem todas as funções quase-convexas são convexas, portanto, quase-convexidade é uma generalização da convexidade. A quase-convexidade e a quase-concavidade estendem às funções com argumentos múltiplos a noção de unimodalidade das funções com um único argumento real.

Definição e propriedades

Uma função definida em um subconjunto convexo de um espaço vetorial real é quase- convexa se for para todos e temos ${\ 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 \}}.}

Em palavras, se é sempre verdade que um ponto diretamente entre dois outros pontos não fornece um valor mais alto da função do que ambos os outros pontos dão, então é quase-convexo. Observe que os pontos e , e o ponto diretamente entre eles, podem ser pontos em uma linha ou, mais geralmente, pontos no espaço n- dimensional. ${\ displaystyle f}$ ${\ displaystyle f}$ ${\ displaystyle x}$ ${\ displaystyle y}$

Uma função quase-linear é quase-convexa e quase-convexa.

O gráfico de uma função que é côncava e quase convexa nos números reais não negativos.

Uma forma alternativa (ver introdução) de definir uma função quase convexa é exigir que cada conjunto de subnível seja um conjunto convexo. ${\ displaystyle f (x)}$ ${\ displaystyle S _ {\ alpha} (f) = \ {x \ mid f (x) \ leq \ alpha \}}$

Se além disso

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

para todos e , então é estritamente quase-convexo . Ou seja, a quase-convexidade estrita requer que um ponto diretamente entre dois outros pontos forneça um valor mais baixo da função do que um dos outros pontos. ${\ displaystyle x \ neq y}$ ${\ displaystyle \ lambda \ in (0,1)}$ ${\ displaystyle f}$

Uma função quase-convexa é uma função cujo negativo é quase-convexo, e uma função estritamente quase-convexa é uma função cujo negativo é estritamente quase-convexo. Equivalentemente, uma função é quase côncava se ${\ displaystyle f}$

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

e estritamente quase côncavo se

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

Uma função (estritamente) quase-convexa tem conjuntos de contorno inferior (estritamente) convexos , enquanto uma função (estritamente) quase-convexa tem conjuntos de contorno superior (estritamente) convexos .

Uma função que é quase-convexa e quase- convexa é quase - linear .

Um caso particular de quase-concavidade, se , é unimodalidade , na qual existe um valor máximo local. ${\ displaystyle S \ subset \ mathbb {R}}$

Formulários

As funções quasiconvexas têm aplicações na análise matemática , na otimização matemática e na teoria e economia dos jogos .

Otimização matemática

Na otimização não linear , a programação quasiconvexa estuda métodos iterativos que convergem a um mínimo (se houver) para funções quasiconvexas. A programação quasiconvexa é uma generalização da programação convexa . A programação quasiconvexa é usada na solução de problemas duais "substitutos" , cujos biduais fornecem fechamentos quase-convexos do problema primordial, que, portanto, fornecem limites mais estreitos do que os fechamentos convexos fornecidos pelos problemas duais de Lagrange . Em teoria , os problemas de programação quase-convexa e programação convexa podem ser resolvidos em tempo razoável, onde o número de iterações cresce como um polinômio na dimensão do problema (e na recíproca do erro de aproximação tolerado); entretanto, tais métodos teoricamente "eficientes" usam regras de tamanho de passo de "série divergente" , que foram desenvolvidas primeiro para métodos clássicos de subgradientes . Os métodos clássicos de subgradiente que usam regras de série divergente são muito mais lentos do que os métodos modernos de minimização convexa, como métodos de projeção de subgradiente, métodos de descida de feixe e métodos de filtro não suaves .

Economia e equações diferenciais parciais: teoremas Minimax

Em microeconomia , as funções de utilidade quase côncava implicam que os consumidores têm preferências convexas . Funções quasiconvexas são importantes também na teoria dos jogos , organização industrial e teoria do equilíbrio geral , particularmente para aplicações do teorema minimax de Sion . Generalizando um teorema minimax de John von Neumann , o teorema de Sion também é usado na teoria das equações diferenciais parciais .

Preservação de quase-convexidade

Operações preservando a quase-convexidade

o máximo de funções quase-convexas (ou seja ) é quase-convexo. Da mesma forma, o máximo de funções quase-convexas estritas é quase-convexo estrito. Da mesma forma, o mínimo de funções quasiconcavas é quase côncava, e o mínimo de funções quase côncavas é estritamente quase côncava. ${\ displaystyle f = \ max \ left \ lbrace f_ {1}, \ ldots, f_ {n} \ right \ rbrace}$
composição com uma função não decrescente (ou seja , quase - convexa, não decrescente, então é quase-convexa) ${\ displaystyle g: \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R}}$ ${\ displaystyle h: \ mathbb {R} \ rightarrow \ mathbb {R}}$ ${\ displaystyle f = h \ circ g}$
minimização (ou seja , conjunto quase- convexo, conjunto quase- convexo ) ${\ displaystyle f (x, y)}$ ${\ displaystyle C}$ ${\ displaystyle h (x) = \ inf _ {y \ in C} f (x, y)}$

Operações que não preservam a quase-convexidade

A soma das funções quase-convexas definidas no mesmo domínio não precisa ser quase-convexa: em outras palavras, se forem quase-convexas, não precisam ser quase-convexas. ${\ displaystyle f (x), g (x)}$ ${\ displaystyle (f + g) (x) = f (x) + g (x)}$
A soma das funções quase-convexas definidas em domínios diferentes (ou seja, se forem quase-convexas ) , não precisa ser quase-convexa. Essas funções são chamadas de "decompostas aditivamente" na economia e "separáveis" na otimização matemática . ${\ displaystyle f (x), g (y)}$ ${\ displaystyle h (x, y) = f (x) + g (y)}$

Exemplos

Toda função convexa é quase convexa.
Uma função côncava pode ser quase convexa. Por exemplo, é côncavo e quase convexo. ${\ displaystyle x \ mapsto \ log (x)}$
Qualquer função monotônica é quase convexa e quase convexa. Mais geralmente, uma função que diminui até certo ponto e aumenta a partir desse ponto é quase-convexa (compare a unimodalidade ).
A função de chão é um exemplo de função quase-convexa que não é convexa nem contínua. ${\ displaystyle x \ mapsto \ lfloor x \ rfloor}$

Veja também

Função convexa
Função côncava
Função logaritmicamente côncava
Pseudoconvexidade no sentido de várias variáveis complexas (não convexidade generalizada)
Função pseudoconvexo
Função Invex
Concavificação

Referências

^ Di Guglielmo (1977 , pp. 287–288): Di Guglielmo, F. (1977). "Dualidade não convexa na otimização multiobjetivo". Matemática da Pesquisa Operacional . 2 (3): 285–291. doi : 10.1287 / moor.2.3.285 . JSTOR 3689518 . MR 0484418 .
^ Di Guglielmo, F. (1981). "Estimativas da lacuna de dualidade para problemas de otimização discreta e quase-convexa". Em Schaible, Siegfried; Ziemba, William T. (eds.). Concavidade generalizada em otimização e economia: Procedimentos do Instituto de Estudos Avançados da OTAN realizados na Universidade de British Columbia, Vancouver, BC, 4–15 de agosto de 1980 . Nova York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. pp. 281–298. ISBN 0-12-621120-5 . MR 0652702 .
^ Kiwiel, Krzysztof C. (2001). “Convergência e eficiência de métodos de subgradientes para minimização quasiconvexa”. Programação Matemática, Série A . 90 (1). Berlim, Heidelberg: Springer. pp. 1-25. doi : 10.1007 / PL00011414 . ISSN 0025-5610 . MR 1819784 . Kiwiel reconhece que Yuri Nesterov primeiro estabeleceu que os problemas de minimização quasiconvexos podem ser resolvidos de forma eficiente.
^ Johansson, Edvard; Petersson, David (2016). "Otimização de parâmetros para soluções de equilíbrio de sistemas de ação em massa" : 13–14 . Retirado em 26 de outubro de 2016 . Citar diário requer |journal= ( ajuda )

Avriel, M., Diewert, WE, Schaible, S. e Zang, I., Generalized Concavity , Plenum Press, 1988.
Crouzeix, J.‑P. (2008). "Quase-concavidade". Em Durlauf, Steven N .; Blume, Lawrence E (eds.). The New Palgrave Dictionary of Economics (Segunda ed.). Palgrave Macmillan. pp. 815–816. doi : 10.1057 / 9780230226203.1375 . ISBN 978-0-333-78676-5 .
Singer, Ivan Análise convexa abstrata . Série de monografias e textos avançados da Canadian Mathematical Society. Publicação Wiley-Interscience. John Wiley & Sons, Inc., New York, 1997. xxii + 491 pp. ISBN 0-471-16015-6

links externos

SION, M., "On general minimax teoreems", Pacific J. Math. 8 (1958), 171-176.
Glossário de programação matemática
Funções côncavas e quase côncavas - por Charles Wilson, Departamento de Economia da NYU
Quase-concavidade e quase-concavidade - por Martin J. Osborne, Departamento de Economia da Universidade de Toronto

[1] Di Guglielmo (1977 , pp. 287–288): Di Guglielmo, F. (1977). "Dualidade não convexa na otimização multiobjetivo". Matemática da Pesquisa Operacional . 2 (3): 285–291. doi : 10.1287 / moor.2.3.285 . JSTOR 3689518 . MR 0484418 .

[2] Di Guglielmo, F. (1981). "Estimativas da lacuna de dualidade para problemas de otimização discreta e quase-convexa". Em Schaible, Siegfried; Ziemba, William T. (eds.). Concavidade generalizada em otimização e economia: Procedimentos do Instituto de Estudos Avançados da OTAN realizados na Universidade de British Columbia, Vancouver, BC, 4–15 de agosto de 1980 . Nova York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. pp. 281–298. ISBN 0-12-621120-5 . MR 0652702 .

[3] Kiwiel, Krzysztof C. (2001). “Convergência e eficiência de métodos de subgradientes para minimização quasiconvexa”. Programação Matemática, Série A . 90 (1). Berlim, Heidelberg: Springer. pp. 1-25. doi : 10.1007 / PL00011414 . ISSN 0025-5610 . MR 1819784 . Kiwiel reconhece que Yuri Nesterov primeiro estabeleceu que os problemas de minimização quasiconvexos podem ser resolvidos de forma eficiente.

[4] Johansson, Edvard; Petersson, David (2016). "Otimização de parâmetros para soluções de equilíbrio de sistemas de ação em massa" : 13–14 . Retirado em 26 de outubro de 2016 . Citar diário requer |journal= ( ajuda )

Languages

In other projects