Search

Geometry plays a crucial role in machine learning. We study the geometric properties of machine learning problems and use that information to develop new algorithms that are accurate and efficient. We present three works that lie at the intersection of machine learning and geometry, and we hope to promote more research on geometry-inspired machine learning methods.We first introduce \textit{geometric policy iteration}~(GPI), a new dynamic programming approach for finite Markov decision process. Recently discovered polyhedral structures of the value function for finite discounted Markov decision processes (MDP) shed light on understanding the success of reinforcement learning. We investigate the value function polytope in greater detail and characterize the polytope boundary using a hyperplane arrangement. We further show that the value space is a union of finitely many cells of the same hyperplane arrangement, and relate it to the polytope of the classical linear programming formulation for MDPs. Inspired by these geometric properties, we propose GPI to solve discounted MDPs. GPI updates the policy of a single state by switching to an action that is mapped to the boundary of the value function polytope, followed by an immediate update of the value function. This new update rule aims at a faster value improvement without compromising computational efficiency. Moreover, our algorithm allows asynchronous updates of state values which is more flexible and advantageous compared to traditional policy iteration when the state set is large. We prove that the complexity of GPI achieves the best known bound $\bigO{\frac{|\actions|}{1 - \gamma}\log \frac{1}{1-\gamma}}$ of policy iteration and empirically demonstrate the strength of GPI on MDPs of various sizes.In the second project, we consider the \emph{integer feasibility problem}, the challenge of deciding whether a system of linear equations and inequalities has a solution with integer values. This is a famous NP-complete problem with applications in many areas of Mathematics and Computer Science. We show that the integer feasibility problem can be transformed into a 3-D tensor game which we call the \textit{Feasibility Game}~(FG). To win the game the player must find a path between the initial state and a final terminal winning state, if one exists. Finding such a winning state is equivalent to solving the integer feasibility problem. The key algebraic ingredient is a Gr\"obner basis of the toric ideal for the underlying axial transportation polyhedron. The Gr\"obner basis can be seen as a set of connecting moves (actions) of the game. We then propose a novel RL approach that trains an agent to predict moves in continuous space to cope with the large size of action space. The continuous move is then projected onto the set of legal moves so that the path always leads to valid states. As a proof of concept we demonstrate in experiments that our agent can play well the simplest version of our game for 2-way tables. Our work highlights the potential to train agents to solve non-trivial mathematical queries through contemporary machine learning methods used to train agents to play games.% In the third project, we applied persistence-based clustering for microglia segmentation which is a critical problem in biology and immunology. Light microscopy methods have continued to advance allowing for unprecedented analysis of various cell types in tissues including the brain. Although the functional state of some cell types such as microglia can be determined by morphometric analysis, techniques to perform robust, quick, and accurate measurements have not kept pace with the amount of imaging data that can now be generated. Here we present PrestoCell, a novel use of persistence-based clustering to segment cells in light microscopy images, as a customized Python-based tool that leverages the free visualization tool Napari. In evaluating and comparing PrestoCell to several existing tools, including a commercial machine-learning implementation, we demonstrate that PrestoCell produces image segmentations that rival or exceed existing solutions. In particular, our use of cell nuclei information resulted in the ability to correctly segment individual cells that were interacting with one another, increasing the accuracy of the segmentation. These benefits are in addition to the simplified graphically based user refinement of cell masks that does not require expensive commercial software licenses. We further demonstrate that PrestoCell can complete image segmentation in large samples from light sheet microscopy, allowing quantitative analysis of these large datasets. As an open-source program that leverages freely available visualization software, with minimum computer requirements, we believe that PrestoCell can significantly increase the ability of users without data or computer science expertise to perform complex image analysis. In the third work, we develop \textit{PrestoCell} which is a Python-based topological framework for segmenting objects with complex shapes. The main contribution of this work is the use of persistence-based clustering~(PBC) to generate segmentations that are topologically correct. Specifically, we use PBC to segment microglia whose 0-d homology is 1 (one connected component), and higher-order homology is 0. PBC, as an unsupervised method, is able to generate high-quality clusters that can be easily improved by some post-processing steps. Our framework is able to take as input very large 3D light microscopy imaging data where a single input volume can contain hundreds of microglia and nuclei. We use PBC to quickly generate candidate microglia clusters which are later refined by the coupled nuclei information. We present the machine-generated segmentation in the free visualization tool Napari. In evaluating and comparing PrestoCell to several existing tools, including a commercial machine-learning implementation, we demonstrate that PrestoCell produces image segmentations that rival or exceed existing solutions. In particular, our use of cell nuclei information resulted in the ability to correctly segment individual cells that were interacting with one another, increasing the accuracy of the segmentation. These benefits are in addition to the simplified graphically based user refinement of cell masks that does not require expensive commercial software licenses. We further demonstrate that PrestoCell can complete image segmentation in large samples from light sheet microscopy, allowing quantitative analysis of these large datasets. As an open-source program that leverages freely available visualization software, with minimum computer requirements, we believe that PrestoCell can significantly increase the ability of users without data or computer science expertise to perform complex image analysis.

