Quantum Annealing (QA) can be used to quickly obtain near-optimal solutions for Quadratic Unconstrained Binary Optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to … Read more
We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly r integer variables and 2 x (# of spanning hyperplanes) general inequality constraints. We use … Read more
The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two … Read more
With wind and solar becoming major contributors to electricity production in many systems, wholesale market operators have become increasingly aware of the need to address uncertainty when forming prices. While implementing theoretically ideal stochastic market clearing to address uncertainty may be impossible, the use of operating reserve demand curves allows market designers to inject an … Read more
We consider the iterative solution of regularized saddle-point systems. When the leading block is symmetric and positive semi-definite on an appropriate subspace, Dollar, Gould, Schilders, and Wathen (SIAM J. Matrix Anal. Appl., 28(1), 2006) describe how to apply the conjugate gradient (CG) method coupled with a constraint preconditioner, a choice that has proved to be … Read more
We introduce an iterative method named BiLQ for solving general square linear systems Ax = b based on the Lanczos biorthogonalization process defined by least-norm subproblems, and is a natural companion to BiCG and QMR. Whereas the BiCG (Fletcher, 1976), CGS (Sonneveld, 1989) and BiCGSTAB (van der Vorst, 1992) iterates may not exist when the … Read more
We look at stochastic optimization problems through the lens of statistical decision theory. In particular, we address admissibility, in the statistical decision theory sense, of the natural sample average estimator for a stochastic optimization problem (which is also known as the empirical risk minimization (ERM) rule in learning literature). It is well known that for … Read more
Cubic Regularization methods have several favorable properties. In particular under mild assumptions, they are globally convergent towards critical points with second order necessary conditions satisfied. Their adoption among practitioners, however, does not yet match the strong theoretical results. One of the reasons for this discrepancy may be additional implementation complexity needed to solve the occurring … Read more
A popular belief for explaining the efficiency in training deep neural networks is that over-paramenterized neural networks have nice landscape. However, it still remains unclear whether over-parameterized neural networks contain spurious local minima in general, since all current positive results cannot prove non-existence of bad local minima, and all current negative results have strong restrictions … Read more
We develop a complementarity-constrained nonlinear optimization model for the time-dependent control of district heating networks. The main physical aspects of water and heat flow in these networks are governed by nonlinear and hyperbolic 1d partial differential equations. In addition, a pooling-type mixing model is required at the nodes of the network to treat the mixing … Read more