-
作者：Bao, Xiaowei; Sahinidis, Nikolaos V.; Tawarmalani, Mohit
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Urbana-Champaign; Purdue University System; Purdue University
摘要：At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be formulated as semidefinite programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is equivale...
-
作者：Fukasawa, Ricardo; Goycoolea, Marcos
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez
摘要：During the last decades, much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets, which we call knapsack cuts. Bixby et al. (The sharpest cut: the impact of Manfred Padberg and his work. MPS/SIAM Series on Optimization, pp. 309-326, 2004) empirically observe that, within the context of branch-and-cut algorithms to solve mixed integer programming problems, the most important inequalities are knapsack cuts derived by the mixed integer rounding (...
-
作者：Averkov, Gennadiy; Henk, Martin
作者单位：Otto von Guericke University
摘要：A polynomial representation of a convex d-polytope P is a finite set {p(1)(x), ... , p(n)(x)} of polynomials over R-d such that P = {x is an element of R-d : p(i)(x) >= 0 for every 1 <= i <= n}. Let s(d, P) be the least possible n as above. It is conjectured that s(d, P) = d for all convex d-polytopes P. We confirm this conjecture for simple d-polytopes by providing an explicit construction of d polynomials that represent a given simple d-polytope P.
-
作者：Bertsekas, Dimitri P.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider the minimization of a sum Sigma(m)(i=1) f(i)(x) consisting of a large number of convex component functions f(i). For this problem, incremental methods consisting of gradient or subgradient iterations applied to single components have proved very effective. We propose new incremental methods, consisting of proximal iterations applied to single components, as well as combinations of gradient, subgradient, and proximal iterations. We provide a convergence and rate of convergence analy...
-
作者：Koenemann, Jochen; Pritchard, David; Tan, Kunlun
作者单位：University of Waterloo; Microsoft
摘要：The authors discuss one type of general forward-backward stochastic differential equations (FBSDEs) with It's stochastic delayed equations as the forward equations and anticipated backward stochastic differential equations as the backward equations. The existence and uniqueness results of the general FBSDEs are obtained. In the framework of the general FBSDEs in this paper, the explicit form of the optimal control for linearquadratic stochastic optimal control problem with delay and the Nash e...
-
作者：Hemmecke, Raymond; Onn, Shmuel; Weismantel, Robert
作者单位：Otto von Guericke University; Technion Israel Institute of Technology
摘要：In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer m...
-
作者：Kiwiel, K. C.
作者单位：Polish Academy of Sciences; Systems Research Institute of the Polish Academy of Sciences
摘要：We give a bundle method for minimizing the sum of two convex functions, one of them being known only via an oracle of arbitrary accuracy. Each iteration involves solving two subproblems in which the functions are alternately represented by their linearizations. Our approach is motivated by applications to nonlinear multicommodity flow problems. Encouraging numerical experience on large scale problems is reported.
-
作者：Lobel, Ilan; Ozdaglar, Asuman; Feijer, Diego
作者单位：New York University; Massachusetts Institute of Technology (MIT)
摘要：We study distributed algorithms for solving global optimization problems in which the objective function is the sum of local objective functions of agents and the constraint set is given by the intersection of local constraint sets of agents. We assume that each agent knows only his own local objective function and constraint set, and exchanges information with the other agents over a randomly varying network topology to update his information state. We assume a state-dependent communication m...
-
作者：Nesterov, Yurii
摘要：In this paper we develop a new affine-invariant primal-dual subgradient method for nonsmooth convex optimization problems. This scheme is based on a self-concordant barrier for the basic feasible set. It is suitable for finding approximate solutions with certain relative accuracy. We discuss some applications of this technique including fractional covering problem, maximal concurrent flow problem, semidefinite relaxations and nonlinear online optimization. For all these problems, the rate of c...
-
作者：Recht, Benjamin; Xu, Weiyu; Hassibi, Babak
作者单位：University of Wisconsin System; University of Wisconsin Madison; California Institute of Technology
摘要：Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in machine learning, control theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-hard, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm-equal to the sum of the singular values-of the decision variable and has been shown t...
