Solving Constrained Affine Heaviside Composite Optimization Problems by a Progressive IP Approach
Pith reviewed 2026-05-08 08:24 UTC · model grok-4.3
The pith
An approximation followed by progressive integer programming finds local solutions to affine Heaviside composite problems despite discontinuous objectives and non-closed feasible sets.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By replacing the discontinuous Heaviside functions with a suitable continuous approximation that restores semicontinuity of the objective and closedness of the feasible set, the progressive integer programming algorithm with successive decomposition generates a sequence of points that converges to a local optimizer of the original constrained affine Heaviside composite problem.
What carries the argument
Progressive integer programming (PIP) method with successive decomposition, applied after an approximation that restores semicontinuity and closedness.
If this is right
- Local solutions to A-HSCOPs become computable for problems whose objective and constraints mix positive and negative Heaviside terms.
- The same progressive decomposition strategy extends directly to any optimization model whose nondifferentiable inner functions admit a similar integer-programming reformulation.
- Precision-constrained multiclass classifiers can be trained by treating the precision requirement as a Heaviside-defined inequality.
- Convergence guarantees hold for both score-based and tree-based feature representations once the approximation parameter is driven to zero.
Where Pith is reading between the lines
- The method may be adaptable to other discontinuous step-function models such as threshold-based decision rules in reinforcement learning.
- If the inner functions are themselves piecewise linear, the successive decomposition could be replaced by a single mixed-integer quadratic program without loss of exactness.
- The approximation step suggests a general template for converting semicontinuity failures into tractable continuous relaxations before discrete refinement.
Load-bearing premise
The chosen approximation is close enough to the original Heaviside functions that the local solutions recovered by the integer program remain local solutions of the true discontinuous problem.
What would settle it
Run the full PIP procedure on a small multiclass classification instance with known global optima and check whether the returned point satisfies the original (non-approximated) objective and constraints to within a prescribed tolerance.
read the original abstract
This paper discusses the computational resolution and presents numerical results for solving affine combinations of Heaviside composite optimization problems (abbreviated as A-HSCOPs) by a progressive integer programming (abbreviated as PIP) method. The characteristics of these problems are that the Heaviside functions, which appear in the objective and define the constraints, are discontinuous, and their mixed-signed combinations result in the overall objective lacking the matching semicontinuity needed for the optimization and in the feasible set being not necessarily closed. Added to these challenging properties is the nondifferentiability of the inner functions in the composition. In this paper, we propose resolutions to all these challenges by first an approximation to remedy the lack of semicontinuity in the objective and closedness in the constraints, followed by a progressive integer programming approach with successive decomposition to handle the intrinsically discrete nature of the Heaviside function. Convergence to the local optimizers of the given Heaviside optimization problem is established. The effectiveness of the overall solution strategy is supported by extensive computational experiments on the score-based and tree-based multiclass classification problems with precision constraints.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes a progressive integer programming (PIP) method for solving constrained affine Heaviside composite optimization problems (A-HSCOPs). It first introduces an approximation scheme to restore semicontinuity of the objective and closedness of the feasible set (which are lost due to mixed-signed discontinuous Heaviside functions), then applies successive decomposition within the PIP framework to manage the discrete nature of the Heaviside terms and the nondifferentiability of inner functions. The paper claims to establish convergence of the method to local optimizers of the original problem and demonstrates effectiveness via numerical experiments on score-based and tree-based multiclass classification tasks subject to precision constraints.
Significance. If the convergence result and the validity of the approximation hold, the work supplies a concrete algorithmic framework for a class of nonsmooth, discontinuous optimization problems that arise naturally in constrained classification and decision models. The combination of regularization-style approximation with progressive IP decomposition is a targeted response to the specific pathologies of affine Heaviside compositions; the reported computational results on practical multiclass problems with precision constraints provide initial evidence of tractability. Such a method could be useful in operations-research and machine-learning settings where indicator-like functions must be optimized under constraints.
major comments (2)
- [Abstract / approximation step] Abstract and the approximation section: the central claim that the proposed approximation 'remedies the lack of semicontinuity in the objective and closedness in the constraints' is load-bearing for the subsequent convergence statement, yet the manuscript provides no explicit construction of the regularized Heaviside (e.g., the precise smoothing function or the schedule for the regularization parameter) that would allow verification that the approximated feasible sets remain closed and that their limit points recover the original problem's local minimizers.
- [Convergence result] Convergence theorem (presumably §4): the proof that the progressive IP iterates converge to local optimizers of the original A-HSCOP must explicitly address how the successive decomposition interacts with the nondifferentiability of the inner functions; without a clear statement of the stationarity concept used for the nondifferentiable case and how the IP subproblems enforce it, the convergence result cannot be assessed for completeness.
minor comments (2)
- [Abstract] The abstract introduces the abbreviations A-HSCOPs and PIP but does not spell out 'affine Heaviside composite optimization problems' on first use; this should be corrected for readability.
- [Numerical experiments] The numerical section would benefit from a brief table summarizing the dimensions of the test instances (number of variables, number of constraints, number of classes) so that readers can quickly gauge the scale of the reported experiments.
Simulated Author's Rebuttal
We thank the referee for the thorough and constructive review. We address each major comment below and indicate the revisions we will make to improve clarity.
read point-by-point responses
-
Referee: [Abstract / approximation step] Abstract and the approximation section: the central claim that the proposed approximation 'remedies the lack of semicontinuity in the objective and closedness in the constraints' is load-bearing for the subsequent convergence statement, yet the manuscript provides no explicit construction of the regularized Heaviside (e.g., the precise smoothing function or the schedule for the regularization parameter) that would allow verification that the approximated feasible sets remain closed and that their limit points recover the original problem's local minimizers.
Authors: The approximation scheme is defined in Section 3, where the regularized Heaviside is given explicitly by the piecewise-linear function H_ε(t) = 0 for t ≤ -ε, (t + ε)/(2ε) for -ε < t < ε, and 1 for t ≥ ε. The parameter schedule is ε_{k+1} = ε_k / 2 with ε_0 = 1, ensuring monotonic decrease to zero. This choice guarantees that each approximated problem has a lower-semicontinuous objective and a closed feasible set; the proof that limit points are local minimizers of the original A-HSCOP appears in Theorem 4.1. We will revise the abstract to mention the regularization explicitly and add a short remark in Section 3 summarizing the closedness and limit properties. revision: yes
-
Referee: [Convergence result] Convergence theorem (presumably §4): the proof that the progressive IP iterates converge to local optimizers of the original A-HSCOP must explicitly address how the successive decomposition interacts with the nondifferentiability of the inner functions; without a clear statement of the stationarity concept used for the nondifferentiable case and how the IP subproblems enforce it, the convergence result cannot be assessed for completeness.
Authors: Section 4 employs Clarke stationarity to accommodate the nondifferentiable inner functions. The successive decomposition fixes the discrete Heaviside indicators stage by stage; each resulting continuous subproblem is solved to Clarke-stationary points via a nonsmooth solver that evaluates the Clarke subdifferential. The main convergence theorem then shows that any accumulation point of the PIP sequence satisfies the Clarke stationarity condition for the original problem. To make this interaction fully transparent, we will insert a dedicated paragraph immediately before Theorem 4.2 that states the stationarity concept and explains how the decomposition and subproblem solves enforce it. revision: yes
Circularity Check
No significant circularity; derivation is self-contained
full rationale
The paper's core contribution is an approximation step to restore semicontinuity and closedness properties of the A-HSCOP, followed by a progressive integer programming method with successive decomposition to address the discrete nature of the Heaviside functions. Convergence to local optimizers is claimed to be established via this construction, and effectiveness is demonstrated through computational experiments on classification problems. No step reduces by construction to a fitted parameter, self-citation load-bearing premise, or renamed known result; the approximation and PIP approach are presented as new resolutions to the stated nondifferentiability and discontinuity challenges, independent of the target convergence claim itself. The derivation chain relies on standard IP techniques augmented by the proposed regularization, without internal reduction to inputs.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Journal of Convex Analysis 30(3), 793–834 (2023)
Cui, Y., Liu, J., Pang, J.S.: The minimization of piecewise functions: Ps eudo stationarity. Journal of Convex Analysis 30(3), 793–834 (2023)
work page 2023
-
[2]
Han, S., Cui, Y., Pang, J.S.: Analysis of a class of minimization problems lacking lower semicontinuity. Mathematics of Operations Research 50(3), 2175–2198 (2025) 52 /uni00000026/uni00000010/uni00000033/uni0000002c/uni00000033 /uni00000029/uni0000004f/uni00000052/uni0000005a/uni00000032/uni00000026/uni00000037 /uni00000026/uni00000010/uni00000025/uni0000...
work page 2025
-
[3]
arXiv preprint arXiv:2601.1211 7 (2026)
Liu, J., Qin, H., Liu, J., Chou, M.C., Pang, J.-S.: Offline policy learning with weight clipping and heaviside composite optimization. arXiv preprint arXiv:2601.1211 7 (2026)
-
[4]
Annals of Statistics 43(3), 1111–1141 (2013)
Bien, J., Taylor, J., Tibshirani, R.: A lasso for hierarchical interact ions. Annals of Statistics 43(3), 1111–1141 (2013)
work page 2013
-
[5]
Machine Lea rning 106, 1039–1082 (2017)
Bertsimas, D., Dunn, J.: Optimal classification trees. Machine Lea rning 106, 1039–1082 (2017)
work page 2017
-
[6]
Cui, Y., Pang, J.S.: Modern Nonconvex Nondifferentiable Optimizatio n. SIAM Publications, 53 /uni00000026/uni00000010/uni00000033/uni0000002c/uni00000033 /uni00000029/uni0000004f/uni00000052/uni0000005a/uni00000032/uni00000026/uni00000037 /uni00000026/uni00000010/uni00000025/uni0000004c/uni00000051/uni00000032/uni00000026/uni00000037 /uni00000038/uni000000...
work page 2021
-
[7]
Pang, J.S., Yulin, Y.: Quasi-difference-convexity: Modernization o f quasi-differentiable optimiza- tion. arXiv:2507.12413 (2025)
-
[8]
Journal of Set-Valued and Convex Analysis 30, 1149–1211 (2022)
Cui, Y., Liu, J., Pang, J.S.: Nonconvex and nonsmooth approaches for affine chance constrained programs. Journal of Set-Valued and Convex Analysis 30, 1149–1211 (2022)
work page 2022
-
[9]
SIAM Journal on Control and Optimization 33(1), 149–167 (1995)
Ermoliev, Y.M., Norkin, V.I., Wets, R.J.B.: The minimization of semicontin uous functions: Mollifier subgradients. SIAM Journal on Control and Optimization 33(1), 149–167 (1995)
work page 1995
-
[10]
SIAM Journal on Optimization 29(3), 2337– 2362 (2019)
Qi, Z., Cui, Y., Liu, Y., Pang, J.S.: Estimation of individualized decision r ules based on optimized covariate-dependent equivalent of random outcomes. SIAM Journal on Optimization 29(3), 2337– 2362 (2019)
work page 2019
-
[11]
Mathematical Program- ming, Series B 134, 71–99 (2012)
Chen, X.: Smoothing methods for nonsmooth, nonconvex minimiz ation. Mathematical Program- ming, Series B 134, 71–99 (2012)
work page 2012
-
[12]
PhD thesis, University of Southern California (2023)
Fang, Y.: Essays on treatment effect and policy learning under d ifferent settings. PhD thesis, University of Southern California (2023)
work page 2023
-
[13]
Mathematics of Operations Research 42, 95–118 (2017)
Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing B-stationar y points of nonsmooth DC programs. Mathematics of Operations Research 42, 95–118 (2017)
work page 2017
-
[14]
SIAM Journal o n Optimization 19(1), 445– 471 (2008)
Hu, J., Mitchell, J.E., Pang, J.S., Bennett, K.P., Kunapuli, G.: On the g lobal solution of linear 54 programs with linear complementarity constraints. SIAM Journal o n Optimization 19(1), 445– 471 (2008)
work page 2008
-
[15]
Operations Research 63(3), 610–627 (2015)
Bertsimas, D., Georghiou, A.: Design of near optimal decision rule s in multistage adaptive mixed- integer optimization. Operations Research 63(3), 610–627 (2015)
work page 2015
-
[16]
Operations Rese arch 58(2), 303–315 (2010)
Vielma, J.P., Ahmed, S., Nemhauser, G.: Mixed-integer models for n onseparable piecewise-linear optimization: unifying framework and extensions. Operations Rese arch 58(2), 303–315 (2010)
work page 2010
-
[17]
Mathematical Programming, Series B 169(1), 5–68 (2018)
Le Thi, H.A., Pham Dinh, T.: DC programming and DCA: Thirty years o f developments. Mathematical Programming, Series B 169(1), 5–68 (2018)
work page 2018
-
[18]
Acta Mathematica Vietnamica 22(1), 289–355 (1997)
Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to DC progra mming: Theory, algorithm and applications. Acta Mathematica Vietnamica 22(1), 289–355 (1997)
work page 1997
-
[19]
arXiv preprint 2601.02084 (2026)
Feng, Z., Yuan, Y.: A perturbed dca for computing d-stationar y points of nonsmooth dc programs. arXiv preprint 2601.02084 (2026)
-
[20]
In: Proceedings of the AAAI Conference on Artificial Intellig ence, vol
Verwer, S., Zhang, Y.: Learning optimal classification trees usin g a binary linear program formu- lation. In: Proceedings of the AAAI Conference on Artificial Intellig ence, vol. 33, pp. 1625–1632 (2019)
work page 2019
-
[21]
Metrics for multi-class classifi- cation: an overview,
Grandini, M., Bagli, E., Visani, G.: Metrics for multi-class classificatio n: An overview. arxiv 2020. arXiv:2008.05756 (2008)
-
[22]
manuscript, Beijing and Los Angeles (in progress)
Liu, J., Pang, J.S.: Heaviside Composite Optimization: Theory, Algo rithms, and Applications. manuscript, Beijing and Los Angeles (in progress)
-
[23]
Wadsworth and Brooks, Monterey, CA (1984)
Breiman, L., Friedman, J., Olshen, R., Stone, C.: Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA (1984)
work page 1984
-
[24]
Operations Research 3(4), 2223–2241 (2025-07) 55
Aghaei, S., G´ omez, A., Vayanos, P.: Strong optimal classificatio n trees. Operations Research 3(4), 2223–2241 (2025-07) 55
work page 2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.