-
作者：Kunisky, Dmitriy; Bandeira, Afonso S.
作者单位：New York University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We show that, if W is an N xN matrix drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares relaxation cannot certify an upper bound on the objective N-1 center dot x(perpendicular to) Wx under the constraints x(i)(2) - 1 = 0 (i.e. x is an element of {+/- 1}(N)) that is asymptotically smaller than lambda(max)(W) approximate to 2. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as N...
-
作者：Borges, Pedro; Sagastizabal, Claudia; Solodov, Mikhail
作者单位：Universidade Estadual de Campinas
摘要：We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in question, while resulting from parameterized convex problems, need not be conve...
-
作者：Do Sang Kim; Mordukhovich, Boris S.; Tien-Son Pham; Nguyen Van Tuyen
作者单位：Pukyong National University; Wayne State University; Peoples Friendship University of Russia; Hanoi Pedagogical University 2 (HPU2); University of Electronic Science & Technology of China
摘要：The paper is devoted to the existence of global optimal solutions for a general class of nonsmooth problems of constrained vector optimization without boundedness assumptions on constraint set. The main attention is paid to the two major notions of optimality in vector problems: Pareto efficiency and proper efficiency in the sense of Geoffrion. Employing adequate tools of variational analysis and generalized differentiation, we first establish relationships between the notions of properness,M-...
-
作者：Bauschke, Heinz H.; Moursi, Walaa M.; Wang, Xianfu
作者单位：University of British Columbia; University of Waterloo
摘要：The correspondence between the monotonicity of a (possibly) set-valued operator and the firm nonexpansiveness of its resolvent is a key ingredient in the convergence analysis of many optimization algorithms. Firmly nonexpansive operators form a proper subclass of the more general-but still pleasant from an algorithmic perspective-class of averaged operators. In this paper, we introduce the new notion of conically nonexpansive operators which generalize nonexpansive mappings. We characterize av...
-
作者：Kleinert, Thomas; Grimm, Veronika; Schmidt, Martin
作者单位：University of Erlangen Nuremberg; University of Erlangen Nuremberg; University of Erlangen Nuremberg; Universitat Trier
摘要：Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continu...
-
作者：Bestehorn, Felix; Hansknecht, Christoph; Kirches, Christian; Manns, Paul
作者单位：Braunschweig University of Technology
摘要：We investigate an extension of Mixed-Integer Optimal Control Problems by adding switching costs, which enables the penalization of chattering and extends current modeling capabilities. The decomposition approach, consisting of solving a partial outer convexification to obtain a relaxed solution and using rounding schemes to obtain a discrete-valued control can still be applied, but the rounding turns out to be difficult in the presence of switching costs or switching constraints as the underly...
-
作者：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...
-
作者：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...
