Optimización convexa - Guía rápida

Este curso es útil para los estudiantes que desean resolver problemas de optimización no lineal que surgen en diversas aplicaciones científicas y de ingeniería. Este curso comienza con la teoría básica de la programación lineal e introducirá los conceptos de conjuntos y funciones convexos y terminologías relacionadas para explicar varios teoremas que se requieren para resolver los problemas de programación no lineal. Este curso presentará varios algoritmos que se utilizan para resolver tales problemas. Este tipo de problemas surgen en diversas aplicaciones, incluido el aprendizaje automático, problemas de optimización en ingeniería eléctrica, etc. Requiere que los estudiantes tengan conocimientos previos de conceptos matemáticos y cálculo de secundaria.

En este curso, los estudiantes aprenderán a resolver problemas de optimización como $ min f \ left (x \ right) $ sujeto a algunas restricciones.

Estos problemas se pueden resolver fácilmente si la función $ f \ left (x \ right) $ es una función lineal y si las restricciones son lineales. Entonces se llama problema de programación lineal (LPP). Pero si las restricciones no son lineales, entonces es difícil resolver el problema anterior. A menos que podamos trazar las funciones en un gráfico, entonces intentar analizar la optimización puede ser de una forma, pero no podemos trazar una función si está más allá de las tres dimensiones. De ahí surgen las técnicas de programación no lineal o programación convexa para resolver este tipo de problemas. En este tutorial, nos centraremos en aprender tales técnicas y, al final, algunos algoritmos para resolver dichos problemas. Primero traeremos la noción de conjuntos convexos que es la base de los problemas de programación convexa. Luego, con la introducción de funciones convexas, veremos algunos teoremas importantes para resolver estos problemas y algunos algoritmos basados ​​en estos teoremas.

Terminologias

• El espacio $ \ mathbb {R} ^ n $ - Es un vector n-dimensional con números reales, definido de la siguiente manera - $ \ mathbb {R} ^ n = \ left \ {\ left (x_1, x_2, ... , x_n \ right) ^ {\ tau}: x_1, x_2, ...., x_n \ in \ mathbb {R} \ right \} $

• El espacio $ \ mathbb {R} ^ {mXn} $ - Es un conjunto de todas las matrices de valores reales de orden $ mXn $.

Metodología

La Programación Lineal, también llamada Optimización Lineal, es una técnica que se utiliza para resolver problemas matemáticos en los que las relaciones son de naturaleza lineal. La naturaleza básica de la programación lineal es maximizar o minimizar unobjective function con sujeto a algunos constraints. La función objetivo es una función lineal que se obtiene del modelo matemático del problema. Las restricciones son las condiciones que se imponen al modelo y también son lineales.

• De la pregunta dada, encuentre la función objetivo.
• encontrar las limitaciones.
• Dibuja las restricciones en un gráfico.
• encuentre la región factible, que está formada por la intersección de todas las restricciones.
• encuentra los vértices de la región factible.
• encuentra el valor de la función objetivo en estos vértices.
• El vértice que maximiza o minimiza la función objetivo (según la pregunta) es la respuesta.

Ejemplos

Step 1 - Maximizar $ 5x + 3y $ sujeto a

$ x + y \ leq 2 $,

$ 3x + y \ leq 3 $,

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

Solution -

El primer paso es encontrar la región factible en un gráfico.

Claramente del gráfico, los vértices de la región factible son

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

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

Poniendo estos valores en la función objetivo, obtenemos -

$ 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

Por lo tanto, la función se maximiza en $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $

Step 2- Una empresa de relojes produce un reloj mecánico y otro digital. Las proyecciones a largo plazo indican una demanda esperada de al menos 100 relojes digitales y 80 mecánicos cada día. Debido a las limitaciones en la capacidad de producción, no se pueden fabricar más de 200 relojes digitales y 170 mecánicos al día. Para cumplir con un contrato de envío, se envían un total de al menos 200 relojes cada día.

Si cada reloj digital vendido da como resultado una pérdida de $ \ $ 2 $, pero cada reloj mecánico produce una ganancia de $ \ $ 5 $, ¿cuántos de cada tipo deberían hacerse diariamente para maximizar las ganancias netas?

Solution -

Sea $ x $ el número de relojes digitales producidos

$ y $ sea el número de relojes mecánicos producidos

Según la pregunta, se deben fabricar al menos 100 relojes digitales al día y se pueden fabricar como máximo 200 relojes digitales.

$ \ Flecha derecha 100 \ leq \: x \ leq 200 $

Del mismo modo, se deben fabricar al menos 80 relojes mecánicos al día y un máximo de 170 relojes mecánicos.

$ \ Flecha derecha 80 \ leq \: y \ leq 170 $

Dado que se van a producir al menos 200 relojes cada día.

$ \ Flecha derecha x + y \ leq 200 $

Dado que cada reloj digital vendido resulta en una pérdida de $ \ $ 2 $, pero cada reloj mecánico produce una ganancia de $ \ $ 5 $,

El beneficio total se puede calcular como

$ Beneficio = -2x + 5y $

Y tenemos que maximizar la ganancia, por lo tanto, la pregunta se puede formular como:

Maximizar $ -2x + 5y $ sujeto a

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

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

$ x + y \: \ leq 200 $

Al trazar las ecuaciones anteriores en un gráfico, obtenemos,

Los vértices de la región factible son

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

El valor máximo de la función objetivo se obtiene en $ \ left (100, 170 \ right) $ Por lo tanto, para maximizar las ganancias netas, se deben producir 100 unidades de relojes digitales y 170 unidades de relojes mecánicos.

Una norma es una función que le da un valor estrictamente positivo a un vector o una variable.

La norma es una función $ f: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $

Las características básicas de una norma son:

Sea $ X $ un vector tal que $ X \ in \ mathbb {R} ^ n $

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

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

• $ \ izquierda \ | \ alpha x \ derecha \ | = \ izquierda | \ alpha \ right | \ left \ | x \ right \ | \ forall \: x \ en X y \: \ alpha \: es \: a \: escalar $

• $ \ left \ | x + y \ right \ | \ leq \ left \ | x \ derecha \ | + \ izquierda \ | y \ right \ | \ para todo x, y \ en X $

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

Por definición, la norma se calcula de la siguiente manera:

• $ \ 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 $

La norma es una función continua.

Prueba

Por definición, si $ x_n \ rightarrow x $ en $ X \ Rightarrow f \ left (x_n \ right) \ rightarrow f \ left (x \ right) $ entonces $ f \ left (x \ right) $ es una función constante.

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

Por lo tanto, $ \ left | f \ left (x_n \ right) -f \ left (x \ right) \ right | = \ left | \ left \ | x_n \ right \ | - \ left \ | x \ derecha \ | \ derecha | \ leq \ izquierda | \ left | x_n-x \ right | \: \ derecha | $

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

Por lo tanto $ \ 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) $

Por tanto, la norma es una función continua.

El producto interno es una función que da un escalar a un par de vectores.

Producto interno - $ f: \ mathbb {R} ^ n \ times \ mathbb {R} ^ n \ rightarrow \ kappa $ donde $ \ kappa $ es un escalar.

Las características básicas del producto interior son las siguientes:

Sea $ 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 \: y \: \ forall x, y \ in X PS

• $ \ 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 \ en X $

Note -

• Relación entre norma y producto 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 $

Ejemplos

1. encontrar el producto interno de $ x = \ left (1,2,1 \ right) \: y \: y = \ left (3, -1,3 \ right) $

Solución

$ \ 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. Si $ x = \ left (4,9,1 \ right), y = \ left (-3,5,1 \ right) $ y $ z = \ left (2,4,1 \ right) $, encontrar $ \ left (x + y, z \ right) $

Solución

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 \ times 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 o Minimizar

$ \ bar {x} \ in \: S $ se dice que es el mínimo local de una función $ f $ si $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ bar {x} \ right) $ donde $ N_ \ varepsilon \ left (\ bar {x} \ right) $ significa vecindario de $ \ bar {x} $, es decir, $ N_ \ varepsilon \ left (\ bar {x} \ right) $ significa $ \ left \ | x- \ bar {x} \ right \ | <\ varepsilon $

Máximo local o maximizador

$ \ bar {x} \ in \: S $ se dice que es el máximo local de una función $ f $ si $ f \ left (\ bar {x} \ right) \ geq f \ left (x \ right), \ forall x \ in N_ \ varepsilon \ left (\ bar {x} \ right) $ donde $ N_ \ varepsilon \ left (\ bar {x} \ right) $ significa vecindario de $ \ bar {x} $, es decir, $ N_ \ varepsilon \ left (\ bar {x} \ right) $ significa $ \ left \ | x- \ bar {x} \ right \ | <\ varepsilon $

Mínimos globales

$ \ bar {x} \ in \: S $ se dice que es el mínimo global de una función $ f $ si $ f \ left (\ bar {x} \ right) \ leq f \ left (x \ right), \ por todo x \ en S $

Máximos globales

$ \ bar {x} \ in \: S $ se dice que es el máximo global de una función $ f $ si $ f \ left (\ bar {x} \ right) \ geq f \ left (x \ right), \ por todo x \ en S $

Ejemplos

