Search

We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same global optimum as the original problem. This success probability is then used to show almost sure convergence of X-REGO to an approximate global solution of the original problem, under weak assumptions on the problem (having a strictly feasible global solution) and on the solver (guaranteed to find an approximate global solution of the reduced problem with sufficiently high probability). In the particular case of unconstrained objectives with low effective dimension, we propose an X-REGO variant that explores random subspaces of increasing dimension until finding the effective dimension of the problem, leading to X-REGO globally converging after a finite number of embeddings, proportional to the effective dimension. We show numerically that this variant efficiently finds both the effective dimension and an approximate global minimizer of the original problem. [ABSTRACT FROM AUTHOR]

We introduce a general framework for large-scale model-based derivative-free optimization based on iterative minimization within random subspaces. We present a probabilistic worst-case complexity analysis for our method, where in particular we prove high-probability bounds on the number of iterations before a given optimality is achieved. This framework is specialized to nonlinear least-squares problems, with a model-based framework based on the Gauss–Newton method. This method achieves scalability by constructing local linear interpolation models to approximate the Jacobian, and computes new steps at each iteration in a subspace with user-determined dimension. We then describe a practical implementation of this framework, which we call DFBGN. We outline efficient techniques for selecting the interpolation points and search subspace, yielding an implementation that has a low per-iteration linear algebra cost (linear in the problem dimension) while also achieving fast objective decrease as measured by evaluations. Extensive numerical results demonstrate that DFBGN has improved scalability, yielding strong performance on large-scale nonlinear least-squares problems. [ABSTRACT FROM AUTHOR]

We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms for the global optimization of these special-structure problems. A reduced subproblem formulation is investigated that solves the original problem over a random low-dimensional subspace subject to affine constraints, so as to preserve feasibility with respect to the given domain. Under reasonable assumptions, we show that the probability that the reduced problem is successful in solving the original, full-dimensional problem is positive. Furthermore, in the case when the objective's effective subspace is aligned with the coordinate axes, we provide an asymptotic bound on this success probability that captures its polynomial dependence on the effective and, surprisingly, ambient dimensions. We then propose X-REGO, a generic algorithmic framework that uses multiple random embeddings, solving the above reduced problem repeatedly, approximately and possibly, adaptively. Using the success probability of the reduced subproblems, we prove that X-REGO converges globally, with probability one, and linearly in the number of embeddings, to an ϵ -neighbourhood of a constrained global minimizer. Our numerical experiments on special structure functions illustrate our theoretical findings and the improved scalability of X-REGO variants when coupled with state-of-the-art global—and even local—optimization solvers for the subproblems. [ABSTRACT FROM AUTHOR]

We investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is formulated as the rank minimization of a nonlinear feature map applied to the original matrix, which is then further approximated by a constrained non-convex optimization problem involving the Grassmann manifold. We propose two sets of algorithms, one arising from Riemannian optimization and the other as an alternating minimization scheme, both of which include first- and second-order variants. Both sets of algorithms have theoretical guarantees. In particular, for the alternating minimization, we establish global convergence and worst-case complexity bounds. Additionally, using the Kurdyka-Lojasiewicz property, we show that the alternating minimization converges to a unique limit point. We provide extensive numerical results for the recovery of union of subspaces and clustering under entry sampling and dense Gaussian sampling. Our methods are competitive with existing approaches and, in particular, high accuracy is achieved in the recovery using Riemannian second-order methods. [ABSTRACT FROM AUTHOR]

The skill of global ocean biogeochemical models, and the earth system models in which they are embedded, can be improved by systematic calibration of the parameter values against observations. However, such tuning is seldom undertaken as these models are computationally very expensive. Here we investigate the performance of DFO-LS, a local, derivative-free optimisation algorithm which has been designed for computationally expensive models with irregular model–data misfit landscapes typical of biogeochemical models. We use DFO-LS to calibrate six parameters of a relatively complex global ocean biogeochemical model (MOPS) against synthetic dissolved oxygen, phosphate and nitrate "observations" from a reference run of the same model with a known parameter configuration. The performance of DFO-LS is compared with that of CMA-ES, another derivative-free algorithm that was applied in a previous study to the same model in one of the first successful attempts at calibrating a global model of this complexity. We find that DFO-LS successfully recovers five of the six parameters in approximately 40 evaluations of the misfit function (each one requiring a 3000-year run of MOPS to equilibrium), while CMA-ES needs over 1200 evaluations. Moreover, DFO-LS reached a "baseline" misfit, defined by observational noise, in just 11–14 evaluations, whereas CMA-ES required approximately 340 evaluations. We also find that the performance of DFO-LS is not significantly affected by observational sparsity, however fewer parameters were successfully optimised in the presence of observational uncertainty. The results presented here suggest that DFO-LS is sufficiently inexpensive and robust to apply to the calibration of complex, global ocean biogeochemical models. [ABSTRACT FROM AUTHOR]

