In this dissertation separation and selection theorems are presented. It begins by presenting a detailed proof of the Inductive Definability Theorem of D. Cenzer and R.D. Mauldin, including their boundedness principle for monotone coanalytic operators.

The main subject of this thesis is the development of new geometric tools and techniques for solving classic problems within the geometry of numbers and convex geometry. At a high level, the problems considered in this thesis concern the varied interplay between the continuous and the discrete, an important theme within computer science and operations research. The first subject we consider is the study of cutting planes for non-linear integer programs. Cutting planes have been implemented to great effect for linear integer programs, and so understanding their properties in more general settings is an important subject of study. As our contribution to this area, we show that Chvatal-Gomory closure of any compact convex set is a rational polytope. As a consequence, we resolve an open problem of Schrijver (Ann. Disc. Math. `80) regarding the same question for irrational polytopes. The second subject of study is that of ellipsoidal approximation of convex bodies. Different such notions have been important to the development of fundamental geometric algorithms: e.g. the ellipsoid method for convex optimization (enclosing ellipsoids), or random walk methods for volume estimation (inertial ellipsoids). Here we consider the construction of an ellipsoid with good "covering" properties with respect to a convex body, known in convex geometry as the M-ellipsoid. As our contribution, we give two algorithms for constructing M-ellipsoids, and provide an application to near-optimal deterministic volume estimation in the oracle model. Equipped with this new geometric tool, we move to the study of classic lattice problems in the geometry of numbers, namely the Shortest (SVP) and Closest Vector Problems (CVP). Here we use M-ellipsoid coverings, combined with an algorithm of Micciancio and Voulgaris for CVP in the ℓ₂ norm (STOC `10), to obtain the first deterministic 2^O(ⁿ) time algorithm for the SVP in general norms. Combining this algorithm with a novel lattice sparsification technique, we derive the first deterministic 2^O(ⁿ)(1+1/ϵ)ⁿ time algorithm for (1+ϵ)-approximate CVP in general norms. For the next subject of study, we analyze the geometry of general integer programs. A central structural result in this area is Kinchine's flatness theorem, which states that every lattice free convex body has integer width bounded by a function of dimension. As our contribution, we build on the work Banaszczyk, using tools from lattice based cryptography, to give a new and tighter proof of the flatness theorem. Lastly, combining all the above techniques, we consider the study of algorithms for the Integer Programming Problem (IP). As our main contribution, we give a new 2^O(ⁿ)nⁿ time algorithm for IP, which yields the fastest currently known algorithm for IP and improves on the classic works of Lenstra (MOR `83) and Kannan (MOR `87).

