No description available.

Title: Semi-infinite programming: theory and portfolio efficiency application Author: Bc. Lukáš Klouda Department: Department of Probability and Mathematical Statistics Supervisor: RNDr. Ing. Miloš Kopa, PhD. Supervisor's e-mail address: kopa@karlin.mff.cuni.cz Abstract: The thesis deals with application of semi-infinite programming to a portfolio efficiency testing. The summary of semi-infinite programming, first and second order optimality conditions and duality in linear semi-infinite programming is presented. The optimization problem for a portfolio efficiency testing with respect to the second order stochastic dominance under assumption of discrete, normal, Students and general elliptical distribution is formulated. Conditional value at risk(CVaR) is used as the risk measure, because of its consistency with the second order stochastic dominance relation. Efficiency of index PX with respect to the second order stochastic dominance is tested. The tests are performed using the program GAMS.

Esta Tesis esta motivada por el interés en aplicar procedimientos de optimización global a problemas del mundo real. Para ello, nos hemos centrado en el problema de Coordinación Hidrotérmica de la Generación Eléctrica a Corto Plazo (llamado Problema de Generación en esta Tesis) donde la función objetivo y las restricciones no lineales son polinomios de grado como máximo cuatro. En el Problema de Generación no tenemos disponible una representación en diferencia convexa de las funciones involucradas ni tampoco es posible utilizar la estructura del problema para simplificarlo. No obstante, cuando disponemos de una función continua f(x) definida en un conjunto cerrado y no vacío S el problema puede transformarse en otro equivalente expresado mediante minimize l(z) subject to z 2 D n int. (programa d.c. canónico), donde l(z) es una función convexa (en general suele ser una función lineal) con D y C conjuntos convexos y cerrados. Una estructura matemática tal como Dnint C no resulta siempre aparente y aunque lo fuera siempre queda por realizar una gran cantidad de cálculos para expresarla de manera que se pueda resolver el problema de una manera eficiente desde un punto de vista computacional.La característica más importante de esta estructura es que aparecen conjuntos convexos y complementarios de conjuntos convexos. Por este motivo en tales problemas se pueden usar herramientas analíticas tales como subdifernciales y hiperplanos soporte. Por otro lado, como aparecen conjuntos complementarios de conjuntos convexos, estas herramientas analíticas se deben usar de una manera determinada y combinándolas con herramientas combinatorias tales como cortes por planos, Branco and bound y aproximación interior.En esta tesis se pone de manifiesto la estructura matemática subyacente en el Problema de Generación utilizando el hecho de que los polinomios son expresables como diferencia de funciones convexas. Utilizando esta propiedad describimos el problema como un programa d.c. canónico equivalente. Pero aun mas, partiendo de la estructura de las funciones del Problema de Generación es posible rescribirlo de una manera mas conveniente y obtener de este modo ventajas numéricas desde elpunto de vista de la implementación.Basándonos en la propiedad de que los polinomios homogéneos de grado 1 son un conjunto de generadores del espacio vectorial de los polinomios homogéneos de grado m hemos desarrollamos los conceptos y propiedades necesarios que nos permiten expresar un polinomio cualquiera como diferencia de polinomios convexos, También, se ha desarrollado y demostrado la convergencia de un nuevo algoritmo de optimización global (llamado Algoritmo Adaptado) que permite resolver el Problema de Generación. Como el programa equivalente no esta acotado se ha introducido una técnica de subdivisión mediante prismas en lugar de la habitual subdivisión mediante conos.Para obtener una descomposición óptima de un polinomio en diferencia de polinomios convexos, se ha enunciado el Problema de Norma Mínima mediante la introducción del concepto de Descomposición con Mínima Desviación, con lo cual obtenemos implementaciones m´as eficientes, al reducir el n´umero de iteraciones del Algoritmo Adaptado. Para resolver el problema de Norma Mínima hemos implementado un algoritmo de programación cuadrática semi-infinita utilizando una estrategia de build-up and build-down, introducida por Den Hertog (1997) para resolver programas lineales semi-infinitos, la cual usa un procedimiento de barrera logarítmica.Finalmente, se describen los resultados obtenidos por la implementación de los algoritmos anteriormente mencionados y se dan las conclusiones. / This Thesis has been motivated by the interest in applying deterministic global optimization procedures to problems in the real world with no special structures. We have focused on the Short-Term Hydrothermal Coordination of Electricity Generation Problem (also named Generation Problem in this Thesis) where the objective function and the nonlinear constraints are polynomials of degree up to four. In the Generation Problem there is no available d.c. representation of the involved functions and we cannot take advantage of any special structure of the problem either. Hence, a very general problem, such as the above-mentioned, does not seem to have any mathematical structure conducive to computational implementations. Nevertheless, when f(x) is a continuous function and S is a nonempty closed set the problem can be transformed into an equivalent problem expressed by minimize l(z) subject to z 2 D n intC (canonical d.c. program), where l(z) is a convex function (which is usually a linear function) and D and C are closed convex sets. A mathematical complementary convex structure such as D n int C is not always apparent and even when it is explicit, a lot of work still remains to be done to bring it into a form amenable to efficient computational implementations. The attractive feature of the mathematicalcomplementary convex structure is that it involves convexity. Thus, we can use analytical tools from convex analysis like sub differential and supporting hyper plane.On the other hand, since convexity is involved in a reverse sense, these tools must be used in some specific way and combined with combinatorial tools like cutting planes, branch and bound and outer approximation.We introduce the common general mathematical complementary convex structure underlying in global optimization problems and describe the Generation Problem, whose functions are d.c. functions because they are polynomials. Thus, by using the properties of the d.c. functions, we describe the Generation Problem as an equivalent canonical d.c. programming problem. From the structure of its functions the Generation Problem can be rewritten as a more suitable equivalent reverse convex program in order to obtain an adaptation for advantageous numerical implementations.Concepts and properties are introduced which allow us to obtain an explicit representation of a polynomial as a deference of convex polynomials, based on the fact that the set of mth powers of homogeneous polynomials of degree 1 is a generating set for the vector space of homogeneous polynomials of degree m.We also describe a new global optimization algorithm (adapted algorithm) in order to solve the Generation Problem. Since the equivalent reverse convex program is unbounded we use prismatical subdivisions instead of conical ones. Moreover, we prove the convergence of the adapted algorithm by using a prismatical subdivision process together with an outer approximation procedure.We enounce the Minimal Norm Problem by using the concept of Least Deviation Decomposition in order to obtain the optimal d.c. representation of a polynomial function, which allows a more efficient implementation, by reducing the number of iterations of the adapted algorithm.A quadratic semi-infinite algorithm is described. We propose a build-up and down strategy, introduced by Den Hertog (1997) for standard linear programs that uses a logarithmic barrier method.Finally, computational results are given and conclusions are explained.