We investigate the potential of applying a state-of-the-art, local derivative-free solver, Py-BOBYQA to global optimization problems. In particular, we demonstrate the potential of a restarts procedure – as distinct from multistart methods – to allow Py-BOBYQA to escape local minima (where ordinarily it would terminate at the first local minimum found). We also introduce an adaptive variant of restarts which yields improved performance on global optimization problems. As Py-BOBYQA is a model-based trust-region method, we compare largely with other global optimization methods for which (global) models are important, such as Bayesian optimization and response surface methods; we also consider state-of-the-art representative deterministic and stochastic codes, such as DIRECT and CMA-ES. We find numerically that the restarts procedures in Py-BOBYQA are effective at helping it to escape local minima, when compared to using no restarts in Py-BOBYQA. Additionally, we find that Py-BOBYQA with adaptive restarts has comparable performance with global optimization solvers for all accuracy/budget regimes, in both smooth and noisy settings. In particular, Py-BOBYQA variants are best performing for smooth and multiplicative noise problems in high-accuracy regimes. As a by-product, some preliminary conclusions can be drawn on the relative performance of the global solvers we have tested with default settings. [ABSTRACT FROM AUTHOR]

We investigate the unconstrained global optimization of functions with low effective dimensionality, which are constant along certain (unknown) linear subspaces. Extending the technique of random subspace embeddings in Wang et al. (2016, J. Artificial Intelligence Res. , 55 , 361–387), we study a generic Random Embeddings for Global Optimization (REGO) framework that is compatible with any global minimization algorithm. Instead of the original, potentially large-scale optimization problem, within REGO, a Gaussian random, low-dimensional problem with bound constraints is formulated and solved in a reduced space. We provide novel probabilistic bounds for the success of REGO in solving the original, low effective-dimensionality problem, which show its independence of the (potentially large) ambient dimension and its precise dependence on the dimensions of the effective and embedding subspaces. These results significantly improve existing theoretical analyses by providing the exact distribution of a reduced minimizer and its Euclidean norm and by the general assumptions required on the problem. We validate our theoretical findings by extensive numerical testing of REGO with three types of global optimization solvers, illustrating the improved scalability of REGO compared with the full-dimensional application of the respective solvers. [ABSTRACT FROM AUTHOR]

The performance of global ocean biogeochemical models, and the Earth System Models in which they are embedded, can be improved by systematic calibration of the parameter values against observations. However, such tuning is seldom undertaken as these models are computationally very expensive. Here we investigate the performance of DFO-LS, a local, derivative-free optimisation algorithm which has been designed for computationally expensive models with irregular model data misfit landscapes typical of biogeochemical models. We use DFO-LS to calibrate six parameters of a relatively complex global ocean biogeochemical model (MOPS) against synthetic dissolved oxygen, inorganic phosphate and inorganic nitrate "observations" from a reference run of the same model with a known parameter configuration. The performance of DFO-LS is compared with that of CMA-ES, another derivative-free algorithm that was applied in a previous study to the same model in one of the first successful attempts at calibrating a global model of this complexity. We find that DFO-LS successfully recovers 5 of the 6 parameters in approximately 40 evaluations of the misfit function (each one requiring a 3000 year run of MOPS to equilibrium), while CMA-ES needs over 1200 evaluations. Moreover, DFO-LS reached a "baseline" misfit, defined by observational noise, in just 11–14 evaluations, whereas CMA-ES required approximately 340 evaluations.We also find that the performance of DFO-LS is not significantly affected by observational sparsity, however fewer parameters were successfully optimised in the presence of observational uncertainty. The results presented here suggest that DFO-LS is sufficiently inexpensive and robust to apply to the calibration of complex, global ocean biogeochemical models. [ABSTRACT FROM AUTHOR]

