U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Minimizing the object dimensions in circle and sphere packing problems

Given a fixed set of identical or different-sized circular items, the problem we deal with consists on finding the smallest object within which the items can be packed. Circular, triangular, squared, rectangular and also strip objects are considered. Moreover, 2D and 3D problems are treated. Twice-differentiable models for all these problems are presented. A strategy to reduce the complexity of evaluating the models is employed and, as a consequence, instances with a large number of items can be considered. Numerical experiments show the flexibility and reliability of the new unified approach. (C) 2007 Elsevier Ltd. All rights reserved.

Improving ultimate convergence of an augmented Lagrangian method

Optimization methods that employ the classical Powell-Hestenes-Rockafellar augmented Lagrangian are useful tools for solving nonlinear programming problems. Their reputation decreased in the last 10 years due to the comparative success of interior-point Newtonian algorithms, which are asymptotically faster. In this research, a combination of both approaches is evaluated. The idea is to produce a competitive method, being more robust and efficient than its `pure` counterparts for critical problems. Moreover, an additional hybrid algorithm is defined, in which the interior-point method is replaced by the Newtonian resolution of a Karush-Kuhn-Tucker (KKT) system identified by the augmented Lagrangian algorithm. The software used in this work is freely available through the Tango Project web page:http://www.ime.usp.br/similar to egbirgin/tango/.

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented.

The C(K, X) spaces for compact metric spaces K and X with a uniformly convex maximal factor

In this paper, we prove that if a Banach space X contains some uniformly convex subspace in certain geometric position, then the C(K, X) spaces of all X-valued continuous functions defined on the compact metric spaces K have exactly the same isomorphism classes that the C(K) spaces. This provides a vector-valued extension of classical results of Bessaga and Pelczynski (1960) [2] and Milutin (1966) [13] on the isomorphic classification of the separable C(K) spaces. As a consequence, we show that if 1 < p < q < infinity then for every infinite countable compact metric spaces K(1), K(2), K(3) and K(4) are equivalent: (a) C(K(1), l(p)) circle plus C(K(2), l(q)) is isomorphic to C(K(3), l(p)) circle plus (K(4), l(q)). (b) C(K(1)) is isomorphic to C(K(3)) and C(K(2)) is isomorphic to C(K(4)). (C) 2011 Elsevier Inc. All rights reserved.

On Approximate KKT Condition and its Extension to Continuous Variational Inequalities

In this work, we introduce a necessary sequential Approximate-Karush-Kuhn-Tucker (AKKT) condition for a point to be a solution of a continuous variational inequality, and we prove its relation with the Approximate Gradient Projection condition (AGP) of Garciga-Otero and Svaiter. We also prove that a slight variation of the AKKT condition is sufficient for a convex problem, either for variational inequalities or optimization. Sequential necessary conditions are more suitable to iterative methods than usual punctual conditions relying on constraint qualifications. The AKKT property holds at a solution independently of the fulfillment of a constraint qualification, but when a weak one holds, we can guarantee the validity of the KKT conditions.

Optimization of the ultrasound-assisted synthesis of allyl 1-naphthyl ether using response surface methodology

Allyl 1-naphthyl ethers are useful compounds for different purposes, but reported methods to synthesize them require long reaction times. In this work, we have obtained allyl 1-naphthyl ether in good yield using ultrasonic-assisted methodology in a 1-h reaction. A central composite design was used to obtain a statistical model and a response surface (p < 0.05; R(2) = 0.970; R(adj)(2) = 0.949; R(pred)(2) = 0.818) that can predict the optimal conditions to maximize the yield, validated experimentally. (C) 2010 Elsevier B.V. All rights reserved.

Optimization of incubation time of protein Tc85 in the construction of biosensor: Is the EIS a good tool?