Step 1- Encuentra los mínimos y máximos locales de $ f \ left (\ bar {x} \ right) = \ left | x ^ 2-4 \ right | $

Solution -

De la gráfica de la función anterior, está claro que los mínimos locales ocurren en $ x = \ pm 2 $ y los máximos locales en $ x = 0 $

Step 2- Encuentra los mínimos globales de la función $ f \ left (x \ right) = \ left | 4x ^ 3-3x ^ 2 + 7 \ right | $

Solution -

Del gráfico de la función anterior, está claro que los mínimos globales ocurren en $ x = -1 $.

Sea $ S \ subseteq \ mathbb {R} ^ n $ Se dice que un conjunto S es convexo si el segmento de línea que une dos puntos cualesquiera del conjunto S también pertenece al S, es decir, si $ x_1, x_2 \ in S $ , luego $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S $ donde $ \ lambda \ in \ left (0,1 \ right) $.

Note -

• La unión de dos conjuntos convexos puede ser convexa o no.
• La intersección de dos conjuntos convexos es siempre convexa.

Proof

Sean $ S_1 $ y $ S_2 $ dos conjuntos convexos.

Sea $ S_3 = S_1 \ cap S_2 $

Sea $ x_1, x_2 \ en S_3 $

Dado que $ S_3 = S_1 \ cap S_2 $ entonces $ x_1, x_2 \ en S_1 $ y $ x_1, x_2 \ en S_2 $

Como $ S_i $ es un conjunto convexo, $ \ forall $ $ i \ in 1,2, $

Por tanto $ \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i $ donde $ \ lambda \ in \ left (0,1 \ right) $

Por lo tanto, $ \ 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 \ in S_3 $

Por tanto, $ S_3 $ es un conjunto convexo.

• Promedio ponderado de la forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, donde $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ y $ \ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right] $ se llama combinación cónica de $ x_1, x_2, .... x_k. $

• Promedio ponderado de la forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $, donde $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_i = 1 $ se llama combinación afín de $ x_1 , x_2, .... x_k. $

• El promedio ponderado de la forma $ \ displaystyle \ sum \ limits_ {i = 1} ^ k \ lambda_ix_i $ se llama combinación lineal de $ x_1, x_2, .... x_k. $

Ejemplos

Step 1 - Demuestre que el conjunto $ S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \} $ es un conjunto convexo.

Solución

Deje $ x_1 $ y $ x_2 \ en S $

$ \ Rightarrow Cx_1 \ leq \ alpha $ y $ \: y \: 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 \ derecha) $

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

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

$ \ Flecha derecha Cy \ leq \ alpha $

$ \ Flecha derecha y \ en S $

Por tanto, $ S $ es un conjunto convexo.

Step 2 - Demuestra que el conjunto $ S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \} $ es un convexo conjunto.

Solución

Sea $ x, y \ en S $

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

$ \ Rightarrow x_ {1} ^ {2} \ leq 8x_2 $ y $ 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] $

$ Ahora, \ 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 $

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

Por lo tanto,

$ \ 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] PS

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

Step 3 - Demuestre que un conjunto $ S \ in \ mathbb {R} ^ n $ es convexo si y solo si para cada entero k, cada combinación convexa de cualesquiera k puntos de $ S $ está en $ S $.

Solución

Sea $ S $ un conjunto convexo. luego, mostrar;

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

Prueba por inducción

Para $ k = 1, x_1 \ en S, c_1 = 1 \ Flecha derecha c_1x_1 \ en S $

Para $ k = 2, x_1, x_2 \ en S, c_1 + c_2 = 1 $ y Dado que S es un conjunto convexo

$ \ Flecha derecha c_1x_1 + c_2x_2 \ en S. $

Sea la combinación convexa de m puntos de S en S, es decir,

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

Ahora, supongamos que $ x_1, x_2 ...., x_m, x_ {m + 1} \ in S $

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

Sea $ 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} $

Sea $ 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} $

Ahora $ y \ en S $ porque la suma de los coeficientes es 1.

$ \ Rightarrow x \ in S $ ya que S es un conjunto convexo y $ y, x_ {m + 1} \ in S $

Por lo tanto probado por inducción.

Se dice que un conjunto $ A $ es un conjunto afín si, para dos puntos distintos, la línea que pasa por estos puntos se encuentra en el conjunto $ A $.

Note -

• $ S $ es un conjunto afín si y solo si contiene todas las combinaciones afines de sus puntos.

• Los conjuntos vacíos y singleton son conjuntos afines y convexos.

  Por ejemplo, la solución de una ecuación lineal es un conjunto afín.

Prueba

Sea S la solución de una ecuación lineal.

Por definición, $ S = \ left \ {x \ in \ mathbb {R} ^ n: Ax = b \ right \} $

Sea $ x_1, x_2 \ in S \ Rightarrow Ax_1 = b $ y $ Ax_2 = b $

Para probar: $ 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 $

Por tanto, S es un conjunto afín.

Teorema

Si $ C $ es un conjunto afín y $ x_0 \ en C $, entonces el conjunto $ V = C-x_0 = \ left \ {x-x_0: x \ in C \ right \} $ es un subespacio de C.

Prueba

Sea $ x_1, x_2 \ en V $

Para mostrar: $ \ alpha x_1 + \ beta x_2 \ in V $ por algunos $ \ alpha, \ beta $

Ahora, $ x_1 + x_0 \ en C $ y $ x_2 + x_0 \ en C $ por definición de V

Ahora, $ \ 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 PS

Pero $ \ alpha \ left (x_1 + x_0 \ right) + \ beta \ left (x_2 + x_0 \ right) + \ left (1- \ alpha - \ beta \ right) x_0 \ en C $ porque C es un conjunto afín .

Por lo tanto, $ \ alpha x_1 + \ beta x_2 \ in V $

Por lo tanto probado.

El casco convexo de un conjunto de puntos en S es el límite de la región convexa más pequeña que contiene todos los puntos de S en su interior o en su límite.

O

Sea $ S \ subseteq \ mathbb {R} ^ n $ El casco convexo de S, denotado $ Co \ left (S \ right) $ por es la colección de todas las combinaciones convexas de S, es decir, $ x \ en Co \ left (S \ right) $ si y solo si $ x \ in \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $, donde $ \ displaystyle \ sum \ limits_ {1} ^ n \ lambda_i = 1 $ y $ \ lambda_i \ geq 0 \ forall x_i \ in S $

Remark - Conves casco de un conjunto de puntos en S en el plano define un polígono convexo y los puntos de S en el límite del polígono definen los vértices del 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 \} $ Demuestre que un casco convexo es un conjunto convexo.

Prueba

Deje $ x_1, x_2 \ in Co \ left (S \ right) $, luego $ x_1 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ix_i $ y $ x_2 = \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_ \ gamma x_i $ donde $ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ y $ \ 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 \ izquierda (1- \ theta \ right) x_i $

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

Considerando los 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 $

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

Por tanto, un casco convexo es un conjunto convexo.

Sea S un conjunto arbitrario en $ \ mathbb {R} ^ n $. Si $ x \ in Co \ left (S \ right) $, entonces $ x \ in Co \ left (x_1, x_2, ...., x_n, x_ {n + 1} \ right) $.

Prueba

Como $ x \ en Co \ left (S \ right) $, entonces $ x $ se representa mediante una combinación convexa de un número finito de puntos en S, es decir,

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

Si $ k \ leq n + 1 $, el resultado obtenido es obviamente cierto.

Si $ k \ geq n + 1 $, entonces $ \ left (x_2-x_1 \ right) \ left (x_3-x_1 \ right), ....., \ left (x_k-x_1 \ right) $ son linealmente dependientes .

$ \ Rightarrow \ existe \ mu _j \ in \ mathbb {R}, 2 \ leq j \ leq k $ (no todo cero) tal que $ \ displaystyle \ sum \ limits_ {j = 2} ^ k \ mu _j \ left (x_j-x_1 \ right) = 0 $

Defina $ \ mu_1 = - \ displaystyle \ sum \ limits_ {j = 2} ^ k \ mu _j $, luego $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ mu_j x_j = 0, \ displaystyle \ sum \ límites_ {j = 1} ^ k \ mu_j = 0 $

donde no todos los $ \ mu_j's $ son iguales a cero. Dado que $ \ displaystyle \ sum \ limits_ {j = 1} ^ k \ mu_j = 0 $, al menos uno de los $ \ mu_j> 0,1 \ leq j \ leq k $

Entonces, $ 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 = \ estilo de visualización \ sum \ límites_ {1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) x_j $

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

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

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

En particular, $ \ lambda_i- \ alpha \ mu_i = 0 $, por definición de $ \ alpha $

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

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

Por tanto, x se puede representar como una combinación convexa de como máximo (k-1) puntos.

Este proceso de reducción puede repetirse hasta que x se represente como una combinación convexa de (n + 1) elementos.

Sea S un conjunto no vacío, cerrado y acotado (también llamado conjunto compacto) en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ una función continua en S, entonces el problema min $ \ left \ {f \ left (x \ right): x \ in S \ right \} $ alcanza su mínimo.

Prueba

Dado que S no está vacío y está acotado, existe un límite inferior.

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

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

Según la definición de infimium, $ S_j $ no está vacío, para cada $ j $.