We show that the minimizers of regularized quadratic functions restricted to their natural Krylov spaces increase in Euclidean norm as the spaces expand. [ABSTRACT FROM AUTHOR]

Adaptive cubic regularization methods have emerged as a credible alternative to linesearch and trust-region for smooth nonconvex optimization, with optimal complexity amongst second-order methods. Here we consider a general/new class of adaptive regularization methods that use first- or higher-order local Taylor models of the objective regularized by a(ny) power of the step size and applied to convexly constrained optimization problems. We investigate the worst-case evaluation complexity/global rate of convergence of these algorithms, when the level of sufficient smoothness of the objective may be unknown or may even be absent. We find that the methods accurately reflect in their complexity the degree of smoothness of the objective and satisfy increasingly better bounds with improving model accuracy. The bounds vary continuously and robustly with respect to the regularization power and accuracy of the model and the degree of smoothness of the objective. [ABSTRACT FROM AUTHOR]

Adaptive cubic regularization methods have emerged as a credible alternative to linesearch and trust-region for smooth nonconvex optimization, with optimal complexity amongst second-order methods. Here we consider a general/new class of adaptive regularization methods that use first- or higher-order local Taylor models of the objective regularized by a(ny) power of the step size and applied to convexly constrained optimization problems. We investigate the worst-case evaluation complexity/global rate of convergence of these algorithms, when the level of sufficient smoothness of the objective may be unknown or may even be absent. We find that the methods accurately reflect in their complexity the degree of smoothness of the objective and satisfy increasingly better bounds with improving model accuracy. The bounds vary continuously and robustly with respect to the regularization power and accuracy of the model and the degree of smoothness of the objective. [ABSTRACT FROM AUTHOR]

High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ-(q+1)) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp. [ABSTRACT FROM AUTHOR]

As shown by Blumensath and Davies (2009) and Baraniuk et al. (2010), signals whose wavelet coefficients exhibit a rooted tree structure can be recovered using specially adapted compressed sensing algorithms from just n=\mathcal O(k) measurements, where $k$ is the sparsity of the signal. Motivated by these results, we introduce a simplified proportional-dimensional asymptotic framework, which enables the quantitative evaluation of recovery guarantees for tree-based compressed sensing. In the context of Gaussian matrices, we apply this framework to existing worst-case analysis of the iterative tree projection (ITP) algorithm, which makes use of the tree-based restricted isometry property (RIP). Within the same framework, we then obtain quantitative results based on a new method of analysis, which considers the fixed points of the algorithm. By exploiting the realistic average-case assumption that the measurements are statistically independent of the signal, we obtain significant quantitative improvements when compared with the tree-based RIP analysis. Our results have a refreshingly simple interpretation, explicitly determining a bound on the number of measurements that are required as a multiple of the sparsity. For example, we prove that exact recovery of binary tree-based signals from noiseless Gaussian measurements is asymptotically guaranteed for ITP with constant stepsize provided $n\geq 50k$ . All our results extend to the more realistic case in which measurements are corrupted by noise. [ABSTRACT FROM PUBLISHER]

We present a new recovery analysis for a standard compressed sensing algorithm, Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2008), which considers the fixed points of the algorithm. In the context of arbitrary measurement matrices, we derive a sufficient condition for the convergence of IHT to a fixed point and a necessary condition for the existence of fixed points. These conditions allow us to perform a sparse signal recovery analysis in the deterministic noiseless case by implying that the original sparse signal is the unique fixed point and limit point of IHT, and in the case of Gaussian measurement matrices and noise by generating a bound on the approximation error of the IHT limit as a multiple of the noise level. By generalizing the notion of fixed points, we extend our analysis to the variable stepsize Normalised IHT (Blumensath and Davies, 2010). For both stepsize schemes, we obtain lower bounds on asymptotic phase transitions in a proportional-dimensional framework, quantifying the sparsity/undersampling tradeoff for which recovery is guaranteed. Exploiting the reasonable average-case assumption that the underlying signal and measurement matrix are independent, comparison with previous results within this framework shows a substantial quantitative improvement. [ABSTRACT FROM AUTHOR]

When solving the general smooth nonlinear and possibly nonconvex optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy ∊ can be obtained by a second-order method using cubic regularization in at most O(∊-3/2) evaluations of problem functions, the same order bound as in the unconstrained case. This result is obtained by first showing that the same result holds for inequality constrained nonlinear leastsquares. As a consequence, the presence of (possibly nonconvex) equality/inequality constraints does not affect the complexity of finding approximate first-order critical points in nonconvex optimization. This result improves on the best known (O(∊-2)) evaluation-complexity bound for solving general nonconvexly constrained optimization problems. [ABSTRACT FROM AUTHOR]

