Otimização convexa - Guia rápido

Este curso é útil para os alunos que desejam resolver problemas de otimização não linear que surgem em várias aplicações científicas e de engenharia. Este curso começa com a teoria básica da programação linear e irá introduzir os conceitos de conjuntos e funções convexas e terminologias relacionadas para explicar vários teoremas que são necessários para resolver os problemas de programação não linear. Este curso irá apresentar vários algoritmos que são usados ​​para resolver esses problemas. Esses tipos de problemas surgem em várias aplicações, incluindo aprendizado de máquina, problemas de otimização em engenharia elétrica, etc. Requer que os alunos tenham conhecimento prévio dos conceitos de matemática e cálculo do ensino médio.

Neste curso, os alunos aprenderão a resolver problemas de otimização como $ min f \ left (x \ right) $ sujeito a algumas restrições.

Esses problemas são facilmente resolvidos se a função $ f \ left (x \ right) $ for uma função linear e se as restrições forem lineares. Em seguida, é chamado de problema de programação linear (LPP). Mas se as restrições não forem lineares, será difícil resolver o problema acima. A menos que possamos plotar as funções em um gráfico, tentar analisar a otimização pode ser de uma maneira, mas não podemos plotar uma função se estiver além de três dimensões. Daí surgem as técnicas de programação não linear ou programação convexa para resolver tais problemas. Neste tutorial, vamos nos concentrar em aprender essas técnicas e, ao final, alguns algoritmos para resolver esses problemas. primeiro traremos a noção de conjuntos convexos que é a base dos problemas de programação convexa. Em seguida, com a introdução das funções convexas, apresentaremos alguns teoremas importantes para resolver esses problemas e alguns algoritmos baseados nesses teoremas.

Terminologias

• O espaço $ \ mathbb {R} ^ n $ - É um vetor n-dimensional com números reais, definidos da seguinte forma - $ \ mathbb {R} ^ n = \ left \ {\ left (x_1, x_2, ... , x_n \ right) ^ {\ tau}: x_1, x_2, ...., x_n \ in \ mathbb {R} \ right \} $

• O espaço $ \ mathbb {R} ^ {mXn} $ - É um conjunto de todas as matrizes de valores reais da ordem $ mXn $.

Metodologia

A Programação Linear, também chamada de Otimização Linear, é uma técnica usada para resolver problemas matemáticos nos quais as relações são lineares por natureza. a natureza básica da Programação Linear é maximizar ou minimizar umobjective function com assunto para alguns constraints. A função objetivo é uma função linear obtida a partir do modelo matemático do problema. As restrições são as condições que são impostas ao modelo e também são lineares.

• A partir da pergunta fornecida, encontre a função objetivo.
• encontre as restrições.
• Desenhe as restrições em um gráfico.
• encontre a região viável, que é formada pela interseção de todas as restrições.
• encontre os vértices da região viável.
• encontre o valor da função objetivo nesses vértices.
• O vértice que maximiza ou minimiza a função objetivo (de acordo com a pergunta) é a resposta.

Exemplos

Step 1 - Maximize $ 5x + 3y $ sujeito a

$ x + y \ leq 2 $,

$ 3x + y \ leq 3 $,

$ x \ geq 0 \: and \: y \ geq 0 $

Solution -

O primeiro passo é encontrar a região viável em um gráfico.

Claramente a partir do gráfico, os vértices da região viável são

$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $

Seja $ f \ left (x, y \ right) = 5x + 3y $

Colocando esses valores na função objetivo, obtemos -

$ f \ left (0, 0 \ right) $ = 0

$ f \ left (0, 2 \ right) $ = 6

$ f \ left (1, 0 \ right) $ = 5

$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7

Portanto, a função é maximizada em $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $

Step 2- Uma empresa de relógios produz um relógio digital e um mecânico. As projeções de longo prazo indicam uma demanda esperada de pelo menos 100 relógios digitais e 80 mecânicos por dia. Devido às limitações na capacidade de produção, não mais do que 200 relógios digitais e 170 mecânicos podem ser produzidos diariamente. Para cumprir um contrato de remessa, um total de pelo menos 200 relógios deve ser despachado por dia.

Se cada relógio digital vendido resulta em uma perda de $ \ $ 2 $, mas cada relógio mecânico produz um lucro de $ \ $ 5 $, quantos de cada tipo devem ser feitos diariamente para maximizar o lucro líquido?

Solution -

Seja $ x $ o número de relógios digitais produzidos

$ y $ é o número de relógios mecânicos produzidos

De acordo com a pergunta, pelo menos 100 relógios digitais devem ser feitos diariamente e no máximo 200 relógios digitais podem ser feitos.

$ \ Rightarrow 100 \ leq \: x \ leq 200 $

Da mesma forma, pelo menos 80 relógios mecânicos devem ser feitos diariamente e no máximo 170 relógios mecânicos podem ser feitos.

$ \ Rightarrow 80 \ leq \: y \ leq 170 $

Uma vez que pelo menos 200 relógios devem ser produzidos a cada dia.

$ \ Rightarrow x + y \ leq 200 $

Uma vez que cada relógio digital vendido resulta em uma perda de $ \ $ 2 $, mas cada relógio mecânico produz um lucro de $ \ $ 5 $,

O lucro total pode ser calculado como

$ Lucro = -2x + 5y $

E temos que maximizar o lucro, portanto, a questão pode ser formulada como -

Maximize $ -2x + 5y $ sujeito a

$ 100 \: \ leq x \: \ leq 200 $

$ 80 \: \ leq y \: \ leq 170 $

$ x + y \: \ leq 200 $

Traçando as equações acima em um gráfico, obtemos,

Os vértices da região viável são

$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) e \ left (100, 100 \ right) $

O valor máximo da função objetivo é obtido em $ \ left (100, 170 \ right) $ Assim, para maximizar os lucros líquidos, 100 unidades de relógios digitais e 170 unidades de relógios mecânicos devem ser produzidas.

Uma norma é uma função que fornece um valor estritamente positivo a um vetor ou variável.

A norma é uma função $ f: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $

As características básicas de uma norma são -

Seja $ X $ um vetor tal que $ X \ in \ mathbb {R} ^ n $

• $ \ left \ | x \ right \ | \ geq 0 $

• $ \ left \ | x \ right \ | = 0 \ Leftrightarrow x = 0 \ forall x \ in X $

• $ \ left \ | \ alpha x \ right \ | = \ left | \ alpha \ right | \ left \ | x \ right \ | \ forall \: x \ in X e \: \ alpha \: is \: a \: escalar $

• $ \ left \ | x + y \ right \ | \ leq \ left \ | x \ right \ | + \ left \ | y \ right \ | \ forall x, y \ in X $

• $ \ left \ | xy \ right \ | \ geq \ left \ | \ left \ | x \ right \ | - \ left \ | y \ right \ | \ right \ | $

Por definição, a norma é calculada da seguinte forma -

• $ \ left \ | x \ right \ | _1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ left | x_i \ right | $

• $ \ left \ | x \ right \ | _2 = \ left (\ displaystyle \ sum \ limits_ {i = 1} ^ n \ left | x_i \ right | ^ 2 \ right) ^ {\ frac {1} {2}} $

• $ \ left \ | x \ right \ | _p = \ left (\ displaystyle \ sum \ limits_ {i = 1} ^ n \ left | x_i \ right | ^ p \ right) ^ {\ frac {1} {p}}, 1 \ leq p \ leq \ infty $

A norma é uma função contínua.

Prova

Por definição, se $ x_n \ rightarrow x $ em $ X \ Rightarrow f \ left (x_n \ right) \ rightarrow f \ left (x \ right) $ então $ f \ left (x \ right) $ é uma função constante.

Seja $ f \ left (x \ right) = \ left \ | x \ right \ | $

Portanto, $ \ left | f \ left (x_n \ right) -f \ left (x \ right) \ right | = \ left | \ left \ | x_n \ right \ | - \ left \ | x \ right \ | \ right | \ leq \ left | \ left | x_n-x \ right | \: \ right | $

Como $ x_n \ rightarrow x $, portanto, $ \ left \ | x_n-x \ right \ | \ rightarrow 0 $

Portanto $ \ left | f \ left (x_n \ right) -f \ left (x \ right) \ right | \ leq 0 \ Rightarrow \ left | f \ left (x_n \ right) -f \ left (x \ right) \ right | = 0 \ Rightarrow f \ left (x_n \ right) \ rightarrow f \ left (x \ right) $

Conseqüentemente, a norma é uma função contínua.

Produto interno é uma função que fornece um escalar para um par de vetores.

Produto interno - $ f: \ mathbb {R} ^ n \ times \ mathbb {R} ^ n \ rightarrow \ kappa $ onde $ \ kappa $ é um escalar.

As características básicas do produto interno são as seguintes -

Seja $ X \ in \ mathbb {R} ^ n $

• $ \ left \ langle x, x \ right \ rangle \ geq 0, \ forall x \ in X $

• $ \ left \ langle x, x \ right \ rangle = 0 \ Leftrightarrow x = 0, \ forall x \ in X $

• $ \ left \ langle \ alpha x, y \ right \ rangle = \ alpha \ left \ langle x, y \ right \ rangle, \ forall \ alpha \ in \ kappa \: e \: \ forall x, y \ in X $

• $ \ left \ langle x + y, z \ right \ rangle = \ left \ langle x, z \ right \ rangle + \ left \ langle y, z \ right \ rangle, \ forall x, y, z \ in X $

• $ \ left \ langle \ overline {y, x} \ right \ rangle = \ left (x, y \ right), \ forall x, y \ in X $

Note -

• Relação entre norma e produto interno: $ \ left \ | x \ right \ | = \ sqrt {\ left (x, x \ right)} $

• $ \ forall x, y \ in \ mathbb {R} ^ n, \ left \ langle x, y \ right \ rangle = x_1y_1 + x_2y_2 + ... + x_ny_n $

Exemplos

1. encontre o produto interno de $ x = \ left (1,2,1 \ right) \: e \: y = \ left (3, -1,3 \ right) $

Solução

$ \ left \ langle x, y \ right \ rangle = x_1y_1 + x_2y_2 + x_3y_3 $

$ \ left \ langle x, y \ right \ rangle = \ left (1 \ times3 \ right) + \ left (2 \ times-1 \ right) + \ left (1 \ times3 \ right) $

$ \ left \ langle x, y \ right \ rangle = 3 + \ left (-2 \ right) + 3 $

$ \ left \ langle x, y \ right \ rangle = 4 $

2. Se $ x = \ left (4,9,1 \ right), y = \ left (-3,5,1 \ right) $ e $ z = \ left (2,4,1 \ right) $, encontre $ \ left (x + y, z \ right) $

Solução

Como sabemos, $ \ left \ langle x + y, z \ right \ rangle = \ left \ langle x, z \ right \ rangle + \ left \ langle y, z \ right \ rangle $

$ \ left \ langle x + y, z \ right \ rangle = \ left (x_1z_1 + x_2z_2 + x_3z_3 \ right) + \ left (y_1z_1 + y_2z_2 + y_3z_3 \ right) $

$ \ left \ langle x + y, z \ right \ rangle = \ left \ {\ left (4 \ times 2 \ right) + \ left (9 \ times 4 \ right) + \ left (1 \ times1 \ right) \ right \} + $

$ \ left \ {\ left (-3 \ times2 \ right) + \ left (5 \ times4 \ right) + \ left (1 \ vezes 1 \ right) \ right \} $

$ \ left \ langle x + y, z \ right \ rangle = \ left (8 + 36 + 1 \ right) + \ left (-6 + 20 + 1 \ right) $

$ \ left \ langle x + y, z \ right \ rangle = 45 + 15 $

$ \ left \ langle x + y, z \ right \ rangle = 60 $

Mínimo local ou minimizar

$ \ bar {x} \ in \: S $ é considerado mínimo local de uma função $ f $ if $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ bar {x} \ right) $ onde $ N_ \ varepsilon \ left (\ bar {x} \ right) $ significa vizinhança de $ \ bar {x} $, ou seja, $ N_ \ varejpsilon \ left (\ bar {x} \ right) $ significa $ \ left \ | x- \ bar {x} \ right \ | <\ varepsilon $

Maxima local ou maximizador

$ \ bar {x} \ in \: S $ é considerado máximo local de uma função $ f $ if $ f \ left (\ bar {x} \ right) \ geq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ bar {x} \ right) $ onde $ N_ \ varepsilon \ left (\ bar {x} \ right) $ significa vizinhança de $ \ bar {x} $, ou seja, $ N_ \ varejpsilon \ left (\ bar {x} \ right) $ significa $ \ left \ | x- \ bar {x} \ right \ | <\ varepsilon $

Mínimos globais

$ \ bar {x} \ in \: S $ são os mínimos globais de uma função $ f $ if $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in S $

Maxima global

$ \ bar {x} \ in \: S $ é considerado o máximo global de uma função $ f $ if $ f \ left (\ bar {x} \ right) \ geq f \ left (x \ right), \ forall x \ in S $

Exemplos

Step 1- encontre os mínimos e máximos locais de $ f \ left (\ bar {x} \ right) = \ left | x ^ 2-4 \ right | $