Elija $ x_j \ en S_j $ para obtener una secuencia $ \ left \ {x_j \ right \} $ para $ j = 1,2, ... $

Como S está acotada, la secuencia también está acotada y hay una subsecuencia convergente $ \ left \ {y_j \ right \} $, que converge a $ \ hat {x} $. Por tanto, $ \ hat {x} $ es un punto límite y S es cerrado, por lo tanto, $ \ hat {x} \ en S $. Como f es continua, $ f \ left (y_i \ right) \ rightarrow f \ left (\ hat {x} \ right) $.

Desde $ \ 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) $

Por tanto, $ \ hat {x} $ es la solución minimizadora.

Observaciones

Hay dos importantes condiciones necesarias para que se mantenga el teorema de Weierstrass. Estos son los siguientes:

• Step 1 - El conjunto S debe ser un conjunto acotado.

  Considere la función f \ left (x \ right) = x $.

  Es un conjunto ilimitado y tiene mínimos en cualquier punto de su dominio.

  Por lo tanto, para obtener los mínimos, S debe estar acotado.

• Step 2 - El conjunto S debe estar cerrado.

  Considere la función $ f \ left (x \ right) = \ frac {1} {x} $ en el dominio \ left (0,1 \ right).

  Esta función no está cerrada en el dominio dado y sus mínimos tampoco existen.

  Por lo tanto, para que se obtengan los mínimos, S debe estar cerrado.

Sea S un conjunto convexo cerrado no vacío en $ \ mathbb {R} ^ n $ y sea $ y \ notin S $, entonces $ \ existe $ un punto $ \ bar {x} \ en S $ con una distancia mínima desde y, es decir, $ \ left \ | y- \ bar {x} \ right \ | \ leq \ left \ | yx \ right \ | \ forall x \ en S. $

Además, $ \ bar {x} $ es un punto de minimización si y solo si $ \ left (y- \ hat {x} \ right) ^ {T} \ left (x- \ hat {x} \ right) \ leq 0 $ o $ \ left (y- \ hat {x}, x- \ hat {x} \ right) \ leq 0 $

Prueba

Existencia del punto más cercano

Desde $ S \ ne \ phi, \ existe $ un punto $ \ hat {x} \ en S $ tal que la distancia mínima de S desde y es menor o igual que $ \ left \ | y- \ hat {x} \ right \ | $.

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

Dado que $ \ hat {S} $ es cerrado y acotado, y dado que la norma es una función continua, entonces, según el teorema de Weierstrass, existe un punto mínimo $ \ hat {x} \ en S $ tal que $ \ left \ | y- \ hat {x} \ right \ | = Inf \ left \ {\ left \ | yx \ right \ |, x \ in S \ right \} $

Unicidad

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

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

Pero, $ \ 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 $

No puede ser una desigualdad estricta porque $ \ hat {x} $ está más cerca de y.

Por lo tanto, $ \ left \ | y- \ hat {x} \ right \ | = \ mu \ left \ | y- \ hat {x} \ right \ | $, por unos $ \ mu $

Ahora $ \ left \ | \ mu \ right \ | = 1. $ Si $ \ mu = -1 $, entonces $ \ left (y- \ hat {x} \ right) = - \ left (y- \ hat {x} \ right) \ Flecha derecha y = \ frac {\ hat {x} + \ bar {x}} {2} \ in S $

Pero $ y \ en S $. De ahí la contradicción. Entonces $ \ mu = 1 \ Rightarrow \ hat {x} = \ bar {x} $

Por lo tanto, minimizar el punto es único.

Para la segunda parte de la prueba, suponga $ \ left (y- \ hat {x} \ right) ^ {\ tau} \ left (x- \ bar {x} \ right) \ leq 0 $ para todos $ x \ en S $

Ahora,

$ \ 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) $

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

Por tanto, $ \ hat {x} $ minimiza el punto.

A la inversa, suponga que $ \ hat {x} $ es el punto de minimización.

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

Dado que S es un conjunto convexo.

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

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

Y

$ \ 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) $

$ \ Flecha derecha \ izquierda \ | 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 $

Por lo tanto probado.

Sea S un conjunto convexo cerrado no vacío en $ \ mathbb {R} ^ n $ y $ y \ notin S $. Entonces, existe un vector distinto de cero $ p $ y escalar $ \ beta $ tal que $ p ^ T y> \ beta $ y $ p ^ T x <\ beta $ para cada $ x \ en S $

Prueba

Dado que S es un conjunto convexo cerrado no vacío y $ y \ no en S $, por lo tanto, según el teorema del punto más cercano, existe un punto mínimo exclusivo $ \ hat {x} \ en S $ tal que

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

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

Entonces $ \ 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 $

Además, $ 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 $

$ \ Flecha derecha p ^ Ty> \ beta $

Este teorema da como resultado la separación de hiperplanos. Los hiperplanos basados ​​en el teorema anterior se pueden definir de la siguiente manera:

Sea $ S_1 $ y $ S_2 $ subconjuntos no vacíos de $ \ mathbb {R} $ y $ H = \ left \ {X: A ^ TX = b \ right \} $ un hiperplano.

• Se dice que el hiperplano H separa $ S_1 $ y $ S_2 $ si $ A ^ TX \ leq b \ forall X \ in S_1 $ y $ A_TX \ geq b \ forall X \ in S_2 $

• Se dice que el hiperplano H separa estrictamente $ S_1 $ y $ S_2 $ si $ A ^ TX <b \ forall X \ in S_1 $ y $ A_TX> b \ forall X \ in S_2 $

• Se dice que el hiperplano H separa fuertemente $ S_1 $ y $ S_2 $ si $ A ^ TX \ leq b \ forall X \ in S_1 $ y $ A_TX \ geq b + \ varepsilon \ forall X \ in S_2 $, donde $ \ varepsilon $ es un escalar positivo.

Se dice que un conjunto C no vacío en $ \ mathbb {R} ^ n $ es un cono con vértice 0 si $ x \ en C \ Rightarrow \ lambda x \ en C \ forall \ lambda \ geq 0 $.

Un conjunto C es un cono convexo si es tanto convexo como cónico.

Por ejemplo, $ y = \ left | x \ right | $ no es un cono convexo porque no es convexo.

Pero, $ y \ geq \ left | x \ right | $ es un cono convexo porque es tanto convexo como cono.

Note - Un cono C es convexo si y solo si para cualquier $ x, y \ en C, x + y \ en C $.

Prueba

Como C es cono, para $ x, y \ en C \ Rightarrow \ lambda x \ en C $ y $ \ mu y \ en C \: \ forall \: \ lambda, \ mu \ geq 0 $

C es convexa si $ \ lambda x + \ left (1- \ lambda \ right) y \ in C \: \ forall \: \ lambda \ in \ left (0, 1 \ right) $

Como C es cono, $ \ lambda x \ en C $ y $ \ left (1- \ lambda \ right) y \ in C \ Leftrightarrow x, y \ in C $

Por tanto, C es convexa si $ x + y \ en C $

En general, si $ x_1, x_2 \ en C $, entonces, $ \ lambda_1x_1 + \ lambda_2x_2 \ en C, \ forall \ lambda_1, \ lambda_2 \ geq 0 $

Ejemplos

• La combinación cónica de un conjunto infinito de vectores en $ \ mathbb {R} ^ n $ es un cono convexo.

• Cualquier conjunto vacío es un cono convexo.

• Cualquier función lineal es un cono convexo.

• Dado que un hiperplano es lineal, también es un cono convexo.

• Los medios espacios cerrados también son conos convexos.

Note - La intersección de dos conos convexos es un cono convexo pero su unión puede ser o no un cono convexo.

Sea S un conjunto no vacío en $ \ mathbb {R} ^ n $ Entonces, el cono polar de S denotado por $ S ^ * $ viene dado por $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Observación

• El cono polar siempre es convexo incluso si S no es convexo.

• Si S es un conjunto vacío, $ S ^ * = \ mathbb {R} ^ n $.

• La polaridad puede verse como una generalización de la ortogonalidad.

Sea $ C \ subseteq \ mathbb {R} ^ n $ y luego el espacio 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

Deje que $ S, S_1 $ y $ S_2 $ sean conjuntos no vacíos en $ \ mathbb {R} ^ n $, entonces las siguientes declaraciones son verdaderas:

• $ S ^ * $ es un cono convexo cerrado.

• $ S \ subseteq S ^ {**} $ donde $ S ^ {**} $ es un cono polar de $ S ^ * $.

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

Prueba

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

• Sea $ x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $ y $ 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 $

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

  Por tanto, $ S ^ * $ es un conjunto convexo.

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

  Por lo tanto, $ \ lambda p ^ T x \ leq 0, $

  $ \ Flecha derecha \ izquierda (\ lambda p \ derecha) ^ T x \ leq 0 $

  $ \ Flecha derecha \ lambda p \ in S ^ * $

  Por tanto, $ S ^ * $ es un cono.

• Para mostrar que $ S ^ * $ está cerrado, es decir, para mostrar si $ p_n \ rightarrow p $ como $ n \ rightarrow \ infty $, entonces $ p \ in S ^ * $

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

  Como $ p_n \ rightarrow p $ como $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

  Por lo tanto $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $. Pero $ p_ {n} ^ {T} x \ leq 0, \: \ forall x \ in S $

  Por lo tanto, $ p ^ Tx \ leq 0, \ forall x \ in S $

  $ \ Flecha derecha p \ en S ^ * $

  Por tanto, $ S ^ * $ está cerrado.

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

