Ponto de colarinho

Em matemática , um ponto de sela (em inglês : pontos de sela ) de uma função $f$ definida em um produto cartesiano $X \times Y$ de dois conjuntos $X$ e $Y$ é um ponto tal que: ${\ displaystyle ({\ bar {x}}, {\ bar {y}}) \ em X \ vezes Y}$

${\ displaystyle y \ mapsto f ({\ bar {x}}, y)}$ atinge um máximo em em $Y$ ; ${\ bar {y}}$
e atingiu um mínimo de $X$ . ${\ displaystyle x \ mapsto f (x, {\ bar {y}})}$ ${\ bar {x}}$

Alguns autores invertem o máximo e o mínimo ( tem um mínimo em e tem um máximo em ), mas isso não modifica qualitativamente os resultados (podemos voltar ao caso presente alterando as variáveis). ${\ displaystyle f ({\ bar {x}}, \ cdot)}$ ${\ bar {y}}$ ${\ displaystyle f (\ cdot, {\ bar {y}})}$ ${\ bar {x}}$

O termo ponto de sela refere - se à forma de uma sela de cavalo que o gráfico da função assume quando $X$ e $Y$ são intervalos de . Também usamos o nome ponto col , portanto, nos referindo à imagem da passagem na montanha. $\ mathbb {R}$

A noção de ponto de sela entra em jogo:

na otimização , como um conceito que permite enunciar condições que garantem a existência de uma solução primal-dual;
na teoria dos jogos ;
para determinar soluções particulares de certas equações que não são mínimos ou máximos de energia funcional.

Definição

Aqui está uma definição bastante geral da noção de ponto de sela de uma função definida em um produto cartesiano de conjuntos. Nenhuma estrutura é necessária nesses conjuntos. A função deve, por outro lado, assumir seus valores no conjunto de reais (ou mais geralmente na linha real completa ). $\ mathbb {R}$ ${\ bar {\ mathbb {R}}}$

Ponto de sela - Let $X$ e $Y ser$ dois jogos e uma função que pode tomar os valores . Dizemos que é um ponto de sela de $f$ em $X$ $\times$ $Y$ se ${\ displaystyle f: X \ times Y \ to {\ bar {\ mathbb {R}}}}$ $\ pm \ infty$ ${\ displaystyle ({\ bar {x}}, {\ bar {y}}) \ em X \ vezes Y}$

${\ displaystyle \ forall \, (x, y) \ in X \ times Y: \ qquad f ({\ bar {x}}, y) \ leqslant f ({\ bar {x}}, {\ bar {y }}) \ leqslant f (x, {\ bar {y}}).}$

Nas condições acima, o valor de sela de $f$ é chamado . ${\ displaystyle f ({\ bar {x}}, {\ bar {y}})}$

Em outras palavras, um pico em cerca de $Y$ e atingido um mínimo de $X$ . Nada é necessário além da cruz , então a imagem da sela ou pescoço pode ser enganosa como quando é definida por $f$ $($ $x$ $,$ $y$ $) =$ $x$ $2$ $y$ $2$ (todos os pontos nas ordenadas do eixo são pontos da sela). ${\ displaystyle y \ mapsto f ({\ bar {x}}, y)}$ ${\ bar {y}}$ ${\ displaystyle x \ mapsto f (x, {\ bar {y}})}$ ${\ bar {x}}$ ${\ displaystyle (\ {{\ bar {x}} \} \ times Y) \ xícara (X \ times \ {{\ bar {y}} \})}$ $f: \ mathbb {R} ^ {2} \ to \ mathbb {R}$

Muitas vezes podemos voltar à definição anterior por uma mudança de variável. Por exemplo, o ponto não é um ponto de sela da função , no sentido da definição acima, mas torna-se local após a mudança da variável e . ${\ displaystyle (0,0) \ in \ mathbb {R} ^ {2}}$ ${\ displaystyle (x, y) \ in \ mathbb {R} ^ {2} \ mapsto xy + (x ^ {3} + y ^ {3})}$ ${\ displaystyle {\ tilde {x}} = x + y}$ ${\ displaystyle {\ tilde {y}} = xy}$

Resultado de existência

O resultado de existência de ponto de sela abaixo lembra aquele de Weierstrass sobre a existência de um minimizador de função, mas requer uma convexidade - suposição de concavidade de $f$ . Sem esta última suposição, nenhum ponto de sela garantido, conforme mostrado pelo exemplo da função

${\ displaystyle f (x, y) = x ^ {2} + y ^ {2}, ~~ {\ mbox {on}} ~ [-1,1] \ times [-1,1].}$

Existência de ponto de sela - Suponha que $X$ e $Y$ sejam convexos compactos não vazios de espaços vetoriais de dimensão finita e que

para todo $y \in Y$ , $f (•, y )$ é convexo semicontínuo inferior ,
para todo $x \in X$ , $f ( x , •)$ é côncavo superiormente semicontínuo .