Solution -

A partir do gráfico da função acima, é claro que os mínimos locais ocorrem em $ x = \ pm 2 $ e os máximos locais em $ x = 0 $

Step 2- encontre os mínimos globais da função $ f \ left (x \ right) = \ left | 4x ^ 3-3x ^ 2 + 7 \ right | $

Solution -

A partir do gráfico da função acima, é claro que os mínimos globais ocorrem em $ x = -1 $.

Seja $ S \ subseteq \ mathbb {R} ^ n $ Um conjunto S é considerado convexo se o segmento de linha que une quaisquer dois pontos do conjunto S também pertence ao S, ou seja, se $ x_1, x_2 \ in S $ , então $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ onde $ \ lambda \ in \ left (0,1 \ right) $.

Note -

• A união de dois conjuntos convexos pode ou não ser convexa.
• A intersecção de dois conjuntos convexos é sempre convexa.

Proof

Sejam $ S_1 $ e $ S_2 $ dois conjuntos convexos.

Deixe $ S_3 = S_1 \ cap S_2 $

Deixe $ x_1, x_2 \ em S_3 $

Como $ S_3 = S_1 \ cap S_2 $, portanto, $ x_1, x_2 \ em S_1 $ e $ x_1, x_2 \ em S_2 $

Uma vez que $ S_i $ é um conjunto convexo, $ \ forall $ $ i \ in 1,2, $

Assim, $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ onde $ \ lambda \ in \ left (0,1 \ right) $

Portanto, $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_1 \ cap S_2 $

$ \ Rightarrow \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ em S_3 $

Portanto, $ S_3 $ é um conjunto convexo.

• Média ponderada da forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, onde $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ e $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ é chamado de combinação cônica de $ x_1, x_2, .... x_k. $

• Média ponderada da forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, onde $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ é chamada de combinação afim de $ x_1 , x_2, .... x_k. $

• A média ponderada da forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ é chamada de combinação linear de $ x_1, x_2, .... x_k. $

Exemplos

Step 1 - Prove que o conjunto $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ é um conjunto convexo.

Solução

Deixe $ x_1 $ e $ x_2 \ em S $

$ \ Rightarrow Cx_1 \ leq \ alpha $ and $ \: and \: Cx_2 \ leq \ alpha $

Para mostrar: $ \: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ direita) $

$ Cy = C \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = \ lambda Cx_1 + \ left (1- \ lambda \ right) Cx_2 $

$ \ Rightarrow Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha $

$ \ Rightarrow Cy \ leq \ alpha $

$ \ Rightarrow y \ in S $

Portanto, $ S $ é um conjunto convexo.

Step 2 - Prove que o conjunto $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ é um convexo conjunto.

Solução

Seja $ x, y \ em S $

Seja $ x = \ left (x_1, x_2 \ right) $ e $ y = \ left (y_1, y_2 \ right) $

$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ e $ y_ {1} ^ {2} \ leq 8y_2 $

Para mostrar - $ \ lambda x + \ left (1- \ lambda \ right) y \ in S \ Rightarrow \ lambda \ left (x_1, x_2 \ right) + \ left (1- \ lambda \ right) \ left (y_1, y_2 \ right) \ in S \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda) y_2] \ in S \ right) \ right] $

$ Agora, \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} = \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) x_1y_1 $

Mas $ 2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2} $

Portanto,

$ \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) \ left (x_ {1} ^ {2} + y_ {1} ^ {2} \ right) $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda x_ {1} ^ {2} + \ left (1- \ lambda \ right) y_ {1} ^ {2} $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ lambda x_2 + 8 \ left (1- \ lambda \ right) y_2 $

$ \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ left [\ lambda x_2 + \ left (1- \ lambda \ right) y_2 \ right] $

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) y \ em S $

Step 3 - Mostre que um conjunto $ S \ in \ mathbb {R} ^ n $ é convexo se e somente se para cada inteiro k, toda combinação convexa de quaisquer k pontos de $ S $ está em $ S $.

Solução

Seja $ S $ um conjunto convexo. então, para mostrar;

$ c_1x_1 + c_2x_2 + ..... + c_kx_k \ in S, \ displaystyle \ sum \ limits_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ...., k $

Prova por indução

Para $ k = 1, x_1 \ em S, c_1 = 1 \ Rightarrow c_1x_1 \ em S $

Para $ k = 2, x_1, x_2 \ em S, c_1 + c_2 = 1 $ e Visto que S é um conjunto convexo

$ \ Rightarrow c_1x_1 + c_2x_2 \ in S. $

Deixe a combinação convexa de m pontos de S em S, isto é,

$ c_1x_1 + c_2x_2 + ... + c_mx_m \ in S, \ displaystyle \ sum \ limits_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ..., m $

Agora, vamos $ x_1, x_2 ...., x_m, x_ {m + 1} \ em S $

Seja $ x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1} $

Deixe $ x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) \ frac {\ mu_1x_1 + \ mu_2x_2 + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} + \ mu_ {m + 1} x_ {m + 1} $

Seja $ y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} $

$ \ Rightarrow x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) y + \ mu_ {m + 1} x_ {m + 1} $

Agora $ y \ em S $ porque a soma dos coeficientes é 1.

$ \ Rightarrow x \ in S $ visto que S é um conjunto convexo e $ y, x_ {m + 1} \ in S $

Daí provado por indução.

Um conjunto $ A $ é considerado um conjunto afim se, para quaisquer dois pontos distintos, a linha que passa por esses pontos estiver no conjunto $ A $.

Note -

• $ S $ é um conjunto afim se, e somente se, contiver todas as combinações afins de seus pontos.

• Conjuntos vazios e singleton são conjuntos afins e convexos.

  Por exemplo, a solução de uma equação linear é um conjunto afim.

Prova

Seja S a solução de uma equação linear.

Por definição, $ S = \ left \ {x \ in \ mathbb {R} ^ n: Ax = b \ right \} $

Seja $ x_1, x_2 \ in S \ Rightarrow Ax_1 = b $ e $ Ax_2 = b $

Para provar: $ A \ left [\ theta x_1 + \ left (1- \ theta \ right) x_2 \ right] = b, \ forall \ theta \ in \ left (0,1 \ right) $

$ A \ left [\ theta x_1 + \ left (1- \ theta \ right) x_2 \ right] = \ theta Ax_1 + \ left (1- \ theta \ right) Ax_2 = \ theta b + \ left (1- \ theta \ right ) b = b $

Portanto, S é um conjunto afim.

Teorema

Se $ C $ é um conjunto afim e $ x_0 \ em C $, então o conjunto $ V = C-x_0 = \ left \ {x-x_0: x \ in C \ right \} $ é um subespaço de C.

Prova

Deixe $ x_1, x_2 \ em V $

Para mostrar: $ \ alpha x_1 + \ beta x_2 \ em V $ para algum $ \ alpha, \ beta $

Agora, $ x_1 + x_0 \ em C $ e $ x_2 + x_0 \ em C $ por definição de V

Agora, $ \ alpha x_1 + \ beta x_2 + x_0 = \ alpha \ left (x_1 + x_0 \ right) + \ beta \ left (x_2 + x_0 \ right) + \ left (1- \ alpha - \ beta \ right) x_0 $

Mas $ \ alpha \ left (x_1 + x_0 \ right) + \ beta \ left (x_2 + x_0 \ right) + \ left (1- \ alpha - \ beta \ right) x_0 \ em C $ porque C é um conjunto afim .

Portanto, $ \ alpha x_1 + \ beta x_2 \ in V $

Conseqüentemente provado.

O envoltório convexo de um conjunto de pontos em S é o limite da menor região convexa que contém todos os pontos de S dentro dele ou em seu limite.

OU

Seja $ S \ subseteq \ mathbb {R} ^ n $ O casco convexo de S, denotado $ Co \ left (S \ right) $ por é a coleção de todas as combinações convexas de S, ou seja, $ x \ in Co \ left (S \ direita) $ se e somente se $ x \ in \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $, onde $ \ displaystyle \ sum \ limits_ {1} ^ n \ lambda_i = 1 $ e $ \ lambda_i \ geq 0 \ forall x_i \ in S $

Remark - O casco dos conves de um conjunto de pontos em S no plano define um polígono convexo e os pontos de S na fronteira do polígono definem os vértices do polígono.

Theorem $ Co \ left (S \ right) = \ left \ {x: x = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i, x_i \ in S, \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 \ right \} $ Mostre que um casco convexo é um conjunto convexo.

Prova

Seja $ x_1, x_2 \ in Co \ left (S \ right) $, então $ x_1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $ e $ x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ \ gamma x_i $ onde $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ e $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Para $ \ theta \ in \ left (0,1 \ right), \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ theta \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_ix_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i \ theta x_i + \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i \ esquerda (1- \ theta \ right) x_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ esquerdo [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ direita] x_i $

Considerando os coeficientes,

$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ right] = \ theta \ displaystyle \ sum \ limits_ {i = 1 } ^ n \ lambda_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limits_ {i = 1} ^ n \ gamma_i = \ theta + \ left (1- \ theta \ right) = 1 $

Portanto, $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

Assim, um casco convexo é um conjunto convexo.

Seja S um conjunto arbitrário em $ \ mathbb {R} ^ n $ .Se $ x \ em Co \ left (S \ right) $, então $ x \ em Co \ left (x_1, x_2, ...., x_n, x_ {n + 1} \ direita) $.

Prova

Como $ x \ em Co \ left (S \ right) $, então $ x $ é representado por uma combinação convexa de um número finito de pontos em S, ou seja,

$ x = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ lambda_jx_j, \ displaystyle \ sum \ limits_ {j = 1} ^ k \ lambda_j = 1, \ lambda_j \ geq 0 $ e $ x_j \ in S, \ forall j \ in \ left (1, k \ right) $

Se $ k \ leq n + 1 $, o resultado obtido é obviamente verdadeiro.

Se $ k \ geq n + 1 $, então $ \ left (x_2-x_1 \ right) \ left (x_3-x_1 \ right), ....., \ left (x_k-x_1 \ right) $ são linearmente dependentes .

$ \ Rightarrow \ existe \ mu _j \ in \ mathbb {R}, 2 \ leq j \ leq k $ (nem todos zero) de modo que $ \ displaystyle \ sum \ limits_ {j = 2} ^ k \ mu _j \ left (x_j-x_1 \ direita) = 0 $

Defina $ \ mu_1 = - \ displaystyle \ sum \ limits_ {j = 2} ^ k \ mu _j $, então $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ mu_j x_j = 0, \ displaystyle \ sum \ limites_ {j = 1} ^ k \ mu_j = 0 $

onde nem todos $ \ mu_j's $ são iguais a zero. Já que $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ mu_j = 0 $, pelo menos um dos $ \ mu_j> 0,1 \ leq j \ leq k $

Então, $ x = \ displaystyle \ sum \ limits_ {1} ^ k \ lambda_j x_j + 0 $

$ x = \ displaystyle \ sum \ limits_ {1} ^ k \ lambda_j x_j- \ alpha \ displaystyle \ sum \ limits_ {1} ^ k \ mu_j x_j $

$ x = \ displaystyle \ sum \ limits_ {1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) x_j $

Escolha $ \ alpha $ de forma que $ \ alpha = min \ left \ {\ frac {\ lambda_j} {\ mu_j}, \ mu_j \ geq 0 \ right \} = \ frac {\ lambda_j} {\ mu _j}, $ para algum $ i = 1,2, ..., k $

Se $ \ mu_j \ leq 0, \ lambda_j- \ alpha \ mu_j \ geq 0 $

Se $ \ mu_j> 0, então \: \ frac {\ lambda _j} {\ mu_j} \ geq \ frac {\ lambda_i} {\ mu _i} = \ alpha \ Rightarrow \ lambda_j- \ alpha \ mu_j \ geq 0, j = 1,2, ... k $

Em particular, $ \ lambda_i- \ alpha \ mu_i = 0 $, por definição de $ \ alpha $

$ x = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) x_j $, onde

$ \ lambda_j- \ alpha \ mu_j \ geq0 $ e $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) = 1 $ e $ \ lambda_i- \ alpha \ mu_i = 0 $

Assim, x pode ser representado como uma combinação convexa de no máximo (k-1) pontos.

Este processo de redução pode ser repetido até que x seja representado como uma combinação convexa de (n + 1) elementos.

Seja S um conjunto não vazio, fechado e limitado (também chamado de conjunto compacto) em $ \ mathbb {R} ^ n $ e seja $ f: S \ rightarrow \ mathbb {R} $ uma função contínua em S, então o problema min $ \ left \ {f \ left (x \ right): x \ in S \ right \} $ atinge seu mínimo.

Prova

Como S não é vazio e é limitado, existe um limite inferior.

$ \ alpha = Inf \ left \ {f \ left (x \ right): x \ in S \ right \} $

Agora vamos $ S_j = \ left \ {x \ in S: \ alpha \ leq f \ left (x \ right) \ leq \ alpha + \ delta ^ j \ right \} \ forall j = 1,2, ... $ e $ \ delta \ in \ left (0,1 \ right) $

