2期

最新文章

• On cardinality constrained cycle and path polytopes AI翻译
  作者：Kaibel, Volker; Stephan, Ruediger
  作者单位：Otto von Guericke University; Technical University of Berlin
  摘要：Given a directed graph D = (N, A) and a sequence of positive integers 1 = c(1) < c(2) < center dot center dot center dot < cm = |N|, we consider those path and cycle polytopes that are defined as the convex hulls of the incidence vectors simple paths and cycles of D of cardinality c(p) for some p is an element of {1, ..., m}, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial t...
• An integer programming approach for linear programs with probabilistic constraints AI翻译
  作者：Luedtke, James; Ahmed, Shabbir; Nemhauser, George L.
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University System of Georgia; Georgia Institute of Technology
  摘要：Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation corresponding to a single row of the probabilistic constraint. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain n...
• Approximation accuracy, gradient methods, and error bound for structured convex optimization AI翻译
  作者：Tseng, Paul
  作者单位：University of Washington; University of Washington Seattle
  摘要：Convex optimization problems arising in applications, possibly as approximations of intractable problems, are often structured and large scale. When the data are noisy, it is of interest to bound the solution error relative to the (unknown) solution of the original noiseless problem. Related to this is an error bound for the linear convergence analysis of first-order gradient methods for solving these problems. Example applications include compressed sensing, variable selection in regression, ...
• Computing deep facet-defining disjunctive cuts for mixed-integer programming AI翻译
  作者：Cadoux, Florent
  摘要：The problem of separation is to find an affine hyperplane, or cut, that lies between the origin O and a given closed convex set Q in a Euclidean space. We study cuts which are deep in a well-defined geometrical sense, and facet-defining. The cases when the deepest cut is decomposable as a combination of facet-defining cuts are characterized using the reverse polar set. When Q is a disjunctive polyhedron, a description of the reverse polar, linked to the so-called cut generating linear program ...
• The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm AI翻译
  作者：Dumitrescu, Irina; Ropke, Stefan; Cordeau, Jean-Francois; Laporte, Gilbert
  作者单位：Universite de Montreal; HEC Montreal; University of Sydney; Universite de Montreal; HEC Montreal
  摘要：The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and seve...
• Copositive programming motivated bounds on the stability and the chromatic numbers AI翻译
  作者：Dukanovic, Igor; Rendl, Franz
  作者单位：University of Maribor; University of Klagenfurt
  摘要：The Lovasz theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovasz theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NP-hard. This motivates the study of tractable ap...
• A generalization of column generation to accelerate convergence AI翻译
  作者：Liang, Dong; Wilhelm, Wilbert E.
  作者单位：Texas A&M University System; Texas A&M University College Station
  摘要：This paper proposes a generalization of column generation, reformulating the master problem with fewer variables at the expense of adding more constraints; the sub-problem structure does not change. It shows both analytically and computationally that the reformulation promotes faster convergence to an optimal solution in application to a linear program and to the relaxation of an integer program at each node in the branch-and-bound tree. Further, it shows that this reformulation subsumes and g...
• Risk-averse dynamic programming for Markov decision processes AI翻译
  作者：Ruszczynski, Andrzej
  作者单位：Rutgers University System; Rutgers University New Brunswick
  摘要：We introduce the concept of a Markov risk measure and we use it to formulate risk-averse control problems for two Markov decision models: a finite horizon model and a discounted infinite horizon model. For both models we derive risk-averse dynamic programming equations and a value iteration method. For the infinite horizon problem we develop a risk-averse policy iteration method and we prove its convergence. We also propose a version of the Newton method to solve a nonsmooth equation arising i...
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints AI翻译
  作者：He, Simai; Li, Zhening; Zhang, Shuzhong
  作者单位：Chinese University of Hong Kong; City University of Hong Kong
  摘要：In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time app...
• An inexact Newton method for nonconvex equality constrained optimization AI翻译
  作者：Byrd, Richard H.; Curtis, Frank E.; Nocedal, Jorge
  作者单位：Northwestern University; University of Colorado System; University of Colorado Boulder; Northwestern University
  摘要：We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351-369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal-dual iteration mat...