After introducing concepts from convex analysis, we study how to continuously transform one convex function into another. A natural choice is the arithmetic average, as it is pointwise continuous; however, this choice fails to average functions with different domains. On the contrary, the proximal average is not only continuous (in the epi-topology) but can actually average functions with disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic average) but also inherits smoothness and differentiability (unlike the arithmetic average). Then we introduce a computational framework for computer-aided convex analysis. Motivated by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope. As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit convex hull algorithm. Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions [5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12, p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can be formulated as shortest path problems.

This thesis contains two parts: the detectability of convex sets and the study on regression models In the first part of this dissertation, we investigate the problem of the detectability of an inhomogeneous convex region in a Gaussian random field. The first proposed detection method relies on checking a constructed statistic on each convex set within an nn image, which is proven to be un-applicable. We then consider using h(v)-parallelograms as the surrogate, which leads to a multiscale strategy. We prove that 2/9 is the minimum proportion of the maximally embedded h(v)-parallelogram in a convex set. Such a constant indicates the effectiveness of the above mentioned multiscale detection method. In the second part, we study the robustness, the optimality, and the computing for regression models. Firstly, for robustness, M-estimators in a regression model where the residuals are of unknown but stochastically bounded distribution are analyzed. An asymptotic minimax M-estimator (RSBN) is derived. Simulations demonstrate the robustness and advantages. Secondly, for optimality, the analysis on the least angle regressions inspired us to consider the conditions under which a vector is the solution of two optimization problems. For these two problems, one can be solved by certain stepwise algorithms, the other is the objective function in many existing subset selection criteria (including Cp, AIC, BIC, MDL, RIC, etc). The latter is proven to be NP-hard. Several conditions are derived. They tell us when a vector is the common optimizer. At last, extending the above idea about finding conditions into exhaustive subset selection in regression, we improve the widely used leaps-and-bounds algorithm (Furnival and Wilson). The proposed method further reduces the number of subsets needed to be considered in the exhaustive subset search by considering not only the residuals, but also the model matrix, and the current coefficients.

After introducing concepts from convex analysis, we study how to continuously transform one convex function into another. A natural choice is the arithmetic average, as it is pointwise continuous; however, this choice fails to average functions with different domains. On the contrary, the proximal average is not only continuous (in the epi-topology) but can actually average functions with disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic average) but also inherits smoothness and differentiability (unlike the arithmetic average). Then we introduce a computational framework for computer-aided convex analysis. Motivated by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope. As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit convex hull algorithm. Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions [5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12, p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can be formulated as shortest path problems.

After introducing concepts from convex analysis, we study how to continuously transform one convex function into another. A natural choice is the arithmetic average, as it is pointwise continuous; however, this choice fails to average functions with different domains. On the contrary, the proximal average is not only continuous (in the epi-topology) but can actually average functions with disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic average) but also inherits smoothness and differentiability (unlike the arithmetic average). Then we introduce a computational framework for computer-aided convex analysis. Motivated by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope. As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit convex hull algorithm. Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions [5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12, p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can be formulated as shortest path problems. / Graduate Studies, College of (Okanagan) / Graduate

Cette thèse est consacrée à l'étude des mesures convexes ainsi qu'aux analogies entre la théorie de Brunn-Minkowski et la théorie de l'information. Je poursuis les travaux de Costa et Cover qui ont mis en lumière des similitudes entre deux grandes théories mathématiques, la théorie de Brunn-Minkowski d'une part et la théorie de l'information d'autre part. Partant de ces similitudes, ils ont conjecturé, comme analogue de la concavité de l'entropie exponentielle, que la racine n-ième du volume parallèle de tout ensemble compact de $R^n$ est une fonction concave, et je résous cette conjecture de manière détaillée. Par ailleurs, j'étudie les mesures convexes définies par Borell et je démontre pour ces mesures une inégalité renforcée de type Brunn-Minkowski pour les ensembles convexes symétriques. Cette thèse se décompose en quatre parties. Tout d'abord, je rappelle un certain nombre de notions de base. Dans une seconde partie, j'établis la validité de la conjecture de Costa-Cover sous certaines conditions et je démontre qu'en toute généralité, cette conjecture est fausse en exhibant des contre-exemples explicites. Dans une troisième partie, j'étends les résultats positifs de cette conjecture de deux manières, d'une part en généralisant la notion de volume et d'autre part en établissant des versions fonctionnelles. Enfin, je prolonge des travaux récents de Gardner et Zvavitch en améliorant la concavité des mesures convexes sous certaines hypothèses telles que la symétrie / This thesis is devoted to the study of convex measures as well as the relationships between the Brunn-Minkowski theory and the Information theory. I pursue the works by Costa and Cover who highlighted similarities between two fundamentals inequalities in the Brunn-Minkowski theory and in the Information theory. Starting with these similarities, they conjectured, as an analogue of the concavity of entropy power, that the n-th root of the parallel volume of every compact subset of $R^n$ is concave, and I give a complete answer to this conjecture. On the other hand, I study the convex measures defined by Borell and I established for these measures a refined inequality of the Brunn-Minkowski type if restricted to convex symmetric sets. This thesis is split in four parts. First, I recall some basic facts. In a second part, I prove the validity of the conjecture of Costa-Cover under special conditions and I show that the conjecture is false in such a generality by giving explicit counterexamples. In a third part, I extend the positive results of this conjecture by extending the notion of the classical volume and by establishing functional versions. Finally, I generalize recent works of Gardner and Zvavitch by improving the concavity of convex measures under different kind of hypothesis such as symmetries

Traditionally, linear programming (LP) has been used to construct convex relaxations in the context of branch and bound for determining global optimal solutions to nonconvex optimization problems. As second-order cone programming (SOCP) and semidefinite programming (SDP) become better understood by optimization researchers, they become alternative choices for obtaining convex relaxations and producing bounds on the optimal values. In this thesis, we study the use of these convex optimization tools in constructing strong relaxations for several nonconvex problems, including 0-1 integer programming, nonconvex box-constrained quadratic programming (BoxQP), and general quadratic programming (QP). We first study a SOCP relaxation for 0-1 integer programs and a sequential relaxation technique based on this SOCP relaxation. We present desirable properties of this SOCP relaxation, for example, this relaxation cuts off all fractional extreme points of the regular LP relaxation. We further prove that the sequential relaxation technique generates the convex hull of 0-1 solutions asymptotically. We next explore nonconvex quadratic programming. We propose a SDP relaxation for BoxQP based on relaxing the first- and second-order KKT conditions, where the difficulty and contribution lie in relaxing the second-order KKT condition. We show that, although the relaxation we obtain this way is equivalent to an existing SDP relaxation at the root node, it is significantly stronger on the children nodes in a branch-and-bound setting. New advance in optimization theory allows one to express QP as optimizing a linear function over the convex cone of completely positive matrices subject to linear constraints, referred to as completely positive programming (CPP). CPP naturally admits strong semidefinite relaxations. We incorporate the first-order KKT conditions of QP into the constraints of QP, and then pose it in the form of CPP to obtain a strong relaxation. We employ the resulting SDP relaxation inside a finite branch-and-bound algorithm to solve the QP. Comparison of our algorithm with commercial global solvers shows potential as well as room for improvement. The remainder is devoted to new techniques for solving a class of large-scale linear programming problems. First order methods, although not as fast as second-order methods, are extremely memory efficient. We develop a first-order method based on Nesterov's smoothing technique and demonstrate the effectiveness of our method on two machine learning problems.

Various convex analysis of mixtures (CAM) based algorithms have been developed to address real world blind source separation (BSS) problems and proven to have good performances in previous papers. This thesis reported the implementation of a comprehensive software CAM-Java, which contains three different CAM based algorithms, CAM compartment modeling (CAM-CM), CAM non-negative independent component analysis (CAM-nICA), and CAM non-negative well-grounded component analysis (CAM-nWCA). The implementation works include: translation of MATLAB coded algorithms to open-sourced R alternatives. As well as building a user friendly graphic user interface (GUI) to integrate three algorithms together, which is accomplished by adopting Java Swing API. In order to combine R and Java coded modules, an open-sourced project RCaller is used to handle the establishment of low level connection between R and Java environment. In addition, specific R scripts and Java classes are also implemented to accomplish the tasks of passing parameters and input data from Java to R, run R scripts in Java environment, read R results back to Java, display R generated figures, and so on. Furthermore, system stream redirection and multi-threads techniques are used to build a simple R messages displaying window in Java built GUI. The final version of the software runs smoothly and stable, and the CAM-CM results on both simulated and real DCE-MRI data are quite close to the original MATLAB version algorithms. The whole GUI based open-sourced software is easy to use, and can be freely distributed among the communities. Technical details in both R and Java modules implementation are also discussed, which presents some good examples of how to develop software with both complicate and up to date algorithms, as well as decent and user friendly GUI in the scientific or engineering research fields. / Master of Science

This research formulates and implements a novel closed-loop optimal control system that drives a train between two stations in an optimal time, energy efficient, or mixed objective manner. The optimal controller uses sensor feedback from the train and in real-time computes the most efficient control decision for the train to follow given knowledge of the track profile ahead of the train, speed restrictions and required arrival time windows. The control problem is solved both on an open track and while safely driving no closer than a fixed distance behind another locomotive. In contrast to other research in the field, this thesis achieves a real-time capable and embeddable closed-loop optimization with advanced modeling and numerical solving techniques with a non-linear optimal control problem. This controller is first formulated as a non-convex control problem and then converted to an advanced convex second-order cone problem with the intent of using a simple numerical solver, ensuring global optimality, and improving control robustness. Convex and non-convex numerical methods of solving the control problem are investigated and closed-loop performance results with a simulated vehicle are presented under realistic modeling conditions on advanced tracks both on desktop and embedded computer architectures. It is observed that the controller is capable of robust vehicle driving in cases both with and without modeling uncertainty. The benefits of pairing the optimal controller with a parameter estimator are demonstrated for cases where very large mismatches exists between the controller model and the simulated vehicle. Stopping performance is consistently within 25cm of target stations, and the worst case closed-loop optimization time was within 100ms for the computation of a 1000 point control horizon on an i7-6700 machine. / Thesis / Master of Applied Science (MASc) / This research formulates and implements a novel closed-loop optimal control system that drives a train between two stations in an optimal time, energy efficient, or mixed objective manner. It is deployed on a commuter vehicle and directly manages the motoring and braking systems. The optimal controller uses sensor feedback from the train and in real-time computes the most efficient control decision for the train to follow given knowledge of the track profile ahead of the train, speed restrictions and required arrival time windows. The final control implementation is capable of safe, high accuracy and optimal driving all while computing fast enough to reliably deploy on a rail vehicle.