Pela definição de infimium, $ S_j $ não é vazio, para cada $ j $.

Escolha algum $ x_j \ em S_j $ para obter uma sequência $ \ left \ {x_j \ right \} $ para $ j = 1,2, ... $

Visto que S é limitado, a sequência também é limitada e existe uma subsequência convergente $ \ left \ {y_j \ right \} $, que converge para $ \ hat {x} $. Logo, $ \ hat {x} $ é um ponto limite e S é fechado, portanto $ \ hat {x} \ in S $. Como f é contínuo, $ f \ left (y_i \ right) \ rightarrow f \ left (\ hat {x} \ right) $.

Como $ \ alpha \ leq f \ left (y_i \ right) \ leq \ alpha + \ delta ^ k, \ alpha = \ displaystyle \ lim_ {k \ rightarrow \ infty} f \ left (y_i \ right) = f \ left ( \ hat {x} \ right) $

Assim, $ \ hat {x} $ é a solução de minimização.

Observações

Existem duas condições necessárias importantes para o Teorema de Weierstrass se sustentar. Estes são os seguintes -

• Step 1 - O conjunto S deve ser um conjunto limitado.

  Considere a função f \ left (x \ right) = x $.

  É um conjunto ilimitado e tem um mínimo em qualquer ponto de seu domínio.

  Assim, para que os mínimos sejam obtidos, S deve ser limitado.

• Step 2 - O conjunto S deve ser fechado.

  Considere a função $ f \ left (x \ right) = \ frac {1} {x} $ no domínio \ left (0,1 \ right).

  Esta função não é fechada no domínio dado e seus mínimos também não existem.

  Portanto, para que os mínimos sejam obtidos, S deve ser fechado.

Seja S um convexo fechado não vazio definido em $ \ mathbb {R} ^ n $ e seja $ y \ notin S $, então $ \ existe $ um ponto $ \ bar {x} \ em S $ com distância mínima de y, ou seja, $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ in S. $

Além disso, $ \ bar {x} $ é um ponto de minimização se e somente se $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ ou $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Prova

Existência do ponto mais próximo

Já que $ S \ ne \ phi, \ existe $ a ponto $ \ hat {x} \ em S $ tal que a distância mínima de S de y é menor ou igual a $ \ left \ | y- \ hat {x} \ right \ | $.

Defina $ \ hat {S} = S \ cap \ left \ {x: \ left \ | yx \ right \ | \ leq \ left \ | y- \ hat {x} \ right \ | \ right \} $

Como $ \ hat {S} $ é fechado e limitado, e como norma é uma função contínua, então pelo teorema de Weierstrass, existe um ponto mínimo $ \ hat {x} \ em S $ tal que $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Singularidade

Suponha $ \ bar {x} \ em S $ tal que $ \ left \ | y- \ hat {x} \ right \ | = \ left \ | y- \ hat {x} \ right \ | = \ alpha $

Como S é convexo, $ \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Mas, $ \ left \ | y- \ frac {\ hat {x} - \ bar {x}} {2} \ right \ | \ leq \ frac {1} {2} \ left \ | y- \ hat {x} \ right \ | + \ frac {1} {2} \ left \ | y- \ bar {x} \ right \ | = \ alpha $

Não pode ser desigualdade estrita porque $ \ hat {x} $ é o mais próximo de y.

Portanto, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, por algum $ \ mu $

Agora $ \ left \ | \ mu \ right \ | = 1. $ Se $ \ mu = -1 $, então $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Rightarrow y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Mas $ y \ em S $. Daí a contradição. Assim, $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Assim, minimizar o ponto é único.

Para a segunda parte da prova, assuma $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ para todos $ x \ em S $

Agora,

$ \ left \ | yx \ right \ | ^ {2} = \ left \ | y- \ hat {x} + \ hat {x} -x \ right \ | ^ {2} = \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ left \ | \ hat {x} -x \ right \ | ^ {2} +2 \ left (\ hat {x} -x \ right) ^ {\ tau} \ left (y- \ hat {x} \ right) $

$ \ Rightarrow \ left \ | yx \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ {2} $ porque $ \ left \ | \ hat {x} -x \ right \ | ^ {2} \ geq 0 $ e $ \ left (\ hat {x} - x \ right) ^ {T} \ left (y- \ hat {x} \ right ) \ geq 0 $

Assim, $ \ hat {x} $ é o ponto de minimização.

Por outro lado, assuma que $ \ hat {x} $ é um ponto de minimização.

$ \ Rightarrow \ left \ | yx \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ 2 \ forall x \ in S $

Uma vez que S é conjunto convexo.

$ \ Rightarrow \ lambda x + \ left (1- \ lambda \ right) \ hat {x} = \ hat {x} + \ lambda \ left (x- \ hat {x} \ right) \ in S $ para $ x \ in S $ e $ \ lambda \ in \ left (0,1 \ right) $

Agora, $ \ left \ | y- \ hat {x} - \ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} \ geq \ left \ | y- \ hat {x} \ right \ | ^ 2 $

E

$ \ left \ | y- \ hat {x} - \ lambda \ left (x- \ hat {x} \ right) \ right \ | ^ {2} = \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ lambda ^ 2 \ left \ | x- \ hat {x} \ right \ | ^ {2} -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) $

$ \ Rightarrow \ left \ | y- \ hat {x} \ right \ | ^ {2} + \ lambda ^ {2} \ left \ | x- \ hat {x} \ right \ | -2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ geq \ left \ | y- \ hat {x} \ right \ | ^ {2} $

$ \ Rightarrow 2 \ lambda \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq \ lambda ^ 2 \ left \ | x- \ hat {x} \ right \ | ^ 2 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $

Daí provado.

Seja S um conjunto convexo fechado não vazio em $ \ mathbb {R} ^ n $ e $ y \ notin S $. Então, existe um vetor diferente de zero $ p $ e escalar $ \ beta $ tal que $ p ^ T y> \ beta $ e $ p ^ T x <\ beta $ para cada $ x \ em S $

Prova

Uma vez que S é um conjunto convexo fechado não vazio e $ y \ notin S $, portanto, pelo teorema do ponto mais próximo, existe um único ponto de minimização $ \ hat {x} \ em S $ tal que

$ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 \ forall x \ in S $

Seja $ p = \ left (y- \ hat {x} \ right) \ neq 0 $ e $ \ beta = \ hat {x} ^ T \ left (y- \ hat {x} \ right) = p ^ T \ hat {x} $.

Então $ \ left (x- \ hat {x} \ right) ^ T \ left (y- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ T \ left (x- \ hat {x} \ right) \ leq 0 $

$ \ Rightarrow \ left (y- \ hat {x} \ right) ^ Tx \ leq \ left (y- \ hat {x} \ right) ^ T \ hat {x} = \ hat {x} ^ T \ left (y- \ hat {x} \ right) $ i, e., $ p ^ Tx \ leq \ beta $

Além disso, $ p ^ Ty- \ beta = \ left (y- \ hat {x} \ right) ^ Ty- \ hat {x} ^ T \ left (y- \ hat {x} \ right) $

$ = \ left (y- \ hat {x} \ right) ^ T \ left (yx \ right) = \ left \ | y- \ hat {x} \ right \ | ^ {2}> 0 $

$ \ Rightarrow p ^ Ty> \ beta $

Este teorema resulta na separação de hiperplanos. Os hiperplanos baseados no teorema acima podem ser definidos da seguinte forma -

Sejam $ S_1 $ e $ S_2 $ subconjuntos não vazios de $ \ mathbb {R} $ e $ H = \ left \ {X: A ^ TX = b \ right \} $ um hiperplano.

• Diz-se que o hiperplano H separa $ S_1 $ e $ S_2 $ se $ A ^ TX \ leq b \ forall X \ in S_1 $ e $ A_TX \ geq b \ forall X \ in S_2 $

• Diz-se que o hiperplano H separa estritamente $ S_1 $ e $ S_2 $ se $ A ^ TX <b \ forall X \ in S_1 $ e $ A_TX> b \ forall X \ in S_2 $

• Diz-se que o hiperplano H separa fortemente $ S_1 $ e $ S_2 $ se $ A ^ TX \ leq b \ forall X \ in S_1 $ e $ A_TX \ geq b + \ varejpsilon \ forall X \ in S_2 $, onde $ \ varejpsilon $ é um escalar positivo.

Um conjunto não vazio C em $ \ mathbb {R} ^ n $ é considerado cone com vértice 0 se $ x \ em C \ Rightarrow \ lambda x \ in C \ forall \ lambda \ geq 0 $.

Um conjunto C é um cone convexo se for convexo e também um cone.

Por exemplo, $ y = \ left | x \ right | $ não é um cone convexo porque não é convexo.

Mas, $ y \ geq \ left | x \ right | $ é um cone convexo porque ele também é convexo.

Note - Um cone C é convexo se e somente se para qualquer $ x, y \ em C, x + y \ em C $.

Prova

Como C é cone, para $ x, y \ em C \ Rightarrow \ lambda x \ em C $ e $ \ mu y \ em C \: \ forall \: \ lambda, \ mu \ geq 0 $

C é convexo se $ \ lambda x + \ left (1- \ lambda \ right) y \ in C \: \ forall \: \ lambda \ in \ left (0, 1 \ right) $

Como C é cone, $ \ lambda x \ em C $ e $ \ left (1- \ lambda \ right) y \ em C \ Leftrightarrow x, y \ em C $

Assim, C é convexo se $ x + y \ em C $

Em geral, se $ x_1, x_2 \ em C $, então, $ \ lambda_1x_1 + \ lambda_2x_2 \ em C, \ forall \ lambda_1, \ lambda_2 \ geq 0 $

Exemplos

• A combinação cônica do conjunto infinito de vetores em $ \ mathbb {R} ^ n $ é um cone convexo.

• Qualquer conjunto vazio é um cone convexo.

• Qualquer função linear é um cone convexo.

• Como um hiperplano é linear, ele também é um cone convexo.

• Meios espaços fechados também são cones convexos.

Note - A intersecção de dois cones convexos é um cone convexo, mas sua união pode ou não ser um cone convexo.

Seja S um conjunto não vazio em $ \ mathbb {R} ^ n $ Então, o cone polar de S denotado por $ S ^ * $ é dado por $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Observação

• O cone polar é sempre convexo, mesmo que S não seja convexo.

• Se S for um conjunto vazio, $ S ^ * = \ mathbb {R} ^ n $.

• A polaridade pode ser vista como uma generalização da ortogonalidade.

Seja $ C \ subseteq \ mathbb {R} ^ n $ então o espaço ortogonal de C, denotado por $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Lema

Sejam $ S, S_1 $ e $ S_2 $ conjuntos não vazios em $ \ mathbb {R} ^ n $, então as seguintes afirmações são verdadeiras -

• $ S ^ * $ é um cone convexo fechado.

• $ S \ subseteq S ^ {**} $ onde $ S ^ {**} $ é um cone polar de $ S ^ * $.

• $ S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*} $.

Prova

Step 1 - $ S ^ * = \ left \ {p \ in \ mathbb {R} ^ n, p ^ Tx \ leq 0 \: \ forall \: x \ in S \ right \} $

• Seja $ x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $ e $ x_ {2} ^ {T} x \ leq 0, \ forall x \ in S $

  Para $ \ lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ right ) ^ T + \ left \ {\ left (1- \ lambda \ right) x_ {2} \ right \} ^ {T} \ right] x, \ forall x \ in S $

  $ = \ left [\ lambda x_ {1} ^ {T} + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ leq 0 $

  Assim, $ \ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \ in S ^ * $

  Portanto, $ S ^ * $ é um conjunto convexo.

• Para $ \ lambda \ geq 0, p ^ {T} x \ leq 0, \ forall \: x \ in S $

  Portanto, $ \ lambda p ^ T x \ leq 0, $

  $ \ Rightarrow \ left (\ lambda p \ right) ^ T x \ leq 0 $

  $ \ Rightarrow \ lambda p \ in S ^ * $

  Portanto, $ S ^ * $ é um cone.

• Para mostrar $ S ^ * $ está fechado, ou seja, para mostrar se $ p_n \ rightarrow p $ como $ n \ rightarrow \ infty $, então $ p \ in S ^ * $

  $ \ forall x \ in S, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ right) ^ T x $

  As $ p_n \ rightarrow p $ as $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

  Portanto, $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $. Mas $ p_ {n} ^ {T} x \ leq 0, \: \ forall x \ in S $

  Assim, $ p ^ Tx \ leq 0, \ forall x \ in S $

  $ \ Rightarrow p \ in S ^ * $

  Portanto, $ S ^ * $ está fechado.

Step 2 - $ S ^ {**} = \ left \ {q \ in \ mathbb {R} ^ n: q ^ T p \ leq 0, \ forall p \ in S ^ * \ right \} $

Seja $ x \ em S $, então $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Assim, $ S \ subseteq S ^ {**} $

Step 3 - $ S_2 ^ * = \ left \ {p \ in \ mathbb {R} ^ n: p ^ Tx \ leq 0, \ forall x \ in S_2 \ right \} $

Desde $ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1 $

