-
作者：Bian, Wei; Chen, Xiaojun; Ye, Yinyu
作者单位：Harbin Institute of Technology; Hong Kong Polytechnic University; Stanford University
摘要：We propose a first order interior point algorithm for a class of non-Lipschitz and nonconvex minimization problems with box constraints, which arise from applications in variable selection and regularized optimization. The objective functions of these problems are continuously differentiable typically at interior points of the feasible set. Our first order algorithm is easy to implement and the objective function value is reduced monotonically along the iteration points. We show that the worst...
-
作者：Iiduka, Hideaki
作者单位：Meiji University
摘要：The existing algorithms for solving the convex minimization problem over the fixed point set of a nonexpansive mapping on a Hilbert space are based on algorithmic methods, such as the steepest descent method and conjugate gradient methods, for finding a minimizer of the objective function over the whole space, and attach importance to minimizing the objective function as quickly as possible. Meanwhile, it is of practical importance to devise algorithms which converge in the fixed point set qui...
-
作者：Kalaitzis, Christos; Madry, Aleksander; Newman, Alantha; Polacek, Lukas; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Royal Institute of Technology; Massachusetts Institute of Technology (MIT); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of , which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is st...
-
作者：Kummer, Mario; Plaumann, Daniel; Vinzant, Cynthia
作者单位：University of Konstanz; University of Michigan System; University of Michigan
摘要：Hyperbolic polynomials are real polynomials whose real hypersurfaces are maximally nested ovaloids, the innermost of which is convex. These polynomials appear in many areas of mathematics, including optimization, combinatorics and differential equations. Here we investigate the special connection between a hyperbolic polynomial and the set of polynomials that interlace it. This set of interlacers is a convex cone, which we write as a linear slice of the cone of nonnegative polynomials. In part...
-
作者：Diouane, Y.; Gratton, S.; Vicente, L. N.
作者单位：CERFACS; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universidade de Coimbra
摘要：In this paper we show how to modify a large class of evolution strategies (ES's) for unconstrained optimization to rigorously achieve a form of global convergence, meaning convergence to stationary points independently of the starting point. The type of ES under consideration recombines the parent points by means of a weighted sum, around which the offspring points are computed by random generation. One relevant instance of such an ES is covariance matrix adaptation ES (CMA-ES). The modificati...
-
作者：Ottem, John Christian; Ranestad, Kristian; Sturmfels, Bernd; Vinzant, Cynthia
作者单位：University of Cambridge; University of Oslo; University of California System; University of California Berkeley; North Carolina State University
摘要：Quartic spectrahedra in 3-space form a semialgebraic set of dimension 24. This set is stratified by the location of the ten nodes of the corresponding real quartic surface. There are twenty maximal strata, identified recently by Degtyarev and Itenberg, via the global Torelli Theorem for real K3 surfaces. We here give a new proof that is self-contained and algorithmic. This involves extending Cayley's characterization of quartic symmetroids, by the property that the branch locus of the projecti...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse
摘要：Given a compact basic semi- algebraic set K subset of R-n x R-m, a simple set B (box or ellipsoid), and some semi- algebraic function f, we consider sets defined with quantifiers, of the form R-f := {x is an element of B : f (x, y) <= 0 for all y such that (x, y) is an element of K} D-f := {x is an element of B : f (x, y) >= 0 for some y such that (x, y) is an element of K}. The former set R-f is particularly useful to qualify robust decisions x versus noise parameter y (e. g. in robust optim...
-
作者：Averkov, Gennadiy; Basu, Amitabh
作者单位：Otto von Guericke University; Johns Hopkins University
摘要：We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu et al. (Math Oper Res 37(2):346-355, 2012) for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterati...
-
作者：He, Bingsheng; Yuan, Xiaoming
作者单位：Nanjing University; Hong Kong Baptist University
摘要：This note provides a simple proof of a worst-case convergence rate measured by the iteration complexity for the Douglas-Rachford operator splitting method for finding a root of the sum of two maximal monotone set-valued operators. The accuracy of an iterate to the solution set is measured by the residual of a characterization of the original problem, which is different from conventional measures such as the distance to the solution set.
-
作者：Li, G.; Mordukhovich, B. S.; Pham, T. S.
作者单位：University of New South Wales Sydney; Wayne State University; King Fahd University of Petroleum & Minerals; Duy Tan University
摘要：In this paper we derive new fractional error bounds for polynomial systems with exponents explicitly determined by the dimension of the underlying space and the number/degree of the involved polynomials. Our major result extends the existing error bounds from the system involving only a single polynomial to a general polynomial system and do not require any regularity assumptions. In this way we resolve, in particular, some open questions posed in the literature. The developed techniques are l...
