Abstract: In this work, we present and analyze a numerical method for recovering a piecewise constant conductivity with multiple phases in inverse conductivity problems. Specifically, we consider two types of inverse conductivity problems: problems with boundary measurements or with internal measurements. The conductivity is assumed to be constant in each phase, and a Voronoi diagram generated by a set of sites is used to model the phases. An optimization problem with respect to the position of the sites is described to approximate the solution of the inverse problem. Combining techniques from non-smooth shape calculus and sensitivity of Voronoi diagrams, we prove shape differentiability and compute the gradient of the cost function. Two different formulas for the gradient, a volumetric and an interface one, are provided. The dependence of the reconstruction on the problem parameters, such as noise, number of sites, and initialization, is investigated through several numerical experiments.

Keywords: Inverse conductivity problems, non-smooth shape calculus, Voronoi diagrams, optimization.

Full text: [pdf]

Abstract: Sustainability has become one of the main objectives in all human activities and, in particular, in manufacturing environments. In this paper we consider the flexible job shop scheduling problem with the objective of minimizing energy consumption. As it is known that a considerable part of the energy consumption occurs when the machines are on and idle, the addressed problem includes the possibility of turning the machines off and on between processing operations. To bring the problem closer to the large variety of real-world problems it encompasses, we include two relevant factors: nonlinear routes and position-based learning effect. The treated problem is formally described through a mixed integer linear programming model. We propose constructive heuristics, two types of neighborhood with which we construct local search schemes and three metaheuristics, namely, general variable neighborhood search, greedy randomized adaptive search procedure and simulated annealing. We conduct a large number of experiments to evaluate the performance of the introduced methods, on small-sized and large-sized instances. In the large-sized instances, the general variable neighborhood search, that combines the two neighborhoods into a single method, is particularly effective. In the small-sized instances with known optimal solution, the greedy randomized adaptive search procedure finds solutions that, on average, are within 0.24\% of the optimal solution.

Keywords: energy-aware scheduling, flexible job shop, nonlinear routes, arbitrary precedence constraints, learning effect, constructive heuristics, local search, metaheuristics.

Full text: [pdf]

Abstract: In this paper we consider the minimization of the unconstrained low order-value function. We also consider the case in which the feasible region is given by a closed convex set, assuming that the projection operation is affordable. For both cases, we introduce regularized first-order algorithms and prove worst-case iteration and evaluation complexity results. Asymptotic convergence results are also presented. The proposed algorithm for the case of constraints given by an arbitrary closed convex set has the classical projected gradient method as a particular case. The algorithms are implemented and several numerical experiments illustrate their application.

Keywords: Low order-value optimization, regularized models, convex constraints, projected gradient, complexity, algorithms.

Full text: [pdf]

Abstract: In [E. G. Birgin, R. Castillo and J. M. Martínez, Computational Optimization and Applications 31, pp. 31-55, 2005], a general class of safeguarded augmented Lagrangian methods is introduced which includes a large number of different methods from the literature. Besides a numerical comparison including 65 different methods, primal-dual global convergence to a KKT point is shown under a (strong) regularity condition. In the present work, we generalize this framework by considering also classical/non-safeguarded Lagrange multipliers updates. This is done in order to give a rigorous theoretical study to the so-called hyperbolic augmented Lagrangian method, which is not safeguarded, while also including the classical Powell-Hestenes-Rockafellar augmented Lagrangian method. Our results are based on a weak regularity condition which does not require boundedness of the set of Lagrange multipliers. Somewhat surprisingly, in non-safeguarded methods, we show that the penalty parameter may be kept constant at every iteration even in the lack of convexity assumptions. Numerical experiments with all the problems in the Netlib and CUTEst collections are reported to compare and discuss the different approaches.

Keywords: Nonlinear optimization, augmented Lagrangian methods, convergence, numerical experiments.

Full text: [pdf]

Abstract: This paper considers the flexible job shop scheduling problem with nonlinear routes, a production environment with a wide range of relevant practical applications, especially in today's on-demand printing industry. In order to approximate the problem of real-world applications, we consider the influence of a position-based learning effect on the processing time of the operations. In the present work, we are concerned with the development of effective and efficient methods for its solution. For this purpose, a local search method and four trajectory metaheuristics are considered. In the local search, we show that the classical strategy of reallocating only operations that are part of the critical path may miss better quality neighbors, as opposed to what happens in the case where there is no learning effect. Consequently, we analyze an alternative type of neighborhood reduction that eliminates only neighbors that are not better than the current solution. In addition, we propose a neighborhood reduction and experimentally verify that it significantly reduces the size of the neighborhood, thereby increasing efficiency, with minimal loss of effectiveness. Extensive numerical experiments are performed. Statistical tests confirm that tabu search based on the reduced neighborhood, when applied to large-sized instances, outperforms the other three metaheuristics, namely iterated local search, greedy randomized adaptive search, and simulated annealing. Experiments on classical instances without sequencing flexibility show that the introduced methods also stand out in relation to methods from the literature. All methods, instances, and solutions are freely available.

Keywords: Scheduling, flexible job shop, routing flexibility, nonlinear routes, position-based learning effect, trajectory metaheuristics.

Full text: [pdf]

Abstract: This paper addresses the flexible job shop scheduling problem with nonlinear routes and position-based learning effect. In this variant of the flexible job shop scheduling problem, precedence constraints of the operations constituting a job are given by an arbitrary directed acyclic graph, in opposition to the classical case in which a total order is imposed. Additionally, it is assumed that the processing time of an operation in a machine is subject to a learning process such that the larger the position of the operation in the machine, the faster the operation is processed. Mixed integer programming and constraint programming models are presented and compared in the present work. In addition, constructive heuristics are introduced to provide an initial solution to the models' solvers. Sets of benchmark instances are also introduced. The problem considered corresponds to modern problems of great relevance in the printing industry. The models and instances presented are intended to support the development of new heuristic and metaheuristics methods for this problem.

Keywords: Flexible job shop scheduling problem, nonlinear routes, learning effect, models, instances, constructive heuristics.

Full text: [pdf]

Abstract: This paper addresses the issue of river level prediction through the use of polynomial regression models, employing solely elevation data and inflow forecasts. A variety of models are considered, including an approximation of elevations by a quadratic function of inlet discharge and position. Additionally, a novel approach founded upon the notion of virtual stations is introduced. It is demonstrated that when a station possesses an adequate quantity of surface elevation data, the elevations at that station can be accurately predicted by linear, quadratic, or cubic models as a function of inlet discharge. In the event that elevation data are not concentrated at a finite number of stations, the method of "virtual stations" is introduced. This method entails the establishment of new stations at strategically selected locations, for which virtual elevation data are derived from the existing stations. An algorithm is provided for the determination of the positions where the virtual stations should be located. Arguments are presented to explain why this procedure produces adequate predictions of surface elevations, but is unlikely to be as efficient in predicting flow rates. The results of comprehensive numerical experiments demonstrate the potential utility of this proposal as a tool for making predictions when the physical characteristics of the river are uncertain.

Keywords: Elevation predictions, natural rivers, Saint-Venant equations, parameter estimation.

Full text: [pdf]

Abstract: Minimization of the order-value function is part of a large family of problems involving functions whose value is calculated by sorting values from a set or subset of other functions. The order-value function has as particular cases the minimum and maximum functions of a set of functions and is well suited for applications involving robust estimation. In this paper, a first order method with quadratic regularization to solve the problem of minimizing the order-value function is proposed. An optimality condition for the problem and theoretical results of iteration complexity and evaluation complexity for the proposed method are presented. The applicability of the problem and method to a parameter estimation problem with outliers is illustrated.

Keywords: Order-value optimization, regularized models, complexity, algorithms, applications.

Full text: [pdf]

Abstract: Spectral residual methods are powerful tools for solving nonlinear systems of equations without derivatives. In a recent paper, it was shown that an acceleration technique based on the Sequential Secant Method can greatly improve its efficiency and robustness. In the present work, an R implementation of the method is presented. Numerical experiments with a widely used test bed compares the presented approach with its plain (i.e. non-accelerated) version that makes part of the R package BB. Additional numerical experiments compare the proposed method with NITSOL, a state-of-the-art solver for nonlinear systems. The comparison shows that the acceleration process greatly improves the robustness of its counterpart included in the existent R package. As a by-product, an interface is provided between R and the consolidated CUTEst collection, which contains over a thousand nonlinear programming problems of all types and represents a standard for evaluating the performance of optimization methods.

Keywords: Nonlinear systems, derivative-free, sequential residual methods, sequential secant approach, acceleration, numerical experiments.

Full text: [pdf]

Abstract: This paper aims to give a brief introduction to the concept of computational complexity in the context of continuous (nonconvex) nonlinear optimization.

Full text: [pdf]

Abstract: At each iteration of the Safeguarded Augmented Lagrangian algorithm Algencan, a bound-constrained subproblem consisting of the minimization of the Powell-Hestenes-Rockafellar augmented Lagrangian function is considered, for which a minimizer with tolerance tending to zero is sought. More precisely, a point that satisfies a subproblem first-order necessary optimality condition with tolerance tending to zero is required. In this work, based on the success of scaled stopping criteria in constrained optimization, we propose a scaled stopping criterion for the subproblems of Algencan. The scaling is done with the maximum absolute value of the first-order Lagrange multipliers approximation, whenever it is larger than one. The difference between the convergence theory of the scaled and non-scaled versions of Algencan is discussed and extensive numerical experiments are provided.

Keywords: Nonlinear optimization, augmented Lagrangian methods, subproblems, scaled stopping criteria, convergence.

Full text: [pdf]

Abstract: In this paper we propose and analyze a numerical method for the recovery of a piecewise constant parameter with multiple phases in the inverse potential problem. The potential is assumed to be constant in each phase, and the phases are modeled by a Voronoi diagram generated by a set of sites, which are used as control parameters. We first reformulate the inverse problem as an optimization problem with respect to the position of the sites. Combining techniques of non-smooth shape calculus and sensitivity of Voronoi diagrams, we are able to compute the gradient of the cost function, under standard non-degeneracy conditions of the diagram. We provide two different formulas for the gradient, a volumetric and an interface one, which are compared in numerical experiments. We provide several numerical experiments to investigate the dependence of the reconstruction on the problem parameters, such as noise, number of sites and initialization.

Keywords: Inverse potential problem, non-smooth shape calculus, Voronoi diagrams, optimization.