Portanto, se $ \ hat {p} \ em S_2 ^ *, $ então $ \ hat {p} ^ Tx \ leq 0, \ forall x \ em S_2 $

$ \ Rightarrow \ hat {p} ^ Tx \ leq 0, \ forall x \ em S_1 $

$ \ Rightarrow \ hat {p} ^ T \ in S_1 ^ * $

$ \ Rightarrow S_2 ^ * \ subseteq S_1 ^ * $

Teorema

Seja C um cone convexo fechado não vazio, então $ C = C ^ ** $

Prova

$ C = C ^ {**} $ pelo lema anterior.

Para provar: $ x \ in C ^ {**} \ subseteq C $

Seja $ x \ em C ^ {**} $ e seja $ x \ notin C $

Então, pelo teorema da separação fundamental, existe um vetor $ p \ neq 0 $ e um escalar $ \ alpha $ tal que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Portanto, $ p ^ Tx> \ alpha $

Mas como $ \ left (y = 0 \ right) \ in C $ e $ p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0 $ e $ p ^ Tx> 0 $

Se $ p \ notin C ^ * $, então existe algum $ \ bar {y} \ em C $ tal que $ p ^ T \ bar {y}> 0 $ e $ p ^ T \ left (\ lambda \ bar {y} \ right) $ pode ser arbitrariamente grande tomando $ \ lambda $ suficientemente grande.

Isso contradiz o fato de que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Portanto, $ p \ in C ^ * $

Já que $ x \ em C ^ * = \ left \ {q: q ^ Tp \ leq 0, \ forall p \ in C ^ * \ right \} $

Portanto, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Mas $ p ^ Tx> \ alpha $

Assim é a contardição.

Assim, $ x \ em C $

Portanto, $ C = C ^ {**} $.

Um ponto da forma $ \ alpha_1x_1 + \ alpha_2x_2 + .... + \ alpha_nx_n $ com $ \ alpha_1, \ alpha_2, ..., \ alpha_n \ geq 0 $ é chamado de combinação cônica de $ x_1, x_2, ..., x_n. $

• Se $ x_i $ estão no cone convexo C, então cada combinação cônica de $ x_i $ também está em C.

• Um conjunto C é um cone convexo se contiver toda a combinação cônica de seus elementos.

Casco Cônico

Um casco cônico é definido como um conjunto de todas as combinações cônicas de um determinado conjunto S e é denotado por coni (S).

Assim, $ coni \ left (S \ right) = \ left \ {\ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i: x_i \ in S, \ lambda_i \ in \ mathbb {R}, \ lambda_i \ geq 0, i = 1,2, ... \ right \} $

• O casco cônico é um conjunto convexo.
• A origem sempre pertence ao casco cônico.

Um conjunto em $ \ mathbb {R} ^ n $ é considerado poliédrico se for a interseção de um número finito de meios-espaços fechados, ou seja,

$ S = \ left \ {x \ in \ mathbb {R} ^ n: p_ {i} ^ {T} x \ leq \ alpha_i, i = 1,2, ...., n \ right \} $

Por exemplo,

• $ \ left \ {x \ in \ mathbb {R} ^ n: AX = b \ right \} $

• $ \ left \ {x \ in \ mathbb {R} ^ n: AX \ leq b \ right \} $

• $ \ left \ {x \ in \ mathbb {R} ^ n: AX \ geq b \ right \} $

Cone Poliédrico

Um conjunto em $ \ mathbb {R} ^ n $ é chamado de cone poliédrico se for a interseção de um número finito de meios espaços que contêm a origem, ou seja, $ S = \ left \ {x \ in \ mathbb { R} ^ n: p_ {i} ^ {T} x \ leq 0, i = 1, 2, ... \ right \} $

Polytope

Um politopo é um conjunto poliédrico que é limitado.

Observações

• Um politopo é uma casca convexa de um conjunto finito de pontos.
• Um cone poliédrico é gerado por um conjunto finito de vetores.
• Um conjunto poliédrico é um conjunto fechado.
• Um conjunto poliédrico é um conjunto convexo.

Seja S um conjunto convexo em $ \ mathbb {R} ^ n $. Um vetor $ x \ em S $ é considerado um ponto extremo de S se $ x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ com $ x_1, x_2 \ in S $ e $ \ lambda \ em \ left (0, 1 \ right) \ Rightarrow x = x_1 = x_2 $.

Exemplo

Step 1 - $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 1 \ right \ } $

Ponto extremo, $ E = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} + x_ {2} ^ {2} = 1 \ right \} $

Step 2 - $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_1 + x_2 <2, -x_1 + 2x_2 \ leq 2, x_1, x_2 \ geq 0 \ right \ } $

Ponto extremo, $ E = \ left \ {\ left (0, 0 \ right), \ left (2, 0 \ right), \ left (0, 1 \ right), \ left (\ frac {2} {3 }, \ frac {4} {3} \ right) \ right \} $

Step 3 - S é o politopo formado pelos pontos $ \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2, 4 \ direita), \ esquerda (0,2 \ direita) \ direita \} $

Ponto extremo, $ E = \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2,4 \ right) \ right \} $

Observações

• Qualquer ponto do conjunto convexo S pode ser representado como uma combinação convexa de seus pontos extremos.

• Só é verdadeiro para conjuntos fechados e limitados em $ \ mathbb {R} ^ n $.

• Pode não ser verdade para conjuntos ilimitados.

k pontos extremos

Um ponto em um conjunto convexo é chamado k extremo se e somente se for o ponto interno de um conjunto convexo k-dimensional dentro de S, e não é um ponto interno de um conjunto convexo (k + 1) - dimensional dentro de S. Basicamente, para um conjunto convexo S, k pontos extremos criam faces abertas k-dimensionais.

Seja S um conjunto convexo fechado em $ \ mathbb {R} ^ n $. Um vetor diferente de zero $ d \ in \ mathbb {R} ^ n $ é chamado de direção de S se para cada $ x \ em S, x + \ lambda d \ em S, \ forall \ lambda \ geq 0. $

• Duas direções $ d_1 $ e $ d_2 $ de S são chamadas distintas se $ d \ neq \ alpha d_2 $ para $ \ alpha> 0 $.

• Uma direção $ d $ de $ S $ é dita direção extrema se não puder ser escrita como uma combinação linear positiva de duas direções distintas, ou seja, se $ d = \ lambda _1d_1 + \ lambda _2d_2 $ para $ \ lambda _1, \ lambda _2> 0 $, então $ d_1 = \ alpha d_2 $ para algum $ \ alpha $.

• Qualquer outra direção pode ser expressa como uma combinação positiva de direções extremas.

• Para um conjunto convexo $ S $, a direção d tal que $ x + \ lambda d \ em S $ para algum $ x \ em S $ e todos $ \ lambda \ geq0 $ é chamada recessive por $ S $.

• Seja E o conjunto dos pontos onde uma certa função $ f: S \ rightarrow $ sobre um conjunto convexo não vazio S em $ \ mathbb {R} ^ n $ atinge seu máximo, então $ E $ é chamado de face exposta de $ S $. As direções das faces expostas são chamadas de direções expostas.

• Um raio cuja direção é uma direção extrema é chamado de raio extremo.

Exemplo

Considere a função $ f \ left (x \ right) = y = \ left | x \ right | $, onde $ x \ in \ mathbb {R} ^ n $. Seja d um vetor unitário em $ \ mathbb {R} ^ n $

Então, d é a direção para a função f porque para qualquer $ \ lambda \ geq 0, x + \ lambda d \ in f \ left (x \ right) $.

Seja $ f: S \ rightarrow \ mathbb {R} $, onde S é convexo não vazio definido em $ \ mathbb {R} ^ n $, então $ f \ left (x \ right) $ é considerado convexo em S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left ( x_2 \ right), \ forall \ lambda \ in \ left (0,1 \ right) $.

Por outro lado, seja $ f: S \ rightarrow \ mathbb {R} $, onde S é convexo não vazio definido em $ \ mathbb {R} ^ n $, então $ f \ left (x \ right) $ é dito a ser côncavo em S se $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ geq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) ) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Seja $ f: S \ rightarrow \ mathbb {R} $ onde S é não vazio convexo definido em $ \ mathbb {R} ^ n $, então $ f \ left (x \ right) $ é dito ser estritamente convexo em S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) <\ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Seja $ f: S \ rightarrow \ mathbb {R} $ onde S é não vazio convexo definido em $ \ mathbb {R} ^ n $, então $ f \ left (x \ right) $ é dito ser estritamente côncavo em S if $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right)> \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $.

Exemplos

• Uma função linear é convexa e côncava.

• $ f \ left (x \ right) = \ left | x \ right | $ é uma função convexa.

• $ f \ left (x \ right) = \ frac {1} {x} $ é uma função convexa.

Teorema

Sejam $ f_1, f_2, ..., f_k: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ funções convexas. Considere a função $ f \ left (x \ right) = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_jf_j \ left (x \ right) $ onde $ \ alpha_j> 0, j = 1, 2,. ..k, $ então $ f \ left (x \ right) $ é uma função convexa.

Prova

Já que $ f_1, f_2, ... f_k $ são funções convexas

Portanto, $ f_i \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f_i \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_i \ left (x_2 \ right), \ forall \ lambda \ in \ left (0, 1 \ right) $ e $ i = 1, 2, ...., k $

Considere a função $ f \ left (x \ right) $.

Portanto,

$ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) $

$ = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_jf_j \ left (\ lambda x_1 + 1- \ lambda \ right) x_2 \ leq \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_j \ lambda f_j \ left (x_1 \ right) + \ left (1- \ lambda \ right) f_j \ left (x_2 \ right) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda \ left (\ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha _jf_j \ left ( x_1 \ right) \ right) + \ left (\ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha _jf_j \ left (x_2 \ right) \ right) $

$ \ Rightarrow f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq \ lambda f \ left (x_2 \ right) \ leq \ left (1- \ lambda \ right) f \ esquerda (x_2 \ direita) $

Portanto, $ f \ left (x \ right) $ é uma função convexa.

Teorema

Seja $ f \ left (x \ right) $ uma função convexa em um conjunto convexo $ S \ subset \ mathbb {R} ^ n $ então um mínimo local de $ f \ left (x \ right) $ em S é um mínimos globais.

Prova

Seja $ \ hat {x} $ um mínimo local para $ f \ left (x \ right) $ e $ \ hat {x} $ não é um mínimo global.

portanto, $ \ existe \ hat {x} \ em S $ tal que $ f \ left (\ bar {x} \ right) <f \ left (\ hat {x} \ right) $

Como $ \ hat {x} $ é um mínimo local, existe a vizinhança $ N_ \ varepsilon \ left (\ hat {x} \ right) $ tal que $ f \ left (\ hat {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $

But $f\left ( x \right )$ is a convex function on S, therefore for $\lambda \in \left ( 0, 1 \right )$

we have $\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}\leq \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left ( \bar{x} \right )$

$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left (\hat{x} \right )$

$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< f\left (\hat{x} \right ), \forall \lambda \in \left ( 0,1 \right )$

But for some $\lambda<1$ but close to 1, we have

$\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \in N_\varepsilon \left ( \hat{x} \right )\cap S$ and $f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )< f\left ( \bar{x} \right )$

which is a contradiction.

Hence, $\bar{x}$ is a global minima.

Epigraph

let S be a non-empty subset in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$ then the epigraph of f denoted by epi(f) or $E_f$ is a subset of $\mathbb{R}^n+1$ defined by $E_f=\left \{ \left ( x,\alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\leq \alpha \right \}$

Hypograph

let S be a non-empty subset in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$, then the hypograph of f denoted by hyp(f) or $H_f=\left \{ \left ( x, \alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\geq \alpha \right \}$

Theorem

Let S be a non-empty convex set in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}^n$, then f is convex if and only if its epigraph $E_f$ is a convex set.

Proof

Let f is a convex function.

To show $E_f$ is a convex set.

Let $\left ( x_1, \alpha_1 \right ),\left ( x_2, \alpha_2 \right ) \in E_f,\lambda \in\left ( 0, 1 \right )$

To show $\lambda \left ( x_1,\alpha_1 \right )+\left ( 1-\lambda \right )\left ( x_2, \alpha_2 \right ) \in E_f$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2 \right ]\in E_f$

$f\left ( x_1 \right )\leq \alpha _1, f\left ( x_2\right )\leq \alpha _2$

Therefore, $f\left (\lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f \left ( x_2 \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2$

Converse

Let $E_f$ is a convex set.

To show f is convex.

i.e., to show if $x_1, x_2 \in S,\lambda \left ( 0, 1\right )$

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Let $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right ),f\left ( x_1 \right ), f\left ( x_2 \right ) \in \mathbb{R}$

Since $E_f$ is a convex set, $\left ( \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )\right )f\left ( x_2 \right )\in E_f$

Therefore, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Let S be a non-empty convex set in $\mathbb{R}^n$ and $f:S \rightarrow \mathbb{R}^n$. Then f is convex if and only if for each integer $k>0$

