-
作者：Todd, M. J.
作者单位：Cornell University
摘要：We observe a curious property of dual versus primal-dual path-following interior-point methods when applied to unbounded linear or conic programming problems in dual form. While primal-dual methods can be viewed as implicitly following a central path to detect primal infeasibility and dual unboundedness, dual methods can sometimes implicitly move away from the analytic center of the set of infeasibility/unboundedness detectors.
-
作者：Takazawa, Kenjiro
作者单位：University of Tokyo; Kyoto University
摘要：An even factor in a digraph, introduced by Cunningham and Geelen (Vertex-disjoint dipaths and even dicircuits. manuscript, 2001), is a collection of vertex-disjoint dipaths and even dicycles, which generalizes a path-matching of Cunningham and Geelen (Combinatorica 17, 315-337, 1997). In a restricted class of digraphs, called odd-cycle-symmetric, Pap (Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, 3509, pp. 66-80, Springer, Heidelberg, 2005) presented a ...
-
作者：Conn, A. R.; Scheinberg, K.; Vicente, Luis N.
作者单位：Universidade de Coimbra; International Business Machines (IBM); IBM USA
摘要：We consider derivative free methods based on sampling approaches for nonlinear optimization problems where derivatives of the objective function are not available and cannot be directly approximated. We show how the bounds on the error between an interpolating polynomial and the true function can be used in the convergence theory of derivative free sampling methods. These bounds involve a constant that reflects the quality of the interpolation set. The main task of such a derivative free algor...
-
作者：Andreani, Roberto; Martinez, Jose Mario; Martinez, Leandro; Yano, Flavio
作者单位：Universidade Estadual de Campinas; Universidade Estadual de Campinas
摘要：Structural Alignment is an important tool for fold identification of proteins, structural screening on ligand databases, pharmacophore identification and other applications. In the general case, the optimization problem of superimposing two structures is nonsmooth and nonconvex, so that most popular methods are heuristic and do not employ derivative information. Usually, these methods do not admit convergence theories of practical significance. In this work it is shown that the optimization of...
-
作者：Eckstein, Jonathan; Svaiter, B. F.
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：A splitting method for two monotone operators A and B is an algorithm that attempts to converge to a zero of the sum A + B by solving a sequence of subproblems, each of which involves only the operator A, or only the operator B. Prior algorithms of this type can all in essence be categorized into three main classes, the Douglas/Peaceman-Rachford class, the forward-backward class, and the little-used double-backward class. Through a certain extended solution set in a product space, we construct...
-
作者：Louveaux, Quentin; Weismantel, Robert
作者单位：Otto von Guericke University
摘要：We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out that the sign patterns of the weight vectors are responsible for the types of combinatorial valid inequalities appearing in the description of the convex hull of the intersection. In particular, we introduce the notion of an incomplete set inequality which is based on a combinatorial principle...
-
作者：Uchoa, Eduardo; Fukasawa, Ricardo; Lysgaard, Jens; Pessoa, Artur; De Aragao, Marcus Poggi; Andrade, Diogo
作者单位：Universidade Federal Fluminense; Aarhus University; Pontificia Universidade Catolica do Rio de Janeiro; Rutgers University System; Rutgers University New Brunswick
摘要：This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to q-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence problem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms: powerful new cuts expressed ove...
-
作者：Dunagan, John; Vempala, Santosh
作者单位：Massachusetts Institute of Technology (MIT); Microsoft
摘要：The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. The resultin...
-
作者：Davis, Timothy A.; Hager, WilliamW.
作者单位：State University System of Florida; University of Florida; State University System of Florida; University of Florida
摘要：We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilev...
-
作者：Goulart, Paul J.; Kerrigan, Eric C.; Ralph, Daniel
作者单位：University of Cambridge; Imperial College London; Imperial College London; University of Cambridge
摘要：This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tracta...
