Search

Quasi-Newton methods employ an update rule that gradually improves the Hessian approximation using the already available gradient evaluations. We propose higher-order secant updates which generalize this idea to higher-order derivatives, approximating for example third derivatives (which are tensors) from given Hessian evaluations. Our generalization is based on the observation that quasi-Newton updates are least-change updates satisfying the secant equation, with different methods using different norms to measure the size of the change. We present a full characterization for least-change updates in weighted Frobenius norms (satisfying an analogue of the secant equation) for derivatives of arbitrary order. Moreover, we establish convergence of the approximations to the true derivative under standard assumptions and explore the quality of the generated approximations in numerical experiments.

Spot electricity markets are considered under a Game-Theoretic framework, where risk averse players submit orders to the market clearing mechanism to maximise their own utility. Consistent with the current practice in Europe, the market clearing mechanism is modelled as a Social Welfare Maximisation problem, with zonal pricing, and we consider inflexible demand, physical constraints of the electricity grid, and capacity-constrained producers. A novel type of non-parametric risk aversion based on a defined worst case scenario is introduced, and this reduces the dimensionality of the strategy variables and ensures boundedness of prices. By leveraging these properties we devise Jacobi and Gauss-Seidel iterative schemes for computation of approximate global Nash Equilibria, which are in contrast to derivative based local equilibria. Our methodology is applied to the real world data of Central Western European (CWE) Spot Market during the 2019-2020 period, and offers a good representation of the historical time series of prices. By also solving for the assumption of truthful bidding, we devise a simple method based on hypothesis testing to infer if and when producers are bidding strategically (instead of truthfully), and we find evidence suggesting that strategic bidding may be fairly pronounced in the CWE region.

For the case of inflexible demand and considering network constraints, we introduce a Cost Minimisation (CM) based market clearing mechanism, and a model representing the standard Social Welfare Maximisation mechanism used in European Day Ahead Electricity Markets. Since the CM model corresponds to a more challenging optimisation problem, we propose four numerical algorithms that leverage the problem structure, each with different trade-offs between computational cost and convergence guarantees. These algorithms are evaluated on synthetic data to provide some intuition of their performance. We also provide strong (but partial) analytical results to facilitate efficient solution of the CM problem, which call for the introduction of a new concept: optimal zonal stack curves, and these results are used to devise one of the four solution algorithms. An evaluation of the CM and SWM models and their comparison is performed, under the assumption of truthful bidding, on the real world data of Central Western European Day Ahead Power Market during the period of 2019-2020. We show that the SWM model we introduce gives a good representation of the historical time series of the real prices. Further, the CM reduces the market power of producers, as generally this results in decreased zonal prices and always decreases the total cost of electricity procurement when compared to the currently employed SWM., Comment: Corrected minor typos, 25 pages, 8 figures

Binary matrix factorisation is an essential tool for identifying discrete patterns in binary data. In this paper we consider the rank-k binary matrix factorisation problem (k-BMF) under Boolean arithmetic: we are given an n x m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n x k and k x m respectively, which minimise the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and two exponential size integer programs (IPs) for k-BMF and show that the compact IP has a weak LP relaxation, while the exponential size IPs have a stronger equivalent LP relaxation. We introduce a new objective function, which differs from the traditional squared Frobenius objective in attributing a weight to zero entries of the input matrix that is proportional to the number of times the zero is erroneously covered in a rank-k factorisation. For one of the exponential size IPs we describe a computational approach based on column generation. Experimental results on synthetic and real word datasets suggest that our integer programming approach is competitive against available methods for k-BMF and provides accurate low-error factorisations.

Network constraints play a key role in the price finding mechanism for European Power Markets, but historical data is very sparse and usually insufficient for many quantitative applications. We reconstruct the constraints data, known as the Power Transmission Distribution Factors (PTDFs) and Remaining Available Margins (RAMs), by first recovering the underlying time dependent signals known as the Generation Shift Keys (GSKs) and Phase Angles (PAs), and the electricity grid characteristics, via a mathematical optimisation problem. This is solved by exploiting marginal convexity in certain subspaces via alternating minimisation. The GSKs and PAs are then mapped to the PTDFs and RAMs, using the grid structure. Our reconstruction achieves good in-sample and out-of-sample relative errors for the PTDFs and RAMs. We further show that our model outperforms the naive approach, and that the reconstructed GSKs and PAs recover specific structure.