$x_1,x_2,...x_k \in S, \displaystyle\sum\limits_{i=1}^k \lambda_i=1, \lambda_i\geq 0, \forall i=1,2,s,k$, we have $f\left ( \displaystyle\sum\limits_{i=1}^k \lambda_ix_i \right )\leq \displaystyle\sum\limits_{i=1}^k \lambda _if\left ( x \right )$

Proof

By induction on k.

$k=1:x_1 \in S$ Therefore $f\left ( \lambda_1 x_1\right ) \leq \lambda_i f\left (x_1\right )$ because $\lambda_i=1$.

$k=2:\lambda_1+\lambda_2=1$ and $x_1, x_2 \in S$

Therefore, $\lambda_1x_1+\lambda_2x_2 \in S$

Hence by definition, $f\left ( \lambda_1 x_1 +\lambda_2 x_2 \right )\leq \lambda _1f\left ( x_1 \right )+\lambda _2f\left ( x_2 \right )$

Let the statement is true for $n < k$

Therefore,

$f\left ( \lambda_1 x_1+ \lambda_2 x_2+....+\lambda_k x_k\right )\leq \lambda_1 f\left (x_1 \right )+\lambda_2 f\left (x_2 \right )+...+\lambda_k f\left (x_k \right )$

$k=n+1:$ Let $x_1, x_2,....x_n,x_{n+1} \in S$ and $\displaystyle\sum\limits_{i=1}^{n+1}=1$

Therefore $\mu_1x_1+\mu_2x_2+.......+\mu_nx_n+\mu_{n+1} x_{n+1} \in S$

thus,$f\left (\mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1} x_{n+1} \right )$

$=f\left ( \left ( \mu_1+\mu_2+...+\mu_n \right)\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+\mu_3}+\mu_{n+1}x_{n+1} \right)$

$=f\left ( \mu_y+\mu_{n+1}x_{n+1} \right )$ where $\mu=\mu_1+\mu_2+...+\mu_n$ and

$y=\frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n}$ and also $\mu_1+\mu_{n+1}=1,y \in S$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq \mu f\left ( y \right )+\mu_{n+1} f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right ) \leq$

$\left ( \mu_1+\mu_2+...+\mu_n \right )f\left ( \frac{\mu_1x_1+\mu_2x_2+...+\mu_nx_n}{\mu_1+\mu_2+...+\mu_n} \right )+\mu_{n+1}f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n +\mu_{n+1}x_{n+1}\right )\leq \left ( \mu_1+ \mu_2+ ...+\mu_n \right )$

$\left [ \frac{\mu_1}{\mu_1+ \mu_2+ ...+\mu_n}f\left ( x_1 \right )+...+\frac{\mu_n}{\mu_1+ \mu_2+ ...+\mu_n}f\left ( x_n \right ) \right ]+\mu_{n+1}f\left ( x_{n+1} \right )$

$\Rightarrow f\left ( \mu_1x_1+\mu_2x_2+...+\mu_nx_n+\mu_{n+1}x_{n+1}\right )\leq \mu_1f\left ( x_1 \right )+\mu_2f\left ( x_2 \right )+....$

Hence Proved.

Let S be a non-empty open set in $\mathbb{R}^n$,then $f:S\rightarrow \mathbb{R}$ is said to be differentiable at $\hat{x} \in S$ if there exist a vector $\bigtriangledown f\left ( \hat{x} \right )$ called gradient vector and a function $\alpha :\mathbb{R}^n\rightarrow \mathbb{R}$ such that

$f\left ( x \right )=f\left ( \hat{x} \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x-\hat{x} \right )+\left \| x=\hat{x} \right \|\alpha \left ( \hat{x}, x-\hat{x} \right ), \forall x \in S$ where

$\alpha \left (\hat{x}, x-\hat{x} \right )\rightarrow 0 \bigtriangledown f\left ( \hat{x} \right )=\left [ \frac{\partial f}{\partial x_1}\frac{\partial f}{\partial x_2}...\frac{\partial f}{\partial x_n} \right ]_{x=\hat{x}}^{T}$

Theorem

let S be a non-empty, open convexset in $\mathbb{R}^n$ and let $f:S\rightarrow \mathbb{R}$ be differentiable on S. Then, f is convex if and only if for $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f\left ( x_2 \right )$

Proof

Let f be a convex function. i.e., for $x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right )$

$f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

$ \Rightarrow f\left [ \lambda x_1+\left ( 1-\lambda \right )x_2 \right ]\leq \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )+f\left ( x_2 \right )$

$ \Rightarrow\lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2+\lambda \left ( x_1-x_2 \right ) \right )-f\left ( x_2 \right )$

$\Rightarrow \lambda \left ( f\left ( x_1 \right )-f\left ( x_2 \right ) \right )\geq f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\lambda +$

$\left \| \lambda \left ( x_1-x_2 \right ) \right \|\alpha \left ( x_2,\lambda\left (x_1 - x_2 \right )-f\left ( x_2 \right ) \right )$

where $\alpha\left ( x_2, \lambda\left (x_1 - x_2 \right ) \right )\rightarrow 0$ as$\lambda \rightarrow 0$

Dividing by $\lambda$ on both sides, we get −

$f\left ( x_1 \right )-f\left ( x_2 \right ) \geq \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right )$

Converse

Let for $x_1,x_2 \in S, \bigtriangledown f\left ( x_2 \right )^T \left ( x_1-x_2 \right ) \leq f\left ( x_1 \right )-f \left ( x_2 \right )$

To show that f is convex.

Since S is convex, $x_3=\lambda x_1+\left (1-\lambda \right )x_2 \in S, \lambda \in \left ( 0, 1 \right )$

Since $x_1, x_3 \in S$, therefore

$f\left ( x_1 \right )-f \left ( x_3 \right ) \geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 -x_3\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - \lambda x_1-\left (1-\lambda \right )x_2\right )$

$ \Rightarrow f\left ( x_1 \right )-f \left ( x_3 \right )\geq \left ( 1- \lambda\right )\bigtriangledown f\left ( x_3 \right )^T \left ( x_1 - x_2\right )$

Since, $x_2, x_3 \in S$ therefore

$f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-\lambda x_1-\left ( 1-\lambda \right )x_2 \right )$

$\Rightarrow f\left ( x_2 \right )-f\left ( x_3 \right )\geq \left ( -\lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )$

Thus, combining the above equations, we get −

$\lambda \left ( f\left ( x_1 \right )-f\left ( x_3 \right ) \right )+\left ( 1- \lambda \right )\left ( f\left ( x_2 \right )-f\left ( x_3 \right ) \right )\geq 0$

$\Rightarrow f\left ( x_3\right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

Theorem

let S be a non-empty open convex set in $\mathbb{R}^n$ and let $f:S \rightarrow \mathbb{R}$ be differentiable on S, then f is convex on S if and only if for any $x_1,x_2 \in S,\left ( \bigtriangledown f \left ( x_2 \right )-\bigtriangledown f \left ( x_1 \right ) \right )^T \left ( x_2-x_1 \right ) \geq 0$

Proof

let f be a convex function, then using the previous theorem −

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )\leq f\left ( x_1 \right )-f\left ( x_2 \right )$ and

$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

Adding the above two equations, we get −

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x_2 \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x_2-x_1 \right )\geq 0$

Converse

Let for any $x_1,x_2 \in S,\left (\bigtriangledown f \left ( x_2\right )- \bigtriangledown f \left ( x_1\right )\right )^T \left ( x_2-x_1\right )\geq 0$

To show that f is convex.

Let $x_1,x_2 \in S$, thus by mean value theorem, $\frac{f\left ( x_1\right )-f\left ( x_2\right )}{x_1-x_2}=\bigtriangledown f\left ( x\right ),x \in \left ( x_1-x_2\right ) \Rightarrow x= \lambda x_1+\left ( 1-\lambda\right )x_2$ because S is a convex set.

$\Rightarrow f\left ( x_1 \right )- f\left ( x_2 \right )=\left ( \bigtriangledown f\left ( x \right )^T \right )\left ( x_1-x_2 \right )$

for $x,x_1$, we know −

$\left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( x-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )-\bigtriangledown f\left ( x_1 \right ) \right )^T\left ( \lambda x_1+\left ( 1-\lambda \right )x_2-x_1 \right )\geq 0$

$\Rightarrow \left ( \bigtriangledown f\left ( x \right )- \bigtriangledown f\left ( x_1 \right )\right )^T\left ( 1- \lambda \right )\left ( x_2-x_1 \right )\geq 0$

$\Rightarrow \bigtriangledown f\left ( x \right )^T\left ( x_2-x_1 \right )\geq \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )$

Combining the above equations, we get −

$\Rightarrow \bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\leq f\left ( x_2 \right )-f\left ( x_1 \right )$

Hence using the last theorem, f is a convex function.

Twice Differentiable function

Let S be a non-empty subset of $\mathbb{R}^n$ and let $f:S\rightarrow \mathbb{R}$ then f is said to be twice differentiable at $\bar{x} \in S$ if there exists a vector $\bigtriangledown f\left (\bar{x}\right ), a \:nXn$ matrix $H\left (x\right )$(called Hessian matrix) and a function $\alpha:\mathbb{R}^n \rightarrow \mathbb{R}$ such that $f\left ( x \right )=f\left ( \bar{x}+x-\bar{x} \right )=f\left ( \bar{x} \right )+\bigtriangledown f\left ( \bar{x} \right )^T\left ( x-\bar{x} \right )+\frac{1}{2}\left ( x-\bar{x} \right )H\left ( \bar{x} \right )\left ( x-\bar{x} \right )$

where $ \alpha \left ( \bar{x}, x-\bar{x} \right )\rightarrow Oasx\rightarrow \bar{x}$

Theorem

Let f be twice differentiable function. If $\bar{x}$ is a local minima, then $\bigtriangledown f\left ( \bar{x} \right )=0$ and the Hessian matrix $H\left ( \bar{x} \right )$ is a positive semidefinite.

Proof

Let $d \in \mathbb{R}^n$. Since f is twice differentiable at $\bar{x}$.

Therefore,

$f\left ( \bar{x} +\lambda d\right )=f\left ( \bar{x} \right )+\lambda \bigtriangledown f\left ( \bar{x} \right )^T d+\lambda^2d^TH\left ( \bar{x} \right )d+\lambda^2d^TH\left ( \bar{x} \right )d+$

$\lambda^2\left \| d \right \|^2\beta \left ( \bar{x}, \lambda d \right )$

But $\bigtriangledown f\left ( \bar{x} \right )=0$ and $\beta\left ( \bar{x}, \lambda d \right )\rightarrow 0$ as $\lambda \rightarrow 0$

$\Rightarrow f\left ( \bar{x} +\lambda d \right )-f\left ( \bar{x} \right )=\lambda ^2d^TH\left ( \bar{x} \right )d$

Since $\bar{x }$ is a local minima, there exists a $\delta > 0$ such that $f\left ( x \right )\leq f\left ( \bar{x}+\lambda d \right ), \forall \lambda \in \left ( 0,\delta \right )$

Theorem

Let $f:S \rightarrow \mathbb{R}^n$ where $S \subset \mathbb{R}^n$ be twice differentiable over S. If $\bigtriangledown f\left ( x\right )=0$ and $H\left ( \bar{x} \right )$ is positive semi-definite, for all $x \in S$, then $\bar{x}$ is a global optimal solution.

Proof

Since $H\left ( \bar{x} \right )$ is positive semi-definite, f is convex function over S. Since f is differentiable and convex at $\bar{x}$

$\bigtriangledown f\left ( \bar{x} \right )^T \left ( x-\bar{x} \right ) \leq f\left (x\right )-f\left (\bar{x}\right ),\forall x \in S$

Since $\bigtriangledown f\left ( \bar{x} \right )=0, f\left ( x \right )\geq f\left ( \bar{x} \right )$

Hence, $\bar{x}$ is a global optima.

Theorem

Suppose $\bar{x} \in S$ is a local optimal solution to the problem $f:S \rightarrow \mathbb{R}$ where S is a non-empty subset of $\mathbb{R}^n$ and S is convex. $min \:f\left ( x \right )$ where $x \in S$.

Then:

• $\bar{x}$ is a global optimal solution.

• If either $\bar{x}$ is strictly local minima or f is strictly convex function, then $\bar{x}$ is the unique global optimal solution and is also strong local minima.

Proof

Let $\bar{x}$ be another global optimal solution to the problem such that $x \neq \bar{x}$ and $f\left ( \bar{x} \right )=f\left ( \hat{x} \right )$

Since $\hat{x},\bar{x} \in S$ and S is convex, then $\frac{\hat{x}+\bar{x}}{2} \in S$ and f is strictly convex.

$\Rightarrow f\left ( \frac{\hat{x}+\bar{x}}{2} \right )< \frac{1}{2} f\left (\bar{x}\right )+\frac{1}{2} f\left (\hat{x}\right )=f\left (\hat{x}\right )$

This is contradiction.

Hence, $\hat{x}$ is a unique global optimal solution.

Corollary

Let $f:S \subset \mathbb{R}^n \rightarrow \mathbb{R}$ be a differentiable convex function where $\phi \neq S\subset \mathbb{R}^n$ is a convex set. Consider the problem $min f\left (x\right ),x \in S$,then $\bar{x}$ is an optimal solution if $\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right ) \geq 0,\forall x \in S.$

