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.

Skull Modularity in Neotropical Marsupials and Monkeys: Size Variation and Evolutionary Constraint and Flexibility

An organism is built through a series of contingent factors, yet it is determined by historical, physical, and developmental constraints. A constraint should not be understood as an absolute obstacle to evolution, as it may also generate new possibilities for evolutionary change. Modularity is, in this context, an important way of organizing biological information and has been recognized as a central concept in evolutionary biology bridging on developmental, genetics, morphological, biochemical, and physiological studies. In this article, we explore how modularity affects the evolution of a complex system in two mammalian lineages by analyzing correlation, variance/covariance, and residual matrices (without size variation). We use the multivariate response to selection equation to simulate the behavior of Eutheria and Metharia skulls in terms of their evolutionary flexibility and constraints. We relate these results to classical approaches based on morphological integration tests based on functional/developmental hypotheses. Eutherians (Neotropical primates) showed smaller magnitudes of integration compared with Metatheria (didelphids) and also skull modules more clearly delimited. Didelphids showed higher magnitudes of integration and their modularity is strongly influenced by within-groups size variation to a degree that evolutionary responses are basically aligned with size variation. Primates still have a good portion of the total variation based on size; however, their enhanced modularization allows a broader spectrum of responses, more similar to the selection gradients applied (enhanced flexibility). Without size variation, both groups become much more similar in terms of modularity patterns and magnitudes and, consequently, in their evolutionary flexibility. J. Exp. Zool. (Mol. Dev. Evol.) 314B:663-683, 2010. (C) 2010 Wiley-Liss, Inc.

Perinatal salt restriction: A new pathway to programming adiposity indices in adult female Wistar rats

Low birth weight has been associated with increased obesity in adulthood. It has been shown that dietary salt restriction during intrauterine life induces low birth weight and insulin resistance in adult Wistar rats. The present study had a two-fold objective: to evaluate the effects that low salt intake during pregnancy and lactation has on the amount and distribution of adipose tissue; and to determine whether the phenotypic changes in fat mass in this model are associated with alterations in the activity of the renin-angiotensin system. Maternal salt restriction was found to reduce birth weight in male and female offspring. In adulthood, the female offspring of dams fed the low-salt diet presented higher adiposity indices than those seen in the offspring of dams fed a normal-salt diet. This was attributed to the fact that adipose tissue mass (retroperitoneal but not gonadal, mesenteric or inguinal) was greater in those rats than in the offspring of dams fed a normal diet. The adult offspring of dams fed the low-salt diet, compared to those dams fed a normal-salt diet, presented the following: plasma leptin levels higher in males and lower in females; plasma renin activity higher in males but not in females; and no differences in body weight, mean arterial blood pressure or serum angiotensin-converting enzyme activity. Therefore, low salt intake during pregnancy might lead to the programming of obesity in adult female offspring. (c) 2009 Elsevier Inc. All rights reserved.

An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance. (C) 2008 Elsevier B.V. All rights reserved.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

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.

Outer Trust-Region Method for Constrained Optimization

Given an algorithm A for solving some mathematical problem based on the iterative solution of simpler subproblems, an outer trust-region (OTR) modification of A is the result of adding a trust-region constraint to each subproblem. The trust-region size is adaptively updated according to the behavior of crucial variables. The new subproblems should not be more complex than the original ones, and the convergence properties of the OTR algorithm should be the same as those of Algorithm A. In the present work, the OTR approach is exploited in connection with the ""greediness phenomenon"" of nonlinear programming. Convergence results for an OTR version of an augmented Lagrangian method for nonconvex constrained optimization are proved, and numerical experiments are presented.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. 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.