We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more
Motivated by the need for reliable traffic management under fluctuating travel demand, we study the problem of determining the worst-case congestion in a multi-commodity traffic network subject to demand uncertainty. To this end, we stress-test a given network by identifying demand realizations and corresponding travelers’ route choices that maximize congestion. The users of the traffic … Read more
We develop a successive, proximal difference-of-convex (DC) function penalty method for solving DC programs with DC constraints. The proposed approach relies on a DC penalty function that measures the violation of constraints and leads to a penalty reformulation sharing the same solution set as the original problem. The resulting penalty problem is a DC program … Read more
We present an effective warm-starting scheme for solving large linear complementarity problems (LCPs) arising from Nash equilibrium problems. The approach generates high-quality starting points that, when passed to the PATH solver, yield substantial reductions in computational time and variance. Our warm-start routine reformulates each agent’s LP using strong duality, leading to a master problem with … Read more
Over the last decades, using piecewise-linear mixed-integer relaxations of nonlinear expressions has become a strong alternative to spatial branching for solving mixed-integer nonlinear programs. Since these relaxations give rise to large numbers of binary variables that encode interval selections, strengthening them is crucial. We investigate how to exploit the resulting combinatorial structure by integrating cutting-plane … Read more
We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in \(n\) variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm … Read more
Convex maximization encompasses a broad class of optimization problems and is generally $\mathsf{NP}$-hard, even for low-rank objectives. While polynomial solvability has been established for several important special cases, a broader structural understanding for mixed-integer settings remains limited. In this paper, we study this question from a geometric perspective and identify a structural property of the … Read more
This paper surveys optimization problems arising in agriculture, energy systems, and water-energy coordination from an operations research perspective. These problems are commonly formulated as integer nonlinear programs, mixed-integer nonlinear programs, or combinatorial set optimization models, characterized by nonlinear physical constraints, discrete decisions, and intertemporal coupling. Such structures pose significant computational challenges in large-scale and repeated-solution … Read more
This work considers polynomial optimization problems where the objective admits a low-rank canonical polyadic tensor decomposition. We introduce LRPOP (low-rank polynomial optimization), a new hierarchy of semidefinite programming relaxations for which the size of the semidefinite blocks is determined by the canonical polyadic rank rather than the number of variables. As a result, LRPOP can … Read more
We study the Heilbronn triangle problem, which involves placing \(n\) points in the unit square such that the minimum area of any triangle formed by these points is maximized. A straightforward maximin formulation of this problem is highly non-linear and non-convex due to the existence of bilinear terms and absolute value equations. We propose two … Read more