No description available.

No description available.

No description available.

In this thesis, we study two optimization problems which have a lot of important applications in diverse domains: Line Cover Problem (LCP) in Computational Geometry and Maximum Genus Embedding (MGE) in Topological Graph Theory. We study LCP whose decision version is known NP-Complete from the perspective of Parameterized Complexity, as well as classical techniques in Algorithm Design. In particular, we provide an exact algorithm in time O(n^3 2n) based on Dynamic Programming and initiate a dual problem of LCP in terms of Linear Programming Duality. We study the dual problem by applying approximation and kernelization, obtaining an approximation algorithm with ratio k - 1 and a kernel of size O(k^4). Then we survey related geometric properties on LCP. Finally we propose a Parameterized Algorithm to solve LCP with running time O*(k^k/1:35^k). We explore connections between the maximum genus of a graph and its cycle space consisting of fundamental cycles only. We revisit a known incorrect approach of finding a maximum genus embedding via computing a maximum pairing of intersected fundamental cycles with respect to an arbitrary spanning tree. We investigate the reason it failed and conclude it confused the concept of deficiency. Also, we characterize the upper-embeddablity of a graph in terms of maximum pairings of intersected fundamental cycles, i.e. a graph is upper-embeddable if and only if the number of maximum pairings of intersected fundamental cycles for any spanning tree is the same. Finally, we present a lower and an upper bound of the maximum number of vertex-disjoint cycles in a general graph, beta(G) - 2gammaM(G) and beta(G) - gammaM(G), only depending on maximum genus and cycle rank.

No description available.

Optimization problems are divided into numerical optimization problems and combinatorial optimization problems. Genetic algorithms (GAs) are applied to solve optimization problems widely. GAs with multi-parent crossover are often used to solve numerical optimization problems. However, no effective multi-parent crossover is used for combinatorial optimization problems. Partially mapped crossover (PMX) is the most popular crossover for combinatorial optimization problems. In this thesis, we propose multi-parent partially mapped crossover (MPPMX). A large amount of experimental results show that the improvement ratio of MPPMX reaches 38.63 % over PMX. The p-values of t-test on the difference between MPPMX and PMX range from 10-6 to 10-14, which indicates the significant improvement of MPPMX over PMX.

5th IFAC Symposium on Mechatronic Systems, Marriott Boston Cambridge, Cambridge, MA, USA, Sept 13-15, 2010

The optimization problems involving stochastic systems are often encountered in financial systems, networks design and routing, supply-chain management, actuarial science, telecommunications systems, statistical pattern recognition analysis associated with electronic commerce and medical diagnosis. / This thesis aims to develop computational methods for solving three optimization problems, where their dynamical systems are described by three different classes of stochastic systems with jumps. / In Chapter 1, a brief review on optimization problems involving stochastic systems with jumps is given. It is then followed by the introduction of three optimization problems, where their dynamical systems are described by three different classes of stochastic systems with jumps. These three stochastic optimization problems will be studied in detail in Chapters 2, 3 and 4, respectively. The literature reviews on optimization problems involving these three stochastic systems with jumps are presented in the last three sections of each of Chapters 2, 3 and 4, respectively. / In Chapter 2, an optimization problem involving nonparametric regression with jump points is considered. A two-stage method is proposed for nonparametric regression with jump points. In the first stage, we identify the rough locations of all the possible jump points of the unknown regression function. In the second stage, we map the yet to be decided jump points into pre-assigned fixed points. In this way, the time domain is divided into several sections. Then the spline function is used to approximate each section of the unknown regression function. These approximation problems are formulated and subsequently solved as optimization problems. The inverse time scaling transformation is then carried out, giving rise to an approximation to the nonparametric regression with jump points. For illustration, several examples are solved by using this method. The result obtained are highly satisfactory. / In Chapter 3, the optimization problem involving nonparametric regression with jump curves is studied. A two-stage method is presented to construct an approximating surface with jump location curve from a set of observed data which are corrupted with noise. In the first stage, we detect an estimate of the jump location curve in a surface. In the second stage, we shift the jump location curve into a row pixels or column pixels. The shifted region is then divided into two disjoint subregions by the jump location row pixels. These subregions are expanded to two overlapping expanded subregions, each of which includes the jump location row pixels. We calculate artificial values at these newly added pixels by using the observed data and then approximate the surface on each expanded subregions in which the artificial values at the pixels in the jump location row pixels for each expanded subregion. The curve with minimal distance between the two surfaces is chosen as the curve dividing the region. Subsequently, two nonoverlapping tensor product cubic spline surfaces are obtained. Then, by carrying out the inverse space scaling transformation, the two fitted smooth surfaces in the original space are obtained. For illustration, a numerical example is solved using the method proposed. / In Chapter 4, a class of stochastic optimal parameter selection problems described by linear Ito stochastic differential equations with state jumps subject to probabilistic constraints on the state is considered, where the times at which the jumps occurred as well as their heights are decision variables. We show that this constrained stochastic impulsive optimal parameter selection problem is equivalent to a deterministic impulsive optimal parameter selection problem subject to continuous state inequality constraints, where the times at which the jumps occurred as well as their heights remain as decision variables. Then we show that this constrained deterministic impulsive optimal parameter selection problem can be transformed into an equivalent constrained deterministic impulsive optimal parameter selection problem with fixed jump times. We approximate the continuous state inequality constraints by a sequence of canonical inequality constraints. This leads to a sequence of approximate deterministic impulsive optimal parameter selection problems subject to canonical inequality constraints. For each of these approximate problems, we derive the gradient formulas of the cost function and the constraint functions. On this basis, an efficient computational method is developed. For illustration, a numerical example is solved. / Finally, Chapter 5 contains some concluding remarks and suggestions for future studies.

