Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods

We consider symmetrized KKT systems arising in the solution of convex quadratic programming problems in standard form by Interior Point methods. Their coefficient matrices usually have 3×3 block structure and, under suitable conditions on both the quadratic programming problem and the solution, they are nonsingular in the limit. We present new spectral estimates for these … Read more

A Second-Order Method for Compressed Sensing Problems with Coherent and Redundant Dictionaries

In this paper we are interested in the solution of Compressed Sensing (CS) problems where the signals to be recovered are sparse in coherent and redundant dictionaries. CS problems of this type are convex with non-smooth and non-separable regularization term, therefore a specialized solver is required. We propose a primal-dual Newton Conjugate Gradients (pdNCG) method. … Read more

A mixed integer programming approach for asset protection during escaped wildfires

Incident Management Teams (IMTs) are responsible for managing the response to wildfires. One of the IMT’s objectives is the protection of assets and infrastructure. In this paper we develop a mathematical model to assist IMTs in assigning resources to asset protection activities during escaped wildfires. We present a mixed integer programming model for resource allocation … Read more

Primal-dual regularized SQP and SQCQP type methods for convex programming and their complexity analysis

This paper presents and studies the iteration-complexity of two new inexact variants of Rockafellar’s proximal method of multipliers (PMM) for solving convex programming (CP) problems with a fi nite number of functional inequality constraints. In contrast to the first variant which solves convex quadratic programming (QP) subproblems at every iteration, the second one solves convex constrained … Read more


We consider a problem in eigenvalue optimization, in particular find- ing a local minimizer of the spectral abscissa – the value of a parameter that results in the smallest magnitude of the largest real part of the spectrum of a matrix system. This is an important problem for the stabilization of control sys- tems. Many … Read more

Chance-Constrained Multi-Terminal Network Design Problems

We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum-cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose a scenario-based Steiner cut formulation, and a … Read more

How Good Are Sparse Cutting-Planes?

Sparse cutting-planes are often the ones used in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-\&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope $P$ (e.g. the integer hull of … Read more

Coordinate shadows of semi-definite and Euclidean distance matrices

We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definite and Euclidean distance completion problems. We characterize when these sets are closed, and use the boundary structure of these two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. … Read more

On the Complexity of the Traveling Umpire Problem

The traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during a double round-robin tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too … Read more

Zero-Convex Functions, Perturbation Resilience, and Subgradient Projections for Feasibility-Seeking Methods

The convex feasibility problem (CFP) is at the core of the modeling of many problems in various areas of science. Subgradient projection methods are important tools for solving the CFP because they enable the use of subgradient calculations instead of orthogonal projections onto the individual sets of the problem. Working in a real Hilbert space, … Read more