Sea $ x \ in S $, luego $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Entonces, $ 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 $

Por lo tanto, si $ \ hat {p} \ in S_2 ^ *, $ entonces $ \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_2 $

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

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

$ \ Flecha derecha S_2 ^ * \ subseteq S_1 ^ * $

Teorema

Sea C un cono convexo cerrado no vacío, entonces $ C = C ^ ** $

Prueba

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

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

Deje $ x \ en C ^ {**} $ y deje $ x \ notin C $

Entonces, por el teorema de separación fundamental, existe un vector $ p \ neq 0 $ y un escalar $ \ alpha $ tal que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Por lo tanto, $ p ^ Tx> \ alpha $

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

Si $ p \ notin C ^ * $, entonces existe algo $ \ bar {y} \ en C $ tal que $ p ^ T \ bar {y}> 0 $ y $ p ^ T \ left (\ lambda \ bar {y} \ right) $ puede hacerse arbitrariamente grande tomando $ \ lambda $ lo suficientemente grande.

Esto contradice el hecho de que $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Por lo tanto, $ p \ en C ^ * $

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

Por lo tanto, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Pero $ p ^ Tx> \ alpha $

Así es la contardicción.

Por tanto, $ x \ en C $

Por tanto, $ C = C ^ {**} $.

Un punto de la forma $ \ alpha_1x_1 + \ alpha_2x_2 + .... + \ alpha_nx_n $ con $ \ alpha_1, \ alpha_2, ..., \ alpha_n \ geq 0 $ se llama combinación cónica de $ x_1, x_2, ..., x_n. $

• Si $ x_i $ están en el cono convexo C, entonces cada combinación cónica de $ x_i $ también está en C.

• Un conjunto C es un cono convexo si contiene toda la combinación cónica de sus elementos.

Casco cónico

Un casco cónico se define como un conjunto de todas las combinaciones cónicas de un conjunto S dado y se denota por coni (S).

Por lo tanto, $ 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 \} $

• El casco cónico es un conjunto convexo.
• El origen siempre pertenece al casco cónico.

Se dice que un conjunto en $ \ mathbb {R} ^ n $ es poliédrico si es la intersección de un número finito de medios espacios cerrados, es decir,

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

Por ejemplo,

• $ \ 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 \} $

Cono poliédrico

Se dice que un conjunto en $ \ mathbb {R} ^ n $ es un cono poliédrico si es la intersección de un número finito de medios espacios que contienen el origen, es decir, $ S = \ left \ {x \ in \ mathbb { R} ^ n: p_ {i} ^ {T} x \ leq 0, i = 1, 2, ... \ right \} $

Politopo

Un politopo es un conjunto poliédrico que está acotado.

Observaciones

• Un politopo es un casco convexo de un conjunto finito de puntos.
• Un cono poliédrico se genera mediante un conjunto finito de vectores.
• Un conjunto poliédrico es un conjunto cerrado.
• Un conjunto poliédrico es un conjunto convexo.

Sea S un conjunto convexo en $ \ mathbb {R} ^ n $. Se dice que un vector $ x \ en S $ es un punto extremo de S si $ x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ con $ x_1, x_2 \ en S $ y $ \ lambda \ en \ left (0, 1 \ right) \ Rightarrow x = x_1 = x_2 $.

Ejemplo

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

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

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 \ PS

Punto 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 es el politopo formado por los puntos $ \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2, 4 \ derecha), \ izquierda (0,2 \ derecha) \ derecha \} $

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

Observaciones

• Cualquier punto del conjunto convexo S, puede representarse como una combinación convexa de sus puntos extremos.

• Solo es cierto para conjuntos cerrados y acotados en $ \ mathbb {R} ^ n $.

• Puede que no sea cierto para conjuntos ilimitados.

k puntos extremos

Un punto en un conjunto convexo se llama k extremo si y solo si es el punto interior de un conjunto convexo de k dimensiones dentro de S, y no es un punto interior de un conjunto convexo de dimensiones k + 1 dentro de S. Básicamente, para un conjunto convexo S, k puntos extremos forman caras abiertas k-dimensionales.

Sea S un conjunto convexo cerrado en $ \ mathbb {R} ^ n $. Un vector distinto de cero $ d \ in \ mathbb {R} ^ n $ se llama una dirección de S si para cada $ x \ en S, x + \ lambda d \ en S, \ forall \ lambda \ geq 0. $

• Dos direcciones $ d_1 $ y $ d_2 $ de S se denominan distintas si $ d \ neq \ alpha d_2 $ para $ \ alpha> 0 $.

• Se dice que una dirección $ d $ de $ S $ es una dirección extrema si no se puede escribir como una combinación lineal positiva de dos direcciones distintas, es decir, si $ d = \ lambda _1d_1 + \ lambda _2d_2 $ para $ \ lambda _1, \ lambda _2> 0 $, luego $ d_1 = \ alpha d_2 $ por algo de $ \ alpha $.

• Cualquier otra dirección puede expresarse como una combinación positiva de direcciones extremas.

• Para un conjunto convexo $ S $, la dirección d tal que $ x + \ lambda d \ en S $ para algunos $ x \ en S $ y todo $ \ lambda \ geq0 $ se llama recessive por $ S $.

• Sea E el conjunto de los puntos donde una determinada función $ f: S \ rightarrow $ sobre un conjunto convexo no vacío S en $ \ mathbb {R} ^ n $ alcanza su máximo, entonces $ E $ se llama cara expuesta de $ S $. Las direcciones de las caras expuestas se denominan direcciones expuestas.

• Un rayo cuya dirección es una dirección extrema se llama rayo extremo.

Ejemplo

Considere la función $ f \ left (x \ right) = y = \ left | x \ right | $, donde $ x \ in \ mathbb {R} ^ n $. Sea d un vector unitario en $ \ mathbb {R} ^ n $

Entonces, d es la dirección de la función f porque para cualquier $ \ lambda \ geq 0, x + \ lambda d \ in f \ left (x \ right) $.

Sea $ f: S \ rightarrow \ mathbb {R} $, donde S es un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces $ f \ left (x \ right) $ se dice que es convexo en 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 otro lado, sea $ f: S \ rightarrow \ mathbb {R} $, donde S es un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces se dice $ f \ left (x \ right) $ ser cóncavo en S si $ 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) $.

Sea $ f: S \ rightarrow \ mathbb {R} $ donde S es un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces $ f \ left (x \ right) $ se dice que es estrictamente convexo en S si $ 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) $.

Sea $ f: S \ rightarrow \ mathbb {R} $ donde S es un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces $ f \ left (x \ right) $ se dice que es estrictamente cóncavo en 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) $.

Ejemplos

• Una función lineal es tanto convexa como cóncava.

• $ f \ left (x \ right) = \ left | x \ right | $ es una función convexa.

• $ f \ left (x \ right) = \ frac {1} {x} $ es una función convexa.

Teorema

Sean $ f_1, f_2, ..., f_k: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ funciones convexas. Considere la función $ f \ left (x \ right) = \ displaystyle \ sum \ limits_ {j = 1} ^ k \ alpha_jf_j \ left (x \ right) $ donde $ \ alpha_j> 0, j = 1, 2,. ..k, $ entonces $ f \ left (x \ right) $ es una función convexa.

Prueba

Dado que $ f_1, f_2, ... f_k $ son funciones convexas

Por lo tanto, $ 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) $ y $ i = 1, 2, ...., k $

Considere la función $ f \ left (x \ right) $.

Por lo tanto,

$ 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 \ izquierda (x_2 \ right) $

Por tanto, $ f \ left (x \ right) $ es una función convexa.

Teorema

Sea $ f \ left (x \ right) $ una función convexa en un conjunto convexo $ S \ subset \ mathbb {R} ^ n $ entonces un mínimo local de $ f \ left (x \ right) $ en S es un mínimos globales.

Prueba

Sea $ \ hat {x} $ un mínimo local para $ f \ left (x \ right) $ y $ \ hat {x} $ no es un mínimo global.

por lo tanto, $ \ existe \ hat {x} \ en S $ tal que $ f \ left (\ bar {x} \ right) <f \ left (\ hat {x} \ right) $

Como $ \ hat {x} $ es un mínimo local, existe un vecindario $ 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 $

Pero $ f \ left (x \ right) $ es una función convexa en S, por lo tanto para $ \ lambda \ in \ left (0, 1 \ right) $

tenemos $ \ 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 \ derecha) 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 \ derecha) $

Pero para algunos $ \ lambda <1 $ pero cerca de 1, tenemos

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

lo cual es una contradicción.

Por tanto, $ \ bar {x} $ es un mínimo global.

Epígrafe

sea ​​S un subconjunto no vacío en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ entonces el epígrafe de f denotado por epi (f) o $ E_f $ es un subconjunto de $ \ mathbb {R} ^ n + 1 $ definido por $ E_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb { R}, f \ izquierda (x \ derecha) \ leq \ alpha \ derecha \} $

Hipografo

