Fig.3.4 Funções unimodais: a) suave, b) contínua, c) descontínua, d) discreta, e) arbitrária.

é possível degenerar para um ponto um ou dois dos segmentos , , (Figura 3.5).

Fig.3.5. Variantes de arranjo e degenerescência a um ponto de segmentos de monotonicidade e constância de uma função unimodal.

o conjunto de funções que são unimodais em um segmento será denotado por Q. A unimodalidade de funções é uma propriedade excepcionalmente importante que é amplamente utilizada em estudos de otimização.

3.2.3 Funções convexas, pseudo-convexas e quase convexas.

Funções convexas e suas generalizações (funções pseudo-convexas e quase-convexas) desempenham um papel importante na teoria da otimização. Essas funções serão usadas para formular condições de otimalidade suficientes.

Uma função numérica f definida em um conjunto convexo X, XÌE n é chamada convexa se para quaisquer dois pontos x 1 ,x 2 нX e um número arbitrário lн a desigualdade

f(lx 1 +(1-l)x 2) £lf(x 1)+(1-l)f(x 2). (3.1)

A desigualdade do sentido oposto define uma função côncava, e os termos "convexo para baixo (1)" "convexo para cima (2)" são frequentemente usados ​​(Figura 3.6).

Fig.3.6. 1) Função convexa (convexa para baixo), 2) Função côncava (côncava para cima).

Geometricamente, a convexidade da função f significa que qualquer ponto de uma corda arbitrária do gráfico f está localizado não abaixo do ponto correspondente do próprio gráfico (está abaixo da corda que liga dois pontos de seu gráfico), (Figura 3.6. , Curva 1).

Os exemplos mais simples de funções convexas de uma variável são a parábola y=x 2 e o expoente y=e x . As funções y=-x 2 e y=-e x são côncavas.

Se para todo x 1, x 2 ОX x 1 ¹x 2 e lО a desigualdade (3.1) é estrita (<), то f называется estritamente convexo em X (Figura 3.7, a). A função é chamada (estritamente) curvado , se - f for (estritamente) convexo (Fig. 3.7, b).

Fig.3.7. Funções estritamente convexas (a) e estritamente côncavas, suas derivadas (linha pontilhada) e uma função que tem seção linear

Função f(x), definido em um conjunto convexo X, é chamado fortemente convexo com constante eu> 0 se

Vamos dar uma interpretação geométrica da definição (3.2) considerando a função

y=f(x) uma variável. Fixação x 1 e x 2 do domínio da função e denotando , mudaremos l de 0 para 1. É claro que então o valor x(l), mudará de x 1 antes x 2, e ponto ( X, f(x)) passará pelo gráfico da função y=f(x) do ponto B = ( x2, f(x2)) até o ponto MAS= (x 1 , f(x 1))(fig.3.8).

Fig.3.8. Gráfico de uma função fortemente convexa.

Equações

no plano xOy descreva uma linha reta eu(secante) conectando os pontos MAS e NO, e as equações

definir uma parábola R Gentil , que passa pelos pontos MAS e NO. A desigualdade (3.2) neste caso significa que o gráfico da função y = f(x) no plano xOy está localizado abaixo não apenas da secante que conecta os pontos MAS e NO, mas também da parábola Р, cuja deflexão é determinada pelo parâmetro eu e pode ser escolhido arbitrariamente pequeno. Em outras palavras, na área limitada pela secante e o gráfico da função, você pode construir uma parábola ligando os pontos MAS e NO.

· Teorema 3.1 Função continuamente diferenciável em um conjunto convexo X fé convexa neste conjunto se e somente se para qualquer x 1 ,x 2 О X verdadeira desigualdade

f(x 2) ³ f(x 1) +<Ñf(x 1 ,x 2 -x 1)>, (3.3)

obtido a partir da decomposição da função f(x) em uma série de Taylor em um ponto x 1 eliminando os termos de segunda e maior ordem da expansão

F(x 1 +h) = f(x 1) + hf ¢(x 1) + h 2 /2*f¢¢(x 1) +..., (3.3)

