On polynomial time solvability of combinatorial Markov random fields

The problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled as a mixed-integer program. This motivates us to study a general class of convex submodular optimization problems with indicator variables, which we show to be polynomially solvable in this paper. The key insight is that, possibly after … Read more

Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables

This paper begins with a class of convex quadratic programs (QPs) with bounded variables solvable by the parametric principal pivoting algorithm with $\mbox{O}(n^3)$ strongly polynomial complexity, where $n$ is the number of variables of the problem. Extension of the Hessian class is also discussed. Our research is motivated by a recent reference [7] wherein the … Read more

Comparing Solution Paths of Sparse Quadratic Minimization with a Stieltjes Matrix

This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “L0-path” where the discontinuous L0-function provides the exact sparsity count; the “L1-path” where the L1-function provides a convex surrogate of sparsity count; … Read more

An Enhanced Logical Benders Approach for Linear Programs with Complementarity

This work extends the ones of Hu et al. (2008) and Bai et al. (2013) of a logical Benders approach for globally solving Linear Programs with Complementarity Constraints. By interpreting the logical Benders method as a reversed branch-and-bound method, where the whole exploration procedure starts from the leaf nodes in an enumeration tree, we provide … Read more

Two-stage Stochastic Programming with Linearly Bi-parameterized Quadratic Recourse

This paper studies the class of two-stage stochastic programs (SP) with a linearly bi-parameterized recourse function defined by a convex quadratic program. A distinguishing feature of this new class of stochastic programs is that the objective function in the second stage is linearly parameterized by the first-stage decision variable, in addition to the standard linear … Read more

Structural Properties of Affine Sparsity Constraints

We introduce a new constraint system for sparse variable selection in statistical learning. Such a system arises when there are logical conditions on the sparsity of certain unknown model parameters that need to be incorporated into their selection process. Formally, extending a cardinality constraint, an affine sparsity constraint (ASC) is defined by a linear inequality … Read more

Solving Linear Programs with Complementarity Constraints using Branch-and-Cut

A linear program with linear complementarity constraints (LPCC) requires the minimization of a linear objective over a set of linear constraints together with additional linear complementarity constraints. This class has emerged as a modeling paradigm for a broad collection of problems, including bilevel programs, Stackelberg games, inverse quadratic programs, and problems involving equilibrium constraints. The … Read more

A Study of the Difference-of-Convex Approach for Solving Linear Programs with Complementarity Constraints

This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a … Read more

On QPCCs, QCQPs and Completely Positive Programs

This paper studies several classes of nonconvex optimization problems defined over convex cones, establishing connections between them and demonstrating that they can be equivalently formulated as convex completely positive programs. The problems being studied include: a quadratically constrained quadratic program (QCQP), a quadratic program with complementarity constraints (QPCC), and rank constrained semidefinite programs. Our results … Read more

Complementarity Formulations of l0-norm Optimization Problems

In a number of application areas, it is desirable to obtain sparse solutions. Minimizing the number of nonzeroes of the solution (its l0-norm) is a difficult nonconvex optimization problem, and is often approximated by the convex problem of minimizing the l1-norm. In contrast, we consider exact formulations as mathematical programs with complementarity constraints and their … Read more