-
作者：Escobar, Daniel Hernandez; Ruckmann, Jan-J
作者单位：University of Bergen
摘要：In this paper we consider the class of mathematical programs with complementarity constraints (MPCC). Under an appropriate constraint qualification of Mangasarian-Fromovitz type we present a topological and an equivalent algebraic characterization of a strongly stable C-stationary point for MPCC. Strong stability refers to the local uniqueness, existence and continuous dependence of a solution for each sufficiently small perturbed problem where perturbations up to second order are allowed. Thi...
-
作者：Kleer, Pieter; Schafer, Guido
作者单位：Max Planck Society; Vrije Universiteit Amsterdam
摘要：We study the computation and efficiency of pure Nash equilibria in combinatorial congestion games, where the strategies of each player i are given by the binary vectors of a polytope P-i. Our main goal is to understand which structural properties of such polytopal congestion games enable us to derive an efficient equilibrium selection procedure to compute pure Nash equilibria with attractive social cost approximation guarantees. To this aim, we identify two general properties of the underlying...
-
作者：Fiorini, Samuel; Huynh, Tony; Weltge, Stefan
作者单位：Universite Libre de Bruxelles; Monash University; Technical University of Munich
摘要：In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the setSof feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific setsSthat arise in combin...
-
作者：Xie, Weijun
作者单位：Virginia Polytechnic Institute & State University
摘要：This paper studies a distributionally robust chance constrained program (DRCCP) with Wasserstein ambiguity set, where the uncertain constraints should be satisfied with a probability at least a given threshold for all the probability distributions of the uncertain parameters within a chosen Wasserstein distance from an empirical distribution. In this work, we investigate equivalent reformulations and approximations of such problems. We first show that a DRCCP can be reformulated as a condition...
-
作者：Flores-Bazan, F.; Garcia, Y.; Hadjisavvas, N.
作者单位：Universidad de Concepcion; Universidad del Pacifico Peru; University of Aegean
摘要：It is well-known that the sum of two quasiconvex functions is not quasiconvex in general, and the same occurs with the minimum. Although apparently these two statements (for the sum or minimum) have nothing in common, they are related, as we show in this paper. To develop our study, the notion of quasiconvex family is introduced, and we establish various characterizations of such a concept: one of them being the quasiconvexity of the pointwise infimum of arbitrary translations of quasiconvex f...
-
作者：Xu, Yangyang
作者单位：Rensselaer Polytechnic Institute
摘要：Augmented Lagrangian method (ALM) has been popularly used for solving constrained optimization problems. Practically, subproblems for updating primal variables in the framework of ALM usually can only be solved inexactly. The convergence and local convergence speed of ALM have been extensively studied. However, the global convergence rate of the inexact ALMis still open for problems with nonlinear inequality constraints. In this paper, we work on general convex programs with both equality and ...
-
作者：Dutta, Joydeep; Enrique Martinez-Legaz, Juan
作者单位：Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Kanpur; Autonomous University of Barcelona
摘要：The main goal in this paper is to devise an approach to explicitly calculate the constant in the Hoffman's error bound for (notnecessarily convex) inequality systems defining convex sets. We give a constructive proof of the Hoffman's error bound and show that we can use our method to calculate the constant at least in simple cases.
-
作者：Bah, Bubacarr; Kurtz, Jannis; Schaudt, Oliver
作者单位：Stellenbosch University; RWTH Aachen University
摘要：In this article we study the problem of signal recovery for group models. More precisely for a given set of groups, each containing a small subset of indices, and for given linear sketches of the true signal vector which is known to be group-sparse in the sense that its support is contained in the union of a small number of these groups, we study algorithms which successfully recover the true signal just by the knowledge of its linear sketches. We derive model projection complexity results and...
-
作者：Chubanov, Sergei
摘要：In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0-1 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method.
-
作者：Martinez-Legaz, Juan Enrique; Pintea, Cornel
作者单位：Autonomous University of Barcelona; Babes Bolyai University from Cluj
摘要：We characterize the closed convex subsets of R-n which have open or closed Gauss ranges. Some special attention is paid to epigraphs of lower semicontinuous convex functions.
