OPTMIZACION NUMERICA: UNIDIRECCIONAL Y UNIDIMENSIONAL

1. Unidireccional:

Una buena técnica de optimización de funciones de una única variable es fundamental por al menos tres
razones:
1. En muchos problemas las restricciones se pueden incluir dentro de la función objetivo, por lo que la
dimensionaliad del problema se reduce a una variable.
2. Algunos problemas sin restricciones, inherentemente incluyen una única variable
3. Las técnicas de optimización con y sin restricciones, generalmente incluyen pasos de búsqueda
unidireccional en sus algoritmos.

Antes de la aparición de los ordenadores de alta velocidad, los métodos de optimización estaban
prácticamente limitados a los métodos indirectos en los cuales el cálculo del extremo potencial estaba
restringido al uso de derivadas y las condiciones necesarias de optimalidad. Los modernos ordenadores han
hecho posible los métodos directos, esto es la búsqueda de un óptimo por comparación sucesiva de los valores
de la función f(x) en una secuencia de puntos x1, x2, x3... sin la necesidad de hacer intervenir derivadas
analíticas. Para llevar a cabo los métodos directos de minimización numérica solamente se usa el valor de la
función objetivo. Se comienza con un valor inicial de x y se continua seleccionando valores de x de acuerdo
con una estrategia pre-seleccionada. El proceso termina cuando f ( x k +1 )−f ( x k ) < ε donde el superíndice k
designa el número de iteración y ε es la tolerancia pre-especificada o criterio de tolerancia. Los métodos
indirectos tienen la ventaja inherente de que la convergencia es generalmente más rápida incluso aun cuando
se utilicen métodos numéricos para calcular las derivadas. Sin embargo, en problemas de ingeniería esta

ventaja es muchas veces neutralizada. (simulación y optimización de procesos quimicos, 2011)

1.1. Acotación del optimo Casi todos los procedimientos de búsqueda unidimensional
requieren que el óptimo esté acotado dentro de un intervalo conocido como primer punto de la
estrategia de búsqueda. Existen varias estrategias que se pueden usar para acotar el óptimo, la más
sencilla consiste en fijar un punto y comenzar a movernos una distancia fija en una dirección.
(simulación y optimización de procesos quimicos, 2011)

1.2.Métodos directos Han sido desarrollado básicamente tres método

1.- Método de Newton

2.- Aproximaciones finitas al método de Newton (Métodos cuasi-Newton)
3.- Métodos de secante.
Para calcular la capacidad de eficacia útil examinar la velocidad con que convergen

‖x k−1−x ¿‖
Lineal ≤ c 0≤ c ≤1
‖ x k −x ¿‖
 ‖x k−1−x ¿‖
Orden p p
≤ c c> 0; p ≥ 1 (el más rápido en la práctica)
‖ x k −x ¿‖

‖x k−1−x ¿‖
Súper lineal lim →0 (habitualmente rápido)
k → ∝ ‖ x −x ‖
k ¿

METODO DE NEWTON De acuerdo con la primera condición necesaria para que una función tuviera

un mínimo local se debe cumplir que f ' x  0 Por lo tanto podemos aplicar el método de Newton a la
derivada. (simulación y optimización de procesos quimicos, 2011)

f ' ( xk)
x k+1=x k −
f {(x} ^ {k} ) ¿
Aseguramos que en la etapa k .f(x k+1)<f(xk), para minimización. Realmente lo que hace el método de
newton es aproximar la función por una función cuadrática en xk.

f ( x )=f ( x ) +f ( x ) ( x−x
k ' k k+1
) + 1 f ' ' ( x)(x−x k )2
2

Y dado que f’(x)=0, diferenciando la ecuación anterior

1 '' k
f ( x ) + 2 f ( x ) ( x−x ) =0
' k k
2
Las ventajas
 El procedimiento es cuadráticamente convergente (p=2), siempre que f´’’(x) sea diferente de cero
 Para una función de exponente 2 el mínimo se obtiene en una iteración

Las desventajas
 Se debe calcular tanto f’(x) como f’’(x)
 Si f ' ' ( x) → 0 el método converge muy lentamente
 Si existe más de un extremo, el método podría no converger al extremo deseado.

METODO DE NEWTON EN DIFERENCIAS FINITAS los método en diferentes finitas tipo Newton, se
utilizan si la derivada de la función objetiva es complicada de obtener, o ésta viene dada de forma numérica.
Consisten en reemplazar las derivadas por aproximaciones en diferencias finitas. (simulación y optimización
de procesos quimicos, 2011)

METODO DE SECANTE
Los métodos de secante toman los dos puntos de ; x p y xq y resuelve una ecuación muy similar a la dada en el
método de Newton.

f ( x ) +m ( x−x )=0
' k k

Donde m es la pendiente de la línea que intersecta xp con xq dad por :

q q p
f ' ( x )( x −x )
m=
[ f ' ( x q ) −f '( x p )]

METODO DE ELIMINACION DE REGION Los métodos de eliminación de región para una búsqueda
unidimensional se basan en eliminar una región, en cada etapa, del intervalo en el que está comprendido el
mínimo. Cuando la región posible es suficientemente pequeña la búsqueda termina. El elemento básico dentro
del sistema de eliminación de regiones es la comparación de valores de f(x) en dos o más puntos dentro del
intervalo de x. Debemos asumir que f(x) es unimodal, y que tiene un mínimo (es convexa) dentro de [a, b].
(simulación y optimización de procesos quimicos, 2011)
Según la (universidad de carabobo, s.f.).Si partimos de dos puntos de test sean x1, x2 deberíamos elegirlos de
tal manera que la búsqueda fuera lo más eficiente posible. Si usamos un espaciado igual, esto es x a b x x x 1
− = − 2 = 2 − 1 el método de búsqueda se llama ‘búsqueda de dos puntos a intervalos iguales’. El intervalo de
incertidumbre se reduce en 1/3 en cada iteración. Así si L0 es la longitud del intervalo original (b-a) y Lk es el
intervalo después de k iteraciones, como en cada iteración se llevan a cabo dos evaluaciones de la función
objetivo, entonces Lk tras k iteraciones viene dado por:

1 k
Lk =( ) L0
2
la estrategia empleada en el método de la sección aurea es localizar dos puntos interiores del intervalo
eliminando en cada iteración de tal manera que se cumpla la relación

