1-2期

最新文章

• Performance of first-order methods for smooth convex minimization: a novel approach AI翻译
  作者：Drori, Yoel; Teboulle, Marc
  作者单位：Tel Aviv University
  摘要：We introduce a novel approach for analyzing the worst-case performance of first-order black-box optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space. Our approach relies on the observation that by definition, the worst-case behavior of a black-box optimization method is by itself an optimization problem, which we call the performance estimation problem (PEP). We formulate and analyze the PEP for two classes of first-order algorithms. We first appl...
• Coordinated cutting plane generation via multi-objective separation AI翻译
  作者：Amaldi, Edoardo; Coniglio, Stefano; Gualandi, Stefano
  作者单位：University of Milan
  摘要：In cutting plane methods, the question of how to generate the best possible set of cuts is both central and crucial. We propose a lexicographic multi-objective cutting plane generation scheme that generates, among all the maximally violated valid inequalities of a given family, an inequality that is undominated and maximally diverse w.r.t. the cuts that were previously found. By optimizing a diversity measure, we introduce a form of coordination between successive cuts. Our focus is on valid i...
• Sobolev seminorm of quadratic functions with applications to derivative-free optimization AI翻译
  作者：Zhang, Zaikun
  作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
  摘要：This paper studies the Sobolev seminorm of quadratic functions. The research is motivated by the least-norm interpolation that is widely used in derivative-free optimization. We express the seminorm of a quadratic function explicitly in terms of the Hessian and the gradient when the underlying domain is a ball. The seminorm gives new insights into least-norm interpolation. It clarifies the analytical and geometrical meaning of the objective function in least-norm interpolation. We employ the s...
• Convergence analysis of stationary points in sample average approximation of stochastic programs with second order stochastic dominance constraints AI翻译
  作者：Sun, Hailin; Xu, Huifu
  作者单位：Harbin Institute of Technology; City St Georges, University of London
  摘要：Sample average approximation (SAA) method has recently been applied to solve stochastic programs with second order stochastic dominance (SSD) constraints. In particular, Hu et al. (Math Program 133:171-201, 2012) presented a detailed convergence analysis of -optimal values and -optimal solutions of sample average approximated stochastic programs with polyhedral SSD constraints. In this paper, we complement the existing research by presenting convergence analysis of stationary points when SAA i...
• Pricing with markups in industries with increasing marginal costs AI翻译
  作者：Correa, Jose R.; Figueroa, Nicolas; Lederman, Roger; Stier-Moses, Nicolas E.
  作者单位：Universidad de Chile; Pontificia Universidad Catolica de Chile; Columbia University; Universidad Torcuato Di Tella
  摘要：We study a game that models a market in which heterogeneous producers of perfect substitutes make pricing decisions in a first stage, followed by consumers that select a producer that sells at lowest price. As opposed to Cournot or Bertrand competition, producers select prices using a supply function that maps prices to production levels. Solutions of this type of models are normally referred to as supply function equilibria. We consider a market where producers' convex costs functions are pro...
• A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support AI翻译
  作者：Luedtke, James
  作者单位：University of Wisconsin System; University of Wisconsin Madison
  摘要：We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with finite support and random polyhedral constraints. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and most available methods are only able to find provably good solutions in certain very special cases. Our approach uses both decomposition, to enable processing subproblems corresponding to one possible outcome at a time, and...
• The triangle closure is a polyhedron AI翻译
  作者：Basu, Amitabh; Hildebrand, Robert; Koeppe, Matthias
  作者单位：University of California System; University of California Davis
  摘要：Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Ander...
• VI-constrained hemivariational inequalities: distributed algorithms and power control in ad-hoc networks AI翻译
  作者：Facchinei, Francisco; Pang, Jong-Shi; Scutari, Gesualdo; Lampariello, Lorenzo
  作者单位：Sapienza University Rome; University of Illinois System; University of Illinois Urbana-Champaign; State University of New York (SUNY) System; University at Buffalo, SUNY
  摘要：We consider centralized and distributed algorithms for the numerical solution of a hemivariational inequality (HVI) where the feasible set is given by the intersection of a closed convex set with the solution set of a lower-level monotone variational inequality (VI). The algorithms consist of a main loop wherein a sequence of one-level, strongly monotone HVIs are solved that involve the penalization of the non-VI constraint and a combination of proximal and Tikhonov regularization to handle th...
• Preemptive and non-preemptive generalized min sum set cover AI翻译
  作者：Im, Sungjin; Sviridenko, Maxim; van der Zwaan, Ruben
  作者单位：Duke University; University of Warwick; Maastricht University
  摘要：In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given ground elements and a collection of sets where each set has a positive requirement that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set is defined as the first index in the ordering such that the first elements in the ordering contain elements in . This problem was introduced by Azar et al. (2009) with interesting motivations in w...
• Computing the nearest Euclidean distance matrix with low embedding dimensions AI翻译
  作者：Qi, Hou-Duo; Yuan, Xiaoming
  作者单位：University of Southampton; Hong Kong Baptist University
  摘要：Euclidean distance embedding appears in many high-profile applications including wireless sensor network localization, where not all pairwise distances among sensors are known or accurate. The classical Multi-Dimensional Scaling (cMDS) generally works well when the partial or contaminated Euclidean Distance Matrix (EDM) is close to the true EDM, but otherwise performs poorly. A natural step preceding cMDS would be to calculate the nearest EDM to the known matrix. A crucial condition on the des...