Full text: [pdf]

Abstract: The problem of covering a two-dimensional bounded set with a fixed number of minimum-radius identical balls is studied in the present work. An asymptotic expansion and bounds on the optimal radius as the number of balls goes to infinity are obtained for a certain class of nonsmooth domains. The proof is based on the approximation of the set to be covered by hexagonal honeycombs, and on the thinnest covering property of the regular hexagonal lattice arrangement in the whole plane. The dependence of the optimal radius on the number of balls is also investigated numerically using a shape optimization approach, and theoretical and numerical convergence rates are compared. An initial point construction strategy is introduced which, in the context of a multi-start method, finds good quality solutions to the problem under consideration. Extensive numerical experiments with a variety of polygonal regions and regular polygons illustrate the introduced approach.

Keywords: Covering with balls, asymptotic bounds, shape optimization, numerical optimization.

Full text: [pdf]

Abstract: This paper concerns the prediction of flows in open channels. For this purpose, models based on partial differential equations are usually employed. Such models require the estimation of constitutive parameters based on available data. In this way, the solution of differential equations produces predictions of the flux evolution. In this research, we consider that most natural channels are not well represented by deterministic models for different reasons. Therefore, we propose to estimate parameters using stochastic variations of the original models. There are two types of parameters to be estimated: constitutive parameters (such as roughness coefficients) and the parameters that define the stochastic variations (usually, dispersion parameters). Both types of estimations are computed using the maximum likelihood principle, which determines the objective function to be employed. After obtaining parameter estimations, due to the random essence of the stochastic models, we are able to produce predictions with appropriate probabilistic margins of the flux behavior in times or places where observations were not available.

Keywords: Decision-making, stochastic processes, partial differential modeling, Manning's coefficient, hydraulic models.

Full text: [pdf]

Abstract: An optimization-based tool for flow predictions in natural rivers is introduced assuming that some physical characteristics of a river within a spatial-time domain $[x_{\min}, x_{\max}] \times [t_{\min}, t_{\mathrm{today}}]$ are known. In particular, it is assumed that the bed elevation and width of the river are known at a finite number of stations in $[x_{\min}, x_{\max}]$ and that the flow-rate at $x=x_{\min}$ is known for a finite number of time instants in $[t_{\min},t_{\mathrm{today}}]$. Using these data, given $t_{\mathrm{future}} > t_{\mathrm{today}}$ and a forecast of the flow-rate at $x=x_{\min}$ and $t=t_{\mathrm{future}}$, a regression-based algorithm informed by partial differential equations produces predictions for all state variables (water elevation, depth, transversal wetted area, and flow-rate) for all $x \in [x_{\min}, x_{\max}]$ and $t=t_{\mathrm{future}}$. The algorithm proceeds by solving a constrained optimization problem that takes into account the available data and the fulfillment of Saint-Venant equations for one-dimensional channels. The effectiveness of this approach is corroborated with flow predictions of a natural river.

Keywords: Flow predictions in natural rivers, Saint-Venant equations, constrained optimization, algorithms.

Full text: [pdf]

Abstract: Minimization diagrams encompass a large class of diagrams of interest in the literature, such as generalized Voronoi diagrams. We develop an abstract perturbation theory and perform a sensitivity analysis for functions depending on sets defined through intersections of smooth sets, and formulate precise conditions to avoid singular situations. This allows us to define a general framework for solving optimization problems depending on minimization diagrams. The particular case of Voronoi diagrams is discussed to illustrate the general theory. A variety of numerical experiments is presented. The experiments include constructing Voronoi diagrams with cells of equal size, cells satisfying conditions on the relative size of their edges or their internal angles, cells with the midpoints of pairs of Voronoi and Delaunay edges as close as possible, or cells of varying sizes governed by a given function. Overall, the experiments show that the proposed methodology allows the construction of customized Voronoi diagrams using off-the-shelf well-established optimization algorithms.

Keywords: Minimization diagrams, generalized Voronoi diagrams, nonsmooth shape optimization.

Full text: [pdf]

Abstract: This paper addresses an integrated lot-sizing and scheduling problem in the industry of consumer goods for personal care, a very competitive market in which the good customer service level and the cost management show up in the competition for the clients. In this research, a complex operational environment composed of unrelated parallel machines with limited production capacity and sequence-dependent setup times and costs is studied. There is also a limited finished-goods storage capacity, a characteristic not found in the literature. Backordering is allowed but it is extremely undesirable. The problem is described through a mixed integer linear programming formulation. Since the problem is NP-hard, relax-and-fix heuristics with hybrid partitioning strategies are investigated. Computational experiments with randomly generated and also with real-world instances are presented. The results show the efficacy and efficiency of the proposed approaches. Compared to current solutions used by the company, the best proposed strategies yield results with substantially lower costs, primarily from the reduction in inventory levels and better allocation of production batches on the machines.

Keywords: Lot sizing and scheduling, mixed integer linear programming models, relax-and-fix, real-world instances.

Full text: [pdf]

Abstract: In [E. G. Birgin, O. C. Romão, and D. P. Ronconi, The multi-period two-dimensional non-guillotine cutting stock problem with usable leftovers, International Transactions in Operational Research 27(3), 1392-1418, 2020] the multi-period two-dimensional non-guillotine cutting stock problem with usable leftovers was introduced. At each decision instant, the problem consists in determining a cutting pattern for a set of ordered items using a set of objects that can be purchased or can be leftovers of previous periods; the goal being the minimization of the overall cost of the objects up to the considered time horizon. Among solutions with minimum cost, a solution that maximizes the value of the leftovers at the end of the considered horizon is sought. A forward-looking matheuristic approach that applies to this problem is introduced in the present work. At each decision instant, the objects and the cutting pattern that will be used is determined, taking into account the impact of this decision in future states of the system. More specifically, for each potentially used object, an attempt is made to estimate the utilization rate of its leftovers and thereby determine whether the object should be used or not. The approach's performance is compared to the performance of a myopic technique. Numerical experiments show the efficacy of the proposed approach.

Keywords: Two-dimensional cutting stock with usable leftovers, non-guillotine cutting and packing, multi-period scenario, forward-looking or looking-ahead approach, matheuristic.

Full text: [pdf]

Abstract: The problem of minimizing the first eigenvalue of the Dirichlet Laplacian with respect to a union of $m$ balls with fixed identical radii and variable centers in the plane is investigated in the present work. The existence of a minimizer is shown and the shape sensitivity analysis of the eigenvalue with respect to the centers' positions is presented. With this tool, the derivative of the eigenvalue is computed and used in a numerical algorithm to determine candidates for minimizers. Candidates are also constructed by hand based on regular polygons. Numerical solutions contribute in at least three aspects. They corroborate the idea that some of the candidates based on regular polygons might be optimal. They also suggest alternative regular patterns that improve solutions associated with regular polygons. Lastly and most importantly, they delivered better quality solutions that do not follow any apparent pattern. Overall, for low values of $m$, candidates for minimizers of the eigenvalue are proposed and their geometrical properties as well as the appearance of regular patterns formed by the centers are discussed.

Keywords: Shape optimization, Dirichlet Laplacian eigenvalue, numerical optimization.

Full text: [pdf]

Abstract: Sequential Residual Methods try to solve nonlinear systems of equations $F(x)=0$ by iteratively updating the current approximate solution along a residual-related direction. Therefore, memory requirements are minimal and, consequently, these methods are attractive for solving large-scale nonlinear systems. However, the convergence of these algorithms may be slow in critical cases; therefore, acceleration procedures are welcome. Anderson-like accelerations are widely used in electronic structure calculations to improve a fixed point algorithm for finding Self Consistent Field (SCF) solutions of Hartree-Fock models. In this paper, it is showed how to apply this type of acceleration to Sequential Residual Methods. The performance of the resulting algorithm is illustrated by applying it to the solution of very large problems coming from the discretization of partial differential equations.

Keywords: Nonlinear systems of equations, Sequential Residual Methods, acceleration, large-scale problems.

Full text: [pdf]

Abstract: Coordinate descent methods with high-order regularized models for box-constrained minimization are introduced. High-order stationarity asymptotic convergence and first-order stationarity worst-case evaluation complexity bounds are established. The computer work that is necessary for obtaining first-order $\varepsilon$-stationarity with respect to the variables of each coordinate-descent block is $O(\varepsilon^{-(p+1)/p})$ whereas the computer work for getting first-order $\varepsilon$-stationarity with respect to all the variables simultaneously is $O(\varepsilon^{-(p+1)})$. Numerical examples involving multidimensional scaling problems are presented. The numerical performance of the methods is enhanced by means of coordinate-descent strategies for choosing initial points.

Keywords: Coordinate descent methods, bound-constrained minimization, worst-case evaluation complexity.

Full text: [pdf]

Abstract: The complexity of solving feasibility problems is considered in this work. It is assumed that the constraints that define the problem can be divided into two sets, namely, expensive and cheap constraints. It is also assumed that the set of solutions of the cheap constraints is non-empty and bounded and that minimizing a quadratic function subject to the cheap constraints is an affordable task. At each iteration, the introduced method minimizes a two-norm regularized quadratic approximation of the sum of squares of the expensive constraints subject to the cheap constraints. Under a H\"older continuity property with constant $\beta \in (0,1]$ on the gradients of the expensive constraints, it is shown that finding a feasible point with precision~$\varepsilon > 0$ or an infeasible point that is stationary with tolerance~$\gamma > 0$ of minimizing the Euclidean norm of the expensive constraints residual subject to the cheap constraints has iterations complexity~$O\left(|\log(\varepsilon)| \; \gamma^{-(1+\beta)/\beta} \; \varepsilon^{(\beta-1)/(2\beta)}\right)$ and evaluations complexity (of the expensive constraints) $O\left(|\log(\varepsilon)|\left[ \gamma^{-(1+\beta)/\beta} \varepsilon^{(\beta-1)/(2\beta)}+ ((1-\beta)/\beta) | \log(\gamma \sqrt{\varepsilon})| \right] \right)$. When the gradients of the expensive constraints satisfy a Lipschitz condition, both complexities reduce to $O(|\log(\varepsilon)| \gamma^{-2})$. Still under the H\"older continuity property on the gradients of the expensive constraints, and under a stronger regularity assumption with constant~$\kappa$, that avoids KKT points of minimizing the sum of squares of the expensive constraints subject to the cheap constraints of being infeasible, the iterations complexity is shown to be $O\left(|\log(\varepsilon)| \; \kappa^{-(1+\beta)/\beta} \; \varepsilon^{(\beta-1)/(2\beta)}\right)$ while the evaluation complexity is given by $O\left(|\log(\varepsilon)|\left[ \kappa^{-(1+\beta)/\beta} \varepsilon^{(\beta-1)/(2\beta)}+ ((1-\beta)/\beta) |\log(\kappa \sqrt{\varepsilon})| \right] \right)$. When the gradients of the expensive constraints satisfy a Lipschitz condition, both complexities reduce to $O(|\log(\varepsilon)| \kappa^{-2})$. The results introduced in the present work complement, by analyzing the case $p=1$, the results obtained for $p$ even in [C. Cartis, N. I. M. Gould, and Ph. L. Toint, Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models, Technical Report NA 15-17, University of Oxford, 2015], where~$p$ is the order of the underlying $(p+1)$-regularized Taylor's model of the sum of squares of the expensive constraints.