Abstract: Oftentimes, machine learning applications using neural networks involve solving discrete optimization problems, such as in pruning, parameter-isolation-based continual learning and training of binary networks. Still, these discrete problems are combinatorial in nature and are also not amenable to gradient-based optimization. Additionally, classical approaches used in discrete settings do not scale well to large neural networks, forcing scientists and empiricists to rely on alternative methods. Among these, two main distinct sources of top-down information can be used to lead the model to good solutions: (1) extrapolating gradient information from points outside of the solution set (2) comparing evaluations between members of a subset of the valid solutions. We take continuation path (CP) methods to represent using purely the former and Monte Carlo (MC) methods to represent the later, while also noting that some hybrid methods combine the two. The main goal of this work is therefore to compare both approaches. For that purpose, we first overview the two classes while also discussing some of their drawbacks analytically. Then, on the experimental section, we compare their performances, starting with smaller Microworld experiments, which allow more fine-grained control of problem variables, and gradually moving towards larger problems in the overparametrized regime, including neural network regression and neural network pruning for image classification, where we additionally compare against magnitude-based pruning. A future version of this work will also include experiments on sequential task learning, which are currently underway.

Optimal detection is one of the most fundamental problems in communication and statistical signal processing. Nevertheless, in many applications, the optimal detection problem often reduces to an NP-complete, or even NP-hard, discrete optimization problem. This research project aims to develop randomized algorithms using Monte Carlo Markov chain methods to achieve near-optimal decision-making. In particular, this project focuses on two specific applications---signal detection in multiple-in-multiple-out systems and decoding of error correction codes. For the scenarios considered, we successfully proposed fast-converging Monte Carlo Markov chain algorithms that achieve near-optimality in reasonable iterations and outperform the previously best-known methods. These results open a new approach to optimal detection.

In this thesis, we consider situations when optimization problems include objective and/or constraint functions whose explicit forms are not directly available. We focus on two complementary situations, when those unknown functions are described by pretrained tree ensembles and when we train an explicit functional form using sample data points to substitute the unknown functions. We first study optimization problems where some objective and/or constraint functions are described by pre-trained tree ensembles. This problem is known as tree ensemble optimization. We establish a connection between tree ensemble optimization and multilinear optimization. We develop new polyhedral results for one problem through the lens of the other problem, and vice versa. Computational experiments show that our formulations provide tighter relaxations and improve the solution times compared to formulations based on modeling piecewise-linear functions and compared to existingtree ensemble formulations. We next study piecewise polyhedral relaxations of multilinear optimization. The developed results can be applied to model optimization problems when some objective and/or constraint functions are generalized decision trees. A generalized decision tree consists of a decision tree and a nonlinear model for each leaf. Given an input value, its prediction is computed by the nonlinear model associated with the leaf that the point corresponds to. We provide the first locally ideal formulation for the relaxation problem and further improve formulations by introducing linking constraints that help relatemodel components that are commonly treated independently in the literature. The implementation of our results inside of an open source mixed-integer nonlinear programming (MINLP) solver reduces by factor of approximately 3 the number of instances that the algorithm cannot solve within an hour with its default setting. Finally, we study symbolic regression, which is a form of regression that learns functional expressions from observational data. An expression tree is typically used to represent a solution function, which is determined by assigning operators and operands to the nodes. The methodology we develop is based on MINLP, which seeks global optimality given a restriction on the size of a solution expression tree. We develop tighter MINLP formulations and a heuristic that iteratively builds an expression tree by solving a restricted MINLP. In computational experiments that are aimed at discovering physics formula from sample data points, our methods outperform the best known approaches from the literature.

