2期

最新文章

• Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times AI翻译
  作者：Shioura, Akiyoshi; Shakhlevich, Natalia V.; Strusevich, Vitaly A.
  作者单位：Tohoku University; University of Leeds; University of Greenwich
  摘要：In this paper we present a decomposition algorithm for maximizing a linear function over a submodular polyhedron intersected with a box. Apart from this contribution to submodular optimization, our results extend the toolkit available in deterministic machine scheduling with controllable processing times. We demonstrate how this method can be applied to developing fast algorithms for minimizing total compression cost for preemptive schedules on parallel machines with respect to given release d...
• A semidefinite programming hierarchy for packing problems in discrete geometry AI翻译
  作者：de laat, David; Vallentin, Frank
  作者单位：Delft University of Technology; University of Cologne
  摘要：Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre's semidefinite programming hierarchy. We generalize this approach to infinite graphs. For this we introduce topological packing graphs as an abstraction for infinite graphs coming from packing problems ...
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex AI翻译
  作者：de Klerk, Etienne; Laurent, Monique; Sun, Zhao
  作者单位：Tilburg University; Centrum Wiskunde & Informatica (CWI)
  摘要：The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems-it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties...
• A Riemannian symmetric rank-one trust-region method AI翻译
  作者：Huang, Wen; Absil, P. -A.; Gallivan, K. A.
  作者单位：State University System of Florida; Florida State University; Universite Catholique Louvain
  摘要：The well-known symmetric rank-one trust-region method-where the Hessian approximation is generated by the symmetric rank-one update-is generalized to the problem of minimizing a real-valued function over a -dimensional Riemannian manifold. The generalization relies on basic differential-geometric concepts, such as tangent spaces, Riemannian metrics, and the Riemannian gradient, as well as on the more recent notions of (first-order) retraction and vector transport. The new method, called RTR-SR...
• A homogeneous interior-point algorithm for nonsymmetric convex conic optimization AI翻译
  作者：Skajaa, Anders; Ye, Yinyu
  作者单位：Technical University of Denmark; Stanford University; Nanjing University
  摘要：A homogeneous interior-point algorithm for solving nonsymmetric convex conic optimization problems is presented. Starting each iteration from the vicinity of the central path, the method steps in the approximate tangent direction and then applies a correction phase to locate the next well-centered primal-dual point. Features of the algorithm include that it makes use only of the primal barrier function, that it is able to detect infeasibilities in the problem and that no phase-I method is need...
• Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones AI翻译
  作者：Saunderson, James; Parrilo, Pablo A.
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We give explicit polynomial-sized (in n and k) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree k in n variables. These convex cones form a family of non-polyhedral outer approximations of the non-negative orthant that preserve low-dimensional faces while successively discarding high-dimensional faces. More generally we construct explicit semidefinite representations (polynomial-sized in k, m, and n) of the hyperbolicity con...
• A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems AI翻译
  作者：Fernandes, Cristina G.; Meira, Luis A. A.; Miyazawa, Flavio K.; Pedrosa, Lehilton L. C.
  作者单位：Universidade de Sao Paulo; Universidade Estadual de Campinas; Universidade Estadual de Campinas
  摘要：A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and show that each such program can be solved by a computer to bound the approximation factor of an associated algorithm. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the metric facility location problem (MFLP) and to a g...
• Primal convergence from dual subgradient methods for convex optimization AI翻译
  作者：Gustavsson, Emil; Patriksson, Michael; Stromberg, Ann-Brith
  作者单位：Chalmers University of Technology; University of Gothenburg
  摘要：When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favorably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach unless the Lagrangian dual function is differentiable at an optimal solution. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which...
• On averaging and representation properties of the BFGS and related secant updates AI翻译
  作者：Tapia, Richard
  作者单位：Rice University
  摘要：In this paper we present several representation theorems and averaging theorems for members of the difference class of secant updates introduced by Brodlie et al. (J Inst Math Appl 11:73-82, 1973). Major contributions are that the integral form of the mean-value theorem leads to a proof that the BFGS update is pointwise the infinite average of all the updates on the one-dimension manifold in the Dennis class that connects the DFP secant update to the Greenstadt update, and that it can be expre...
• A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization AI翻译
  作者：Bertsimas, Dimitris; Goyal, Vineet; Lu, Brian Y.
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Columbia University
  摘要：In this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters (Feige et al. in Lect Notes Comput Sci 4513:439-453, 2007). On the other hand, a static solu...