onde h é um número suficientemente pequeno, |h|

Ñf(x 1) = (¶f/¶x 1 , ¶f/¶x 2 ,.., ¶f/¶x n) m,

Essa. é um vetor de derivadas parciais de primeira ordem, calculado no ponto x 1 e é chamado de gradiente da função f no ponto x 1 .

· Teorema 3.2 Seja uma função f duas vezes continuamente diferenciável em um conjunto convexo X contendo pelo menos um ponto interior, e seja m 2 f(x) sua hessiana. Então para a convexidade de f no conjunto X é necessário e suficiente que a matriz m 2 f(x) seja definida não negativa para todo xнX, ou seja, à desigualdade

<Ñ 2 f(x)h, h>³0 (3,4)

realizada para todos os pontos xнX, hнE n . Aqui a matriz numérica Ñ 2 f(x) é chamada de Hessiana (ou matriz Hessiana). Se uma função f tem derivadas parciais de segunda ordem contínuas (duas vezes continuamente diferenciável) em um ponto x 1 , então ela é duas vezes diferenciável em x 1 e tem uma matriz Hessiana da forma

além disso, essa matriz é simétrica, ou seja,

Afirmações semelhantes também valem para funções côncavas. Neste caso, nas fórmulas (3.2) e (3.4), o sinal de desigualdade ³ deve ser substituído por £.

Verificando a convexidade de uma função.

Uma função f é convexa se sua matriz hessiana for definida positiva (>0) ou semidefinida positiva para todos os valores x 1 ,x 2 ,..,x n.

Verificando a função de convexidade.

Uma função f é convexa se sua matriz hessiana for semidefinida negativa (£0) para todo x 1 ,x 2 ,..,x n .

Uma função estritamente convexa ou côncava tem um único extremo, que é o mínimo ou máximo global, respectivamente. Uma função que tem uma seção linear (Figura 3.7, c) tem um número infinito de extremos iguais em magnitude.

Para julgar uma-extremidade na presença de restrições, pode-se usar o conceito de convexidade de um conjunto admissível. Um conjunto é convexo se qualquer segmento da linha reta que liga dois pontos dos limites do conjunto está inteiramente dentro do conjunto.

A convexidade ou concavidade da função objetivo também pode ser julgada pela natureza da mudança em suas derivadas parciais ¶f/¶x. No caso de uma função estritamente convexa, essa derivada aumenta à medida que o argumento aumenta (Fig. 3.7 a), e para uma função estritamente convexa ela diminui (Fig. 3.7 b). Se houver um segmento linear da função objetivo, a derivada indicada neste segmento é constante.

Conjunto convexo da forma

X=(xнE n ) | Ax£b)=(xнE n | £b i , i=1,..,m)

onde A é uma matriz m*n com linhas a 1 ,..,a m , b=(b 1 ,..,b m) н E n (m=1,2,..). Costuma-se chamar poliédrico ou simplesmente poliedro. Assim, um poliedro é um conjunto de soluções para algum sistema de um número finito de desigualdades lineares, ou, o que dá no mesmo, uma interseção de um número finito de meios-espaços (Figura 3.9).

Fig.3.9. Conjunto poliédrico (poliedro).

Por exemplo, o polígono da Fig. 2.1, a é convexo e o polígono da Fig. 2.1, b não é convexo (está localizado em ambos os lados da reta BC).

A propriedade de definição geral que distingue um polígono convexo de um não convexo é que, se você pegar dois de seus pontos e conectá-los a um segmento, todo o segmento pertencerá a esse polígono. Esta propriedade pode ser tomada como a definição de um conjunto convexo de pontos.

Um conjunto de pontos é chamado convexo se, juntamente com quaisquer dois de seus pontos, contiver todo o segmento que liga esses pontos.

De acordo com essa definição, o polígono da Fig. 2.1, a é um conjunto convexo e o polígono da Fig. 2.1, b não é tal, porque o segmento WE entre seus dois pontos M e / V não pertence completamente a este polígono.