The complexity of finding $$\epsilon $$-approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that $$O(\epsilon ^{-2})$$ in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply. [ABSTRACT FROM AUTHOR]

We propose a new termination criterion suitable for potentially singular, zero or nonzero residual, least-squares problems, with which cubic regularization variants take at most O(∈3/2) residual- and Jacobian-evaluations to drive either the Euclidean norm of the residual or its gradient below e; this is the best known bound for potentially rank-deficient nonlinear least-squares problems. We then apply the new optimality measure and cubic regularization steps to a family of least-squares merit functions in the context of a target-following algorithm for nonlinear equality-constrained problems; this approach yields the first evaluation complexity bound of order ∈3/2 for nonconvexly constrained problems when higher accuracy is required for primal feasibility than for dual first-order criticality. [ABSTRACT FROM AUTHOR]

This short note considers and resolves the apparent contradiction between known worst-case complexity results for first- and second-order methods for solving unconstrained smooth nonconvex optimization problems and a recent note by Jarre [On Nesterov's smooth Chebyshev–Rosenbrock function, Optim. Methods Softw. (2011)] implying a very large lower bound on the number of iterations required to reach the solution's neighbourhood for a specific problem with variable dimension. [ABSTRACT FROM AUTHOR]

The adaptive cubic regularization algorithms described in Cartis, Gould and Toint [Adaptive cubic regularisation methods for unconstrained optimization Part II: Worst-case function- and derivative-evaluation complexity, Math. Program. (2010), doi:10.1007/s10107-009-0337-y (online)]; [Part I: Motivation, convergence and numerical results, Math. Program. 127(2) (2011), pp. 245–295] for unconstrained (nonconvex) optimization are shown to have improved worst-case efficiency in terms of the function- and gradient-evaluation count when applied to convex and strongly convex objectives. In particular, our complexity upper bounds match in order (as a function of the accuracy of approximation), and sometimes even improve, those obtained by Nesterov [Introductory Lectures on Convex Optimization, Kluwer Academic Publishers, Dordrecht, 2004; Accelerating the cubic regularization of Newton's method on convex problems, Math. Program. 112(1) (2008), pp. 159–181] and Nesterov and Polyak [Cubic regularization of Newton's method and its global performance, Math. Program. 108(1) (2006), pp. 177–205] for these same problem classes, without requiring exact Hessians or exact or global solution of the subproblem. An additional outcome of our approximate approach is that our complexity results can naturally capture the advantages of both first- and second-order methods. [ABSTRACT FROM AUTHOR]

The (optimal) function/gradient evaluations worst-case complexity analysis available for the adaptive regularization algorithms with cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative-free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente [Worst Case Complexity of Direct Search, Technical report, Preprint 10-17, Department of Mathematics, University of Coimbra, Coimbra, Portugal, 2010] is also discussed, giving some theoretical insight into the relative merits of various methods in this popular class of algorithms. [ABSTRACT FROM AUTHOR]

An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi:, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413-431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most $${\mathcal{O}(\epsilon^{-3/2})}$$ iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy $${\epsilon}$$, and $${\mathcal{O}(\epsilon^{-3})}$$ iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians. [ABSTRACT FROM AUTHOR]

We estimate the worst-case complexity of minimizing all unconstrained, nonconvex composite objective with a structured nonsmooth term by means of some first-order methods. We find that it is unaffected by the nonsmoothness of the objective in that a first-order trust-region or quadratic regularization method applied to it takes at most …(ε-2) function evaluations to reduce the size of a first-order criticality measure below ε. Specializing this result to the case when the composite objective is an exact penalty function allows us to consider the objective- and constraint evaluation worst-case complexity of nonconvex equality-constrained optimization when the solution is computed using a first-order exact penalty method. We obtain that in the reasonable case when the penalty parameters are bounded, the complexity of reaching within ε of a KKT point is at most …(ε-2) problem evaluations, which is the same in order as the function-evaluation complexity of steepest-descent methods applied to unconstrained, nonconvex smooth optimization. [ABSTRACT FROM AUTHOR]

n Adaptive Regularisation algorithm using Cubics (ARC) is proposed for unconstrained optimization, generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser et al. (Optim Methods Softw 22(3):413-431, 2007). At each iteration of our approach, an approximate global minimizer of a local cubic regularisation of the objective function is determined, and this ensures a significant improvement in the objective so long as the Hessian of the objective is locally Lipschitz continuous. The new method uses an adaptive estimation of the local Lipschitz constant and approximations to the global model-minimizer which remain computationally-viable even for large-scale problems. We show that the excellent global and local convergence properties obtained by Nesterov and Polyak are retained, and sometimes extended to a wider class of problems, by our ARC approach. Preliminary numerical experiments with small-scale test problems from the CUTEr set show encouraging performance of the ARC algorithm when compared to a basic trust-region implementation. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS) seeks to recover an unknown vector with N entries by making far fewer than N measurements; it posits that the number of CS measurements should be comparable to the information content of tile vector, not simply N. CS combines directly the important task of compression with the measurement task. Since its introduction in 2004 there have been hundreds of papers on CS, a large fraction of which develop algorithms to recover a signal from its compressed measurements. Because of the paradoxical nature of CS--exact reconstruction from seemingly undersampled measurements--it is crucial for acceptance of an algorithm that rigorous analyses verify the degree of undersampling the algorithm permits. The restricted isometry property (RIP) has become the dominant tool used for the analysis in such cases. We present here an asymmetric form of RIP that gives tighter bounds than the usual symmetric one. We give the best known bounds on the RIP constants for matrices from the Gaussian ensemble. Our derivations illustrate the way in which the combinatorial nature of CS is controlled. Our quantitative bounds on the RIP allow precise statements as to how aggressively a signal can be undersampled, the essential question for practitioners. We also document the extent to which RIP gives precise information about the true performance limits of CS, by comparison with approaches from high-dimensional geometry. [ABSTRACT FROM AUTHOR]

