Search

In this paper we extend the core branch-and-bound algorithm of an RLT-based solver for continuous polynomial optimization, RAPOSa, to handle mixed-integer problems. We do so by a direct adaptation, in which LP relaxations are replaced with MILP ones and, therefore, the additional burden caused by the discrete variables is taken care of by the auxiliary MILP solver. The analysis then focuses on the impact of a number of choices that must be made for the resulting algorithm to be effective at providing good lower and upper bounds upon termination.

Over the last few years, there has been a surge in the use of learning techniques to improve the performance of optimization algorithms. In particular, the learning of branching rules in mixed integer linear programming has received a lot of attention, with most methodologies based on strong branching imitation. Recently, some advances have been made as well in the context of nonlinear programming, with some methodologies focusing on learning to select the best branching rule among a predefined set of rules leading to promising results. In this paper we explore, in the nonlinear setting, the limits on the improvements that might be achieved by the above two approaches: learning to select the best variable (strong branching) and learning to select the best rule (rule selection).

Domain reduction techniques are at the core of any global optimization solver for NLP or MINLP problems. In this paper, we delve into several of these techniques and assess the impact they may have in the performance of an RLT-based algorithm for polynomial optimization problems. These techniques include i) the use of (nonlinear) conic relaxations for optimality-based bound tightening, ii) the use of Lagrangian dual information to enhance feasibility-based bound tightening, and iii) different strategies for branching point selection. We also explore how a solver equipped with these domain reduction enhancements can further improve its performance by using machine learning to better choose the best domain reduction approach to use on a given instance.

This paper presents a new approach to quadrify a polynomial programming problem, i.e. reduce the polynomial program to a quadratic program, before solving it. The proposed approach, QUAD-RLT, exploits the Reformulation-Linearization Technique (RLT) structure to obtain smaller relaxations that can be solved faster and still provide high quality bounds. QUAD-RLT is compared to other quadrification techniques that have been previously discussed in the literature. The paper presents theoretical as well as computational results showing the advantage of QUAD-RLT compared to other quadrification techniques. Furthermore, rather than quadrifying a polynomial program, QUAD-RLT is generalized to reduce the degree of the polynomial to any degree. Computational results show that reducing the degree of the polynomial to a degree that is higher than two provides computational advantages in certain cases compared to fully quadrifying the problem. Finally, QUAD-RLT along with other quadrification/degree reduction schemes are implemented and made available in the freely available software RAPOSa.

Low-cost portable devices capable of capturing signature signals are being increasingly used. Additionally, the social and legal acceptance of the written signature for authentication purposes is opening a range of new applications. We describe a highly versatile and scalable prototype for Web-based secure access using signature verification. The proposed architecture can be easily extended to work with different kinds of sensors and large-scale databases. Several remarks are also given on security and privacy of network-based signature verification., Comment: Published at IEEE Aerospace and Electronic Systems Magazine

We report on experiments for the fingerprint modality conducted during the First BioSecure Residential Workshop. Two reference systems for fingerprint verification have been tested together with two additional non-reference systems. These systems follow different approaches of fingerprint processing and are discussed in detail. Fusion experiments I volving different combinations of the available systems are presented. The experimental results show that the best recognition strategy involves both minutiae-based and correlation-based measurements. Regarding the fusion experiments, the best relative improvement is obtained when fusing systems that are based on heterogeneous strategies for feature extraction and/or matching. The best combinations of two/three/four systems always include the best individual systems whereas the best verification performance is obtained when combining all the available systems., Comment: Published at Annals of Telecommunications, Special Issue on Multimodal Biometrics

Signal-quality awareness has been found to increase recognition rates and to support decisions in multisensor environments significantly. Nevertheless, automatic quality assessment is still an open issue. Here, we study the orientation tensor of fingerprint images to quantify signal impairments, such as noise, lack of structure, blur, with the help of symmetry descriptors. A strongly reduced reference is especially favorable in biometrics, but less information is not sufficient for the approach. This is also supported by numerous experiments involving a simpler quality estimator, a trained method (NFIQ), as well as the human perception of fingerprint quality on several public databases. Furthermore, quality measurements are extensively reused to adapt fusion parameters in a monomodal multialgorithm fingerprint recognition environment. In this study, several trained and nontrained score-level fusion schemes are investigated. A Bayes-based strategy for incorporating experts past performances and current quality conditions, a novel cascaded scheme for computational efficiency, besides simple fusion rules, is presented. The quantitative results favor quality awareness under all aspects, boosting recognition rates and fusing differently skilled experts efficiently as well as effectively (by training)., Comment: Published at IEEE Transactions on Information Forensics and Security

As biometric technology is increasingly deployed, it will be common to replace parts of operational systems with newer designs. The cost and inconvenience of reacquiring enrolled users when a new vendor solution is incorporated makes this approach difficult and many applications will require to deal with information from different sources regularly. These interoperability problems can dramatically affect the performance of biometric systems and thus, they need to be overcome. Here, we describe and evaluate the ATVS-UAM fusion approach submitted to the quality-based evaluation of the 2007 BioSecure Multimodal Evaluation Campaign, whose aim was to compare fusion algorithms when biometric signals were generated using several biometric devices in mismatched conditions. Quality measures from the raw biometric data are available to allow system adjustment to changing quality conditions due to device changes. This system adjustment is referred to as quality-based conditional processing. The proposed fusion approach is based on linear logistic regression, in which fused scores tend to be log-likelihood-ratios. This allows the easy and efficient combination of matching scores from different devices assuming low dependence among modalities. In our system, quality information is used to switch between different system modules depending on the data source (the sensor in our case) and to reject channels with low quality data during the fusion. We compare our fusion approach to a set of rule-based fusion schemes over normalized scores. Results show that the proposed approach outperforms all the rule-based fusion schemes. We also show that with the quality-based channel rejection scheme, an overall improvement of 25% in the equal error rate is obtained., Comment: Published at IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans

Conic optimization has recently emerged as a powerful tool for designing tractable and guaranteed algorithms for non-convex polynomial optimization problems. On the one hand, tractability is crucial for efficiently solving large-scale problems and, on the other hand, strong bounds are needed to ensure high quality solutions. In this research, we investigate the strengthening of RLT relaxations of polynomial optimization problems through the addition of nine different types of constraints that are based on linear, second-order cone, and semidefinite programming to solve to optimality the instances of well established test sets of polynomial optimization problems. We describe how to design these conic constraints and their performance with respect to each other and with respect to the standard RLT relaxations. Our first finding is that the different variants of nonlinear constraints (second-order cone and semidefinite) are the best performing ones in around $50\%$ of the instances. Additionally, we present a machine learning approach to decide on the most suitable constraints to add for a given instance. The computational results show that the machine learning approach significantly outperforms each and every one of the nine individual approaches.

The use of machine learning techniques to improve the performance of branch-and-bound optimization algorithms is a very active area in the context of mixed integer linear problems, but little has been done for non-linear optimization. To bridge this gap, we develop a learning framework for spatial branching and show its efficacy in the context of the Reformulation-Linearization Technique for polynomial optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Novel graph-based features are introduced, which turn out to play an important role for the learning. Experiments on different benchmark instances from the literature show that the learning-based branching rule significantly outperforms the standard rules.

A new multimodal biometric database designed and acquired within the framework of the European BioSecure Network of Excellence is presented. It is comprised of more than 600 individuals acquired simultaneously in three scenarios: 1) over the Internet, 2) in an office environment with desktop PC, and 3) in indoor/outdoor environments with mobile portable hardware. The three scenarios include a common part of audio/video data. Also, signature and fingerprint data have been acquired both with desktop PC and mobile portable hardware. Additionally, hand and iris data were acquired in the second scenario using desktop PC. Acquisition has been conducted by 11 European institutions. Additional features of the BioSecure Multimodal Database (BMDB) are: two acquisition sessions, several sensors in certain modalities, balanced gender and age distributions, multimodal realistic scenarios with simple and quick tasks per modality, cross-European diversity, availability of demographic data, and compatibility with other multimodal databases. The novel acquisition conditions of the BMDB allow us to perform new challenging research and evaluation of either monomodal or multimodal biometric systems, as in the recent BioSecure Multimodal Evaluation campaign. A description of this campaign including baseline results of individual modalities from the new database is also given. The database is expected to be available for research purposes through the BioSecure Association during 2008, Comment: Published at IEEE Transactions on Pattern Analysis and Machine Intelligence journal

One of the open issues in fingerprint verification is the lack of robustness against image-quality degradation. Poor-quality images result in spurious and missing features, thus degrading the performance of the overall system. Therefore, it is important for a fingerprint recognition system to estimate the quality and validity of the captured fingerprint images. In this work, we review existing approaches for fingerprint image-quality estimation, including the rationale behind the published measures and visual examples showing their behavior under different quality conditions. We have also tested a selection of fingerprint image-quality estimation algorithms. For the experiments, we employ the BioSec multimodal baseline corpus, which includes 19200 fingerprint images from 200 individuals acquired in two sessions with three different sensors. The behavior of the selected quality measures is compared, showing high correlation between them in most cases. The effect of low-quality samples in the verification performance is also studied for a widely available minutiae-based fingerprint matching system., Comment: Published at IEEE Transactions on Information Forensics and Security

A new multimodal biometric database, acquired in the framework of the BiosecurID project, is presented together with the description of the acquisition setup and protocol. The database includes eight unimodal biometric traits, namely: speech, iris, face (still images, videos of talking faces), handwritten signature and handwritten text (on-line dynamic signals, off-line scanned images), fingerprints (acquired with two different sensors), hand (palmprint, contour-geometry) and keystroking. The database comprises 400 subjects and presents features such as: realistic acquisition scenario, balanced gender and population distributions, availability of information about particular demographic groups (age, gender, handedness), acquisition of replay attacks for speech and keystroking, skilled forgeries for signatures, and compatibility with other existing databases. All these characteristics make it very useful in research and development of unimodal and multimodal biometric systems., Comment: Published at Pattern Analysis and Applications journal

Using the Wherl entropy, we study the delocalization in phase-space of energy eigenstates in the vicinity of avoided crossing in the Lipkin-Meshkov-Glick model. These avoided crossing, appearing at intermediate energies in a certain parameter region of the model, originate classically from pairs of trajectories lying in different phase space regions, which contrary to the low energy regime, are not connected by the discrete parity symmetry of the model. As coupling parameters are varied, a sudden increase of the Wherl entropy is observed for eigenstates close to the critical energy of the excited-state quantum phase transition (ESQPT). This allows to detect when an avoided crossing is accompanied by a superposition of the pair of classical trajectories in the Husimi functions of eigenstates. This superposition yields an enhancement of dynamical tunneling, which is observed by considering initial Bloch states that evolve partially into the partner region of the paired classical trajectories, thus breaking the quantum-classical correspondence in the evolution of observables.