Sejam M e N quaisquer dois pontos de interseção de dois conjuntos A e B (Fig. 2.3). Como os pontos M e N pertencem à interseção de conjuntos, ou seja, um conjunto convexo A e um conjunto convexo B, então, de acordo com a definição de um conjunto convexo, todos os pontos do segmento MI pertencerão tanto ao conjunto A quanto ao conjunto B, ou seja, interseção desses conjuntos. E isso significa que a interseção desses conjuntos é um conjunto convexo. ■

Entre os pontos de um conjunto convexo, pode-se destacar pontos interiores, limites e cantos.

Um ponto de um conjunto é dito interno se alguma de suas vizinhanças contém pontos somente deste conjunto.

Fig- 2-3 O ponto do conjunto é chamado de fronteira,

se alguma de suas vizinhanças contém pontos que pertencem ao conjunto dado e pontos que não pertencem a ele.

Pontos de canto são de particular interesse em problemas de programação linear.

Um ponto de um conjunto é chamado de ponto de canto (ou extremo) se não for interno a nenhum segmento pertencente inteiramente ao conjunto dado.

Na fig. 2.4 mostra exemplos de vários pontos do polígono: interno (ponto M), limite (ponto I) e canto (pontos A, B, C, D E). O ponto A é angular, pois para qualquer segmento que pertença inteiramente ao polígono, por exemplo, segmento AP, ele não é interno; o ponto A é interno ao segmento Kb, mas este segmento não pertence inteiramente ao polígono.

Para um conjunto convexo, os pontos dos cantos sempre coincidem com os vértices do polígono (poliedro), enquanto isso não é necessário para um conjunto não convexo. Assim, na fig. 2,5 ponto A é um vértice de um polígono não convexo, mas não de vértice (é interno ao segmento Kb, que pertence inteiramente a este polígono).

Um conjunto de pontos é chamado fechado se incluir todos os seus pontos de fronteira. Um conjunto de pontos é dito limitado se existe uma bola (círculo) de raio de comprimento finito centrado em qualquer ponto do conjunto que contém completamente o conjunto dado; caso contrário, o conjunto é chamado de ilimitado.

Se uma figura é limitada apenas a linhas retas ou seus segmentos, então o número de seus pontos de canto é finito; no caso de contornos curvilíneos, a figura contém infinitos pontos de canto, o que nos permite fazer a seguinte definição.

Um conjunto fechado convexo de pontos em um espaço (plano) que tem um número finito de pontos de vértice é chamado de poliedro convexo (polígono) se for limitado, e uma região poliédrica convexa (poligonal) se for ilimitado.

Até agora consideramos conjuntos convexos de pontos no plano e no espaço. Analiticamente, tais pontos são representados por um par ordenado de números (xx x2) ou um triplo ordenado de números (*1, *2, *h). O conceito de ponto pode ser generalizado, ou seja, por um ponto (ou um vetor ) um conjunto ordenado de n números ., xn), no qual os números xx, x2, ..., xn são chamados de coordenadas de um ponto (vetor). Tal generalização faz sentido, pois se tomarmos qualquer objeto econômico, então dois ou três números geralmente não são suficientes para caracterizá-lo, sendo necessário tomar n números, onde n > 3.

O conjunto de todos os pontos X = (xx x2,..., xn) é um espaço de ponto n-dimensional (vetor). Para n > 3, os pontos e figuras de um espaço n-dimensional não têm significado geométrico real, e todos os estudos de objetos neste espaço devem ser realizados de forma analítica. No entanto, parece ser conveniente, neste caso, usar conceitos geométricos para facilitar idéias sobre os objetos do "espaço dimensional".

III. Conjuntos e Funções Convexas 569

3. Todas as funções de uma variável com elasticidade constante ω têm a forma (8) (use a igualdade (4)).

4. Funções de várias variáveis ​​com elasticidades parciais constantes são funções de potência da forma

y = Ax1 B 1 x2 B 2 ,..., xN B N .

III. Conjuntos e funções convexos

