Mathematical Programming

最新文章

• Exact approaches for convex adjustable robust optimization AI翻译
  作者：Lefebvre, Henri; Malaguti, Enrico; Monaci, Michele
  作者单位：Universitat Trier; University of Bologna
  摘要：Adjustable Robust Optimization (ARO) is a paradigm for facing uncertainty in a decision problem, in case some recourse actions are allowed after the actual value of all input parameters is revealed. While several approaches have been introduced for the linear case, little is known regarding exact methods for the convex case. In this work, we introduce a new general framework for attacking a wide class of ARO problems involving convex functions in the recourse problem. We first recall a semi-in...
• Low-rank mirror-prox methods for nonsmooth and low-rank matrix optimization problems AI翻译
  作者：Garber, Dan; Kaplan, Atara
  作者单位：Technion Israel Institute of Technology
  摘要：Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in developing efficient methods for smooth problems that avoid computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced.In this paper we consider a standard convex relaxation: minimizing a convex nonsmooth objective function over the spectrahedron (set of real positive-semidefinite matrices with unit trac...
• The two-stripe symmetric circulant TSP is in P AI翻译
  作者：Gutekunst, Samuel C.; Jin, Billy; Williamson, David P.
  作者单位：Bucknell University; Cornell University; Purdue University System; Purdue University
  摘要：The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of the input, remarkably little is known about the symmetric circulant TSP, and the complexity of the problem has been an often-cited open question. Considerable effort has been made to understand the case in which only edges of two lengths are allowed to have finite cost: the two-stripe symmetric circulant TSP. In this ...
• Convex envelopes of bounded monomials on two-variable cones AI翻译
  作者：Belotti, Pietro
  作者单位：Polytechnic University of Milan
  摘要：We consider an n-variate monomial function that is restricted both in value by lower and upper bounds and in domain by two homogeneous linear inequalities. Monomial functions are building blocks for the class of Mixed Integer Nonlinear Optimization problems, which has many practical applications. We show that the upper envelope of the function in the given domain, for n >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepa...
• Projection onto hyperbolicity cones and beyond: a dual Frank-Wolfe approach AI翻译
  作者：Nagano, Takayuki; Lourenco, Bruno F.; Takeda, Akiko
  作者单位：University of Tokyo; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; RIKEN
  摘要：We discuss the problem of projecting a point onto an arbitrary hyperbolicity cone from both theoretical and numerical perspectives. While hyperbolicity cones are furnished with a generalization of the notion of eigenvalues, obtaining closed form expressions for the projection operator as in the case of semidefinite matrices is an elusive endeavour. To address that we propose a Frank-Wolfe method to handle this task and, more generally, strongly convex optimization over closed convex cones. One...
• Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs AI翻译
  作者：Brown, Adam; Laddha, Aditi; Pittu, Madhusudhan; Singh, Mohit
  作者单位：University System of Georgia; Georgia Institute of Technology; Yale University; Carnegie Mellon University
  摘要：In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {G}$$\end{document}, and n agents, A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \use...
• Accelerated first-order optimization under nonlinear constraints AI翻译
  作者：Muehlebach, Michael; Jordan, Michael I.
  作者单位：Max Planck Society; University of California System; University of California Berkeley
  摘要：We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each iteration. We prove convergence to stationary points even in a nonconvex setting and we derive accelerated rates for the convex setting both in continuous time, as well as in dis...
• Preference ambiguity and robustness in multistage decision making AI翻译
  作者：Liu, Jia; Chen, Zhiping; Xu, Huifu
  作者单位：Xi'an Jiaotong University; Chinese University of Hong Kong
  摘要：In this paper, we consider a multistage expected utility maximization problem where the decision maker's utility function at each stage depends on historical path and the information on the true utility function is incomplete. To mitigate the adverse impact arising from ambiguity regarding the true utility, we propose a maximin robust model where the optimal policy is based on the worst-case sequence of utility functions from an ambiguity set constructed with partially available information ab...
• Minimax-optimal Halpern iterations for Lipschitz maps AI翻译
  作者：Bravo, Mario; Cominetti, Roberto; Lee, Jongmin
  作者单位：Universidad de Santiago de Chile; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile; Seoul National University (SNU)
  摘要：This paper investigates the minimax-optimality of Halpern fixed-point iterations for Lipschitz maps in general normed spaces. Starting from an a priori bound on the orbit of iterates, we derive non-asymptotic estimates for the fixed-point residuals. These bounds are tight, meaning that they are attained by a suitable Lipschitz map and an associated Halpern sequence. By minimizing these tight bounds we identify the minimax-optimal Halpern scheme. For contractions, the optimal iteration exhibits...
• On integer programs with irrational data AI翻译
  作者：Hosseinian, Seyedmohammadhossein; Schaefer, Andrew J.
  作者单位：North Carolina State University; Rice University
  摘要：An integer program (IP) with a finite number of feasible solutions may have an unbounded continuous relaxation if it contains irrational parameters, due to implicit constraints induced by those irrational numbers. For IPs with polynomial constraints, we show that these implicit constraints can be derived explicitly when the irrational parameters belong to an extension field of the rational numbers by roots of integers, leading to a rational reformulation. We also present a weaker result for IP...