METODOS DE APROXIMACION POLINOMICA

Otra clase de métodos de minimización unidimensional localizan un punto x cercano a x*, el valor de la
variable independiente correspondiente al mínimo de f(x), por interpolación y extrapolación utilizando
aproximaciones polinómicas a f(x). Se han propuesto tanto aproximaciones cuadráticas como cúbicas usando
tanto los valores de la función solamente como los de sus derivadas primeras. Se ha comprobado que los
métodos de interpolación polinómica son normalmente ligeramente mejores que el método de la sección
áurea. (universidad de carabobo, s.f.)
ITERPOLACION CAUDRATICA Nos basamos en la (universidad de carabobo, s.f.)Si comenzamos con
tres puntos, por ejemplo x1, x2, x3 en orden creciente, y no necesariamente igualmente espaciados, pero
contenidos dentro de la zona de búsqueda (a,b), podemos aproximarlos a un polinomio de grado 2,
f(X)=a+bx+cx2 de tal manera que dicho polinomio pasa exactamente por esos tres puntos y debe presentar un
mínimo en:
¿ −b
x=
2c
Si suponemos que f(x) se evalúa en los 3 puntos, podríamos obtener los valores de a,b,c resolviendo el
sistema de ecuaciones

Lo que nos lleva afirmar que:

Con f 1 ≡ f ( x 1 ) ; f 2 ≡( x ¿¿ 2); f 3 ≡( x ¿¿ 3)¿ ¿

La primera etapa del procedimiento está representado de la siguiente manera:

ITERPOLACION CUBICA “La interpolación cúbica en la búsqueda de un óptimo se basa en la

aproximación de la función objetivo por un polinomio de tercer grado dentro del intervalo de interés, y
determinar el punto estacionario asociado con el polinomio. Para realizar la interpolación cúbica hacen falta
cuatro puntos o dos puntos con sus respectivas derivadas. (simulación y optimización de procesos quimicos,
2011).En el caso de que se evalúen cuatro puntos, tenemos que aparece un sistema de cuatro ecuaciones
lineales con cuatro incógnitas (los coeficientes del polinomio).
Aplicaciones en métodos unidireccionales
Método de Newton
En análisis numérico, el método de Newton (conocido también como el método de Newton-
Raphson o el método de Newton-Fourier) es un algoritmo eficiente para encontrar
aproximaciones de los ceros o raíces de una función real. También puede ser usado para encontrar
el máximo o mínimo de una función, encontrando los ceros de su primera derivada.

Descripción del método

El método de Newton-Raphson es un método abierto, en el sentido de que su convergencia global
no está garantizada. La única manera de alcanzar la convergencia es seleccionar un valor inicial lo
suficientemente cercano a la raíz buscada. Así, se ha de comenzar la iteración con un valor
razonablemente cercano al cero (denominado punto de arranque o valor supuesto). La relativa
cercanía del punto inicial a la raíz depende mucho de la naturaleza de la propia función; si ésta
presenta múltiples puntos de inflexión o pendientes grandes en el entorno de la raíz, entonces las
probabilidades de que el algoritmo diverja aumentan, lo cual exige seleccionar un valor supuesto
cercano a la raíz. Una vez se ha hecho esto, el método linealiza la función por la recta tangente en
ese valor supuesto. La abscisa en el origen de dicha recta será, según el método, una mejor
aproximación de la raíz que el valor anterior. Se realizarán sucesivas iteraciones hasta que el
método haya convergido lo suficiente.

Sea f : [a, b] -> R función derivable definida en el intervalo real [a, b]. Empezamos con un valor
inicial x0 y definimos para cada número natural n

Donde f ' denota la derivada de f.

Nótese que el método descrito es de aplicación exclusiva para funciones de una sola variable con
forma analítica o implícita cognoscible. Existen variantes del método aplicables a sistemas
discretos que permiten estimar las raíces de la tendencia, así como algoritmos que extienden el
método de Newton a sistemas multivariables, sistemas de ecuaciones, etc.
Ilustración de una iteración del método de Newton (la función f se demuestra en azul y la línea de
la tangente está en rojo). Vemos que xn + 1 es una aproximación mejor que xn para la raíz x de la
función f.

Método de la secante

En análisis numérico el método de la secante es un método para encontrar los ceros de una
función de forma iterativa.
Es una variación del método de Newton-Raphson donde en vez de calcular la derivada de la
función en el punto de estudio, teniendo en mente la definición de derivada, se aproxima la
pendiente a la recta que une la función evaluada en el punto de estudio y en el punto de la

iteración anterior. Este método es de especial interés cuando el coste computacional de derivar la
función de estudio y evaluarla es demasiado elevado, por lo que el método de Newton no resulta
atractivo.
En otras palabras, el método de la secante es un algoritmo de la raíz de investigación que utiliza
una serie de raíces de las líneas secantes para aproximar mejor la raíz de una función f. El método
de la secante se puede considerar como una aproximación en diferencias finitas del método de
Newton-Raphson. Sin embargo, este método fue desarrollado independientemente de este
último.
El método se define por la relación de recurrencia:

Como se puede ver, este método necesitará dos aproximaciones iniciales de la raíz para poder
inducir una pendiente inicial.

Dos primeras iteraciones del método de la secante.

PRESENTACIÓN DEL PROBLEMA

La ecuación de una ola estacionaria reflejada en un puerto está dada por:

[
h=h0 sen ( 2λπ )cos ( 2 πxλ )+e
−x
]
Para  16 , t=12, v=48, h=0.4h0, (40% de la altura inicial)

Movimiento de las moléculas de agua, en la zona superficial del mar, provocado por la acción del
viento. En este movimiento, que es originariamente circular, no hay desplazamiento horizontal de
dichas moléculas ni de la masa de agua por ellas constituida, aunque sí lo hay del movimiento
ondulatorio generado por ese movimiento molecular. Este tipo de olas, que se originan en alta
mar, se conocen con el nombre de 'olas libres' u 'olas estacionarias'.

Cuando una ola se aproxima a la costa, el movimiento típico del mar libre, movimiento circular, se
transforma, por rozamiento con el fondo, en un movimiento elíptico; la cresta de la ola avanza por
este motivo más deprisa que su punto opuesto en la vertical y se produce un desplazamiento
horizontal de la masa de agua que provoca la ruptura de la ola al llegar a la costa.