It is a common practice among humans to deduce, to explain and to make predictions based on concepts that are not directly observable. In Bayesian statistics, the underlying propositions of the unobserved latent variables are summarized in the posterior distribution. With the increasing complexity of real-world data and statistical models, fast and accurate inference for the posterior becomes essential. Variational methods, by casting the posterior inference problem in the optimization framework, are widely used for their flexibility and computational efficiency. In this thesis, we develop new variational methods, studying their theoretical properties and applications. In the first part of the thesis, we utilize dependence structures towards addressing fundamental problems in variational inference (VI): posterior uncertainty estimation, convergence properties, and discrete optimization. Though it is flexible, variational inference often underestimates the posterior uncertainty. This is a consequence of the over-simplified variational family. Mean-field variational inference (MFVI), for example, uses a product of independent distributions as a coarse approximation to the posterior. As a remedy, we propose a hierarchical variational distribution with flexible parameterization that can model the dependence structure between latent variables. With a newly derived objective, we show that the proposed variational method can achieve accurate and efficient uncertainty estimation. We further theoretically study the structured variational inference in the setting of the Stochastic Blockmodel (SBM). The variational distribution is constructed with a pairwise structure among the nodes of a graph. We prove that, in a broad density regime and for general random initializations, the estimated class labels by structured VI converge to the ground truth with high probability. Empirically, we demonstrate structured VI is more robust compared with MFVI when the graph is sparse and the signal to noise ratio is low. When the latent variables are discrete, gradient descent based VI often suffers from bias and high variance in the gradient estimation. With correlated random samples, we propose a novel unbiased, low-variance gradient estimator. We demonstrate that under certain constraints, such correlated sampling gives an optimal control variates for the variance reduction. The efficient gradient estimation can be applied to solve a wide range of problems such as the variable selection, reinforcement learning, natural language processing, among others. For the second part of the thesis, we apply variational methods to the study of generalization problems in the meta-learning. When trained over multiple-tasks, we identify that a variety of the meta-learning algorithms implicitly require the tasks to have a mutually-exclusive dependence structure. This prevents the task-level overfitting problem and ensures the fast adaptation of the algorithm in the face of a new task. However, such dependence structure may not exist for general tasks. When the tasks are non-mutually exclusive, we develop new meta-learning algorithms with variational regularization to prevent the task-level overfitting. Consequently, we can expand the meta-learning to the domains which it cannot be effective on before.

Networks (or graphs) are a powerful tool to model complex systems such as social networks, transportation networks, and the Web. Network design problems, including planning, implementing and augmenting networks for desirable properties, arise naturally in many applications: How to improve commute time in traffic network? How to contain fake news in social networks? How to preserve a species by conserving important properties of an ecosystem? How to promote healthier behaviour among individuals via their social interactions? However, characterizing the combinatorial effect of these network modifications leads to challenging optimization problems. From a theoretical standpoint, different from their search counterparts (e.g. computing shortest path), the design problems (e.g. optimizing shortest paths) are computationally hard. My thesis focuses on the development of algorithms for solving large-scale real-world problems using network design. In this thesis, I will discuss a few network design problems and their solutions. In the first part, I will describe design problems to optimize structural properties of a network. More specifically, I will focus on shortest path distance optimization and improvement of node centrality. In the second part, I will show how network design can be used in security related applications via leader hiding problem. Lastly, network modification will be used to improve or control network processes. In particular I will describe influence minimization and resilience maximization in networks via making optimal changes. I will present fast algorithms for these problems using continuous optimization, randomized algorithms and game theoretic techniques.