A subfield of artificial intelligence, machine learning (ML), is concerned with the development of algorithms that allow computers to &ldquo / learn&rdquo / . ML is the process of training a system with large number of examples, extracting rules and finding patterns in order to make predictions on new data points (examples). The most common machine learning schemes are supervised, semi-supervised, unsupervised and reinforcement learning. These schemes apply to natural language processing, search engines, medical diagnosis, bioinformatics, detecting credit fraud, stock market analysis, classification of DNA sequences, speech and hand writing recognition in computer vision, to encounter just a few. In this thesis, we focus on Support Vector Machines (SVMs) which is one of the most powerful methods currently in machine learning. As a first motivation, we develop a model selection tool induced into SVM in order to solve a particular problem of computational biology which is prediction of eukaryotic pro-peptide cleavage site applied on the real data collected from NCBI data bank. Based on our biological example, a generalized model selection method is employed as a generalization for all kinds of learning problems. In ML algorithms, one of the crucial issues is the representation of the data. Discrete geometric structures and, especially, linear separability of the data play an important role in ML. If the data is not linearly separable, a kernel function transforms the nonlinear data into a higher-dimensional space in which the nonlinear data are linearly separable. As the data become heterogeneous and large-scale, single kernel methods become insufficient to classify nonlinear data. Convex combinations of kernels were developed to classify this kind of data [8]. Nevertheless, selection of the finite combinations of kernels are limited up to a finite choice. In order to overcome this discrepancy, we propose a novel method of &ldquo / infinite&rdquo / kernel combinations for learning problems with the help of infinite and semi-infinite programming regarding all elements in kernel space. This will provide to study variations of combinations of kernels when considering heterogeneous data in real-world applications. Combination of kernels can be done, e.g., along a homotopy parameter or a more specific parameter. Looking at all infinitesimally fine convex combinations of the kernels from the infinite kernel set, the margin is maximized subject to an infinite number of constraints with a compact index set and an additional (Riemann-Stieltjes) integral constraint due to the combinations. After a parametrization in the space of probability measures, it becomes semi-infinite. We analyze the regularity conditions which satisfy the Reduction Ansatz and discuss the type of distribution functions within the structure of the constraints and our bilevel optimization problem. Finally, we adapted well known numerical methods of semiinfinite programming to our new kernel machine. We improved the discretization method for our specific model and proposed two new algorithms. We proved the convergence of the numerical methods and we analyzed the conditions and assumptions of these convergence theorems such as optimality and convergence.