In this paper, we construct an algorithm for minimising piecewise smooth functions for which derivative information is not available. The algorithm constructs a pair of quadratic functions, one on each side of the point with smallest known function value, and selects the intersection of these quadratics as the next test point. This algorithm relies on the quadratic function underestimating the true function within a specific range, which is accomplished using a adjustment term that is modified as the algorithm progresses.

Identifying discrete patterns in binary data is an important dimensionality reduction tool in machine learning and data mining. In this paper, we consider the problem of low-rank binary matrix factorisation (BMF) under Boolean arithmetic. Due to the hardness of this problem, most previous attempts rely on heuristic techniques. We formulate the problem as a mixed integer linear program and use a large scale optimisation technique of column generation to solve it without the need of heuristic pattern mining. Our approach focuses on accuracy and on the provision of optimality guarantees. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations and improves on the previously available best known results for 15 out of 24 problem instances., Comment: final version as published by AAAI2021, plus including Appendix

In the seminal paper on optimal execution of portfolio transactions, Almgren and Chriss (2001) define the optimal trading strategy to liquidate a fixed volume of a single security under price uncertainty. Yet there exist situations, such as in the power market, in which the volume to be traded can only be estimated and becomes more accurate when approaching a specified delivery time. During the course of execution, a trader should then constantly adapt their trading strategy to meet their fluctuating volume target. In this paper, we develop a model that accounts for volume uncertainty and we show that a risk-averse trader has benefit in delaying their trades. More precisely, we argue that the optimal strategy is a trade-off between early and late trades in order to balance risk associated with both price and volume. By incorporating a risk term related to the volume to trade, the static optimal strategies suggested by our model avoid the explosion in the algorithmic complexity usually associated with dynamic programming solutions, all the while yielding competitive performance.

This paper introduces Memory-limited Online Subspace Estimation Scheme (MOSES) for both estimating the principal components of streaming data and reducing its dimension. More specifically, in various applications such as sensor networks, the data vectors are presented sequentially to a user who has limited storage and processing time available. Applied to such problems, MOSES can provide a running estimate of leading principal components of the data that has arrived so far and also reduce its dimension. MOSES generalises the popular incremental Singular Vale Decomposition (iSVD) to handle thin blocks of data, rather than just vectors. This minor generalisation in part allows us to complement MOSES with a comprehensive statistical analysis, thus providing the first theoretically-sound variant of iSVD, which has been lacking despite the empirical success of this method. This generalisation also enables us to concretely interpret MOSES as an approximate solver for the underlying non-convex optimisation program. We find that MOSES consistently surpasses the state of the art in our numerical experiments with both synthetic and real-world datasets, while being computationally inexpensive.

Principal Component Analysis (PCA) finds the best linear representation of data, and is an indispensable tool in many learning and inference tasks. Classically, principal components of a dataset are interpreted as the directions that preserve most of its "energy", an interpretation that is theoretically underpinned by the celebrated Eckart-Young-Mirsky Theorem. This paper introduces many other ways of performing PCA, with various geometric interpretations, and proves that the corresponding family of non-convex programs have no spurious local optima, while possessing only strict saddle points. These programs therefore loosely behave like convex problems and can be efficiently solved to global optimality, for example, with certain variants of the stochastic gradient descent. Beyond providing new geometric interpretations and enhancing our theoretical understanding of PCA, our findings might pave the way for entirely new approaches to structured dimensionality reduction, such as sparse PCA and nonnegative matrix factorisation. More specifically, we study an unconstrained formulation of PCA using determinant optimisation that might provide an elegant alternative to the deflating scheme commonly used in sparse PCA.

