-
作者：Xie, Yue; Wright, Stephen J.
作者单位：University of Hong Kong; University of Hong Kong; University of Wisconsin System; University of Wisconsin Madison
摘要：This paper describes a method for solving smooth nonconvex minimization problems subject to bound constraints with good worst-case complexity guarantees and practical performance. The method contains elements of two existing methods: the classi-cal gradient projection approach for bound-constrained optimization and a recently proposed Newton-conjugate gradient algorithm for unconstrained nonconvex opti-mization. Using a new definition of approximate second-order optimality parametrized by some...
-
作者：He, Ziyu; Han, Shaoning; Gomez, Andres; Cui, Ying; Pang, Jong-Shi
作者单位：University of Southern California; University of Minnesota System; University of Minnesota Twin Cities
摘要：This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the l(0)-path where the discontinuous l(0)-function provides the exact sparsity count; the l(1)-path where the l(1)-function provides a convex surrogate of sparsity count; and the capped l(1)-path where the nonconvex nondifferentiable capped l(1)-function aims to enhance th...
-
作者：Lyu, Bochuan; Hicks, Illya V.; Huchette, Joey
作者单位：Rice University; Alphabet Inc.; Google Incorporated
摘要：We introduce techniques to build small ideal mixed-integer programming (MIP) formulations of combinatorial disjunctive constraints (CDCs) via the independent branching scheme. We present a novel pairwise IB-representable class of CDCs, CDCs admitting junction trees, and provide a combinatorial procedure to build MIP formu-lations for those constraints. Generalized special ordered sets (SOS k) can be modeled by CDCs admitting junction trees and we also obtain MIP formulations of SOS k. Furtherm...
-
作者：Caragiannis, Ioannis; Filos-Ratsikas, Aris; Frederiksen, Soren Kristoffer Stiil; Hansen, Kristoffer Arnsfelt; Tan, Zihan
作者单位：Aarhus University; University of Edinburgh; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick
摘要：We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space have to be assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agen...
-
作者：Grabisch, Michel; Sudholter, Peter
作者单位：heSam Universite; Universite Pantheon-Sorbonne; Paris School of Economics; University of Southern Denmark
摘要：A balanced transferable utility game (N, v) has a stable core if its core is externally stable, that is, if each imputation that is not in the core is dominated by some core element. Given two payoff allocations x and y, we say that xoutvotesy via some coalition S of a feasible set if x dominates y via S and x allocates at least v(T) to any feasible T that is not contained in S. It turns out that outvoting is transitive and the set M of maximal elements with respect to outvoting coincides with...
-
作者：Cominetti, Roberto; Dose, Valerio; Scarsini, Marco
作者单位：Universidad Adolfo Ibanez; Sapienza University Rome; Luiss Guido Carli University
摘要：The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing g...
-
作者：Baiou, Mourad; Correa, Jose; Laraki, Rida
作者单位：Universite Clermont Auvergne (UCA); Centre National de la Recherche Scientifique (CNRS); Polytechnic Institute of Clermont Auvergne; IMT - Institut Mines-Telecom; Mines Saint-Etienne; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
-
作者：Audet, Charles; Bouchet, Pierre-Yves; Bourdin, Loic
作者单位：Universite de Montreal
摘要：This note provides a counterexample to a theorem announced in the last part of the paper (Vicente and Custodio Math Program 133:299-325, 2012). The counterexample involves an objective function f : R -> R which satisfies all the assumptions required by the theorem but contradicts some of its conclusions. A corollary of this theorem is also affected by this counterexample. The main flaw revealed by the counterexample is the possibility that a directional direct search method (dDSM) generates a ...
-
作者：Bredies, Kristian; Carioni, Marcello; Fanzon, Silvio; Walter, Daniel
作者单位：University of Graz; University of Twente; University of Hull; Humboldt University of Berlin
摘要：We propose a fully-corrective generalized conditional gradient method (FC-GCG) for the minimization of the sum of a smooth, convex loss function and a convex one homogeneous regularizer over a Banach space. The algorithm relies on the mutual update of a finite set Ak of extremal points of the unit ball of the regularizer and of an iterate uk ? cone(Ak). Each iteration requires the solution of one linear problem to update Ak and of one finite dimensional convex minimization problem to update th...
-
作者：Das Gupta, Shuvomoy; Van Parys, Bart P. G.; Ryu, Ernest K.
作者单位：Massachusetts Institute of Technology (MIT); Seoul National University (SNU)
