1 |
La Dualidad en la programación no linealOré Luján, Luis Alberto January 1991 (has links)
En el Presente trabajo se estudia el Problema Dual Minimáx; con el objeto de posibilitar el desarrollo del tema en referencia, se ha agrupado el presente trabajo en 4 Capítulos. En el Capitulo l, se establecen conceptos y propiedades matemáticas funda-mentales, En el Capitulo 2. se ·presentan algunos teoremas: básicos de la Programación Matemática con sus respectivas demostraciones, En el Capitulo 3, se define el concepto de Programa Matemático No Lineal y se desarrollan las condiciones de optimización de Kuhn-Tucker, así Como otros teoremas, los cuales permiten caracterizar la solución óptima del problema de Programación No Lineal. En el Capítulo 4. se define, el Dual Minimáx y se desarrollan sus propiedades con respecto del Programa Primal; el desarrollo de los temas de interés viene acompañado de sus respectivos ejemplos, lo cual hace fácil la comprensión de los mismos.
|
2 |
Optimización del modelo Media-Varianza-Skewness para la selección de un portafolio de acciones y su aplicación en la BVL usando programación no linealCorrales Céspedes, José 03 November 2011 (has links)
El presente trabajo de Tesis muestra tres metodologías distintas para obtener la composición más eficiente de un portafolio de acciones a través de la optimización matemática, a partir de la media, varianza y asimetría, de algunas acciones seleccionadas del Índice Selectivo de la Bolsa de Valores de Lima, dichas metodologías parten de la ampliación de
la Teoría de Portafolios Eficientes de Markowitz.
Las acciones fueron seleccionadas teniendo en consideración la antigüedad de su cotización en la Bolsa de Valores de Lima, puesto que se trabaja con precios de acciones
semanales, aquellas que recientemente cotizan en bolsa no tienen información suficiente para obtener matrices de varianza/covarianza y asimetría/coasimetría, adecuadamente
definidas.
La primera metodología de solución genera portafolios que se encuentran en la Superficie
Eficiente, es decir portafolios que no pueden mejorar en alguna de las variables (media,
varianza o asimetría) sin desmejorar en otra, la selección de cualquiera de ellos dependerá de las características del inversionista, como el nivel de aversión al riesgo, entre otros.
La segunda metodología es la optimización Lexicográfica, basada en la optimización sucesiva de la media, varianza y asimetría, teniendo siempre como restricciones los parámetros
obtenidos en la optimización anterior. Dado que el orden de las optimizaciones influye en la solución final, se aplicó la metodología bajo todas las combinaciones posibles. Los
portafolios que se obtuvieron fueron soluciones de esquina, y en la mayoría de los casos
no hubo cambio desde la primera optimización.
La tercera metodología es la optimización por Niveles Objetivo, donde se plantean objetivos
deseables de media, varianza y asimetría, que en nuestro caso fueron los obtenidos de los portafolios del Índice General de la Bolsa de Valores de Lima y del Índice Selectivo de la Bolsa de Valores de Lima. El portafolio solución superó en todos los casos los
índices objetivo. / Tesis
|
3 |
Aplicación de la programación no lineal para la determinación de la cartera óptima de inversión: una aplicación al mercado de valores peruanoCastillo Montes, José Alberto January 2007 (has links)
Plantea un problema de programación no lineal, específicamente de Programación Cuadrática, requiriéndose datos del movimiento bursátil ofertados por la Bolsa de Valores de Lima y CONASEV, cuya recopilación estadística pertenece a las más importantes empresas accionarías de diversos sectores de la economía nacional. Para las pruebas de investigación se ha utilizado programas computacionales como Solver Excel, Premium Solver Plataform y el WinQSB, respectivamente. Con estos medios operativos, se va a generar la frontera eficiente de la cual se podrán obtener los portafolios óptimos de inversión. Este estudio muestra la importancia que tienen los Modelos de Investigación de Operaciones, constituyéndose en una herramienta poderosa de las decisiones financieras. / Tesis
|
4 |
El método del gradiente espectral proyectado acelerado mediante paralelismo : aplicaciones a ingeniería de procesosArdenghi, Juan Ignacio 20 May 2014 (has links)
En el área de Ingeniería de Procesos abundan los problemas de
optimización no lineales. En busca de formulaciones más realistas ha aumentado la
exigencia de un modelado riguroso. Como complejidades incorporadas, al aumento de
la cantidad de variables continuas y restricciones no lineales se le suman la presencia de
variables binarias. En muchos casos los problemas se resuelven mediante la relajación
de variables y condiciones, así generando subproblemas no lineales cuya resolución se
realiza a través de aproximaciones lineales y cuadráticas. La pregunta formulada en
esta tesis es la siguiente ¿Podemos lograr eficiencia sin tener que relajar el problema?
Es decir ¿podemos conseguir soluciones del modelo original en tiempos razonables? En
esta tesis proponemos explotar el Método del Gradiente Espectral Proyectado (SPG)
mediante su refundación a partir del paradigma paralelo.
El SPG es un método de optimización global no monótono para problemas de
programación no lineal, con características diferentes a las exhibidas por los métodos
clásicos de gradiente proyectado. La no monotonicidad y una elección particular de
la longitud del paso permiten aprovechar situaciones especiales que se presentan en
muchos problemas, acelerando la convergencia con mínimos costos de almacenamiento
de datos. Entre sus características más atractivas aparece su bajo costo en operaciones:
SPG no calcula matrices hessianas ni resuelve sistemas lineales. SPG sólo utiliza
productos matriz vector y una estrategia de búsqueda lineal no monótona para garantizar
convergencia global. Combinado con un esquema de Lagrangiano Aumentado, el método
se muestra como una herramienta muy prometedora para el abordaje de problemas
muy exigentes en cuanto a esfuerzo computacional y eficiencia. Sus puntos débiles se
encuentran en el requerimiento de muchas búsquedas lineales para obtener un nuevo
iterado, y en la necesidad de una buena aproximación del gradiente cuando éste no
está disponible en forma analítica. En problemas de aplicaciones industriales estos dos
aspectos pueden devenir en verdaderos cuellos de botella del algoritmo. En consecuencia,
el bajo costo aritmético por iteración no se ve reflejado en el tiempo total de resolución.
El auge del desarrollo en la programación en paralelo hace que este paradigma
se presente como un recurso que ofrece una gran oportunidad para superar estos
inconvenientes. El objetivo de esta tesis fue el desarrollo y análisis del desempeño de una
versión eficiente del algoritmo SPG programado en paralelo, asumiendo desconocimiento
de expresiones analíticas de la función objetivo o de los gradientes. Este escenario a
menudo se presenta en los problemas de optimización en ingeniería de procesos con gran
cantidad de variables y restricciones no lineales. La nueva versión del algoritmo SPG
genera una sucesión de iterados que es alternativa a la que genera la versión secuencial
lo que lo hace más competitivo, pero manteniendo la robustez de convergencia que posee
el método SPG original.
Se desarrollaron e implementaron dos versiones del algoritmo paralelo: una fue
concebida para ejecutarse eficientemente sobre una arquitectura distribuida mediante
pasaje de mensajes sobre una red de área local estándar, y la otra fue diseñada para
ejecutarse sobre una arquitectura de memoria local compartida. La experimentación
numérica se realizó sobre un cluster de 8 procesadores y en una computadora multicore
de 12 núcleos. Se demostró en forma teórica la eficiencia esperada. Además, hemos
contrastado estos desarrollos teóricos con resultados empíricos obtenidos en algunos
problemas de diseño relacionados a plantas de procesos industriales, ubicando así a este
resolvedor paralelo como una herramienta competitiva frente a los resolvedores clásicos
de paquetes comerciales. / There are many nonlinear optimization problems in the area of Process
Engineering. In the search of more realistic formulations the need of more rigorous
modeling has grown. The presence of binary variables, the increasing amount
of continuous variables and nonlinear constraints count among the incorporated
complexities. In many cases the problems are solved by relaxing variables and conditions,
thus generating nonlinear subproblems whose resolution is carried out through linear and
quadratic approximations. The question posed in this thesis is the following: Can we
achieve efficiency without having to relax the problem? I mean: Can we get the original
model solutions in reasonable time? In this thesis we propose to exploit the Spectral
Projected Gradient method (SPG) by its relaunching from the parallel paradigm.
SPG is a non-monotone global optimization method for nonlinear programming
problems, its features being different from those exhibited by the classical projectedgradient
methods. The non-monotonicity and a particular choice of the step length allow
to exploit special situations that arise in many problems, accelerating the convergence
with minimal data-storage costs. Its low operating cost features among its most
attractive attributes SPG neither calculates Hessian matrices nor solves linear systems.
SPG just performs matrix vector products and a non-monotone line-search strategy in
order to ensure global convergence. When combined with an Augmented Lagrangian
scheme, the method looks like a promising tool for addressing demanding problems in
terms of computational effort and efficiency. Its weaknesses lie in the requirement of too
many line-searches for a new iterate, and in the need for a good approximation of the
gradient when it is not available in analytical form. In industrial application these two
mentioned aspects may become real bottlenecks in the algorithm. In consequence, the
low arithmetic cost per iteration is not reflected in the total elapsed time of resolution.
The boom development in parallel programming presents this paradigm as a resource
that provides a great opportunity to overcome these drawbacks. The goal of this thesis
was the development and analysis of the performance of an efficient version of the SPG
algorithm programmed in parallel, assuming lack of knowledge about the analytical
expressions of the objective function or gradients. This scenario often appears in process
engineering optimization problems with many variables and non-linear constraints. The
new version of the SPG algorithm generates a sequence of iterates that is alternative to
the one generated by the sequential version. In this way, the proposed version becomes
more competitive, while maintaining the robustness of the original method.
Two versions of the parallel algorithm were developed and implemented: one of them
was conceived to run efficiently on a distributed architecture by using message passing
on a standard local area network, and another one was designed to run on a shared
local-memory architecture. The numerical experiments were performed on a cluster of
8 processors and a 12-core multicore computer. We have proved the expected efficiency
theoretically. Besides, we have contrasted these theoretical developments with empirical
results in some design problems related to industrial plants processes. thus placing this
parallel solver as a competitive tool against classical commercial packages.
|
5 |
Implementación de un Método de Programación Semidefinida Usando Computación ParalelaPeredo Andrade, Oscar Francisco January 2010 (has links)
En el presente trabajo se estudió y rediseñó una implementación existente del algoritmo Filter-SDP, el cual resuelve problemas de programación semidefinida no lineal de la forma:
donde f : Rn → R, h : Rn → Rp y G : Rn → Sm son funciones de clase C2 y Sm
denota el espacio lineal de las matrices simétricas de m×m dotado del producto interno A·B = . El algoritmo resuelve en cada iteración una aproximación local representada por un problema de programación semidefinida lineal, y adicionalmente
se utiliza un esquema de penalización multi-objetivo, en el cual se minimiza la función
objetivo y una función de mérito utilizando un filtro.
Se estudió la introducción de cálculo paralelo en partes específicas del algoritmo, con el objetivo de disminuir el tiempo de ejecución. Se reimplementó el algoritmo utilizando el lenguaje C y la librería de cálculo paralelo MPI. Esa nueva implementación se comparó con un desarrollo ya existente, realizado sobre la plataforma MATLAB, y se midió su speedup en los problemas más pesados de una batería de tests escogida. Como apoyo al desarrollo del algoritmo, se diseñaron nuevas fases de restauración sobre la plataforma MATLAB, con el objetivo de mejorar la calidad de las soluciones obtenidas. Se diseñaron 4 nuevos métodos para la fase de restauración del algoritmo, cuyas principales áreas de influencia son la restauración inexacta, el diseño de controladores retroalimentados de salida estática y el posicionamiento de polos.
Dentro de los resultados obtenidos, se logró visualizar las ventajas de la nueva implementación con respecto al desarrollo ya existente, así como demostrar el beneficio que se obtiene en el speedup para problemas pesados. También se realizó una comparación entre los métodos diseñados para la fase de restauración, con la cual se llegó a conclusiones que pueden abrir nuevas áreas de investigación y trabajo a futuro.
Finalmente, se aprendió a utilizar una herramienta de álgebra lineal que funciona sobre ambientes de cálculo paralelo, ScaLAPACK, y se perfeccionó el proceso de desarrollo de software que ya se tenía sobre este tipo de plataformas.
|
6 |
Self-optimizing skeleton execution using eventsPabón Sánchez, Gustavo Adolfo January 2015 (has links)
Magíster en Ciencias, Mención Computación / Esta tesis propone una forma novedosa para introducir características autonómicas de auto-configuración y auto-optimización a Patrones de Paralelismo (o Algorithmic Skeletons en inglés) usando técnicas de la Programación Dirigida por Eventos (o EDP por sus siglas en inglés).
Gracias al uso de la programación dirigida por eventos, la solución propuesta en esta tesis presenta las siguientes contribuciones a las soluciones actuales:
- No está relacionada a una arquitectura de aplicaciones en particular, por ejemplo la arquitectura de componentes. De esta forma, presenta una solución con un mayor alcance y es
independiente de la arquitectura usada para la implementación de los patrones de paralelismo.
- Provee un mayor nivel de adaptabilidad por permitir la introducción de cambios estructurales
en tiempo de ejecución. A diferencia de otras soluciones que solo permiten la introducción de
este tipo de cambios durante la compilación.
- Los estimados de trabajo futuro pueden ser calculados en tiempo de ejecución y no hay
dependencia a estimados pre-calculados en ejecuciones anteriores.
Las características autonómicas presentadas en esta tesis se enfocan principalmente en garantizar un tiempo de ejecución a un patron de paralelismo por medio de la optimización de la cantidad de hilos de ejecución usados. Las calidades de servicio (QoS por sus siglas en inglés) usadas para este fin son: (1) tiempo de ejecución percibido por el usuario y (2) nivel de paralelismo.
Otras contribuciones de esta tesis son:
- Diseño e implementación de una novedosa solución a la separación de asuntos en los patrones
de paralelismo usando técnicas de la programación dirigida por eventos. Esta solución
novedosa permite la introducción de asuntos no-funcionales a los patrones de paralelismo sin
disminuir sus abstracciones de alto nivel.
- Evaluación de diferentes estrategias de estimación de trabajo futuro con el fin de realizar
recomendaciones relacionadas a responder a la pregunta ¿Qué estrategia produce mejores
estimados bajo qué circunstancias?
|
7 |
Estudio de problemas de optimización para la reducción de emisiones de dióxido de carbono en refinerías de petróleoUgalde Salas, Pablo Andrés January 2017 (has links)
Ingeniero Civil Matemático / Este trabajo es una primera aproximación a la inclusión de costos asociados a la reducción de CO2 en el subproceso de descarga y mezcla de crudos. En este subproceso la cantidad de CO2 liberado a la atmósfera crece en función del volumen de crudo que se procesa en cada unidad de destilación.
El modelo matemático del subproceso de descarga y mezcla de crudos expuesto en esta memoria corresponde a un problema no lineal mixto (PNLM), donde la no linealidad proviene de restricciones asociadas a la composición de la mezcla de los crudos en los estanques.
Desde un punto de vista matemático el modelo presentado contiene considerables simetrías, lo que se traduce en grandes tiempos de ejecución. Lo anterior fue abordado introduciendo restricciones en la formulación para reducir el espacio de búsqueda. En este aspecto la técnica más interesante y de mejores resultados proviene del modelamiento del orden de las operaciones de una refinería como una palabra perteneciente a un lenguaje regular.
Existen tecnologías capaces de capturar alguna fracción del CO2 liberado, pero el uso de éstas se traduce en costos económicos para la refinería. Se tiene como primera novedad una modificación del modelo anterior para que este incluya los costos asociados a la reducción de CO2.
Naturalmente existe un tradeoff entre las emisiones capturadas y las ganancias de la refinería. Esta memoria propone una manera de cuantificar este tradeoff. Para lo anterior se desarrolla un modelo multiperiodo del proceso de descarga y mezcla de crudos, el cual considera a la vez las ganancias de la refinería y las emisiones de CO2. Utilizando el concepto de pareto eficiencia se plantea un esquema numérico para encontrar las mejores decisiones de calendarización.
|
8 |
Precontrol óptimo. Caracterización, análisis y técnicas de resoluciónGiner Bosch, Vicent 26 January 2015 (has links)
El precontrol es una herramienta para el control de la calidad que tiene
como objeto evaluar la aptitud de un proceso para producir piezas dentro
de unas especificaciones dadas. Es usada, entre otros contextos, en la
validación de la puesta a punto de procesos con ciclos de ejecución cortos.
Basa su funcionamiento en la comparación de las sucesivas observaciones
individuales muestreadas frente a los límites de tolerancia y los llamados
límites de precontrol, y utiliza conteos acumulados para emitir un juicio
sobre la validez del proceso. Es una técnica sencilla, rápida y fácil de
aplicar.
El hecho de que, en su versión original, la técnica del precontrol no tenga
en cuenta la variabilidad natural del proceso objeto de monitorización,
unido a la sencillez de su diseño, provocan que, bajo ciertas circunstancias,
su comportamiento no sea tan eficaz como sería deseable, en términos
de la tasa de falsa alarma y de la potencia para detectar desviaciones
inaceptables, hasta el punto de que algunos autores rechazan su uso. En
este sentido, existen en la literatura diversas propuestas encaminadas a
mejorar el comportamiento de la técnica original mediante la modificación,
en mayor o menor medida, de sus reglas de funcionamiento.
En esta tesis doctoral se aborda la mejora del precontrol como
herramienta para la cualificación de procesos, a través de la determinación
óptima de los parámetros que rigen su comportamiento, utilizando
técnicas de programación no lineal entera mixta. El objetivo es desarrollar
una metodología para automatizar el proceso de elección del valor de los
parámetros del precontrol, de manera que éste se ajuste lo mejor posible a
los requerimientos del usuario. Este enfoque de Optimización, inédito en
el precontrol, ha sido aplicado con éxito a otras técnicas de control de la
calidad en las últimas décadas, permitiendo obtener mejores herramientas
para la toma de decisiones.
Para ello, en primer lugar se realiza una revisión exhaustiva de las
diferentes propuestas existentes en la literatura en torno al precontrol.
Posteriormente, se define el problema a resolver y se desarrolla un
modelo de programación matemática específico para la obtención de
los denominados planes de precontrol óptimos. Se realiza una completa
experiencia numérica con software de optimización de propósito general,
mediante la que se evidencia la eficacia del modelo propuesto y, al mismo
tiempo, se pone de manifiesto la existencia de diferencias significativas
entre los resultados proporcionados por los diferentes algoritmos tomados
en consideración, debidas en parte a la doble naturaleza no lineal y
entera del problema, así como la incapacidad de dichos algoritmos para
garantizar la convergencia a un óptimo global, a causa de la existencia de
no convexidades.
Todo ello justifica el diseño de algoritmos específicos para la obtención
de planes de precontrol óptimos, tarea que también se aborda en
la presente tesis doctoral. Previamente, se realiza un estudio de las
propiedades matemáticas del modelo de optimización construido, que
permite ampliar el conocimiento sobre el problema del precontrol óptimo.
Este conocimiento es empleado en la elaboración de un algoritmo
exacto para la resolución de dicho problema, denominado OPCenum, el
cual combina una estrategia enumerativa implícita con una búsqueda
local basada en métodos de búsqueda de raíces sin uso de derivadas. El
algoritmo es implementado y probado sobre la misma batería de ejemplos
que conformaban la experiencia numérica anterior.
Las pruebas revelan la eficacia y eficiencia del algoritmo OPCenum como
método para la obtención de planes de precontrol óptimos a partir de
unos requerimientos dados.
La elaboración de una interfaz gráfica para hacer más accesible el
algoritmo al usuario final, la adaptación del problema a funciones de
distribución asimétricas y a ámbitos como el de la fiabilidad, así como el
desarrollo de un enfoque paralelo al acometido aquí en el que se considere
el precontrol como herramienta para validar la capacidad del proceso
destacan como líneas futuras de investigación que surgen a partir de los
resultados obtenidos en la presente tesis doctoral. / Giner Bosch, V. (2014). Precontrol óptimo. Caracterización, análisis y técnicas de resolución [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/46373 / TESIS
|
9 |
Algoritmo genético multiobjetivo para la optimización de la distribución de ayuda humanitaria en caso de desastres naturales en el PerúAduviri Choque, Robert Alonso 03 December 2019 (has links)
El Perú es un país susceptible a desastres naturales, hecho evidenciado con el terremoto de Pisco en 2007 y el fenómeno de El Niño Costero en 2017. Ante la ocurrencia de un desastre surge una cantidad considerable y variada de ayuda proveniente de distintos lugares: INDECI, empresas privadas, ciudadanía y ayuda internacional. Es posible identificar una demanda de bienes de ayuda diferenciada entre las zonas afectadas; sin embargo, el plan logístico del INDECI no indica un procedimiento de distribución de ayuda humanitaria con sustento científico. Ante esto, en el presente proyecto se propone un modelo de programación no lineal entero mixto que servirá como base para generar un plan de distribución de ayuda humanitaria a gran escala de manera automática, abarcando los niveles nacional y regional luego de un desastre. Asimismo, dado que en escenarios reales el tiempo de ejecución de métodos para encontrar soluciones para este modelo es limitado, se propone el diseño e implementación de un algoritmo genético, el cual es un algoritmo de optimización metaheurístico basado en principios evolutivos que se caracteriza por obtener soluciones aproximadas con un tiempo de ejecución menor al de métodos exactos, y permiten generar poblaciones de posibles soluciones para evaluar múltiples objetivos de optimización como la minimización de la inequidad en la distribución y el costo de transporte. Para probar el método exacto y metaheurístico se generará información a partir de datos disponibles del INDECI y la simulación de datos de prueba a partir de distribuciones de probabilidad. Asimismo, se realizará una comparación entre estos métodos, buscando obtener con el algoritmo genético una efectividad aproximada al del método exacto en un tiempo de ejecución mucho menor, y con el objetivo de conocer a partir de qué tamaño de problema es preferible el uso del algoritmo genético. Finalmente, como cada plan de distribución dependerá de las características del desastre a analizar, se propone la implementación de una interfaz de software para la entrada y visualización de información.
|
10 |
Optimización del modelo Media-Varianza-Skewness para la selección de un portafolio de acciones y su aplicación en la BVL usando programación no linealCorrales Céspedes, José 03 November 2011 (has links)
El presente trabajo de Tesis muestra tres metodologías distintas para obtener la composición más eficiente de un portafolio de acciones a través de la optimización matemática, a partir de la media, varianza y asimetría, de algunas acciones seleccionadas del Índice Selectivo de la Bolsa de Valores de Lima, dichas metodologías parten de la ampliación de
la Teoría de Portafolios Eficientes de Markowitz.
Las acciones fueron seleccionadas teniendo en consideración la antigüedad de su cotización en la Bolsa de Valores de Lima, puesto que se trabaja con precios de acciones
semanales, aquellas que recientemente cotizan en bolsa no tienen información suficiente para obtener matrices de varianza/covarianza y asimetría/coasimetría, adecuadamente
definidas.
La primera metodología de solución genera portafolios que se encuentran en la Superficie
Eficiente, es decir portafolios que no pueden mejorar en alguna de las variables (media,
varianza o asimetría) sin desmejorar en otra, la selección de cualquiera de ellos dependerá de las características del inversionista, como el nivel de aversión al riesgo, entre otros.
La segunda metodología es la optimización Lexicográfica, basada en la optimización sucesiva de la media, varianza y asimetría, teniendo siempre como restricciones los parámetros
obtenidos en la optimización anterior. Dado que el orden de las optimizaciones influye en la solución final, se aplicó la metodología bajo todas las combinaciones posibles. Los
portafolios que se obtuvieron fueron soluciones de esquina, y en la mayoría de los casos
no hubo cambio desde la primera optimización.
La tercera metodología es la optimización por Niveles Objetivo, donde se plantean objetivos
deseables de media, varianza y asimetría, que en nuestro caso fueron los obtenidos de los portafolios del Índice General de la Bolsa de Valores de Lima y del Índice Selectivo de la Bolsa de Valores de Lima. El portafolio solución superó en todos los casos los
índices objetivo.
|
Page generated in 0.3892 seconds