sea ​​S un subconjunto no vacío en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $, luego el hipograma de f denotado por hyp (f) o $ H_f = \ left \ {\ left (x, \ alpha \ right): x \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R} ^ n, \ alpha \ in \ mathbb {R}, f \ left ( x \ derecha) \ geq \ alpha \ right \} $

Teorema

Sea S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} ^ n $, entonces f es convexa si y solo si su epígrafe $ E_f $ es un conjunto convexo.

Prueba

Sea f una función convexa.

Para mostrar que $ E_f $ es un conjunto convexo.

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

Para mostrar $ \ lambda \ left (x_1, \ alpha_1 \ right) + \ left (1- \ lambda \ right) \ left (x_2, \ alpha_2 \ right) \ en 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 \ izquierda (x_1 \ derecha) \ leq \ alpha _1, f \ izquierda (x_2 \ derecha) \ leq \ alpha _2 $

Por lo tanto, $ 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 \ derecha) $

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

Conversar

Sea $ E_f $ un conjunto convexo.

Para mostrar f es convexa.

es decir, para mostrar si $ 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) $

Sea $ 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} $

Como $ E_f $ es un conjunto convexo, $ \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2, \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) \ derecha) f \ left (x_2 \ right) \ in E_f $

Por lo tanto, $ 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 \ derecha) $

Sea S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ y $ f: S \ rightarrow \ mathbb {R} ^ n $. Entonces f es convexa si y solo si para cada entero $ k> 0 $

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

Prueba

Por inducción en k.

$ k = 1: x_1 \ in S $ Por lo tanto $ f \ left (\ lambda_1 x_1 \ right) \ leq \ lambda_i f \ left (x_1 \ right) $ porque $ \ lambda_i = 1 $.

$ k = 2: \ lambda_1 + \ lambda_2 = 1 $ y $ x_1, x_2 \ en S $

Por lo tanto, $ \ lambda_1x_1 + \ lambda_2x_2 \ in S $

Por lo tanto, por definición, $ f \ left (\ lambda_1 x_1 + \ lambda_2 x_2 \ right) \ leq \ lambda _1f \ left (x_1 \ right) + \ lambda _2f \ left (x_2 \ right) $

Sea el enunciado verdadero para $ n <k $

Por lo tanto,

$ 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: $ Sea $ x_1, x_2, .... x_n, x_ {n + 1} \ in S $ y $ \ displaystyle \ sum \ limits_ {i = 1} ^ {n + 1} = 1 $

Por lo tanto $ \ mu_1x_1 + \ mu_2x_2 + ....... + \ mu_nx_n + \ mu_ {n + 1} x_ {n + 1} \ in S $

así, $ 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) $ donde $ \ mu = \ mu_1 + \ mu_2 + ... + \ mu_n $ y

$ y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n} {\ mu_1 + \ mu_2 + ... + \ mu_n} $ y también $ \ mu_1 + \ mu_ {n + 1} = 1, y \ en 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 \ derecha) $

$ \ 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) + .... $

Por lo tanto probado.

Sea S un conjunto abierto no vacío en $ \ mathbb {R} ^ n $, entonces se dice que $ f: S \ rightarrow \ mathbb {R} $ es diferenciable en $ \ hat {x} \ en S $ si existe un vector $ \ bigtriangledown f \ left (\ hat {x} \ right) $ llamado vector degradado y una función $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tal que

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

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

Teorema

sea ​​S un conjunto convexo abierto no vacío en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ diferenciable en S. Entonces, f es convexa si y solo si para $ 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) $

Prueba

Sea f una función convexa. es decir, para $ 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) $

donde $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ como $ \ lambda \ rightarrow 0 $

Dividiendo por $ \ lambda $ en ambos lados, obtenemos -

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

Conversar

Sea para $ 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) PS

Para demostrar que f es convexa.

Como S es convexo, $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

Como $ x_1, x_3 \ en S $, por lo tanto

$ 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) $

Dado que, $ x_2, x_3 \ in S $ por lo tanto

$ 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 \ derecha) $

Por lo tanto, combinando las ecuaciones anteriores, obtenemos:

$ \ 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) $

Teorema

sea ​​S un conjunto convexo abierto no vacío en $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ diferenciable en S, entonces f es convexa en S si y solo si para cualquier $ 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 PS

Prueba

sea ​​f una función convexa, luego usando el teorema anterior -

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

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

Sumando las dos ecuaciones anteriores, obtenemos:

$ \ 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 $

Conversar

Sea para cualquier $ x_1, x_2 \ en S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Para demostrar que f es convexa.

Sea $ x_1, x_2 \ en S $, por lo tanto, por el teorema del valor medio, $ \ 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 $ porque S es un conjunto convexo.

$ \ 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) $

por $ x, x_1 $, sabemos -

$ \ 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 \ derecha) \ 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) $

Combinando las ecuaciones anteriores, obtenemos:

$ \ 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) $

Por tanto, utilizando el último teorema, f es una función convexa.

Función dos veces diferenciable

Sea S un subconjunto no vacío de $ \ mathbb {R} ^ n $ y sea $ f: S \ rightarrow \ mathbb {R} $ entonces se dice que f es dos veces diferenciable en $ \ bar {x} \ en S $ si existe un vector $ \ bigtriangledown f \ left (\ bar {x} \ right), una \: nXn $ matriz $ H \ left (x \ right) $ (llamada matriz de Hesse) y una función $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ tal que $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ izquierda (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) + \ frac {1} {2} \ izquierda (x- \ bar {x} \ derecha) H \ izquierda (\ bar {x} \ derecha) \ izquierda (x- \ bar {x} \ derecha) $

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

Teorema

Sea f una función dos veces diferenciable. Si $ \ bar {x} $ es un mínimo local, entonces $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ y la matriz de Hesse $ H \ left (\ bar {x} \ right) $ es un semidefinito positivo.

Prueba

Sea $ d \ in \ mathbb {R} ^ n $. Dado que f es dos veces diferenciable en $ \ bar {x} $.

Por lo tanto,

$ 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) $

Pero $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $ y $ \ beta \ left (\ bar {x}, \ lambda d \ right) \ rightarrow 0 $ como $ \ lambda \ rightarrow 0 $

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

Como $ \ bar {x} $ es un mínimo local, existe un $ \ delta> 0 $ tal que $ f \ left (x \ right) \ leq f \ left (\ bar {x} + \ lambda d \ right ), \ forall \ lambda \ in \ left (0, \ delta \ right) $

Teorema

Sea $ f: S \ rightarrow \ mathbb {R} ^ n $ donde $ S \ subset \ mathbb {R} ^ n $ sea dos veces diferenciable sobre S. Si $ \ bigtriangledown f \ left (x \ right) = 0 $ y $ H \ left (\ bar {x} \ right) $ es semidefinido positivo, para todo $ x \ en S $, entonces $ \ bar {x} $ es una solución óptima global.

Prueba

Como $ H \ left (\ bar {x} \ right) $ es semidefinida positiva, f es una función convexa sobre S. Dado que f es diferenciable y convexa en $ \ 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 $

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

Por tanto, $ \ bar {x} $ es un óptimo global.

Teorema

Suponga que $ \ bar {x} \ in S $ es una solución local óptima al problema $ f: S \ rightarrow \ mathbb {R} $ donde S es un subconjunto no vacío de $ \ mathbb {R} ^ n $ y S es convexo. $ min \: f \ left (x \ right) $ donde $ x \ en S $.

Luego:

• $ \ bar {x} $ es una solución óptima global.

• Si $ \ bar {x} $ es estrictamente un mínimo local o f es una función estrictamente convexa, entonces $ \ bar {x} $ es la solución óptima global única y también es un mínimo local fuerte.

Prueba

Sea $ \ bar {x} $ otra solución óptima global al problema, tal que $ x \ neq \ bar {x} $ y $ f \ left (\ bar {x} \ right) = f \ left (\ hat { x} \ right) $

Como $ \ hat {x}, \ bar {x} \ en S $ y S es convexo, entonces $ \ frac {\ hat {x} + \ bar {x}} {2} \ en S $ yf es estrictamente convexo.

$ \ 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) $

Eso es una contradicción.

Por tanto, $ \ hat {x} $ es una solución óptima global única.

Corolario

Sea $ f: S \ subset \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ una función convexa diferenciable donde $ \ phi \ neq S \ subset \ mathbb {R} ^ n $ es un conjunto convexo. Considere el problema $ min f \ left (x \ right), x \ in S $, entonces $ \ bar {x} $ es una solución óptima si $ \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) \ geq 0, \ forall x \ in S. $

Prueba

Sea $ \ bar {x} $ una solución óptima, es decir, $ 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} \ derecha) + \ izquierda \ | x- \ bar {x} \ right \ | \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) $

donde $ \ 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 $

Corolario

Sea f una función convexa diferenciable en $ \ bar {x} $, entonces $ \ bar {x} $ es el mínimo global sif $ \ bigtriangledown f \ left (\ bar {x} \ right) = 0 $

Ejemplos

• $ 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 $

  Por lo tanto, $ 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 $ definido en $ S = \ left \ {x \ in \ mathbb {R}, x> 0 \ right \} $.

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

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

  Por tanto, esta función es estrictamente convexa.

• $ f \ left (x \ right) = e ^ {x}, x \ in \ mathbb {R} $ es estrictamente convexo.