Keywords: Complexity, feasibility problem, first order methods.

Full text: [pdf]

Abstract: At each iteration of a Block Coordinate Descent method one minimizes an approximation of the objective function with respect to a generally small set of variables subject to constraints in which these variables are involved. The unconstrained case and the case in which the constraints are simple were analyzed in the recent literature. In this paper we address the problem in which block constraints are not simple and, moreover, the case in which they are not defined by global sets of equations and inequations. A general algorithm that minimizes quadratic models with quadratric regularization over blocks of variables is defined and convergence and complexity are proved. In particular, given tolerances $\delta>0$ and $\varepsilon>0$ for feasibility/complementarity and optimality, respectively, it is shown that a measure of $(\delta,0)$-criticality tends to zero; and the the number of iterations and functional evaluations required to achieve $(\delta,\varepsilon)$-criticality is $O(\varepsilon^{-2})$. Numerical experiments in which the proposed method is used to solve a continuous version of the traveling salesman problem are presented.

Keywords: Coordinate descent methods, convergence, complexity.

Full text: [pdf]

Abstract: The problem of covering a region of the plane with a fixed number of minimum-radius identical balls is studied in the present work. An explicit construction of bi-Lipschitz mappings is provided to model small perturbations of the union of balls. This allows us to obtain analytical expressions for first- and second-order derivatives using nonsmooth shape optimization techniques under appropriate regularity assumptions. Singular cases are also studied using asymptotic analysis. For the case of regions given by the union of disjoint convex polygons, algorithms based on Voronoi diagrams that do not rely on approximations are given to compute the derivatives. Extensive numerical experiments illustrate the capabilities and limitations of the introduced approach.

Keywords: Covering problem, nonsmooth shape optimization, Augmented Lagrangian, Newton's method.

Full text: [pdf]

Abstract: The Inexact Restoration approach has proved to be an adequate tool for handling the problem of minimizing an expensive function within an arbitrary feasible set by using different degrees of precision in the objective function. The Inexact Restoration framework allows one to obtain suitable convergence and complexity results for an approach that rationally combines low- and high-precision evaluations. In the present research, it is recognized that many problems with expensive objective functions are nonsmooth and, sometimes, even discontinuous. Having this in mind, the Inexact Restoration approach is extended to the nonsmooth or discontinuous case. Although optimization phases that rely on smoothness cannot be used in this case, basic convergence and complexity results are recovered. A derivative-free optimization phase is defined and the subproblems that arise at this phase are solved using a regularization approach that take advantage of different notions of stationarity. The new methodology is applied to the problem of reproducing a controlled experiment that mimics the failure of a dam.

Keywords: Inexact Restoration, derivative-free, inexact evaluation, expensive function, global convergence, algorithms.

Full text: [pdf]

Abstract: A general framework for solving nonlinear least squares problems without the employment of derivatives is proposed in the present paper together with a new general global convergence theory. With the aim to cope with the case in which the number of variables is big (for the standards of derivative-free optimization), two dimension-reduction procedures are introduced. One of them is based on iterative subspace minimization and the other one is based on spline interpolation with variable nodes. Each iteration based on those procedures is followed by an acceleration step inspired in the Sequential Secant Method. The practical motivation for this work is the estimation of parameters in Hydraulic models applied to dam breaking problems. Numerical examples of the application of the new method to those problems are given.

Keywords: Nonlinear least-squares, derivative-free methods, acceleration, Manning coefficients.

Full text: [pdf]

Abstract: Many practical problems require the solution of large-scale constrained optimization problems for which preserving feasibility is a key issue and the evaluation of the objective function is very expensive. In these cases it is mandatory to start with a feasible approximation of the solution, the obtention of which should not require objective function evaluations. The necessity of solving this type of problems motivated us to revisit the classical barrier approach for nonlinear optimization, providing a careful implementation of a modern version of this method. This is the main objective of the present paper. For completeness, we provide global convergence results and comparative numerical experiments with one of the state-of-the-art interior-point solvers for continuous optimization.

Keywords: Linearly constrained optimization, feasible barrier methods, convergence, numerical experiments.

Full text: [pdf]

Abstract: In this paper, the problem of covering a region in the plane with the union of $m$ identical balls of minimum radius is studied. The region to be covered may be a disconnected union of Lipschitz domains and in particular may have corners and be nonconvex. Nullifying the area of the complement of the union of balls with respect to the region to be covered is considered as the constraint, while minimizing the balls' radius is the objective function. The first-order sensitivity analysis of the area to be nullified in the constraint is performed using shape optimization techniques. A bi-Lipschitz mapping is built to model small perturbations of the nonsmooth shape defined via unions and intersections; this allows us to compute the derivative of the constraint via the notion of shape derivative. The considered approach is fairly general and can be adapted to tackle other relevant nonsmooth shape optimization problems. By discretizing the integrals that appear in the formulation of the problem and its derivatives, a nonlinear programming problem is obtained. From the practical point of view, the region to be covered is modeled by an oracle that, for a given point, answers whether it belongs to the region or not. No additional information on the region is required. Numerical examples in which the nonlinear programming problem is solved with an Augmented Lagrangian approach are presented. The experiments illustrate the wide variety of regions whose covering can be addressed with the proposed approach.

Keywords: Covering problem, nonsmooth shape optimization, shape derivatives.

Full text: [pdf]

Abstract: In this work, the online printing shop scheduling problem introduced in (Lunardi et al., Mixed Integer Linear Programming and Constraint Programming Models for the Online Printing Shop Scheduling Problem, Computers & Operations Research, to appear) is considered. This challenging real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility; and it presents several complicating specificities such as resumable operations, periods of unavailability of the machines, sequence-dependent setup times, partial overlapping between operations with precedence constraints, and fixed operations, among others. A local search strategy and metaheuristic approaches for the problem are proposed and evaluated. Based on a common representation scheme, trajectory and populational metaheuristics are considered. Extensive numerical experiments with large-sized instances show that the proposed methods are suitable for solving practical instances of the problem; and that they outperform a half-heuristic-half-exact off-the-shelf solver by a large extent. Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case.

Keywords: Flexible job shop scheduling, Sequencing flexibility, Resumable operations, Machine availability, Sequence-dependent setup time, Local search, Metaheuristics.

Full text: [pdf]

Abstract: In many engineering applications it is necessary to minimize smooth functions plus penalty (or regularization) terms that violate smoothness and convexity. Specific algorithms for this type of problems are available in recent literature. Here a smooth reformulation is proposed and equivalence with the original problem is proved both from the point of view of global and local optimization. Moreover, for the cases in which the objective function is much more expensive than the constraints, model-intensive algorithms, accompanied by their convergence and complexity theories, are introduced. Finally, numerical experiments are presented.

Keywords: Constrained non-Lipschitz nonsmooth optimization, complexity analysis, optimality conditions.

Full text: [pdf]

Abstract: Algencan is a well established safeguarded Augmented Lagrangian algorithm introduced in [R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt, On Augmented Lagrangian methods with general lower-level constraints, SIAM Journal on Optimization 18, pp. 1286-1309, 2008]. Complexity results that report its worst-case behavior in terms of iterations and evaluations of functions and derivatives that are necessary to obtain suitable stopping criteria are presented in this work. In addition, the computational performance of a new version of the method is presented, which shows that the updated software is a useful tool for solving large-scale constrained optimization problems.

Keywords: Nonlinear programming, Augmented Lagrangian methods, complexity, numerical experiments.

Full text: [pdf]

Abstract: In this work, the online printing shop scheduling problem is considered. The problem, that appears in the nowadays printing industry, can be seen as an extended flexible job shop scheduling problem with several particularities such as operations' release times, operations' precedence constraints given by an arbitrary acyclic graph, partial overlapping among operations with precedence constraints, sequence-dependent setup times, fixed operations, and machines' unavailability periods. In the present work, mixed integer programming and constraint programming models for the minimization of the makespan are presented. Modeling the problem is twofold. On the one hand, the problem is precisely defined. On the other hand, small- and medium-sized instances are optimally solved. Extensive numerical experiments show the capabilities and limitations of a commercial software for solving the models.

Keywords: Flexible job shop scheduling, Mixed integer linear programming, Constraint programming.

Full text: [pdf]

Abstract: In a recent paper [E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and Ph. L. Toint, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Mathematical Programming 163(1), 359-368, 2017], it was shown that, for the smooth unconstrained optimization problem, worst-case evaluation complexity $O(\epsilon^{-(p+1)/p})$ may be obtained by means of algorithms that employ sequential approximate minimizations of $p$-th order Taylor models plus $(p+1)$-th order regularization terms. The aforementioned result, which assumes Lipschitz continuity of the $p$-th partial derivatives, generalizes the case $p=2$, known since 2006, which has already motivated efficient implementations. The present paper addresses the issue of defining a reliable algorithm for the case $p=3$. With that purpose, we propose a specific algorithm and we show numerical experiments.

Keywords: Unconstrained minimization, third-order models, regularization, complexity.

Full text: [pdf]

