This article defines an efficient subspace method, called SSDFO , for unconstrained derivative-free optimization problems where the gradients of the objective function are Lipschitz continuous but only exact function values are available. SSDFO employs line searches along directions constructed on the basis of quadratic models. These approximate the objective function in a subspace spanned by some previous search directions. A worst-case complexity bound on the number of iterations and function evaluations is derived for a basic algorithm using this technique. Numerical results for a practical variant with additional heuristic features show that, on the unconstrained CUTEst test problems, SSDFO has superior performance compared to the best solvers from the literature.

Abstract This paper suggests a new limited memory trust region algorithm for large unconstrained black box least squares problems, called LMLS. Main features of LMLS are a new non-monotone technique, a new adaptive radius strategy, a new Broyden-like algorithm based on the previous good points, and a heuristic estimation for the Jacobian matrix in a subspace with random basis indices. Our numerical results show that LMLS is robust and efficient, especially in comparison with solvers using traditional limited memory and standard quasi-Newton approximations.

We consider square, sparse nonlinear systems of equations whose Jacobian is structurally nonsingular, with reasonable bound constraints on all variables. We propose an algorithm for finding good approximations to all well-separated solutions of such systems. We assume that the input system is ordered such that its Jacobian is in bordered block lower triangular form with small diagonal blocks and with small border width; this can be performed fully automatically with off-the-shelf decomposition methods. Five decades of numerical experience show that models of technical systems tend to decompose favorably in practice. Once the block decomposition is available, we reduce the task of solving the large nonlinear system of equations to that of solving a sequence of low-dimensional ones. The most serious weakness of this approach is well-known: It may suffer from severe numerical instability. The proposed method resolves this issue with the novel backsolve step. We study the effect of the decomposition on a sequence of challenging problems. Beyond a certain problem size, the computational effort of multistart (no decomposition) grows exponentially. In contrast, thanks to the decomposition, for the proposed method the computational effort grows only linearly with the problem size. It depends on the problem size and on the hyperparameter settings whether the decomposition and the more sophisticated algorithm pay off. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size hyperparameter improves the robustness of the proposed method.

This paper considers the task of finding the smallest circle into which one can pack a fixed number of non-overlapping unit squares that are free to rotate. Due to the rotation angles, the packing of unit squares into a container is considerably harder to solve than their circle packing counterparts. Therefore, optimal arrangements were so far proved to be optimal only for one or two unit squares. By a computer-assisted method based on interval arithmetic techniques, we solve the case of three squares and find rigorous enclosures for every optimal arrangement of this problem. We model the relation between the squares and the circle as a constraint satisfaction problem (CSP) and found every box that may contain a solution inside a given upper bound of the radius. Due to symmetries in the search domain, general purpose interval methods are far too slow to solve the CSP directly. To overcome this difficulty, we split the problem into a set of subproblems by systematically adding constraints to the center of each square. Our proof requires the solution of 6, 43 and 12 subproblems with 1, 2 and 3 unit squares respectively. In principle, the method proposed in this paper generalizes to any number of squares.

One of the relevant research topics to which Chris Floudas contributed was quadratically constrained quadratic programming (QCQP). This paper considers one of the simplest hard cases of QCQP, the two trust region subproblem (TTRS). In this case, one needs to minimize a quadratic function constrained by the intersection of two ellipsoids. The Lagrangian dual of the TTRS is a semidefinite program (SDP) and this result has been extensively used to solve the problem efficiently. We focus on numerical aspects of branch-and-bound solvers with three goals in mind. We provide (i) a detailed analysis of the ability of state-of-the-art solvers to complete the global search for a solution, (ii) a quantitative approach for measuring the cluster effect on each solver and (iii) a comparison between the branch-and-bound and the SDP approaches. We perform the numerical experiments on a set of 212 challenging problems provided by Kurt Anstreicher. Our findings indicate that SDP relaxations and branch-and-bound have orthogonal difficulties, thus pointing to a possible benefit of a combined method. The following solvers were selected for the experiments: Antigone 1.1 , Baron 16.12.7 , Lindo Global 10.0 , Couenne 0.5 and SCIP 3.2 .

The paper describes improved analysis techniques for basis reduction that allow one to prove strong complexity bounds and reduced basis guarantees for traditional reduction algorithms and some of their variants. This is achieved by a careful exploitation of the linear equations and inequalities relating various bit sizes before and after one or more reduction steps.

An important aspect in the solution process of constraint satisfaction problems is to identify exclusion boxes which are boxes that do not contain feasible points. This paper presents a certificate of infeasibility for finding such boxes by solving a linearly constrained nonsmooth optimization problem. Furthermore, the constructed certificate can be used to enlarge an exclusion box by solving a nonlinearly constrained nonsmooth optimization problem.

We describe an asymptotically fast variant of the LLL lattice reduction algorithm. It takes as input a basis B ∈ Zn x n and returns a (reduced) basis C of the Euclidean lattice L spanned by B, whose first vector satisfies |c1| ≤ (1+c) (4/3)(n-1)/4 (det L)1/n for any fixed c>0. It terminates within O(n4+ε β1+ε) bit operations for any ε >0, with β = log maxi |bi|. It does rely on fast integer arithmetic but does not make use of fast matrix multiplication.

