We study mixed-integer quadratic optimization (MIQO) problems with indicator variables. We propose a unified framework, based on decision diagrams, that serves both to solve the associated optimization problems and to construct ideal conic quadratic extended formulations of the closure of the convex hull of the underlying mixed-integer set. The construction applies to arbitrary quadratics and to any combinatorial constraints admitting a tractable dynamic programming representation. The resulting diagrams and the ensuing convex hull descriptions are of polynomial size when the quadratic is low-rank, or when the support graph of the Hessian or of its inverse is a tree, recovering and generalizing several results from the literature. For structured sparse and inverse-sparse quadratics, we show that approximate decision diagrams have size linear in the dimension while yielding solutions with arbitrarily low optimality gap. Computational experiments demonstrate the effectiveness of the proposed approach.
Soobin Choi, S. Fattahi, Andrés Gómez et al.· 0 citations
Distributionally robust optimization (DRO) with optimal transport ambiguity sets is traditionally solved by reformulating the minimax problem into a single-level convex program. While theoretically tractable, these reformulations introduce numerous auxiliary variables and demanding conic constraints that scale poorly in practice. In this paper, we address this challenge by reducing the inner worst-case expectation problem exactly to a scalar budget allocation task. This structural insight yields an efficient algorithm that bypasses large lifted reformulations, alongside a fast post-processing scheme to recover an optimal worst-case distribution supported on at most $N+1$ points, where $N$ denotes the sample size. We embed this procedure within an oracle-based distributional best-response framework to directly compute an approximate primal-dual solution to the overall DRO problem. Furthermore, we extend our analysis to the dual DRO formulation, proving the existence of a least-favorable distribution supported on at most $\min\{N+n+1, KN\}$ atoms, where $n$ and $K$ denote the decision dimension and number of loss components, respectively, and provide an efficient convex programming reduction to extract it from the solution of the primal DRO. Numerical experiments demonstrate that the proposed approach significantly outperforms state-of-the-art reformulation-based solvers.
Guixian Chen, S. Fattahi, Soroosh Shafiee· 1 citation
In nonsmooth optimization, identifiable sets describe the local region eventually reached by sequences converging to a prescribed critical point. When such a set is a $C^2$ manifold on which the objective restricts to a $C^2$ function, it is called an identifiable manifold. Their appeal lies in what they enable: many first-order methods identify these manifolds in finitely many iterations, after which the iterates enter a region in which the problem is effectively smooth. Consequently, many powerful tools and guarantees from smooth optimization transplant naturally to the nonsmooth setting. Owing to these properties, much existing work has focused on characterizing conditions that guarantee their existence. In this work, we study a complementary question: under what conditions is a critical point devoid of any identifiable manifold? We answer this by developing a deterministic branching criterion for a broad class of finite-max composite optimization problems, characterizing when a critical point admits no identifiable manifold. This criterion is surprisingly mild in certain classes of problems: it holds with high probability for overparameterized robust low-rank recovery and almost surely at common interpolators of random minimax regression, suggesting that the absence of identifiable manifolds may be the rule rather than the exception in modern optimization.