Gas separation with polymer membranes are becoming one of the mainstream separation techniques for a myriad of industrial applications. Membrane technologies are recognized as a viable and economical unit operation compared to more conventional separation processes. The design and material selection of membrane separation processes depends highly on the transport properties of separated gas molecules within the membrane material. Therefore, to use efficient methods for gas membrane characterization is paramount for the proper design of membrane separation processes. A membrane can be typically characterized by three main properties: permeability, solubility and diffusivity. The permeability of a membrane is the product of its diffusivity and solubility, therefore obtaining two of the three parameters is sufficient to fully characterize a membrane. The time-lag method is one of the oldest and most used gas membrane characterization methods. However, it suffers from various limitations that make the method not applicable for many types of membranes. The focus in this study was to develop new gas membrane characterization techniques that are based on extracting the membrane properties from the upstream gas pressure measurements rather than only from the downstream pressure measurements. It is believed that characterizing the membrane based on the upstream pressure measurements would be highly useful in characterizing barrier materials which are usually difficult to characterize using the conventional time-lag method. Moreover, glassy polymers which are widely used in industry exhibit behavior associated with nonlinear sorption isotherms and, therefore, the conventional time-lag method is incapable of obtaining an accurate estimation of glassy polymer properties. As a result, sorption experiments to generate a sorption isotherm are usually required in addition to permeation experiments to fully characterize glassy polymer membranes. To quantify the errors associated with the conventional time-lag assumptions and to fundamentally comprehend the impact of nonlinearities on the time-lag method, a comprehensive numerical investigation has been undertaken using the finite difference method. The investigation has clearly put in evidence the effect of the various Langmuir parameters on the accuracy of the time lag and on the time required to achieve steady state. This investigation also allowed assessing the errors associated with the usual assumptions made on the boundary conditions in determining the time lag. In this study, three novel gas membrane characterization methods were developed and proposed. Two of the proposed methods are concerned with the characterization of membranes that can be represented with a linear sorption isotherm. These two methods are entirely based on the upstream pressure measurements. The third membrane characterization method that is proposed is based on the dynamic monitoring of both upstream and downstream pressure measurements and is applicable to systems that exhibit a nonlinear isotherm sorption behavior. The three proposed methods are promising and further experimental validation is recommended to determine their full range of applicability.

