-
作者：Bonnans, J. Frederic; Lavigne, Pierre; Pfeiffer, Laurent
作者单位：Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS); Inria; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Inria; Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We propose and investigate a general class of discrete time and finite state space mean field game (MFG) problems with potential structure. Our model incorporates interactions through a congestion term and a price variable. It also allows hard constraints on the distribution of the agents. We analyze the connection between the MFG problem and two optimal control problems in duality. We present two families of numerical methods and detail their implementation: (i) primal-dual proximal methods (...
-
作者：Dey, Santanu S.; Dubey, Yatharth; Molinaro, Marco
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained via disjunctions of the form x(j) <= left perpendicular (x) over bar (j) right perpendicular nu x(j) >= inverted right perpendicular (x) over bar (j) inverted left perpendicular, where (x) over bar is an optimal solution to the LP corresponding to the parent node. Even though ...
-
作者：Ye, Jane J.; Yuan, Xiaoming; Zeng, Shangzhi; Zhang, Jin
作者单位：University of Victoria; University of Hong Kong; Peng Cheng Laboratory; Southern University of Science & Technology
摘要：In this paper, we present difference of convex algorithms for solving bilevel programs in which the upper level objective functions are difference of convex functions, and the lower level programs are fully convex. This nontrivial class of bilevel programs provides a powerful modelling framework for dealing with applications arising from hyperparameter selection in machine learning. Thanks to the full convexity of the lower level program, the value function of the lower level program turns out...
-
作者：Naves, Guyslain; Shepherd, F. Bruce; Xia, Henry
作者单位：Aix-Marseille Universite; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of British Columbia
摘要：Since 1997 there has been a steady stream of advances for the maximum disjoint paths problem. Achieving tractable results has usually required focusing on relaxations such as: (i) to allow some bounded edge congestion in solutions, (ii) to only consider the unit weight (cardinality) setting, (iii) to only require fractional routability of the selected demands (the all-or-nothing flow setting). For the general form (no congestion, general weights, integral routing) of edge-disjoint paths (edp) ...
-
作者：Bennett, Kristin P.; Ferris, Michael C.; Pang, Jong-Shi; Solodov, Mikhail V.; Wright, Stephen J.
作者单位：Rensselaer Polytechnic Institute; University of Wisconsin System; University of Wisconsin Madison; University of Southern California; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
-
作者：Shen, Lingqing; Nam Ho-Nguyen; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University; University of Sydney
摘要：We propose a new framework for solving the convex bilevel optimization problem, where one optimizes a convex objective over the optimal solutions of another convex optimization problem. As a key step of our framework, we form an online convex optimization (OCO) problem in which the objective function remains fixed while the domain changes over time. We note that the structure of our OCO problem is different from the classical OCO problem that has been intensively studied in the literature. We ...
-
作者：Knop, Dusan; Koutecky, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
作者单位：Czech Technical University Prague; Charles University Prague; Technion Israel Institute of Technology; Hamburg University of Technology
摘要：N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explic...
-
作者：Rodomanov, Anton; Nesterov, Yurii
摘要：In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the...
-
作者：Cartis, Coralia; Massart, Estelle; Otemissov, Adilet
作者单位：University of Oxford; Alan Turing Institute; National Physical Laboratory - UK; Nazarbayev University
摘要：We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms for the global optimization of these special-structure problems. A reduced subproblem formulation...
-
作者：Oba, Ryoshun; Tanigawa, Shin-ichi
作者单位：University of Tokyo
摘要：A tensegrity is a structure made from cables, struts, and stiff bars. A d-dimensional tensegrity is universally rigid if it is rigid in any dimension d' with d' >= d. The celebrated super stability condition due to Connelly gives a sufficient condition for a tensegrity to be universally rigid. Gortler and Thurston showed that super stability characterizes universal rigidity when the point configuration is generic and everymember is a stiff bar. We extend this result in two directions. We first...