GLOBAL is a multi-start type stochastic method for bound constrained global optimization problems. Its goal is to find the best local minima that are potentially global. For this reason it involves a combination of sampling, clustering, and local search. The role of clustering is to reduce the number of local searches by forming groups of points around the local minimizers from a uniformly sampled domain and to start few local searches in each of those groups. We evaluate the performance of the GLOBAL algorithm on the BBOB 2009 noiseless testbed, containing problems which reflect the typical difficulties arising in real-world applications. The obtained results are also compared with those obtained form the simple multi-start procedure in order to analyze the effects of the applied clustering rule. An improved parameterization is introduced in the GLOBAL method and the performance of the new procedure is compared with the performance of the MATLAB GlobalSearch solver by using the BBOB 2010 test environment.

We examine symbolic tools associated with two modeling systems for mathematical programming, which can be used to automatically detect the presence or absence of convexity and concavity in the objective and constraint functions, as well as convexity of the feasible set in some cases. The coconut solver system [Schichl, H. 2004a. COCONUT: COntinuous CONstraints—Updating the technology] focuses on nonlinear global continuous optimization and possesses its own modeling language and data structures. The Dr. Ampl meta-solver [Fourer, R., D. Orban. 2007. Dr. Ampl—A meta solver for optimization. Technical Report G-2007-10, GERAD, Montréal] aims to analyze nonlinear differentiable optimization models and hooks into the ampl Solver Library [Gay, D. M. 2002. Hooking your solver to AMPL]. Our symbolic convexity analysis may be supplemented, when it returns inconclusive results, with a numerical phase that may detect nonconvexity. We report numerical results using these tools on sets of test problems for both global and local optimization.

The software package SNOBFIT for bound-constrained (and soft-constrained) noisy optimization of an expensive objective function is described. It combines global and local search by branching and local fits. The program is made robust and flexible for practical use by allowing for hidden constraints, batch function evaluations, change of search regions, etc.

This paper presents new, simple arguments improving the lower bounds for the total energy and the minimal inter-particle distance in minimal energy atom cluster problems with interactions given by a Morse potential, where the atom separation problem is difficult due to the finite energy at zero atom separation. Apart from being sharper than previously known bounds, they also apply for a wider range ρ ≥ 4.967 of the parameter in the Morse potential. Most results also hold for more general pair potentials.

In this paper, we demonstrate how methods based on interval arithmetic and interval analysis can be used to achieve numerical certification of the kinematic calibration of a parallel robots. We introduce our work by describing the usual calibration methods and the motivations for a numerical certification. Then, we briefly present the interval methods we used and the kinematic calibration problem. In the main part, we develop our certified approach of this problem in the case of a Gough platform, and we show with numerical examples how this approach avoids wrong solutions produced by classical approach. Details on implementation and performance are also given.

Focuses on the methods and application of optimization under uncertainty to radiation therapy planning, where it is natural and useful to model the uncertainty of the problem directly. In particular, we present methods for optimization under uncertainty in radiation therapy of tumors and compare their results. Two themes are developed in this study: (1) the modeling of inherent uncertainty of the problems and (2) the application of uncertainty optimization.

Dynamical characteristics of a complex system can often be inferred from analysis of a stochastic time series model fitted to observations of the system. Oscillations in geophysical systems, for example, are sometimes characterized by principal oscillation patterns, eigenmodes of estimated autoregressive (AR) models of first order. This paper describes the estimation of eigenmodes of AR models of arbitrary order. AR processes of any order can be decomposed into eigenmodes with characteristic oscillation periods, damping times, and excitations. Estimated eigenmodes and confidence intervals for the eigenmodes and their oscillation periods and damping times can be computed from estimated models parameters. As a computationally efficient method of estimating the parameters of AR models from high-dimensional data, a stepwise least squares algorithm is proposed. This algorithm computes models of successively decreasing order. Numerical simulations indicate that, with the least squares algorithm, the AR model coefficients and the eigenmodes derived from the coefficients and eigenmodes are rough approximations of the confidence intervals inferred from the simulaitons.

ARfit is a collection of Matlab modules for modeling and analyzing multivariate time series with autoregressive (AR) models. ARfit contains modules to given time series data, for analyzing eigen modes of a fitted model, and for simulating AR processes. ARfit estimates the parameters of AR models from given time series data with a stepwise least squares algorithm that is computationally efficient, in particular when the data are high-dimensional. ARfit modules construct approximate confidence intervals for the estimated parameters and compute statistics with which the adequacy of a fitted model can be assessed. Dynamical characteristics of the modeled time series can be examined by means of a decomposition of a fitted AR model into eigenmodes and associated oscillation periods, damping times, and excitations. The ARfit module that performs the eigendecomposition of a fitted model also constructs approximate confidence intervals for the eigenmodes and their oscillation periods and damping times.

The authors propose a new way to iteratively solve large scale ill-posed problems and in particular the image reconstruction problem in positron emission tomography by exploiting the relation between Tikhonov regularization and multiobjective optimization to obtain iteratively approximations to the Tikhonov L-curve and its corner. Monitoring the change of the approximate L-curves allows the authors to adjust the regularization parameter adaptively during a preconditioned conjugate gradient iteration, so that the desired solution can be reconstructed with a small number of iterations.