Proof

Let $\bar{x}$ is an optimal solution, i.e, $f\left (\bar{x}\right )\leq f\left (x\right ),\forall x \in S$

$\Rightarrow f\left (x\right )=f\left (\bar{x}\right )\geq 0$

$f\left (x\right )=f\left (\bar{x}\right )+\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right )+\left \| x-\bar{x} \right \|\alpha \left ( \bar{x},x-\bar{x} \right )$

where $\alpha \left ( \bar{x},x-\bar{x} \right )\rightarrow 0$ as $x \rightarrow \bar{x}$

$\Rightarrow f\left (x\right )-f\left (\bar{x}\right )=\bigtriangledown f\left (\bar{x}\right )^T\left (x-\bar{x}\right )\geq 0$

Corollary

Let f be a differentiable convex function at $\bar{x}$,then $\bar{x}$ is global minimum iff $\bigtriangledown f\left (\bar{x}\right )=0$

Examples

• $f\left (x\right )=\left (x^2-1\right )^{3}, x \in \mathbb{R}$.

  $\bigtriangledown f\left (x\right )=0 \Rightarrow x= -1,0,1$.

  $\bigtriangledown^2f\left (\pm 1 \right )=0, \bigtriangledown^2 f\left (0 \right )=6>0$.

  $f\left (\pm 1 \right )=0,f\left (0 \right )=-1$

  Hence, $f\left (x \right ) \geq -1=f\left (0 \right )\Rightarrow f\left (0 \right ) \leq f \left (x \right)\forall x \in \mathbb{R}$

• $f\left (x \right )=x\log x$ defined on $S=\left \{ x \in \mathbb{R}, x> 0 \right \}$.

  ${f}'x=1+\log x$

  ${f}''x=\frac{1}{x}>0$

  Thus, this function is strictly convex.

• $f \left (x \right )=e^{x},x \in \mathbb{R}$ is strictly convex.

Let $f:S \rightarrow \mathbb{R}$ where $S \subset \mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1,x_2 \in S$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq max\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \},\lambda \in \left ( 0, 1 \right )$

For example, $f\left ( x \right )=x^{3}$

Let $f:S\rightarrow R $ where $S\subset \mathbb{R}^n$ is a non-empty convex set. The function f is said to be quasiconvex if for each $x_1, x_2 \in S$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\geq min\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}, \lambda \in \left ( 0, 1 \right )$

Remarks

• Every convex function is quasiconvex but the converse is not true.
• A function which is both quasiconvex and quasiconcave is called quasimonotone.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasiconvex if and only if $S_{\alpha} =\left ( x \in S:f\left ( x \right )\leq \alpha \right \}$ is convex for each real number \alpha$

Proof

Let f is quasiconvex on S.

Let $x_1,x_2 \in S_{\alpha}$ therefore $x_1,x_2 \in S$ and $max \left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}\leq \alpha$

Let $\lambda \in \left (0, 1 \right )$ and let $x=\lambda x_1+\left ( 1-\lambda \right )x_2\leq max \left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}\Rightarrow x \in S$

Thus, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq max\left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}\leq \alpha$

Therefore, $S_{\alpha}$ is convex.

Converse

Let $S_{\alpha}$ is convex for each $\alpha$

$x_1,x_2 \in S, \lambda \in \left ( 0,1\right )$

$x=\lambda x_1+\left ( 1-\lambda \right )x_2$

Let $x=\lambda x_1+\left ( 1-\lambda \right )x_2$

For $x_1, x_2 \in S_{\alpha}, \alpha= max \left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}$

$\Rightarrow \lambda x_1+\left (1-\lambda \right )x_2 \in S_{\alpha}$

$\Rightarrow f \left (\lambda x_1+\left (1-\lambda \right )x_2 \right )\leq \alpha$

Hence proved.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasiconcave if and only if $S_{\alpha} =\left \{ x \in S:f\left ( x \right )\geq \alpha \right \}$ is convex for each real number $\alpha$.

Theorem

Let $f:S\rightarrow \mathbb{R}$ and S is a non empty convex set in $\mathbb{R}^n$. The function f is quasimonotone if and only if $S_{\alpha} =\left \{ x \in S:f\left ( x \right )= \alpha \right \}$ is convex for each real number $\alpha$.

Theorem

Let S be a non empty convex set in $\mathbb{R}^n$ and $f:S \rightarrow \mathbb{R}$ be differentiable on S, then f is quasiconvex if and only if for any $x_1,x_2 \in S$ and $f\left ( x_1 \right )\leq f\left ( x_2 \right )$, we have $\bigtriangledown f\left ( x_2 \right )^T\left ( x_2-x_1 \right )\leq 0$

Proof

Let f be a quasiconvex function.

Let $x_1,x_2 \in S$ such that $f\left ( x_1 \right ) \leq f\left ( x_2 \right )$

By differentiability of f at $x_2, \lambda \in \left ( 0, 1 \right )$

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )=f\left ( x_2+\lambda \left (x_1-x_2 \right ) \right )=f\left ( x_2 \right )+\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1-x_2 \right ) \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )-f\left ( x_2 \right )-f\left ( x_2 \right )=\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )$

$+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x2, \lambda\left ( x_1-x_2 \right )\right )$

But since f is quasiconvex, $f \left ( \lambda x_1+ \left ( 1- \lambda \right )x_2 \right )\leq f \left (x_2 \right )$

$\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right )+\lambda \left \| x_1-x_2 \right \|\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right ) \right )\leq 0$

But $\alpha \left ( x_2,\lambda \left ( x_1,x_2 \right )\right )\rightarrow 0$ as $\lambda \rightarrow 0$

Therefore, $\bigtriangledown f\left ( x_2 \right )^T\left ( x_1-x_2 \right ) \leq 0$

Converse

let for $x_1,x_2 \in S$ and $f\left ( x_1 \right )\leq f\left ( x_2 \right )$, $\bigtriangledown f\left ( x_2 \right )^T \left ( x_1,x_2 \right ) \leq 0$

To show that f is quasiconvex,ie, $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq f\left ( x_2 \right )$

Proof by contradiction

Suppose there exists an $x_3= \lambda x_1+\left ( 1-\lambda \right )x_2$ such that $f\left ( x_2 \right )< f \left ( x_3 \right )$ for some $ \lambda \in \left ( 0, 1 \right )$

For $x_2$ and $x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_2-x_3 \right ) \leq 0$

$\Rightarrow -\lambda \bigtriangledown f\left ( x_3 \right )^T\left ( x_2-x_3 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\geq 0$

For $x_1$ and $x_3,\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_3 \right ) \leq 0$

$\Rightarrow \left ( 1- \lambda \right )\bigtriangledown f\left ( x_3 \right )^T\left ( x_1-x_2 \right )\leq 0$

$\Rightarrow \bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )\leq 0$

thus, from the above equations, $\bigtriangledown f\left ( x_3 \right )^T \left ( x_1-x_2 \right )=0$

Define $U=\left \{ x:f\left ( x \right )\leq f\left ( x_2 \right ),x=\mu x_2+\left ( 1-\mu \right )x_3, \mu \in \left ( 0,1 \right ) \right \}$

Thus we can find $x_0 \in U$ such that $x_0 = \mu_0 x_2= \mu x_2+\left ( 1- \mu \right )x_3$ for some $\mu _0 \in \left ( 0,1 \right )$ which is nearest to $x_3$ and $\hat{x} \in \left ( x_0,x_1 \right )$ such that by mean value theorem,

$$\frac{f\left ( x_3\right )-f\left ( x_0\right )}{x_3-x_0}= \bigtriangledown f\left ( \hat{x}\right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\bigtriangledown f\left ( \hat{x} \right )^T\left ( x_3-x_0 \right )$$

$$\Rightarrow f\left ( x_3 \right )=f\left ( x_0 \right )+\mu_0 \lambda f\left ( \hat{x}\right )^T \left ( x_1-x_2 \right )$$

Since $x_0$ is a combination of $x_1$ and $x_2$ and $f\left (x_2 \right )< f\left ( \hat{x}\right )$

By repeating the starting procedure, $\bigtriangledown f \left ( \hat{x}\right )^T \left ( x_1-x_2\right )=0$

Thus, combining the above equations, we get:

$$f\left ( x_3\right )=f\left ( x_0 \right ) \leq f\left ( x_2\right )$$

$$\Rightarrow f\left ( x_3\right )\leq f\left ( x_2\right )$$

Hence, it is contradiction.

Examples

Step 1 − $f\left ( x\right )=X^3$

$Let f \left ( x_1\right )\leq f\left ( x_2\right )$

$\Rightarrow x_{1}^{3}\leq x_{2}^{3}\Rightarrow x_1\leq x_2$

$\bigtriangledown f\left ( x_2 \right )\left ( x_1-x_2 \right )=3x_{2}^{2}\left ( x_1-x_2 \right )\leq 0$

Thus, $f\left ( x\right )$ is quasiconvex.

Step 2 − $f\left ( x\right )=x_{1}^{3}+x_{2}^{3}$

Let $\hat{x_1}=\left ( 2, -2\right )$ and $\hat{x_2}=\left ( 1, 0\right )$

thus, $f\left ( \hat{x_1}\right )=0,f\left ( \hat{x_2}\right )=1 \Rightarrow f\left ( \hat{x_1}\right )\setminus < f \left ( \hat{x_2}\right )$

Thus, $\bigtriangledown f \left ( \hat{x_2}\right )^T \left ( \hat{x_1}- \hat{x_2}\right )= \left ( 3, 0\right )^T \left ( 1, -2\right )=3 >0$

Hence $f\left ( x\right )$ is not quasiconvex.

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$ then f is said to be strictly quasicovex function if for each $x_1,x_2 \in S$ with $f\left ( x_1 \right ) \neq f\left ( x_2 \right )$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \}$

Remarks

• Every strictly quasiconvex function is strictly convex.
• Strictly quasiconvex function does not imply quasiconvexity.
• Strictly quasiconvex function may not be strongly quasiconvex.
• Pseudoconvex function is a strictly quasiconvex function.

Theorem

Let $f:S\rightarrow \mathbb{R}^n$ be strictly quasiconvex function and S be a non-empty convex set in $\mathbb{R}^n$.Consider the problem: $min \:f\left ( x \right ), x \in S$. If $\hat{x}$ is local optimal solution, then $\bar{x}$ is global optimal solution.

Proof

Let there exists $ \bar{x} \in S$ such that $f\left ( \bar{x}\right )\leq f \left ( \hat{x}\right )$

Since $\bar{x},\hat{x} \in S$ and S is convex set, therefore,

$$\lambda \bar{x}+\left ( 1-\lambda \right )\hat{x}\in S, \forall \lambda \in \left ( 0,1 \right )$$

Since $\hat{x}$ is local minima, $f\left ( \hat{x} \right ) \leq f\left ( \lambda \bar{x}+\left ( 1-\lambda \right )\hat{x} \right ), \forall \lambda \in \left ( 0,\delta \right )$

Since f is strictly quasiconvex.

$$f\left ( \lambda \bar{x}+\left ( 1-\lambda \right )\hat{x} \right )< max \left \{ f\left ( \hat{x} \right ),f\left ( \bar{x} \right ) \right \}=f\left ( \hat{x} \right )$$

Hence, it is contradiction.

Strictly quasiconcave function

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$, then f is saud to be strictly quasicovex function if for each $x_1,x_2 \in S$ with $f\left (x_1\right )\neq f\left (x_2\right )$, we have

$$f\left (\lambda x_1+\left (1-\lambda\right )x_2\right )> min \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$$.

Examples

• $f\left (x\right )=x^2-2$

  It is a strictly quasiconvex function because if we take any two points $x_1,x_2$ in the domain that satisfy the constraints in the definition $f\left (\lambda x_1+\left (1- \lambda\right )x_2\right )< max \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$ As the function is decreasing in the negative x-axis and it is increasing in the positive x-axis (since it is a parabola).

• $f\left (x\right )=-x^2$

  It is not a strictly quasiconvex function because if we take take $x_1=1$ and $x_2=-1$ and $\lambda=0.5$, then $f\left (x_1\right )=-1=f\left (x_2\right )$ but $f\left (\lambda x_1+\left (1- \lambda\right )x_2\right )=0$ Therefore it does not satisfy the conditions stated in the definition. But it is a quasiconcave function because if we take any two points in the domain that satisfy the constraints in the definition $f\left ( \lambda x_1+\left (1-\lambda\right )x_2\right )> min \left \{ f \left (x_1\right ),f\left (x_2\right )\right \}$. As the function is increasing in the negative x-axis and it is decreasing in the positive x-axis.

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$ then f is strongly quasiconvex function if for any $x_1,x_2 \in S$ with $\left ( x_1 \right ) \neq \left ( x_2 \right )$, we have $f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< max \:\left \{ f\left ( x_1 \right ),f\left ( x_2 \right ) \right \},\forall \lambda \in \left ( 0,1\right )$

Theorem

