-
作者：Dobre, Cristian; Vera, Juan
作者单位：Wageningen University & Research; Tilburg University
摘要：Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and the lack of information about the quality of the semidefinite programming approximations. These drawbacks are an inevitable conseque...
-
作者：Cornuejols, Gerard; Schaefer, Andrew
作者单位：Carnegie Mellon University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
-
作者：Ben-Tal, Aharon; den Hertog, Dick; Vial, Jean-Philippe
作者单位：Technion Israel Institute of Technology; Tilburg University; Tilburg University
摘要：In this paper we provide a systematic way to construct the robust counterpart of a nonlinear uncertain inequality that is concave in the uncertain parameters. We use convex analysis (support functions, conjugate functions, Fenchel duality) and conic duality in order to convert the robust counterpart into an explicit and computationally tractable set of constraints. It turns out that to do so one has to calculate the support function of the uncertainty set and the concave conjugate of the nonli...
-
作者：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...
