-
作者：Dempe, Stephan; Nguyen Dinh; Dutta, Joydeep; Pandit, Tanushree
作者单位：Technical University Freiberg; Vietnam National University Ho Chi Minh City (VNUHCM) System; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Kanpur; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Kanpur
摘要：In this paper we discuss the simple bilevel programming problem (SBP) and its extension, the simple mathematical programming problem under equilibrium constraints (SMPEC). Here we first define both these problems and study their interrelations. Next we study the various types of necessary and sufficient optimality conditions for the (SMPEC) problems, which occur under various reformulations. The optimality conditions for (SBP) are special cases of the results obtained for (SMPEC) when the lowe...
-
作者：Gutman, David H.; Pena, Javier F.
作者单位：Texas Tech University System; Texas Tech University; Carnegie Mellon University
摘要：The condition number of a differentiable convex function, namely the ratio of its smoothness to strong convexity constants, is closely tied to fundamental properties of the function. In particular, the condition number of a quadratic convex function is the square of the aspect ratio of a canonical ellipsoid associated to the function. Furthermore, the condition number of a function bounds the linear rate of convergence of the gradient descent algorithm for unconstrained convex minimization. We...
-
作者：Gomez, Andres
作者单位：University of Southern California
摘要：We study the convex hull of the mixed-integer set given by a conic quadratic inequality and indicator variables. Conic quadratic terms are often used to encode uncertainties, while the indicator variables are used to model fixed costs or enforce sparsity in the solutions. We provide the convex hull description of the set under consideration when the continuous variables are unbounded. We propose valid nonlinear inequalities for the bounded case, and show that they describe the convex hull for ...
-
作者：Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier
作者单位：Columbia University; University of Rome Tor Vergata; Kedge Business School
摘要：The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of providing a decent linear description for this polytope (Grotschel et al. in Geometric algorithms and combinatorial optimization, Springe...
-
作者：Chakrabarty, Deeparnab; Khanna, Sanjeev
作者单位：Dartmouth College; University of Pennsylvania
摘要：Given a non-negative n xm real matrix A, the matrix scaling problem is to determine if it is possible to scale the rows and columns so that each row and each column sums to a specified positive target values. The Sinkhorn-Knopp algorithm is a simple and classic procedure which alternately scales all rows and all columns to meet these targets. The focus of this paper is the worst-case theoretical analysis of this algorithm. We present an elementary convergence analysis for this algorithm that i...
-
作者：Agarwal, Naman; Boumal, Nicolas; Bullins, Brian; Cartis, Coralia
作者单位：Alphabet Inc.; Google Incorporated; Princeton University; Toyota Technological Institute - Chicago; University of Oxford
摘要：Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the trust-region method, its iterations can be thought of as approximate, safe-guarded Newton steps. For cost functions with Lipschitz continuous Hessian, ARC has optimal iteration complexity, in the sense that it produces an iterate with gradient smaller than epsilon in O(1/epsilon 1.5) iterations. For the same price, it can also guarantee a Hessian with smallest eigenvalue larger tha...
-
作者：Berczi, Kristof; Schwarcz, Tamas
作者单位：Eotvos Lorand University; Eotvos Lorand University
摘要：One of the most intriguing unsolved questions of matroid optimization is the characterization of the existence of k disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list of conjectures that can be formulated as special cases, such as Woodall's conjecture on packing disjoint dijoins in a directed graph, or Rota's beautiful conjecture on rearrangements of bases. In the present paper we prove that the problem is difficult under the rank oracle...
-
作者：Bolte, Jerome; Pauwels, Edouard
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS)
摘要：Modern problems in AI or in numerical analysis require nonsmooth approaches with a flexible calculus. We introduce generalized derivatives called conservative fields for which we develop a calculus and provide representation formulas. Functions having a conservative field are called path differentiable: convex, concave, Clarke regular and any semialgebraic Lipschitz continuous functions are path differentiable. Using Whitney stratification techniques for semialgebraic and definable sets, our m...
-
作者：Schmidt, Daniel; Zey, Bernd; Margot, Francois
作者单位：University of Bonn; Dortmund University of Technology
摘要：A correction to this paper has been published: https://doi.org/10.1007/s10107-021-01648-9
-
作者：Seguin-Charbonneau, Loic; Shepherd, F. Bruce
作者单位：University of British Columbia
摘要：We study the maximum edge-disjoint path problem (medp) in planar graphs G = (V, E) with edge capacities u(e). We are given a set of terminal pairs si ti, i = 1, 2..., k and wish to find a maximum routable subset of demands. That is, a subset of demands that can be connected by a family of paths that use each edge at most u(e) times. It is well-known that there is an integrality gap of Omega(root n) for the natural LP relaxation, even in planar graphs (Garg-Vazirani-Yannakakis). We show that if...
