Proximal methods for nonlinear programming: double regularization and inexact subproblems

This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that leads to fully smooth subproblems. We first enhance the existing theory to show that our approach is globally convergent in both the primal and dual spaces when applied to convex problems. We then present an extensive computational evaluation using the CUTE test set, showing that some aspects of our approach are promising, but some are not. These conclusions in turn lead to additional computational experiments suggesting where to next focus our theoretical and computational efforts.

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.

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.

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.

QUASISTATIONARY DISTRIBUTIONS AND FLEMING-VIOT PROCESSES IN FINITE SPACES

Consider a continuous-time Markov process with transition rates matrix Q in the state space Lambda boolean OR {0}. In In the associated Fleming-Viot process N particles evolve independently in A with transition rates matrix Q until one of them attempts to jump to state 0. At this moment the particle jumps to one of the positions of the other particles, chosen uniformly at random. When Lambda is finite, we show that the empirical distribution of the particles at a fixed time converges as N -> infinity to the distribution of a single particle at the same time conditioned on not touching {0}. Furthermore, the empirical profile of the unique invariant measure for the Fleming-Viot process with N particles converges as N -> infinity to the unique quasistationary distribution of the one-particle motion. A key element of the approach is to show that the two-particle correlations are of order 1/N.

Tilt-critical algebras of tame type

Let A be a finite dimensional k-algebra over an algebraically closed field. Assume A=kQ/I where Q is a quiver without oriented cycles. We say that A is tilt-critical if it is not tilted but every proper convex subcategory of A is tilted. We describe the tilt-critical algebras which are strongly simply connected and tame.

On the Multiplicity of Orthogonal Geodesics in Riemannian Manifold With Concave Boundary. Applications to Brake Orbits and Homoclinics

Let (M, g) be a complete Riemannian Manifold, Omega subset of M an open subset whose closure is diffeomorphic to an annulus. If partial derivative Omega is smooth and it satisfies a strong concavity assumption, then it is possible to prove that there are at least two geometrically distinct geodesics in (Omega) over bar = Omega boolean OR partial derivative Omega starting orthogonally to one connected component of partial derivative Omega and arriving orthogonally onto the other one. The results given in [6] allow to obtain a proof of the existence of two distinct homoclinic orbits for an autonomous Lagrangian system emanating from a nondegenerate maximum point of the potential energy, and a proof of the existence of two distinct brake orbits for a. class of Hamiltonian systems. Under a further symmetry assumption, it is possible to show the existence of at least dim(M) pairs of geometrically distinct geodesics as above, brake orbits and homoclinics.

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.

Synthesis and Characterization of Magnetic Composites Based on Cis-Polyisoprene and CoFe(2)O(4) Nanoparticles

CoFe(2)O(4) nanoparticles were obtained by the co-precipitation method. They were further modified by the adsorption of ricinoleic acid (RA). The non-modified and modified CoFe(2)O(4)/RA nanoparticles were characterized by transmission electron microscopy (TEM), atomic force microscopy (AFM), Raman, and Fourier transform infrared (FTIR) spectroscopy. The modified particles present a mean diameter < 20 nm. The adsorption of RA on the CoFe(2)O(4) surface is characterized by the IR absorptions of the RA while in the Raman spectrum the predominant signals are those from the CoFe(2)O(4). The cis-polyisoprene (PI) composite was prepared by dissolving PI in cyclohexane followed by the addition of a magnetic fluid based on CoFe(2)O(4)/RA nanoparticles dispersed in cyclohexane. After solvent evaporation a magnetic composite was obtained and characterized by AFM, Raman, and FTIR measurements. AFM images show uniformly CoFe(2)O(4)/RA particles distributed in the PI matrix. Raman spectra obtained for the composites reveal the characteristic Raman peaks of PI and CoFe(2)O(4) nanoparticles.

Thin films of xyloglucans for BSA adsorption

In this work. XG extracted from Tamarindus indica (XGT) and Copaifera langsdorffii (XGC) seeds were deposited onto Si wafers as thin films. The characteristics of XGT and XGC adsorbed layers were compared with a commercial XG sample (TKP, Tamarind kernel powder) by ellipsometry, and atomic force microscopy (AFM). Moreover, the adsorption of oxidized derivative of XGT (To60) onto amino-terminated Si wafers and the immobilization of bovine serum albumin (BSA) onto polysaccharides covered wafers, as a function of pH, were also investigated. The XG samples presented molar ratios Glc:Xyl:Gal of 2.4:2.1:1 (XGC) 2.8: 23: 1 (XGT) and 1.91.91 (TKP). The structure of XGT and XGC was determined by O-methy alditol acetate derivatization and showed similar features, but XGC confirmed the presence of more alpha-D-Xyl branches due to more beta-D-Gal ends. XGT deposited onto Si adsorbed as fibers and small entities uniformly distributed, as evidenced by AFM, while TPK and XGC formed larger aggregates. The thickness of To60 onto amino-terminated surface was similar to that determined for XGT onto Si wafers. A maximum in the adsorbed amount of BSA occurred close to its isoelectric point (5.5). These findings indicate that XGT and To60 are potential materials for the development of biomaterials and biotechnological devices. (C) 2008 Elsevier B.V. All rights reserved.

Ex Situ Scanning Electrochemical Microscopy (SECM) Investigation of Bismuth- and Bismuth/Lead Alloy Film-Modified Gold Electrodes in Alkaline Medium

Scanning electrochemical microscopy (SECM) in feedback mode was employed to characterise the reactivity and microscopic peculiarities of bismuth and bismuth/lead alloys plated onto gold disk substrates in 0.1 molL(-1) NaOH solutions. Methyl viologen was used as redox mediator, while a platinum microelectrode was employed as the SECM tip. The metal films were electrodeposited ex situ from NaOH solutions containing either bismuth ions only or both bismuth and lead ions. Approach curves and SECM images indicated that the metal films were conductive and locally reactive with oxygen to provide Bi(3+) and Pb(2+) ions. The occurrence of the latter chemical reactions was verified by local anodic stripping voltammetry (ASV) at the substrate solution interface by using a mercury-coated platinum SECM tip. The latter types of measurements allowed also verifying that lead was not uniformly distributed onto the bismuth film electrode substrate. These findings were confirmed by scanning electron microscopy images. The surface heterogeneity produced during the metal deposition process, however, did not affect the analytical performance of the bismuth coated gold electrode in anodic stripping voltammetry for the determination of lead in alkaline media, even in aerated aqueous solutions. Under the latter conditions, stripping peak currents proportional to lead concentration with a satisfactory reproducibility (within 5% RSD) were obtained.

Electrodeposition and characterization of undoped and nitrogen-doped ZnSe films

Semiconducting films of (n-type) ZnSe and (p-type) nitrogen-doped ZnSe were electrodeposited by a linear-sweep voltammetric technique on to a substrate of fluorine-tin oxide (FM) glass ceramics. The films were characterized by scanning electron microscopy, energy-dispersive X-ray analysis and grazing-incidence X-ray diffraction. The results indicated that the material was deposited uniformly over the substrate, forming clusters when the Zn content of the bath was 0.1 mol L(-1) and a film when it was 0.2 or 0.3 mol L(-1). The effectiveness of doping the films with nitrogen by adding ammonium sulfate to the deposition solution was assessed by measuring the film-electrolyte interface capacitance (C) at various applied potentials (E(ap)) and plotting Mott-Schottky curves (C(-2) vs E(ap)), whose slope sign was used to identify p-type ZnSe. (C) 2009 Elsevier B.V. All rights reserved.