Electrochemical impedance spectroscopy (EIS) in pH 6.9 phosphate buffer solution was used to investigate each step of the procedure employed to modify a screen-printed electrode (SPE). The SPE was modified with self-assembled monolayers (SAMs) of cystamine (CYS, deposited from 20 mM solution), followed by glutaraldehyde (GA, 0.3 M solution). The Trypanosoma cruzi antigen was immobilized using different deposition times. The influence of incubation time (2-18 h) of protein was also investigated. The topography of modified electrode with this protein was investigated by atomic force microscopy (AFM). Interpretation of impedance data was based on physical and chemical adsorption, and degradation of the layer at high and meddle frequencies, and charge transfer reaction involving mainly the reduction of oxygen at low frequencies. EIS studies on modified electrodes with Tc85 protein immobilized for different incubation times indicated that the optimum incubation time was 6-8 h. It was demonstrated that EIS is a good technique to evaluate the different steps and the integrity of the surface modifications, and to optimize the incubation time of protein in the development of biosensors. (C) 2010 Elsevier B.V. All rights reserved.

Synthesis Optimization of Hydroxymethylnitrofurazone, an Antichagasic Candidate, Using 3(2) Factorial Design

Hydroxymethylnitrofurazone presents in vitro activity against Trypanosoma cruzi. The optimization of the synthesis of this compound was performed through a 3(2) factorial statistical design. Quadratic model produced the best response surface predicting a maximum yield (82%) close to the center design point with a seven hours reaction and a 1:1.5 (NF:K(2)CO(3)) ratio.

Optimization of a method for determination of phenolic acids in exotic fruits by capillary electrophoresis