Em seguida, $f$ tem um ponto de sela em $X x Y$ .

Este resultado generaliza a identidade de von Neumann que lida com o caso em que $f$ é bilinear e os conjuntos $X$ e $Y$ são simplexes de dimensão finita.

Propriedades

O seguinte resultado é fundamental na teoria da dualidade na otimização, na qual definimos um problema primordial por

${\ displaystyle (P) \ quad \ inf _ {x \ in X} \, \ sup _ {y \ in Y} \, f (x, y)}$

e o problema duplo associado por

${\ displaystyle (D) \ quad \ sup _ {y \ in Y} \, \ inf _ {x \ in X} \, f (x, y).}$

Então dizemos que não há salto de dualidade se

${\ displaystyle \ sup _ {y \ in Y} \, \ inf _ {x \ in X} \, f (x, y) = \ inf _ {x \ in X} \, \ sup _ {y \ in Y} \, f (x, y),}$

a desigualdade ≤ denominada dualidade fraca sendo sempre garantida.

Caracterização dos pontos de sela - Um par de pontos é um ponto de sela de $f$ em $X$ $\times$ $Y$ se, e somente se, for a solução do problema primordial $($ $P$ $)$ , for a solução do problema dual $($ $D$ $)$ e não houver dualidade pular. ${\ displaystyle ({\ bar {x}}, {\ bar {y}}) \ em X \ vezes Y}$ ${\ bar {x}}$ ${\ bar {y}}$

O conjunto de pontos de sela de uma função tem uma estrutura muito particular, como mostra o seguinte resultado: é um produto cartesiano. Denotamos por $Sol ($ $P$ $)$ o conjunto de soluções do problema primal $($ $P$ $)$ e $Sol ($ $D$ $)$ o conjunto de soluções do problema dual $($ $D$ $)$ . ${\ displaystyle f: X \ times Y \ to {\ bar {\ mathbb {R}}}}$

Produto cartesiano de pontos de sela - suponha que a função tenha um ponto de sela. Então ${\ displaystyle f: X \ times Y \ to {\ bar {\ mathbb {R}}}}$

o conjunto de pontos de sela de $f$ é o produto cartesiano $Sol ( P ) \times Sol ( D )$ ,
a função $f$ assume um valor constante em $Sol ( P ) \times Sol ( D )$ , digamos , ${\ bar {f}}$
temos
${\ displaystyle {\ begin {array} {c} \ operatorname {Sol} (P) = \ bigcap _ {y \ in Y} \ {x \ in X: f (x, y) \ leqslant {\ bar {f }} \} \\\ operatorname {Sol} (D) = \ bigcap _ {x \ in X} \ {y \ in Y: f (x, y) \ geqslant {\ bar {f}} \}. \ fim {array}}}$

Ponto de sela no cálculo diferencial

Uso de Hessian

Para determinar se um ponto crítico de uma função de classe $C 2$ de $n$ variáveis com valores reais $f ( x 1 , ..., x n )$ é um ponto de sela, calculamos a matriz de Hesse neste ponto. Se a forma quadrática definida pelo Hessiano é não degenerada e do tipo $( p , q )$ com $p > 0, q > 0$ (o que, para $n = 2$ , equivale a dizer que o determinante da matriz Hessiana é estritamente negativo), temos um ponto de sela após alterar e agrupar as variáveis (de acordo com o lema de Morse ).

Por exemplo, o gradiente e o Hessian da função $f ( x , y ) = x 2 - y 2$ são escritos

${\ displaystyle \ nabla f (x, y) = {\ begin {pmatrix} 2x \\ - 2y \ end {pmatrix}} \ qquad {\ mbox {and}} \ qquad \ nabla ^ {2} f (x, y) = {\ begin {pmatrix} 2 & 0 \\ 0 & -2 \ end {pmatrix}}.}$

O gradiente é, portanto, zero em $(0; 0)$ (é um ponto crítico) e o Hessiano tem um autovalor estritamente positivo (2) e um autovalor estritamente negativo (-2). Portanto, $(0; 0)$ é um ponto de sela.

Este critério não fornece uma condição necessária : para a função , o ponto $(0; 0)$ é um ponto de sela, mas o Hessiano neste ponto é a matriz nula. Portanto, o Hessian não tem um autovalor estritamente positivo e negativo. ${\ displaystyle (x, y) \ mapsto f (x, y) = x ^ {4} -y ^ {4}}$

Apêndices

Observação

Ver Maurice Sion (1958) e o Teorema 1.1 em Brezis (1973).

Bibliografia

H. Brézis (1973), Maximal Monotonic Operators and semi-groups of contractions in Hilbert spaces . Estudos de Matemática 5. North-Holland, Amsterdam. ( ISBN 978-0-7204-2705-9 ) .
(en) M. Sion (1958), “ On general minimax teoreems ” , Pacific Journal of Mathematics 8, 171-176.