A GRADIENT-LIKE NONAUTONOMOUS EVOLUTION PROCESS

In this paper we consider a dissipative damped wave equation with nonautonomous damping of the form u(tt) + beta(t)u(t) - Delta u + f(u) (1) in a bounded smooth domain Omega subset of R(n) with Dirichlet boundary conditions, where f is a dissipative smooth nonlinearity and the damping beta : R -> (0, infinity) is a suitable function. We prove, if (1) has finitely many equilibria, that all global bounded solutions of (1) are backwards and forwards asymptotic to equilibria. Thus, we give a class of examples of nonautonomous evolution processes for which the structure of the pullback attractors is well understood. That complements the results of [Carvalho & Langa, 2009] on characterization of attractors, where it was shown that a small nonautonomous perturbation of an autonomous gradient-like evolution process is also gradient-like. Note that the evolution process associated to (1) is not a small nonautonomous perturbation of any autonomous gradient-like evolution processes. Moreover, we are also able to prove that the pullback attractor for (1) is also a forwards attractor and that the rate of attraction is exponential.

An extension of the concept of gradient semigroups which is stable under perturbation

In this article we introduce the concept of a gradient-like nonlinear semigroup as an intermediate concept between a gradient nonlinear semigroup (those possessing a Lyapunov function, see [J.K. Hale, Asymptotic Behavior of Dissipative Systems, Math. Surveys Monogr., vol. 25, Amer. Math. Soc., 1989]) and a nonlinear semigroup possessing a gradient-like attractor. We prove that a perturbation of a gradient-like nonlinear semigroup remains a gradient-like nonlinear semigroup. Moreover, for non-autonomous dynamical systems we introduce the concept of a gradient-like evolution process and prove that a non-autonomous perturbation of a gradient-like nonlinear semigroup is a gradient-like evolution process. For gradient-like nonlinear semigroups and evolution processes, we prove continuity, characterization and (pullback and forwards) exponential attraction of their attractors under perturbation extending the results of [A.N. Carvalho, J.A. Langa, J.C. Robinson, A. Suarez, Characterization of non-autonomous attractors of a perturbed gradient system, J. Differential Equations 236 (2007) 570-603] on characterization and of [A.V. Babin, M.I. Vishik, Attractors in Evolutionary Equations, Stud. Math. Appl.. vol. 25, North-Holland, Amsterdam, 1992] on exponential attraction. (C) 2009 Elsevier Inc. All rights reserved.

Stability of gradient semigroups under perturbations

In this paper we prove that gradient-like semigroups (in the sense of Carvalho and Langa (2009 J. Diff. Eqns 246 2646-68)) are gradient semigroups (possess a Lyapunov function). This is primarily done to provide conditions under which gradient semigroups, in a general metric space, are stable under perturbation exploiting the known fact (see Carvalho and Langa (2009 J. Diff. Eqns 246 2646-68)) that gradient-like semigroups are stable under perturbation. The results presented here were motivated by the work carried out in Conley (1978 Isolated Invariant Sets and the Morse Index (CBMS Regional Conference Series in Mathematics vol 38) (RI: American Mathematical Society Providence)) for groups in compact metric spaces (see also Rybakowski (1987 The Homotopy Index and Partial Differential Equations (Universitext) (Berlin: Springer)) for the Morse decomposition of an invariant set for a semigroup on a compact metric space).

Reduced gradient method combined with augmented Lagrangian and barrier for the optimal power flow problem

A new approach for solving the optimal power flow (OPF) problem is established by combining the reduced gradient method and the augmented Lagrangian method with barriers and exploring specific characteristics of the relations between the variables of the OPF problem. Computer simulations on IEEE 14-bus and IEEE 30-bus test systems illustrate the method. (c) 2007 Elsevier Inc. All rights reserved.

Optimal subdivision of land in agrarian reform projects: an analysis using genetic algorithms