Low-rank approximations of data matrices are an important dimensionality reduction tool in machine learning and regression analysis. We consider the case of categorical variables, where it can be formulated as the problem of finding low-rank approximations to Boolean matrices. In this paper we give what is to the best of our knowledge the first integer programming formulation that relies on only polynomially many variables and constraints, we discuss how to solve it computationally and report numerical tests on synthetic and real-world data.

Principal component analysis (PCA) is an indispensable tool in many learning tasks that finds the best linear representation for data. Classically, principal components of a dataset are interpreted as the directions that preserve most of its "energy", an interpretation that is theoretically underpinned by the celebrated Eckart-Young-Mirsky Theorem. There are yet other ways of interpreting PCA that are rarely exploited in practice, largely because it is not known how to reliably solve the corresponding non-convex optimisation programs. In this paper, we consider one such interpretation of principal components as the directions that preserve most of the "volume" of the dataset. Our main contribution is a theorem that shows that the corresponding non-convex program has no spurious local optima. We apply a number of solvers for empirical confirmation.

Principal component analysis is an important pattern recognition and dimensionality reduction tool in many applications. Principal components are computed as eigenvectors of a maximum likelihood covariance $\widehat{\Sigma}$ that approximates a population covariance $\Sigma$, and these eigenvectors are often used to extract structural information about the variables (or attributes) of the studied population. Since PCA is based on the eigendecomposition of the proxy covariance $\widehat{\Sigma}$ rather than the ground-truth $\Sigma$, it is important to understand the approximation error in each individual eigenvector as a function of the number of available samples. The recent results of Kolchinskii and Lounici yield such bounds. In the present paper we sharpen these bounds and show that eigenvectors can often be reconstructed to a required accuracy from a sample of strictly smaller size order.

We extend Relative Robust Portfolio Optimisation models to allow portfolios to optimise their distance to a set of benchmarks. Portfolio managers are also given the option of computing regret in a way which is more in line with market practices than other approaches suggested in the literature. In addition, they are given the choice of simply adding an extra constraint to their optimisation problem instead of outright changing the objective function, as is commonly suggested in the literature. We illustrate the benefits of this approach by applying it to equity portfolios in a variety of regions.

3D image reconstruction from a set of X-ray projections is an important image reconstruction problem, with applications in medical imaging, industrial inspection and airport security. The innovation of X-ray emitter arrays allows for a novel type of X-ray scanners with multiple simultaneously emitting sources. However, two or more sources emitting at the same time can yield measurements from overlapping rays, imposing a new type of image reconstruction problem based on nonlinear constraints. Using traditional linear reconstruction methods, respective scanner geometries have to be implemented such that no rays overlap, which severely restricts the scanner design. We derive a new type of 3D image reconstruction model with nonlinear constraints, based on measurements with overlapping X-rays. Further, we show that the arising optimization problem is partially convex, and present an algorithm to solve it. Experiments show highly improved image reconstruction results from both simulated and real-world measurements., Comment: Published in Computer Vision - ECCV 2016. The final publication is available at link.springer.com/chapter/10.1007/978-3-319-46466-4_2

In this work we present two particular cases of the general duality result for linear optimisation problems over signed measures with infinitely many constraints in the form of integrals of functions with respect to the decision variables (the measure in question) for which strong duality holds. In the first case the optimisation problems are over measures with $L^p$ density functions with $1 < p < \infty$. In the second case we consider a semi-infinite optimisation problem where finitely many constraints are given in form of bounds on integrals. The latter case has a particular importance in practice where the model can be applied in robust risk management and model-free option pricing.

In this paper we introduce a new approach to model-free path-dependent option pricing. We first introduce a general duality result for linear optimisation problems over signed measures introduced in [3] and show how the the problem of model-free option pricing can be formulated in the new framework. We then introduce a model to solve the problem numerically when the only information provided is the market data of vanilla call or put option prices. Compared to the common approaches in the literature, e.g. [4], the model does not require the marginal distributions of the stock price for different maturities. Though the experiments are carried out for simple path-dependent options on a single stock, the model is easy to generalise for multi-asset framework.

