Salar Fattahi

Probabilistically Exact Convexification of Mixed-Integer Quadratic Optimization with Indicators

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming Tags , ,

We study the convexification of mixed-integer quadratic optimization with indicator variables. The problem remains NP-hard even when the quadratic matrix has bandwidth two, posing a fundamental obstacle to tractable exact convexification. To overcome this challenge in realistic settings, we introduce probabilistically exact (inner) convexification, a framework that relaxes the requirement of exactness for every objective … Read more

Convexification of mixed-integer quadratic optimization via decision diagrams

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming Tags , ,

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 … Read more

On the Absence of Identifiable Manifolds in Finite-Max Composite Optimization

Categories Nonlinear Optimization, Nonsmooth Optimization, Other Topics Tags , ,

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 … Read more

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

We consider mixed-integer convex optimization problems in which binary indicators control continuous variables. We introduce the Coordinate Optimality Reformulation (CORe) framework, which augments standard indicator formulations by incorporating coordinate-wise optimality information. The resulting reformulations preserve global optimality while substantially improving branch-and-bound performance, particularly in sparse and structured settings where the coordinate-wise optimality conditions expose exploitable … Read more

Solving Convex Quadratic Optimization with Indicators Over Structured Graphs

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming Tags ,

This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more

A Parametric Approach for Solving Convex Quadratic Optimization with Indicators Over Trees

Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Quadratic Programming Tags , , , , ,

This paper investigates convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this … Read more

Solution Path of Time-varying Markov Random Fields with Discrete Regularization

Categories Dynamic Programming, Integer Programming, Optimization in Data Science

We study the problem of inferring sparse time-varying Markov random fields (MRFs) with different discrete and temporal regularizations on the parameters. Due to the intractability of discrete regularization, most approaches for solving this problem rely on the so-called maximum-likelihood estimation (MLE) with relaxed regularization, which neither results in ideal statistical properties nor scale to the … Read more

On the Optimization Landscape of Burer-Monteiro Factorization: When do Global Solutions Correspond to Ground Truth?

Categories Global Optimization, Nonlinear Optimization, Optimization in Data Science Tags , ,

In low-rank matrix recovery, the goal is to recover a low-rank matrix, given a limited number of linear and possibly noisy measurements. Low-rank matrix recovery is typically solved via a nonconvex method called Burer-Monteiro factorization (BM). If the rank of the ground truth is known, BM is free of sub-optimal local solutions, and its true solutions … Read more

Simple Alternating Minimization Provably Solves Complete Dictionary Learning

Categories Optimization in Data Science

This paper focuses on complete dictionary learning problem, where the goal is to reparametrize a set of given signals as linear combinations of atoms from a learned dictionary. There are two main challenges faced by theoretical and practical studies of dictionary learning: the lack of theoretical guarantees for practically-used heuristic algorithms, and their poor scalability … Read more

Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition

Categories Optimization in Data Science

This work analyzes the solution trajectory of gradient-based algorithms via a novel basis function decomposition. We show that, although solution trajectories of gradient-based algorithms may vary depending on the learning task, they behave almost monotonically when projected onto an appropriate orthonormal function basis. Such projection gives rise to a basis function decomposition of the solution … Read more