Publications

Andrés Gómez, Shaoning Han and Leonardo Lozano, “Real-Time Solution of Quadratic Optimization Problems with Banded Matrices and Indicator Variables,” Submitted, 2024.
[abstract] [bibtex] [url]

We consider mixed-integer quadratic optimization problems with banded matrices and indicator variables. These problems arise pervasively in statistical inference problems with time-series data, where the banded matrix captures the temporal relationship of the underlying process. In particular, the problem studied arises in monitoring problems, where the decision-maker wants to detect changes or anomalies. We propose to solve these problems using decision diagrams. In particular we show how to exploit the temporal dependencies to construct diagrams with size polynomial in the number of decision variables. We also describe how to construct the convex hull of the set under study from the decision diagrams, and how to deploy the method online to solve the problems in milliseconds via a shortest path algorithm.
```
@article{ghl2024realtime,

  author = {Gómez, Andrés and Han, Shaoning and Lozano, Leonardo},

  title = {Real-Time Solution of Quadratic Optimization Problems with Banded Matrices and Indicator Variables},

  year = {2024},

  url = {https://arxiv.org/abs/2405.03051}

}
```
Valentina Cepeda, Andrés Gómez and Shaoning Han, “Robust Support Vector Machines via Conic Optimization,” Submitted, 2024.
[abstract] [bibtex] [url]

We consider the problem of learning support vector machines robust to uncertainty. It has been established in the literature that typical loss functions, including the hinge loss, are sensible to data perturbations and outliers, thus performing poorly in the setting considered. In contrast, using the 0-1 loss or a suitable non-convex approximation results in robust estimators, at the expense of large computational costs. In this paper we use mixed-integer optimization techniques to derive a new loss function that better approximates the 0-1 loss compared with existing alternatives, while preserving the convexity of the learning problem. In our computational results, we show that the proposed estimator is competitive with the standard SVMs with the hinge loss in outlier-free regimes and better in the presence of outliers.
```
@article{cgh2024robust,

  author = {Cepeda, Valentina and Gómez, Andrés and Han, Shaoning},

  title = {Robust Support Vector Machines via Conic Optimization},

  year = {2024},

  url = {https://optimization-online.org/2024/02/robust-support-vector-machines-via-conic-optimization}

}
```
Shaoning Han, Ying Cui and Jong-Shi Pang, “Analysis of a Class of Minimization Problems Lacking Lower Semicontinuity,” Submitted, 2024.
[abstract] [bibtex] [url]

The minimization of non-lower semicontinuous functions is a difficult topic that has been minimally studied. Among such functions is a Heaviside composite function that is the composition of a Heaviside function with a possibly nonsmooth multivariate function. Unifying a statistical estimation problem with hierarchical selection of variables and a sample average approximation of composite chance constrained stochastic programs, a Heaviside composite optimization problem is one whose objective and constraints are defined by sums of possibly nonlinear multiples of such composite functions. Via a pulled-out formulation, a pseudo stationarity concept for a feasible point was introduced in an earlier work as a necessary condition for a local minimizer of a Heaviside composite optimization problem. The present paper extends this previous study in several directions: (a) showing that pseudo stationarity is implied by, thus weaker than, a sharper subdifferential based stationarity condition which we term epi-stationarity; (b) introducing a set-theoretic sufficient condition, which we term local convexity-like property, under which an epi-stationary point of a possibly non-lower semicontinuous optimization problem is a local minimizer; (c) providing several classes of Heaviside composite functions satisfying this local convexity-like property; (d) extending the epigraphical formulation of a nonnegative multiple of a Heaviside composite function to a lifted formulation for arbitrarily signed multiples of the Heaviside composite function, based on which we show that an epi-stationary solution of the given Heaviside composite program with broad classes of B-differentiable component functions can in principle be approximately computed by surrogation methods.
```
@article{hcp2023nonlsc,

  author = {Han, Shaoning and Cui, Ying and Pang, Jong-Shi},

  title = {Analysis of a Class of Minimization Problems Lacking Lower Semicontinuity},

  year = {2024},

  url = {https://optimization-online.org/2023/10/analysis-of-a-class-of-minimization-problems-lacking-lower-semicontinuity}

}
```
Shaoning Han, Xinyao Zhang and Jong-Shi Pang, “On the Number of Pivots of Dantzig's Simplex Methods for Linear and Convex Quadratic Programs,” Operations Research Letters, 2024.
[abstract] [bibtex] [url] [slides]

