Biography

High-order tensor methods for solving both convex and nonconvex optimization problems have recently generated significant research interest, due in part to the natural way in which higher derivatives can be incorporated into adaptive regularization frameworks, leading to algorithms with optimal global rates of convergence and local rates that are faster than Newton’s method. On each iteration, to find the next solution approximation, these methods require the unconstrained local minimization of a (potentially nonconvex) multivariate polynomial of degree higher than two, constructed using third-order (or higher) derivative information, and regularized by an appropriate power of the change in the iterates. Developing efficient techniques for the solution of such subproblems is a current topic of research, and this paper addresses this question for the case of the third-order tensor subproblem. In particular, we propose the CQR algorithmic framework, for minimizing a nonconvex Cubic multivariate polynomial with Quartic Regularisation, by sequentially minimizing a sequence of local quadratic models that also incorporate both simple cubic and quartic terms. The role of the cubic term is to crudely approximate local tensor information, while the quartic one provides model regularization and controls progress. We provide necessary and sufficient optimality conditions that fully characterise the global minimizers of these cubic-quartic models. We then turn these conditions into secular equations that can be solved efficiently using root-finding procedures. We propose practical CQR variants that judiciously use local tensor information to construct the local cubic-quartic models. We test these variants numerically and observe them to be competitive with cubic regularization and other subproblem solvers on typical instances and even show superior performance on ill-conditioned subproblems with special structures.

There has been growing interest in high-order tensor methods for nonconvex optimization, with adaptive regularization, as they possess better/optimal worst-case evaluation complexity globally and faster convergence asymptotically. These algorithms crucially rely on repeatedly minimizing nonconvex multivariate Taylor-based polynomial sub-problems, at least locally. Finding efficient techniques for the solution of these sub-problems, beyond the second-order case, has been an open question. This paper proposes a second-order method, Quadratic Quartic Regularisation (QQR), for efficiently minimizing nonconvex quartically-regularized cubic polynomials. Inspired by Nesterov’s recent work, QQR approximates the third-order tensor term by a linear combination of quadratic and quartic terms, yielding (possibly nonconvex) local models that are solvable to global optimality. Preliminary numerical experiments indicate that two QQR variants perform competitively with state-of-the-art approaches such as ARC (also known as ARp with p=2), achieving either lower objective value or iteration counts.

High-order tensor methods that employ Taylor-based local models of positive integer degree p within adaptive regularization frameworks have recently garnered significant research interest for both convex and nonconvex optimization problems. The well-known pth-order adaptive regularization (ARp) method has demonstrated optimal worst-case global convergence rates and local convergence rates. At each iteration of this method, a local model of the objective function, consisting of a pth-order Taylor approximation and a (p+1)th-order regularization term, is minimized. However, for any p≥3, it remains an open question how to efficiently minimize the subproblem and which minimizer to select. In this context, designing efficient ARp variants is a critical area of interest, especially for p≥3. In this paper, we extend the interpolation-based updating strategies, originally introduced by Gould, Porcelli, and Toint in 2012 for p=2, to cases where p≥3. This updating strategy enables the regularization parameter to adjust adaptively based on interpolation models. We propose a novel prerejection mechanism that rejects unwanted subproblem minimizers prior to any function evaluations, thereby reducing computational costs for p≥3. Numerical results illustrate how the proposed interpolation-based updating strategy and the prerejection mechanism for p=3 enhance the overall numerical performance.

High-order tensor methods that employ Taylor-based local models within adaptive regularization frameworks have been recently proposed for both convex and nonconvex optimization problems. They have been shown to have superior, and even optimal, worst-case global convergence rates and local rates compared to Newton’s method Finding rigorous and efficient techniques for minimizing the Taylor polynomial sub-problems remains a challenging aspect for these algorithms. Ahmadi et al recently introduced a tensor method based on sum-of-squares (SoS) reformulations, so that each Taylor polynomial sub-problem in their approach can be tractably minimized using semidefinite programming (SDP); however, the global convergence and complexity of their method have not been addressed for general nonconvex problems. This paper introduces an algorithmic framework that combines the Sum of Squares (SoS) Taylor model with adaptive regularization techniques for nonconvex smooth optimization problems. Each iteration minimizes an SoS-convex Taylor model, offering a polynomial cost per iteration. To our knowledge, this is the first global rate analysis for an adaptive regularization algorithm with a tractable high-order sub-problem in nonconvex smooth optimization, opening the way for further improvements.

The classical risk-neutral newsvendor problem is to decide the order quantity that maximises the expected profit.
This paper proposes a feature-based non-parametric approach to Newsvendor conditional value-at-risk (CVaR) minimization under adaptive data selection (NPC). The NPC method is simple and general. It can handle minimisation with both linear and nonlinear profits and requires no prior knowledge of the demand distribution. Our main contribution is two-fold. Firstly, NPC uses a feature-based approach. The estimated parameters of NPC can be easily applied to prescriptive analytic to provide additional operational insights. Secondly, unlike common non-parametric methods, our NPC method uses an adaptive data selection criterion and requires only a small proportion of data (only data from two tails), significantly reducing the computational effort. Results from both numerical and real-life experiments confirm that NPC is robust concerning difficult and large data structures. Using fewer data points, the computed order quantities from NPC lead to equal or less downside loss in extreme cases than competing methods