Solving L 1-CTA in 3D tables by an interior-point method for primal block-angular problems

The purpose of the field of statistical disclosure control is to avoid that confidential information could be derived from statistical data released by, mainly, national statistical agencies. Controlled tabular adjustment (CTA) is an emerging technique for the protection of statistical tabular data. Given a table with sensitive information, CTA looks for the closest safe table. In this work we focus on CTA for three-dimensional tables using the L ₁ norm for the distance between the original and protected tables. Three L ₁-CTA models are presented, giving rise to six different primal block-angular structures of the constraint matrices. The resulting linear programming problems are solved by a specialized interior-point algorithm for this constraints structure which solves the normal equations by a combination of Cholesky factorization and preconditioned conjugate gradients (PCG). In the past this algorithm was shown to be one of the most efficient approaches for some classes of block-angular problems. The effect of quadratic regularizations is also analyzed, showing that for three of the six primal block-angular structures the performance of PCG is guaranteed to improve. Computational results are reported for a set of large instances, which provide linear optimization problems of up to 50 million variables and 25 million constraints. The specialized interior-point algorithm is compared with the state-of-the-art barrier solver of the CPLEX 12.1 package, showing to be a more efficient choice for very large L ₁-CTA instances.     

Recent advances in optimization techniques for statistical tabular data protection

One of the main services of National Statistical Agencies (NSAs) for the current Information Society is the dissemination of large amounts of tabular data, which is obtained from microdata by crossing one or more categorical variables. NSAs must guarantee that no confidential individual information can be obtained from the released tabular data. Several statistical disclosure control methods are available for this purpose. These methods result in large linear, mixed integer linear, or quadratic mixed integer linear optimization problems. This paper reviews some of the existing approaches, with an emphasis on two of them: cell suppression problem (CSP) and controlled tabular adjustment (CTA). CSP and CTA have concentrated most of the recent research in the tabular data protection field. The particular focus of this work is on methods and results of practical interest for end-users (mostly, NSAs). Therefore, in addition to the resulting optimization models and solution approaches, computational results comparing the main optimization techniques - both optimal and heuristic - using real-world instances are also presented.     

Quadratic interior-point methods in statistical disclosure control

The safe dissemination of statistical tabular data is one of the main concerns of National Statistical Institutes (NSIs). Although each cell of the tables is made up of the aggregated information of several individuals, the statistical confidentiality can be violated. NSIs must guarantee that no individual information can be derived from the released tables. One widely used type of methods to reduce the disclosure risk is based on the perturbation of the cell values. We consider a new controlled perturbation method which, given a set of tables to be protected, finds the closest safe ones - thus reducing the information loss while preserving confidentiality. This approach means solving a quadratic optimization problem with a much larger number of variables than constraints. Real instances can provide problems with millions of variables. We show that interior-point methods are an effective choice for that model, and, also, that specialized algorithms which exploit the problem structure can be faster than state-of-the art general solvers. Computational results are presented for instances of up to 1000000 variables.AMS Subject Classification: 90C06, 90C20, 90C51, 90C90Jordi Castro: Partially supported by the EU IST-2000-25069 CASC project and by the Spanish MCyT project TIC2003-00997.     

Convex approximations in stochastic programming by semidefinite programming

The following question arises in stochastic programming: how can one approximate a noisy convex function with a convex quadratic function that is optimal in some sense. Using several approaches for constructing convex approximations we present some optimization models yielding convex quadratic regressions that are optimal approximations in L ₁, L _?? and L ₂ norm. Extensive numerical experiments to investigate the behavior of the proposed methods are also performed.     

A computational study and survey of methods for the single-row facility layout problem

The single-row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange rectangular departments so as to minimize the overall interaction cost. This paper compares the different modelling approaches for (SRFLP) and applies a recent SDP approach for general quadratic ordering problems from Hungerländer and Rendl to (SRFLP). In particular, we report optimal solutions for several (SRFLP) instances from the literature with up to 42 departments that remained unsolved so far. Secondly we significantly reduce the best known gaps and running times for large instances with up to 110 departments.     

Reflection theorem for divisor class groups of relative quadratic function fields