Abstract: A major enterprise in compressed sensing and sparse approximation is the design and analysis of computationally tractable algorithms for recovering sparse, exact or approximate, solutions of underdetermined linear systems of equations. Many such algorithms have now been proven to have optimal-order uniform recovery guarantees using the ubiquitous Restricted Isometry Property (RIP) (Candès and Tao (2005) ). However, without specifying a matrix, or class of matrices, it is unclear when the RIP-based sufficient conditions on the algorithm are satisfied. Bounds on RIP constants can be inserted into the algorithms RIP-based conditions, translating the conditions into requirements on the signal''s sparsity level, length, and number of measurements. We illustrate this approach for Gaussian matrices on three of the state-of-the-art greedy algorithms: CoSaMP (Needell and Tropp (2009) ), Subspace Pursuit (SP) (Dai and Milenkovic (2009) ) and Iterative Hard Thresholding (IHT) (Blumensath and Davies (2009) ). Designed to allow a direct comparison of existing theory, our framework implies that, according to the best available analysis on these three algorithms, IHT requires the fewest number of compressed sensing measurements, has the best proven stability bounds, and has the lowest per iteration computational cost. [Copyright &y& Elsevier]

Abstract: Employing a new primal-dual corrector algorithm, we investigate the impact that corrector directions may have on the convergence behaviour of predictor–corrector methods. The Primal-Dual Corrector (pdc) algorithm that we propose computes on each iteration a corrector direction in addition to the direction of the standard primal-dual path-following interior point method [M. Kojima, S. Mizuno, A. Yoshise, A primal-dual interior point algorithm for linear programming, in: Progress in Mathematical Programming, Pacific Grove, CA, 1987, Springer, New York, 1989, pp. 29–47] for Linear Programming (lp), in an attempt to improve performance. The new iterate is chosen by moving along the sum of these directions, from the current iterate. This technique is similar to the construction of Mehrotra''s highly popular predictor–corrector algorithm [S. Mehrotra, On finding a vertex solution using interior point methods, Linear Algebra Appl. 152 (1991) 233–253]. We present examples, however, that show that the pdc algorithm may fail to converge to a solution of the lp problem, in both exact and finite arithmetic, regardless of the choice of stepsize that is employed. The cause of this bad behaviour is that the correctors exert too much influence on the direction in which the iterates move. [Copyright &y& Elsevier]