In this work, the separation of nine phenolic acids (benzoic, caffeic, chlorogenic, p-coumaric, ferulic, gallic, protocatechuic, syringic, and vanillic acid) was approached by a 32 factorial design in electrolytes consisting of sodium tetraborate buffer(STB) in the concentration range of 10-50 mmol L(-1) and methanol in the volume percentage of 5-20%. Derringer`s desirability functions combined globally were tested as response functions. An optimal electrolyte composed by 50 mmol L(-1) tetraborate buffer at pH 9.2, and 7.5% (v/v) methanol allowed baseline resolution of all phenolic acids under investigation in less than 15 min. In order to promote sample clean up, to preconcentrate the phenolic fraction and to release esterified phenolic acids from the fruit matrix, elaborate liquid-liquid extraction procedures followed by alkaline hydrolysis were performed. The proposed methodology was fully validated (linearity from 10.0 to 100 mu g mL(-1), R(2) > 0.999: LOD and LOQ from 1.32 to 3.80 mu g mL(-1) and from 4.01 to 11.5 mu g mL(-1), respectively; intra-day precision better than 2.8% CV for migration time and 5.4% CV for peak area; inter-day precision better than 4.8% CV for migration time and 4.8-11% CV for peak area: recoveries from 81% to 115%) and applied successfully to the evaluation of phenolic contents of abiu-roxo (Chrysophyllum caimito), wild mulberry growing in Brazil (Morus nigra L.) and tree tomato (Cyphomandra betacea). Values in the range of 1.50-47.3 mu g g(-1) were found, with smaller amounts occurring as free phenolic acids. (C) 2009 Elsevier B.V. All rights reserved.

Multivariant optimization, validation, and application of capillary electrophoresis for simultaneous determination of polyphenols and phenolic acids in Brazilian wines

A method for the simultaneous determination of the stilbene resveratrol, four phenolic acids (syringic, coumaric, caffeic, and gallic acids), and five flavonoids (catechin, rutin, kaempferol, myricetin, and quercetin) in wine by CE was developed and validated. The CE electrolyte composition and instrumental conditions were optimized using 2(7-3) factorial design and response surface analysis, showing sodium tetraborate, MeOH, and their interaction as the most influential variables. The optimal electrophoretic conditions, minimizing the chromatographic resolution statistic values, consisted of 17 mmol/L sodium tetraborate with 20% methanol as electrolyte, constant voltage of 25 kV, hydrodynamic injection at 50 mbar for 3 s, and temperature of 25 degrees C. The R(2) values for linearity varied from 0.994 to 0.999; LOD and LOQ were 0.1 to 0.3 mg/L and 0.4 to 0.8 mg/L, respectively. The RSDs for migration time and peak area obtained from ten consecutive injections were less than 2% and recoveries varied from 97 to 102%. The method was applied to 23 samples of inexpensive Brazilian wines, showing wide compositional variation.

Sequential injection analysis (SIA) and response surface methodology: A versatile small volume approach for optimization of photo-Fenton processes

Optimization of photo-Fenton degradation of copper phthalocyanine blue was achieved by response surface methodology (RSM) constructed with the aid of a sequential injection analysis (SIA) system coupled to a homemade photo-reactor. Highest degradation percentage was obtained at the following conditions [H(2)O(2)]/[phthalocyanine] = 7, [H(2)O(2)]/[FeSO(4)] = 10, pH = 2.5, and stopped flow time in the photo reactor = 30 s. The SIA system was designed to prepare a monosegment containing the reagents and sample, to pump it toward the photo-reactor for the specified time and send the products to a flow-through spectrophotometer for monitoring the color reduction of the dye. Changes in parameters such as reagent molar ratios. residence time and pH were made by modifications in the software commanding the SI system, without the need for physical reconfiguration of reagents around the selection valve. The proposed procedure and system fed the statistical program with degradation data for fast construction of response surface plots. After optimization, 97% of the dye was degraded. (C) 2009 Elsevier B.V. All rights reserved.

Applying sequential injection analysis (SIA) and response surface methodology for optimization of Fenton-based processes

This work presents the use of sequential injection analysis (SIA) and the response surface methodology as a tool for optimization of Fenton-based processes. Alizarin red S dye (C.I. 58005) was used as a model compound for the anthraquinones family. whose pigments have a large use in coatings industry. The following factors were considered: [H(2)O(2)]:[Alizarin] and [H(2)O(2)]:[FeSO(4)] ratios and pH. The SIA system was designed to add reagents to the reactor and to perform on-line sampling of the reaction medium, sending the samples to a flow-through spectrophotometer for monitoring the color reduction of the dye. The proposed system fed the statistical program with degradation data for fast construction of response surface plots. After optimization, 99.7% of the dye was degraded and the TOC content was reduced to 35% of the original value. Low reagents consumption and high sampling throughput were the remarkable features of the SIA system. (C) 2008 Published by Elsevier B.V.

Determination of sorbate and benzoate in beverage samples by capillary electrophoresis - Optimization of the method with inspection of ionic mobilities

The aim of this study was to develop a fast capillary electrophoresis method for the determination of benzoate and sorbate ions in commercial beverages. In the method development the pH and constituents of the background electrolyte were selected using the effective mobility versus pH curves. As the high resolution obtained experimentally for sorbate and benzoate in the studies presented in the literature is not in agreement with that expected from the ionic mobility values published, a procedure to determine these values was carried out. The salicylate ion was used as the internal standard. The background electrolyte was composed of 25 mmol L(-1) tris(hydroxymethyl)aminomethane and 12.5 mmol L(-1) 2-hydroxyisobutyric acid, atpH 8.1.Separation was conducted in a fused-silica capillary(32 cm total length and 8.5 cm effective length, 50 mu m I.D.), with short-end injection configuration and direct UV detection at 200 nm for benzoate and salicylate and 254 nm for sorbate ions. The run time was only 28 s. A few figures of merit of the proposed method include: good linearity (R(2) > 0.999), limit of detection of 0.9 and 0.3 mg L(-1) for benzoate and sorbate, respectively, inter-day precision better than 2.7% (n =9) and recovery in the range 97.9-105%. Beverage samples were prepared by simple dilution with deionized water (1:11, v/v). Concentrations in the range of 197-401 mg L(-1) for benzoate and 28-144 mg L(-1) for sorbate were found in soft drinks and tea. (c) 2008 Elsevier B.V. All rights reserved.