We present the reflection theorem for divisor class groups of relative quadratic function fields. Let K be a global function field with constant field Fq. Let L₁ be a quadratic geometric extension of K and let L₂ be its twist by the quadratic constant field extension of K. We show that for every odd integer m that divides q+1 the divisor class groups of L₁ and L₂ have the same m-rank.     

Exact L 2-norm plane separation

We consider the problem of separating two sets of points in an n-dimensional real space with a (hyper)plane that minimizes the sum of L _p -norm distances to the plane of points lying on the wrong side of it. Despite recent progress, practical techniques for the exact solution of cases other than the L ₁ and L _∞-norm were unavailable. We propose and implement a new approach, based on non-convex quadratic programming, for the exact solution of the L ₂-norm case. We solve in reasonable computing times artificial problems of up to 20000 points (in 6 dimensions) and 13 dimensions (with 2000 points). We also observe that, for difficult real-life instances from the UCI Repository, computation times are substantially reduced by incorporating heuristic results in the exact solution process. Finally, we compare the classification performance of the planes obtained for the L ₁, L ₂ and L _∞ formulations. It appears that, despite the fact that L ₂ formulation is computationally more expensive, it does not give significantly better results than the L ₁ and L _∞ formulations.     

The Scholz theorem in function fields

The Scholz theorem in function fields states that the l-rank difference between the class groups of an imaginary quadratic function field and its associated real quadratic function field is either 0 or 1 for some prime l. Furthermore, Leopoldt's Spiegelungssatz (= the Reflection theorem) in function fields yields a comparison between the m-rank of some subgroup of the class group of an imaginary cyclic function field L₁ and the m-rank of some subgroup of the class group of its associated real cyclic function field L₂ for some prime number m; then their m-ranks also equal or differ by 1. In this paper we find an explicit necessary condition for their m-ranks (respectively l-ranks) to be the same in the case of cyclic function fields (respectively quadratic function fields). In particular, in the case of quadratic function fields, if l does not divide the regulator of L₂, then their l-ranks are the same, equivalently if their l-ranks differ by 1, then l divides the regulator of L₂.     

The generalized trust region subproblem

The interval bounded generalized trust region subproblem (GTRS) consists in minimizing a general quadratic objective, q ₀(x)→min, subject to an upper and lower bounded general quadratic constraint, ?≤q ₁(x)≤u. This means that there are no definiteness assumptions on either quadratic function. We first study characterizations of optimality for this implicitly convex problem under a constraint qualification and show that it can be assumed without loss of generality. We next classify the GTRS into easy case and hard case instances, and demonstrate that the upper and lower bounded general problem can be reduced to an equivalent equality constrained problem after identifying suitable generalized eigenvalues and possibly solving a sparse system. We then discuss how the Rendl-Wolkowicz algorithm proposed in Fortin and Wolkowicz (Optim. Methods Softw. 19(1):41–67, 2004) and Rendl and Wolkowicz (Math. Program. 77(2, Ser. B):273–299, 1997) can be extended to solve the resulting equality constrained problem, highlighting the connection between the GTRS and the problem of finding minimum generalized eigenvalues of a parameterized matrix pencil. Finally, we present numerical results to illustrate this algorithm at the end of the paper.     

POPMUSIC for the travelling salesman problem

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.     

General L p -harmonic Blaschke bodies

Lutwak introduced the harmonic Blaschke combination and the harmonic Blaschke body of a star body. Further, Feng and Wang introduced the concept of the L _p -harmonic Blaschke body of a star body. In this paper, we define the notion of general L _p -harmonic Blaschke bodies and establish some of its properties. In particular, we obtain the extreme values concerning the volume and the L _p -dual geominimal surface area of this new notion.     

Central values of L-functions over CM fields

We prove an explicit formula for the central values of certain Rankin L-functions. These L-functions are the L-functions attached to Hilbert newforms over a totally real field F, twisted by unitary Hecke characters of a totally imaginary quadratic extension of F. This formula generalizes our former result on L-functions twisted by finite CM characters.     

An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem

In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form “no more than l_ccars are allowed to require a component c in any subsequence of m_cconsecutive cars”. The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSP_LIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSP_LIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods.     