This dissertation is concerned with new ways of using oscillators to perform computational tasks. Specifically, it introduces methods for building finite state machines (for general-purpose Boolean computation) as well as Ising machines (for solving combinatorial optimization problems) using coupled oscillator networks.But firstly, why oscillators? Why use them for computation?An important reason is simply that oscillators are fascinating. Coupled oscillator systems often display intriguing synchronization phenomena where spontaneous patterns arise. From the synchronous flashing of fireflies to Huygens' clocks ticking in unison, from the molecular mechanism of circadian rhythms to the phase patterns in oscillatory neural circuits, the observation and study of synchronization in coupled oscillators has a long and rich history. Engineers across many disciplines have also taken inspiration from these phenomena, e.g., to design high-performance radio frequency communication circuits and optical lasers. To be able to contribute to the study of coupled oscillators and leverage them in novel paradigms of computing is without question an interesting andfulfilling quest in and of itself.Moreover, as Moore's Law nears its limits, new computing paradigms that are different from mere conventional complementary metal–oxide–semiconductor (CMOS) scaling have become an important area of exploration. One broad direction aims to improve CMOS performance using device technology such as fin field-effect transistors (FinFET) and gate-all-around (GAA) FETs. Other new computing schemes are based on non-CMOS material and device technology, e.g., graphene, carbon nanotubes, memristive devices, optical devices, etc.. Another growing trend in both academia and industry is to build digital application-specific integrated circuits (ASIC) suitable for speeding up certain computational tasks, often leveraging the parallel nature of unconventional non-von Neumann architectures. These schemes seek to circumvent the limitations posed at the device level through innovations at the system/architecture level.Our work on oscillator-based computation represents a direction that is different from the above and features several points of novelty and attractiveness. Firstly, it makes meaningful use of nonlinear dynamical phenomena to tackle well-defined computational tasks that span analog and digital domains. It also differs from conventional computational systems at the fundamental logic encoding level, using timing/phase of oscillation as opposed to voltage levels to represent logic values. These differences bring about several advantages. The change of logic encoding scheme has several device- and system-level benefits related to noise immunity and interference resistance. The use of nonlinear oscillator dynamics allows our systems to address problems difficult for conventional digital computation. Furthermore, our schemes are amenable to realizations using almost all types of oscillators, allowing a wide variety of devices from multiple physical domains to serve as the substrate for computing. This ability to leverage emerging multiphysics devices need not put off the realization of our ideas far into the future. Instead, implementations using well-established circuit technology are already both practical and attractive.This work also differs from all past work on oscillator-based computing, which mostly focuses on specialized image preprocessing tasks, such as edge detection, image segmentation and pattern recognition. Perhaps its most unique feature is that our systems use transitions between analog and digital modes of operation --- unlike other existing schemes that simply couple oscillators and let their phases settle to a continuum of values, we use a special type of injection locking to make each oscillator settle to one of the several well-defined multistable phase-locked states, which we use to encode logic values for computation. Our schemes of oscillator-based Boolean and Ising computation are built upon this digitization of phase; they expand the scope of oscillator-based computing significantly.Our ideas are built on years of past research in the modelling, simulation and analysis of oscillators. While there is a considerable amount of literature (arguably since Christiaan Huygens wrote about his observation of synchronized pendulum clocks in the 17th century) analyzing the synchronization phenomenon from different perspectives at different levels, we have been able to further develop the theory of injection locking, connecting the dots to find a path of analysis that starts from the low-level differential equations of individual oscillators and arrives at phase-based models and energy landscapes of coupled oscillator systems. This theoretical scaffolding is able not only to explain the operation of oscillator-based systems, but also to serve as the basis for simulation and design tools. Building on this, we explore the practical design of our proposed systems, demonstrate working prototypes, as well as develop the techniques, tools and methodologies essential for the process.

We consider a class of optimization approaches that incorporate machine learning models into the algorithm structure. Our focus is on the algorithms that can learn the patterns in the search space in order to boost computational performance. The idea is to design optimization techniques that allow for computationally efficient tuning a priori. The final objective of this work is to provide efficient solvers that can be tuned for optimal performance in serial and parallel environments.This dissertation provides a novel machine learning model based on logistic regression and describes an implementation for scheduling problems. We incorporate the proposed learning model into a well-known optimization algorithm, tabu search, and demonstrate the potential of the underlying ideas. The dissertation also establishes a new framework for comparing optimization algorithms. This framework provides a comparison of algorithms that is statistically meaningful and intuitive. Using this framework, we demonstrate that the inclusion of the logistic regression model into the tabu search method provides significant boost of its performance. Finally, we study the parallel implementation of the algorithm and evaluate the algorithm performance when more connections between threads exist.