No estudo de fenômenos econômicos por métodos matemáticos, uma propriedade de muitos conjuntos e funções como a convexidade acaba sendo muito significativa. A natureza do comportamento de muitos objetos econômicos está relacionada ao fato. que certas dependências que descrevem esses objetos são convexas. A existência ou unicidade da solução de problemas econômicos é frequentemente associada à convexidade de funções e conjuntos: muitos algoritmos computacionais são baseados nesta propriedade.

A validade de muitas afirmações sobre conjuntos e funções convexas é bastante clara, elas são quase óbvias. Ao mesmo tempo, sua prova é muitas vezes muito difícil. Portanto, alguns fatos básicos relacionados à convexidade serão aqui expostos, sem comprovação, contando com sua persuasão intuitiva.

1. Conjuntos convexos no plano

Qualquer figura geométrica no plano pode ser considerada como um conjunto de pontos pertencentes a esta figura. Alguns conjuntos (por exemplo, um círculo, um retângulo, uma faixa entre linhas paralelas) contêm pontos internos e de limite; outros (por exemplo, um segmento, um círculo) consistem apenas em pontos de fronteira.

Um conjunto de pontos em um plano é chamado de convexo se tiver a seguinte propriedade: o segmento que liga quaisquer dois pontos desse conjunto está inteiramente contido nesse conjunto (Fig. 1).

Exemplos de conjuntos convexos são: um triângulo, um segmento, um semiplano (uma parte de um plano que se encontra em um lado de uma linha reta), o plano inteiro. Outros exemplos de conjuntos convexos são mostrados na fig. 2a. Na fig. 2b mostra exemplos de conjuntos não convexos.

Um conjunto que consiste em um único ponto e um conjunto vazio que não contém pontos, por convenção, também são considerados convexos. De qualquer forma, nesses conjuntos é impossível traçar um segmento que conecte alguns pontos desses conjuntos e não pertença inteiramente a esses conjuntos, - neles

570 Aplicação Matemática

Arroz. 1. Um segmento ligando quaisquer dois pontos de uma figura convexa está contido inteiramente nele.

Arroz. 2. Conjuntos convexos (a) e não convexos (b) no plano.

não é possível selecionar dois pontos. Portanto, sua inclusão entre conjuntos convexos não levará a uma contradição com a definição, e isso é suficiente para o raciocínio matemático.

A interseção, ou seja, a parte comum de dois conjuntos convexos, é sempre convexa: tomando quaisquer dois pontos de interseção (e eles são comuns, ou seja, eles pertencem a cada um dos conjuntos que se intersectam) e conectando-os com um segmento, podemos ver facilmente que todos os pontos do segmento i são comuns a ambos os conjuntos, pois cada um deles é convexo. Você - a interseção de qualquer número de conjuntos convexos também será convexa.

Uma propriedade importante dos conjuntos convexos é sua separabilidade: se dois conjuntos convexos não têm pontos internos comuns, então o plano pode ser cortado ao longo de uma linha reta de tal forma que um dos conjuntos fique inteiramente em um semiplano, e o outro no outro (na linha de corte) pontos de ambos os conjuntos podem ser localizados). A linha que os separa em alguns casos x acaba sendo a única possível, em outros não (Fig. 3).

O ponto limite de qualquer conjunto convexo em si pode ser considerado como um conjunto convexo que não tem com o conjunto original

Arroz. 3. Linhas de separação. Arroz. 4. Linhas de referência.

III. Conjuntos e funções convexos 571

por pontos interiores comuns, portanto, pode ser separado dele por alguma linha reta. A linha que separa seu ponto limite de um conjunto convexo é chamada de linha de suporte desse conjunto no ponto dado. As linhas de referência em alguns pontos do contorno podem ser as únicas, em outros não são as únicas (Fig. 4).

Vamos introduzir um sistema de coordenadas cartesianas x, y no plano. Agora temos a oportunidade de considerar várias figuras como conjuntos de tais pontos cujas coordenadas satisfazem certas equações ou desigualdades (se as coordenadas de um ponto satisfazem alguma condição, diremos por brevidade que o próprio ponto satisfaz essa condição).

