Search

This paper establishes a closed-form expression for projecting onto a capped rotated second-order cone. This special object is a convex set that arises as a part of the feasible region of the perspective relaxation of mixed-integer nonlinear programs (MINLP) with binary indicator variables. The rapid computation of the projection onto this convex set enables the development of effective methods for solving the continuous relaxation of MINLPs whose feasible region may involve a Cartesian product of a large number of such sets. As a proof of concept for the applicability of our projection method, we develop a projected gradient method and specialize a general form of FISTA to use our projection technique in order to effectively solve the continuous perspective relaxation of a sparse regression problem with $L_0$ and $L_2$ penalties. We also generalize the basic sparse regression formulation and solution method to support group sparsity. In experiments we first demonstrate that the projection problem is solved faster and more accurately with our closed-form than with an interior-point solver, and also when solving sparse regression problems our methods that applies our projection formula can outperform a state-of-the-art interior point solver while nearly matching its solution accuracy.

Mathematical programming formulations are developed for a problem motivated by determining chains of organ-donation exchange pairs in a compatibility graph. The objective is to maximize the expected value where pairs are known to fail with given probabilities. Historically this NP-hard problem has been solved heuristically or exactly only for limited path lengths. Although the problem appears highly nonlinear, we formulate it as a mixed-integer linear program (MILP). A computationally tractable layered formulation that approximately solves larger instances is also presented.

We consider robust variants of the bin-packing problem where the sizes of the items can take any value in a given uncertainty set U ⊆ × n i=1 [ai, ai + ˆ ai], where a ∈ [0, 1] n represents the nominal sizes of the items andâandˆandâ ∈ [0, 1] n their possible deviations. We consider more specifically two uncertainty sets previously studied in the literature. The first set, denoted U Γ , contains scenarios in which at most Γ ∈ N items deviate, each of them reaching its peak value ai + ˆ ai, while each other item has its nominal value ai. The second set, denoted U Ω , bounds by Ω ∈ [0, 1] the total amount of deviation in each scenario. We show that a variant of the next-fit algorithm provides a 2-approximation for model U Ω , and a 2(Γ +1) approximation for model U Γ (which can be improved to 2 approximation for Γ = 1). This motivates the question of the existence of a constant ratio approximation algorithm for the U Γ model. Our main result is to answer positively to this question by providing a 4.5 approximation for U Γ model based on dynamic programming.

Classification and supervised learning problems in general aim to choose a function that best describes a relation between a set of observed attributes and their corresponding outputs. We focus on binary classification, where the output is a binary response variable. In this dissertation, we seek motivation within statistical learning theory, which attempts to estimate how well a classification function generalizes with respect to unseen data in a probabilistic setting.We study linear programming formulations for finding a hyperplane that separates two sets of points. Such formulations were initially given by Mangasarian (1965) for the separable case, and more recently extended by "soft margin'' formulations that maximize the margin of separation subject to a penalty proportional to the sum of margin violations. LP-Boost is a boosting algorithm which solves the large scale linear program in a high dimensional space of features using a column generation solution technique. While many authors have developed different boosting algorithms that assume the existence of effective base learning algorithms for generating a feature or base classifier (e.g., solving the pricing problem with a column generation approach), there has not been much work done to propose such algorithms. In this dissertation, we propose a branch-and-bound algorithm for finding a Boolean monomial that best agrees with the given set of data. This problem has been known as maximum monomial agreement and has been mostly studied in the computational complexity and learning communities in the context of negative computational complexity results. Here we propose an algorithm that finds the monomial that best agrees with the given data and show that it is computationally efficient in practice for UCI datasets.Revisiting the problem of finding weighted voting classifiers, we consider the problem of balancing the sparsity of the vector of weights and accuracy with respect to the given the training data. It has been suggested by several authors to minimize the L1-norm of the normal vector of the separating hyperplane in order to find sparse solutions. In contrast, we formulate the discrete optimization problem of minimizing the sum of disagreements of a weighted voting classifier and a penalty proportional to the number of nonzero components of the hyperplane's normal vector. The problem that we propose extends the NP-hard Minimum Disagreement Halfspace problem studied in computational learning theory. We are able to formulate this problem as a Mixed Integer Linear Program (MILP), and show that the continuous relaxation of the MILP is equivalent to the well-known L1-norm minimizing LP for finding weighted voting classifiers. We proceed by suggesting novel cutting planes to tighten the continuous relaxation. Finally, we propose and test a novel boosting algorithm that solves the relaxation by dynamic generation of columns and cuts. The algorithm used for generating the columns in this procedure generalizes our algorithm for maximum monomial agreement. In our experiments with the novel MILP relaxation, we demonstrate that our formulation, as well as solution technique, provide an effective approach for constructing sparse and accurate classifiers, and balancing the tradeoff between the two.