Mathematical Programming

最新文章

• Convergence rates with inexact non-expansive operators AI翻译
  作者：Liang, Jingwei; Fadili, Jalal; Peyre, Gabriel
  作者单位：Universite de Caen Normandie; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine; Universite PSL; Universite Paris-Dauphine
  摘要：In this paper, we present a convergence rate analysis for the inexact Krasnosel'skiAaEuroMann iteration built from non-expansive operators. The presented results include two main parts: we first establish the global pointwise and ergodic iteration-complexity bounds; then, under a metric sub-regularity assumption, we establish a local linear convergence for the distance of the iterates to the set of fixed points. The obtained results can be applied to analyze the convergence rate of various mon...
• 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...
• Chance-constrained problems and rare events: an importance sampling approach AI翻译
  作者：Barrera, Javiera; Homem-de-Mello, Tito; Moreno, Eduardo; Pagnoncelli, Bernardo K.; Canessa, Gianpiero
  作者单位：Universidad Adolfo Ibanez; Universidad Adolfo Ibanez; Universidad Adolfo Ibanez
  摘要：We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that varian...
• 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...
• An approximation scheme for a class of risk-averse stochastic equilibrium problems AI翻译
  作者：Luna, Juan Pablo; Sagastizabal, Claudia; Solodov, Mikhail
  作者单位：Universidade Federal do Rio de Janeiro; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
  摘要：We consider two models for stochastic equilibrium: one based on the variational equilibrium of a generalized Nash game, and the other on the mixed complementarity formulation. Each agent in the market solves a single-stage risk-averse optimization problem with both here-and-now (investment) variables and (production) wait-and-see variables. A shared constraint couples almost surely the wait-and-see decisions of all the agents. An important characteristic of our approach is that the agents hedg...
• 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...