Abstract: In this work we present an Augmented Lagrangian algorithm for nonlinear semidefinite problems (NLSDPs), which is a natural extension of its consolidated counterpart in nonlinear programming. This method works with two levels of constraints; one that is penalized and other that is kept within the subproblems. This is done in order to allow exploiting the subproblem structure while solving it. The global convergence theory is based on recent results regarding approximate Karush-Kuhn-Tucker optimality conditions for NLSDPs, which are stronger than the usually employed Fritz John optimality conditions. Additionally, we approach the problem of covering a given object with a fixed number of balls with a minimum radius, where we exploit some convex algebraic geometry tools, such as Stengle's Positivstellensatz and its variations, which allows for a much more general model. Preliminary numerical experiments are presented.

Keywords: Augmented Lagrangian, Nonlinear Semidefinite Programming, Covering Problem, Convex Algebraic Geometry.

Full text: [pdf]

Abstract: This paper addresses the minimization of the absolute deviation of job completion times from a common due date in a flowshop scheduling problem. Besides this main objective, the minimization of the waiting time of the jobs in the production environment is also considered. Initially, a mixed integer programming model for this problem is proposed and, due to its complexity, heuristic approaches are developed. A list-scheduling algorithm for the approached problem is introduced. Moreover, a filtered beam search method that explores specific characteristics of the considered environment is proposed. Numerical experiments show that the presented methods can be successfully applied to this problem.

Keywords: Scheduling, flowshop, earliness and tardiness, common due date, waiting time, heuristics, beam search.

Full text: [pdf]

Abstract: A mixed integer linear programming model for the two-dimensional non-guillotine cutting problem with usable leftovers was recently introduced in Andrade et al. [Journal of the Operational Research Society 65, pp. 1649-1663, 2014]. The problem consists in cutting a set of ordered items using a set of objects of minimum cost and, within the set of solutions of minimum cost, maximizing the value of the usable leftovers. Since the concept of usable leftovers assumes they can potentially be used to attend new arriving orders, the problem is extended to the multiperiod framework in this work. In this way, the decision at each instant does not minimize in a myopic way the cost of the objects required to attend the orders of the current instant; but it aims to minimize the overall cost of the objects up to the considered time horizon. Some variants of the proposed model are analyzed and numerical results are presented.

Keywords: Two-dimensional cutting with usable leftovers, MIP models, non-guillotine cutting and packing, multiperiod scenario.

Full text: [pdf]