Sea $ f: S \ rightarrow \ mathbb {R} $ donde $ S \ subset \ mathbb {R} ^ n $ es un conjunto convexo no vacío. Se dice que la función f es cuasiconvexa si para cada $ x_1, x_2 \ en S $, tenemos $ 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) $

Por ejemplo, $ f \ left (x \ right) = x ^ {3} $

Sea $ f: S \ rightarrow R $ donde $ S \ subset \ mathbb {R} ^ n $ es un conjunto convexo no vacío. Se dice que la función f es cuasiconvexa si para cada $ x_1, x_2 \ en S $, tenemos $ 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) $

Observaciones

• Toda función convexa es cuasiconvexa pero lo contrario no es cierto.
• Una función que es tanto cuasiconvexa como cuasicóncava se llama cuasimonotona.

Teorema

Sea $ f: S \ rightarrow \ mathbb {R} $ y S es un conjunto convexo no vacío en $ \ mathbb {R} ^ n $. La función f es cuasiconvexa si y solo si $ S _ {\ alpha} = \ left (x \ in S: f \ left (x \ right) \ leq \ alpha \ right \} $ es convexa para cada número real \ alpha $

Prueba

Sea f cuasiconvexo en S.

Deje $ x_1, x_2 \ en S _ {\ alpha} $ por lo tanto $ x_1, x_2 \ en S $ y $ max \ left \ {f \ left (x_1 \ right), f \ left (x_2 \ right) \ right \} \ leq \ alpha $

Deje $ \ lambda \ in \ left (0, 1 \ right) $ y deje $ 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 $

Por lo tanto, $ 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 $

Por tanto, $ S _ {\ alpha} $ es convexo.

Conversar

Sea $ S _ {\ alpha} $ convexo para cada $ \ alpha $

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

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

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

Para $ x_1, x_2 \ en 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 $

Por lo tanto probado.

Teorema

Sea $ f: S \ rightarrow \ mathbb {R} $ y S es un conjunto convexo no vacío en $ \ mathbb {R} ^ n $. La función f es cuasicóncava si y solo si $ S _ {\ alpha} = \ left \ {x \ in S: f \ left (x \ right) \ geq \ alpha \ right \} $ es convexo para cada número real $ \ alpha $.

Teorema

Sea $ f: S \ rightarrow \ mathbb {R} $ y S es un conjunto convexo no vacío en $ \ mathbb {R} ^ n $. La función f es cuasimonotona si y solo si $ S _ {\ alpha} = \ left \ {x \ in S: f \ left (x \ right) = \ alpha \ right \} $ es convexa para cada número real $ \ alpha PS

Teorema

Sea S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ y $ f: S \ rightarrow \ mathbb {R} $ sea diferenciable en S, entonces f es cuasiconvexo si y solo si para cualquier $ x_1, x_2 \ en S $ y $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $, tenemos $ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0 $

Prueba

Sea f una función cuasiconvexa.

Sea $ x_1, x_2 \ en S $ tal que $ f \ left (x_1 \ right) \ leq f \ left (x_2 \ right) $

Por diferenciabilidad de f en $ 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) $

Pero como f es cuasiconvexa, $ 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 $

Pero $ \ alpha \ left (x_2, \ lambda \ left (x_1, x_2 \ right) \ right) \ rightarrow 0 $ como $ \ lambda \ rightarrow 0 $

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

Conversar

supongamos que $ x_1, x_2 \ in S $ y $ 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 $

Para mostrar que f es cuasiconvexa, es decir, $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ leq f \ left (x_2 \ right) $

Proof by contradiction

Suponga que existe un $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ tal que $ f \ left (x_2 \ right) <f \ left (x_3 \ right) $ para algunos $ \ lambda \ in \ left (0, 1 \ right) $

Para $ x_2 $ y $ 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 $

Para $ x_1 $ y $ 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 $

por lo tanto, de las ecuaciones anteriores, $ \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

Defina $ 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 \ izquierda (0,1 \ derecha) \ derecha \} $

Por lo tanto, podemos encontrar $ x_0 \ en U $ tal que $ x_0 = \ mu_0 x_2 = \ mu x_2 + \ left (1- \ mu \ right) x_3 $ para algunos $ \ mu _0 \ in \ left (0,1 \ right ) $ que está más cerca de $ x_3 $ y $ \ hat {x} \ in \ left (x_0, x_1 \ right) $ tal que por teorema del valor medio

$$ \ 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) $ PS

Dado que $ x_0 $ es una combinación de $ x_1 $ y $ x_2 $ y $ f \ left (x_2 \ right) <f \ left (\ hat {x} \ right) $

Repitiendo el procedimiento inicial, $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x_1-x_2 \ right) = 0 $

Así, combinando las ecuaciones anteriores, obtenemos:

$$ 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) $$

Por tanto, es una contradicción.

Ejemplos

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

$ Sea 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 $

Por tanto, $ f \ left (x \ right) $ es cuasiconvexo.

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

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

así, $ 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) $

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

Por tanto, $ f \ left (x \ right) $ no es cuasiconvexo.

Sea $ f: S \ rightarrow \ mathbb {R} ^ n $ y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces se dice que f es estrictamente una función cuasicovexa si para cada $ x_1, x_2 \ en S $ con $ f \ left (x_1 \ right) \ neq f \ left (x_2 \ right) $, tenemos $ 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 \} $

Observaciones

• Toda función estrictamente cuasiconvexa es estrictamente convexa.
• La función estrictamente cuasiconvexa no implica cuasiconvexidad.
• La función estrictamente cuasiconvexa puede no ser muy cuasiconvexa.
• La función pseudoconvexa es una función estrictamente cuasiconvexa.

Teorema

Sea $ f: S \ rightarrow \ mathbb {R} ^ n $ una función estrictamente cuasiconvexa y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $. Considere el problema: $ min \: f \ left (x \ derecha), x \ en S $. Si $ \ hat {x} $ es la solución óptima local, entonces $ \ bar {x} $ es la solución óptima global.

Prueba

Deje que exista $ \ bar {x} \ en S $ tal que $ f \ left (\ bar {x} \ right) \ leq f \ left (\ hat {x} \ right) $

Como $ \ bar {x}, \ hat {x} \ en S $ y S es un conjunto convexo, por lo tanto,

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

Como $ \ hat {x} $ es el mínimo local, $ f \ left (\ hat {x} \ right) \ leq f \ left (\ lambda \ bar {x} + \ left (1- \ lambda \ right) \ sombrero {x} \ right), \ forall \ lambda \ in \ left (0, \ delta \ right) $

Dado que f es estrictamente cuasiconvexo.

$$ 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) $$

Por tanto, es una contradicción.

Función estrictamente cuasicóncava

Sea $ f: S \ rightarrow \ mathbb {R} ^ n $ y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces f es una función estrictamente cuasicovexa si para cada $ x_1, x_2 \ in S $ con $ f \ left (x_1 \ right) \ neq f \ left (x_2 \ right) $, tenemos

$$ 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 \} $$.

Ejemplos

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

  Es una función estrictamente cuasiconvexa porque si tomamos dos puntos cualesquiera $ x_1, x_2 $ en el dominio que satisfacen las restricciones en la definición $ 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 \} $ A medida que la función disminuye en el eje x negativo y aumenta en el eje x positivo ( ya que es una parábola).

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

  No es una función estrictamente cuasiconvexa porque si tomamos $ x_1 = 1 $ y $ x_2 = -1 $ y $ \ lambda = 0.5 $, entonces $ f \ left (x_1 \ right) = - 1 = f \ left ( x_2 \ right) $ pero $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = 0 $ Por tanto, no satisface las condiciones establecidas en la definición. Pero es una función cuasicóncava porque si tomamos dos puntos cualesquiera en el dominio que satisfacen las restricciones en la definición $ 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 \} $. A medida que la función aumenta en el eje x negativo y disminuye en el eje x positivo.

Sea $ f: S \ rightarrow \ mathbb {R} ^ n $ y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ entonces f es una función fuertemente cuasiconvexa si para cualquier $ x_1, x_2 \ en S $ con $ \ left (x_1 \ right) \ neq \ left (x_2 \ right) $, tenemos $ f \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) <max \: \ izquierda \ {f \ izquierda (x_1 \ derecha), f \ izquierda (x_2 \ derecha) \ derecha \}, \ forall \ lambda \ in \ izquierda (0,1 \ derecha) $

Teorema

Una función cuasiconvexa $ f: S \ rightarrow \ mathbb {R} ^ n $ en un conjunto convexo no vacío S en $ \ mathbb {R} ^ n $ es una función fuertemente cuasiconvexa si no es constante en un segmento de línea que une cualquier puntos de S.

Prueba

Sea f una función cuasiconvexa y no es constante en un segmento de línea que une cualquier punto de S.

Suponga que f no es una función fuertemente cuasiconvexa.

Existen $ x_1, x_2 \ en S $ con $ x_1 \ neq x_2 $ tales que

$$ 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) $ y $ f \ left (x_2 \ right) \ leq f \ left (z \ right) $

Dado que f no es constante en $ \ left [x_1, z \ right] $ y $ \ left [z, x_2 \ right] $

Entonces existe $ u \ in \ left [x_1, z \ right] $ y $ 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 $$

