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
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
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
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
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
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
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
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
We employ recent work on computational noise to obtain near-optimal finite difference estimates of the derivatives of a noisy function. Our analysis employs a stochastic model of the noise without assuming a specific form of distribution. We use this model to derive theoretical bounds for the errors in the difference estimates and obtain an easily … Read more
We present an inexact spectral bundle method for solving convex quadratic semidefinite optimization problems. This method is a first-order method, hence requires much less computational cost each iteration than second-order approaches such as interior-point methods. In each iteration of our method, we solve an eigenvalue minimization problem inexactly, and solve a small convex quadratic semidefinite … Read more