Abstract: In this paper, we address the Constrained Two-dimensional Rectangular Guillotine Single Large Placement Problem (2D R CG SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts.In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new compact integer non-linear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the ILP formulation, without loss of optimality. From the ILP formulation, we derive two new compact models for particular cases of the 2D R CG SLOPP, which consider only 2-staged or 1-group patterns. Finally, as a specific solution method for the 2D R CG SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch-and-Benders-cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the objecti's dimensions.

Keywords: Cutting and packing problems, Constrained two-dimensional guillotine cuts, Integer programming models, branch-and-Benders-cut algorithm.

Full text: [pdf]

Abstract: In many cases in which one wishes to minimize a complicated or expensive function, it is convenient to employ cheap approximations, at least when the current approximation to the solution is far from the solution. Adequate strategies for deciding the accuracy desired at each stage of optimization are crucial for the global convergence and overall efficiency of the process. A recently introduced procedure [E. G. Birgin, N. Krejić, and J. M. Martínez, On the employment of Inexact Restoration for the minimization of functions whose evaluation is subject to errors, Mathematics of Computation 87, pp. 1307-1326, 2018] based on Inexact Restoration is revisited, modified, and analyzed from the point of view of worst-case evaluation complexity in this work.

Keywords: Inexact Restoration, global convergence, worst-case evaluation complexity.

Full text: [pdf]

Abstract: A Newton-like method for unconstrained minimization is introduced in the present work. While the computer work per iteration of the best-known implementations may need several factorizations per iteration or may use rather expensive matrix decompositions, the proposed method uses a single cheap factorization per iteration. Convergence and complexity and results, even in the case in which the subproblems' Hessians are far from being Hessians of the objective function, are presented. Moreover, when the Hessian is Lipschitz-continuous, the proposed method enjoys $O(\varepsilon^{-3/2})$ evaluation complexity for first-order optimality and $O(\varepsilon^{-3})$ for second-order optimality as other recently introduced Newton method for unconstrained optimization based on cubic regularization or special trust-region procedures. Fairly successful and fully reproducible numerical experiments are presented and the developed corresponding software is freely available.

Keywords: Smooth unconstrained minimization, Bunch-Parlett-Kaufman factorizations, regularization, Newton-type methods.

Full text: [pdf]

Abstract: The problem of packing ellipsoids in the three-dimensional space is considered in the present work. The proposed approach combines heuristic techniques with the resolution of recently introduced nonlinear programming models in order to construct solutions with a large number of ellipsoids. The introduced approach is able to pack identical and non-identical ellipsoids within a variety of containers. Moreover, it allows the inclusion of additional positioning constraints. This fact makes the proposed approach suitable for constructing large-scale solutions with specific positioning constraints in which density may not be the main issue. Numerical experiments illustrate that the introduced approach delivers good quality solutions with a computational cost that scales linearly with the number of ellipsoids; and solutions with more than a million ellipsoids are exhibited.

Keywords: Packing, ellipsoids, nonlinear programming, algorithms, matheuristic.

Full text: [pdf]

Abstract: The main objective of this research is to introduce a practical method for smooth bound-constrained optimization that possesses worst-case evaluation complexity $O(\varepsilon^{-3/2})$ for finding an $\varepsilon$-approximate first-order stationary point when the Hessian of the objective function is Lipschitz-continuous. As other well established algorithms for optimization with box constraints, the algorithm proceeds visiting the different faces of the domain aiming to reduce the norm of an internal projected gradient and abandoning active constraints when no additional progress is expected in the current face. The introduced method emerges as a particular case of a method for minimization with linear constraints. Moreover, the linearly-constrained minimization algorithm is an instance of a minimization algorithm with general constraints whose implementation may be unaffordable when the constraints are complicated. As a procedure for leaving faces, it is employed a different method that may be regarded as an independent device for constrained optimization. Such independent algorithm may be employed to solve linearly-constrained optimization problem on its own, without relying on the active-set strategy. A careful implementation and numerical experiments shows that the algorithm that combines active sets with leaving-face iterations is more effective than the independent algorithm on which leaving-face iterations are based, although both exhibits similar complexities $O(\varepsilon^{-3/2})$.

Keywords: Nonlinear programming, bound-constrained minimization, active-set strategies, regularization, complexity.

Full text: [pdf]

Abstract: Inexact Restoration is a well established technique for continuous minimization problems with constraints. Recently, it has been used by Krejic and Martínez for optimization of functions whose evaluation is necessarily inexact and comes from an iterative process. This technique will be generalized in the present paper and it will be applied to stochastic optimization and related problems. New convergence results will be given and numerical results will be presented.

Keywords: Inexact Restoration, stochastic programming, global convergence, numerical experiments.

Full text: [pdf]

Abstract: Augmented Lagrangian methods with convergence to second-order stationary points in which any constraint can be penalized or carried out to the subproblems are considered in this work. The resolution of each subproblem can be done by any numerical algorithm able to return approximate second-order stationary points. The developed global convergence theory is stronger than the ones known for current algorithms with convergence to second-order points in the sense that, besides the flexibility introduced by the general lower-level approach, it includes a loose requirement for the resolution of subproblems. The proposed approach relies on a weak constraint qualification, that allows Lagrange multipliers to be unbounded at the solution. It is also shown that second-order resolution of subproblems increases the chances of finding a feasible point, in the sense that limit points are second-order stationary for the problem of minimizing the squared infeasibility. The applicability of the proposed method is illustrated in numerical examples with ball-constrained subproblems.

Keywords: Augmented Lagrangian methods, nonlinear programming, second-order stationary points, algorithms.

Full text: [pdf]

Abstract: A general approach for the solution of possibly discontinuous optimization problems by means of pointwise (perhaps smooth) approximations will be proposed. It will be proved that sequences generated by pointwise approximation techniques eventually satisfy well justified stopping criteria. Numerical examples will be given.

Keywords:Discontinuous functions, pointwise approximations, smoothing, minimization.

Full text: [pdf]

Abstract: The problem of packing ellipsoids is considered in the present work. Usually, the computational effort associated with numerical optimization methods devoted to packing ellipsoids grows quadratically with respect to the number of ellipsoids being packed. The reason is that the number of variables and constraints of ellipsoids' packing models is associated with the requirement that every pair of ellipsoids must not overlap. As a consequence, it is hard to solve the problem when the number of ellipsoids is large. In this paper, we present a nonlinear programming model for packing ellipsoids that contains a linear number of variables and constraints. The proposed model finds its basis in a transformation-based non-overlapping model recently introduced by Birgin, Lobato, and Martínez [Journal of Global Optimization (2015), DOI: 10.1007/s10898-015-0395-z]. Numerical experiments show the efficiency and effectiveness of the proposed model.

Keywords: Cutting and packing ellipsoids, optimization, nonlinear programming, models, numerical experiments.

Full text: [pdf]

Abstract: Cubic-regularization and trust-region methods with worst-case first-order complexity $O(\varepsilon^{-3/2})$ and worst-case second-order complexity $O(\varepsilon^{-3})$ have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic-regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. Asymptotic convergence and order of convergence results are also presented. Finally, some numerical experiments comparing the new algorithm with a well-established quadratic regularization method are shown.

Keywords: Nonlinear programming, unconstrained minimization, quadratic regularization, cubic descent, complexity.

Full text: [pdf]

Abstract: The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order $p$ (for $p \geq 1$) and to assume Lipschitz continuity of the $p$-th derivative, then an $\epsilon$-approximate first-order critical point can be computed in at most $O(\epsilon^{-(p+1)/p})$ evaluations of the problem's objective function and its derivatives. This generalizes and subsumes results known for $p = 1$ and $p = 2$.

Keywords: Unconstrained minimization, worst-case complexity.

Full text: [pdf]

Abstract: A new method is proposed for solving optimization problems with equality constraints and bounds on the variables. In the spirit of Sequential Quadratic Programming and Sequential Linearly-Constrained Programming, the new method approximately solves, at each iteration, an equality-constrained optimization problem. The bound constraints are handled in outer iterations by means of an Augmented Lagrangian scheme. Global convergence of the method follows from well-established non-linear programming theories. Numerical experiments are presented.

Keywords:Nonlinear programming, Sequential Equality-Constrained Optimization, Augmented Lagrangian, numerical experiments.

Full text: [pdf]

Abstract: Inexact restoration (IR) is a well established technique for continuous minimization prob- lems with constraints that can be applied to constrained optimization problems with specific structures. When some variables are restricted to be integer, an IR strategy seems to be appropriate. The IR strategy employs a restoration procedure in which one solves a standard nonlinear programming problem and an optimization procedure in which the constraints are linearized and techniques for mixed-integer (linear or quadratic) programming can be em- ployed.

Keywords: Inexact restoration, mixed-integer nonlinear programming (MINLP), projected gradients.

Full text: [pdf]

Abstract: In this paper, continuous and dierentiable nonlinear programming models and algorithms for packing ellipsoids in the n-dimensional space are introduced. Two dierent models for the non-overlapping and models for the inclusion of ellipsoids within half-spaces and ellipsoids are presented. By applying a simple multi-start strategy combined with a clever choice of starting guesses and a nonlinear programming local solver, illustrative numerical experiments are presented.

Keywords: Cutting and packing ellipsoids, nonlinear programming, models, numerical experiments.

Full text: [pdf]

Abstract: The evaluation complexity of general nonlinear, possibly nonconvex, constrained optimization is analyzed. It is shown that, under suitable smoothness conditions, an $\epsilon$-approximate first-order critical point of the problem can be computed in order $O(\epsilon^{1-2(p+1)/p})$ evaluations of the problem's function and their first p derivatives. This is achieved by using a two-phases algorithm inspired by Cartis, Gould, and Toint [8, 11]. It is also shown that strong guarantees (in terms of handling degeneracies) on the possible limit points of the sequence of iterates generated by this algorithm can be obtained at the cost of increased complexity. At variance with previous results, the -approximate first-order criticality is defined by satisfying a version of the KKT conditions with an accuracy that does not depend on the size of the Lagrange multipliers.

Keywords: Nonlinear programming, complexity, approximate KKT point.

Full text: [pdf]

Abstract: Algencan is a freely available piece of software that aims to solve smooth large-scale constrained optimization problems. When applied to specific problems, obtaining a good performance in terms of efficacy and efficiency may depend on careful choices of options and parameters. In the present paper the application of Algencan to four portfolio optimization problems is discussed and numerical results are presented and evaluated.

Keywords: Constrained optimization, Augmented Lagrangian, Portfolios, Generalized Order-Value Optimization, Conditional Value-at-Risk.

Full text: [pdf]

Abstract: The problem of packing items within bounded regions in the Euclidean space has multiple applications in a variety of areas, such as, Physics, Chemistry, and Engineering. Problems of this type exhibit various levels of complexity. Nonlinear programming formulations and methods had been successfully applied to a wide range of packing problems. In this review paper, a brief description of the state-of-the-art and an illustrated overview of packing nonlinear programming techniques and applications will be presented.

Full text: [pdf]

Abstract: In this study we are concerned with the non-exact two-stage two-dimensional guillotine cutting problem considering usable leftovers, in which stock plates remainders of the cutting patterns (non-used material or trim loss) can be used in the future, if they are large enough to fulfill future demands of items (ordered smaller plates). This cutting problem can be characterized as a residual bin-packing problem because of the possibility of creating new residual pieces, as the trim loss of each cutting/packing pattern does not necessarily represent waste of material and, depending on its size, it can be put back into stock. Two bilevel mathematical programming models to represent this non-exact two-stage two-dimensional residual bin-packing problem are presented. The models basically consist on cutting/packing the ordered items using a set of plates of minimum cost and, among all possible solutions of minimum cost, choosing one that maximizes the value of the generated usable leftovers. Because of special characteristics of these bilevel models, they can be reformulated as one-level mixed integer programming models. Results of some numerical experiments are presented to show that the models represent appropriately the problem and to illustrate their performances.

Keywords: Two-stage two-dimensional guillotine cutting, residual bin-packing problem, bilevel programming, MIP models, leftovers.

Full text: [pdf]

Abstract: The Quadratic Finite Element Model Updating Problem (QFEMUP) concerns with updating a symmetric second-order finite element model so that it remains symmetric and the updated model reproduces a given set of desired eigenvalues and eigenvectors by replacing the corresponding ones from the original model. Taking advantage of the special structure of the constraint set, it is first shown that the QFEMUP can be formulated as a suitable constrained nonlinear programming problem. Using this formulation, a method based on successive optimizations is then proposed and analyzed. To avoid that spurious modes (eigenvectors) appear in the frequency range of interest (eigenvalues) after the model has been updated, additional constraints based on a quadratic Rayleigh quotient are dynamically included in the constraint set. A distinct practical feature of the proposed method is that it is implementable computing only a few eigenvalues and eigenvectors of the associated quadratic matrix pencil. The results of our numerical experiments on illustrative problems show that the algorithm works well in practice.

Keywords: Quadratic matrix model updating, quadratic Rayleigh quotient, nonlinear programming, algorithms.

Full text: [pdf]

Abstract: An extended version of the flexible job shop problem is tackled in this work. The considered extension to the classical flexible job shop problem allows the precedences between the operations to be given by an arbitrary directed acyclic graph instead of a linear order. Therefore, the problem consists of allocating the operations to the machines and sequencing them in compliance with the given precedences. The goal in the present work is the minimization of the makespan. A list scheduling algorithm is introduced and its natural extension to a beam search method is proposed. Numerical experiments assess the efficiency of the proposed approaches.

Keywords: Scheduling, flexible job shop, makespan, list scheduling, beam search.

Full text: [pdf]

Abstract: Sometimes, the feasible set of an optimization problem that one aims to solve using a Nonlinear Programming algorithm is empty. In this case, two characteristics of the algorithm are desirable. On the one hand, the algorithm should converge to a minimizer of some infeasibility measure. On the other hand, one may wish to find a point with minimal infeasibility for which some optimality condition, with respect to the objective function, holds. Ideally, the algorithm should converge to a minimizer of the objective function subject to minimal infeasibility. In this paper the behavior of an Augmented Lagrangian algorithm with respect to those properties will be studied.

Keywords:Nonlinear Programming, infeasible domains, Augmented Lagrangians, algorithms, numerical experiments.

Full text: [pdf]

Abstract: Inexact Restoration methods have been proved to be effective to solve constrained optimization problems in which some structure of the feasible set induces a natural way of recovering feasibility from arbitrary infeasible points. Sometimes natural ways of dealing with minimization over tangent approximations of the feasible set are also employed. A recent paper [N. Banihashemi and C. Y. Kaya, Inexact Restoration for Euler discretization of box-constrained optimal control problems, Journal of Optimization Theory and Applications 156, pp. 726--760, 2013] suggests that the Inexact Restoration approach can be competitive with well-established nonlinear programming solvers when applied to certain control problems without any problem-oriented procedure for restoring feasibility. This result motivated us to revisit the idea of designing general-purpose Inexact Restoration methods, especially for large-scale problems. In this paper we introduce an affordable algorithm of Inexact Restoration type for solving arbitrary nonlinear programming problems and we perform the first experiments that aim to assess its reliability.

Keywords:Nonlinear programming, Inexact Restoration, numerical experiments.

Full text: [pdf]

Abstract: This paper presents iterated local search and great deluge trajectory metaheuristics for the linear ordering problem (LOP). Both metaheuristics are based on the TREE local search method introduced in Sakuraba and Yagiura, 2010 (Efficient local search algorithms for the linear ordering problem, International Transactions in Operational Research 17, pp. 711-737) that is the only method ever applied to a set of large-sized instances that are in line with the scale of nowadays real applications. By providing diversification and intensification features, the introduced methods improve all best known solutions of the large-sized instances set. Extensive numerical experiments show that the introduced methods are capable of tackling sparse and dense large-scale instances with up to 8,000 vertices and 31,996,000 edges in a reasonable amount of time; while they also performs well in practice when compared with other state-of-the-art methods in a benchmark with small and medium-scale instances.

Keywords:Metaheuristics, iterated local search, great deluge, linear ordering problem, large-scale instances.

Full text: [pdf]

Abstract: In this study we deal with the two-dimensional non-guillotine cutting problem of how to cut a set of rectangular objects with known sizes and quantities to exactly produce a set of rectangular items with specified sizes and demands to be fulfilled. We are concerned with the special case of the problem in which the non-used material of the cutting patterns (objects leftovers) may be used in the future, if it is large enough to fulfill future items demands. Therefore, the problem is seen as a two-dimensional non-guillotine cutting/packing problem with usable leftovers, also known in the literature as a two-dimensional residual bin-packing problem. We use multilevel mathematical programming models to represent appropriately the problem, which basically consists on cutting the ordered items using a set of objects of minimum cost, among all possible solutions of minimum cost, choosing one that maximizes the value of the usable leftovers, and, among them, selecting one that minimizes the number of usable leftovers. Because of special characteristics of these multilevel models, they can be reformulated as one-level mixed integer programming (MIP) models. Illustrative numerical examples are presented and analysed.

Keywords: Two-dimensional cutting with usable leftovers, MIP models, non-guillotine cutting and packing, multilevel mathematical programming, residual bin-packing problem.

Full text: [pdf]

Abstract: Over the last two decades, it has been observed that using the gradient vector as a search direction in large-scale optimization may lead to efficient algorithms. The effectiveness relies on choosing the step lengths according to novel ideas that are related to the spectrum of the underlying local Hessian rather than related to the standard decrease in the objective function. A review of these so-called spectral projected gradient methods for convex constrained optimization is presented. To illustrate the performance of these low-cost schemes, an optimization problem on the set of positive definite matrices is described.

Keywords: Spectral Projected Gradient methods, nonmonotone line search, large scale problems, convex constrained problems.

Full text: [pdf]

Abstract: A MILP model for an extended version of the Flexible Job Shop Scheduling problem is proposed. The extension allows the precedences between operations of a job to be given by an arbitrary directed acyclic graph rather than a linear order. The goal is the minimization of the makespan. Theoretical and practical advantages of the proposed model are discussed. Numerical experiments show the performance of a commercial exact solver when applied to the proposed model. The new model is also compared with a simple extension of the model described by Ozguven, Ozbakir, and Yavuz (Mathematical models for job-shop scheduling problems with routing and process plan flexibility, Applied Mathematical Modelling, 34:1539--1548, 2010), using instances from the literature and instances inspired by real data from the printing industry.

Keywords: Scheduling, Flexible Job Shop, MIP models.

Full text: [pdf]

Abstract: In a recent paper, Birgin, Floudas and Martínez introduced an augmented Lagrangian method for global optimization. In their approach, augmented Lagrangian subproblems are solved using the alphaBB method and convergence to global minimizers was obtained assuming feasibility of the original problem. In the present research, the algorithm mentioned above will be improved in several crucial aspects. On the one hand, feasibility of the problem will not be required. Possible infeasibility will be detected in finite time by the new algorithms and optimal infeasibility results will be proved. On the other hand, finite termination results that guarantee optimality and/or feasibility up to any required precision will be provided. An adaptive modification in which subproblem tolerances depend on current feasibility and complementarity will also be given. The adaptive algorithm allows the augmented Lagrangian subproblems to be solved without requiring unnecessary potentially high precisions in the intermediate steps of the method, which improves the overall efficiency. Experiments showing how the new algorithms and results are related to practical computations will be given.

Keywords: Deterministic global optimization, augmented Lagrangians, nonlinear programming, algorithms, numerical experiments.

Full text: [pdf]

Abstract: The problem of packing circles within ellipses is considered in the present paper. A new ellipse-based system of coordinates is introduced by means of which a closed formula to compute the distance of an arbitrary point to the boundary of an ellipse exists. Nonlinear programming models for some variants of 2D and 3D packing problems involving circular items and elliptical objects are given. The resulting models are medium-sized highly nonlinear challenging nonlinear programming problems for which a global solution is sought. For this purpose, multistart strategies are carefully and thoroughly explored. Numerical experiments are exhibited.

Keywords: Packing, ellipses, circles, global optimization.

Full text: [pdf]

Abstract: Large-scale electronic structure calculations usually involve huge nonlinear eigenvalue problems. A method for solving these problems without employing expensive eigenvalue decompositions of the Fock matrix is presented in this work. The sparsity of the input and output matrices is preserved at every iteration and the memory required by the algorithm scales linearly with the number of atoms of the system. The algorithm is based on a projected gradient iteration applied to the constraint fulfillment problem. The computer time required by the algorithm also scales approximately linearly with the number of atoms (or non-null elements of the matrices), and the algorithm is faster than standard implementations of modern eigenvalue decomposition methods for sparse matrices containing more than 50,000 non-null elements. The new method reproduces the sequence of semiempirical SCF iterations obtained by standard eigenvalue decomposition algorithms to good precision.

Keywords: Electronic Structure Calculations, Semiempirical methods, Projected Gradient, linear scaling, sparsity.

Full text: [pdf]

Abstract: Two problems related to packing identical orthogonal rectangles within a polyhedron are tackled in the present work. The first problem consists in packing as many identical rectangles as possible within a given polyhedron, while the second problem consists in finding the smallest polyhedron of a given type that accommodates a fixed number of identical rectangles. Both problems are modeled as mixed integer programming problems. Symmetry-breaking constraints that facilitate the solution of the MIP models are introduced. Numerical results are presented.

Keywords: Packing of rectangles, MIP models, symmetry-breaking constraints, algorithms.

Full text: [pdf]

Abstract: Problems of planar covering with ellipses are tackled in this work. Ellipses can have a fixed angle or each of them can be freely rotated. Deterministic global optimization methods are developed for both cases, while a stochastic version of the method is also proposed for large instances of the latter case. Numerical results show the effectiveness and efficiency of the proposed methods.

Keywords: Planar covering with ellipses, deterministic global optimization, algorithms.

Full text: [pdf]

Abstract: Bound-constrained minimization is a subject of active research. To assess the performance of existent solvers, numerical evaluations and comparisons are carried on. Arbitrary decisions that may have a crucial effect on the conclusions of numerical experiments are highlighted in the present work. As a result, a detailed evaluation based on performance profiles is applied to the comparison of bound-constrained minimization solvers. Extensive numerical results are presented and analyzed.

Keywords: Bound-constrained minimization, benchmarking, numerical evaluation, performance profiles.

Full text: [pdf]

Abstract: The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, we investigate the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.

Keywords: Scheduling, single machine, earliness and tardiness, heuristic methods.

Full text: [pdf]

Abstract: Augmented Lagrangian methods are effective tools for solving large-scale nonlinear programming problems. At each outer iteration a minimization subproblem with simple constraints, whose objective function depends on updated Lagrange multipliers and penalty parameters, is approximately solved. When the penalty parameter becomes very large the subproblem is difficult, therefore the effectiveness of this approach is associated with boundedness of penalty parameters. In this paper it is proved that, under more natural assumptions than the ones up to now employed, penalty parameters are bounded. For proving the new boundedness result, the original algorithm has been slightly modified. Numerical consequences of the modifications are discussed and computational experiments are presented.

Keywords: Nonlinear Programming, Augmented Lagrangian methods, Penalty parameters, Numerical experiments.

Full text: [pdf]

Abstract: At each outer iteration of standard Augmented Lagrangian methods one tries to solve a box-constrained optimization problem with some prescribed tolerance. In the continuous world, using exact arithmetic, this subproblem is always solvable. Therefore, the possibility of finishing the subproblem resolution without satisfying the theoretical stopping conditions is not contemplated in usual convergence theories. However, in practice, one might not be able to solve the subproblem up to the required precision. This may be due to different reasons. One of them is that the presence of an excessively large penalty parameter could impair the performance of the box-constraint optimization solver. In this paper a practical strategy for decreasing the penalty parameter in situations like the one mentioned above is proposed. More generally, the different decisions that may be taken when, in practice, one is not able to solve the Augmented Lagrangian subproblem will be discussed. As a result, an improved Augmented Lagrangian method is presented, which takes into account numerical difficulties in a satisfactory way, preserving suitable convergence theory. Numerical experiments are presented involving all the CUTEr collection test problems.

Keywords: Nonlinear Programming, Augmented Lagrangian methods, Penalty parameters, Numerical experiments.

Full text: [pdf]

Abstract: In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of problem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method.

Keywords: Cutting and packing, two-dimensional non-guillotine cutting pattern, dynamic programming, recursive approach, distributor's pallet loading problem.

Full text: [pdf]

Abstract: Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this work we examine the flowshop scheduling problem with no storage constraints and with blocking in-process. In this latter environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Performance is measured by the minimization of the sum of earliness and tardiness of the jobs. Mixed-integer models that represent these scheduling flowshop problems are presented. The models are evaluated and compared in several problems using commercial known software.

Keywords: Flowshop scheduling, earliness and tardiness, blocking in-process, mixed-integer programming formulations.

Full text: [pdf]

Abstract: In Low Order-Value Optimization (LOVO) problems the sum of the r smallest values of a finite sequence of q functions is involved as the objective to be minimized or as a constraint. The latter case is considered in the present paper. Portfolio optimization problems with a constraint on the admissible Value at Risk (VaR) can be modeled in terms of a LOVO problem with constraints given by Low Order-Value functions. Different algorithms for practical solution of this problem will be presented. Using these techniques, portfolio optimization problems with transaction costs will be solved.

Keywords: Optimization, Augmented Lagrangian, Order-Value Optimization, Low Order-Value Optimization, Value at Risk, Numerical algorithms.

Full text: [pdf]

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

Keywords: Nonlinear programming, Augmented Lagrangian method, trust regions.

Full text: [pdf]

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

Keywords: Packing and cutting of rectangles, orthogonal packing, isotropic convex regions, feasibility problems, nonlinear programming, models.

Full text: [pdf]

Abstract: Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a hybrid heuristic -- based on the CGRASP and GENCAN methods -- for finding approximate solutions for continuous global optimization problems subject to box constraints. Experimental results illustrate the relative effectiveness of CGRASP-GENCAN on a set of benchmark multimodal test functions.

Keywords: Global optimization, stochastic methods, active-set methods, heuristic, CGRASP, GENCAN.

Full text: [pdf]

Abstract: A novel global optimization method based on an Augmented Lagrangian framework is introduced for continuous constrained nonlinear optimization problems. At each outer iteration the method requires the $\varepsilon$-global minimization of the Augmented Lagrangian with simple constraints. Global convergence to an $\varepsilon$-global minimizer of the original problem is proved. The subproblems are solved using the $\alpha$BB method. Numerical experiments are presented.

Keywords: Deterministic global optimization, Augmented Lagrangians, nonlinear programming, algorithms, numerical experiments.

Full text: [pdf] [ps]

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

Keywords: Sentinels, polygons, intersection, packing, nonlinear programming.

Full text: [pdf]

Abstract: 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 converge to second-order stationary points in situations in which first-order methods fail are exhibited.

Keywords: Nonlinear programming, Augmented Lagrangians, global convergence, optimality conditions, second-order conditions, constraint qualifications.

Full text: [pdf]

Abstract: In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an $L$-approach for packing rectangles into larger rectangles and $L$-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50 thousand instances). It is also effective for solving the instances of problem set Cover III (almost 100 thousand instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmark purposes at http://www.ime.usp.br/~egbirgin/packing/.

Keywords: Cutting and packing, manufacturer's pallet loading problem, woodpulp stowage problem, non-guillotine cutting pattern, recursive algorithms.

Full text: [pdf] [ps]

Abstract: The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of nonlinear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/~egbirgin/packing/.

Keywords: Packing, nonlinear equations system, Newton's method, nonlinear programming.

Full text: [pdf]

Abstract: A method for linearly constrained optimization which modifies and generalizes recent box-constraint optimization algorithms is introduced. The new algorithm is based on a relaxed form of Spectral Projected Gradient iterations. Intercalated with these projected steps, internal iterations restricted to faces of the polytope are performed, which enhance the efficiency of the algorithms. Convergence proofs are given and numerical experiments are included and commented. Software supporting this paper is available through the TANGO Project web page.

Keywords: Linearly constrained optimization, spectral projected gradient method, active set methods.

Full text: [pdf]

Abstract: Adequate initial configurations for molecular dynamics simulations consist of arrangements of molecules distributed in space in such a way to approximately represent the system's overall structure. In order that the simulations are not disrupted by large Van der Waals repulsive interactions, atoms from different molecules must keep safe pairwise distances. Obtaining such a molecular arrangement can be considered a packing problem: Each type molecule must satisfy spatial constraints related to the geometry of the system, and the distance between atoms of different molecules must be greater than some specified tolerance. We have developed a code able to pack millions of atoms, grouped in arbitrarily complex molecules, inside a variety of three-dimensional regions. The regions may be intersections of spheres, ellipses, cylinders, planes or boxes. The user must provide only the structure of one molecule of each type and the geometrical constraints that each type of molecule must satisfy. Building complex mixtures, interfaces, solvating biomolecules in water or other solvents, or mixtures of solvents is straightforward. In addition, different atoms belonging to the same molecule may also be restricted to different spacial regions, in such a way that more ordered molecular arrangements can be built, as micelles, lipid double-layers, etc. The packing time for state-of-the-art molecular dynamics systems varies from a few seconds to a few minutes in a personal computer. The input files are simple and currently compatible with PDB, Tinker, Molden or Moldy coordinate files. The package is distributed as free software and can be downloaded from http://www.ime.unicamp.br/~martinez/packmol/.

Keywords: Initial configuration, molecular dynamics, packing, large-scale optimization, PACKMOL.

Full text: [pdf]

Abstract: The Reverse Engineering problem addressed in the present research consists in estimating the thicknesses and the optical parameters of two thin films deposited on a transparent substrate using only transmittance data through the whole stack. To the present author's knowledge this is the first report on the retrieval of the optical constants and the thickness of multiple film structures using transmittance data only. The same methodology may be used if the available data correspond to normal reflectance. The software used in this work is freely available through the PUMA Project web page (http://www.ime.usp.br/~egbirgin/puma/).

Keywords: Optical constants, thin films, optimization, numerical algorithms, Reverse Engineering.

Full text: [pdf] [ps]

Abstract: 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 ten years due to the comparative success of Interior-Point Newtonian algorithms, which are asymptotically faster. In the present 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 KKT system identified by the Augmented Lagrangian algorithm. The software used in this work is freely available through the TANGO Project web page.

Keywords: Nonlinear programming, Augmented Lagrangian methods, Interior-Point methods, Newton's method, experiments.

Full text: [pdf] [ps]

Abstract: 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 of the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the CUTE collection are presented.

Keywords: Nonlinear programming, Augmented Lagrangian methods, box constraints, quasi-Newton, truncated-Newton.

Full text: [pdf] [ps]

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

Keywords: Packing of circles and spheres, models, algorithms, nonlinear programming.

Full text: [pdf] [ps]

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

Keywords: Nonlinear programming, Augmented Lagrangian methods, KKT systems, numerical experiments.

Full text: [pdf] [ps]

Abstract: Augmented Lagrangian methods with general lower-level constraints are considered in the present research. These methods are useful when efficient algorithms exist for solving subproblems where the constraints are only of the lower-level type. Two methods of this class are introduced and analyzed. Inexact resolution of the lower-level constrained subproblems is considered. Global convergence is proved using the Constant Positive Linear Dependence constraint qualification. Conditions for boundedness of the penalty parameters are discussed. The reliability of the approach is tested by means of an exhaustive comparison against Lancelot. All the problems of the Cute collection are used in this comparison. Moreover, the resolution of location problems in which many constraints of the lower-level set are nonlinear is addressed, employing the Spectral Projected Gradient method for solving the subproblems. Problems of this type with more than $3 \times 10^6$ variables and $14 \times 10^6$ constraints are solved in this way, using moderate computer time.

Keywords: Nonlinear programming, Augmented Lagrangian methods, global convergence, constraint qualifications, numerical experiments.

Full text: [pdf] [ps]

Abstract: A new method is introduced for packing objects in convex regions of the Euclidian n-dimensional space. By means of this approach the packing problem becomes a global finite-dimensional continuous optimization problem. The strategy is based on the new concept of sentinels sets. Sentinels sets are finite subsets of the objects to be packed such that when two objects are superposed at least one sentinel of one object is in the interior of the other. Minimal sets of sentinels are found in simple 2-dimensional cases. Numerical experiments and pictures showing the potentiality of the new technique are presented.

Keywords: Sentinels, packing problems, cutting problems, models, nonlinear programming.

Full text: [pdf] [ps]

Abstract: The orthogonal packing of rectangular items in an arbitrary convex region is considered in this work. The packing problem is modeled as the problem of deciding for the feasibility or infeasibility of a set of nonlinear equality and inequality constraints. A procedure based on nonlinear programming is introduced and numerical experiments which show that the new procedure is reliable are exhibited.

Keywords: Packing of rectangles, orthogonal packing, feasibility problems, models, nonlinear programming.

Full text: [pdf] [ps]

Abstract: Local convergence of an inexact-restoration method for nonlinear programming is proved. Numerical experiments are performed with the objective of evaluating the behavior of the purely local method against a globally convergent nonlinear-programming algorithm.

Keywords: Inexact-restoration method, nonlinear programming, local convergence, numerical experiments.

Full text: [pdf] [ps]

See also the Technical Report (extended version of the published article) [pdf] [ps]

Abstract: An L-approach for packing (l,w)-rectangles into an (L,W)-rectangle was introduced in [L. Lins, S. Lins and R. Morabito, An L-approach for packing (l,w)-rectangles into rectangular and L-shaped pieces, Journal of the Operational Research Society 54, pp. 777-789, 2003]. The authors of that paper conjecture that the L-approach is exact and point out its runtime requirements as the main drawback. In this note it is shown that, by simply using a different data structure, the runtime is considerably reduced in spite of larger (but affordable) memory requirements. This reduction is important for practical purposes since it makes the algorithm much more acceptable for supporting actual decisions in pallet loading. Intensive numerical experiments showing the efficiency and effectiveness of the algorithm are presented.

Keywords: Cutting and packing, pallet and container loading, recursive algorithm, implementation.

Full text: [pdf] [ps]

Abstract: The present work considers the problem of estimating the thickness and the optical constants (extinction coefficient and refractive index) of thin films from the spectrum of normal reflectance R. This is an ill-conditioned highly underdetermined inverse problem. The estimation is done in the spectral range where the film is not opaque. The idea behind the choice of this particular spectral range is to compare the film characteristics retrieved from transmittance T and from reflectance data. In the first part of the paper a compact formula for R is deduced. The approach to deconvolute the R data is to use well known information on the dependence of the optical constants on photon energy of semiconductors and dielectrics and to formulate the estimation as a nonlinear optimization problem. Previous publications of the group on the subject provide guidelines for designing the new procedures. The consistency of the approach is tested with computer generated thin films and also with measured R and T spectral data of an a-Si:H film deposited onto glass. The results on gedanken films and onto a-Si:H indicate a very good agreement between expected and retrieved values.

Keywords: Optical constants, thin films, reflectance, optimization, numerical algorithms.

Full text: [pdf] [ps]

Abstract: A practical active-set method for bound-constrained minimization is introduced. Within the current face the classical Euclidian trust-region method is employed. Spectral projected gradient directions are used to abandon faces. Numerical results are presented.

Keywords: Bound-constrained optimization, projected gradient, spectral gradient, trust regions.

Full text: [pdf] [ps]

Abstract: Augmented Lagrangian algorithms are very popular tools for solving nonlinear programming problems. At each outer iteration of these methods a simpler optimization problem is solved, for which efficient algorithms can be used, especially when the problems are large. The most famous Augmented Lagrangian algorithm for minimization with inequality constraints is known as Powell-Hestenes-Rockafellar (PHR) method. The main drawback of PHR is that the objective function of the subproblems is not twice continuously differentiable. This is the main motivation for the introduction of many alternative Augmented Lagrangian methods. Most of them have interesting interpretations as proximal point methods for solving the dual problem, when the original nonlinear programming problem is convex. In this paper a numerical comparison between many of these methods is performed using all the suitable problems of the CUTE collection.

Keywords: Nonlinear programming, Augmented Lagrangian methods, inequality constraints, benchmarking, algorithms.

Full text: [pdf] [ps]

Abstract: Dykstra's algorithm is a suitable alternating projection scheme for solving the optimization problem of finding the closest point to a given one onto the intersection of a finite number of closed and convex sets. It has been recently used in a wide variety of applications. However, in practice, the commonly used stopping criteria are not robust and could stop the iterative process prematurely at a point that does not solve the optimization problem. In this work we present a counter example to illustrate the weakness of the commonly used criteria, and then we develop full-proof stopping rules. Additional experiments are shown to illustrate the advantages of this new stopping criteria, including their associated computational cost.

Keywords: Convex optimization, alternating projection methods, Dykstra's algorithm, stopping criteria.

Full text: [pdf] [ps]

Abstract: A family of variable metric methods for convex constrained optimization was introduced recently by Birgin, Martínez and Raydan. One of the members of this family is the Inexact Spectral Projected Gradient (ISPG) method for minimization with convex constraints. At each iteration of these methods a strictly convex quadratic function with convex constraints must be (inexactly) minimized. In the case of ISPG it was shown that, in some important applications, iterative projection methods can be used for this minimization. In this paper the particular case in which the convex domain is a polytope described by a finite set of linear inequalities is considered. For solving the linearly constrained convex quadratic subproblem a dual approach is adopted, by means of which subproblems become (not necessarily strictly) convex quadratic minimization problems with box constraints. For solving this problem, we use an active-set box-constraint quadratic optimizer with a proximal-point type unconstrained algorithm for minimization within the current faces. Convergence results and numerical experiments are presented.

Keywords: Linearly-constrained optimization, projected gradient, nonmonotone line search, spectral gradient.

Full text: [pdf] [ps]

Abstract: The container loading problem has important industrial and commercial applications. An increase in the number of items in a container leads to a decrease in cost. For this reason the related optimization problem is of economic importance. In this work, a procedure based on a nonlinear decision problem to solve the cylinder packing problem with identical diameters is presented. This formulation is based on the fact that the centers of the cylinders have to be inside the rectangular box defined by the base of the container (a radius far from the frontier) and far from each other at least one diameter. With this basic premise the procedure tries to find the maximum number of cylinder centers that satisfy these restrictions. The continuous nature of the problem is one of the reasons that motivated this study. A comparative study with other methods of the literature is presented and better results are achieved.

Keywords: Cylinder packing, rectangular container, circular container, nonlinear programming, bound-constrained minimization, convex-constrained minimization.

Full text: [pdf] [ps]

Abstract: A new method is introduced for large scale convex constrained optimization. The general model algorithm involves, at each iteration, the approximate minimization of a convex quadratic on the feasible set of the original problem and global convergence is obtained by means of nonmonotone line searches. A specific algorithm, the Inexact Spectral Projected Gradient method (ISPG), is implemented using inexact projections computed by Dykstra's alternating projection method and generates interior iterates. The ISPG method is a generalization of the Spectral Projected Gradient method (SPG), but can be used when projections are difficult to compute. Numerical results for constrained least-squares rectangular matrix problems are presented.

Keywords: Convex constrained optimization, Projected gradient, nonmonotone line search, spectral gradient, Dykstra's algorithm.

Full text: [pdf] [ps]

Abstract: In recent papers, the problem of estimating the thickness and the optical constants (refractive index and absorption coefficient) of thin films using only transmittance data has been addressed by means of optimization techniques. Models were proposed for solving this problem using linearly constrained optimization and unconstrained optimization. However, the optical parameters of ``very thin'' films could not be recovered with methods that are successful in other situations. Here we introduce an optimization technique that seems to be efficient for recovering the parameters of very thin films.

Keywords: Optical constants, thin films, optimization, numerical algorithms.

Full text: [pdf] [ps]

Abstract: Large scale nonlinear systems of equations can be solved by means of inexact quasi-Newton methods. A global convergence theory is introduced that guarantees that, under reasonable assumptions, the algorithmic sequence converges to a solution of the problem. Under additional standard assumptions, superlinear convergence is preserved.

Keywords: Nonlinear systems, inexact Newton methods, global convergence, superlinear convergence, quasi-Newton methods.

Full text: [pdf] [ps]

Abstract: In a recent paper, the authors introduced a method to estimate optical parameters of thin films using transmission data. The associated model assumes that the film is deposited on a completely transparent substrate. It has been observed, however, that small absorption of substrates affect in a nonnegligible way the transmitted energy. The question arises of the reliability of the estimation method to retrieve optical parameters in the presence of substrates of different thicknesses and absorption degrees. In this paper, transmission spectra of thin films deposited on non-transparent substrates are generated and, as a first approximation, the method based on transparent substrates is used to estimate the optical parameters. As expected, the method is good when the absorption of the substrate is very small, but fails when one deals with less transparent substrates. To overcome this drawback, an iterative procedure is introduced, that allows one to approximate the transmittance with transparent substrate, given the transmittance with absorbent substrate. The updated method turns out to be almost as efficient in the case of absorbent substrates as it was in the case of transparent ones.

Keywords: Optimization, estimation of parameters, unconstrained minimization, constrained optimization, thin films, optical constants, transmittance.

Full text: [pdf] [ps]

Abstract: Nonlinear systems of equations often represent mathematical models of chemical production processes and other engineering problems. Homotopic techniques (in particular, the bounded homotopies introduced by Paloschi) are used for enhancing convergence to solutions, especially when a good initial estimate is not available. In this paper, the homotopy curve is considered as the feasible set of a mathematical programming problem, where the objective is to find the optimal value of the homotopic parameter. Inexact restoration techniques can then be used to generate approximations in a neighborhood of the homotopy, the size of which is theoretically justified. Numerical examples are given.

Keywords: Nonlinear programming, nonlinear systems, homotopies, bounded homotopies, homotopy methods, inexact restoration.

Full text: [pdf] [ps]

Abstract: A practical problem that requires the classification of a set of points of Rⁿ using a criterion not sensitive to bounded outliers is studied in this paper. A fixed-point (k-means) algorithm is defined that uses an arbitrary distance function. Finite convergence is proved. A robust distance defined by Boente, Fraiman and Yohai is selected for applications. Smooth approximations of this distance are defined and suitable heuristics are introduced to enhance the probability of finding global optimizers. A real-life example is presented and commented.

Keywords: Nonlinear programming, heuristics, clustering, classification, fixed points.

Full text: [pdf] [ps]

Abstract: This contribution addresses the relevant question of retrieving, from transmittance data, the optical constants and thickness of very thin semiconductor and dielectric films. The retrieval process looks for a thickness that, subject to the physical input of the problem, minimizes the difference between the measured and the theoretical spectra. This is a highly underdetermined problem but, the use of approximate - though simple - functional dependences of the index of refraction and of the absorption coefficient on photon energy, used as an a priori information, allows surmounting the ill-posedness of the problem. The method is illustrated with the analysis of transmittance data of very thin amorphous silicon films. The method allows retrieving physically meaningful solutions for films as thin as 300 A. The estimated parameters agree well with known data or with optical parameters measured by independent methods. The limitations of the adopted model and the shortcomings of the optimization algorithm are presented and discussed.

Keywords: Optical constants, thin films, optimization, numerical algorithms.

Full text: [pdf] [ps]

Abstract: A new active-set method for smooth box-constrained minimization is introduced. The algorithm combines an unconstrained method, including a new line-search which aims to add many constraints to the working set at a single iteration, with a recently introduced technique (spectral projected gradient) for dropping constraints from the working set. Global convergence is proved. A computer implementation is fully described and a numerical comparison assesses the reliability of the new algorithm.

Keywords: Box-constrained minimization, numerical methods, active-set strategies, Spectral Projected Gradient.

Full text: [pdf] [ps]

Abstract: A Fortran 77 software which implements the SPG method is introduced. SPG is a nonmonotone projected gradient algorithm for solving large-scale convex-constrained optimization problems. It combines the classical projected gradient method with the spectral gradient choice of steplength and a nonmonotone line search strategy. Implementation details are presented and the usage of the software is described. Some new numerical tests that have been recently performed are reported. The main conclusion is that SPG compares favorably with existing software.

Keywords: Projected gradients, nonmonotone line search, large-scale problems, bound constrained problems, spectral gradient method.

Full text: [pdf] [ps]

Abstract: A practical algorithm for box-constrained optimization is introduced. The algorithm combines an active-set strategy with spectral projected gradient iterations. In the interior of each face a strategy that deals efficiently with negative curvature is employed. Global convergence results are given. Numerical results are presented.

Keywords: Box constrained minimization, active set methods, spectral projected gradients, dogleg path methods.

Full text: [pdf] [ps]

Abstract: A family of scaled conjugate-gradient algorithms for large-scale unconstrained minimization is defined. The Perry, the Polak-Ribièere and the Fletcher-Reeves formulae are compared using a spectral scaling derived from Raydan's spectral gradient optimization method. The best combination of formula, scaling and initial choice of step-length is compared against well known algorithms using a classical set of problems. An additional comparison involving an ill-conditioned estimation problem in Optics is presented.

Keywords: Unconstrained minimization, spectral gradient method, conjugate gradients.

Full text: [pdf] [ps]

Abstract: This work presents the first application of a recently developed numerical method to determine the thickness and the optical constants of thin films using experimental transmittance data only. The new method may be applied to films not displaying a fringe pattern and is shown to work for a-Si:H layers as thin as 100 nm. The performance and limitations of the method are discussed on the basis of experiments performed on a series of six a-Si:H samples grown under identical conditions, but with thickness varying from 98 nm to 1.2 mu m.

Keywords: Thin films, optical constants, a-Si:H films, unconstrained minimization.

Full text: [pdf] [ps]

Abstract: Nonmonotone projected gradient techniques are considered for the minimization of differentiable functions on closed convex sets.  The classical projected gradient schemes are extended to include a nonmonotone steplength strategy that is based on the Grippo-Lampariello-Lucidi nonmonotone line search. In particular, the nonmonotone strategy is combined with the spectral gradient choice of steplength to accelerate the convergence process. In addition to the classical projected gradient nonlinear path, the feasible spectral projected gradient is used as a search direction to avoid additional trial projections during the one-dimensional search process. Convergence properties and extensive numerical results are presented.

Keywords: Projected gradients, nonmonotone line search, large scale problems, bound constrained problems, spectral gradient method.

Full text: [pdf] [ps]

Abstract: For a fixed, central ray in an isotropic elastic or acoustic media, traveltime moveouts of rays in its vicinity can be described in terms of a certain number of parameters that refer to the central ray only. The determination of these parameters out of multi-coverage data leads to very powerful algorithms that can be used for several imaging and inversion processes. Assuming two-dimensional propagation, the traveltime expressions depend on three parameters directly related to the geometry of the unknown model in the vicinity of the central ray. We present a new method to extract these parameters out of coherency analysis applied directly to the data. It uses (a) fast one-parameter searches on different sections extracted from the multi-coverage data to derive initial values of the sections parameters, and (b) the application of a recently introduced Spectral Projected Gradient optimization algorithm for the final parameter estimation. Application of the method on a synthetic example shows an excellent performance of the algorithm both in accuracy and efficiency. The results obtained so far indicate that the algorithm may be a feasible option to solve the corresponding, harder, full three-dimensional problem, in which eight parameters, instead of three, are required.

Keywords: Multi-coverage data, Common Reflection Surface method, hyperbolic traveltime, coherency function, optimization, Spectral Projected Gradient method.

Full text: [pdf] [ps]

Abstract: The problem of estimating the thickness and the optical constants of thin films using transmission data only is very challenging from the mathematical point of view, and has a technological and an economic importance. In many cases it represents a very ill-conditioned inverse problem with many local-nonglobal solutions. In a recent publication we proposed nonlinear programming models for solving this problem.Well-known software for linearly constrained optimization was used with success for this purpose. In this paper we introduce an unconstrained formulation of the nonlinear programming model and we solve the estimation problem using a method based on repeated calls to a recently introduced unconstrained minimization algorithm. Numerical experiments on computer-generated films show that the new procedure is reliable.

Keywords: Unconstrained minimization, spectral gradient method, optical constants, thin films.

Full text: [pdf] [ps]

Abstract: Automatic differentiation is used for the solution of optimal control problems. The original problem is reduced to a nonlinear programming problem using general Runge-Kutta integration formulas. Canonical formulas which use a fast automatic differentiation strategy are given to compute derivatives of the goal function.

Keywords: Automatic differentiation, optimal control problem, Runge-Kutta integration methods.

Full text: [pdf] [ps]

Abstract: Automatic differentiation and nonmonotone spectral projected gradient techniques are used for solving optimal control problems. The original problem is reduced to a nonlinear programming one using general Runge-Kutta integration formulas. Canonical formulas which use a fast automatic differentiation strategy are given to compute derivatives of the objective function. On the basis of this approach, codes for solving optimal control problems are developed and some numerical results are presented.

Keywords: Automatic differentiation, Spectral Projected Gradient, nonmonotone line search, optimal control problem, software for optimal control problems, Runge-Kutta integration methods.

Full text: [pdf] [ps]