Using sentinels to detect intersections of convex and nonconvex polygons

We describe finite sets of points, called sentinels, which allow us to decide if isometric copies of polygons, convex or not, intersect. As an example of the applicability of the concept of sentinel, we explain how they can be used to formulate an algorithm based on the optimization of differentiable models to pack polygons in convex sets. Mathematical subject classification: 90C53, 65K05.

ON THE THREE-DIMENSIONAL BLASCHKE-LEBESGUE PROBLEM

The width of a closed convex subset of n-dimensional Euclidean space is the distance between two parallel supporting hyperplanes. The Blaschke-Lebesgue problem consists of minimizing the volume in the class of convex sets of fixed constant width and is still open in dimension n >= 3. In this paper we describe a necessary condition that the minimizer of the Blaschke-Lebesgue must satisfy in dimension n = 3: we prove that the smooth components of the boundary of the minimizer have their smaller principal curvature constant and therefore are either spherical caps or pieces of tubes (canal surfaces).

Second-order negative-curvature methods for box-constrained and general constrained optimization

A Nonlinear Programming algorithm that converges to second-order stationary points is introduced in this paper. The main tool is a second-order negative-curvature method for box-constrained minimization of a certain class of functions that do not possess continuous second derivatives. This method is used to define an Augmented Lagrangian algorithm of PHR (Powell-Hestenes-Rockafellar) type. Convergence proofs under weak constraint qualifications are given. Numerical examples showing that the new method converges to second-order stationary points in situations in which first-order methods fail are exhibited.

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization

Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

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.

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|.

Increased Levels of NOTCH1, NF-kappa B, and Other Interconnected Transcription Factors Characterize Primitive Sets of Hematopoietic Stem Cells

As previously shown, higher levels of NOTCH1 and increased NF-kappa B signaling is a distinctive feature of the more primitive umbilical cord blood (UCB) CD34+ hematopoietic stem cells (HSCs), as compared to bone marrow ( BM). Differences between BM and UCB cell composition also account for this finding. The CD133 marker defines a more primitive cell subset among CD34+ HSC with a proposed hemangioblast potential. To further evaluate the molecular basis related to the more primitive characteristics of UCB and CD133+ HSC, immunomagnetically purified human CD34+ and CD133+ cells from BM and UCB were used on gene expression microarrays studies. UCB CD34+ cells contained a significantly higher proportion of CD133+ cells than BM (70% and 40%, respectively). Cluster analysis showed that BM CD133+ cells grouped with the UCB cells ( CD133+ and CD34+) rather than to BM CD34+ cells. Compared with CD34+ cells, CD133+ had a higher expression of many transcription factors (TFs). Promoter analysis on all these TF genes revealed a significantly higher frequency ( than expected by chance) of NF-kappa B-binding sites (BS), including potentially novel NF-kappa B targets such as RUNX1, GATA3, and USF1. Selected transcripts of TF related to primitive hematopoiesis and self-renewal, such as RUNX1, GATA3, USF1, TAL1, HOXA9, HOXB4, NOTCH1, RELB, and NFKB2 were evaluated by real-time PCR and were all significantly positively correlated. Taken together, our data indicate the existence of an interconnected transcriptional network characterized by higher levels of NOTCH1, NF-kappa B, and other important TFs on more primitive HSC sets.

INFERENCE FOR EIGENVALUES AND EIGENVECTORS OF GAUSSIAN SYMMETRIC MATRICES

This article presents maximum likelihood estimators (MLEs) and log-likelihood ratio (LLR) tests for the eigenvalues and eigenvectors of Gaussian random symmetric matrices of arbitrary dimension, where the observations are independent repeated samples from one or two populations. These inference problems are relevant in the analysis of diffusion tensor imaging data and polarized cosmic background radiation data, where the observations are, respectively, 3 x 3 and 2 x 2 symmetric positive definite matrices. The parameter sets involved in the inference problems for eigenvalues and eigenvectors are subsets of Euclidean space that are either affine subspaces, embedded submanifolds that are invariant under orthogonal transformations or polyhedral convex cones. We show that for a class of sets that includes the ones considered in this paper, the MLEs of the mean parameter do not depend on the covariance parameters if and only if the covariance structure is orthogonally invariant. Closed-form expressions for the MLEs and the associated LLRs are derived for this covariance structure.

Ethanol electrooxidation onto stepped surfaces modified by Ru deposition: electrochemical and spectroscopic studies

Oxidation of ethanol on ruthenium-modified Pt(775) and Pt(332) stepped electrodes has been studied using electrochemical and FTIR techniques. It has been found that the oxidation of ethanol on these electrodes takes place preferentially on the step sites yielding CO(2) as the major final product. The cleavage of the C-C bond, which is the required step to yield CO(2), occurs only on this type of site. The presence of low ruthenium coverages on the step sites promotes the complete oxidation of ethanol since it facilitates the oxidation of CO formed on the step from the cleavage of the C-C bond. However, high ruthenium coverages have an important inhibiting effect since the adatoms block the step sites, which are required for the cleavage of the C-C bond. Under these conditions, the oxidation current diminishes and the major product in the oxidation process is acetic acid, which is the product formed preferentially on the (111) terrace sites.

Extremal problems on sum-free sets and coverings in tridimensional spaces

Given a prime power q, define c (q) as the minimum cardinality of a subset H of F 3 q which satisfies the following property: every vector in this space di ff ers in at most 1 coordinate from a multiple of a vector in H. In this work, we introduce two extremal problems in combinatorial number theory aiming to discuss a known connection between the corresponding coverings and sum-free sets. Also, we provide several bounds on these maps which yield new classes of coverings, improving the previous upper bound on c (q)