Estela de ola formada por el paso de un barco.

Para nuestro caso nos dan la ecuación respectiva de la ola junto con varios parámetros de esta
tales como la longitud de onda, las alturas respectivas, la velocidad, el tiempo y nos piden hallar la
distancia donde rompe la ola dada por x.

Debido a la presencia de por ejemplo la función logarítmica estamos en presencia de una ecuación
no lineal y se procederá a hallar las soluciones mediante los métodos anteriormente descritos.

DESCRIPCIÓN DE LA SOLUCIÓN
Para hallar la solución dada se pueden aplicar varios métodos enseñados en el curso de Análisis
Numérico, tales como de Aproximaciones Sucesivas, El método de Newton, Método de la secante,
etc. Para hallar nuestra solución se uso el método de Newton debido a su rápida convergencia en
hallar la solución, así como el más fácil de entender y aplicar, se comprobaron dichos resultados
con el método de la secante obteniéndose los mismos valores de x.

Determinando la solución positiva más pequeña:

La solución más pequeña positiva se encuentra en el intervalo [5,10].

Se halla la solución positiva más pequeña a través de 2 métodos.

I. Usando el método de Newton

Se halla un punto inicial correspondiente:

Como f(c)*f’(c) > 0, se tiene un punto inicial y se puede proseguir.

II. Usando el método de la secante

Se escogen otras variables y se expresa la correspondiente expresión para el método de la secante
modificado desarrollado en clase:
RESULTADOS
En el problema de la onda estacionaria se tiene una ecuación periódica debido a la presencia de la
variable independiente x dentro de una función seno, por lo tanto vamos a tener múltiples
respuestas debido a la periodicidad de esta función.

La solución a la ecuación de la ola estacionaria estará dada en los puntos donde f(x) tienen a cero.
Para valores de x donde la función periódica f(x) es igual a cero se tendrán las soluciones para x.
De la gráfica se observa para valores negativos o pequeños de x e-x tiene un efecto considerable
mientras que cuando x tiende a valores mayores e-x tiende a cero por lo que no influye mayor en
la solución, mientras que por lo tanto la función quedaría de la forma:
f(x) = A*sin(K*x) - 0.4
Donde se ve claramente que van a ver infinitas soluciones de x para lo cual f(x) = 0.
Se tendrán infinitas soluciones de x para f(x) = 0, ya que la función seno desplazada 0.4 hacia abajo
corta al eje horizontal cada π radianes, donde 2π es el período de la onda.