Motion planning problems are characterized by huge search spaces and complex obstacle structures with no concise mathematical expression. The fixed-wing airplane application considered in this thesis adds differential constraints and point-wise bounds, i. e. an infinite number of equality and inequality constraints. An optimal trajectory planning approach is presented, based on the randomized Rapidly-exploring Random Trees framework (RRT*). The local planner relies on differential flatness of the equations of motion to obtain tree branch candidates that automatically satisfy the differential constraints. Flat output trajectories, in this case equivalent to the airplane's flight path, are designed using Bézier curves. Segment feasibility in terms of point-wise inequality constraints is tested by an indicator integral, which is evaluated alongside the segment cost functional. Although the RRT* guarantees optimality in the limit of infinite planning time, it is argued by intuition and experimentation that convergence is not approached at a practically useful rate. Therefore, the randomized planner is augmented by a deterministic variational optimization technique. To this end, the optimal planning task is formulated as a semi-infinite optimization problem, using the intermediate result of the RRT(*) as an initial guess. The proposed optimization algorithm follows the feasible flavor of the primal-dual interior point paradigm. Discretization of functional (infinite) constraints is deferred to the linear subproblems, where it is realized implicitly by numeric quadrature. An inherent numerical ill-conditioning of the method is circumvented by a reduction-like approach, which tracks active constraint locations by introducing new problem variables. Obstacle avoidance is achieved by extending the line search procedure and dynamically adding obstacle-awareness constraints to the problem formulation. Experimental evaluation confirms that the hybrid approach is practically feasible and does indeed outperform RRT*'s built-in optimization mechanism, but the computational burden is still significant. / Bewegungsplanungsaufgaben sind typischerweise gekennzeichnet durch umfangreiche Suchräume, deren vollständige Exploration nicht praktikabel ist, sowie durch unstrukturierte Hindernisse, für die nur selten eine geschlossene mathematische Beschreibung existiert. Bei der in dieser Arbeit betrachteten Anwendung auf Flächenflugzeuge kommen differentielle Randbedingungen und beschränkte Systemgrößen erschwerend hinzu. Der vorgestellte Ansatz zur optimalen Trajektorienplanung basiert auf dem Rapidly-exploring Random Trees-Algorithmus (RRT*), welcher die Suchraumkomplexität durch Randomisierung beherrschbar macht. Der spezifische Beitrag ist eine Realisierung des lokalen Planers zur Generierung der Äste des Suchbaums. Dieser erfordert ein flaches Bewegungsmodell, sodass differentielle Randbedingungen automatisch erfüllt sind. Die Trajektorien des flachen Ausgangs, welche im betrachteten Beispiel der Flugbahn entsprechen, werden mittels Bézier-Kurven entworfen. Die Einhaltung der Ungleichungsnebenbedingungen wird durch ein Indikator-Integral überprüft, welches sich mit wenig Zusatzaufwand parallel zum Kostenfunktional berechnen lässt. Zwar konvergiert der RRT*-Algorithmus (im probabilistischen Sinne) zu einer optimalen Lösung, jedoch ist die Konvergenzrate aus praktischer Sicht unbrauchbar langsam. Es ist daher naheliegend, den Planer durch ein gradientenbasiertes lokales Optimierungsverfahren mit besseren Konvergenzeigenschaften zu unterstützen. Hierzu wird die aktuelle Zwischenlösung des Planers als Initialschätzung für ein kompatibles semi-infinites Optimierungsproblem verwendet. Der vorgeschlagene Optimierungsalgorithmus erweitert das verbreitete innere-Punkte-Konzept (primal dual interior point method) auf semi-infinite Probleme. Eine explizite Diskretisierung der funktionalen Ungleichungsnebenbedingungen ist nicht erforderlich, denn diese erfolgt implizit durch eine numerische Integralauswertung im Rahmen der linearen Teilprobleme. Da die Methode an Stellen aktiver Nebenbedingungen nicht wohldefiniert ist, kommt zusätzlich eine Variante des Reduktions-Ansatzes zum Einsatz, bei welcher der Vektor der Optimierungsvariablen um die (endliche) Menge der aktiven Indizes erweitert wird. Weiterhin wurde eine Kollisionsvermeidung integriert, die in den Teilschritt der Liniensuche eingreift und die Problemformulierung dynamisch um Randbedingungen zur lokalen Berücksichtigung von Hindernissen erweitert. Experimentelle Untersuchungen bestätigen, dass die Ergebnisse des hybriden Ansatzes aus RRT(*) und numerischem Optimierungsverfahren der klassischen RRT*-basierten Trajektorienoptimierung überlegen sind. Der erforderliche Rechenaufwand ist zwar beträchtlich, aber unter realistischen Bedingungen praktisch beherrschbar.

We discuss a full-waveform based material profile reconstruction in two-dimensional heterogeneous semi-infinite domains. In particular, we try to image the spatial variation of shear moduli/wave velocities, directly in the time-domain, from scant surficial measurements of the domain's response to prescribed dynamic excitation. In addition, in one-dimensional media, we try to image the spatial variability of elastic and attenuation properties simultaneously. To deal with the semi-infinite extent of the physical domains, we introduce truncation boundaries, and adopt perfectly-matched-layers (PMLs) as the boundary wave absorbers. Within this framework we develop a new mixed displacement-stress (or stress memory) finite element formulation based on unsplit-field PMLs for transient scalar wave simulations in heterogeneous semi-infinite domains. We use, as is typically done, complex-coordinate stretching transformations in the frequency-domain, and recover the governing PDEs in the time-domain through the inverse Fourier transform. Upon spatial discretization, the resulting equations lead to a mixed semi-discrete form, where both displacements and stresses (or stress histories/memories) are treated as independent unknowns. We propose approximant pairs, which numerically, are shown to be stable. The resulting mixed finite element scheme is relatively simple and straightforward to implement, when compared against split-field PML techniques. It also bypasses the need for complicated time integration schemes that arise when recent displacement-based formulations are used. We report numerical results for 1D and 2D scalar wave propagation in semi-infinite domains truncated by PMLs. We also conduct parametric studies and report on the effect the various PML parameter choices have on the simulation error. To tackle the inversion, we adopt a PDE-constrained optimization approach, that formally leads to a classic KKT (Karush-Kuhn-Tucker) system comprising an initial-value state, a final-value adjoint, and a time-invariant control problem. We iteratively update the velocity profile by solving the KKT system via a reduced space approach. To narrow the feasibility space and alleviate the inherent solution multiplicity of the inverse problem, Tikhonov and Total Variation (TV) regularization schemes are used, endowed with a regularization factor continuation algorithm. We use a source frequency continuation scheme to make successive iterates remain within the basin of attraction of the global minimum. We also limit the total observation time to optimally account for the domain's heterogeneity during inversion iterations. We report on both one- and two-dimensional examples, including the Marmousi benchmark problem, that lead efficiently to the reconstruction of heterogeneous profiles involving both horizontal and inclined layers, as well as of inclusions within layered systems. / text

