-
作者：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...
-
作者：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...
-
作者：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...
-
作者：Slot, Lucas; Laurent, Monique
作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
摘要：We consider a hierarchy of upper approximations for the minimization of a polynomial f over a compact set K subset of R-n proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on K by the polynomial f and involves univariate sums of squares of polynomials with growing degrees 2r. Hence it is weaker, but cheaper to compute, than an earlier hierarchy by Lasserre (SIAM Journal on Optimization 21(3), 864-885, 2011),...
-
作者：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...
