Publications

Quasi-Newton methods are well known techniques for large-scale numerical optimization. They use an approximation of the Hessian in optimization problems or the Jacobian in system of nonlinear equations. In the Interior Point context, quasi-Newton algorithms compute low-rank updates of the matrix associated with the Newton systems, instead of computing it from scratch at every iteration. In this work, we show that a simplified quasi-Newton primal-dual interior point algorithm for linear programming enjoys polynomial worst-case iteration complexity. Feasible and infeasible cases of the algorithm are considered and the most common neighborhoods of the central path are analyzed. To the best of our knowledge, this is the first attempt to deliver polynomial worst-case iteration complexity bounds for these methods. Unsurprisingly, the worst-case complexity results obtained when quasi-Newton directions are used are worse than their counterparts when Newton directions are employed. However, quasi-Newton updates are very attractive for large-scale optimization problems where the cost of factorizing the matrices is much higher than the cost of solving linear systems.

Complexity analysis has become an important tool in the convergence analysis of optimization algorithms. For derivative-free optimization algorithms, it is not different. Interestingly, several constants that appear when developing complexity results hide the dimensions of the problem. This work organizes several results in literature about bounds that appear in derivative-free trust-region algorithms based on linear and quadratic models. All the constants are given explicitly by the quality of the sample set, dimension of the problem and number of sample points. We extend some results to allow "inexact" interpolation sets. We also provide a clearer proof than those already existing in literature for the underdetermined case.

* The submitted version has not undergone peer review (when applicable) or any post-submission improvements or corrections. The Version of Record of this article is published in Optimization Letters, and is available online at https://doi.org/10.1007/s11590-024-02147-4 .

In this paper, we present the online tool salaplanejada.unifesp.br developed to assist the layout planning of classrooms considering the social distance in the context of the COVID-19 pandemic. We address both the allocation problem in rooms where seats are fixed as well as the problem in rooms where seats can be moved freely. For the first case, we use two integer optimization models and discussed some curiosities about the solutions found. For the case of mobile seats, we handle the problem with circle packing techniques using continuous non-linear optimization. For these problems we propose a new model and algorithms to solve the problem, similar to other packing problems in the literature. In addition, we propose a heuristic that provides not only a good starting point for the optimization procedure but also a configuration ensuring the students positions in lines, that may be of interest to the user. Some computational results are presented to illustrate the numerical behavior of the algorithms and models.

The development of Pickering emulsions as ecologically correct stabilized with bio-based material by substituting synthetic petroleum-derived tensoactives assumed a very attractive level, representing the current guideline of the global market for homecare industry, food and beverage applications. In this wor, cellulose nanocrystals (CNCs), a hierarchically advanced biomaterial, were produced to stabilize innovative emulsions formulated with western soapberry Sapindus saponaria L. oil (SO). Besides, green surfactants (triterpene saponins extracted from S. saponaria L. pericarp; SAP) were also investigated to stabilize the oil/water interface. The synergistic combination between cellulose nanowhiskers and the bioactive glycosides has never been reported in the literature. Dynamic interfacial tensions of SAP and SO were firstly investigated, and their capacity to form a plastic membrane at oil/water interface was revealed. Response surface methodology (RSM) was employed to study the influence of the binary systems (CNC:SAP) on the stability of emulsified systems, such as size and zeta potential. In addition, a new calculation was proposed to determine the coverage of the oil droplets formed by the mixture of cellulose crystallites and natural surfactants. The optimal nanoemulsion composition was determined to be 60 w/w (%) of water, 23.905 w/w % of SO, 5 w/w % of CNC and 8.095 w/w% of SAP to produce of smallest droplet (165.1 nm) combined with higher zeta potential module (-46.7 mV). Results highlight the potential of Sapindus saponins and cellulose nanowhiskers for efficient producing label-friendly nanoemulsions applicable for drug, cosmeceutical or edible delivery systems

The robust adjustment of nonlinear models to data is considered in this paper. When data comes from real experiments, it is possible that measurement errors cause the appearance of discrepant values, which should be ignored when adjusting models to them. This work presents a Lower Order-value Optimization (LOVO) version of the Levenberg-Marquardt algorithm, which is well suited to deal with outliers in fitting problems. A general algorithm is presented and convergence to stationary points is demonstrated. Numerical results show that the algorithm is successfully able to detect and ignore outliers without too many specific parameters. Parallel and distributed executions of the algorithm are also possible, allowing for the use of larger datasets. Comparison against publicly available robust algorithms shows that the present approach is able to find better adjustments in well known statistical models.

* This is a pre-print of an article published in Journal of Global Optimization. The final authenticated version is available online at: https://doi.org/10.1007/s10898-020-00970-4 .

RAFF.jl is a Julia package for the adjustment of a function to a dataset coming from some experiment. This package is an alternative to classical adjustment techniques such as linear and nonlinear regression. The goal of this package is to find robust adjustments free from the influence of possible outliers (discrepant points of the adjustment).

Interior Point Methods (IPM) rely on the Newton method for solving systems of nonlinear equations. Solving the linear systems which arise from this approach is the most computationally expensive task of an interior point iteration. If, due to problem's inner structure, there are special techniques for efficiently solving linear systems, IPMs enjoy fast convergence and are able to solve large scale optimization problems. It is tempting to try to replace the Newton method by quasi-Newton methods. Quasi-Newton approaches to IPMs either are built to approximate the Lagrangian function for nonlinear programming problems or provide an inexpensive preconditioner. In this work we study the impact of using quasi-Newton methods applied directly to the nonlinear system of equations for general quadratic programming problems. The cost of each iteration can be compared to the cost of computing correctors in a usual interior point iteration. Numerical experiments show that the new approach is able to reduce the overall number of matrix factorizations and is suitable for a matrix-free implementation.