Experimental observations indicate the presence of attached, gravity induced, horizontal buoyant currents above large area fires. Their driving mechanism is indirect and resembles the one observed above heated horizontal plates. Classic plume modelling is satisfactory for providing information for the flow far from the source. In dealing with large areas and directing attention to the flow close to the source, the classic plume theory should fail because the radial pressure gradient that is responsible for the driving of the flow is squeezed in the long and thin classic plume assumption. For this we propose a new plume structure for the description of the buoyant flow above a circular region of large radius L as “The flow field must be divided into three regions. A region where the flow is predominantly horizontal and attached to the surface, a transition region from horizontal to vertical where separation of the attached current takes place, and a region where vertical flow is established and classic plume theory can be applied”. A model for the description of the gross properties of the horizontal currents is developed under the term “horizontal plume”. The modified Richardson number for the horizontal plume a, being analogous to the radius of the large area, is studied asymptotically in the limit a → ∞ and second order uniformly valid semi-analytical solutions are obtained. The hot plate experiment was set up in order to test the model and facilitate its improvement. A chapter is dedicated to the data analysis coming from thermocouple readings and visualisation of the flow using particle image velocimetry.In the remainder of this thesis two classic problems of laminar natural convection are revisited. That of the first order laminar boundary layer above an isothermal circular plate of radius a and the first order laminar boundary layer above the semi- infinite plate inclined to horizontal. In both cases allowances to variable property effects were made through the introduction of a nondimensional parameter λT, with its value set to zero implying the assumption of the Boussinesq approximation. For the circular plate, fourth order series solutions were obtained valid at the edge of the plate where the effects of λT and Prandtl number Pr are studied. Furthermore a finite difference scheme for the numerical solution of the nonsimilar partial integro- differential equation was developed using the Keller Box method and compared with results obtained from the commercial finite element software COMSOL Multiphysics 3.5a. For the semi-infinite plate, fourth order series approximations valid at the edge of the plate were obtained, while an extensive analysis for the effect of λT, Pr and inclination parameter σ was performed on the flow. Positions of the separation points when the inclination is negative (σ < 0) as a function of Pr and λT were recovered.

Ce rapport de thèse est consacré à l'étude de modèles de champ de phase de type Caginalp. Nous considérons ici, deux modèles : le premier étant une généralisation du modèle de champ de phase de Caginalp basée sur une généralisation de la loi de Maxwell-Cattaneo et le second une généralisation provenant de la théorie de la conduction de chaleur introduite par Chen et Gurtin. L'étude du premier modèle est faite aussi bien dans un domaine borné (avec un potentiel régulier puis dans le cas d'un potentiel non régulier), que dans un domaine non borné, en l'occurrence R3. Le second modèle est un problème de champ de phase avec un couplage (linéaire et non linéaire). Tout d'abord, l'existence, l'unicité et la régularité des solutions sont analysées aux moyens d'arguments classiques. Ensuite, l'existence d'ensembles bornés absorbants et compacts attractifs est établie, assurant ainsi l'existence de l'attracteur global. Enfin, dans certains cas, l'existence d'attracteurs exponentiels, ainsi que le comportement spatial des solutions lorsque le domaine spatial est un cylindre semi-infini tri-dimensionnel, sont analysés. / This thesis report is dedicated to the study of Caginalp type phase-field Models. Here, we consider two models: the first one being a generalization of the field phase Caginalp based on a generalization of the Maxwell-Cattaneo law and the second one coming from the theory of heat conduction involving two temperatures. We study the first model in bounded (with regular and irregular potentials) and unbounded (i.e. R3) domains. The second model is a phase-field one with coupling term (linear and nonlinear). Firstly, the existence, uniqueness and regularity of solutions are analyzed by means of classical arguments. Secondly, the existence of bounded absorbing sets and attractive compact is established. Such results ensures the existence of the global attractor. Finally, in some cases, the existence of exponential attractors, as well as the spatial behavior of solutions when the spatial domain is a three-dimensional semi-infinite cylinder, are analyzed.