In this paper we propose a quadratic programming model that can be used for calculating the term structure of electricity prices while explicitly modeling startup costs of power plants. In contrast to other approaches presented in the literature, we incorporate the startup costs in a mathematically rigorous manner without relying on ad hoc heuristics. Moreover, we propose a tractable approach for estimating the startup costs of power plants based on their historical production. Through numerical simulations applied to the entire UK power grid, we demonstrate that the inclusion of startup costs is necessary for the modeling of electricity prices in realistic power systems. Numerical results show that startup costs make electricity prices very spiky. In the second part of the paper, we extend the initial model by including the grid operator who is responsible for managing the grid. Numerical simulations demonstrate that robust decision making of the grid operator can significantly decrease the number and severity of spikes in the electricity price and improve the reliability of the power grid., Comment: Corrected paragraph style on page 16. arXiv admin note: substantial text overlap with arXiv:1409.6645

A fundamental problem in risk management is the robust aggregation of different sources of risk in a situation where little or no data are available to infer information about their dependencies. A popular approach to solving this problem is to formulate an optimization problem under which one maximizes a risk measure over all multivariate distributions that are consistent with the available data. In several special cases of such models, there exist dual problems that are easier to solve or approximate, yielding robust bounds on the aggregated risk. In this chapter we formulate a general optimization problem, which can be seen as a doubly infinite linear programming problem, and we show that the associated dual generalizes several well known special cases and extends to new risk management models we propose.

Consider finite sequences $X_{[1,n]}=X_1\dots X_n$ and $Y_{[1,n]}=Y_1\dots Y_n$ of length $n$, consisting of i.i.d.\ samples of random letters from a finite alphabet, and let $S$ and $T$ be chosen i.i.d.\ randomly from the unit ball in the space of symmetric scoring functions over this alphabet augmented by a gap symbol. We prove a probabilistic upper bound of linear order in $n^{0.75}$ for the deviation of the score relative to $T$ of optimal alignments with gaps of $X_{[1,n]}$ and $Y_{[1,n]}$ relative to $S$. It remains an open problem to prove a lower bound. Our result contributes to the understanding of the microstructure of optimal alignments relative to one given scoring function, extending a theory begun by the first two authors.

In this paper we propose a tractable quadratic programming formulation for calculating the equilibrium term structure of electricity prices. We rely on a theoretical model described in [21], but extend it so that it reflects actually traded electricity contracts, transaction costs and liquidity considerations. Our numerical simulations examine the properties of the term structure and its dependence on various parameters of the model. The proposed quadratic programming formulation is applied to calculate the equilibrium term structure of electricity prices in the UK power grid consisting of a few hundred power plants. The impact of ramp up and ramp down constraints are also studied., Comment: arXiv admin note: text overlap with arXiv:1408.2464

We propose a term structure power price model that, in contrast to widely accepted no-arbitrage based approaches, accounts for the non-storable nature of power. It belongs to a class of equilibrium game theoretic models with players divided into producers and consumers. The consumers' goal is to maximize a mean-variance utility function subject to satisfying an inelastic demand of their own clients (e.g households, businesses etc.) to whom they sell the power. The producers, who own a portfolio of power plants each defined by a running fuel (e.g. gas, coal, oil...) and physical characteristics (e.g. efficiency, capacity, ramp up/down times...), similarly, seek to maximize a mean-variance utility function consisting of power, fuel, and emission prices subject to production constraints. Our goal is to determine the term structure of the power price at which production matches consumption. In this paper we show that in such a setting the equilibrium price exists and also discuss the conditions for its uniqueness.

Regression is widely used by practioners across many disciplines. We reformulate the underlying optimisation problem as a second-order conic program providing the flexibility often needed in applications. Using examples from portfolio management and quantitative trading we solve regression problems with and without constraints. Several Python code fragments are given. The code and data are available online at http://www.github.com/tschm/MosekRegression.

Although modern portfolio theory has been in existence for over 60 years, fund managers often struggle to get its models to produce reliable portfolio allocations without strongly constraining the decision vector by tight bands of strategic allocation targets. The two main root causes to this problem are inadequate parameter estimation and numerical artifacts. When both obstacles are overcome, portfolio models yield excellent allocations. In this paper, which is primarily aimed at practitioners, we discuss the most common mistakes in setting up portfolio models and in solving them algorithmically.