A quasiconvex function $f:S\rightarrow \mathbb{R}^n$ on a non-empty convex set S in $\mathbb{R}^n$ is strongly quasiconvex function if it is not constant on a line segment joining any points of S.

Proof

Let f is quasiconvex function and it is not constant on a line segment joining any points of S.

Suppose f is not strongly quasiconvex function.

There exist $x_1,x_2 \in S$ with $x_1 \neq x_2$ such that

$$f\left ( z \right )\geq max\left \{ f\left ( x_1 \right ), f\left ( x_2 \right ) \right \}, \forall z= \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \in \left ( 0,1 \right )$$

$\Rightarrow f\left ( x_1 \right )\leq f\left ( z \right )$ and $f\left ( x_2 \right )\leq f\left ( z \right )$

Since f is not constant in $\left [ x_1,z \right ]$ and $\left [z,x_2 \right ] $

So there exists $u \in \left [ x_1,z \right ]$ and $v=\left [ z,x_2 \right ]$

$$\Rightarrow u= \mu_1x_1+\left ( 1-\mu_1\right )z,v=\mu_2z+\left ( 1- \mu_2\right )x_2$$

Since f is quasiconvex,

$$\Rightarrow f\left ( u \right )\leq max\left \{ f\left ( x_1 \right ),f \left ( z \right ) \right \}=f\left ( z \right )\:\: and \:\:f \left ( v \right ) \leq max \left \{ f\left ( z \right ),f\left ( x_2 \right ) \right \}$$

$$\Rightarrow f\left ( u \right )\leq f\left ( z \right ) \:\: and \:\: f\left ( v \right )\leq f\left ( z \right )$$

$$\Rightarrow max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$$

But z is any point between u and v, if any of them are equal, then f is constant.

Therefore, $max \left \{ f\left ( u \right ),f\left ( v \right ) \right \} \leq f\left ( z \right )$

which contradicts the quasiconvexity of f as $z \in \left [ u,v \right ]$.

Hence f is strongly quasiconvex function.

Theorem

Let $f:S\rightarrow \mathbb{R}^n$ and S be a non-empty convex set in $\mathbb{R}^n$. If $\hat{x}$ is local optimal solution, then $\hat{x}$ is unique global optimal solution.

Proof

Since a strong quasiconvex function is also strictly quasiconvex function, thus a local optimal solution is global optimal solution.

Uniqueness − Let f attains global optimal solution at two points $u,v \in S$

$$\Rightarrow f\left ( u \right ) \leq f\left ( x \right ).\forall x \in S\:\: and \:\:f\left ( v \right ) \leq f\left ( x \right ).\forall x \in S$$

If u is global optimal solution, $f\left ( u \right )\leq f\left ( v \right )$ and $f\left ( v \right )\leq f\left ( u\right )\Rightarrow f\left ( u \right )=f\left ( v\right )$

$$f\left ( \lambda u+\left ( 1-\lambda\right )v\right )< max \left \{f\left ( u \right ),f\left ( v \right ) \right \}=f\left ( u \right )$$

which is a contradiction.

Hence there exists only one global optimal solution.

Remarks

• A strongly quasiconvex function is also strictly quasiconvex fucntion.
• A strictly convex function may or may not be strongly quasiconvex.
• A differentiable strictly convex is strongly quasiconvex.

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1,x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )\geq f\left ( x_1 \right )$, or equivalently if $f\left ( x_1 \right )>f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )<0$

Pseudoconcave function

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1, x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )\leq f\left ( x_1 \right )$, or equivalently if $f\left ( x_1 \right )>f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )>0$

Remarks

• If a function is both pseudoconvex and pseudoconcave, then is is called pseudolinear.

• A differentiable convex function is also pseudoconvex.

• A pseudoconvex function may not be convex. For example,

  $f\left ( x \right )=x+x^3$ is not convex. If $x_1 \leq x_2,x_{1}^{3} \leq x_{2}^{3}$

  Thus,$\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )=\left ( 1+3x_{1}^{2} \right )\left ( x_2-x_1 \right ) \geq 0$

  And, $f\left ( x_2 \right )-f\left ( x_1 \right )=\left ( x_2-x_1 \right )+\left ( x_{2}^{3} -x_{1}^{3}\right )\geq 0$

  $\Rightarrow f\left ( x_2 \right )\geq f\left ( x_1 \right )$

  Thus, it is pseudoconvex.

  A pseudoconvex function is strictly quasiconvex. Thus, every local minima of pseudoconvex is also global minima.

Strictly pseudoconvex function

Let $f:S\rightarrow \mathbb{R}$ be a differentiable function and S be a non-empty convex set in $\mathbb{R}^n$, then f is said to be pseudoconvex if for each $x_1,x_2 \in S$ with $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )\geq 0$, we have $f\left ( x_2 \right )> f\left ( x_1 \right )$,or equivalently if $f\left ( x_1 \right )\geq f\left ( x_2 \right )$ then $\bigtriangledown f\left ( x_1 \right )^T\left ( x_2-x_1 \right )<0$

Theorem

Let f be a pseudoconvex function and suppose $\bigtriangledown f\left ( \hat{x}\right )=0$ for some $\hat{x} \in S$, then $\hat{x}$ is global optimal solution of f over S.

Proof

Let $\hat{x}$ be a critical point of f, ie, $\bigtriangledown f\left ( \hat{x}\right )=0$

Since f is pseudoconvex function, for $x \in S,$ we have

$$\bigtriangledown f\left ( \hat{x}\right )\left ( x-\hat{x}\right )=0 \Rightarrow f\left ( \hat{x}\right )\leq f\left ( x\right ), \forall x \in S$$

Hence, $\hat{x}$ is global optimal solution.

Remark

If f is strictly pseudoconvex function, $\hat{x}$ is unique global optimal solution.

Theorem

If f is differentiable pseudoconvex function over S, then f is both strictly quasiconvex as well as quasiconvex function.

Remarks

• The sum of two pseudoconvex fucntions defined on an open set S of $\mathbb{R}^n$ may not be pseudoconvex.

• Let $f:S\rightarrow \mathbb{R}$ be a quasiconvex function and S be a non-empty convex subset of $\mathbb{R}^n$ then f is pseudoconvex if and only if every critical point is a global minima of f over S.

• Let S be a non-empty convex subset of $\mathbb{R}^n$ and $f:S\rightarrow \mathbb{R}$ be a function such that $\bigtriangledown f\left ( x\right )\neq 0$ for every $x \in S$ then f is pseudoconvex if and only if it is a quasiconvex function.

There are four types of convex programming problems −

Step 1 − $min \:f\left ( x \right )$, where $x \in S$ and S be a non-empty convex set in $\mathbb{R}^n$ and $f\left ( x \right )$ is convex function.

Step 2 − $min \: f\left ( x \right ), x \in \mathbb{R}^n$ subject to

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ and $g_i\left ( x \right )$ is a convex function.

$g_i\left ( x \right ) \leq 0,m_1+1 \leq m_2$ and $g_i\left ( x \right )$ is a concave function.

$g_i\left ( x \right ) = 0, m_2+1 \leq m$ and $g_i\left ( x \right )$ is a linear function.

where $f\left ( x \right )$ is a convex fucntion.

Step 3 − $max \:f\left ( x \right )$ where $x \in S$ and S be a non-empty convex set in $\mathbb{R}^n$ and $f\left ( x \right )$ is concave function.

Step 4 − $min \:f\left ( x \right )$, where $x \in \mathbb{R}^n$ subject to

$g_i\left ( x \right ) \geq 0, 1 \leq m_1$ and $g_i\left ( x \right )$ is a convex function.

$g_i\left ( x \right ) \leq 0, m_1+1 \leq m_2$ and $g_i\left ( x \right )$ is a concave function.

$g_i\left ( x \right ) = 0,m_2+1 \leq m$ and $g_i\left ( x \right )$ is a linear function.

where $f\left ( x \right )$ is a concave function.

Cone of feasible direction

Let S be a non-empty set in $\mathbb{R}^n$ and let $\hat{x} \in \:Closure\left ( S \right )$, then the cone of feasible direction of S at $\hat{x}$, denoted by D, is defined as $D=\left \{ d:d\neq 0,\hat{x}+\lambda d \in S, \lambda \in \left ( 0, \delta \right ), \delta > 0 \right \}$

Each non-zero vector $d \in D$ is called feasible direction.

For a given function $f:\mathbb{R}^n \Rightarrow \mathbb{R}$ the cone of improving direction at $\hat{x}$ is denoted by F and is given by

$$F=\left \{ d:f\left ( \hat{x}+\lambda d \right )\leq f\left ( \hat{x} \right ),\forall \lambda \in \left ( 0,\delta \right ), \delta >0 \right \}$$

Each direction $d \in F$ is called an improving direction or descent direction of f at $\hat{x}$

Theorem

Necessary Condition

Consider the problem $min f\left ( x \right )$ such that $x \in S$ where S be a non-empty set in $\mathbb{R}^n$. Suppose f is differentiable at a point $\hat{x} \in S$. If $\hat{x}$ is a local optimal solution, then $F_0 \cap D= \phi$ where $F_0=\left \{ d:\bigtriangledown f\left ( \hat{x} \right )^T d < 0 \right \}$ and D is a cone of feasible direction.

Sufficient Condition

If $F_0 \cap D= \phi$ f is a pseudoconvex function at $\hat{x}$ and there exists a neighbourhood of $\hat{x},N_\varepsilon \left ( \hat{x} \right ), \varepsilon > 0$ such that $d=x-\hat{x}\in D$ for any $x \in S \cap N_\varepsilon \left ( \hat{x} \right )$, then $\hat{x}$ is local optimal solution.

Proof

Necessary Condition

Let $F_0 \cap D\neq \phi$, ie, there exists a $d \in F_0 \cap D$ such that $d \in F_0$ and $d\in D$

Since $d \in D$, therefore there exists $\delta_1 >0$ such that $\hat{x}+\lambda d \in S, \lambda \in \left ( 0,\delta_1 \right ).$

Since $d \in F_0$, therefore $\bigtriangledown f \left ( \hat{x}\right )^T d <0$

Thus, there exists $\delta_2>0$ such that $f\left ( \hat{x}+\lambda d\right )< f\left ( \hat{x}\right ),\forall \lambda \in f \left ( 0,\delta_2 \right )$

Let $\delta=min \left \{\delta_1,\delta_2 \right \}$

Then $\hat{x}+\lambda d \in S, f\left (\hat{x}+\lambda d \right ) < f\left ( \hat{x} \right ),\forall \lambda \in f \left ( 0,\delta \right )$

But $\hat{x}$ is local optimal solution.

Hence it is contradiction.

Thus $F_0\cap D=\phi$

Sufficient Condition

Let $F_0 \cap D\neq \phi$ nd let f be a pseudoconvex function.

Let there exists a neighbourhood of $\hat{x}, N_{\varepsilon}\left ( \hat{x} \right )$ such that $d=x-\hat{x}, \forall x \in S \cap N_\varepsilon\left ( \hat{x} \right )$

Let $\hat{x}$ is not a local optimal solution.

Thus, there exists $\bar{x} \in S \cap N_\varepsilon \left ( \hat{x} \right )$ such that $f \left ( \bar{x} \right )< f \left ( \hat{x} \right )$

By assumption on $S \cap N_\varepsilon \left ( \hat{x} \right ),d=\left ( \bar{x}-\hat{x} \right )\in D$

By pseudoconvex of f,

$$f\left ( \hat{x} \right )>f\left ( \bar{x} \right )\Rightarrow \bigtriangledown f\left ( \hat{x} \right )^T\left ( \bar{x}-\hat{x} \right )<0$$

$\Rightarrow \bigtriangledown f\left ( \hat{x} \right) ^T d <0$

$\Rightarrow d \in F_0$

hence $F_0\cap D \neq \phi$

which is a contradiction.

Hence, $\hat{x}$ is local optimal solution.

Consider the following problem:$min \:f\left ( x\right )$ where $x \in X$ such that $g_x\left ( x\right ) \leq 0, i=1,2,...,m$

$f:X \rightarrow \mathbb{R},g_i:X \rightarrow \mathbb{R}^n$ and X is an open set in $\mathbb{R}^n$

Let $S=\left \{x:g_i\left ( x\right )\leq 0,\forall i \right \}$

Let $\hat{x} \in X$, then $M=\left \{1,2,...,m \right \}$

Let $I=\left \{i:g_i\left ( \hat{x}\right )=0, i \in M\right \}$ where I is called index set for all active constraints at $\hat{x}$

Let $J=\left \{i:g_i\left ( \hat{x}\right )<0,i \in M\right \}$ where J is called index set for all active constraints at $\hat{x}$.

Let $F_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown f\left ( \hat{x} \right )^T d <0 \right \}$

Let $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gI\left ( \hat{x} \right )^T d <0 \right \}$

or $G_0=\left \{ d \in \mathbb{R}^m:\bigtriangledown gi\left ( \hat{x} \right )^T d <0 ,\forall i \in I \right \}$

Lemma

