1-2期

最新文章

• On Lipschitz optimization based on gray-box piecewise linearization AI翻译
  作者：Griewank, Andreas; Walther, Andrea; Fiege, Sabrina; Bosse, Torsten
  作者单位：Universidad Yachay Tech; University of Paderborn; United States Department of Energy (DOE); Argonne National Laboratory
  摘要：We address the problem of minimizing objectives from the class of piecewise differentiable functions whose nonsmoothness can be encapsulated in the absolute value function. They possess local piecewise linear approximations with a discrepancy that can be bounded by a quadratic proximal term. This overestimating local model is continuous but generally nonconvex. It can be generated in its abs-normal form by a minor extension of standard algorithmic differentiation tools. Here we demonstrate how...
• The convex recoloring problem: polyhedra, facets and computational experiments AI翻译
  作者：Campelo, Manoel; Freire, Alexandre S.; Lima, Karla R.; Moura, Phablo F. S.; Wakabayashi, Yoshiko
  作者单位：Universidade Federal do Ceara; Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidade de Sao Paulo
  摘要：A coloring of the vertices of a graph is convex if the vertices receiving a common color induce a connected subgraph of . We address the convex recoloring problem: given a graph and a coloring of its vertices, recolor a minimum number of vertices of , so that the resulting coloring is convex. This problem is known to be -hard even when is a path. We show an integer programming formulation for arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defi...
• Error bounds for mixed integer linear optimization problems AI翻译
  作者：Stein, Oliver
  作者单位：Helmholtz Association; Karlsruhe Institute of Technology
  摘要：We introduce computable a priori and a posteriori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the LP relaxation of a mixed integer linear optimization problem. Treating the mesh size of integer vectors as a parameter allows us to study the effect of different granularities in the discrete variables on the error bounds. Our analysis mainly bases on a global error bound for mixed integer linear problems constructed via a so-called grid ...
• On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts AI翻译
  作者：Balas, Egon; Kis, Tamas
  作者单位：Carnegie Mellon University; HUN-REN; HUN-REN Institute for Computer Science & Control
  摘要：We examine the connections between the classes of cuts in the title. We show that lift-and-project (L&P) cuts from a given disjunction are equivalent to generalized intersection cuts from the family of polyhedra obtained by taking positive combinations of the complements of the inequalities of each term of the disjunction. While L&P cuts from split disjunctions are known to be equivalent to standard intersection cuts (SICs) from the strip obtained by complementing the terms of the split, we sh...
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts AI翻译
  作者：Fawzi, Hamza; Saunderson, James; Parrilo, Pablo A.
  作者单位：Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
  摘要：Let G be a finite abelian group. This paper is concerned with nonnegative functions on G that are sparse with respect to the Fourier basis. We establish combinatorial conditions on subsets and of Fourier basis elements under which nonnegative functions with Fourier support are sums of squares of functions with Fourier support . Our combinatorial condition involves constructing a chordal cover of a graph related to G and (the Cayley graph ) with maximal cliques related to . Our result relies on...
• Gradient sliding for composite optimization AI翻译
  作者：Lan, Guanghui
  作者单位：State University System of Florida; University of Florida
  摘要：We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the computation of the gradient for the smooth component from time to time. As a consequence, these algorithms require only gradient evaluations for the smooth component in order to...
• A note on Fejer-monotone sequences in product spaces and its applications to the dual convergence of augmented Lagrangian methods AI翻译
  作者：Alves, M. Marques; Svaiter, B. F.
  作者单位：Universidade Federal de Santa Catarina (UFSC); Instituto Nacional de Matematica Pura e Aplicada (IMPA)
  摘要：In a recent Math. Program. paper, Eckstein and Silva proposed a new error criterion for the approximate solutions of augmented Lagrangian subproblems. Based on a saddle-point formulation of the primal and dual problems, they proved that dual sequences generated by augmented Lagrangians under this error criterion are bounded and that their limit points are dual solutions. In this note, we prove a new result about the convergence of Fej,r-monotone sequences in product spaces (which seems to be i...
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree AI翻译
  作者：Feldmann, Andreas Emil; Konemann, Jochen; Olver, Neil; Sanita, Laura
  作者单位：University of Waterloo; Hungarian Academy of Sciences; HUN-REN; HUN-REN Institute for Computer Science & Control; Charles University Prague; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
  摘要：The bottleneck of the currently best -approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are strongly NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be sol...
• Sparse solutions of linear complementarity problems AI翻译
  作者：Chen, Xiaojun; Xiang, Shuhuang
  作者单位：Hong Kong Polytechnic University; Central South University
  摘要：This paper considers the characterization and computation of sparse solutions and least-p-norm solutions of the linear complementarity problem . We show that the number of non-zero entries of any least-p-norm solution of the is less than or equal to the rank of M for any arbitrary matrix M and any number , and there is such that all least-p-norm solutions for are sparse solutions. Moreover, we provide conditions on M such that a sparse solution can be found by solving convex minimization. Appl...
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems AI翻译
  作者：Li, Guoyin; Pong, Ting Kei
  作者单位：University of New South Wales Sydney; Hong Kong Polytechnic University
  摘要：We adapt the Douglas-Rachford (DR) splitting method to solve nonconvex feasibility problems by studying this method for a class of nonconvex optimization problem. While the convergence properties of the method for convex problems have been well studied, far less is known in the nonconvex setting. In this paper, for the direct adaptation of the method to minimize the sum of a proper closed function g and a smooth function f with a Lipschitz continuous gradient, we show that if the step-size par...