Research

Research Topics: integer programming, mixed-integer nonlinear optimization, data analytics

Studied the parameter Δ of integer programs defined by equations and box constraints (Δ is the maximum absolute determinants among the basis of constraint matrix)
Gave the first column number bound that is polynomial in both Δ and the number of equations
Gave a tight bound on the number of differing columns in a bimodular constraint matrix, which is the first tight bound since Heller's result on TU matrices
Gave the column number bound that is best possible up to a polynomial in Δ by discovering forbidden submatrices and combining these with results from extremal matroid theory

Joseph Paat, Ingo Stallknecht, Zach Walsh, X.. On the column number and forbidden sumatrices of Delta-modular matrices. SIAM Journal on Discrete Mathematics, 38(1):1-18, 2024.

Jon Lee, Joseph Paat, Ingo Stallknecht, X.. Polynomial upper bounds on the number of differing columns of Δ-modular integer programs. Mathematics of Operations Research, 48(4):2267–2286, 2022.

Aimed to give a tighter bound or show the tightness of the bound for the distance between the optimal solution of IP (MIP) and its LP relaxation
Gave a tighter bound for mixed-integer linear optimization with k-regular coefficient matrices (k-regular is related with circuit imbalanced measure)
Gave the first polynomial bound in both m and Δ on proximity by using the recent sparsity results
Gave another polynomial bound in both m and Δ on proximity by using the column number bound
Implemented in SageMath to compute the sharp proximity bounds for small m and Δ: https://github.com/xuluze/proximity

Matthias Köppe, Moises Reyes Rivas, and X.. (2024). Determining Sharp Proximity Bounds For Low Row Rank and ∆-Modularity. Accepted in 2024 INFORMS Optimization Society Conference.

Jon Lee, Joseph Paat, Ingo Stallknecht, X.. Polynomial upper bounds on the number of differing columns of Δ-modular integer programs. Mathematics of Operations Research, 48(4):2267–2286, 2022.
Jon Lee, Joseph Paat, Ingo Stallknecht, X.. Improving proximity bounds using sparsity. ISCO 2020, 115-127. Lecture Notes in Computer Science, Springer.
X., Jon Lee. On proximity for k-regular mixed-integer linear optimization. In: WCGO 2019: Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2020, Le Hoai An Thi, Hoai Minh Le, Tao Pham Dinh, eds. pp. 438-447.

Investigated extended formulations of a class of Δ-modular IPs based on structural matroid properties.
Demonstrated a broader class of problems that have a polynomial-sized extended formulation
Reduced the gap between Δ-modular IP examples with polynomial-sized and exponential-sized extended formulations in the literature.

Aimed to investigate the structure of integer points in convex cones, motivated by mixed-integer conic optimization
Generalized the notion of Hilbert basis to non-polyhedral cones with group action and introduced (R,G)-finitely generation
Proved that second-order cone up to dimension 10 and positive semidefinite matrices cone in any dimension are (R, G)-finitely generated
Up to dimension 5, integer PSD matrix can be written as the sum of rank 1 integer matrices

Jesús De Loera, Brittney Marsters, X., Shixuan Zhang. (2023). Integer points in arbitrary convex cones: the case of the PSD and SOC cones. A conference version is accepted in the 25th Conference on Integer Programming and Combinatorial Optimization (IPCO) 2024.

Studied the MINLO (Mixed-Integer Nonlinear Optimization) formulations of the disjunction: y is zero when x is zero, and y is a convex function when x belongs to an interval not including 0.
Investigated various relaxations related to piecewise-linear under-estimators of the convex function
Used volume as a metric to characterize the optimal placement of linearization points for convex power functions and analyzed the monotone behavior of Newton's method on our volume minimization problem
linked volume computation to integration over a simplex and extend some of the univariate results to multivariate functions on simplices
Used the triangulation approach to address the difficulties of multivariate functions on box domains

Jon Lee, Daphne Skipper, Emily Speakman, X.. (2020). Gaining or losing perspective for piecewise-linear under-estimators of convex univariate functions. Journal of Optimization Theory and Applications, 196:1-35, 2023.

Aimed to smooth univariate functions with some non-smooth properties as square root function in the context of global optimization of MINLO (Mixed-Integer Nonlinear Optimization)
Used a successful approach from D' Ambrosio et al to replace part of the original function on [0,delta] with a homogeneous cubic, matching the function and its first two derivatives at delta
Gave a necessary and sufficient condition for virtuous smoothing functions to keep the good properties of original functions, such as increasing and concave
Generalized the previous lower bound and better bound results of virtuous smoothing functions to all root functions and beyond

X., Jon Lee, Daphne Skipper. More virtuous smoothing. SIAM Journal on Optimization, 29(2):1240–1259, 2019.

In applications such as least-squares regression, only certain properties of the Moore-Penrose (M-P) pseudoinverse are necessary.
Aimed to balance the tradeoff between properties of the Moore-Penrose pseudoinverse and alternative sparser generalized inverses via techniques of sparse optimization
Designed new block construction recipes and approximation algorithms to a 1-norm minimizing symmetric reflexive generalized inverse of a symmetric matrix
Designed new block construction recipes and approximation algorithms to a 1-norm minimizing ah-symmetric (or ha-symmetric) reflexive generalized inverse
Analyzed the approximation ratios of the local search approximation algorithms

Investigated 2,1-norm aimed at row-sparse generalized inverses
Showed that 2,1-norm minimizing generalized inverses satisfy the properties for least-squares solutions
Established a 2,1-norm approximation result for a local-search procedure that was originally designed for 1-norm minimization
Compared the ADMM algorithms with the local-search procedure and with general-purpose optimization solver

Gabriel Ponte, Marcia Fampa, Jon Lee, X.. On computing sparse generalized inverses. Operations Research Letters, 52:107058, 2024.

Report abuse