Mathematical Programming

最新文章

• Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods AI翻译
  作者：Das Gupta, Shuvomoy; Van Parys, Bart P. G.; Ryu, Ernest K.
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Seoul National University (SNU)
  摘要：We present the Branch-and-Bound Performance Estimation Programming (BnB-PEP), a unified methodology for constructing optimal first-order methods for convex and nonconvex optimization. BnB-PEP poses the problem of finding the optimal optimization method as a nonconvex but practically tractable quadratically constrained quadratic optimization problem and solves it to certifiable global optimality using a customized branch-and-bound algorithm. By directly confronting the nonconvexity, BnB-PEP off...
• On the stationarity for nonlinear optimization problems with polyhedral constraints AI翻译
  作者：di Serafino, Daniela; Hager, William W. W.; Toraldo, Gerardo; Viola, Marco
  作者单位：University of Naples Federico II; State University System of Florida; University of Florida; Universita della Campania Vanvitelli; University College Dublin
  摘要：For polyhedral constrained optimization problems and a feasible point x, it is shown that the projection of the negative gradient on the tangent cone, denoted del(Omega) f(x), has an orthogonal decomposition of the form beta(x) + phi(x). At a stationary point, del(Omega) f(x) = 0 so parallel to del(Omega) f(x)parallel to reflects the distance to a stationary point. Away from a stationary point, parallel to beta(x)parallel to and parallel to phi(x)parallel to measure different aspects of optima...
• No-regret algorithms in on-line learning, games and convex optimization AI翻译
  作者：Sorin, Sylvain
  作者单位：Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Cite
  摘要：The purpose of this article is to underline the links between some no-regret algorithms used in on-line learning, games and convex optimization and to compare the continuous and discrete time versions.
• Absorption paths and equilibria in quitting games AI翻译
  作者：Ashkenazi-Golan, Galit; Krasikov, Ilia; Rainer, Catherine; Solan, Eilon
  作者单位：University of London; London School Economics & Political Science; HSE University (National Research University Higher School of Economics); Centre National de la Recherche Scientifique (CNRS); Universite de Bretagne Occidentale
  摘要：We study quitting games and introduce an alternative notion of strategy profiles- absorption paths. An absorption path is parametrized by the total probability of absorption in past play rather than by time, and it accommodates both discrete-time aspects and continuous-time aspects. We then define the concept of sequentially 0-pelfect absorption paths, which are shown to be limits of epsilon-equilibrium strategy profiles as epsilon goes to 0. We establish that all quitting games that do not ha...
• Adjustability in robust linear optimization AI翻译
  作者：Wei, Ningji; Zhang, Peter
  作者单位：Texas Tech University System; Texas Tech University; Carnegie Mellon University
  摘要：We investigate the concept of adjustability-the difference in objective values between two types of dynamic robust optimization formulations: one where (static) decisions are made before uncertainty realization, and one where uncertainty is resolved before (adjustable) decisions. This difference reflects the value of information and decision timing in optimization under uncertainty, and is related to several other concepts such as the optimality of decision rules in robust optimization. We dev...
• Hardness and approximation of submodular minimum linear ordering problems AI翻译
  作者：Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C.
  作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Carnegie Mellon University
  摘要：The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost f (center dot) due to an ordering sigma of the items (say [n]), i.e., min(sigma) Sigma(i is an element of n]) f (E-i,E- sigma), where E-i,E- sigma is the set of items mapped by s to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whe...
• Cutoff stability under distributional constraints with an application to summer internship matching AI翻译
  作者：Aziz, Haris; Baychkov, Anton; Biro, Peter
  作者单位：University of New South Wales Sydney; University of Sydney; HUN-REN; HUN-REN Centre for Economic & Regional Studies; Corvinus University Budapest
  摘要：We introduce a new two-sided stable matching problem that describes the summer internship matching practice of an Australian university. The model is a case between two models of Kamada and Kojima on matchings with distributional constraints. We study three solution concepts, the strong and weak stability concepts proposed by Kamada and Kojima, and a new one in between the two, called cutoff stability. Kamada and Kojima showed that a strongly stable matching may not exist in their most restric...
• Consistent queueing rules AI翻译
  作者：Thomson, William; Velez, Rodrigo A.
  作者单位：University of Rochester
  摘要：In a queueing problem , a group of agents are waiting for a service. Each agent incurs a cost of waiting that is proportional to the time they wait. Monetary transfers can take place. We study the subsolutions of the no-envy solution that are anonymous, consistent, conversely consistent, and continuous. We show that there are infinitely many proper consistent subsolutions from the no-envy solution and characterize a class of these solutions on the basis of basic requirements of continuity, ano...
• Nonsmooth convex-concave saddle point problems with cardinality penalties AI翻译
  作者：Bian, Wei; Chen, Xiaojun
  作者单位：Harbin Institute of Technology; Hong Kong Polytechnic University
  摘要：In this paper, we focus on a class of convexly constrained nonsmooth convex-concave saddle point problems with cardinality penalties. Although such nonsmooth nonconvex-nonconcave and discontinuous min-max problems may not have a saddle point, we show that they have a local saddle point and a global minimax point, and some local saddle points have the lower bound properties. We define a class of strong local saddle points based on the lower bound properties for stability of variable selection. ...
• Intersecting and dense restrictions of clutters in polynomial time AI翻译
  作者：Drees, Martin
  作者单位：University of Bonn
  摘要：A clutter is a family of sets, called members, such that no member contains another. It is called intersecting if every two members intersect, but not all members have a common element. Dense clutters additionally do not have a fractional packing of value 2. We are looking at certain substructures of clutters, namely minors and restrictions. For a family of clutters we introduce a general sufficient condition such that for every clutter we can decide whether the clutter has a restriction in th...