Conic quadratic functions arise often when modeling uncertainty and risk-aversion, and are used in many fields including finance, machine-learning and robotics. Such functions are convex, and thanks to substantial efforts over the past two decades in developing techniques for convex problems, large conic quadratic optimization problems can be solved efficiently in practice. However, many decision-making problems involving logical choices are discrete in nature, and thus non-convex. Despite considerable improvements in our ability to solve mixed-integer linear optimization problems (MILO), their nonlinear and conic counterparts are still poorly understood and considered intractable.Most of the advances in solving mixed-integer nonlinear optimization (MINLO) were obtained by adapting techniques used for linear discrete optimization. One of the first approaches proposed was to construct a linearization of the nonlinear terms and solving the optimization problem as a MILO, but since such approaches solve a relaxation of the original problem, they may fail to find optimal solutions. More recent approaches that have proved successful involve using linear outer approximations with extended formulations, or using mixed-integer rounding and lift-and-project cuts, which where original proposed for MILO. However, such approaches based on previous results for MILO may fail to consider and exploit the specific structure of the nonlinear discrete problems.In this dissertation, we study the structures specific to nonlinear mixed-integer optimization. Moreover, we propose a variety of novel algorithms for conic discrete optimization. The algorithms, despite exploiting the nonlinear structure of the problems, are similar to algorithms commonly used for the linear case.In Chapter 2 we study the problem of maximizing a class of nonlinear utility functions over the vertices of an integral polytope, and propose an approximation algorithm for the problem. The algorithm exploits the fact that there exists an optimal solution to the natural convex relaxation of the problem in an edge of the polytope, and rounds the solution to a vertex. One of the principal approaches for solving discrete optimization problems to optimality are branch-and-bound algorithms. For linear problems, branch-and-bound algorithms are typically implemented using the simplex method, which allows to use warm-starts to efficiently solve the convex subproblems at each node of the branch-and-bound tree. In Chapter 3 we present a simplex method for conic quadratic minimization over polyhedra, and show that the algorithm outperforms existing methods in both convex and discrete instances.In Chapter 4 we study strong formulations for general mixed-binary conic quadratic optimization. In particular, we give a complete description of the convex hull of the lower level set of a mixed-integer conic quadratic function. The convex hull can be described in an extended formulation using a single conic quadratic constraint and exponentially many linear inequalities. Thus, the inequalities can be implemented as cutting planes using existing techniques. Our computational experiments indicate that the inequalities strengthen the formulation considerably, and often result in order-of-magnitude improvements over commercial software.In Chapter 5 we consider binary quadratic problems, which are a special case of conic quadratic problems. We propose an approach based on the decomposition of binary quadratic functions into a submodular component and a component with a convex relaxation. Then, by linearizing only the submodular component, we obtain formulations stronger than the natural convex relaxation of the problem and the formulation obtained from the full linearization of the quadratic expression. Preliminary computational experiments indicate that the proposed approach can result in considerable faster branch-and-bound algorithms. Finally, in Chapter 6 we give an overview of the main contributions in the dissertation, and provide promising directions for future research.

We explore methods for drawing a graph of DNA sequences on a digital canvas such that the Euclidean distances between sequences on the canvas suggest the distances between the sequences as calculated from pairwise sequence alignment. We use data from three plant taxa, the genus Castilleja as well as the families Caryophyllaceae and Cactaceae, to test our methods. We discuss different possible measures of the cost of a drawing, and analyze heuristic approaches to the problem including random assignment, greedy assignment, the iterated hill-climber, and simulated annealing. We find that our hill-climbing method tends to return superior drawings. Our simulated annealing method also returns drawings with low costs, but in much less time than the hill-climbing method for large datasets.

