As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry … Read more
We consider feasibility problems defined by a set of constraints that exhibit gradient H\”older continuity plus additional constraints defined by the affordability of obtaining approximate minimizers of quadratic models onto the associated feasible set. Each iteration of the method introduced in this paper involves the approximate minimization of a two-norm regularized quadratic subject to the … Read more
Recent papers indicate that some algorithms for constrained optimization may exhibit worst-case complexity bounds that are very similar to those of unconstrained optimization algorithms. A natural question is whether well established practical algorithms, perhaps with small variations, may enjoy analogous complexity results. In the present paper we show that the answer is positive with respect … Read more
For the unconstrained optimization of black box functions, this paper introduces a new randomized algorithm called VRBBO. In practice, VRBBO matches the quality of other state-of-the-art algorithms for finding, in small and large dimensions, a local minimizer with reasonable accuracy. Although our theory guarantees only local minimizers our heuristic techniques turn VRBBO into an efficient … Read more
The stochastic Frank-Wolfe method has recently attracted much general interest in the context of optimization for statistical and machine learning due to its ability to work with a more general feasible region. However, there has been a complexity gap in the guaranteed convergence rate for stochastic Frank-Wolfe compared to its deterministic counterpart. In this work, … Read more
We consider the coordination of planning decisions of a single product in a supply chain composed of one supplier and one retailer, by using contracts. We assume that the retailer has the market power: he can impose his optimal replenishment plan to the supplier. Our aim is to minimize the supplier’s cost without increasing the … Read more
It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in testing convexity … Read more
We present a short step interior point method for solving a class of nonlinear programming problems with quadratic objective function. Convex quadratic programming problems can be reformulated as problems in this class. The method is shown to have weak polynomial time complexity. A complete proof of the numerical stability of the method is provided. No … Read more
We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of n-by-n matrices and an n-dimensional vector, find a sequence of K matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the K matrices and the … Read more
We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems … Read more