1-2期

最新文章

• Structural and algorithmic properties for parametric minimum cuts AI翻译
  作者：Granot, Frieda; McCormick, S. Thomas; Queyranne, Maurice; Tardella, Fabio
  作者单位：Sapienza University Rome
  摘要：We consider the minimum s, t-cut problem in a network with parametrized arc capacities. Following the seminal work of Gallo et al. (SIAM J. Comput. 18(1):30-55, 1989), classes of this parametric problem have been shown to enjoy the nice Structural Property that minimum cuts are nested, and the nice Algorithmic Property that all minimum cuts can be computed in the same asymptotic time as a single minimum cut by using a clever Flow Update step to move from one value of the parameter to the next....
• First order conditions for semidefinite representations of convex sets defined by rational or singular polynomials AI翻译
  作者：Nie, Jiawang
  作者单位：University of California System; University of California San Diego
  摘要：A set is called semidefinite representable or semidefinite programming (SDP) representable if it equals the projection of a higher dimensional set which is defined by some Linear Matrix Inequality (LMI). This paper discusses the semidefinite representability conditions for convex sets of the form S-D(f) = {x is an element of D : f (x) >= 0}. Here, D = {x is an element of R-n : g(1)(x) >= 0, ..., g(m)(x) >= 0} is a convex domain defined by some nice concave polynomials g(i)(x) (they satisfy cer...
• A relaxed constant positive linear dependence constraint qualification and applications AI翻译
  作者：Andreani, Roberto; Haeser, Gabriel; Laura Schuverdt, Maria; Silva, Paulo J. S.
  作者单位：Universidade de Sao Paulo; Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); National University of La Plata; Universidade Federal de Sao Paulo (UNIFESP); Universidade Estadual de Campinas
  摘要：In this work we introduce a relaxed version of the constant positive linear dependence constraint qualification (CPLD) that we call RCPLD. This development is inspired by a recent generalization of the constant rank constraint qualification by Minchenko and Stakhovski that was called RCRCQ. We show that RCPLD is enough to ensure the convergence of an augmented Lagrangian algorithm and that it asserts the validity of an error bound. We also provide proofs and counter-examples that show the rela...
• A weighted independent even factor algorithm AI翻译
  作者：Takazawa, Kenjiro
  作者单位：Kyoto University
  摘要：An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cun...
• A primal-dual interior point method for nonlinear semidefinite programming AI翻译
  作者：Yamashita, Hiroshi; Yabe, Hiroshi; Harada, Kouhei
  作者单位：Tokyo University of Science
  摘要：This paper is concerned with a primal-dual interior point method for solving nonlinear semidefinite programming problems. The method consists of the outer iteration (SDPIP) that finds a KKT point and the inner iteration (SDPLS) that calculates an approximate barrier KKT point. Algorithm SDPLS uses a commutative class of Newton-like directions for the generation of line search directions. By combining the primal barrier penalty function and the primal-dual barrier function, a new primal-dual me...
• Sample average approximation of stochastic dominance constrained programs AI翻译
  作者：Hu, Jian; Homem-de-Mello, Tito; Mehrotra, Sanjay
  作者单位：Northwestern University; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
  摘要：In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of -dominance, which generalizes some notions of multi-variate do...
• Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra AI翻译
  作者：Dash, Sanjeeb; Dey, Santanu S.; Guenluek, Oktay
  作者单位：International Business Machines (IBM); IBM USA; University System of Georgia; Georgia Institute of Technology
  摘要：In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in , and various types of disjunctions. Recently Li and Richard (2008), studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (Presentation at the Spring Meeting of the American Mathematical So...
• Cone superadditivity of discrete convex functions AI翻译
  作者：Kobayashi, Yusuke; Murota, Kazuo; Weismantel, Robert
  作者单位：University of Tokyo; Swiss Federal Institutes of Technology Domain; ETH Zurich
  摘要：A function f is said to be cone superadditive if there exists a partition of R (n) into a family of polyhedral convex cones such that f(z + x) + f(z + y) a parts per thousand currency sign f(z) + f(z + x + y) holds whenever x and y belong to the same cone in the family. This concept is useful in nonlinear integer programming in that, if the objective function is cone superadditive, the global minimality can be characterized by local optimality criterion involving Hilbert bases. This paper show...
• Semidefinite programming for min-max problems and games AI翻译
  作者：Laraki, R.; Lasserre, J. B.
  作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
  摘要：We consider two min-max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796-817, 2001; Math Program B 112:65-92, 2...
• On linear and semidefinite programming relaxations for hypergraph matching AI翻译
  作者：Chan, Yuk Hei; Lau, Lap Chi
  作者单位：Chinese University of Hong Kong
  摘要：The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are th...