This research addresses the concept of radio resource allocation for cellular communications systems operating in congested and contested environments with an emphasis on end-to-end quality of service (QoS). The radio resource allocation is cast under a proportional fairness formulation which translates to a convex optimization problem. Moreover, the resource allocation scheme considers subscription-based and traffic differentiation in order to meet the QoS requirements of the applications running on the user equipment in the system. The devised resource allocation scheme is realized through a centralized and a distributed architecture and solution algorithms for the aforementioned architectures is derived and implemented in the mobile devices and the base stations. The sensitivity of the resource allocation scheme to the temporal dynamics of the quantity of the users in the system is investigated. Furthermore, the sensitivity of the resource allocation scheme to the temporal dynamics in the application usage percentages is accounted for. In addition, a transmission overhead of the centralized and distributed architectures for the resource allocation schemes is performed. Furthermore, the resource allocation scheme is modified to account for a possible additive bandwidth done through spectrum sharing in congested and contested environments, in particular spectrally coexistent radar systems. The radar-spectrum additive portion is devised in a way to ensure fairness of the allocation, high bandwidth utilization, and interference avoidance. In order to justify the aforesaid modification, the interference from radar systems into the Long Term Evolution (LTE) as the predominant 4G technology is studies to confirm the possibility of the spectrum sharing. The preceding interference analysis contains a detailed simulation of radar systems, propagation path loss models, and a third generation partnership project compliant LTE system. The propagation models are Free Space Path Loss (FSPL) and Irregular Terrain Model (ITM). The LTE systems under consideration are macro cell, outdoor small cells, and indoor small cells. Furthermore, the resource allocation under channel consideration is formalized such that the resources are allocated under a congested environment and based on the quality of channel the users have in the network as well as the quality of service requirements of the applications running on the mobile devices.

In today's world, it is becoming increasingly important to be able to design high performance integrated circuits (ICs) and have them run at as low power as possible. Gate sizing and threshold voltage (Vt) assignment optimizations are one of the major contributors to such trade-offs for power and performance of ICs. In fact, the ever increasing design sizes and more aggressive timing requirements make gate sizing and Vt assignment one of the most important CAD problems in physical synthesis. A promising gate sizing optimization algorithm has to satisfy requirements like being scalable to tackle very large design sizes, being able to optimally utilize a large (but finite) number of possible gate configurations available in standard cell library based on different gate sizes and/or threshold voltages (Vt) and/or gate lengths (Lg), and also, being able to handle non-convex cell delays in modern cell libraries. The work in this thesis makes use of the research-oriented infrastructure made available as part of the ISPD (International Symposium on Physical Design) 2012 Gate Sizing Contest that addresses the issues encountered in modern gate sizing problems. We present a two-phase optimization approach where Lagrangian Relaxation is used to formulate the optimization problem. In the first phase, the Lagrangian relaxed subproblem is iteratively solved using a greedy algorithm, while in the second phase, a cell downsizing and Vt upscaling heuristic is employed to further recover power from the timing-feasible and power-optimized sizing solution obtained at the end of first phase. We also propose a multi-core implementation of the first-phase optimizations, which constitute majority of the total runtime, to take advantage of multi-core processors available today. A speedup of the order of 4 to 9 times is seen on different benchmarks as compared to serial implementation when run on a 2 socket 6-core machine. Compared to the winner of ISPD 2012 contest, we further reduce leakage power by 17.21% and runtime by 87.92%, on average, while obtaining feasible sizing solutions on all the benchmark designs.

A discrete search strategy is presented to determine optimal aircraft trajectories which can be unconstrained or regulated to follow current Air Traffic Control (ATC) procedures. The heuristic based Astar (A*) search algorithm has been selected for its efficiency and its inherent ability to handle numerous constraints as a discrete method. A point-mass aircraft model is assumed to accurately simulate commercial aircraft dynamics for the provided trajectories. The two dimensional space and the states of aircraft have been divided into discrete pieces. To show the effectiveness of the algorithm, two-dimensional vertical and horizontal profile are simulated. Simulation results compare optimal trajectories that range from unconstrained to those that completely adhere to strict ATC procedures. Those trajectories following ATC procedures follow a segmented flight pattern where each segment follows specified objectives, terminating when certain criteria has been met. Trajectories are optimized for a combination of time and fuel with an emphasis on reducing fuel consumption.

