The ConicBundle approach for large scale semidefinite programming iteratively solves a quadratic semidefinite subproblem corresponding to the problem projected to a subspace together with a quadratic prox function in order to find the next candidate and uses the Ritz vectors of approximate eigenvalue computations in the candidate to improve the subspace. Instead of solving each subproblem separately by interior point methods we experiment with a dynamic interior point method in which the problem is modified and restarted dynamically whenever the current interior point solution suggests an intermediate evaluation might be worth the trouble. In a first tentative implementation of these ideas within the callable library ConicBundle the results on randomly generated large scale max-cut and theta-function instances indicate that the approach is competitive and frequently significantly faster than the non dynamic approach.

Block-structured quadratic programs (QPs) arise naturally in direct optimal control and must be solved efficiently and reliably to achieve reasonable real-time performance. While Alternating Direction Method of Multipliers (ADMM)-based QP solvers have gained popularity in this domain, existing approaches typically split the problem into an equality-constrained QP and a projection onto a box, which is a proven and widely used strategy, but one that does not fully exploit the block structure inherent to QPs arising from direct optimal control.

We propose qpBAMM, an ADMM-based solver that introduces a novel problem splitting: The QP is decomposed into a box-constrained QP and a projection onto linear dynamics. This splitting proves particularly beneficial for block-structured QPs, as the box-constrained subproblem decouples into smaller box-constrained QPs that can be solved independently and in parallel, while in the projection step the structure induced by the dynamics can be also exploited.

We introduce the algorithmic design of qpBAMM and discuss convergence properties and key implementation aspects of the algorithm. We then present numerical results comparing qpBAMM against other recent QP solvers, including an investigation of the effect of available parallelism on the performance of qpBAMM. The results demonstrate significant advantages of qpBAMM in terms of computation time, particularly for optimal control problems with a high-dimensional state space.

In his 9th problem on the list of problems for the 21st century, S. Smale asks whether there exist polynomial-time algorithms over the reals for Linear Programming (LP). He also highlights the issue of extending traditional exact computational models to allow for inexact representation.

Extending Smale's 9th question to inexact arithmetic leads to a surprising conclusion: even on well-conditioned problem spaces, implementable algorithms cannot approximate minimizers for LP or Basis Pursuit (BP).

And yet, randomization completely changes the picture: randomized algorithms can compute minimizers with arbitrarily high probability, despite deterministic non-computability. This behavior contrasts sharply with the established wisdom that randomness cannot aid computability beyond a success probability of \(1/2\), dating back to the work of de Leeuw, Moore, Shannon, and Shapiro from 1956.

More precisely, using the Solvability Complexity Index hierarchy, we construct both rational and real versions of problem spaces \(\Omega_{K,p}\) (with any \(K \in \mathbb{N}\) and \(p \in (0,1)\) --- in particular, \(p\) can be chosen to be arbitrarily close to \(1\)) for LP and BP on which no deterministic inexact-arithmetic algorithm can compute \(K\) digits of minimizers. However, on \(\Omega_{K,p}\), there exist randomized algorithms that compute \(K\) digits with probability \(p\).

Furthermore, the problem spaces \(\Omega_{K,p}\) exhibit several phase transitions. Allowing partial or non-halting algorithms increases achievable success probabilities. Meanwhile, on \(\Omega_{K,p}\), deterministic algorithms with unbounded complexity recover \(K-1\) digits and polynomial-time algorithms recover \(K-2\) digits.

More general results bound the condition numbers and norms of inputs in \(\Omega_{K,p}\) by \(O(10^{-K}/(1-p))\), suggesting a trade-off between condition numbers, precision, and effectiveness of randomization in the form of "The more poorly conditioned or the higher the desired precision, the more randomness can help".