Exercício 1

Considere figuras cujos pontos satisfazem as desigualdades: a) y ³ x2 ; b)xy ³ 1; c)xy ³ 1, x > 0; d) |x| + |ó|£ 2;

e) (õ+1)2 + (ó – 2)2 £ 9. Quais delas são convexas?

A equação linear ax + by = c é satisfeita pelos pontos da reta. Em outras palavras, a linha reta é a solução dessa equação. Resolvendo a desigualdade linear

A solução de cada uma das inequações é um semiplano. A solução do sistema é um conjunto de pontos, cada um dos quais satisfaz todas as inequações do sistema, ou seja, a solução do sistema de inequações é a interseção de todas as soluções das inequações individuais que compõem o sistema. Um semiplano é um conjunto convexo e a interseção de conjuntos convexos é sempre convexa. Assim, a solução do sistema (2) é um conjunto convexo. Na fig. 5 mostra a solução do sistema de desigualdades

ïî - 2x - y ³ -7.

Arroz. 5. Solução de um sistema de três desigualdades lineares.

572 Aplicação Matemática

Observe que a desigualdade ax + por £ c pode ser substituída por uma desigualdade equivalente –àõ – by³ –ñ tendo a forma (1). Além disso, a equação ax + by = c é equivalente ao seguinte par de desigualdades:

( ax + por ³ c; ax + por £ c.

Assim, a solução de um sistema de equações lineares e inequações é sempre um conjunto convexo.

Exercício 2

A solução do sistema

ai x + bi y > ci , i = l, 2, ..., N

conjunto convexo? Como ela difere da solução do sistema s (2)?

Exercício 3

Invente sistemas de desigualdades cujas soluções sejam: a) um paralelogramo; b) o interior do canto; c) uma faixa entre duas retas paralelas; d) um único ponto; e) o conjunto vazio.

2. Funções convexas de uma variável

A maneira mais fácil de definir uma função convexa é geometricamente. Para isso, é útil introduzir o conceito de epígrafe de uma função. A epígrafe de uma função é o conjunto de pontos localizados acima do gráfico da função e no próprio gráfico. Mais estritamente, a epígrafe da função f(x) é o conjunto de tais pontos cuja coordenada x está no domínio da função e cuja coordenada y satisfaz a desigualdade y ³ f(x).

Uma função é chamada de convexa para baixo se sua epígrafe for um conjunto convexo. Arroz. 6 ilustra esta definição.

Arroz. 6. Epígrafe de uma função convexa.

Arroz. 7. O ponto da corda não pode estar abaixo do gráfico.

III. Conjuntos e funções convexos 573

A definição acima é bastante rigorosa e pode ser traduzida inequivocamente em linguagem analítica.

Primeiro, a função f(x) deve ter um domínio convexo de definição - um segmento, uma semi-reta ou a reta inteira.

Caso contrário, a epígrafe se dividiria em várias áreas separadas, e o segmento conectando pontos de diferentes áreas passaria pela "zona proibida".

Para descobrir qual condição os valores da função convexa para baixo f(x) devem atender, “selecionamos dois pontos quaisquer M1 и M2 em seu gráfico e desenhamos uma corda M1 M2 (Fig. 7). Deve estar inteiramente na epígrafe, ou seja, qualquer ponto M da corda deve pertencer à epígrafe.

Considere o número l mostrando a proporção em que o ponto M divide a corda:

l = M 2 M .

M2 M1

Este valor está dentro de 0 £ l £ 1. É claro que na mesma proporção a abcissa e a ordenada do ponto M dividem os segmentos è [ó1 , ó2 ]:

õ2 – õ3 =l (õ2 – x1); y2 – y3 =l (y2 – y1);

õ3 =l x1 + (1 –l )õ2 ; y3 =l y1 + (1 –l)y2.

A condição para um ponto pertencer à desigualdade y3 ³ f(õ3 ). E assim a desigualdade pode ser representada em

M overgraph - é assim que y 1 \u003d f (x 1), y 2 \u003d f (õ 2) - this