Refining and extending works by Ye and Kitahara-Mizuno, this paper presents new results on the number of pivots of simplex-type methods for solving linear programs of the Leontief kind, certain linear complementarity problems of the P kind, and nonnegatively constrained convex quadratic programs. Our results contribute to the further understanding of the complexity and efficiency of simplex-type methods for solving these problems. Two applications of the quadratic programming results are presented.
```
@article{hzp2023simplex,

  author = {Han, Shaoning and Zhang, Xinyao and Pang, Jong-Shi},

  title = {On the Number of Pivots of Dantzig's Simplex Methods for Linear and Convex Quadratic Programs},

  journal = { Operations Research Letters},

  year = {2024},

  url = {https://www.sciencedirect.com/science/article/pii/S0167637724000270},

  doi = {https://doi.org/10.1016/j.orl.2024.107091}

}
```
Shaoning Han, Andrés Gómez and Jong-Shi Pang, “On Polynomial-Time Solvability of Combinatorial Markov Random Fields,” Submitted, 2022.
[abstract] [bibtex] [url] [slides]

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 a suitable reformulation, indicator constraints preserve submodularity. Fast computations of the associated Lovász extensions are also discussed under certain smoothness conditions, and can be implemented using only linear-algebraic operations in the case of quadratic objectives.
```
@article{han2022polynomial,

  author = {Han, Shaoning and Gómez, Andrés and Pang, Jong-Shi},

  title = {On Polynomial-Time Solvability of Combinatorial Markov Random Fields},

  year = {2022},

  url = {https://arxiv.org/abs/2209.13161}

}
```
Shaoning Han and Jong-Shi Pang, “Continuous Selections of Solutions to Parametric Variational Inequalities,” SIAM Journal on Optimization, vol. 34, no. 1, pp. 870-892, 2024.
[abstract] [bibtex] [url]

Abstract. This paper studies the existence of a (Lipschitz) continuous (single-valued) solution function of parametric variational inequalities under functional and constraint perturbations. At the most elementary level, this issue can be explained from classical parametric linear programming and its resolution by the parametric simplex method, which computes a solution trajectory of the problem when the objective coefficients and the right-hand sides of the constraints are parameterized by a single scalar parameter. The computed optimal solution vector (and not the optimal objective value) is a continuous piecewise affine function in the parameter when the objective coefficients are kept constant, whereas the computed solution vector can be discontinuous when the right-hand constraint coefficients are kept fixed and there is a basis change at a critical value of the parameter in the objective. We investigate this issue more broadly first in the context of an affine variational inequality (AVI) and obtain results that go beyond those pertaining to the lower semicontinuity of the solution map with joint vector perturbations; the latter property is closely tied to a stability theory of a parametric AVI and in particular to Robinson’s seminal concept of strong regularity. Extensions to nonlinear variational inequalities is also investigated without requiring solution uniqueness (and therefore applicable to nonstrongly regular problems). The role of solution uniqueness in this issue of continuous single-valued solution selection is further clarified.
```
@article{han2022continuous,

  author = {Han, Shaoning and Pang, Jong-Shi},

  title = {Continuous Selections of Solutions to Parametric Variational Inequalities},

  journal = { SIAM Journal on Optimization},

  year = {2024},

  volume = {34},

  number = {1},

  pages = {870-892},

  url = {https://doi.org/10.1137/22M1514982},

  doi = {https://doi.org/10.1137/22M1514982}

}
```
Jong-Shi Pang and Shaoning Han, “Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables,” SIAM Journal on Optimization, vol. 33, no. 2, pp. 899-920, 2023.
[abstract] [bibtex] [url] [slides]