The modern view of optimization is that optimization algorithms are not designed in a vacuum, but can make use of information regarding the broad class of objective functions from which a problem instance is drawn. Using this knowledge, we want to design optimization algorithms that execute quickly (efficiency), solve the objective function with minimal samples (performance), and are applicable over a wide range of problems (abstraction). However, we present a new theory for blackbox optimization from which, we conclude that of these three desired characteristics, only two can be maximized by any algorithm. We put forward an alternate view of optimization where we use knowledge about the problem class and samples from the problem instance to identify which problem instances from the class are being solved. From this Elimination of Fitness Functions approach, an idealized optimization algorithm that minimizes sample counts over any problem class, given complete knowledge about the class, is designed. This theory allows us to learn more about the difficulty of various problems, and we are able to use it to develop problem complexity bounds. We present general methods to model this algorithm over a particular problem class and gain efficiency at the cost of specifically targeting that class. This is demonstrated over the Generalized Leading-Ones problem and a generalization called LO∗∗ , and efficient algorithms with optimal performance are derived and analyzed. We also iii tighten existing bounds for LO∗∗∗. Additionally, we present a probabilistic framework based on our Elimination of Fitness Functions approach that clarifies how one can ideally learn about the problem class we face from the objective functions. This problem learning increases the performance of an optimization algorithm at the cost of abstraction. In the context of this theory, we re-examine the blackbox framework as an algorithm design framework and suggest several improvements to existing methods, including incorporating problem learning, not being restricted to blackbox framework and building parametrized algorithms. We feel that this theory and our recommendations will help a practitioner make substantially better use of all that is available in typical practical optimization algorithm design scenarios.

This research work deals with the design and optimization of a large composite structure. In design of large structural systems, it is customary to divide the problem into many smaller independent/semi-independent local design problems. For example, the wing structure design problem is decomposed into several local panel design problem. The use of composite necessitates the inclusion of ply angles as design variables. These design variables are discrete in nature because of manufacturing constraint. The multilevel approach results into a nonblended solution with no continuity of laminate layups across the panels. The nonblended solution is not desirable because of two reasons. First, the structural integrity of the whole system is questionable. Second, even if there is continuity to some extent, the manufacturing process ends up being costlier. In this work, we develop a global local design methodology to design blended composite laminates across the whole structural system. The blending constraint is imposed via a guide based approach within the genetic algorithm optimization scheme. Two different blending schemes are investigated, outer and inner blending. The global local approach is implemented for a complex composite wing structure design problem, which is known to have a strong global local coupling. To reduce the computational cost, the originally proposed local one dimensional search is replaced by an intuitive local improvement operator. The local panels design problem arises in global/local wing structure design has a straight edge boundary condition. A postbuckling analysis module is developed for such panels with applied edge displacements. A parametric study of the effects of flexural and inplane stiffnesses on the design of composite laminates for optimal postbuckling performance is done. The design optimization of composite laminates for postbuckling strength is properly formulated with stacking sequence as design variables. Next, we formulate the stacking sequence design (fiber orientation angle of the layers) of laminated composite flat panels for maximum supersonic flutter speed and maximum thermal buckling capacity. The design is constrained so that the behavior of the panel in the vicinity of the flutter boundary should be limited to stable limit cycle oscillation. A parametric study is carried out to investigate the tradeoff between designs for thermal buckling and flutter. In an effort to include the postbuckling constraint into the multilevel design optimization of large composite structure, an alternative cheap methodology for predicting load paths in postbuckled structure is presented. This approach being computationally less expensive compared to full scale nonlinear analysis can be used in conjunction with an optimizer for preliminary design of large composite structure with postbuckling constraint. This approach assumes that the postbuckled stiffness of the structure, though reduced considerably, remains linear. The analytical expressions for postbuckled stiffness are given in a form that can be used with any commercially available linear finite element solver. Using the developed approximate load path prediction scheme, a global local design approach is developed to design large composite structure with blending and local postbuckling constraints. The methodology is demonstrated via a composite wing box design with blended laminates.