Given a quadratic function $h$ that satisfies a Slater condition, Yakubovich's S-Procedure (or S-Lemma) gives a characterization of all other quadratic functions that are copositive with $h$ in a form that is amenable to numerical computations. In this paper we present a deep-rooted connection between the S-Procedure and the dual cone calculus formula $(K_1\cap K_2)^*= K_1^*+K_2^*$, which holds for closed convex cones in $\R^2$. To establish the link with the S-Procedure, we generalize the dual cone calculus formula to a situation where $K_1$ is nonclosed, nonconvex and nonconic but exhibits sufficient mathematical resemblance to a closed convex cone. As a result, we obtain a new proof of the S-Lemma and an extension to Hilbert space kernels.

Considering mean-variance portfolio problems with uncertain model parameters, we contrast the classical absolute robust optimization approach with the relative robust approach based on a maximum regret function. Although the latter problems are NP-hard in general, we show that tractable inner and outer approximations exist in several cases that are of central interest in asset management.

Considering two optimally aligned random sequences, we investigate the effect on the alignment score caused by changing a random letter in one of the two sequences. Using this idea in conjunction with large deviations theory, we show that in alignments with a low proportion of gaps the optimal alignment is locally unique in most places with high probability. This has implications in the design of recently pioneered alignment methods that use the local uniqueness as a homology indicator.

The problem of determining the correct order of fluctuation of the optimal alignment score of two random strings of length $n$ has been open for several decades. It is known that the biased expected effect of a random letter-change on the optimal score implies an order of fluctuation linear in $\sqrt{n}$. However, in many situations where such a biased effect is observed empirically, it has been impossible to prove analytically. The main result of this paper shows that when the rescaled-limit of the optimal alignment score increases in a certain direction, then the biased effect exists. On the basis of this result one can quantify a confidence level for the existence of such a biased effect and hence of an order $\sqrt{n}$ fluctuation based on simulation of optimal alignments scores.This is an important step forward, as the correct order of fluctuation was previously known only for certain special distributions. To illustrate the usefulness of our new methodology, we apply it to optimal alignments of strings written in the DNA-alphabet. As scoring function, we use the BLASTZ default-substitution matrix together with a realistic gap penalty. BLASTZ is one of the most widely used sequence alignment methodologies in bioinformatics. For this DNA-setting, we show that with a high level of confidence, the fluctuation of the optimal alignment score is of order $\Theta(\sqrt{n})$. An important special case of optimal alignment score is the Longest Common Subsequence (LCS) of random strings. For binary sequences with equiprobable symbols, the question of the fluctuation of the LCS remains open. The symmetry in that case does not allow for our method. On the other hand, in real-life DNA sequences, it is not the case that all letters occur with the same frequency. Thus, for many real life situations, our method allows to determine the order of the fluctuation up to a high confidence level.

Considering the optimal alignment of two i.i.d. random sequences of length $n$, we show that when the scoring function is chosen randomly, almost surely the empirical distribution of aligned letter pairs in all optimal alignments converges to a unique limiting distribution as $n$ tends to infinity. This result is interesting because it helps understanding the microscopic path structure of a special type of last passage percolation problem with correlated weights, an area of long-standing open problems. Characterizing the microscopic path structure yields furthermore a robust alternative to optimal alignment scores for testing the relatedness of genetic sequences.

The purpose of this note is to extend the results on uniform smoothed analysis of condition numbers from \cite{BuCuLo:07} to the case where the perturbation follows a radially symmetric probability distribution. In particular, we will show that the bounds derived in \cite{BuCuLo:07} still hold in the case of distributions whose density has a singularity at the center of the perturbation, which we call {\em adversarial}., Comment: 8 pages

