Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers—already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an … Read more
In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving … Read more
This paper explores the idea that two-stage worst-case regret minimization problems with either objective or right-hand side uncertainty can be reformulated as two-stage robust optimization problems and can therefore benefit from the solution schemes and theoretical knowledge that have been developed in the last decade for this class of problems. In particular, we identify conditions … Read more
For the Lagrangian-DNN relaxation of quadratic optimization problems (QOPs), we propose a Newton-bracketing method to improve the performance of the bisection-projection method implemented in BBCPOP [to appear in ACM Tran. Softw., 2019]. The relaxation problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function … Read more
A new primal-dual interior-point algorithm applicable to nonsymmetric conic optimization is proposed. It is a generalization of the famous algorithm suggested by Nesterov and Todd for the symmetric conic case, and uses primal-dual scalings for nonsymmetric cones proposed by Tuncel. We specialize Tuncel’s primal-dual scalings for the important case of 3 dimensional exponential-cones, resulting in … Read more
We consider the problem of computing the minimum value of a polynomial f over a compact set K⊆R^n, which can be reformulated as finding a probability measure ν on K minimizing the expected value of f over K. Lasserre showed that it suffices to consider such measures of the form ν=qμ, where q is a … Read more
We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a … Read more
Dantzig-Wolfe decomposition (DWD) is a classical algorithm for solving large-scale linear programs whose constraint matrix involves a set of independent blocks coupled with a set of linking rows. The algorithm decomposes such a model into a master problem and a set of independent subproblems that can be solved in a distributed manner. In a typical … Read more
Diverse forms of nonlinear optimization problems can be recast to the special form of second-order cone problems (SOCPs), permitting a wider variety of highly effective solvers to be applied. Popular solvers assume, however, that the necessary transformations to required canonical forms have already been identified and carried out. We describe a general approach to the … Read more
We develop techniques to construct a series of sparse polyhedral approximations of the semidefinite cone. Motivated by the semidefinite (SD) bases proposed by Tanaka and Yoshise (2018), we propose a simple expansion of SD bases so as to keep the sparsity of the matrices composing it. We prove that the polyhedral approximation using our expanded … Read more