We derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We do this for a broad range of uncertainty sets. In particular, we show how to reformulate the support functions of uncertainty sets represented in terms of matrix norms and cones. Our … Read more
Semidefinite programs (SDPs) — some of the most useful and pervasive optimization problems of the last few decades — often behave pathologically: the optimal values of the primal and dual problems may differ and may not be attained. Such SDPs are theoretically interesting and often impossible to solve. Yet, the pathological SDPs in the literature … Read more
Asynchronous-parallel algorithms have the potential to vastly speed up algorithms by eliminating costly synchronization. However, our understanding to these algorithms is limited because the current convergence of asynchronous (block) coordinate descent algorithms are based on somewhat unrealistic assumptions. In particular, the age of the shared optimization variables being used to update a block is assumed … Read more
This paper establishes the iteration-complexity of a Jacobi-type non-Euclidean proximal alternating direction method of multipliers (ADMM) for solving multi-block linearly constrained nonconvex programs. The subproblems of this ADMM variant can be solved in parallel and hence the method has great potential to solve large scale multi-block linearly constrained nonconvex programs. Moreover, our analysis allows the … Read more
This article analyzes how the Unit Commitment Problem (UCP) complexity evolves with respect to the number n of units and T of time periods.A classical reduction from the knapsack problem shows that the UCP is NP-hard in the ordinary sense even for T=1. The UCP is proved to be strongly NP-hard.When either a unitary cost … Read more
This paper studies a general form problem in which a lower bounded continuously differentiable function is minimized over a block separable set incorporating a group sparsity expression as a constraint or a penalty (or both) in the group sparsity setting. This class of problems is generally hard to solve, yet highly applicable in numerous practical … Read more
In this paper, we study augmented Lagrangian functions for nonlinear semidefinite programming (NSDP) problems with exactness properties. The term exact is used in the sense that the penalty parameter can be taken appropriately, so a single minimization of the augmented Lagrangian recovers a solution of the original problem. This leads to reformulations of NSDP problems … Read more
Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton’s method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: … Read more
The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable … Read more
We present a branch-and-cut algorithm for solving discrete bilevel linear programs where the upper-level variables are binary and the lower-level variables are either pure integer or pure binary. This algorithm performs local search to find improved bilevel feasible solutions. We strengthen the relaxed node subproblems in the branch-and-cut search tree by generating cuts to eliminate … Read more