An investigation of phosphate adsorption from aqueous solution onto hydrous niobium oxide prepared by co-precipitation method

The synthetic hydrous niobium oxide has been used for phosphate removal from the aqueous solutions. The kinetic data correspond very well to the pseudo second-order equation The phosphate removal tended. to increase with a decrease of pH. The equilibrium data describe very well the Langmuir isotherm. The peak appearing at 1050 cm(-1) in IR spectra after adsorption was attributed to the bending vibration of adsorbed phosphate. The adsorption capacities are high, and increased with increasing temperature. The evaluated Delta G degrees and Delta H degrees indicate the spontaneous and endothermic nature of the reactions. The adsorptions occur with increase in entropy (Delta S positive) value suggest increase in randomness at the solid-liquid interface during the adsorption. A phosphate desorbability of approximately 60% was observed with water at pH 12, which indicated a relatively strong bonding between the adsorbed phosphate and the sorptive sites on the surface of the adsorbent. (C) 2008 Elsevier B.V. All rights reserved.

Thermodynamic and kinetic investigations of phosphate adsorption onto hydrous niobium oxide prepared by homogeneous solution method

The adsorption kinetics of phosphate onto Nb(2)O(5)center dot nH(2)O was investigated at initial phosphate concentrations 10 and 50 mg L(-1). The kinetic process was described by a pseudo second-order rate model very well. The adsorption thermodynamics was carried out at 298, 308, 318, 328 and 338 K. The positive values of both Delta H and Delta S suggest an endothermic reaction and increase in randomness at the solid-liquid interface during the adsorption. Delta G values obtained were negative indicating a spontaneous adsorption process. The Langmuir model described the data better than the Freundlich isotherm model. The peak appearing at 1050 cm(-1) in IR spectra after adsorption was attributed to the bending vibration of adsorbed phosphate. The effective desorption could be achieved using water at pH 12. (C) 2010 Elsevier B.V. All rights reserved.

Adsorption kinetic, thermodynamic and desorption studies of phosphate onto hydrous niobium oxide prepared by reverse microemulsion method

A type of Nb(2)O(5)center dot 3H(2)O was synthesized and its phosphate removal potential was investigated in this study. The kinetic study, adsorption isotherm, pH effect, thermodynamic study and desorption were examined in batch experiments. The kinetic process was described by a pseudo-second-order rate model very well. The phosphate adsorption tended to increase with a decrease of pH. The adsorption data fitted well to the Langmuir model with which the maximum P adsorption capacity was estimated to be 18.36 mg-Pg(-1). The peak appearing at 1050 cm(-1) in IR spectra after adsorption was attributed to the bending vibration of adsorbed phosphate. The positive values of both Delta H degrees and Delta S degrees suggest an endothermic reaction and increase in randomness at the solid-liquid interface during the adsorption. Delta G degrees values obtained were negative indicating a spontaneous adsorption process. A phosphate desorbability of approximately 68% was observed with water at pH 12, which indicated a relatively strong bonding between the adsorbed phosphate and the sorptive sites on the surface of the adsorbent. The immobilization of phosphate probably occurs by the mechanisms of ion exchange and physicochemical attraction. Due to its high adsorption capacity, this type of hydrous niobium oxide has the potential for application to control phosphorus pollution.

Effect of pH and oxalic acid on the reduction of Fe(3+) by a biomimetic chelator and on Fe(3+) desorption/adsorption onto wood: Implications for brown-rot decay

Fenton reaction is thought to play an important role in wood degradation by brown-rot fungi. In this context, the effect of oxalic acid and pH on iron reduction by a biomimetic fungal chelator and on the adsorption/desorption of iron to/from wood was investigated. The results presented in this work indicate that at pH 2.0 and 4.5 and in the presence of oxalic acid, the phenolate chelator 2,3-dihydroxybenzoic acid (2,3-DHBA) is capable of reducing ferric iron only when the iron is complexed with oxalate to form Fe mono-oxalate (Fe(C(2)O(4))(+)). Within the pH range tested in this work, this complex formation occurs when the oxalate:Fe(3+) molar ratio is less than 20 (pH 2.0) or less than 10 (pH 4.5). When aqueous ferric iron was passed through a column packed with milled red spruce (Picea rubens) wood equilibrated at pH 2.0 and 4.5. it was observed that ferric iron binds to wood at pH 4.5 but not at pH 2.0, and the bound iron could then be released by application of oxalic acid at pH 4.5. The release of bound iron was dependent on the amount of oxalic acid applied in the column. When the amount of oxalate was at least 20-fold greater than the amount of iron bound to the wood, all bound iron was released. When Fe-oxalate complexes were applied to the milled wood column equilibrated in the pH range of 2-4.5, iron from Fe-oxalate complexes was bound to the wood only when the pH was 3.6 or higher and the oxalate:Fe(3+) molar ratio was less than 10. When 2,3-DHBA was evaluated for its ability to release iron bound to the milled wood, it was found that 2,3-DHBA possessed a greater affinity for ferric iron than the wood as 2,3-DHBA was capable of releasing the ferric iron bound to the wood in the pH range 3.6-5.5. These results further the understanding of the mechanisms employed by brown-rot fungi in wood biodegradation processes. (C) 2009 Elsevier Ltd. All rights reserved.