-
作者：Anderson, Daniel; Le Bodic, Pierre; Morgan, Kerri
作者单位：Carnegie Mellon University; Monash University; Deakin University
摘要：A key ingredient in branch and bound (B&B) solvers for mixed-integer programming (MIP) is the selection of branching variables since poor or arbitrary selection can affect the size of the resulting search trees by orders of magnitude. A recent article by Le Bodic and Nemhauser (Math Program 166(1-2):369-405, 2017) investigated variable selection rules by developing a theoretical model of B&B trees from which they developed some new, effective scoring functions for MIP solvers. In their work, L...
-
作者：Fischer, A.; Izmailov, A. F.; Solodov, M., V
作者单位：Technische Universitat Dresden; Lomonosov Moscow State University; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：As is well known, when initialized close to a nonsingular solution of a smooth nonlinear equation, the Newton method converges to this solution superlinearly. Moreover, the common Armijo linesearch procedure used to globalize the process for convergence from arbitrary starting points, accepts the unit stepsize asymptotically and ensures fast local convergence. In the case of a singular and possibly even nonisolated solution, the situation is much more complicated. Local linear convergence (wit...
-
作者：Sikiric, Mathieu Dutour; Schuermann, Achill; Vallentin, Frank
作者单位：Rudjer Boskovic Institute; University of Rostock; University of Cologne
摘要：In this paper we provide an algorithm, similar to the simplex algorithm, which determines a rational cp-factorization of a given matrix, whenever the matrix allows such a factorization. This algorithm can be used to show that every integral completely positive 2x2 matrix has an integral cp-factorization.
-
作者：Bendotti, Pascale; Fouilhoux, Pierre; Rottner, Cecile
作者单位：Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; Electricite de France (EDF)
摘要：This paper focuses on integer linear programs where solutions are binary matrices, and the corresponding symmetry group is the set of all column permutations. Orbitopal fixing, as introduced in Kaibel et al. (Discrete Optim 8(4):595-610, 2011), is a technique designed to break symmetries in the special case of partitioning (resp. packing) formulations involving matrices with exactly (resp. at most) one 1-entry in each row. The main result of this paper is to extend orbitopal fixing to the full...
-
作者：Garber, Dan; Kaplan, Atara; Sabach, Shoham
作者单位：Technion Israel Institute of Technology; Technion Israel Institute of Technology
摘要：Motivated by robust matrix recovery problems such as Robust Principal Component Analysis, we consider a general optimization problem of minimizing a smooth and strongly convex loss function applied to the sum of two blocks of variables, where each block of variables is constrained or regularized individually. We study a Conditional Gradient-Type method which is able to leverage the special structure of the problem to obtain faster convergence rates than those attainable via standard methods, u...
-
作者：Mordukhovich, B. S.; Parra, J.; Shapiro, A.
作者单位：Wayne State University; Universidad Miguel Hernandez de Elche; University System of Georgia; Georgia Institute of Technology
-
作者：Kim, Donghwan
作者单位：Korea Advanced Institute of Science & Technology (KAIST)
摘要：This paper proposes an accelerated proximal point method for maximally monotone operators. The proof is computer-assisted via the performance estimation problem approach. The proximal point method includes various well-known convex optimization methods, such as the proximal method of multipliers and the alternating direction method of multipliers, and thus the proposed acceleration has wide applications. Numerical experiments are presented to demonstrate the accelerating behaviors.
-
作者：Carmon, Yair; Duchi, John C.; Hinder, Oliver; Sidford, Aaron
作者单位：Stanford University; Stanford University; Stanford University
摘要：We establish lower bounds on the complexity of finding similar to-stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic first-order methods, even applied to arbitrarily smooth functions, cannot achieve convergence rates in similar to better than similar to -8/5, which is within similar to-1/15 log 1 similar to of the best known rate for such methods. Moreover, for functions with Lipschitz first and second derivatives, we prove...
-
作者：Chen, Yin; Dang, Chuangyin
作者单位：City University of Hong Kong
摘要：The notion of perfect equilibrium was formulated by Selten (Int J Game Theory 4(1):25-55, 1975) as a strict refinement of Nash equilibrium. For an extensive-form game with perfect recall, every perfect equilibrium of its agent normal-form game yields a perfect equilibrium of the extensive-form game. This paper aims to develop a differentiable homotopy method for computing perfect equilibria of normal-form games. To accomplish this objective, we constitute an artificial game by introducing a co...
-
作者：Huerga, L.; Jimenez, B.; Luc, D. T.; Novo, V.
作者单位：Universidad Nacional de Educacion a Distancia (UNED); Ton Duc Thang University; Ton Duc Thang University
摘要：In this paper, we introduce some new notions of quasi efficiency and quasi proper efficiency for multiobjective optimization problems that reduce to the most important concepts of approximate and quasi efficient solutions given up to now. We establish main properties and provide characterizations for these solutions by linear and nonlinear scalarizations. With the help of quasi efficient solutions, a generalized subdifferential of a vector mapping is introduced, which generates a number of app...
