The Human Genome Project completed in 2003 and the draft of human genome sequences were also yielded. It has been known that any two human gnomes are almost identical, and only very little difference makes human diversities. Single nucleotide polymorphism (SNP) means that a single-base nucleotide changes in DNA. A SNP sequence from one of a pair of chromosomes is called a haplotype. In this thesis, we study how to reconstruct a pair of chromosomes from a given set of fragments obtained by DNA sequencing in an individual. We define a new problem, the chromosome pair assembly problem, for the chromosome reconstruction. The goal of the problem is to find a pair of sequences such that the pair of output sequences have the minimum mismatch with the input fragments and their lengths are minimum. We first transform the problem instance into a directed multigraph. And then we propose an efficient algorithm to solve the problem. We apply the ACO algorithm to optimize the ordering of input fragments and use dynamic programming to determine SNP sites. After the chromosome pair is reconstructed, the two haplotypes can also be determined. We perform our algorithm on some artificial test data. The experiments show that our results are near the optimal solutions of the test data.

This thesis is focused on the limits of performance of large-scale convex optimization algorithms. Classical theory of oracle complexity, first proposed by Nemirovski and Yudin in 1983, successfully established the worst-case behavior of methods based on local oracles (a generalization of first-order oracle for smooth functions) for nonsmooth convex minimization, both in the large-scale and low-scale regimes; and the complexity of approximately solving linear systems of equations (equivalent to convex quadratic minimization) over Euclidean balls, under a matrix-vector multiplication oracle. Our work extends the applicability of lower bounds in two directions: Worst-Case Complexity of Large-Scale Smooth Convex Optimization: We generalize lower bounds on the complexity of first-order methods for convex optimization, considering classes of convex functions with Hölder continuous gradients. Our technique relies on the existence of a smoothing kernel, which defines a smooth approximation for any convex function via infimal convolution. As a consequence, we derive lower bounds for \ell_p/\ell_q-setups, where 1\leq p,q\leq \infty, and extend to its matrix analogue: Smooth convex minimization (with respect to the Schatten q-norm) over matrices with bounded Schatten p-norm. The major consequences of this result are the near-optimality of the Conditional Gradient method over box-type domains (p=q=\infty), and the near-optimality of Nesterov's accelerated method over the cross-polytope (p=q=1). Distributional Complexity of Nonsmooth Convex Optimization: In this work, we prove average-case lower bounds for the complexity of nonsmooth convex ptimization. We introduce an information-theoretic method to analyze the complexity of oracle-based algorithms solving a random instance, based on the reconstruction principle. Our technique shows that all known lower bounds for nonsmooth convex optimization can be derived by an emulation procedure from a common String-Guessing Problem, which is combinatorial in nature. The derived average-case lower bounds extend to hold with high probability, and for algorithms with bounded probability error, via Fano's inequality. Finally, from the proposed technique we establish the equivalence (up to constant factors) of distributional, randomized, and worst-case complexity for black-box convex optimization. In particular, there is no gain from randomization in this setup.

Minimum Cost Polygon Overlay (MCPO) is a unique two-dimensional optimization problem that involves the task of covering a polygon shaped area with a series of rectangular shaped panels. The challenges in solving MCPO problems are related to the interdependencies that exist among the parameters and constraints that may be applied to the solution.This thesis examines the MCPO problem to construct a model that captures essential parameters to be solved using optimization algorithms. The purpose of the model is to make it possible that a solution for an MCPO problem can be generated automatically. A software application has been developed to provide a framework for validating the model.The development of the software has uncovered a host of geometric operations that are required to enable optimization to take place. Many of these operations are non-trivial, demanding novel, well-constructed algorithms based on careful appreciation of the nature of the problem.For the actual optimization task, three algorithms have been implemented: a greedy search, a Monte Carlo method, and a Genetic Algorithm. The behavior of the completed software is observed through its application on a series of test data. The results are presented to show the effectiveness of the software under various settings. This is followed by critical analysis of various findings of the research.Conclusions are drawn to summarize lessons learned from the research. Important issues about which no satisfactory explanation exists are given as material to be studied by future research.

Thesis (MSc) - Information and Communication Technology, Swinburne University of Technology, 2007. / Submitted in partial fulfilment of the requirements for the degree of Master of Science (IT), [Information and Communication Technology], Swinburne University of Technology - 2007. Typescript. Includes bibliographical references.