J.A. Ferreira Neto, E.C. Santos Junior, U. Fra Paleo, D. Miranda Barros, and M.C.O. Moreira. 2011. Optimal subdivision of land in agrarian reform projects: an analysis using genetic algorithms. Cien. Inv. Agr. 38(2): 169-178. The objective of this manuscript is to develop a new procedure to achieve optimal land subdivision using genetic algorithms (GA). The genetic algorithm was tested in the rural settlement of Veredas, located in Minas Gerais, Brazil. This implementation was based on the land aptitude and its productivity index. The sequence of tests in the study was carried out in two areas with eight different agricultural aptitude classes, including one area of 391.88 ha subdivided into 12 lots and another of 404.1763 ha subdivided into 14 lots. The effectiveness of the method was measured using the shunting line standard value of a parceled area lot`s productivity index. To evaluate each parameter, a sequence of 15 calculations was performed to record the best individual fitness average (MMI) found for each parameter variation. The best parameter combination found in testing and used to generate the new parceling with the GA was the following: 320 as the generation number, a population of 40 individuals, 0.8 mutation tax, and a 0.3 renewal tax. The solution generated rather homogeneous lots in terms of productive capacity.

Patterns of water and heat flux across a biome gradient from tropical forest to savanna in Brazil

We investigated the seasonal patterns of water vapor and sensible heat flux along a tropical biome gradient from forest to savanna. We analyzed data from a network of flux towers in Brazil that were operated within the Large-Scale Biosphere-Atmosphere Experiment in Amazonia (LBA). These tower sites included tropical humid and semideciduous forest, transitional forest, floodplain (with physiognomies of cerrado), and cerrado sensu stricto. The mean annual sensible heat flux at all sites ranged from 20 to 38 Wm(-2), and was generally reduced in the wet season and increased in the late dry season, coincident with seasonal variations of net radiation and soil moisture. The sites were easily divisible into two functional groups based on the seasonality of evaporation: tropical forest and savanna. At sites with an annual precipitation above 1900 mm and a dry season length less than 4 months (Manaus, Santarem and Rondonia), evaporation rates increased in the dry season, coincident with increased radiation. Evaporation rates were as high as 4.0 mm d(-1) in these evergreen or semidecidous forests. In contrast, ecosystems with precipitation less than 1700 mm and a longer dry season (Mato Grosso, Tocantins and Sao Paulo) showed clear evidence of reduced evaporation in the dry season. Evaporation rates were as low as 2.5 mm d(-1) in the transitional forests and 1 mm d(-1) in the cerrado. The controls on evapotranspiration seasonality changed along the biome gradient, with evaporative demand (especially net radiation) playing a more important role in the wetter forests, and soil moisture playing a more important role in the drier savannah sites.

Extending the use of canonical and microcanonical Monte Carlo algorithms to spin models

We describe the canonical and microcanonical Monte Carlo algorithms for different systems that can be described by spin models. Sites of the lattice, chosen at random, interchange their spin values, provided they are different. The canonical ensemble is generated by performing exchanges according to the Metropolis prescription whereas in the microcanonical ensemble, exchanges are performed as long as the total energy remains constant. A systematic finite size analysis of intensive quantities and a comparison with results obtained from distinct ensembles are performed and the quality of results reveal that the present approach may be an useful tool for the study of phase transitions, specially first-order transitions. (C) 2009 Elsevier B.V. All rights reserved.

Role of Surfactants in Carbon Nanotubes Density Gradient Separation

Several strategies aimed at sorting single-walled carbon nanotubes (SWNT) by diameter and/or electronic structure have been developed in recent years. A nondestructive sorting method was recently proposed in which nanotube bundles are dispersed in water-surfactant solutions and submitted to ultracentrifugation in a density gradient. By this method, SWNTs of different diameters are distributed according to their densities along the centrifuge tube. A mixture of two anionic amphiphiles, namely sodium dodecylsulfate (SIDS) and sodium cholate (SC), presented the best performance in discriminating nanotubes by diameter. We present molecular dynamics studies of the water-surfactant-SWNT system. The simulations revealed one aspect of the discriminating power of surfactants: they can actually be attracted toward the interior of the nanotube cage. The binding energies of SDS and SC on the outer nanotube surface are very similar and depend weakly on diameter. The binding inside the tubes, on the contrary, is strongly diameter dependent: SDS fits best inside tubes with diameters ranging from 8 to 9 angstrom, while SC is best accommodated in larger tubes, with diameters in the range 10.5-12 angstrom. The dynamics at room temperature showed that, as the amphiphile moves to the hollow cage, water molecules are dragged together, thereby promoting the nanotube filling. The resulting densities of filled SWNT are in agreement with measured densities.

A novel MAP-MRF approach for multispectral image contextual classification using combination of suboptimal iterative algorithms

In this paper we present a novel approach for multispectral image contextual classification by combining iterative combinatorial optimization algorithms. The pixel-wise decision rule is defined using a Bayesian approach to combine two MRF models: a Gaussian Markov Random Field (GMRF) for the observations (likelihood) and a Potts model for the a priori knowledge, to regularize the solution in the presence of noisy data. Hence, the classification problem is stated according to a Maximum a Posteriori (MAP) framework. In order to approximate the MAP solution we apply several combinatorial optimization methods using multiple simultaneous initializations, making the solution less sensitive to the initial conditions and reducing both computational cost and time in comparison to Simulated Annealing, often unfeasible in many real image processing applications. Markov Random Field model parameters are estimated by Maximum Pseudo-Likelihood (MPL) approach, avoiding manual adjustments in the choice of the regularization parameters. Asymptotic evaluations assess the accuracy of the proposed parameter estimation procedure. To test and evaluate the proposed classification method, we adopt metrics for quantitative performance assessment (Cohen`s Kappa coefficient), allowing a robust and accurate statistical analysis. The obtained results clearly show that combining sub-optimal contextual algorithms significantly improves the classification performance, indicating the effectiveness of the proposed methodology. (C) 2010 Elsevier B.V. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

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.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. 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|.

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.

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