-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University
摘要：We consider the multilinear polytope defined as the convex hull of the set of binary points z, satisfying a collection of equations of the form z(e) = Pi (upsilon is an element of e) z(upsilon) for all e is an element of E. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of ss-acyclic hypergraphs, hence characterizing the acy...
-
作者：Zhang, Haixiang; Yalcin, Baturalp; Lavaei, Javad; Sojoudi, Somayeh
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：In this work, we develop a new complexity metric for an important class of low-rank matrix optimization problems in both symmetric and asymmetric cases, where the metric aims to quantify the complexity of the nonconvex optimization landscape of each problem and the success of local search methods in solving the problem. The existing literature has focused on two recovery guarantees. The RIP constant is commonly used to characterize the complexity of matrix sensing problems. On the other hand, ...
-
作者：Grimmer, Benjamin
作者单位：Johns Hopkins University
摘要：The first part of this work established the foundations of a radial duality between nonnegative optimization problems, inspired by the work of Renegar (SIAM J Optim 26(4): 2649-2676, 2016). Here we utilize our radial duality theory to design and analyze projection-free optimization algorithms that operate by solving a radially dual problem. In particular, we consider radial subgradient, smoothing, and accelerated methods that are capable of solving a range of constrained convex and nonconvex o...
-
作者：Boursier, Etienne; Perchet, Vianney
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Institut Polytechnique de Paris; ENSAE Paris
摘要：Strategic information is valuable either by remaining private (for instance if it is sensitive) or, on the other hand, by being used publicly to increase some utility. These two objectives are antagonistic and leaking this information by taking full advantage of it might be more rewarding than concealing it. Unlike classical solutions that focus on the first point, we consider instead agents that optimize a natural trade-off between both objectives. We formalize this as an optimization problem...
-
作者：Herings, P. Jean-Jacques; Zhan, Yang
作者单位：Tilburg University; Nanjing University; Nanjing University
摘要：One of the most important stability concepts for network formation is pairwise stability. We develop a homotopy algorithm that is effective in computing pairwise stable networks for a generic network formation problem. To do so, we reformulate the concept of pairwise stability as a Nash equilibrium of a non-cooperative game played by the links in the network and adapt the linear tracing procedure for non-cooperative games to the network formation problem. As a by-product of our main result, we...
-
作者：Nagele, Martin; Nobel, Christian; Santiago, Richard; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：There has been significant work recently on integer programs (IPs) min{c(inverted perpendicular)x:Ax <= b,x is an element of Z(n)} with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant Delta is an element of Z(>0), Delta-modular IPs are efficiently solvable, which are IPs where the constraint matrix A is an element of Zmxn has full column rank and all nxn minors of A are within {-Delta,& mldr;,Delta}. Previous progr...
-
作者：Sinjorgo, Lennart; Sotirov, Renata; Anjos, Miguel F.
作者单位：Tilburg University; University of Edinburgh
摘要：We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices xx(H), where the elements of x is an element of C-n aremth unit roots. These polytopes have appli-cations in MAX-3-CUT, digital communication technology, angular synchronizationand more generally, complex quadratic programming. Form=2, the complex cutpolytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut poly tope with finitem>2 and provide a f...
-
作者：Thomae, Simon; Walther, Grit; Schiffer, Maximilian
作者单位：RWTH Aachen University; Technical University of Munich; Technical University of Munich
摘要：We study piecewise affine policies for multi-stage adjustable robust optimization (ARO) problems with non-negative right-hand side uncertainty. First, we construct new dominating uncertainty sets and show how a multi-stage ARO problem can be solved efficiently with a linear program when uncertainty is replaced by these new sets. We then demonstrate how solutions for this alternative problem can be transformed into solutions for the original problem. By carefully choosing the dominating sets, w...
-
作者：Liang, Jiaming; Guigues, Vincent; Monteiro, Renato D. C.
作者单位：University of Rochester; University of Rochester; Getulio Vargas Foundation; University System of Georgia; Georgia Institute of Technology
摘要：This paper considers optimization problems where the objective is the sum of a function given by an expectation and a closed convex function, and proposes stochastic composite proximal bundle (SCPB) methods for solving it. Complexity guarantees are established for them without requiring knowledge of parameters associated with the problem instance. Moreover, it is shown that they have optimal complexity when these problem parameters are known. To the best of our knowledge, this is the first pro...
-
作者：Hirayama, Tsuyoshi; Liu, Yuhao; Makino, Kazuhisa; Shi, Ke; Xu, Chao
作者单位：University of Electronic Science & Technology of China; Kyoto University
摘要：In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f : 2(V) -> R, computing a k-partition {V-1, ... , V-k} of V with minimum Sigma k(i=1) f(V-i). The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for fixed k <= 3. In this paper, we construct the first polynomial-time algorithm for ...