Solution of the wave equation in Rn + 1 with data on a characteristic cone

A unified treatment of the problem is presented for both odd and even space dimensions. In contrast to previous results for odd n, when the space dimension is even, there is no general existence although the uniqueness holds. A necessary and sufficient condition for admissible data is given. Of independent interest are several versions of the “Plancherel theorem” of the Radon transform, in the space L₂¹(Rⁿ) of all functions whose gradients are square integrable.     

Superconvergence of RT1 mixed finite element approximations for elliptic control problems

In this paper,we investigate the superconvergence property of the numerical solution to a quadratic elliptic control problem by using mixed finite element methods.The state and co-state are approximated by the order k=1 Raviart-Thomas mixed finite element spaces and the control variable is approximated by piecewise constant functions.We prove the superconvergence error estimate of h3/2 in L2-norm between the approximated solution and the average L2 projection of the control.Moreover,by the postprocessing technique,a quadratic superconvergence result of the control is derived.     

Splitting of Quadratic Forms under Some Generic Field Extensions

Let F be a field, char F ≠ 2, and ? and ψ be anisotropic quadratic forms over F. Let L be a generic field extension of F such that i(ψ _L ) ≥ 2. Under what conditions is the form ? _L isotropic? We give an answer to this question in the cases where dim ? = 5, dim ψ = 6 and dim ? = 6, dim ψ = 7. Bibliography: 18 titles.     

A comparison of algorithms for the multivariate L 1-median

The L ₁-median is a robust estimator of multivariate location with good statistical properties. Several algorithms for computing the L ₁-median are available. Problem specific algorithms can be used, but also general optimization routines. The aim is to compare different algorithms with respect to their precision and runtime. This is possible because all considered algorithms have been implemented in a standardized manner in the open source environment R. In most situations, the algorithm based on the optimization routine NLM (non-linear minimization) clearly outperforms other approaches. Its low computation time makes applications for large and high-dimensional data feasible.     

Some Siegel modular standard L-values, and Shafarevich-Tate groups

We explain how the Bloch-Kato conjecture leads us to the following conclusion: a large prime dividing a critical value of the L-function of a classical Hecke eigenform f of level 1, should often also divide certain ratios of critical values for the standard L-function of a related genus two (and in general vector-valued) Hecke eigenform F. The relation between f and F (Harder?s conjecture in the vector-valued case) is a congruence involving Hecke eigenvalues, modulo the large prime. In the scalar-valued case we prove the divisibility, subject to weak conditions. In two instances in the vector-valued case, we confirm the divisibility using elaborate computations involving special differential operators. These computations do not depend for their validity on any unproved conjecture.     

Stationary logic of ordinals

The L(aa)-theory of ordinals—Th_aa(On)—is studied. It is shown that Th_aa(On) is primitive recursive. In a suitable language it is possible to eliminate quantifiers. L(aa)-equivalence invariants are given. Both the complete L(aa)-theories of ordinals and the complete extensions of Th_aa(On) are characterized. An ordering is L(aa)-inductive if every L(aa)-definable subset (with suitable parameters) has a least element. The models of Th_aa(On) are the L(aa)-inductive orderings. A variant of the back and forth method is introduced in order toprove primitive recursive decidability and elimination of quantifier results.     

Quadratic residues and the distribution of prime numbers

D. Shanks [11] has given a heuristical argument for the fact that there are “more” primes in the non-quadratic residue classes modq than in the quadratic ones. In this paper we confirmShanks' conjecture in all casesq<25 in the following sense. Ifl ₁ is a quadratic residue,l ₂ a non-residue modq, ε(n, q, l ₁,l ₂) takes the values +1 or ?1 according ton?l ₁ orl ₂ modq, then $$\mathop {\lim }\limits_{x \to \infty } \sum\limits_p {\varepsilon (p,q,l_1 ,l_2 )} \log pp^{ - \alpha } \exp ( - (\log p)^2 /x) = - \infty$$ for 0≤α<1/2. In the general case the same holds, if all zeros ?=β+yγ of allL(s, χ modq),q fix, satisfy the inequality β²?γ²<1/4.