Despite the success of simulated annealing to find near-optimal solutions of intractable discrete optimization problems, there have been attempts to enhance the algorithm by modifying transition probabilities. However, the asymptotic behavior of modified algorithms is very difficult to analyze, i.e., well-known convergence results of simulated annealing usually become inapplicable to other annealing algorithms. In this research, we consider a generalized annealing algorithm, the acceptance probability of which depends on the cost of the current solution, the cost of the solution candidate, and the control parameter. We present convergence results that relax sufficient conditions provided by most general convergence theorems in the literature. We study the asymptotic behavior of the stationary distribution corresponding to the generalized annealing algorithm. Using a novel approach that relies on the Markov Chain Tree Theorem, we provide a convergence theorem for the stationary distribution. By exploiting the same insights, we analyze the limiting stationary distribution of a generalized annealing algorithm that uses local information other than the cost of the current solution to guide the search. The class of convergent transition probabilities can be further extended by employing an adaptive cooling schedule. By so doing, we can relax the condition that the transition probabilities asymptotically behave like an exponential function. Based on an adaptive cooling schedule scheme, we present conditions that guarantee the convergence to optimal solutions. We develop a novel stochastic search algorithm called functional annealing that combines the attractive features of both simulated annealing and a local search technique. The algorithm can thereby benefit from exploiting a very large-scale neighborhood structure. Furthermore, we incorporate functional annealing with statistical learning techniques to enhance the finite-time performance of the algorithm. Our computational results on the Quadratic Assignment Problem reveal that functional annealing algorithms outperform many existing ones. We also present theoretical and computation results from the use of functional annealing for solving a discrete stochastic optimization problem.

Engineering optimization problems are known to be difficult to solve using mathematical programming techniques because of large search spaces, complex objective and constraint functions, and, in many cases, their combinatorial nature. Simulated annealing is a well known heuristic optimization technique that has been used to solve a number of problems in discrete, non-differential, and combinatorial optimization and hence is suitable for solving such engineering optimization problems. However, computationally intensive problems are frequently encountered in the field of engineering optimization, in which case the use of simulated annealing can be prohibitively time consuming. The objective of this thesis is to develop an object oriented framework that implements a distributed simulated annealing algorithm, which can be easily extended to solve computationally intensive engineering optimization problems. A distributed simulated annealing algorithm (DSA Algorithm) was developed and incorporated into a distributed simulated annealing framework called the DSA Framework. The framework defines interfaces, through which optimization problems can be modeled, utilizing a distributed computing framework, Vitri, to engage multiple desktop computers in a collective effort to solve problems. The framework was used to solve a 40 variable knapsack problem as a benchmark problem to analyze the performance of the algorithm. The framework was also used to optimize support locations in a piping system subject to seismic loads. The DSA framework proves to be an efficient, fairly scalable tool that shows consistent reduction in execution time with increasing number of servers, thus proving to be a valuable tool in solving computationally intensive engineering optimization problems.

This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle. This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing.

Identifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value. It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions.

Generalized hill climbing (GHC) algorithms provide a unifying framework for describing several discrete optimization problem local search heuristics, including simulated annealing and tabu search. A necessary and a sufficient convergence condition for GHC algorithms are presented. The convergence conditions presented in this dissertation are based upon a new iteration classification scheme for GHC algorithms. The convergence theory for particular formulations of GHC algorithms is presented and the implications discussed. Examples are provided to illustrate the relationship between the new convergence conditions and previously existing convergence conditions in the literature. The contributions of the necessary and the sufficient convergence conditions for GHC algorithms are discussed and future research endeavors are suggested.

Generalized hill climbing (GHC) algorithms are introduced, as a tool to address difficult discrete optimization problems. Particular formulations of GHC algorithms include simulated annealing (SA), local search, and threshold accepting (T A), among. others. A proof of convergence of GHC algorithms is presented, that relaxes the sufficient conditions for the most general proof of convergence for stochastic search algorithms in the literature (Anily and Federgruen [1987]). Proofs of convergence for SA are based on the concept that deteriorating (hill climbing) transitions between neighboring solutions are accepted by comparing a deterministic function of both the solution change cost and a temperature parameter to a uniform (0,1) random variable. GHC algorithms represent a more general model, whereby deteriorating moves are accepted according to a general random variable. Computational results are reported that illustrate relationships that exist between the GHC algorithm's finite-time performance on three problems, and the general random variable formulations used. The dissertation concludes with suggestions for further research.