*The Technical Report is a pre-print of an article published in Computational Optimization and Applications. The final authenticated version is freely available online at: https://doi.org/10.1007/s10589-019-00102-z.

The discovery and characterization of driving behavior profiles can be useful to support the optimization of processes for insurance companies or fleet managers. The evolution of ubiquitous computing and data analysis techniques have made such tasks possible. In this paper, we present a study on the analysis of driving behavior through clustering algorithms on a real-world dataset. We applied the k-Means++ and Spectral Clustering algorithms that came up with results that showed: the existence of less and more aggressive behavior profiles; potential to discover more profiles since preliminary quantitative evaluation indicated good quality in clustering with four profiles.

In this work we present an algorithm for solving constrained optimization problems that does not make explicit use of the objective function derivatives. The algorithm mixes an inexact restoration framework with filter techniques, where the forbidden regions can be given by the flat or slanting filter rule. Each iteration is decomposed in two independent phases: a feasibility phase which reduces an infeasibility measure without evaluations of the objective function, and an optimality phase which reduces the objective function value. As the derivatives of the objective function are not available, the optimality step is computed by derivative-free trust-region internal iterations. Any technique to construct the trust-region models can be used since the gradient of the model is a reasonable approximation of the gradient of the objective function at the current point. Assuming this and classical assumptions, we prove that the full steps are efficient in the sense that near a feasible nonstationary point, the decrease in the objective function is relatively large, ensuring the global convergence results of the algorithm. Numerical experiments show the effectiveness of the proposed method.

A new method is introduced for solving constrained optimization problems in which the derivatives of the constraints are available but the derivatives of the objective function are not. The method is based on the Inexact Restoration framework, by means of which each iteration is divided in two phases. In the first phase one considers only the constraints, in order to improve feasibility. In the second phase one minimizes a suitable objective function subject to a linear approximation of the constraints. The second phase must be solved using derivative-free methods. An algorithm introduced recently by Kolda, Lewis, and Torczon for linearly constrained derivative-free optimization is employed for this purpose. Under usual assumptions, convergence to stationary points is proved. A computer implementation is described and numerical experiments are presented.

Many derivative-free methods for constrained problems are not efficient for minimizing functions on \"thin\" domains. Other algorithms, like those based on Augmented Lagrangians, deal with thin constraints using penalty-like strategies. When the constraints are computationally inexpensive but highly nonlinear, these methods spend many potentially expensive objective function evaluations motivated by the difficulties of improving feasibility. An algorithm that handles efficiently this case is proposed in this paper. The main iteration is split into two steps: restoration and minimization. In the restoration step the aim is to decrease infeasibility without evaluating the objective function. In the minimization step the objective function f is minimized on a relaxed feasible set. A global minimization result will be proved and computational experiments showing the advantages of this approach will be presented.

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.

RAFF.jl is a Julia package for the adjustment of a function to a dataset coming from some experiment. This package is an alternative to classical adjustment techniques such as linear and nonlinear regression. The goal of this package is to find robust adjustments free from the influence of possible outliers (discrepant points of the adjustment).

Derivative-free optimization problems arise from models whose derivatives of some functions are not available. This information is unavailable due to extremely complex and black-box functions, originated from simulation procedures, or even to user inability. Following the growth in the number of applications, the number of derivative-free algorithms has increased in the last years. However, few algorithms are able to handle thin feasible domains efficiently, for example, in the presence of equality nonlinear constraints. In the present work, we describe the theory and implementation of two algorithms capable of dealing with thin-constrained derivative-free problems. Their definition considers that the objective function evaluation is the most expensive part of the problem. Based on this principle, the process of solving a problem is split into two phases. In the restoration phase, we try to improve the feasibility without evaluating the objective function. In the minimization phase, the aim is to decrease the objective function value by using well-established algorithms in order to solve derivative-free problems with simple constraints. The first algorithm uses Inexact Restoration ideas together with a decreasing infeasibility tolerance. Under the usual hypotheses of direct search methods, we show global minimization results. The second algorithm extends to the derivative-free case all the theoretical results obtained in a recent line-search Inexact Restoration algorithm. In this approach, only the derivatives of the objective function are not available. We perform numerical experiments to show the advantages of each algorithm, in particular when comparing with penalty-like algorithms.

In problems of hierarchical nature, the choices made by the most influential level - the so-called leader - affect the behavior of the lower levels. For each one of the leader's decisions there is a response from the lower levels, which maximizes the value of their respective objectives. These optimal choices, in return, may have influence in the results achieved by the leader, which also wants to make the optimal choices. In mathematical programming, this kind of problem is described as a multilevel programming problem. The present work considers a specific kind of multilevel problem: the bilevel mathematical problem. We study a resolution technique which consists in replacing the lower level problem by its necessary first order conditions, which can be formulated in various ways, as complementarity constraints occur and are modified. The new reformulated problem is a nonlinear programming problem which can be solved by classical optimization methods. Using first and second order optimality conditions, we show the relations between the original bilevel problem and the reformulated problem. We apply the described technique to solve a set of bilevel problems taken from the literature, analyse their behavior and discuss strategies to prevent undesirable difficulties that may arise.