Dado que f es cuasiconvexo,

$$ \ Rightarrow f \ left (u \ right) \ leq max \ left \ {f \ left (x_1 \ right), f \ left (z \ right) \ right \} = f \ left (z \ right) \ : \: y \: \: 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) \: \: y \: \: f \ left (v \ right) \ leq f \ left (z \ right) $ PS

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

Pero z es cualquier punto entre uyv, si alguno de ellos es igual, entonces f es constante.

Por lo tanto, $ max \ left \ {f \ left (u \ right), f \ left (v \ right) \ right \} \ leq f \ left (z \ right) $

lo cual contradice la cuasiconvexidad de f como $ z \ in \ left [u, v \ right] $.

Por tanto, f es una función fuertemente cuasiconvexa.

Teorema

Sea $ f: S \ rightarrow \ mathbb {R} ^ n $ y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $. Si $ \ hat {x} $ es la solución óptima local, entonces $ \ hat {x} $ es la solución óptima global única.

Prueba

Dado que una función cuasiconvexa fuerte también es estrictamente una función cuasiconvexa, una solución óptima local es una solución óptima global.

Uniqueness - Sea f alcanza la solución óptima global en dos puntos $ u, v \ en S $

$$ \ Rightarrow f \ left (u \ right) \ leq f \ left (x \ right). \ Forall x \ in S \: \: y \: \: f \ left (v \ right) \ leq f \ izquierda (x \ derecha). \ forall x \ in S $$

Si u es la solución global óptima, $ f \ left (u \ right) \ leq f \ left (v \ right) $ y $ 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 \ izquierda (u \ derecha) $$

lo cual es una contradicción.

Por lo tanto, solo existe una solución óptima global.

Observaciones

• Una función fuertemente cuasiconvexa es también una función estrictamente cuasiconvexa.
• Una función estrictamente convexa puede ser muy cuasiconvexa o no.
• Un estrictamente convexo diferenciable es fuertemente cuasiconvexo.

Sea $ f: S \ rightarrow \ mathbb {R} $ una función diferenciable y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces se dice que f es pseudoconvexo si para cada $ x_1, x_2 \ in S $ con $ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $, tenemos $ f \ left (x_2 \ right) \ geq f \ left ( x_1 \ right) $, o equivalentemente si $ f \ left (x_1 \ right)> f \ left (x_2 \ right) $ entonces $ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right ) <0 $

Función pseudoconcava

Sea $ f: S \ rightarrow \ mathbb {R} $ una función diferenciable y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces se dice que f es pseudoconvexo si para cada $ x_1, x_2 \ in S $ con $ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $, tenemos $ f \ left (x_2 \ right) \ leq f \ left ( x_1 \ right) $, o equivalentemente si $ f \ left (x_1 \ right)> f \ left (x_2 \ right) $ entonces $ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right )> 0 $

Observaciones

• Si una función es tanto pseudoconvexa como pseudoconcava, entonces se llama pseudolinear.

• Una función convexa diferenciable también es pseudoconvexa.

• Una función pseudoconvexa puede no ser convexa. Por ejemplo,

  $ f \ left (x \ right) = x + x ^ 3 $ no es convexo. Si $ x_1 \ leq x_2, x_ {1} ^ {3} \ leq x_ {2} ^ {3} $

  Por lo tanto, $ \ 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 $

  Y $ 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) $

  Por tanto, es pseudoconvexo.

  Una función pseudoconvexa es estrictamente cuasiconvexa. Por lo tanto, cada mínimo local de pseudoconvexo es también mínimo global.

Función estrictamente pseudoconvexa

Sea $ f: S \ rightarrow \ mathbb {R} $ una función diferenciable y S un conjunto convexo no vacío en $ \ mathbb {R} ^ n $, entonces se dice que f es pseudoconvexo si para cada $ x_1, x_2 \ in S $ con $ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $, tenemos $ f \ left (x_2 \ right)> f \ left (x_1 \ right) $, o equivalentemente si $ f \ left (x_1 \ right) \ geq f \ left (x_2 \ right) $ entonces $ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right ) <0 $

Teorema

Sea f una función pseudoconvexa y suponga que $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $ para algunos $ \ hat {x} \ en S $, entonces $ \ hat {x} $ es global óptimo solución de f sobre S.

Prueba

Sea $ \ hat {x} $ un punto crítico de f, es decir, $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $

Como f es una función pseudoconvexa, para $ x \ en S, $ tenemos

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

Por tanto, $ \ hat {x} $ es la solución óptima global.

Observación

Si f es una función estrictamente pseudoconvexa, $ \ hat {x} $ es una solución óptima global única.

Teorema

Si f es una función pseudoconvexa diferenciable sobre S, entonces f es tanto una función estrictamente cuasiconvexa como cuasiconvexa.

Observaciones

• La suma de dos funciones pseudoconvexas definidas en un conjunto abierto S de $ \ mathbb {R} ^ n $ puede no ser pseudoconvexa.

• Sea $ f: S \ rightarrow \ mathbb {R} $ una función cuasiconvexa y S un subconjunto convexo no vacío de $ \ mathbb {R} ^ n $ entonces f es pseudoconvexo si y solo si cada punto crítico es un global mínimos de f sobre S.

• Sea S un subconjunto convexo no vacío de $ \ mathbb {R} ^ n $ y $ f: S \ rightarrow \ mathbb {R} $ una función tal que $ \ bigtriangledown f \ left (x \ right) \ neq 0 $ por cada $ x \ en S $ entonces f es pseudoconvexa si y solo si es una función cuasiconvexa.

Hay cuatro tipos de problemas de programación convexa:

Step 1 - $ min \: f \ left (x \ right) $, donde $ x \ en S $ y S son un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ y $ f \ left (x \ right ) $ es una función convexa.

Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ sujeto a

$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ y $ g_i \ left (x \ right) $ es una función convexa.

$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ y $ g_i \ left (x \ right) $ es una función cóncava.

$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ y $ g_i \ left (x \ right) $ es una función lineal.

donde $ f \ left (x \ right) $ es una función convexa.

Step 3 - $ max \: f \ left (x \ right) $ donde $ x \ en S $ y S son un conjunto convexo no vacío en $ \ mathbb {R} ^ n $ y $ f \ left (x \ right) $ es una función cóncava.

Step 4 - $ min \: f \ left (x \ right) $, donde $ x \ in \ mathbb {R} ^ n $ sujeto a

$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ y $ g_i \ left (x \ right) $ es una función convexa.

$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ y $ g_i \ left (x \ right) $ es una función cóncava.

$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ y $ g_i \ left (x \ right) $ es una función lineal.

donde $ f \ left (x \ right) $ es una función cóncava.

Cono de dirección factible

Sea S un conjunto no vacío en $ \ mathbb {R} ^ n $ y sea $ \ hat {x} \ in \: Closure \ left (S \ right) $, luego el cono de dirección factible de S en $ \ hat {x} $, denotado por D, se define como $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $

Cada vector distinto de cero $ d \ en D $ se llama dirección factible.

Para una función dada $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ el cono de dirección mejorada en $ \ hat {x} $ se denota por F y viene dado por

$$ 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 \} $$

Cada dirección $ d \ en F $ se denomina dirección de mejora o dirección de descenso de f en $ \ hat {x} $

Teorema

Necessary Condition

Considere el problema $ min f \ left (x \ right) $ tal que $ x \ en S $ donde S sea un conjunto no vacío en $ \ mathbb {R} ^ n $. Suponga que f es diferenciable en un punto $ \ hat {x} \ en S $. Si $ \ hat {x} $ es una solución local óptima, entonces $ F_0 \ cap D = \ phi $ donde $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ y D es un cono de dirección factible.

Sufficient Condition

Si $ F_0 \ cap D = \ phi $ f es una función pseudoconvexa en $ \ hat {x} $ y existe una vecindad de $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $ tal que $ d = x- \ hat {x} \ in D $ para cualquier $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, luego $ \ hat {x} $ es la solución local óptima.

Prueba

Necessary Condition

Sea $ F_0 \ cap D \ neq \ phi $, es decir, existe un $ d \ en F_0 \ cap D $ tal que $ d \ en F_0 $ y $ d \ en D $

Desde $ d \ en D $, existe $ \ delta_1> 0 $ tal que $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $

Desde $ d \ en F_0 $, por lo tanto $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $

Por lo tanto, existe $ \ delta_2> 0 $ tal que $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta_2 \ right) $

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

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

Pero $ \ hat {x} $ es la solución local óptima.

De ahí que sea una contradicción.

Entonces $ F_0 \ cap D = \ phi $

Sufficient Condition

Sea $ F_0 \ cap D \ neq \ phi $ nd sea f una función pseudoconvexa.

Supongamos que existe una vecindad de $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ tal que $ d = x- \ hat {x}, \ forall x \ in S \ gorra N_ \ varepsilon \ left (\ hat {x} \ right) $

Sea $ \ hat {x} $ no es una solución óptima local.

Por lo tanto, existe $ \ bar {x} \ en S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ tal que $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $

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

Por pseudoconvexo de 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 $

$ \ Flecha derecha d \ en F_0 $

por lo tanto $ F_0 \ cap D \ neq \ phi $

lo cual es una contradicción.

Por tanto, $ \ hat {x} $ es la solución local óptima.

