-
作者：Ahmadi, Amir Ali; Zhang, Jeffrey
作者单位：Princeton University; Carnegie Mellon University
摘要：We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance c(n) (for any constant c >= 0) of a local minimizer of an n-variate quadratic function over a polytope. This result (even with c = 0) answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. Our proof technique also implies that the problem of deciding whether a quadratic function has a local...
-
作者：Erdogdu, Murat A.; Ozdaglar, Asuman; Parrilo, Pablo A.; Vanli, Nuri Denizcan
作者单位：University of Toronto; University of Toronto; Massachusetts Institute of Technology (MIT)
摘要：Semidetinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solvers do not scale well with the dimension of the problem. In order to address this issue, Burer and Monteiro (Math Program 95(2):329-357, 2003) proposed to reduce the dimension of the problem by appealing to a low-rank factorization and solve the subs...
-
作者：Traub, Vera; Trobst, Thorben
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Irvine
摘要：We consider the capacitated cycle covering problem: given an undirected, complete graph G with metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle co...
-
作者：Ryu, Ernest K.; Hannah, Robert; Yin, Wotao
作者单位：Seoul National University (SNU); University of California System; University of California Los Angeles
摘要：Many iterative methods in applied mathematics can be thought of as fixed-point iterations, and such algorithms are usually analyzed analytically, with inequalities. In this paper, we present a geometric approach to analyzing contractive and non-expansive fixed point iterations with a new tool called the scaled relative graph. The SRG provides a correspondence between nonlinear operators and subsets of the 2D plane. Under this framework, a geometric argument in the 2D plane becomes a rigorous p...
-
作者：Cheon, Myun-Seok
作者单位：Exxon Mobil Corporation
摘要：This paper discusses an outer-approximation guided optimization method for constrained neural network inverse problems with rectified linear units. The constrained neural network inverse problems refer to an optimization problem to find the best set of input values of a given trained neural network in order to produce a predefined desired output in presence of constraints on input values. This paper analyzes the characteristics of optimal solutions of neural network inverse problems with recti...
-
作者：Mai, Ngoc Hoang Anh; Lasserre, Jean-Bernard; Magron, Victor
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：In a first contribution, we revisit two certificates of positivity on (possibly non-compact) basic semialgebraic sets due to Putinar and Vasilescu (C R Acad Sci Ser I Math 328(6):495-499, 1999). We use Jacobi's technique from (Math Z 237(2):259-273, 2001) to provide an alternative proof with an effective degree bound on the sums of squares weights in such certificates. As a consequence, it allows one to define a hierarchy of semidefinite relaxations for a general polynomial optimization proble...
-
作者：Barak, Boaz; Moitra, Ankur
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：In the noisy tensor completion problem we observe m entries (whose location is chosen uniformly at random) from an unknown n(1) x n(2) x n(3) tensor T. We assume that T is entry-wise close to being rank r. Our goal is to fill in its missing entries using as few observations as possible. Let n = max(n(1), n(2), n(3)). We show that if m greater than or similar to n(3/2)r then there is a polynomial time algorithm based on the sixth level of the sum-of-squares hierarchy for completing it. Our esti...
-
作者：Naderi, Mohammad Javad; Buchanan, Austin; Walteros, Jose L.
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater; State University of New York (SUNY) System; University at Buffalo, SUNY
摘要：The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worst-case properties, especially for sparse graphs. The smallest MIP that we pro...
-
作者：Kiraly, Csaba; Mihalyko, Andras
作者单位：Eotvos Lorand University; HUN-REN
摘要：For two integers k > 0 and l, a graph G = (V, E) is called (k, l)-tight if vertical bar E vertical bar = k vertical bar V vertical bar-l and i(G)(X) <= k vertical bar X vertical bar-l for each X subset of V for which i(G)(X) >= 1, where i(G)(X) denotes the number of induced edges by X. G is called (k, l)-redundant if G - e has a spanning (k, l)-tight subgraph for all e is an element of E. We consider the following augmentation problem. Given a graph G = (V, E) that has a (k, l)-tight spanning ...
-
作者：Kocyigit, Cagil; Rujeerapaiboon, Napat; Kuhn, Daniel
作者单位：University of Luxembourg; National University of Singapore; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer's values for the goods range over a rectangular uncertainty set. We interpret this pricing problem as a zero-sum game between the seller, who chooses a selling mechanism, and a fictitious adversary or 'nature', who chooses the buyer's values from within the uncertainty set. Using duality techniques rooted in robust optimizati...