If $S=\left \{ x \in X:g_i\left ( x\right ) \leq 0, \forall i \in I\right \}$ and X is non-empty open set in $\mathbb{R}^n$. Let $\hat{x}\in S$ and $g_i$ are different at $\hat{x}, i \in I$ and let $g_i$ where $i \in J$ are continuous at $\hat{x}$, then $G_0 \subseteq D$.

Proof

Let $d \in G_0$

Since $\hat{x} \in X$ and X is an open set, thus there exists $\delta_1 >0$ such that $\hat{x}+\lambda d \in X$ for $\lambda \in \left ( 0, \delta_1\right )$

Also since $g_\hat{x}<0$ and $g_i$ are continuous at $\hat{x}, \forall i \in J$, there exists $\delta_2>0$, $g_i\left ( \hat{x}+\lambda d\right )<0, \lambda \in \left ( 0, \delta_2\right )$

Since $d \in G_0$, therefore, $\bigtriangledown g_i\left ( \hat{x}\right )^T d <0, \forall i \in I$ thus there exists $\delta_3 >0, g_i\left ( \hat{x}+\lambda d\right )< g_i\left ( \hat{x}\right )=0$, for $\lambda \in \left ( 0, \delta_3\right ) i \in J$

Let $\delta=min\left \{ \delta_1, \delta_2, \delta_3 \right \}$

therefore, $\hat{x}+\lambda d \in X, g_i\left ( \hat{x}+\lambda d\right )< 0, i \in M$

$\Rightarrow \hat{x}+\lambda d \in S$

$\Rightarrow d \in D$

$\Rightarrow G_0 \subseteq D$

Hence Proved.

Theorem

Necessary Condition

Let $f$ and $g_i, i \in I$, are different at $\hat{x} \in S,$ and $g_j$ are continous at $\hat{x} \in S$. If $\hat{x}$ is local minima of $S$, then $F_0 \cap G_0=\phi$.

Sufficient Condition

If $F_0 \cap G_0= \phi$ and f is a pseudoconvex function at $\left (\hat{x}, g_i 9x \right ), i \in I$ are strictly pseudoconvex functions over some $\varepsilon$ - neighbourhood of $\hat{x}, \hat{x}$ is a local optimal solution.

Observações

• Seja $ \ hat {x} $ um ponto viável tal que $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, então $ F_0 = \ phi $. Assim, $ F_0 \ cap G_0 = \ phi $ mas $ \ hat {x} $ não é uma solução ótima

• Mas se $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, então $ G_0 = \ phi $, portanto $ F_0 \ cap G_0 = \ phi $

• Considere o problema: min $ f \ left (x \ right) $ tal que $ g \ left (x \ right) = 0 $.

  Como $ g \ left (x \ right) = 0 $, então $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ e $ g_2 \ left (x \ right) = - g \ esquerda (x \ direita) \ leq 0 $.

  Seja $ \ hat {x} \ em S $, então $ g_1 \ left (\ hat {x} \ right) = 0 $ e $ g_2 \ left (\ hat {x} \ right) = 0 $.

  Mas $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $

  Assim, $ G_0 = \ phi $ e $ F_0 \ cap G_0 = \ phi $.

Condições Necessárias

Teorema

Considere o problema - $ min f \ left (x \ right) $ tal que $ x \ in X $ onde X é um conjunto aberto em $ \ mathbb {R} ^ n $ e deixe $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.

Seja $ f: X \ rightarrow \ mathbb {R} $ e $ g_i: X \ rightarrow \ mathbb {R} $

Seja $ \ hat {x} $ uma solução viável e sejam f e $ g_i, i \ in I $ sejam diferenciáveis ​​em $ \ hat {x} $ e $ g_i, i \ in J $ sejam contínuos em $ \ hat { x} $.

Se $ \ hat {x} $ resolve o problema acima localmente, então existe $ u_0, u_i \ in \ mathbb {R}, i \ in I $ tal que $ u_0 \ bigtriangledown f \ left (\ hat {x} \ direita) + \ displaystyle \ sum \ limits_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0

onde $ u_0, u_i \ geq 0, i \ in I $ e $ \ left (u_0, u_I \ right) \ neq \ left (0,0 \ right) $

Além disso, se $ g_i, i \ in J $ também são diferenciáveis ​​em $ \ hat {x} $, então as condições acima podem ser escritas como -

$ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $

$ u_ig_i \ left (\ hat {x} \ right) $ = 0

$ u_0, u_i \ geq 0, \ forall i = 1,2, ...., m $

$ \ left (u_0, u \ right) \ neq \ left (0,0 \ right), u = \ left (u_1, u_2, s, u_m \ right) \ in \ mathbb {R} ^ m $

Observações

• $ u_i $ são chamados de multiplicadores de Lagrange.

• A condição de que $ \ hat {x} $ seja viável para o problema dado é chamada de condição viável primal.

• O requisito $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ é chamado de viabilidade dupla doença.

• A condição $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ é chamada de condição de folga complementar. Esta condição requer $ u_i = 0, i \ in J $

• Juntas, a condição de viabilidade primária, a condição de viabilidade dupla e a folga complementar são chamadas de Condições de Fritz-John.

Condições Suficientes

Teorema

Se existe uma vizinhança $ \ varepsilon $ -de $ \ hat {x} N_ \ varejpsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ tal que f é pseudoconvex sobre $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ e $ g_i, i \ in I $ são estritamente pseudoconvexos sobre $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, então $ \ hat { x} $ é a solução ótima local para o problema descrito acima. Se f é pseudoconvexo em $ \ hat {x} $ e se $ g_i, i \ in I $ são ambos estritamente pseudoconvexo e função quase-convexa em $ \ hat {x}, \ hat {x} $ é a solução ótima global para o problema descrito acima.

Exemplo

• $ min \: f \ left (x_1, x_2 \ right) = \ left (x_1-3 \ right) ^ 2 + \ left (x_2-2 \ right) ^ 2 $

  de modo que $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ E $ \ hat {x} = \ left (2 , 1 \ right) $

  Deixe $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5, $

  $ g_2 \ left (x_1, x_2 \ right) = x_1 + 2x_2-4, $

  $ g_3 \ left (x_1, x_2 \ right) = - x_1 $ e $ g_4 \ left (x_1, x_2 \ right) = -x_2 $.

  Assim, as restrições acima podem ser escritas como -

  $ g_1 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_2 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_3 \ left (x_1, x_2 \ right) \ leq 0 $ e

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Assim, $ I = \ left \ {1,2 \ right \} $ portanto, $ u_3 = 0, u_4 = 0 $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ right) ) $ e $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  Assim, colocando esses valores na primeira condição das condições de Fritz-John, obtemos -

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ e $ u_2 = 1 $, portanto $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  Assim, as condições de Fritz John são satisfeitas.

• $ min f \ left (x_1, x_2 \ right) = - x_1 $.

  de modo que $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,

  $ -x_2 \ leq 0 $ e $ \ hat {x} = \ left (1,0 \ right) $

  Deixe $ g_1 \ left (x_1, x_2 \ right) = x_2- \ left (1-x_1 \ right) ^ 3 $,

  $ g_2 \ left (x_1, x_2 \ right) = - x_2 $

  Assim, as restrições acima podem ser escritas como -

  $ g_1 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_2 \ left (x_1, x_2 \ right) \ leq 0, $

  Assim, $ I = \ left \ {1,2 \ right \} $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (-1,0 \ right) $

  $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (0,1 \ right) $ e $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right) ) $

  Assim, colocando esses valores na primeira condição das condições de Fritz-John, obtemos -

  $ u_0 = 0, \: \: u_1 = u_2 = a> 0 $

  Assim, as condições de Fritz John são satisfeitas.

Considere o problema -

$ min \: f \ left (x \ right) $ tal que $ x \ in X $, onde X é um conjunto aberto em $ \ mathbb {R} ^ n $ e $ g_i \ left (x \ right) \ leq 0, i = 1, 2, ..., m $

Seja $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $

Seja $ \ hat {x} \ in S $ e seja $ f $ e $ g_i, i \ in I $ são diferenciáveis ​​em $ \ hat {x} $ e $ g_i, i \ in J $ são contínuos em $ \ hat {x} $. Além disso, $ \ bigtriangledown g_i \ left (\ hat {x} \ right), i \ in I $ são linearmente independentes. Se $ \ hat {x} $ resolve o problema acima localmente, então existe $ u_i, i \ in I $ tal que

$ \ bigtriangledown f \ left (x \ right) + \ displaystyle \ sum \ limits_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $, $ \: \: u_i \ geq 0, i \ in I $

Se $ g_i, i \ in J $ também são diferenciáveis ​​em $ \ hat {x} $. então $ \ hat {x} $, então

$ \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $

$ u_ig_i \ left (\ hat {x} \ right) = 0, \ forall i = 1,2, ..., m $

$ u_i \ geq 0 \ forall i = 1,2, ..., m $

Exemplo

Considere o seguinte problema -

$ min \: f \ left (x_1, x_2 \ right) = \ left (x_1-3 \ right) ^ 2 + \ left (x_2-2 \ right) ^ 2 $

de modo que $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5 $,

$ x_1,2x_2 \ geq 0 $ e $ \ hat {x} = \ left (2,1 \ right) $

Deixe $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5 $,

$ g_2 \ left (x_1, x_2 \ right) = x_ {1} + 2x_2-4 $

$ g_3 \ left (x_1, x_2 \ right) = - x_ {1} $ e $ g_4 \ left (x_1, x_2 \ right) = - x_2 $

Assim, as restrições acima podem ser escritas como -

$ g_1 \ left (x_1, x_2 \ right) \ leq 0, g_2 \ left (x_1, x_2 \ right) \ leq 0 $

$ g_3 \ left (x_1, x_2 \ right) \ leq 0, $ e $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Assim, $ I = \ left \ {1,2 \ right \} $ portanto , $ u_3 = 0, \: \: u_4 = 0 $

$ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ right) ) $ e

$ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

Assim, colocando esses valores na primeira condição das condições de Karush-Kuhn-Tucker, obtemos -

$ u_1 = \ frac {1} {3} $ e $ u_2 = \ frac {2} {3} $

Assim, as condições de Karush-Kuhn-Tucker são satisfeitas.

Método de descida mais íngreme

Este método também é chamado de método do gradiente ou método de Cauchy. Este método envolve as seguintes terminologias -

$$ x_ {k + 1} = x_k + \ alpha_kd_k $$

$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ ou $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $

Seja $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $

Diferenciando $ \ phi $ e igualando-o a zero, podemos obter $ \ alpha $.

Portanto, o algoritmo é o seguinte -

• Inicialize $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ e defina $ k = 0 $.

• Defina $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ ou $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $.

• encontre $ \ alpha_k $ de forma que minimize $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.

• Defina $ x_ {k + 1} = x_k + \ alpha_kd_k $.

• Se $ \ left \ | x_ {k + 1-x_k} \ right \ | <\ varejpsilon_1 $ ou $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, vá para a etapa 6, caso contrário, defina $ k = k + 1 $ e vá para a etapa 2.

• A solução ótima é $ \ hat {x} = x_ {k + 1} $.

Método Newton

O Método de Newton trabalha com o seguinte princípio -

$ f \ left (x \ right) = y \ left (x \ right) = f \ left (x_k \ right) + \ left (x-x_k \ right) ^ T \ bigtriangledown f \ left (x_k \ right) + \ frac {1} {2} \ left (x-x_k \ right) ^ TH \ left (x_k \ right) \ left (x-x_k \ right) $

$ \ bigtriangledown y \ left (x \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x-x_k \ right) $

Em $ x_ {k + 1}, \ bigtriangledown y \ left (x_ {k + 1} \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x_ {k +1} -x_k \ right) $

Para $ x_ {k + 1} $ ser a solução ótima $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $

Assim, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $

Aqui $ H \ left (x_k \ right) $ deve ser não singular.

Portanto, o algoritmo funciona da seguinte forma -

Step 1 - Inicialize $ x_0, \ varepsilon $ e defina $ k = 0 $.

Step 2 - encontre $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $.

Step 3 - Resolva para o sistema linear $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ para $ h \ left (x_k \ right) $.

Step 4 - encontre $ x_ {k + 1} = x_k-h \ left (x_k \ right) $.

Step 5- Se $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ ou $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ então vá para a etapa 6, caso contrário, defina $ k = k + 1 $ e vá para a etapa 2.

Step 6 - A solução ótima é $ \ hat {x} = x_ {k + 1} $.

Método do gradiente conjugado

Este método é usado para resolver problemas dos seguintes tipos -

$ min f \ left (x \ right) = \ frac {1} {2} x ^ T Qx-bx $

onde Q é uma matriz nXn definida positiva e b é constante.

Dado $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $

Defina $ d_0 = -g_0 $ para $ k = 0,1,2, ..., $

Defina $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $

Calcule $ x_ {k + 1} = x_k + \ alpha_kd_k $

Defina $ g_ {k + 1} = g_k + \ alpha_kd_k $

Calcule $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $

Calcule $ x_ {k + 1} = x_k + \ alpha_kd_k $

Defina $ g_ {k + 1} = x_k + \ alpha_kQd_k $

Calcule $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $

Defina $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.