Considere el siguiente problema: $ min \: f \ left (x \ right) $ donde $ x \ in X $ tal que $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $

$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ y X es un conjunto abierto en $ \ mathbb {R} ^ n $

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

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

Deje $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M ​​\ right \} $ donde I se llama índice establecido para todas las restricciones activas en $ \ hat {x PS

Sea $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M ​​\ right \} $ donde J se llama índice establecido para todas las restricciones activas en $ \ hat {x PS

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

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

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

Lema

Si $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ y X es un conjunto abierto no vacío en $ \ mathbb {R } ^ n $. Sea $ \ hat {x} \ in S $ y $ g_i $ diferentes en $ \ hat {x}, i \ in I $ y dejemos que $ g_i $ donde $ i \ in J $ sean continuos en $ \ hat {x } $, luego $ G_0 \ subseteq D $.

Prueba

Sea $ d \ en G_0 $

Como $ \ hat {x} \ in X $ y X es un conjunto abierto, existe $ \ delta_1> 0 $ tal que $ \ hat {x} + \ lambda d \ in X $ para $ \ lambda \ in \ izquierda (0, \ delta_1 \ derecha) $

Además, dado que $ g_ \ hat {x} <0 $ y $ g_i $ son continuos en $ \ hat {x}, \ forall i \ en J $, existe $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $

Desde $ d \ en G_0 $, por lo tanto, $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $ entonces existe $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, para $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J PS

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

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

$ \ Flecha derecha \ hat {x} + \ lambda d \ in S $

$ \ Flecha derecha d \ en D $

$ \ Flecha derecha G_0 \ subseteq D $

Por lo tanto probado.

Teorema

Necessary Condition

Sea $ f $ y $ g_i, i \ en I $, diferentes en $ \ hat {x} \ en S, $ y $ g_j $ son continuos en $ \ hat {x} \ en S $. Si $ \ hat {x} $ es el mínimo local de $ S $, entonces $ F_0 \ cap G_0 = \ phi $.

Sufficient Condition

Si $ F_0 \ cap G_0 = \ phi $ yf es una función pseudoconvexa en $ \ left (\ hat {x}, g_i 9x \ right), i \ en I $ son funciones estrictamente pseudoconvexas sobre algunos $ \ varepsilon $ de $ \ hat {x}, \ hat {x} $ es una solución local óptima.

Observaciones

• Sea $ \ hat {x} $ un punto factible tal que $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, luego $ F_0 = \ phi $. Por lo tanto, $ F_0 \ cap G_0 = \ phi $ pero $ \ hat {x} $ no es una solución óptima

• Pero si $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, entonces $ G_0 = \ phi $, entonces $ F_0 \ cap G_0 = \ phi $

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

  Dado que $ g \ left (x \ right) = 0 $, entonces $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ y $ g_2 \ left (x \ right) = - g \ izquierda (x \ derecha) \ leq 0 $.

  Deje que $ \ hat {x} \ in S $, luego $ g_1 \ left (\ hat {x} \ right) = 0 $ y $ g_2 \ left (\ hat {x} \ right) = 0 $.

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

  Por lo tanto, $ G_0 = \ phi $ y $ F_0 \ cap G_0 = \ phi $.

Condiciones necesarias

Teorema

Considere el problema - $ min f \ left (x \ right) $ tal que $ x \ en X $ donde X es un conjunto abierto en $ \ mathbb {R} ^ n $ y sea $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.

Sea $ f: X \ rightarrow \ mathbb {R} $ y $ g_i: X \ rightarrow \ mathbb {R} $

Sea $ \ hat {x} $ una solución factible y sean f y $ g_i, i \ en I $ diferenciables en $ \ hat {x} $ y $ g_i, i \ en J $ son continuas en $ \ hat { x} $.

Si $ \ hat {x} $ resuelve el problema anterior localmente, entonces existe $ u_0, u_i \ in \ mathbb {R}, i \ in I $ tal que $ u_0 \ bigtriangledown f \ left (\ hat {x} \ derecha) + \ Displaystyle \ sum \ limits_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0

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

Además, si $ g_i, i \ en J $ también son diferenciables en $ \ hat {x} $, entonces las condiciones anteriores se pueden escribir 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 $

Observaciones

• $ u_i $ se denominan multiplicadores lagrangianos.

• La condición de que $ \ hat {x} $ sea factible para el problema dado se llama condición factible primaria.

• El requisito $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ se llama factibilidad dual condición.

• La condición $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ se llama condición de holgura complementaria. Esta condición requiere $ u_i = 0, i \ in J $

• Juntas, la condición de factibilidad primaria, la condición de factibilidad dual y la holgura complementaria se denominan Condiciones de Fritz-John.

Condiciones suficientes

Teorema

Si existe un $ \ varepsilon $ -vecino de $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ tal que f es pseudoconvexo sobre $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ y $ g_i, i \ in I $ son estrictamente pseudoconvexos sobre $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, luego $ \ hat { x} $ es la solución local óptima al problema descrito anteriormente. Si f es pseudoconvexa en $ \ hat {x} $ y si $ g_i, i \ en I $ son funciones estrictamente pseudoconvexas y cuasiconvexas en $ \ hat {x}, \ hat {x} $ es la solución global óptima al problema descrito arriba.

Ejemplo

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

  tal que $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ Y $ \ hat {x} = \ left (2 , 1 \ derecha) $

  Sea $ 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 $ y $ g_4 \ left (x_1, x_2 \ right) = -x_2 $.

  Por lo tanto, las restricciones anteriores se pueden escribir 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 $ y

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Por lo tanto, $ I = \ left \ {1,2 \ right \} $ por lo tanto, $ 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 ) $ y $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  Así, poniendo estos valores en la primera condición de las condiciones de Fritz-John, obtenemos:

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ y sea $ u_2 = 1 $, por lo tanto $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  Así se cumplen las condiciones de Fritz John.

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

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

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

  Deje $ 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 $

  Por lo tanto, las restricciones anteriores se pueden escribir como:

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

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

  Por lo tanto, $ 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) $ y $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right PS

  Así, poniendo estos valores en la primera condición de las condiciones de Fritz-John, obtenemos:

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

  Así se cumplen las condiciones de Fritz John.

Considere el problema:

$ min \: f \ left (x \ right) $ tal que $ x \ en X $, donde X es un conjunto abierto en $ \ mathbb {R} ^ n $ y $ g_i \ left (x \ right) \ leq 0, yo = 1, 2, ..., m $

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

Sea $ \ hat {x} \ en S $ y deje que $ f $ y $ g_i, i \ in I $ sean diferenciables en $ \ hat {x} $ y $ g_i, i \ in J $ sean continuos en $ \ hat {x} $. Además, $ \ bigtriangledown g_i \ left (\ hat {x} \ right), i \ en I $ son linealmente independientes. Si $ \ hat {x} $ resuelve el problema anterior localmente, entonces 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 $

Si $ g_i, i \ en J $ también son diferenciables en $ \ hat {x} $. luego $ \ hat {x} $, luego

$ \ 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 $

Ejemplo

Considere el siguiente problema:

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

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

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

Deje que $ 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} $ y $ g_4 \ left (x_1, x_2 \ right) = - x_2 $

Por lo tanto, las restricciones anteriores se pueden escribir 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, $ y $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Por lo tanto, $ I = \ left \ {1,2 \ right \} $ por lo tanto , $ 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 ) $ y

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

Por lo tanto, poniendo estos valores en la primera condición de las condiciones de Karush-Kuhn-Tucker, obtenemos:

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

Por tanto, se cumplen las condiciones de Karush-Kuhn-Tucker.

Método de descenso más empinado

Este método también se denomina método de gradiente o método de Cauchy. Este método implica las siguientes terminologías:

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

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

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

Al diferenciar $ \ phi $ y equipararlo a cero, podemos obtener $ \ alpha $.

Entonces, el algoritmo es el siguiente:

• Inicialice $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ y establezca $ k = 0 $.

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

• encuentra $ \ alpha_k $ de manera que minimice $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.

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

• Si $ \ left \ | x_ {k + 1-x_k} \ right \ | <\ varepsilon_1 $ o $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, vaya al paso 6, de lo contrario establezca $ k = k + 1 $ y vaya al paso 2.

• La solución óptima es $ \ hat {x} = x_ {k + 1} $.

Método Newton

El método Newton funciona según el siguiente principio:

$ 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) $

En $ 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 que $ x_ {k + 1} $ sea la solución óptima $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $

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

Aquí $ H \ left (x_k \ right) $ no debería ser singular.

Por lo tanto, el algoritmo es el siguiente:

Step 1 - Inicialice $ x_0, \ varepsilon $ y establezca $ k = 0 $.

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

Step 3 - Resuelva para el sistema lineal $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ para $ h \ left (x_k \ right) $.

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

Step 5- Si $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ o $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ luego vaya al paso 6, de lo contrario configure $ k = k + 1 $ y vaya al paso 2.

Step 6 - La solución óptima es $ \ hat {x} = x_ {k + 1} $.

Método de gradiente conjugado

Este método se utiliza para resolver problemas de los siguientes tipos:

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

donde Q es una matriz nXn definida positiva y b es constante.

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

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

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

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

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

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

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

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

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

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