On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems

  • Etienne de Klerk
  • Monique Laurent
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The Lasserre hierarchy of semidefinite programming approximations to convex polynomial optimization problems is known to converge finitely under some assumptions. [J.B. Lasserre. Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19, 1995-2014, 2009.] We give a new proof of the finite convergence property, that does not require the assumption that the Hessian of … Read more

    Using the analytic center in the feasibility pump

  • Daniel Baena
  • Jordi Castro
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    The feasibility pump (FP) [5,7] has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for finding better quality solutions. Briefly, FP alternates between two sequences of points: one of feasible so- lutions for the relaxed problem (but not integer), and another of … Read more

    A heuristic block coordinate descent approach for controlled tabular adjustment

  • Jordi Castro
  • Jose Antonio Gonzalez
    • Categories Applications - OR and Management Sciences Tags , , , , , ,

    One of the main concerns of national statistical agencies (NSAs) is to publish tabular data. NSAs have to guarantee that no private information from specific respondents can be disclosed from the released tables. The purpose of the statistical disclosure control field is to avoid such a leak of private information. Most protection techniques for tabular … Read more

    Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags ,

    The adaptive cubic regularization algorithms described in Cartis, Gould & Toint (2009, 2010) for unconstrained (nonconvex) optimization are shown to have improved worst-case efficiency in terms of the function- and gradient-evaluation count when applied to convex and strongly convex objectives. In particular, our complexity upper bounds match in order (as a function of the accuracy … Read more

    Bundle-type methods uniformly optimal for smooth and nonsmooth convex optimization

  • Guanghui Lan
    • Categories Convex Optimization Tags , , ,

    The bundle-level method and their certain variants are known to exhibit an optimal rate of convergence, i.e., ${\cal O}(1/\sqrt{t})$, and also excellent practical performance for solving general non-smooth convex programming (CP) problems. However, this rate of convergence is significantly worse than the optimal one for solving smooth CP problems, i.e., ${\cal O}(1/t^2)$. In this paper, … Read more

    Reduced RLT Representations for Nonconvex Polynomial Programming Problems

  • Evrim Dalkiran
  • Leo Liberti
  • Hanif D. Sherali
    • Categories Global Optimization Theory Tags , , , , ,

    This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations and develop certain coherent associated branching rules … Read more

    Convex envelopes for quadratic and polynomial functions over polytopes

  • Marco Locatelli
    • Categories Global Optimization Theory Tags , , , ,

    In this paper we consider the problem of computing the value and a supporting hyperplane of the convex envelope for quadratic and polynomial functions over polytopes with known vertex set. We show that for general quadratic functions the computation can be carried on through a copositive problem, but in some cases (including all the two-dimensional … Read more

    Radio Planning of Energy-Aware Cellular Networks

  • Capone Antonio
  • Silvia Boiardi
  • Brunilde Sansò
    • Categories Telecommunications Tags , , , , ,

    The role of the Information and Communication Technology sector on productivity and economic growth is constantly increasing and, due to its pervasiveness, the ICT power consumption can no longer be ignored. Some energy-aware models and approaches have already been proposed for cellular networks, they aim at reducing power expenditures while decreasing network operators costs. However, … Read more

    Convergence analysis of primal-dual algorithms for total variation image restoration

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , ,

    Recently, some attractive primal-dual algorithms have been proposed for solving a saddle-point problem, with particular applications in the area of total variation (TV) image restoration. This paper focuses on the convergence analysis of existing primal-dual algorithms and shows that the involved parameters of those primal-dual algorithms (including the step sizes) can be significantly enlarged if … Read more

    Symmetric tensor approximation hierarchies for the completely positive cone

  • Hongbo Dong
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper we construct two approximation hierarchies for the completely positive cone based on symmetric tensors. We show that one hierarchy corresponds to dual cones of a known polyhedral approximation hierarchy for the copositive cone, and the other hierarchy corresponds to dual cones of a known semidefinite approximation hierarchy for the copositive cone. As … Read more