En matemática, una función es periódica si los valores de la función se repiten conforme se añade
a la variable independiente un determinado período, o sea:
, donde P es el período.
Las funciones trigonométricas, tales como la función seno o coseno, son casos típicos de funciones
periódicas, en las que su período es de 360 grados.
Al tener la función periódica K seno(2πx/λ) todos los valores donde sea x=x' el valor donde la
función tiende a cero y nos da la solución, para valores de (2π/λ)(x'+λ*n), se tendrán nuevos
valores de x''= x'+λ*n donde n=0,1,2,3,4...N.

CONCLUSIONES
Debido a la naturaleza oscilatoria de las ondas del mar, se tendrán múltiples respuestas sin
embargo se considerará a la solución fundamental a la solución más pequeña positiva.

Se tienen infinitos cruces de la función por cero debido a que para grandes valores de x la función
exponencial tiene a cero, quedando solo la ecuación seno multiplicada por una constante y
desplazada para abajo en 0.4, por lo tanto, corta al eje horizontal 2 veces en cada periodo.

Al hallar las 2 primeras soluciones, se puede ver que las demás soluciones son simplemente
soluciones iguales desplazadas en 2π radianes. Esto se da debido a que sen(x)=sen(x+2π).
En este trabajo se pudo comprobar la eficacia de estos métodos iterativos, encontrando
satisfactoriamente la respuesta y se vio que, a pesar de tener términos no lineales como la función
exponencial, estos sólo prevalecen para una región del problema, que en nuestro caso para hallar
la solución prácticamente no tiene mayor efecto en los valores finales.

OPTIMIZACIÓN NUMÉRICA MULTIDIMENSIONAL

1. INTRODUCCIÓN:

- La optimización o programación matemática intenta dar respuesta a un tipo

general de problemas donde se desea elegir el mejor entre un conjunto de
elementos.
La localización de raíces y la optimización están relacionadas, en el sentido de
que ambas involucran valores iniciales y búsqueda de un punto sobre una
función.

2. OBJETIVOS:

- Comprender el concepto de optimización y orientarlo a resolver problemas

prácticos de ingeniería.
- Diferenciar entra localización de raíces y optimización.
- Comprender la importancia que esta tiene en el campo de la ingeniería.
- Utilizar herramientas informáticas (Excel, Matlab, Mathcad) para resolver
problemas de optimización.

3. MÉTODOS DIRECTOS
- Los métodos directos no hacen uso de la información proporcionada para las
derivadas. Bajo estas circunstancias, estos métodos se pueden usar con bastante
efectividad, pero son muy ineficientes comparados con los métodos discutidos
anteriormente (Optimización Numérica Unidimensional).
- Tienen ventaja de que estos métodos son muy simples de entender y muy fáciles
de ejecutar.
3.1. MÉTODOS DE BÚSQUEDA ALEATORIA
- Un método aleatorio simplemente selecciona un vector inicial x0, evalúa la
función objetivo en ese punto y entonces aleatoriamente selecciona otro vector
x1. Tanto la dirección de búsqueda como la longitud de búsqueda son elegidas
simultáneamente. Después de una o más etapas, el valor de f (x k) se compara
con el mejor valor previo de f(x) y se toma la decisión de continuar o terminar el
procedimiento. Existen diversas variaciones de este algoritmo, aunque
estrictamente hablando sólo se alcanza la solución cuando k → ∞, pero desde un
punto de vista práctico, si el objetivo tiene una forma muy plana se pueden
encontrar soluciones subóptimas bastante aceptables. Aunque el método es
bastante ineficiente por sí mismo, puede dar valores aceptables de partida para
otros métodos.

3.2. MÉTODOS DE BÚSQUEDA EN REJILLA

- Los métodos básicos de diseño de experimentos discutidos en muchos textos de
estadística, se pueden aplicar también a minimización de funciones. Se pueden
seleccionar una serie de puntos alrededor de un punto base de referencia, de
acuerdo a algunos de los diseños del tipo que se muestra en la siguiente figura.
Después se pasa al punto que más mejora la función objetivo y se continua la
búsqueda. Sin embargo, el sistema es muy ineficaz, por ejemplo, con n=10 y
una búsqueda factorial a tres niveles deberíamos realizar 310-1=59048
evaluaciones de la función objetivo, lo cual es obviamente prohibitivo.
- Otro método muy sencillo de optimización consiste en seleccionar n direcciones
fijas de búsqueda, para n variables, (habitualmente los ejes coordenados) de tal
manera que f(x) se minimiza de forma secuencial usando búsquedas
unidimensionales en cada una de las direcciones previamente seleccionadas. El
método suele ser bastante ineficaz incluso llegando a puntos muy alejados del
óptimo de los cuales no puede salir.

3.4. MÉTODO SIMPLEX FLEXIBLE

- Este método se basa en tomar una figura regular (conocida como simplex) como
base. Así en 2 dimensiones tal figura debería ser un triángulo equilátero. Los
experimentos se localizan de tal manera que la función objetivo se evalúa en
cada uno de los vértices que forman la figura geométrica. Los valores de la
función objetivo obtenida en cada uno de los vértices se comparan entre sí
rechazando el peor valor de todos formando una nueva figura geométrica por
reflexión del peor de los puntos respecto a los que no han sido rechazados. En el
simplex original se mantiene la figura geométrica, mientras que la modificación
de Neadler y Mead permite distorsiones de ésta para acelerar el proceso de
búsqueda. Veamos de forma sistemática cada uno de los pasos del simplex:

3.4.1. SELECCIÓN DE LA FIGURA “SIMPLEX” INICIAL:

- Para visualizarlo de forma sencilla comenzaremos con el caso de dos
dimensiones. Así la distancia entre un punto x1= (x11, x12) y otro x2= (x21,
x22) viene dada por la expresión:

procediendo de tal manera las distancias entre dos puntos vendrán dadas por una
expresión similar.
 2 3!
como tenemos tres puntos podemos hacer C 3= =3 , así en dos dimensiones
2! 1 !
(3 vértices) podemos definir tres distintas entre vértices (todas ellas iguales). Por
lo tanto, especificando un punto base x1 el punto x2 estará localizado en un punto
cualquiera de una circunferencia de radio “a” centrada en x1. Una vez elegido el
punto x2, el punto x3 deberá estar en la intersección entre las circunferencias de
radio “a” centradas en x1 y en x2 respectivamente. Existen dos posibilidades.

De forma similar en n dimensiones tenemos n+¿ 1 puntos. La tabla siguiente es

una

propuesta para comenzar un simplex de n variables cuando x1 es el origen.

 Si en lugar del origen se toma cualquier otro punto x1 basta realizar una
traslación.
Se puede encontrar otra serie de puntos, pero este es uno de los más simples
para hallar p y q y la condición de que formen parte de la figura simplex, se
puede aplicar a cada par de puntos; así entre los puntos 1 y 2:

Entre los puntos 2 y 3:

Resolviendo el sistema:

Una vez fijada la figura inicial del simplex, se sigue una búsqueda secuencial,
en la que en cada paso se eliminará un vértice y se incluirá otro nuevo.
(supondremos que queremos minimizar).

Paso 0:

- Calcular la función objetivo en cada uno de los puntos (vértices), hallar el

vértice con el valor máximo “Qmáx” el vértice con valor mínimo “Qmín” y el
centroide de todos los vértices excepto aquel que ha dado el peor valor:

El procedimiento a seguir a continuación consiste en calcular un nuevo vértice y

eliminar aquel que dio un peor valor. (Qmáx)
 Paso 1:

- Se calcula un nuevo vértice ⃗

Q cuyas ordenadas son:

Donde y r es el llamado coeficiente de reflexión, una cantidad positiva que

generalmente suele ser la unidad. Realmente lo que hemos hecho ha sido reflejar
el punto con el peor valor respecto al centroide. Las siguientes figuras lo ilustran
para el caso de 2 y 3 variables.

Después de la reflexión pueden ocurrir tres posibilidades:

(a) Si se reemplaza el vértice por Q *, se recalcula Qmáx y

B(centroide) y se vuelve a la etapa 1.

(b) Si

Donde y c es un coeficiente de expansión, generalmente 2.

 (c) Si Q*>Qi excepto de Qmáx se lleva a cabo una “Contracción” obteniéndose un
nuevo punto Q***.

Donde y c es un coeficiente de contracción, generalmente 0.5. Y se vuelve al

punto 1, excepto en el caso que el nuevo vértice sea peor Q máx en cuyo caso
se sigue con c1.

3.5. DIRECCIONES CONJUGADAS. MÉTODO DE POWELL

- La experiencia ha demostrado que las direcciones llamadas conjugadas son
mucho más efectivas como direcciones de búsqueda que otras como pueden ser
la búsqueda univariante o las direcciones ortogonales.
Dos direcciones si y sj se dice que son conjugadas una con respecto a la otra si:

En general un conjunto de n direcciones de búsqueda linealmente

independientes s0,s1,s2,…sn-1 se dice que son conjugadas con respecto a una
matriz definida positiva Q si:

En optimización la matriz Q es la matriz hessiana de la función objetivo, H. Para

una función cuadrática f(x) de n variable, para la cual H es una matriz constante
está garantizado que se obtiene el óptimo de n etapas de búsqueda
unidireccional si se obtiene exactamente el mínimo de cada etapa. Una dirección
conjugada en general no es una dirección única. Sim embargo, en dos
dimensiones, si se elige una dirección s1 y Q s2 queda completamente
especificada.
La ortogonalidad es un caso especial de la conjugación cuando Q=I, Aunque es
corriente encontrar en la bibliografía conjuntos de métodos conocidos como de
direcciones conjugadas estas, estrictamente hablando sólo existen para
funciones cuadráticas o aproximaciones cuadráticas de la función objetivo en la
etapa k.

¿Cómo se puede calcular las direcciones conjugadas sin usar derivadas? Este es
un concepto básico que lo referiremos a la siguiente figura. Comenzamos con el
punto x0. Localizamos el punto xa que es el mínimo en una dirección cualquiera
s. Elegimos otro punto cualquiera (distinto del primero) x1, y localizamos el
punto xb que es el mínimo partiendo del punto x1 en la misma dirección s. Los
puntos xa y xb se obtienen minimizando f(x0+ λ s) con respecto a λ admitiendo
que f(x) es una función cuadrática:
 Se puede demostrar que el óptimo de una función cuadrática cae en la línea que
une a xa co xb. Sim embargo esta última afirmación no es válida para otro tipo de
funciones.

Powell desarrollo un método basado en las direcciones conjugadas aplicable a

cualquier tipo de funciones. Aunque Powell introdujo importantes
modificaciones a su método para conseguir la adaptación. El método sigue una
serie de pasos:

Paso 1:
- El método comienza realizando una búsqueda en n direcciones linealmente
independientes que suelen tomarse paralelos a los ejes
coordenados.
Partiendo del punto base x0 se lleva a cabo una búsqueda unidimensional en la
dirección s01 para llegar al punto x 01 . Este punto ( x 01) se toma como punto de
partida para una nueva búsqueda unidireccional, en este caso en la dirección s02,
y así sucesivamente hasta acabar en el punto x 0n.

Paso 2:
- Buscamos el punto particular x 0k para el cual se ha obtenido una mejoría mayor
de la función objetivo respecto al punto anterior x 0k−[Link] dos
magnitudes:
 Paso 3:
- Determinamos:

Y llevamos a cabo dos comparaciones.

Entonces la dirección μ no es una buena dirección de búsqueda y repetiríamos la

búsqueda comenzando desde el punto x n0 como punto base. En caso contrario se
procede a incorporar la dirección μal conjunto de direcciones de búsqueda,
sustituyendo a la dirección que peor resultado hubiese obtenido.
En la nueva etapa de búsqueda conviene que la última dirección investigada (en
la etapa de búsqueda unidireccional) sea μ.
Las dos desigualdades anteriores comprueban, la primera si se obtiene una
mejora en la dirección al pasar del punto x 00, y la segunda, que la función
descienda de manera pronunciada y no a través de una zona plana.
4. MÉTODOS INDIRECTOS: MÉTODOS DE PRIMER ORDEN.
- Los métodos indirectos, en contraste con los métodos descritos en las secciones
previas hacen uso de las derivadas en la determinación de la dirección de
búsqueda. Sim embargo, nuestra calificación en métodos directos e indirectos,
podría no estar clara del todo debido a la aproximación de las derivadas por
diferencias finitas, lo que estrictamente hablando hace a estos métodos “libres
de derivadas”. Una buena dirección de búsqueda debería reducir (para
minimización) la función objetivo, de tal manera que si x0 es el punto inicial y x1
es un nuevo punto:

Una dirección s es llamada de descenso si satisface la siguiente relación en un

punto dado:

4.1. MÉTODO DEL GRADIENTE (MÁXIMO DESCENSO)

- Se recordará que el gradiente es un vector en un punto x que proporciona la
dirección (local) de máxima variación de la función. El vector gradiente es un
vector ortogonal al contorno de la función en el punto. Por lo tanto, en la
búsqueda de un mínimo la dirección de movimiento será contragradiente:

En el método de máximo descenso la transición de un punto x k a otro xk+1 viene

dada por la siguiente expresión:

Donde:
El gradiente negativo da la dirección de movimiento, pero no la longitud de
dicho movimiento. Por lo tanto, existen varios procedimientos posibles
dependiendo de la elección de λ k. Entre los diversos métodos que existen para la
selección de la longitud de paso, dos merecen una mención especial. El primero
de ellos emplea una búsqueda unidireccional en la dirección del gradiente. El
segundo especifica a priori la longitud del paso para cada iteración. Claramente
la principal dificultad con la segunda aproximación es que a menudo no se sabe
a priori la longitud de paso adecuada. ¿Cómo se debería cambiar esta longitud
de paso y como debería reducirse a medida que nos aproximamos al mínimo
para conseguir la convergencia? Una ilustración nos indicará el problema:
Supongamos una función cuadrática de dos variables como de la figura
siguiente:

Si en cada paso se realiza una optimización total en la dirección contraria al

gradiente los pasos sucesivos del método máximo descenso son ortogonales uno
con respecto al anterior. Este resultado, que parece peculiar, ocurre para una
determinada f(x) debido a que la derivada de f(x) a lo largo de la línea s( λ ) viene
dado, utilizando la regla de la cadena por:
En el paso final de la búsqueda queremos que y, por lo tanto
En la práctica, por lo tanto, no es deseable llevar a cabo suboptimizaciones con
demasiada precisión. Mientras que el método del gradiente puede producir
progresos muy satisfactorios en la reducción de f(x) en las primeras iteraciones
tiende a hacerse muy lento en las últimas. Alargando excesivamente los
cálculos.

El algoritmo práctico lo podemos reducir en los siguientes pasos:

Un método estricto de descenso máximo puede terminar en cualquier punto

estacionario, es decir, puede llegar a un mínimo local o a un punto de silla. Para
asegurarnos que tipo de resultado hemos obtenido debemos asegurarnos que la
matriz Hessiana es definida positiva. Por otra parte, la dificultad básica del
método de gradiente es que es muy sensible al escalado de f(x) por lo que la
convergencia puede ser muy lenta y producirse un número enorme de
 oscilaciones. Desde este punto de vista el método del gradiente no es muy
efectivo.

4.2. MÉTODO DEL GRADIENTE CONJUGADO

- El método del gradiente conjugado debido a Fletcher y Reeves (1964) combina
las características de la convergencia cuadrática del método de las direcciones
conjugadas con las del método del gradiente. El método supone una importante
mejora del método del gradiente con sólo un pequeño incremento en el esfuerzo
de cálculo. El método del gradiente conjugado, esencialmente, combina la
información obtenida del vector gradiente con la información acerca del vector
gradiente de iteraciones previas. Lo que hace el método es calcular la nueva
dirección de búsqueda utilizando una combinación lineal del gradiente en la
etapa considerada y el de la etapa anterior. La principal ventaja del método es
que necesita almacenar muy poca cantidad de información con lo que puede ser
programado fácilmente incluso en calculadoras.

Los pasos de cálculo se comentan a continuación:

 Para la Función cuadrática se puede demostrar que dos direcciones de búsqueda
son conjugadas. Después de n iteraciones conviene comenzar otra vez desde el
principio tomando el último punto k=n como nuevo punto de partida.

Algunas de las dificultades que aparecen en el método de Powell también aparecen

en el método del gradiente conjugado. Se puede producir una dependencia lineal de
las direcciones de búsqueda. Esto se puede eliminar reiniciando el proceso cada
cuatro o cinco etapas completas.

5. MÉTODOS INDIRECTOS: MÉTODOS DE SEGUNDO ORDEN

- Desde el punto de vista de las direcciones de búsqueda el método del máximo
descenso se puede interpretar como un movimiento ortogonal a una
aproximación lineal (tangente) a la función objetivo en el punto xk. Examinemos
ahora la siguiente figura y realicemos una aproximación cuadrática de f(x) en xk.
 Donde H(x) es la matriz Hessiana evaluada en el punto x k. Por lo tanto, es
posible tener en cuenta la curvatura de la función en las proximidades del punto
de forma análoga a como se hacía en el método de Newton.
5.1.

EL MÉTODO DE NEWTON
- El método de Newton hace uso de la aproximación de segundo orden de la
función utilizando las derivadas segundas con respecto a cada una de las
variables independientes. De esa forma es posible tener en cuenta la curvatura
de la función en el punto e identificar las mejores direcciones de búsqueda.
El mínimo de f(x) se obtiene diferenciando la aproximación cuadrática de f(x)
con respecto a cada una de las variables e igualando a cero. Así:

Si f(x) es una función cuadrática el mínimo se alcanza en un único paso. Pero

para una función general no lineal el óptimo no se alcanza en un único paso, por
lo que se puede modificar la ecuación anterior para introducir el parámetro de
longitud de paso, con lo que queda:

Obsérvese que la dirección s viene ahora dada por:

La longitud de paso se puede calcular vía cualquier método de optimización
numérica de los ya comentados o bien analíticamente con la que se obtendría:

En el método de Newton estrictamente hablando el valor de λ es la unidad. El

problema también se puede resolver sin necesidad de invertir la matriz Hessiana
resolviendo directamente el sistema de ecuaciones lineales en Δx , aplicando la
factorización adecuada y evitando los errores de redondeo, en la medida de lo
posible, que puedan aparecer como consecuencia del proceso de inversión de
matrices.

El método de Newton es el método de minimización más rápido, cuando

funciona bien. Pero presenta las siguientes desventajas:

La dificultad 3 se puede aliviar utilizando métodos apropiados de diferencias

finitas para el cálculo de las derivadas primera y segunda. La convergencia
 global se puede reforzar si, al realizar un paso de Newton propiamente dicho (
λ=1) no se obtiene mejoría de la función objetivo, se vuelve al punto anterior y
se realiza una búsqueda con el valor de λ variable.
Para evitar la dificultad 4 se debe ser muy cuidadoso con la técnica que se
utiliza para garantizar que la matriz Hessiana o inversa sea definida positiva. (en
algunos casos debido al número de condición de la matriz la inversión de está
podría llevar a matrices no definidas positivas). Por otra parte, sólo está
garantizado que el valor de la función objetivo mejora si la matriz Hessiana es
definida positiva. H(x) es definida positiva sólo para funciones estrictamente
convexas, pero las funciones no lineales en general la matriz H(x) puede
cambiar de punto a punto y el método de Newton podría llevarnos a direcciones
que no reducen el valor de la función objetivo (o al menos no las direcciones
óptimas). En otras palabras, si los valores propios de la matriz Hessiana son
todos positivos sabemos que estamos aproximado nuestra función por una
cuadrática de contornos circulares o elipsoidales que tienen un mínimo. Pero si
al menos dos valores propios presentan signos opuestos podríamos movernos en
dirección a un punto de silla en lugar de hacia el mínimo.
El método de Newton tiene la ventaja de la convergencia cuadrática sólo en la
vecindad del óptimo, donde la función objetivo puede ser aproximada bastante
bien por una función cuadrática. Pero en zonas más alejadas otros métodos
pueden presentar velocidades de convergencia mayores.

5.2. FORZANDO A LA MATRIZ HESSIANA A SER DEFINIDA POSITIVA

- Marquardt, Levenverg y otros han sugerido que la matriz Hessiana de f(x) puede
ser modificada para obligarla a ser definida positiva y bien condicionada en cada
etapa de búsqueda. El procedimiento consiste en añadir elementos a la diagonal
principal de H(x):

Donde β es una constante positiva para asegurar que H(x) sea definida positiva
cuando H(x) no lo es. También es posible usar.
 Donde y es una escalar de suficiente valor para el mismo propósito. Para estar
seguro de que valor β usar se debe calcular el valor propio más pequeño (más
negativo) de la matriz Hessiana en el punto y hacer , donde
es un valor propio de H(x).
Remarcar que si el valor de β es demasiado grande la diagonal principal se hace
tan dominante que el método se convierte en el de máximo descenso. El
problema que aparece ahora es que en cada paso se deben calcular los valores
propios de la matriz Hessiana. Se han desarrollado algunos algoritmos que
utilizan valores arbitrarios de dicho parámetro que se modifican en cada paso de
acuerdo a los valores previos obtenidos.
Aunque el método más común consiste en utilizar una factorización de
Cholesky de la matriz Hessiana.

5.3. MÉTODOS DE LA SECANTE

- Los métodos de secante comienzan con la misma ecuación usada en el método
de Newton:

Pero a diferencia del método de Newton estamos interesados en conseguir una

actualización de la matriz H(x), a la que llamaremos H(x) usando solamente las
derivadas parciales primeras de la función, a semejanza de lo que hacíamos en
los métodos de secante unidimensionales. Si queremos aproximar la matriz
inversa, los métodos de secante o quasi-Newton calculan un nuevo vector x a
partir de otro de una etapa precedente a través de ecuaciones análogas a las del
método de Newton:
Donde se conoce en ocasiones como Matriz de dirección y representa
una matriz que es una aproximación de la verdadera inversa de la Hessiana.
Desde este punto de vista si la matriz es la identidad el método se
convierte en el de descenso rápido.

Se han desarrollado varias fórmulas para actualizar las matrices Hessianas.

Supongamos por un momento que f(x) es una función cuadrática entonces
podríamos elegir dos puntos, xk y xk+1 y un punto de referencia xp.

Para una función no cuadrática, la matriz H se podría obtener resolviendo las

ecuaciones de la secante en los puntos xk y xk+1:
Debido a que tenemos solamente n ecuaciones y un total de n 2 incógnitas (cada
uno de los elementos de la matriz Hessiana a actualizar) aparece un número
infinito de posibles soluciones a las ecuaciones anteriores. Se debería elegir una
matriz H(x) lo más parecida posible a Hk en algún determinado sentido. Se han
hecho muchas sugerencias al respecto, a continuación, se muestran las dos
actualizaciones más utilizadas y que han demostrado dar los mejores resultados
en la práctica. Ambas mantienen la matriz Hessiana definida positiva y
simétrica. Son las actualizaciones de Devidon-Fletcher-Powell(DPF) y la de
Broyden-Fletcher-Goldfard y Shanno (BFGS).
DFP:

BFGS:
APLICACIONES:
MÉTODOS DE BÚSQUEDA ALEATORIA
El problema de la programación de producción en talleres de fabricación
Un taller de fabricación o job-shop es una configuración productiva que permite fabricar una gran cantidad
de productos diferentes. Este tipo de sistema se caracteriza por tener máquinas de propósito general, y
porque cada trabajo tiene una ruta de fabricación única, que no necesariamente se repite entre trabajos. Un
taller de maquinado constituye un buen ejemplo de un job-shop: Sus máquinas -tornos, fresadoras, taladros,
rectificadoras, etc.- son de propósito general, ya en ellas se pueden procesar una casi infinita gama de
productos diferentes. En estos talleres cada producto puede tener una ruta diferente dentro del sistema; es
decir, alguna orden de producción irá primero al torno para luego pasar a la fresadora y por último a la
rectificadora, mientras que otra orden puede iniciar su proceso en la fresadora, seguir a la rectificadora y
terminar en el torno.
Jain, y Meeran (1999) describen el problema de la programación de producción en ambientes job-shop de la
siguiente manera: Un conjunto de n trabajos debe ser procesado en m máquinas. Cada trabajo debe ser
procesado en las máquinas en un orden establecido, que no puede ser violado bajo ninguna circunstancia.
Esta última condición se conoce como la restricción de precedencia, y consiste en que, por ejemplo, un
producto no puede ser empacado sin haber sido pintado antes. En este caso la operación de pintura precede
a la operación de empaque. Este problema se conoce como el problema de programación de producción
job-shop de n x m, donde n es el número de trabajos y m el número de máquinas. Considérese una situación
en la cual cuatro trabajos (1, 2, 3, 4) van a ser programados en cuatro máquinas (A, B, C, D) de acuerdo con
la secuencia y los tiempos dados en la tabla 1. El siguiente es un problema de programación de job-shop de
4×4 ; es decir, cuatro trabajos para ser programados en cuatro máquinas. En la figura 1 se puede apreciar
una solución al problema expresada en forma de diagrama de Gantt. Nótese que en el trabajo 1, la
operación en la máquina A precede a la operación en la máquina B, y ésta a su vez precede la operación en
la máquina C. Estas son las relaciones de precedencia mencionadas anteriormente. Una de las características
que hace que la programación de producción en ambientes job-shop sea tan compleja de resolver es
precisamente que estas restricciones de precedencia cambian de un trabajo a otro, como se puede apreciar
en la tabla 1.
La complejidad del problema de programación de producción en job-shop radica en la cantidad abrumadora
de posibles soluciones. Para un problema de n x m, esta cantidad está dada por (n!) m. En estas condiciones
un problema aparentemente sencillo de 20 x 10, en el que se requiera programar 20 trabajos en 10
máquinas tiene 7.2652 x 10138 posibles soluciones. Si una computadora tardara un microsegundo (10-6
segundos) en evaluar cada solución, la edad estimada del universo no bastaría para evaluar todas las
posibles soluciones al problema.

MÉTODOS DE BÚSQUEDA EN REJILLA

En la estrategia denominada búsqueda en rejilla (o grid search) el proceso anterior se automatiza realizando
una búsqueda, no aleatoria en todo el espacio formado por las posibles combinaciones de los parámetros,
sino en puntos de dicho espacio repartidos de forma espaciada en una rejilla.

Scikit-learn ofrece esta funcionalidad en la clase sklearn.model_selection.GridSearchCV.

Repitamos la búsqueda de los mejores parámetros en el mismo escenario que el de la búsqueda aleatoria.
Comenzamos importando la clase GridSearchCV y cargando el dataset:

from sklearn.model_selection import GridSearchCV

iris = sns.load_dataset("iris")
y = [Link]("species")
X = iris
del(iris)

Al objeto de la clase GridSearchCV tenemos que pasarle un mínimo de dos argumentos: estimator -modelo a
usar- y param_grid -diccionario conteniendo como "claves" los hiperparámetros del modelo, y como
"valores" los valores de los hiperparámetros que queremos probar-. El parámetro opcional cv define la
estrategia de validación cruzada a seguir: si pasamos un número entero n, se ejecutará una validación
cruzada con n bloques.

Por lo tanto, instanciamos el algoritmo (vamos a seguir usando RandomForestClassifier):

model = RandomForestClassifier(n_estimators = 100, random_state = 0)

...y definimos el diccionario con los hiperparámetros y sus posibles valores:
parameters = {
    "max_depth": range(1, 11, 2),
    "min_samples_split": range(2, 21, 2)
}
Ahora ya podemos instanciar la clase GridSearchCV y entrenarla (obsérvese que, al ejecutarse la validación
cruzada, podemos pasar a la clase las variables X e y sin necesidad de separaras en bloques de
entrenamiento y validación):
clf = GridSearchCV(model, parameters, cv = 5)
[Link](X, y)
GridSearchCV(cv=5, error_score='raise-deprecating',
       estimator=RandomForestClassifier(bootstrap=True,
class_weight=None, criterion='gini',
            max_depth=None, max_features='auto', max_leaf_nodes=None,
            min_impurity_decrease=0.0, min_impurity_split=None,
            min_samples_leaf=1, min_samples_split=2,
            min_weight_fraction_leaf=0.0, n_estimators=100,
n_jobs=None,
            oob_score=False, random_state=0, verbose=0,
warm_start=False),
       fit_params=None, iid='warn', n_jobs=None,
       param_grid={'max_depth': range(1, 11, 2), 'min_samples_split':
range(2, 21, 2)},
       pre_dispatch='2*n_jobs', refit=True, return_train_score='warn',
       scoring=None, verbose=0)
Una vez entrenado, podemos acceder al mejor modelo, a la mejor puntuación y a los mejores parámetros
encontrados a través de los atributos best_estimator_, best_score_ y best_params_ respectivamente:
clf.best_estimator_ 
RandomForestClassifier(bootstrap=True, class_weight=None,
criterion='gini',
            max_depth=5, max_features='auto', max_leaf_nodes=None,
            min_impurity_decrease=0.0, min_impurity_split=None,
            min_samples_leaf=1, min_samples_split=4,
            min_weight_fraction_leaf=0.0, n_estimators=100,
n_jobs=None,
            oob_score=False, random_state=0, verbose=0,
warm_start=False)
clf.best_score_
0.9666666666666667
clf.best_params_
{'max_depth': 5, 'min_samples_split': 4}
El parámetro de la clase GridSearchCV scoring nos permite especificar un criterio de evaluación del
algoritmo.

El parámetro param_grid comentado puede ser un diccionario o una lista de diccionarios. Si se trata de una
lista, el objeto GridSearchCV probará de forma secuencial las combinaciones de hiperparámetros de cada
uno de los diccionarios de la lista.

El mayor inconveniente que ofrece este método es que se prueban de forma exhaustiva todas las
combinaciones indicadas, lo que puede exigir un tiempo más que notable y difícilmente estimable. Esto
significa que si queremos aprovechar un equipo para que realice una búsqueda durante la noche, es muy
fácil que el proceso termine a las 4 de la madrugada -y estemos desperdiciando varias horas de posible
búsqueda adicional- o que no termine hasta las 11 de la mañana, retrasando otras tareas que estén
pendientes.

Además, no es posible acceder a los mejores valores encontrados hasta que no termina el entrenamiento.
Fijar el argumento "verbose" a 3 o más muestra en pantalla el detalle del proceso, pero la única forma de
encontrar en la información mostrada los mejores valores es a través de una inspección visual, poco
recomendable y muy pesada.

MÉTODO SIMPLEX
Minimizar la siguiente función:

La
construcción inicial del simplex requiere la especificación de un punto inicial y un factor de escala.
Suponiendo x0 =[0,0]T y α=2, entonces:
 Si

observamos detenidamente las iteraciones realizadas podemos percibir que en las últimas cuatro (M = 4)
permanece invariante uno de los vértices del simplex, punto x 6 , en este momento se debe reducir el tamaño
del simplex, de acuerdo a un factor de reducción, es la etapa de “ciclado”. Se comienza nuevamente con las
iteraciones tomando como punto base aquel en el cual se obtuvo el menor valor de función, en nuestro caso
el punto de partida será x 6 . Reducimos ahora el tamaño de nuestro simplex original, x 0 =[5.7954,1.5528]T y
α=0.5, entonces:

El método se continua hasta que el tamaño del simplex o la desviación estándar entre los valores de función
en los vértices sea lo suficientemente pequeña
DIRECCIONES DE BÚSQUEDAS CONJUGADAS
Método de Powell
MÉTODOS INDIRECTOS:

El punto inicial, de igual manera que en los ejemplos anteriores es x 0 =[0,0]T , entonces el nuevo punto es: x1
=[5,1]T . El método de Newton trabaja con una aproximación de segundo orden de la función, al ser la
función objetivo cuadrática el valor óptimo se obtiene en una sola iteración, y este valor es el único punto
crítico de la función.

MÉTODO DE GRADIENTE:

Resolveremos el problema utilizando el método del gradiente, comenzando con el punto xT 1 = (0.00, 3.00).
La tabla 5.5 muestra un resumen de los cálculos. Después de 7 iteraciones, alcanzamos el punto xT 8 = (2.28,
1.15). El algoritmo termina puesto que ||∇f(x8)|| = 0.09 es pequeño. Podemos observar la evolución del
método en la figura 5.7. Notar que la solución de este problema es (2.00, 1.00).

METODO HESSIANO:
CONCLUSIONES
Debido a la naturaleza oscilatoria de las ondas del mar, se tendrán múltiples respuestas sin
embargo se considerará a la solución fundamental a la solución más pequeña positiva.

Se tienen infinitos cruces de la función por cero debido a que para grandes valores de x la función
exponencial tiene a cero, quedando solo la ecuación seno multiplicada por una constante y
desplazada para abajo en 0.4, por lo tanto, corta al eje horizontal 2 veces en cada periodo.

Al hallar las 2 primeras soluciones, se puede ver que las demás soluciones son simplemente
soluciones iguales desplazadas en 2π radianes. Esto se da debido a que sen(x)=sen(x+2π).

En este trabajo se pudo comprobar la eficacia de estos métodos iterativos, encontrando

satisfactoriamente la respuesta y se vio que, a pesar de tener términos no lineales como la función
exponencial, estos sólo prevalecen para una región del problema, que en nuestro caso para hallar
la solución prácticamente no tiene mayor efecto en los valores finales.

REFERENCIAS
[1] Chapra S. & Canales R. / Métodos numéricos para ingenieros. / Edit. Mc
Graw Hill . N.Y. 1994, 641p.

[2] Aljama C. Tomás , Cadena M. Miguel , Charleston V. , Miguel ,

Yañez S. Oscar / Procesamiento digital de señales. / Universidad Autónoma

Metropolitana / México 1998, páginas 244p
[Link]
nonlinear-equations-for-sea-wave-modeling#:~:text=M%C3%A9todo%20de%20la
%20secante&text=Es%20una%20variaci%C3%B3n%20del%20m%C3%A9todo,punto
%20de%20la%20iteraci%C3%B3n%20anterior
simulación y optimización de procesos quimicos. (2011). simulación y optimización de procesos quimicos.
Obtenido de [Link]
%C3%89RICOS%20DE%20OPTIMIZACI%C3%93N_%20PROBLEMAS%20DE%20OPTIMIZACI%C3%93N
%20SIN%20RESTRICCIONES.%202.1.-%20B%C3%BAsqueda%20Unidireccional.%20Conceptos
%20Generales.%20(2).pdf
universidad de carabobo. (s.f.). Obtenido de [Link]
%C3%A9todo-converge-muy-lentamente-3-Si-existe-m%C3%A1s-de-un-extremo-el/

[Link]
[Link]
[Link]
[Link]
leer_desde_pag_10_a_la_18.pdf