Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Black-scholes type equations

In this work we are concerned with the analysis and numerical solution of Black-Scholes type equations arising in the modeling of incomplete financial markets and an inverse problem of determining the local volatility function in a generalized Black-Scholes model from observed option prices. In the first chapter a fully nonlinear Black-Scholes equation which models transaction costs arising in option pricing is discretized by a new high order compact scheme. The compact scheme is proved to be unconditionally stable and non-oscillatory and is very efficient compared to classical schemes. Moreover, it is shown that the finite difference solution converges locally uniformly to the unique viscosity solution of the continuous equation. In the next chapter we turn to the calibration problem of computing local volatility functions from market data in a generalized Black-Scholes setting. We follow an optimal control approach in a Lagrangian framework. We show the existence of a global solution and study first- and second-order optimality conditions. Furthermore, we propose an algorithm that is based on a globalized sequential quadratic programming method and a primal-dual active set strategy, and present numerical results. In the last chapter we consider a quasilinear parabolic equation with quadratic gradient terms, which arises in the modeling of an optimal portfolio in incomplete markets. The existence of weak solutions is shown by considering a sequence of approximate solutions. The main difficulty of the proof is to infer the strong convergence of the sequence. Furthermore, we prove the uniqueness of weak solutions under a smallness condition on the derivatives of the covariance matrices with respect to the solution, but without additional regularity assumptions on the solution. The results are illustrated by a numerical example.

Quantum gravity effects in rotating black hole spacetimes

The aim of this work is to explore, within the framework of the presumably asymptotically safe Quantum Einstein Gravity, quantum corrections to black hole spacetimes, in particular in the case of rotating black holes. We have analysed this problem by exploiting the scale dependent Newton s constant implied by the renormalization group equation for the effective average action, and introducing an appropriate "cutoff identification" which relates the renormalization scale to the geometry of the spacetime manifold. We used these two ingredients in order to "renormalization group improve" the classical Kerr metric that describes the spacetime generated by a rotating black hole. We have focused our investigation on four basic subjects of black hole physics. The main results related to these topics can be summarized as follows. Concerning the critical surfaces, i.e. horizons and static limit surfaces, the improvement leads to a smooth deformation of the classical critical surfaces. Their number remains unchanged. In relation to the Penrose process for energy extraction from black holes, we have found that there exists a non-trivial correlation between regions of negative energy states in the phase space of rotating test particles and configurations of critical surfaces of the black hole. As for the vacuum energy-momentum tensor and the energy conditions we have shown that no model with "normal" matter, in the sense of matter fulfilling the usual energy conditions, can simulate the quantum fluctuations described by the improved Kerr spacetime that we have derived. Finally, in the context of black hole thermodynamics, we have performed calculations of the mass and angular momentum of the improved Kerr black hole, applying the standard Komar integrals. The results reflect the antiscreening character of the quantum fluctuations of the gravitational field. Furthermore we calculated approximations to the entropy and the temperature of the improved Kerr black hole to leading order in the angular momentum. More generally we have proven that the temperature can no longer be proportional to the surface gravity if an entropy-like state function is to exist.