No description available.

Thesis (MSc (Mathematics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: The first approach initiated by Merton [Mer69, Mer71] to solve utility maximization portfolio problems in continuous time is based on stochastic control theory. The idea of Merton was to interpret the maximization portfolio problem as a stochastic control problem where the trading strategies are considered as a control process and the portfolio wealth as the controlled process. Merton derived the Hamilton-Jacobi-Bellman (HJB) equation and for the special case of power, logarithm and exponential utility functions he produced a closedform solution. A principal disadvantage of this approach is the requirement of the Markov property for the stocks prices. The so-called martingale method represents the second approach for solving utility maximization portfolio problems in continuous time. It was introduced by Pliska [Pli86], Cox and Huang [CH89, CH91] and Karatzas et al. [KLS87] in di erent variant. It is constructed upon convex duality arguments and allows one to transform the initial dynamic portfolio optimization problem into a static one and to resolve it without requiring any \Markov" assumption. A de nitive answer (necessary and su cient conditions) to the utility maximization portfolio problem for terminal wealth has been obtained by Kramkov and Schachermayer [KS99]. In this thesis, we study the convex duality approach to the expected utility maximization problem (from terminal wealth) in continuous time stochastic markets, which as already mentioned above can be traced back to the seminal work by Merton [Mer69, Mer71]. Before we detail the structure of our thesis, we would like to emphasize that the starting point of our work is based on Chapter 7 in Pham [P09] a recent textbook. However, as the careful reader will notice, we have deepened and added important notions and results (such as the study of the upper (lower) hedge, the characterization of the essential supremum of all the possible prices, compare Theorem 7.2.2 in Pham [P09] with our stated Theorem 2.4.9, the dynamic programming equation 2.31, the superhedging theorem 2.6.1...) and we have made a considerable e ort in the proofs. Indeed, several proofs of theorems in Pham [P09] have serious gaps (not to mention typos) and even aws (for example see the proof of Proposition 7.3.2 in Pham [P09] and our proof of Proposition 3.4.8). In the rst chapter, we state the expected utility maximization problem and motivate the convex dual approach following an illustrative example by Rogers [KR07, R03]. We also brie y review the von Neumann - Morgenstern Expected Utility Theory. In the second chapter, we begin by formulating the superreplication problem as introduced by El Karoui and Quenez [KQ95]. The fundamental result in the literature on super-hedging is the dual characterization of the set of all initial endowments leading to a super-hedge of a European contingent claim. El Karoui and Quenez [KQ95] rst proved the superhedging theorem 2.6.1 in an It^o di usion setting and Delbaen and Schachermayer [DS95, DS98] generalized it to, respectively, a locally bounded and unbounded semimartingale model, using a Hahn-Banach separation argument. The superreplication problem inspired a very nice result, called the optional decomposition theorem for supermartingales 2.4.1, in stochastic analysis theory. This important theorem introduced by El Karoui and Quenez [KQ95], and extended in full generality by Kramkov [Kra96] is stated in Section 2.4 and proved at the end of Section 2.7. The third chapter forms the theoretical core of this thesis and it contains the statement and detailed proof of the famous Kramkov-Schachermayer Theorem that addresses the duality of utility maximization portfolio problems. Firstly, we show in Lemma 3.2.1 how to transform the dynamic utility maximization problem into a static maximization problem. This is done thanks to the dual representation of the set of European contingent claims, which can be dominated (or super-hedged) almost surely from an initial endowment x and an admissible self- nancing portfolio strategy given in Corollary 2.5 and obtained as a consequence of the optional decomposition of supermartingale. Secondly, under some assumptions on the utility function, the existence and uniqueness of the solution to the static problem is given in Theorem 3.2.3. Because the solution of the static problem is not easy to nd, we will look at it in its dual form. We therefore synthesize the dual problem from the primal problem using convex conjugate functions. Before we state the Kramkov-Schachermayer Theorem 3.4.1, we present the Inada Condition and the Asymptotic Elasticity Condition for Utility functions. For the sake of clarity, we divide the long and technical proof of Kramkov-Schachermayer Theorem 3.4.1 into several lemmas and propositions of independent interest, where the required assumptions are clearly indicate for each step of the proof. The key argument in the proof of Kramkov-Schachermayer Theorem is an in nitedimensional version of the minimax theorem (the classical method of nding a saddlepoint for the Lagrangian is not enough in our situation), which is central in the theory of Lagrange multipliers. For this, we have stated and proved the technical Lemmata 3.4.5 and 3.4.6. The main steps in the proof of the the Kramkov-Schachermayer Theorem 3.4.1 are: We show in Proposition 3.4.9 that the solution to the dual problem exists and we characterize it in Proposition 3.4.12. From the construction of the dual problem, we nd a set of necessary and su cient conditions (3.1.1), (3.1.2), (3.3.1) and (3.3.7) for the primal and dual problems to each have a solution. Using these conditions, we can show the existence of the solution to the given problem and characterize it in terms of the market parameters and the solution to the dual problem. In the last chapter we will present and study concrete examples of the utility maximization portfolio problem in speci c markets. First, we consider the complete markets case, where closed-form solutions are easily obtained. The detailed solution to the classical Merton problem with power utility function is provided. Lastly, we deal with incomplete markets under It^o processes and the Brownian ltration framework. The solution to the logarithmic utility function as well as to the power utility function is presented. / AFRIKAANSE OPSOMMING: Die eerste benadering, begin deur Merton [Mer69, Mer71], om nutsmaksimering portefeulje probleme op te los in kontinue tyd is gebaseer op stogastiese beheerteorie. Merton se idee is om die maksimering portefeulje probleem te interpreteer as 'n stogastiese beheer probleem waar die handelstrategi e as 'n beheer-proses beskou word en die portefeulje waarde as die gereguleerde proses. Merton het die Hamilton-Jacobi-Bellman (HJB) vergelyking afgelei en vir die spesiale geval van die mags, logaritmies en eksponensi ele nutsfunksies het hy 'n oplossing in geslote-vorm gevind. 'n Groot nadeel van hierdie benadering is die vereiste van die Markov eienskap vir die aandele pryse. Die sogenaamde martingale metode verteenwoordig die tweede benadering vir die oplossing van nutsmaksimering portefeulje probleme in kontinue tyd. Dit was voorgestel deur Pliska [Pli86], Cox en Huang [CH89, CH91] en Karatzas et al. [KLS87] in verskillende wisselvorme. Dit word aangevoer deur argumente van konvekse dualiteit, waar dit in staat stel om die aanvanklike dinamiese portefeulje optimalisering probleem te omvorm na 'n statiese een en dit op te los sonder dat' n \Markov" aanname gemaak hoef te word. 'n Bepalende antwoord (met die nodige en voldoende voorwaardes) tot die nutsmaksimering portefeulje probleem vir terminale vermo e is verkry deur Kramkov en Schachermayer [KS99]. In hierdie proefskrif bestudeer ons die konveks dualiteit benadering tot die verwagte nuts maksimering probleem (van terminale vermo e) in kontinue tyd stogastiese markte, wat soos reeds vermeld is teruggevoer kan word na die seminale werk van Merton [Mer69, Mer71]. Voordat ons die struktuur van ons tesis uitl^e, wil ons graag beklemtoon dat die beginpunt van ons werk gebaseer is op Hoofstuk 7 van Pham [P09] se onlangse handboek. Die noukeurige leser sal egter opmerk, dat ons belangrike begrippe en resultate verdiep en bygelas het (soos die studie van die boonste (onderste) verskansing, die karakterisering van die noodsaaklike supremum van alle moontlike pryse, vergelyk Stelling 7.2.2 in Pham [P09] met ons verklaarde Stelling 2.4.9, die dinamiese programerings vergelyking 2.31, die superverskansing stelling 2.6.1...) en ons het 'n aansienlike inspanning in die bewyse gemaak. Trouens, verskeie bewyse van stellings in Pham cite (P09) het ernstige gapings (nie te praat van setfoute nie) en selfs foute (kyk byvoorbeeld die bewys van Stelling 7.3.2 in Pham [P09] en ons bewys van Stelling 3.4.8). In die eerste hoofstuk, sit ons die verwagte nutsmaksimering probleem uit een en motiveer ons die konveks duaale benadering gebaseer op 'n voorbeeld van Rogers [KR07, R03]. Ons gee ook 'n kort oorsig van die von Neumann - Morgenstern Verwagte Nutsteorie. In die tweede hoofstuk, begin ons met die formulering van die superreplikasie probleem soos voorgestel deur El Karoui en Quenez [KQ95]. Die fundamentele resultaat in die literatuur oor super-verskansing is die duaale karakterisering van die versameling van alle eerste skenkings wat lei tot 'n super-verskans van' n Europese voorwaardelike eis. El Karoui en Quenez [KQ95] het eers die super-verskansing stelling 2.6.1 bewys in 'n It^o di usie raamwerk en Delbaen en Schachermayer [DS95, DS98] het dit veralgemeen na, onderskeidelik, 'n plaaslik begrensde en onbegrensde semimartingale model, met 'n Hahn-Banach skeidings argument. Die superreplikasie probleem het 'n prag resultaat ge nspireer, genaamd die opsionele ontbinding stelling vir supermartingales 2.4.1 in stogastiese ontledings teorie. Hierdie belangrike stelling wat deur El Karoui en Quenez [KQ95] voorgestel is en tot volle veralgemening uitgebrei is deur Kramkov [Kra96] is uiteengesit in Afdeling 2.4 en bewys aan die einde van Afdeling 2.7. Die derde hoofstuk vorm die teoretiese basis van hierdie proefskrif en bevat die verklaring en gedetailleerde bewys van die beroemde Kramkov-Schachermayer stelling wat die dualiteit van nutsmaksimering portefeulje probleme adresseer. Eerstens, wys ons in Lemma 3.2.1 hoe om die dinamiese nutsmaksimering probleem te omskep in 'n statiese maksimerings probleem. Dit kan gedoen word te danke aan die duaale voorstelling van die versameling Europese voorwaardelike eise, wat oorheers (of super-verskans) kan word byna seker van 'n aanvanklike skenking x en 'n toelaatbare self- nansierings portefeulje strategie wat in Gevolgtrekking 2.5 gegee word en verkry is as gevolg van die opsionele ontbinding van supermartingale. In die tweede plek, met sekere aannames oor die nutsfunksie, is die bestaan en uniekheid van die oplossing van die statiese probleem gegee in Stelling 3.2.3. Omdat die oplossing van die statiese probleem nie maklik verkrygbaar is nie, sal ons kyk na die duaale vorm. Ons sintetiseer dan die duale probleem van die prim^ere probleem met konvekse toegevoegde funksies. Voordat ons die Kramkov-Schachermayer Stelling 3.4.1 beskryf, gee ons die Inada voorwaardes en die Asimptotiese Elastisiteits Voorwaarde vir Nutsfunksies. Ter wille van duidelikheid, verdeel ons die lang en tegniese bewys van die Kramkov-Schachermayer Stelling ref in verskeie lemmas en proposisies op, elk van onafhanklike belang waar die nodige aannames duidelik uiteengesit is vir elke stap van die bewys. Die belangrikste argument in die bewys van die Kramkov-Schachermayer Stelling is 'n oneindig-dimensionele weergawe van die minimax stelling (die klassieke metode om 'n saalpunt vir die Lagrange-funksie te bekom is nie genoeg in die geval nie), wat noodsaaklik is in die teorie van Lagrange-multiplikators. Vir die, meld en bewys ons die tegniese Lemmata 3.4.5 en 3.4.6. Die belangrikste stappe in die bewys van die die Kramkov-Schachermayer Stelling 3.4.1 is: Ons wys in Proposisie 3.4.9 dat die oplossing vir die duale probleem bestaan en ons karaktiriseer dit in Proposisie 3.4.12. Uit die konstruksie van die duale probleem vind ons 'n versameling nodige en voldoende voorwaardes (3.1.1), (3.1.2), (3.3.1) en (3.3.7) wat die prim^ere en duale probleem oplossings elk moet aan voldoen. Deur hierdie voorwaardes te gebruik, kan ons die bestaan van die oplossing vir die gegewe probleem wys en dit karakteriseer in terme van die mark parameters en die oplossing vir die duale probleem. In die laaste hoofstuk sal ons konkrete voorbeelde van die nutsmaksimering portefeulje probleem bestudeer vir spesi eke markte. Ons kyk eers na die volledige markte geval waar geslote-vorm oplossings maklik verkrygbaar is. Die gedetailleerde oplossing vir die klassieke Merton probleem met mags nutsfunksie word voorsien. Ten slotte, hanteer ons onvolledige markte onderhewig aan It^o prosesse en die Brown ltrering raamwerk. Die oplossing vir die logaritmiese nutsfunksie, sowel as die mags nutsfunksie word aangebied.