2020

最新文章

• Stationarity conditions and constraint qualifications for mathematical programs with switching constraints With applications to either-or-constrained programming AI翻译
  作者：Mehlitz, Patrick
  作者单位：Brandenburg University of Technology Cottbus
  摘要：In optimal control, switching structures demanding at most one control to be active at any time instance appear frequently. Discretizing such problems, a so-called mathematical program with switching constraints is obtained. Although these problems are related to other types of disjunctive programs like optimization problems with complementarity or vanishing constraints, their inherent structure makes a separate consideration necessary. Since standard constraint qualifications are likely to fa...
• Using regularization and second order information in outer approximation for convex MINLP AI翻译
  作者：Kronqvist, Jan; Bernal, David E.; Grossmann, Ignacio E.
  作者单位：Abo Akademi University; Carnegie Mellon University
  摘要：In this paper, we present two new methods for solving convex mixed-integer nonlinear programming problems based on the outer approximation method. The first method is inspired by the level method and uses a regularization technique to reduce the step size when choosing new integer combinations. The second method combines ideas from both the level method and the sequential quadratic programming technique and uses a second order approximation of the Lagrangean when choosing the new integer combi...
• Faster algorithms for extensive-form game solving via improved smoothing functions AI翻译
  作者：Kroer, Christian; Waugh, Kevin; Kilinc-Karzan, Fatma; Sandholm, Tuomas
  作者单位：Carnegie Mellon University; University of Alberta; Carnegie Mellon University
  摘要：Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergence rates of these methods depend heavily on the properties of the distance-generating function that they are based on. We investigate both the theoretical and practical performance improvement of first-order methods (FOMs) for solving extensive-form games through better design of the dilated entropy function-a class ...
• Online covering with lq-norm objectives and applications to network design AI翻译
  作者：Shen, Xiangkun; Nagarajan, Viswanath
  作者单位：University of Michigan System; University of Michigan
  摘要：We consider fractional online covering problems withlq-norm objectives as well as its dual packing problems. The problem of interest is of the formmin{f(x):Ax >= 1,x >= 0}wheref(x)= n-ary sumation ece||x(Se)||qeis the weighted sum oflq-norms andAis a non-negative matrix. The rows ofA(i.e. covering constraints) arrive online over time. We provide an onlineO(logd+log rho)-competitive algorithm where rho=amaxaminanddis the maximum of the row sparsity ofAandmax|Se|This is based on the online prima...
• Convex approximations for two-stage mixed-integer mean-risk recourse models with conditional value-at-risk AI翻译
  作者：van Beesten, E. Ruben; Romeijnders, Ward
  作者单位：University of Groningen
  摘要：In traditional two-stage mixed-integer recourse models, the expected value of the total costs is minimized. In order to address risk-averse attitudes of decision makers, we consider a weighted mean-risk objective instead. Conditional value-at-risk is used as our risk measure. Integrality conditions on decision variables make the model non-convex and hence, hard to solve. To tackle this problem, we derive convex approximation models and corresponding error bounds, that depend on the total varia...
• Improving the integrality gap for multiway cut AI翻译
  作者：Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Madan, Vivek
  作者单位：Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology
  摘要：In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k >= 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrak (Proceedings of the forty-sixth annual...
• On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope AI翻译
  作者：Li, Xudong; Sun, Defeng; Toh, Kim-Chuan
  作者单位：Fudan University; Hong Kong Polytechnic University; National University of Singapore; National University of Singapore
  摘要：We derive an explicit formula, as well as an efficient procedure, for constructing a generalized Jacobian for the projector of a given square matrix onto the Birkhoff polytope, i.e., the set of doubly stochastic matrices. To guarantee the high efficiency of our procedure, a semismooth Newton method for solving the dual of the projection problem is proposed and efficiently implemented. Extensive numerical experiments are presented to demonstrate the merits and effectiveness of our method by com...
• An efficient characterization of submodular spanning tree games AI翻译
  作者：Koh, Zhuan Khye; Sanita, Laura
  作者单位：University of London; London School Economics & Political Science; University of Waterloo; Eindhoven University of Technology
  摘要：Cooperative games form an important class of problems in game theory, where a key goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is submodularity (or convexity). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing...
• New analysis of linear convergence of gradient-type methods via unifying error bound conditions AI翻译
  作者：Zhang, Hui
  作者单位：National University of Defense Technology - China
  摘要：This paper reveals that a common and central role, played in many error bound (EB) conditions and a variety of gradient-type methods, is a residual measure operator. On one hand, by linking this operator with other optimality measures, we define a group of abstract EB conditions, and then analyze the interplay between them; on the other hand, by using this operator as an ascent direction, we propose an abstract gradient-type method, and then derive EB conditions that are necessary and sufficie...
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions AI翻译
  作者：Della Croce, Federico; Scatamacchia, Rosario
  作者单位：Polytechnic University of Turin; Consiglio Nazionale delle Ricerche (CNR); Istituto di Elettronica e di Ingegneria dell'Informazione e delle Telecomunicazioni (IEIIT-CNR)
  摘要：We consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the p...