We consider the minimization of a cost function f on a manifold |$\mathcal{M}$| using Riemannian gradient descent and Riemannian trust regions (RTR). We focus on satisfying necessary optimality conditions within a tolerance ε. Specifically, we show that, under Lipschitz-type assumptions on the pullbacks of f to the tangent spaces of |$\mathcal{M}$|⁠, both of these algorithms produce points with Riemannian gradient smaller than ε in |$\mathcal{O}\big(1/\varepsilon ^{2}\big)$| iterations. Furthermore, RTR returns a point where also the Riemannian Hessian's least eigenvalue is larger than − ε in |$\mathcal{O} \big(1/\varepsilon ^{3}\big)$| iterations. There are no assumptions on initialization. The rates match their (sharp) unconstrained counterparts as a function of the accuracy ε (up to constants) and hence are sharp in that sense. These are the first deterministic results for global rates of convergence to approximate first- and second-order Karush-Kuhn-Tucker points on manifolds. They apply in particular for optimization constrained to compact submanifolds of |${\mathbb{R}^{n}}$|⁠, under simpler assumptions. [ABSTRACT FROM AUTHOR]

Uncertainty in climate projections is large as shown by the likely uncertainty ranges in equilibrium climate sensitivity (ECS) of 2.5–4 K and in the transient climate response (TCR) of 1.4–2.2 K. Uncertainty in model projections could arise from the way in which unresolved processes are represented, the parameter values used, or the targets for model calibration. We show that, in two climate model ensembles that were objectively calibrated to minimize differences from observed large-scale atmospheric climatology, uncertainties in ECS and TCR are about 2–6 times smaller than in the CMIP5 or CMIP6 multimodel ensemble. We also find that projected uncertainties in surface temperature, precipitation, and annual extremes are relatively small. Residual uncertainty largely arises from unconstrained sea ice feedbacks. The more than 20-year-old HadAM3 standard model configuration simulates observed hemispheric-scale observations and preindustrial surface temperatures about as well as the median CMIP5 and CMIP6 ensembles while the optimized configurations simulate these better than almost all the CMIP5 and CMIP6 models. Hemispheric-scale observations and preindustrial temperatures are not systematically better simulated in CMIP6 than in CMIP5 although the CMIP6 ensemble seems to better simulate patterns of large-scale observations than the CMIP5 ensemble and the optimized HadAM3 configurations. Our results suggest that most CMIP models could be improved in their simulation of large-scale observations by systematic calibration. However, the uncertainty in climate projections (for a given scenario) likely largely arises from the choice of parameterization schemes for unresolved processes ("structural uncertainty"), with different tuning targets another possible contributor. Significance Statement: Climate models represent unresolved phenomena controlled by uncertain parameters. Changes in these parameters impact how well a climate model simulates current climate and its climate projections. Multiple calibrations of a single climate model, using an objective method, to large-scale atmospheric observations are performed. These models produce very similar climate projections at both global and regional scales. An analysis that combines uncertainties in observations with simulated sensitivity to observations and climate response also has small uncertainty showing that, for this model, current observations constrain climate projections. Recently developed climate models have a broad range of abilities to simulate large-scale climate with only some improvement in their ability to simulate this despite a decade of model development. [ABSTRACT FROM AUTHOR]

Perturbed physics configurations of version 3 of the Hadley Centre Atmosphere Model (HadAM3) driven with observed sea surface temperatures (SST) and sea ice were tuned to outgoing radiation observations using a Gauss-Newton line search optimization algorithm to adjust the model parameters. Four key parameters that previous research found affected climate sensitivity were adjusted to several different target values including two sets of observations. The observations used were the global average reflected shortwave radiation (RSR) and outgoing longwave radiation (OLR) from the Clouds and the Earth's Radiant Energy System instruments combined with observations of ocean heat content. Using the same method, configurations were also generated that were consistent with the earlier Earth Radiation Budget Experiment results. Many, though not all, tuning experiments were successful, with about 2500 configurations being generated and the changes in simulated outgoing radiation largely due to changes in clouds. Clear-sky radiation changes were small, largely due to a cancellation between changes in upper-tropospheric relative humidity and temperature. Changes in other climate variables are strongly related to changes in OLR and RSR particularly on large scales. There appears to be some equifinality with different parameter configurations producing OLR and RSR values close to observed values. These models have small differences in their climatology with the one group being similar to the standard configuration and the other group drier in the tropics and warmer everywhere. [ABSTRACT FROM AUTHOR]

Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the trust-region method, its iterations can be thought of as approximate, safe-guarded Newton steps. For cost functions with Lipschitz continuous Hessian, ARC has optimal iteration complexity, in the sense that it produces an iterate with gradient smaller than ε in O (1 / ε 1.5) iterations. For the same price, it can also guarantee a Hessian with smallest eigenvalue larger than - ε . In this paper, we study a generalization of ARC to optimization on Riemannian manifolds. In particular, we generalize the iteration complexity results to this richer framework. Our central contribution lies in the identification of appropriate manifold-specific assumptions that allow us to secure these complexity guarantees both when using the exponential map and when using a general retraction. A substantial part of the paper is devoted to studying these assumptions—relevant beyond ARC—and providing user-friendly sufficient conditions for them. Numerical experiments are encouraging. [ABSTRACT FROM AUTHOR]

