-
作者：d'Aspremont, Alexandre; Bach, Francis; El Ghaoui, Laurent
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Ecole Normale Superieure (ENS); Inria; University of California System; University of California Berkeley
摘要：We produce approximation bounds on a semidefinite programming relaxation for sparse principal component analysis. The sparse maximum eigenvalue problem cannot be efficiently approximated up to a constant approximation ratio, so our bounds depend on the optimum value of the semidefinite relaxation: the higher this value, the better the approximation. In particular, these bounds allow us to control approximation ratios for tractable statistics in hypothesis testing problems where data points are...
-
作者：Brunsch, Tobias; Roeglin, Heiko; Rutten, Cyriel; Vredeveld, Tjark
作者单位：University of Bonn; Maastricht University
摘要：We study popular local search and greedy algorithms for standard machine scheduling problems. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat contrived and it is questionable whether they arise in practical applications. To find out how robust these bounds are, we study the algorithms in the framework of smoothed analysis, in which instances are subject to some degree of random noise. While the lower bounds for all scheduling vari...
-
作者：Ding, Chao; Sun, Defeng; Toh, Kim-Chuan
作者单位：Chinese Academy of Sciences; National University of Singapore; National University of Singapore
摘要：In this paper, we define a class of linear conic programming (which we call matrix cone programming or MCP) involving the epigraphs of five commonly used matrix norms and the well studied symmetric cone. MCP has recently been found to have many important applications, for example, in nuclear norm relaxations of affine rank minimization problems. In order to make the defined MCP tractable and meaningful, we must first understand the structure of these epigraphs. So far, only the epigraph of the...
-
作者：Epstein, Leah; Levin, Asaf
作者单位：University of Haifa; Technion Israel Institute of Technology
摘要：We consider basic problems of non-preemptive scheduling on uniformly related machines. For a given schedule, defined by a partition of the jobs into m subsets corresponding to the m machines, denotes the completion time of machine i. Our goal is to find a schedule that minimizes or maximizes for a fixed value of p such that . For the minimization problem is equivalent to the well-known problem of minimizing the norm of the vector of the completion times of the machines, and for , the maximizat...
-
作者：Attouch, Hedy; Bolte, Jerome; Svaiter, Benar Fux
作者单位：Universite de Montpellier; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：In view of the minimization of a nonsmooth nonconvex function f, we prove an abstract convergence result for descent methods satisfying a sufficient-decrease assumption, and allowing a relative error tolerance. Our result guarantees the convergence of bounded sequences, under the assumption that the function f satisfies the Kurdyka-Aojasiewicz inequality. This assumption allows to cover a wide range of problems, including nonsmooth semi-algebraic (or more generally tame) minimization. The spec...
-
作者：Buchheim, Christoph; Wiegele, Angelika
作者单位：Dortmund University of Technology; University of Klagenfurt
摘要：We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this approach as a bounding routine in an SDP-based branch-and-bound framework. In case of a conv...
-
作者：Zhao, Ming; de Farias, Ismael Regis, Jr.
作者单位：Texas Tech University System; Texas Tech University
摘要：We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints.
-
作者：Van Ngai Huynh; Huu Tron Nguyen; Thera, Michel
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Limoges
摘要：In this paper, we establish some new characterizations of metric regularity of implicit multifunctions in complete metric spaces by using lower semicontinuous envelopes of the distance functions to set-valued mappings. Through these new characterizations it is possible to investigate implicit multifunction theorems based on coderivatives and on contingent derivatives as well as the perturbation stability of implicit multifunctions.
-
作者：Zymler, Steve; Kuhn, Daniel; Rustem, Berc
作者单位：Imperial College London
摘要：We develop tractable semidefinite programming based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove that this approximation is exact for robust individual chance constraints with concave or (n...
-
作者：Duer, Mirjam; Hiriart-Urruty, Jean-Baptiste
作者单位：Universitat Trier; Universite de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：We consider the problem of minimizing an indefinite quadratic form over the nonnegative orthant, or equivalently, the problem of deciding whether a symmetric matrix is copositive. We formulate the problem as a difference of convex functions problem. Using conjugate duality, we show that there is a one-to-one correspondence between their respective critical points and minima. We then apply a subgradient algorithm to approximate those critical points and obtain an efficient heuristic to verify n...