Se a desigualdade (3) for satisfeita para quaisquer valores de x1 è õ2 , então qualquer acorde está na epígrafe e, mais ainda, qualquer segmento conectando os pontos localizados acima está na epígrafe.

Assim, uma função f(x) definida em um conjunto convexo é convexa para baixo se tiver a seguinte propriedade: para quaisquer dois números x1 × õ2 do domínio da função e qualquer número l do intervalo, a desigualdade (3) vale.

A desigualdade (3) é frequentemente escrita em uma forma "simétrica"

574 Aplicação Matemática

Arroz. 8. Funções: convexa para baixo (a), convexa para cima (b), não tendo sinal permanente protuberâncias (c).

Funções convexas para cima podem ser definidas de forma semelhante: para isso, os sinais de desigualdade (3) e (4) devem ser substituídos por outros opostos.

As funções que são convexas para baixo são muitas vezes referidas simplesmente como "convexas". As funções convexas têm uma propriedade mais geral do que a desigualdade (4). Se x1 , õ2 ,..., xN são valores arbitrários do argumento l 1 ,l 2 ,...,

lN - números não negativos, cuja soma é igual a um, então

III. Conjuntos e Funções Convexas 575

Se a derivada f¢(x) é diferenciável (ou seja, a função convexa f(x) é duas vezes diferenciável), então f¢¢(x) ³ 0. Para funções duas vezes diferenciáveis, essa desigualdade acaba sendo equivalente à definição acima de uma função convexa; em cursos analise matemática a convexidade é geralmente determinada pelo sinal da segunda derivada. Mas em aplicações econômicas, onde muitas vezes temos que lidar com funções cujos gráficos têm quebras, tal definição é de pouca utilidade.

Se f(x) e g(x) são funções convexas e a ³ 0, então as funções

a) f(x) + g(x);

c) max(f(x), g(x)).

A convexidade das funções em a) eb) é verificada diretamente usando a desigualdade (3) ou (4). A função c) para cada x assume um valor igual ao maior dos valores de f(x) e g(x) (e qualquer um deles se forem iguais). A epígrafe da função max(f(x), g(x)) é a interseção das epígrafes das funções f(x) eg(x) (confira!) - daí a convexidade da função c).

Exercício 4

Existem funções convexas para baixo e convexas para cima ao mesmo tempo?

Exercício 5

Como fica o gráfico da função f(x) = max (0, a + bx) para diferentes valores dos parâmetros a e b? Essas funções são convexas?

Exercício 6

A função é convexa

Arroz. 10. Gráficos de funções f(x) (1), g(x)

N (2) è max(f(x), g(x)) (3). f(x) = å fi (x),

fi(x) = max(0, ai + bi x)?

Como é a agenda dela?

576 Aplicação Matemática

Para quais valores de a e b essa função

Curvado para baixo?

Curvado para cima?

- não tem um sinal convexo permanente?

4. O espaço das bênçãos

Conceitos Básicos

Muitos questões teóricas são discutidos em nosso livro para o caso de dois produtos. Como uma ferramenta conveniente que simplifica muito sua análise, usamos construções gráficas, nas quais um conjunto incluindo dois produtos nas quantidades x1, и x2 foi representado por um ponto em um plano com Coordenadas cartesianas(x1, x2). Tradução conceitos teóricos em linguagem geométrica tornou as propriedades dos fenômenos em discussão muito claras e ao mesmo tempo não levou a uma perda de rigor: todos os conceitos geométricos (retas, curvas, ângulos de inclinação, etc.) , derivadas, relações entre parâmetros, etc. Portanto, tais construções são amplamente utilizadas tanto em livros didáticos de economia quanto em publicações científicas.

No entanto, esse raciocínio geométrico foi rigoroso e preciso apenas para os casos em que a lista de bens consumidos incluía apenas dois itens. Na realidade, o número de benefícios que as pessoas utilizam é ​​muito maior. As conclusões a que se chega geometricamente podem ser consideradas como tendo generalidade suficiente se puderem ser estendidas aos casos de um número arbitrário de bens.