Optimisation methods were successfully used to calibrate parameters in an atmospheric component of a climate model using two variants of the Gauss-Newton line-search algorithm. 1) A standard Gauss-Newton algorithm in which, in each iteration, all parameters were perturbed. 2) A randomized block-coordinate variant in which, in each iteration, a random sub-set of parameters was perturbed. The cost function to be minimized used multiple large-scale observations and was constrained to produce net radiative fluxes close to those observed. These algorithms were used to calibrate the HadAM3 (3rd Hadley Centre Atmospheric Model) model at N48 resolution and the HadAM3P model at N96 resolution. For the HadAM3 model, cases with seven and fourteen parameters were tried. All ten 7-parameter cases using HadAM3 converged to cost function values similar to that of the standard configuration. For the 14-parameter cases several failed to converge, with the random variant in which 6 parameters were perturbed being most successful. Multiple sets of parameter values were found that produced multiple models very similar to the standard configuration. HadAM3 cases that converged were coupled to an ocean model and ran for 20 years starting from a pre-industrial HadCM3 (3rd Hadley Centre Coupled model) state resulting in several models whose global-average temperatures were consistent with pre-industrial estimates. For the 7-parameter cases the Gauss-Newton algorithm converged in about 70 evaluations. For the 14-parameter algorithm with 6 parameters being randomly perturbed about 80 evaluations were needed for convergence. However, when 8 parameters were randomly perturbed algorithm performance was poor. Our results suggest the computational cost for the Gauss-Newton algorithm scales between P and P2 where P is the number of parameters being calibrated. For the HadAM3P model three algorithms were tested. Algorithms in which seven parameters were perturbed and three out of seven parameters randomly perturbed produced final configurations comparable to the standard hand tuned configuration. An algorithm in which six out of thirteen parameters were randomly perturbed failed to converge. These results suggest that automatic parameter calibration using atmospheric models is feasible and that the resulting coupled models are stable. Thus, automatic calibration could replace human driven trial and error. However, convergence and costs are, likely, sensitive to details of the algorithm. [ABSTRACT FROM AUTHOR]

A large number of perturbed-physics simulations of version 3 of the Hadley Centre Atmosphere Model (HadAM3) were compared with the Clouds and the Earth's Radiant Energy System (CERES) estimates of outgoing longwave radiation (OLR) and reflected shortwave radiation (RSR) as well as OLR and RSR from the earlier Earth Radiation Budget Experiment (ERBE) estimates. The model configurations were produced from several independent optimization experiments in which four parameters were adjusted. Model-observation uncertainty was estimated by combining uncertainty arising from satellite measurements, observational radiation imbalance, total solar irradiance, radiative forcing, natural aerosol, internal climate variability, and sea surface temperature and that arising from parameters that were not varied. Using an emulator built from 14 001 'slab' model evaluations carried out using the ensemble, the climate sensitivity for each configuration was estimated. Combining different prior probabilities for model configurations with the likelihood for each configuration and taking account of uncertainty in the emulated climate sensitivity gives, for the HadAM3 model, a 2.5%-97.5% range for climate sensitivity of 2.7-4.2 K if the CERES observations are correct. If the ERBE observations are correct, then they suggest a larger range, for HadAM3, of 2.8-5.6 K. Amplifying the CERES observational covariance estimate by a factor of 20 brings CERES and ERBE estimates into agreement. In this case the climate sensitivity range is 2.7-5.4 K. The results rule out, at the 2.5% level for HadAM3 and several different prior assumptions, climate sensitivities greater than 5.6 K. [ABSTRACT FROM AUTHOR]