pith. sign in

arxiv: 2605.06020 · v1 · submitted 2026-05-07 · 🧮 math.OC

Solving Constrained Affine Heaviside Composite Optimization Problems by a Progressive IP Approach

Ke Zheng , Junyi Liu , Yurui Wang , Jong-Shi Pang This is my paper

Pith reviewed 2026-05-08 08:24 UTC · model grok-4.3

classification 🧮 math.OC
keywords Heaviside composite optimizationaffine combinationsprogressive integer programmingsuccessive decompositionmulticlass classificationprecision constraintsdiscontinuous optimization
0
0 comments X

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.

The paper addresses optimization problems where the objective and constraints involve affine combinations of Heaviside functions, which are discontinuous and produce an objective without semicontinuity plus a feasible set that may not be closed. It remedies these issues with a preliminary approximation step and then applies a progressive integer programming method that decomposes the problem successively to manage the discrete character of the Heaviside step. Convergence of the resulting sequence to local optimizers of the original problem is proved. The approach is tested on score-based and tree-based multiclass classification tasks that include precision constraints, where numerical results confirm practical performance.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. [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

2 responses · 0 unresolved

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

  1. 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

  2. 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

0 steps flagged

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

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on the effectiveness of an unspecified approximation to restore semicontinuity and closedness, plus the validity of the convergence proof for the progressive IP decomposition. No explicit free parameters, axioms, or invented entities are identifiable from the abstract alone.

pith-pipeline@v0.9.0 · 5498 in / 1182 out tokens · 49654 ms · 2026-05-08T08:24:09.150594+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [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. [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. [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)

    work page arXiv 2026

  4. [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. [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. [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. [7]

    arXiv:2507.12413 (2025)

    Pang, J.S., Yulin, Y.: Quasi-difference-convexity: Modernization o f quasi-differentiable optimiza- tion. arXiv:2507.12413 (2025)

    work page arXiv 2025

  8. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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)

    work page arXiv 2026

  20. [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. [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)

    work page arXiv 2020

  22. [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)

    work page

  23. [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. [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