2期

最新文章

• Hirsch polytopes with exponentially long combinatorial segments AI翻译
  作者：Labbe, Jean-Philippe; Manneville, Thibault; Santos, Francisco
  作者单位：Hebrew University of Jerusalem; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Institut Polytechnique de Paris; Ecole Polytechnique; Universidad de Cantabria
  摘要：In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340-1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent ...
• Polynomial root radius optimization with affine constraints AI翻译
  作者：Eaton, Julia; Grundel, Sara; Gurbuzbalaban, Mert; Overton, Michael L.
  作者单位：University of Washington; University of Washington Tacoma; Max Planck Society; Rutgers University System; Rutgers University New Brunswick; New York University
  摘要：The root radius of a polynomial is the maximum of the moduli of its roots (zeros). We consider the following optimization problem: minimize the root radius over monic polynomials of degree n, with either real or complex coefficients, subject to k linearly independent affine constraints on the coefficients. We show that there always exists an optimal polynomial with at most inactive roots, that is, roots whose moduli are strictly less than the optimal root radius. We illustrate our results usin...
• The matching problem has no small symmetric SDP AI翻译
  作者：Braun, Gabor; Brown-Cohen, Jonah; Huq, Arefin; Pokutta, Sebastian; Raghavendra, Prasad; Roy, Aurko; Weitz, Benjamin; Zink, Daniel
  作者单位：University System of Georgia; Georgia Institute of Technology; University of California System; University of California Berkeley
  摘要：Yannakakis (Proceedings of the STOC, pp 223-228, 1988; J Comput Syst Sci 43(3):441-466, 1991. doi:10.1016/0022-0000(91)90024-Y) showed that the matching problem does not have a small symmetric linear program. Rothvoss (Proceedings of the STOC, pp 263-272, 2014) recently proved that any, not necessarily symmetric, linear program also has exponential size. In light of this, it is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programmin...
• A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables AI翻译
  作者：Chen, Chen; Atamturk, Alper; Oren, Shmuel S.
  作者单位：University of California System; University of California Berkeley
  摘要：We develop a spatial branch-and-cut approach for nonconvex quadratically constrained quadratic programs with bounded complex variables (CQCQP). Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP. These valid inequalities are derived from the convex hull description of a nonconvex set of positive semidefinite Hermitian matrices subject to a rank-one constraint. We propose branching rules based on an alternative to the ...
• An extended formulation of the convex recoloring problem on a tree AI翻译
  作者：Chopra, Sunil; Filipecki, Bartosz; Lee, Kangbok; Ryu, Minseok; Shim, Sangho; Van Vyve, Mathieu
  作者单位：Northwestern University; Universite Catholique Louvain; Pohang University of Science & Technology (POSTECH); University of Michigan System; University of Michigan; Robert Morris University
  摘要：We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing phylogenetic trees. The extended formulation has only a polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities introduced by Camplo et al. (Math Progr 156:303-330, 2016). We show that all valid inequalities introduced by Camplo et al. can be derived from the extended formulation. We also show that the na...
• A unified approach to error bounds for structured convex optimization problems AI翻译
  作者：Zhou, Zirui; So, Anthony Man-Cho
  作者单位：Chinese University of Hong Kong
  摘要：Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper conve...
• Probably certifiably correct k-means clustering AI翻译
  作者：Iguchi, Takayuki; Mixon, Dustin G.; Peterson, Jesse; Villar, Soledad
  作者单位：Air Force Institute of Technology (AFIT); University of Texas System; University of Texas Austin
  摘要：Recently, Bandeira (C R Math, 2015) introduced a new type of algorithm (the so-called probably certifiably correct algorithm) that combines fast solvers with the optimality certificates provided by convex relaxations. In this paper, we devise such an algorithm for the problem of k-means clustering. First, we prove that Peng and Wei's semidefinite relaxation of k-means Peng and Wei (SIAM J Optim 18(1):186-205, 2007) is tight with high probability under a distribution of planted clusters called ...
• Revisiting k-sum optimization AI翻译
  作者：Puerto, J.; Rodriguez-Chia, A. M.; Tamir, A.
  作者单位：University of Sevilla; Universidad de Cadiz; Tel Aviv University
  摘要：In this paper, we address continuous, integer and combinatorial k-sum optimization problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for solving a variety of k-sum optimization problems and at the same time, improves the complexity bounds of many ad-hoc algorithms previously reported in the literature for particular versions of this prob...
• From error bounds to the complexity of first-order descent methods for convex functions AI翻译
  作者：Bolte, Jerome; Trong Phong Nguyen; Peypouquet, Juan; Suter, Bruce W.
  作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universidad Tecnica Federico Santa Maria; Universidad Tecnica Federico Santa Maria; United States Department of Defense; United States Air Force; US Air Force Research Laboratory; Yamaguchi University
  摘要：This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-Aojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Holderian growth). A counterexample shows that the...