Both constrained and unconstrained optimization problems regularly appear in recursive tracking problems engineers currently address -- however, constraints are rarely exploited for these applications. We define the Kalman Filter and discuss two different approaches to incorporating constraints. Each of these approaches are first applied to equality constraints and then extended to inequality constraints. We discuss methods for dealing with nonlinear constraints and for constraining the state prediction. Finally, some experiments are provided to indicate the usefulness of such methods., Comment: 26 pages, 3 figures

We discuss a method for predicting financial movements and finding pockets of predictability in the price-series, which is built around inferring the heterogeneity of trading strategies in a multi-agent trader population. This work explores extensions to our previous framework (arXiv:physics/0506134). Here we allow for more intelligent agents possessing a richer strategy set, and we no longer constrain the estimate for the heterogeneity of the agents to a probability space. We also introduce a scheme which allows the incorporation of models with a wide variety of agent types, and discuss a mechanism for the removal of bias from relevant parameters., Comment: 15 pages, 2 figures, to appear as a chapter in "Econophysics and Sociophysics of Markets and Networks", Springer-Verlag

We discuss the theoretical machinery involved in predicting financial market movements using an artificial market model which has been trained on real financial data. This approach to market prediction - in particular, forecasting financial time-series by training a third-party or 'black box' game on the financial data itself -- was discussed by Johnson et al. in cond-mat/0105303 and cond-mat/0105258 and was based on some encouraging preliminary investigations of the dollar-yen exchange rate, various individual stocks, and stock market indices. However, the initial attempts lacked a clear formal methodology. Here we present a detailed methodology, using optimization techniques to build an estimate of the strategy distribution across the multi-trader population. In contrast to earlier attempts, we are able to present a systematic method for identifying 'pockets of predictability' in real-world markets. We find that as each pocket closes up, the black-box system needs to be 'reset' - which is equivalent to saying that the current probability estimates of the strategy allocation across the multi-trader population are no longer accurate. Instead, new probability estimates need to be obtained by iterative updating, until a new 'pocket of predictability' emerges and reliable prediction can resume., Comment: 18 pages, 5 figures, added Monte Carlo algorithm tests

In this paper we study the distribution tails and the moments of a condition number which arises in the study of homogeneous systems of linear inequalities. We consider the case where this system is defined by a Gaussian random matrix and characterise the exact decay rates of the distribution tails, improve the existing moment estimates, and prove various limit theorems for large scale systems. Our results are of complexity theoretic interest, because interior-point methods and relaxation methods for the solution of systems of linear inequalities have running times that are bounded in terms of the logarithm and the square of the condition number respectively., Comment: 31 pages

Self-scaled barrier functions are fundamental objects in the theory of interior-point methods for linear optimization over symmetric cones, of which linear and semidefinite programming are special cases. We are classifying all self-scaled barriers over irreducible symmetric cones and show that these functions are merely homothetic transformations of the universal barrier function. Together with a decomposition theorem for self-scaled barriers this concludes the algebraic classification theory of these functions. After introducing the reader to the concepts relevant to the problem and tracing the history of the subject, we start by deriving our result from first principles in the important special case of semidefinite programming. We then generalise these arguments to irreducible symmetric cones by invoking results from the theory of Euclidean Jordan algebras., Comment: 12 pages

Self-scaled barrier functions on self-scaled cones were introduced through a set of axioms in 1994 by Y.E. Nesterov and M.J. Todd as a tool for the construction of long-step interior point algorithms. This paper provides firm foundation for these objects by exhibiting their symmetry properties, their intimate ties with the symmetry groups of their domains of definition, and subsequently their decomposition into irreducible parts and algebraic classification theory. In a first part we recall the characterisation of the family of self-scaled cones as the set of symmetric cones and develop a primal-dual symmetric viewpoint on self-scaled barriers, results that were first discovered by the second author. We then show in a short, simple proof that any pointed, convex cone decomposes into a direct sum of irreducible components in a unique way, a result which can also be of independent interest. We then show that any self-scaled barrier function decomposes in an essentially unique way into a direct sum of self-scaled barriers defined on the irreducible components of the underlying symmetric cone. Finally, we present a complete algebraic classification of self-scaled barrier functions using the correspondence between symmetric cones and Euclidean Jordan algebras., Comment: 17 pages