Thesis (M. Phil.)--University of Hong Kong, 2009. / Includes bibliographical references (leaves 156-165). Also available in print.

Thesis (Ph.D.)--University of Colorado at Boulder, 2002. / Director: Lucy Y. Pao. Includes bibliographical references.

The performance of optimization algorithms is sensitive to both the optimization problem's numerical characteristics and the termination criteria of the algorithm. Given these considerations two tuning algorithms named tMOPSO and MOTA are proposed to assist optimization practitioners to nd algorithm settings which are approximate for the problem at hand. For a speci ed problem tMOPSO aims to determine multiple groups of control parameter values, each of which results in optimal performance at a di erent objective function evaluation budget. To achieve this, the control parameter tuning problem is formulated as a multi-objective optimization problem. Furthermore, tMOPSO uses a noise-handling strategy and control parameter value assessment procedure, which are specialized for tuning stochastic optimization algorithms. The principles upon which tMOPSO were designed are expanded into the context of many objective optimization, to create the MOTA tuning algorithm. MOTA tunes an optimization algorithm to multiple problems over a range of objective function evaluation budgets. To optimize the resulting many objective tuning problem, MOTA makes use of bi-objective decomposition. The last section of work entails an application of the tMOPSO and MOTA algorithms to benchmark optimization algorithms according to their tunability. Benchmarking via tunability is shown to be an effective approach for comparing optimization algorithms, where the various control parameter choices available to an optimization practitioner are included into the benchmarking process. / Thesis (PhD)--University of Pretoria, 2014 / gm2015 / Mechanical and Aeronautical Engineering / PhD / Unrestricted

No description available.

We study a parameter identification problem for the steady state diffusion equations. In this thesis, we transform this identification problem into a minimization problem by considering an appropriate cost functional and propose a finite element method for the identification of the parameter for the linear and nonlinear partial differential equation. The cost functional involves the classical output least square term, a term approximating the derivative of the piezometric head 𝑢(𝑥), an equation error term plus some regularization terms, which happen to be a norm or a semi-norm of the variables in the cost functional in an appropriate Sobolev space. The existence and uniqueness of the minimizer for the cost functional is proved. Error estimates in a weighted 𝐻⁻¹-norm, 𝐿²-norm and 𝐿¹-norm for the numerical solution are derived. Numerical examples will be given to show features of this numerical method. / Ph. D.

Proliferation of non-linear, single-phase power electronics loads, such as personal computers, television sets, CFLs, has resulted in thousands of individual small harmonic current injectors connected to a distribution feeder network. Harmonic standard: IEC 1000-3-2 classifies such loads as Class D, “low-voltage” equipment with current emissions limited to 16A/Phase. Individual harmonic contributions of such loads appear insignificant; their collective contribution, however, is a matter of concern. The average order of voltage distortion usually varies between 4-6%; current distortion, however, is usually of the order of 100%. Limitations and high-costs associated with conventional harmonic mitigation measures, has furthered the need for regulation and alternative strategies. The objective of this research is to predict, and mitigate the effects of harmonic proliferation in the main supply current measured at the point of common coupling (PCC). An equivalent circuit model – an aggregation of single phase power electronics loads connected to the distribution feeder network is proposed as a part of a forward solution. Each load, individually, behaves as a harmonic current source; the proposed model combines these individual harmonic current injectors into a single harmonic source connected at the PCC and their collective contribution as a single composite harmonic signal. It represents harmonic conditions at the PCC and provides a theoretical measure of harmonic distortion in the supply current. Such a model finds application during harmonic compliance testing for single-phase power electronics loads; it simulates and predicts the harmonic response of such loads using a theoretical pure 60 Hz sine wave as the supply voltage diffcult to obtain physically, yet critical to such tests. The accuracy of the equivalent circuit model in predicting a harmonic response is pivotal to a successful forward solution. A feed-backwards mechanism is proposed. For a given harmonic supply voltage and circuit configuration of the equivalent circuit model, the feed-backwards method generates the modeled response and compares it to a reference physical response. Finally, it optimizes the circuit configuration to a unique Correction Factor that facilitates an accurate modeled response. Three optimization algorithms, labeled as Response Optimization algorithms have been developed to execute the feed-backwards mechanism. These algorithms are written in FORTRAN-90. / text