We present alfonso, an opensource Matlab package for solving conic optimization problems over nonsymmetric convex cones. The implementation is based on the authors’ corrected analysis of a method of Skajaa and Ye. It enables optimization over any convex cone as long as a logarithmically homogeneous selfconcordant barrier is available for the cone or its dual. This includes many nonsymmetric cones, for example, hyperbolicity cones and their duals (such as sumofsquares cones), semidefinite and secondorder cone representable cones, power cones, and the exponential cone. Besides enabling the solution of problems that cannot be cast as optimization problems over a symmetric cone, algorithms for nonsymmetric conic optimization also offer performance advantages for problems whose symmetric cone programming representation requires a large number of auxiliary variables or has a special structure that can be exploited in the barrier computation. The worstcase iteration complexity of alfonso is the best known for nonsymmetric cone optimization: [Formula: see text] iterations to reach an εoptimal solution, where ν is the barrier parameter of the barrier function used in the optimization. Alfonso can be interfaced with a Matlab function (supplied by the user) that computes the Hessian of a barrier function for the cone. A simplified interface is also available to optimize over the direct product of cones for which a barrier function has already been built into the software. This interface can be easily extended to include new cones. Both interfaces are illustrated by solving linear programs. The oracle interface and the efficiency of alfonso are also demonstrated using an optimal design of experiments problem in which the tailored barrier computation greatly decreases the solution time compared with using stateoftheart, offtheshelf conic optimization software. Summary of Contribution: The paper describes an opensource Matlab package for optimization over nonsymmetric cones. A particularly important feature of this software is that, unlike other conic optimization software, it enables optimization over any convex cone as long as a suitable barrier function is available for the cone or its dual, not limiting the user to a small number of specific cones. Nonsymmetric cones for which such barriers are already known include, for example, hyperbolicity cones and their duals (such as sumofsquares cones), semidefinite and secondorder cone representable cones, power cones, and the exponential cone. Thus, the scope of this software is far larger than most current conic optimization software. This does not come at the price of efficiency, as the worstcase iteration complexity of our algorithm matches the iteration complexity of the most successful interiorpoint methods for symmetric cones. Besides enabling the solution of problems that cannot be cast as optimization problems over a symmetric cone, our software can also offer performance advantages for problems whose symmetric cone programming representation requires a large number of auxiliary variables or has a special structure that can be exploited in the barrier computation. This is also demonstrated in this paper via an example in which our code significantly outperforms Mosek 9 and SCS 2.
more »
« less
BlackBox Acceleration of Monotone Convex Program Solvers
This paper presents a blackbox framework for accelerating packing optimization solvers. Our method applies to packing linear programming problems and a family of convex programming problems with linear constraints. The framework is designed for highdimensional problems, for which the number of variables n is much larger than the number of measurements m. Given an [Formula: see text] problem, we construct a smaller [Formula: see text] problem, whose solution we use to find an approximation to the optimal solution. Our framework can accelerate both exact and approximate solvers. If the solver being accelerated produces an αapproximation, then we produce a [Formula: see text]approximation of the optimal solution to the original problem. We present worstcase guarantees on run time and empirically demonstrate speedups of two orders of magnitude.
more »
« less
 NSFPAR ID:
 10389449
 Date Published:
 Journal Name:
 Operations Research
 ISSN:
 0030364X
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem [Formula: see text] as a largescale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worstcase attacks. We show that optimal solutions of [Formula: see text] can be obtained from the equilibria of a largescale zerosum game. Our equilibrium analysis involves both gametheoretic and combinatorial arguments and leads to a computationally tractable approach to solve [Formula: see text]. First, we construct an approximate solution by using solutions of minimum set cover (MSC) and maximum set packing (MSP) problems and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Second, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSPbased solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in largescale networks by strategically positioning a small number of detectors.more » « less

We consider the following general network design problem. The input is an asymmetric metric (V, c), root [Formula: see text], monotone submodular function [Formula: see text], and budget B. The goal is to find an rrooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasipolynomial time [Formula: see text]approximation algorithm for this problem, in which [Formula: see text] is the number of vertices in an optimal solution. As a consequence, we obtain an [Formula: see text]approximation algorithm for directed (polymatroid) Steiner tree in quasipolynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved [Formula: see text]approximation algorithms for the singlesource buyatbulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio but improves significantly on the running time. For polymatroid Steiner tree and singlesource buyatbulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are the best possible (up to constant factors).more » « less

We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 01 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of generalpurpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cuttingplanes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 01 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.more » « less

The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multiitem inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NPhard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NPhard for constant joint cycle length and prove that it is strongly NPhard for nonconstant joint cycle length. For constant joint cyclelength discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the singlecycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NPhard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed [Formula: see text], provides a linear time [Formula: see text] approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be easier than the respective discrete problem. We narrow the previously known complexity gap between the continuous and discrete versions of RSP for the multicycle RSP (with either constant or nonconstant cycle length) and the singlecycle RSP with constant cycle length and widen the gap for singlecycle RSP with nonconstant cycle length. For the multicycle case and constant joint cycle length, the complexity status of continuous RSP is open, whereas it is proved here that the discrete RSP is weakly NPhard. Under our conjecture that the continuous RSP is easier than the discrete one, this implies that continuous RSP on multicycle and constant joint cycle length (currently of unknown complexity status) is at most weakly NPhard.more » « less