-
作者：Cartis, Coralia; Massart, Estelle; Otemissov, Adilet
作者单位：Alan Turing Institute; University of Oxford; National Physical Laboratory - UK; Nazarbayev University
摘要：We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same...
-
作者：Ye, Haishan; Lin, Dachao; Chang, Xiangyu; Zhang, Zhihua
作者单位：Xi'an Jiaotong University; Peking University; Peking University
摘要：We study the convergence rate of the famous Symmetric Rank-1 (SR1) algorithm, which has wide applications in different scenarios. Although it has been extensively investigated, SR1 still lacks a non-asymptotic superlinear rate compared with other quasi-Newton methods such as DFP and BFGS. In this paper, we address the aforementioned issue to obtain the first explicit non-asymptotic rates of superlinear convergence for the vanilla SR1 methods with a correction strategy that is used to achieve n...
-
作者：Carr, Robert; Ravi, R.; Simonetti, Neil
作者单位：University of New Mexico; Carnegie Mellon University
摘要：In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost c(ij) of traveling from city i to city j, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP requiring only two classe...
-
作者：Atamturk, Alper; Gomez, Andres
作者单位：University of California System; University of California Berkeley; University of Southern California
摘要：We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in general, difficult, the specific set function for the rank-one quadratic can be minimized in linear time. We show that the convex hull of the epigraph of the quadratic can be obtained from inequalities for the underlying supermodular set function by lifting them into nonlinear i...
-
作者：Hu, Hao; Sotirov, Renata; Wolkowicz, Henry
作者单位：Clemson University; Tilburg University; University of Waterloo
摘要：We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN, relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN rel...
-
作者：Garg, Paritosh; Jordan, Linus; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result th...
-
作者：Tien-Son Pham
作者单位：Dalat University
摘要：Given a polynomial function f : R-n -> R and an unbounded closed semi-algebraic set S subset of R-n, we show that the conditions listed below are characterized exactly in terms of the so-called tangency variety of the restriction of f on S: f is bounded from below on S; f attains its infimum on S; The sublevel sets (x is an element of S vertical bar f (x) <= lambda} for lambda is an element of R are compact; f is coercive on S. Besides, we also provide some stability criteria for boundedness a...
-
作者：Babecki, Catherine; Thomas, Rekha R.
作者单位：University of Washington; University of Washington Seattle
摘要：A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use Gale duality to show that positively weighted graphical designs in regular graphs are in bijection with the faces of a generalized eigenpolytope of the graph. This connection can be used to organize, compute and optimize designs. We illustrate the power of this tool on three families of Cayley graphs - cocktail party graphs, cyc...
-
作者：Okuno, Takayuki; Fukushima, Masao
作者单位：Seikei University; RIKEN
摘要：In this paper, we propose a primal-dual path following method for nonlinear semi-infinite semi-definite programs with infinitely many convex inequality constraints, called SISDP for short. A straightforward approach to the SISDP is to use classical methods for semi-infinite programs such as discretization and exchange methods and solve a sequence of (nonlinear) semi-definite programs (SDPs). However, it is often too demanding to find exact solutions of SDPs. In contrast, our approach does not ...
-
作者：Buchbinder, Niv; Coester, Christian; Naor, Joseph
作者单位：Tel Aviv University; University of Sheffield; Technion Israel Institute of Technology
摘要：We consider the online k-taxi problem, a generalization of the k-server problem, in which k servers are located in a metric space. A sequence of requests is revealed one by one, where each request is a pair of two points, representing the start and destination of a travel request by a passenger. The goal is to serve all requests while minimizing the distance traveled without carrying a passenger. We show that the classic Double Coverage algorithm has competitive ratio 2(k) - 1 on HSTs, matchin...
