-
作者：Chen, Liang; Chen, Ruoning; Sun, Defeng; Zhang, Liping
作者单位：Hunan University; Tsinghua University; Hong Kong Polytechnic University
摘要：In this paper, we study the Aubin property of the Karush-Kuhn-Tucker solution mapping for the nonlinear semidefinite programming (NLSDP) problem at a locally optimal solution. In the literature, it is known that the Aubin property implies the constraint nondegeneracy by Fusek (SIAM J. Optim. 23:1041-1061, 2013) and the second-order sufficient condition by Ding et al. (SIAM J. Optim. 27:67-90, 2017). Based on the Mordukhovich criterion, here we further prove that the strong second-order suffici...
-
作者：Buchheim, Christoph
作者单位：Dortmund University of Technology
摘要：Extended formulations are an important tool in polyhedral combinatorics. Many combinatorial optimization problems require an exponential number of inequalities when modeled as a linear program in the natural space of variables. However, by adding artificial variables, one can often find a small linear formulation, i.e., one containing a polynomial number of variables and constraints, such that the projection to the original space of variables yields a perfect linear formulation. Motivated by b...
-
作者：Rebjock, Quentin; Boumal, Nicolas
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Trust-region methods (TR) can converge quadratically to minima where the Hessian is positive definite. However, if the minima are not isolated, then the Hessian there cannot be positive definite. The weaker Polyak-& Lstrok;ojasiewicz (P & Lstrok;) condition is compatible with non-isolated minima, and it is enough for many algorithms to preserve good local behavior. Yet, TR with an exact subproblem solver lacks even basic features such as a capture theorem under P & Lstrok;. In practice, a popu...
-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; Lehigh University
摘要：With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the set of binary points z is an element of {0, 1}(V boolean OR S) satisfying a collection of equalities of the form z(s) = Pi(v is an element of s) sigma(s)(z(v)), for all s is an element of S, where sigma(s) (z(v)) is an element of {z(v), 1 - z(v)}, and where S is a multiset of subsets of V. By representing the pseudo-Boolean polytope via a signed hyp...
-
作者：Scott, James R.; Geunes, Joseph
作者单位：Texas A&M University System; Texas A&M University College Station; Duke University
摘要：We devise a method for minimizing a low-rank quasiconcave objective function over a polytope by first projecting the polytope's normal fan, then using the projected fan to obtain candidate solutions. When the polytope's maximal number of nonparallel edges is bounded by a polynomial in its dimension, our method solves the problem in time that is polynomial in the number of variables and exponential in the rank of the objective function. We discuss several problems from previous literature that ...
-
作者：Qiu, Yuzhou; Yildirim, E. Alper
作者单位：University of Edinburgh
摘要：We study linear programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. Using these properties, we present a complete description of the set of instances th...
-
作者：He, Ziyu; Liu, Junyi; Pang, Jong-Shi
作者单位：University of Southern California; University of Southern California; Tsinghua University
摘要：This paper explores Logarithmic Integral Optimization (LIO) problems, providing a unified computational framework for various tasks in computational statistics. Key among these are Maximum Likelihood Estimation (MLE) and Maximum a Posteriori (MAP) inference for probabilistic models. Specifically, we investigate scenarios where the model consists of conditional density functions with intractable normalizers. This feature can pose substantial computational challenges for the associated LIO, espe...
-
作者：Bestuzheva, Ksenia; Gleixner, Ambros; Achterberg, Tobias
作者单位：Zuse Institute Berlin
摘要：The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, we present a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs, which is based on analyzing linear constraints with binary variables, thus ...
-
作者：van Ee, Martijn; Oosterwijk, Tim; Sitters, Rene; Wiese, Andreas
作者单位：Vrije Universiteit Amsterdam; Technical University of Munich
摘要：We study routing problems of a convoy in a graph, generalizing the shortest path problem (SPP), the travelling salesperson problem (TSP), and the Chinese postman problem (CPP) which are all well-studied in the classical (non-convoy) setting. We assume that each edge in the graph has a length and a speed at which it can be traversed and that our convoy has a given length. While the convoy moves through the graph, parts of it can be located on different edges. For safety requirements, at all tim...
-
作者：Rebjock, Quentin; Boumal, Nicolas
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Optimization algorithms can see their local convergence rates deteriorate when the Hessian at the optimum is singular. These singularities are inescapable when the optima are non-isolated. Yet, under the right circumstances, several algorithms preserve their favorable rates even when optima form a continuum (e.g., due to over-parameterization). This has been explained under various structural assumptions, including the Polyak-& Lstrok;ojasiewicz condition, Quadratic Growth and the Error Bound....
