Here are my papers. The titles are also links to the content (if available).
Preprints
Tensor Completion via Integer Optimization
Submitted to Mathematical Programming
X. Chen, S. Kudva, Y. Dai, A. Aswani, C. Chen
The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution, or have polynomial-time algorithms that require an exponentially-larger number of samples for low estimation error. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate. Our approach formulates tensor completion as a convex optimization problem constrained using a gauge-based tensor norm, which is defined in a way that allows the use of integer linear optimization to solve linear separation problems over the unit-ball in this new norm. Adaptations based on this insight are incorporated into a Frank-Wolfe variant to build our algorithm. We show our algorithm scales-well using numerical experiments on tensors with up to ten million entries.
Parallelized Conflict Cut Generation
Y. Dai, C. Chen
Published/Accepted
Mixed-Integer Exponential Conic Optimization for Reliability Enhancement of Power Distribution Systems
Optimization and Engineering, 2023.
M. Dehghani Filabadi, C. Chen, A. Conejo
This paper develops an optimization model for determining the placement of switches, tie lines, and underground cables in order to enhance the reliability of an electric power distribution system. A central novelty in the model is the inclusion of nodal reliability constraints, which consider network topology and are important in practice. The model can be reformulated either as a mixed-integer exponential conic optimization problem or as a mixed-integer linear program. We demonstrate both theoretically and empirically that the judicious application of partial linearization is key to rendering a practically tractable formulation. Computational studies indicate that realistic instances can indeed be solved in a reasonable amount of time on standard hardware.
Distributed Projections onto a Simplex
INFORMS Journal on Computing, 2023.
Y. Dai, C. Chen
Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, all but one of these algorithms are serial. We address this gap by developing a method that preprocesses the input vector by decomposing and distributing it across multiple processors for local projection. Our method is especially effective when the projection is highly sparse; which is the case, for instance, in large-scale problems with i.i.d. entries. Moreover, the method can be adapted to work with a broad range of serial algorithms from the literature. We fill in theoretical gaps in serial algorithm analysis, and develop similar results for our parallel analogues. Numerical experiments conducted on a wide range of large-scale instances demonstrate the practical effectiveness of the method.
Accelerated Non-Negative Tensor Completion via Integer Programming
Frontiers in Applied Mathematics and Statistics, 2023.
W. Pan, A. Aswani, C. Chen
The problem of tensor completion has applications in healthcare, computer vision, and other domains. However, past approaches to tensor completion have faced a tension in that they either have polynomial-time computation but require exponentially more samples than the information-theoretic rate, or they use fewer samples but require solving NP-hard problems for which there are no known practical algorithms. A recent approach, based on integer programming, resolves this tension for non-negative tensor completion. It achieves the information-theoretic sample complexity rate and deploys the blended conditional gradients algorithm, which requires a linear (in numerical tolerance) number of oracle steps to converge to the global optimum. The tradeoff in this approach is that, in the worst case, the oracle step requires solving an integer linear program. Despite this theoretical limitation, numerical experiments show that this algorithm can, on certain instances, scale up to 100 million entries while running on a personal computer. The goal of this study is to further enhance this algorithm, with the intention to expand both the breadth and scale of instances that can be solved. We explore several variants that can maintain the same theoretical guarantees as the algorithm but offer potentially faster computation. We consider different data structures, acceleration of gradient descent steps, and the use of the blended pairwise conditional gradients algorithm. We describe the original approach and these variants, and conduct numerical experiments in order to explore various tradeoffs in these algorithmic design choices.
Nonnegative Tensor Completion via Integer Optimization
NeurIPS, 2022.
C. Bugg, C. Chen, A. Aswani
Unlike matrix completion, no algorithm for the tensor completion problem has so far been shown to achieve the information-theoretic sample complexity rate. This paper develops a new algorithm for the special case of completion for nonnegative tensors. We prove that our algorithm converges in a linear (in numerical tolerance) number of oracle steps, while achieving the information-theoretic rate. Our approach is to define a new norm for nonnegative tensors using the gauge of a specific 0-1 polytope that we construct. Because the norm is defined using a 0-1 polytope, this means we can use integer linear programming to solve linear separation problems over the polytope. We combine this insight with a variant of the Frank-Wolfe algorithm to construct our numerical algorithm, and we demonstrate its effectiveness and scalability through experiments.
Outer-Product-Free Sets for Polynomial Optimization and Oracle-Based Cuts
Mathematical Programming, 2020.
D. Bienstock, C. Chen, G. Muñoz
Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S∩P, where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S we construct a convergent pure cutting plane algorithm; if the initial relaxation is a polytope, the algorithm is shown to converge. Cuts are generated from convex forbidden zones, or S-free sets derived from the oracle. We also consider the special case of polynomial optimization. Polynomial optimization may be represented using a symmetric matrix of variables, and in this lifted representation we can let S be the set of matrices that are real, symmetric outer products. Accordingly we develop a theory of outer-product-free sets. All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify two families of such sets. These families can be used to generate intersection cuts that can separate any infeasible extreme point of a linear programming relaxation in polynomial time. Moreover, the oracle-based approach can be strengthened and implemented in polynomial-time for polynomial optimization.
Intersection Cuts for Polynomial Optimization
IPCO, 2019
D. Bienstock, C. Chen, G. Muñoz
We consider dynamically generating linear constraints (cutting planes) to tighten relaxations for polynomial optimization problems. Many optimization problems have feasible set of the form S∩P, where S is a closed set and P is a polyhedron. Integer programs are in this class and one can construct intersection cuts using convex “forbidden” regions, or S-free sets. Here, we observe that polynomial optimization problems can also be represented as a problem with linear objective function over such a feasible set, where S is the set of real, symmetric matrices representable as outer-products of the form xx^T. Accordingly, we study outer-product-free sets and develop a thorough characterization of several (inclusion-wise) maximal intersection cut families. In addition, we present a cutting plane approach that guarantees polynomial-time separation of an extreme point in P∖S using our outer-product-free sets. Computational experiments demonstrate the promise of our approach from the point of view of strength and speed.
A Spatial Branch-and-Cut Algorithm for Nonconvex QCQP with Bounded Complex Variables
Mathematical Programming, 2016
C. Chen, A. Atamtürk and S.S. Oren
We develop a spatial branch-and-cut approach for nonconvex Quadratically Constrained Quadratic Programs with bounded complex variables (CQCQP). Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP. These valid inequalities are derived from the convex hull description of a nonconvex set of 2×2 positive semidefinite Hermitian matrices subject to rank-one constraint. We propose branching rules based on an alternative to a rank-one constraint that allows for local measurement of constraint violation. Closed-form bound tightening procedures are used to reduce the domain of the problem. We apply the algorithm to solve the Alternating Current Optimal Power Flow problem with complex variables and the Box-constrained Quadratic Programming problem with real variables.
Bound Tightening for the Alternating Current Optimal Power Flow Problem
IEEE Transactions on Power Systems, 2015
C. Chen, A. Atamtürk and S.S. Oren
We consider the Alternating Current Optimal Power Flow (ACOPF) problem, formulated as a nonconvex Quadratically-Constrained Quadratic Program (QCQP) with complex variables. ACOPF may be solved to global optimality with a semidefinite programming (SDP) relaxation in cases where its QCQP formulation attains zero duality gap. However, when there is positive duality gap, no optimal solution to the SDP relaxation is feasible for ACOPF. One way to find a global optimum is to partition the problem using a spatial branch- and-bound method. Tightening upper and lower variable bounds can improve solution times in spatial branching by potentially reducing the number of partitions needed. We propose special- purpose closed-form bound tightening methods to tighten limits on nodal powers, line flows, phase angle differences, and voltage magnitudes. Computational experiments are conducted using a spatial branch-and-cut solver. We construct variants of IEEE test cases with high duality gaps to demonstrate the effectiveness of the bound tightening procedures.
Robust Portfolio Selection for Index Tracking
Computers & Operations Research, 2012
C. Chen and R.H. Kwon
We develop a robust portfolio selection model for tracking a market index using a subset of its assets. The model is a 0–1 integer program that seeks to maximize similarity between selected assets and the assets of the target index. We allow uncertainty in the objective function by using a computationally tractable robust framework that can control the conservativeness of the solution. This protects against worst-case realizations of potential estimation errors and other deviations. Out-of-sample experiments using the S&P 100 demonstrate the advantages of the robust model. Compared to portfolios constructed with the nominal model, moderately conservative robust portfolios are shown to have lower tracking error and risk profiles that are more similar to the target index.
Dissertation Abstract
Title: Branch-and-Cut for Nonlinear Power Systems Problems
Dissertation Committee: Shmuel S. Oren (Chair), Alper Atamtürk, Kameshwar Poolla, David Tse
This dissertation is concerned with the design of branch-and-cut algorithms for a variety of nonconvex nonlinear problems pertaining to power systems operations and planning. By understanding the structure of specific problems, we can leverage powerful commercial optimization solvers designed for convex optimization and mixed-integer programs. The bulk of the work concerns the Alternating Current Optimal Power Flow (ACOPF) problem. The ACOPF problem is to find a minimum cost generation dispatch that will yield flows that can satisfy demand as well as various engineering constraints. A standard formulation can be posed as a nonconvex Quadratically Constrained Quadratic Program with complex variables. We develop a novel spatial branch-and-bound algorithm for generic nonconvex QCQP with bounded complex variables that relies on a semidefinite programming (SDP) relaxation strengthened with linear valid inequalities. ACOPF-specific domain reduction or bound tightening techniques are also introduced to improve the algorithm’s convergence rate. We also introduce second-order conic valid inequalities so that any SDP can be outer-approximated with conic quadratic cuts and test the technique on ACOPF. Another application is the incorporation of convex quadratic costs in unit commitment, which is a multi-period electric generation scheduling problem. We show that conic reformulation can both theoretically and practically improve performance on this mixed-integer nonlinear problem. We conclude with methods for approximating a mixed-integer convex exponential constraint. Applications include capital budgeting, the system reliability redundancy problem, and feature subset selection for logistic regression.