This paper begins with a class of convex quadratic programs (QPs) with bounded variables solvable by the parametric principal pivoting algorithm with 𝒪(n³) strongly polynomial complexity, where n is the number of variables of the problem. Extensions of this Hessian class are the main contributions of this paper, which is motivated by a recent paper [P. Liu, S. Fattahi, A. Gómez, and S. Küçükyavuz, Math. Program. (2022), https://doi.org/10.1007/s10107-022-01845-0], wherein the efficient solution of a quadratic program with a tridiagonal Hessian matrix in the quadratic objective is needed for the construction of a polynomial-time algorithm for solving an associated sparse variable selection problem. With the tridiagonal structure, the complexity of the QP algorithm reduces to 𝒪(n²). Our strongly polynomiality results extend previous works of some strongly polynomially solvable linear complementarity problems with a P-matrix [J. S. Pang and R. Chandrasekaran, Math. Program. Stud., 25 (1985), pp. 13–27]; special cases of the extended results include weakly quasi-diagonally dominant problems in addition to the tridiagonal ones.
```
@article{pang2023some,

  author = {Pang, Jong-Shi and Han, Shaoning},

  title = {Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables},

  journal = { SIAM Journal on Optimization},

  year = {2023},

  volume = {33},

  number = {2},

  pages = {899-920},

  url = {https://doi.org/10.1137/21M1463793},

  doi = {https://doi.org/10.1137/21M1463793}

}
```

Shaoning Han, Andrés Gómez and Alper Atamtürk, “The Equivalence of Optimal Perspective Formulation and Shor's SDP for Quadratic Programs with Indicator Variables,” Operations Research Letters, vol. 50, no. 2, pp. 195-198, 2022.
[abstract] [bibtex] [url]

In this paper, we compare the strength of the optimal perspective reformulation and Shor's SDP relaxation. We prove these two formulations are equivalent for quadratic optimization problems with indicator variables.


@article{han2021equiv,

  author = {Han, Shaoning and Gómez, Andrés and Atamtürk, Alper},

  title = {The Equivalence of Optimal Perspective Formulation and Shor's SDP for Quadratic Programs with Indicator Variables},

  journal = { Operations Research Letters},

  year = {2022},

  volume = {50},

  number = {2},

  pages = {195-198},

  url = {https://www.sciencedirect.com/science/article/pii/S0167637722000141},

  doi = {https://doi.org/10.1016/j.orl.2022.01.007}

}

Shaoning Han and Andrés Gómez, “Compact Extended Formulations for Low-Rank Functions with Indicator Variables,” Mathematics of Operations Research (Accepted), 2024.
[abstract] [bibtex] [url] [slides]
• Third Place, INFORMS Junior Faculty Interest Group (JFIG) Paper Competition, 2023

We study the mixed-integer epigraph of a low-rank convex function with non-convex indicator constraints, which are often used to impose logical constraints on the support of the solutions. Extended formulations describing the convex hull of such sets can easily be constructed via disjunctive programming, although a direct application of this method often yields prohibitively large formulations, whose size is exponential in the number of variables. In this paper, we propose a new disjunctive representation of the sets under study, which leads to compact formulations with size exponential in the rank of the function, but polynomial in the number of variables. Moreover, we show how to project out the additional variables for the case of rank-one functions, recovering or generalizing known results for the convex hulls of such sets (in the original space of variables).
```
@article{han2021compact,

  author = {Han, Shaoning and Gómez, Andrés},

  title = {Compact Extended Formulations for Low-Rank Functions with Indicator Variables},

  journal = { Mathematics of Operations Research (Accepted)},

  year = {2024},

  url = {https://optimization-online.org/2021/10/8659/}

}
```
Ziyu He, Shaoning Han, Andrés Gómez, Ying Cui and Jong-Shi Pang, “Comparing Solution Paths of Sparse Quadratic Minimization with a Stieltjes Matrix,” Mathematical Programming, vol. 204, pp. 517-566, 2024.
[abstract] [bibtex] [url] [slides]

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 "ℓ₀-path" where the discontinuous ℓ₀-function provides the exact sparsity count; the "ℓ₁-path" where the ℓ₁-function provides a convex surrogate of sparsity count; and the "capped ℓ₁-path" where the nonconvex nondifferentiable capped ℓ₁-function aims to enhance the ℓ₁-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new)properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped ℓ₁-path. Our study of the capped ℓ₁-path is the first of its kind as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped ℓ₁-regularized problem offers interesting theoretical properties and practical compromise between the ℓ₀-path and the ℓ₀-path. Indeed, while the ℓ₀-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed integer nonlinear programs, the quality of ℓ₁-path, in terms of the two criteria---loss and sparsity--- in the estimation objective, is inferior to the capped ℓ₁-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.
```
@article{he2023comparing,

  author = {He, Ziyu and Han, Shaoning and Gómez, Andrés and Cui, Ying and Pang, Jong-Shi},

  title = {Comparing Solution Paths of Sparse Quadratic Minimization with a Stieltjes Matrix},

  journal = { Mathematical Programming},

  year = {2024},

  volume = {204},

  pages = {517--566},

  url = {https://doi.org/10.1007/s10107-023-01966-0},

  doi = {https://doi.org/10.1007/s10107-023-01966-0}

}
```
Shaoning Han and Andrés Gómez, “Single-Neuron Convexifications for Binarized Neural Networks,” Technical Report, 2021.
[abstract] [bibtex] [url]

Binarized neural networks are an important class of neural network in deep learning due to their computational efficiency. This paper contributes towards a better understanding of the structure of binarized neural networks, specifically, ideal convex representations of the activation functions used. We describe the convex hull of the graph of the signum activation function associated with a single neuron, deriving closed forms for the convex and concave envelopes that improve upon those used in the literature. The new formulations lead to improved methods to verify the robustness of a binarized neural network via convex optimization.
```
@article{han2021single,

  author = {Han, Shaoning and Gómez, Andrés},

  title = {Single-Neuron Convexifications for Binarized Neural Networks},

  year = {2021},

  url = {http://www.optimization-online.org/DB_HTML/2021/05/8419.html}

}
```
Shaoning Han, Andrés Gómez and Alper Atamtürk, “2×2-Convexifications For Convex Quadratic Optimization with Indicator Variables,” Mathematical Programming, vol. 202, pp. 95-134, 2023.
[abstract] [bibtex] [url] [slides]

In this paper, we study the convex quadratic optimization problem with indicator variables. For the 2×2 case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the 2×2 case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including the optimal perspective relaxation and the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.
```
@article{HGA2023,

  author = {Han, Shaoning and Gómez, Andrés and Atamtürk, Alper},

  title = {2×2-Convexifications For Convex Quadratic Optimization with Indicator Variables},

  journal = { Mathematical Programming},

  year = {2023},

  volume = {202},

  pages = {95--134},

  url = {https://doi.org/10.1007/s10107-023-01924-w},

  doi = {https://doi.org/10.1007/s10107-023-01924-w}

}
```
Shaoning Han, Andrés Gómez and Oleg A. Prokopyev, “Fractional 0-1 Programming and Submodularity,” Journal of Global Optimization, vol. 84, pp. 77-93, 2022.
[abstract] [bibtex] [url] [slides]
• Honorable Mention, Journal of Global Optimization Best Paper Award, 2023

In this note we study multiple-ratio fractional 0--1 programs, a broad class of NP-hard combinatorial optimization problems. In particular, under some relatively mild assumptions we provide a complete characterization of the conditions, which ensure that a single-ratio function is submodular. Then we illustrate our theoretical results with the assortment optimization and facility location problems, and discuss practical situations that guarantee submodularity in the considered application settings. In such cases, near-optimal solutions for multiple-ratio fractional 0--1 programs can be found via simple greedy algorithms.
```
@article{han2019fractional,

  author = {Han, Shaoning and Gómez, Andrés and Prokopyev, Oleg A},

  title = {Fractional 0-1 Programming and Submodularity},

  journal = { Journal of Global Optimization},

  year = {2022},

  volume = {84},

  pages = {77--93},

  url = {https://doi.org/10.1007/s10898-022-01131-5}

}
```
Alper Atamtürk, Andrés Gómez and Shaoning Han, “Sparse and Smooth Signal Estimation: Convexification of ℓ₀-Formulations,” Journal of Machine Learning Research, vol. 22, no. 52, pp. 1-43, 2021. [alphabetical order]
[abstract] [bibtex] [url]

Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with ℓ₀-``norm" constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on ℓ₁-norm relaxations. In this paper, we propose new iterative conic quadratic relaxations that exploit not only the ℓ₀-``norm" terms, but also the fitness and smoothness functions. The iterative convexification approach substantially closes the gap between the ℓ₀-``norm" and its ℓ₁ surrogate. Experiments using an off-the-shelf conic quadratic solver on synthetic as well as real datasets indicate that the proposed iterative convex relaxations lead to significantly better estimators than ℓ₁-norm while preserving the computational efficiency. In addition, the parameters of the model and the resulting estimators are easily interpretable.
```
@article{atamturk2021sparse,

  author = {Atamtürk, Alper and Gómez, Andrés and Han, Shaoning},

  title = {Sparse and Smooth Signal Estimation: Convexification of ℓ₀-Formulations},

  journal = { Journal of Machine Learning Research},

  year = {2021},

  volume = {22},

  number = {52},

  pages = {1--43},

  url = {https://www.jmlr.org/papers/volume22/18-745/18-745.pdf}

}
```