pith. sign in

arxiv: 2210.11889 · v5 · submitted 2022-10-21 · 🧮 math.OC

0/1 Constrained Optimization Solving Sample Average Approximation for Chance Constrained Programming

Shenglong Zhou , Lili Pan , Naihua Xiu , Geoffrey Ye Li This is my paper

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

classification 🧮 math.OC
keywords chance constrained programmingsample average approximation0/1 constraintsemismooth Newton methodoptimality conditionsstochastic optimizationconvergence analysisnonsmooth equations
0
0 comments X

The pith

A semismooth Newton algorithm solves the 0/1 constrained form of sample average approximation for chance constrained programs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a direct method for sample average approximation in chance constrained programming by treating the problem as general 0/1 constrained optimization rather than reformulating it into integer programs or relaxations. It begins by deriving the Bouligand tangent cone and Fréchet normal cone of the 0/1 constraint set, then uses these to obtain optimality conditions that reduce to an equivalent system of equations. This system supports a semismooth Newton-type algorithm that converges locally at a superlinear or quadratic rate under standard assumptions. The approach also shows competitive numerical results against leading solvers on test problems. A reader would care because it supplies both theory and a practical solver for a class of stochastic problems that usually forces indirect or combinatorial methods.

Core claim

Optimality conditions for 0/1 constrained optimization can be derived from the Bouligand tangent and Fréchet normal cones of the 0/1 set and expressed as a system of equations; this system is solved by a semismooth Newton-type algorithm that attains locally superlinear or quadratic convergence and performs well numerically on sample average approximations of chance constrained programs.

What carries the argument

The Bouligand tangent cone and Fréchet normal cone of the 0/1 constraint, which produce optimality conditions equivalent to a nonsmooth equation system that the semismooth Newton algorithm solves.

If this is right

  • The method applies directly to SAA formulations without requiring binary integer programming or continuous relaxations.
  • Local convergence guarantees hold for the Newton iterates once a sufficiently accurate starting point is reached.
  • The same cone-based optimality conditions extend to other 0/1 constrained problems beyond chance constraints.
  • Numerical performance remains stable across multiple leading solvers on benchmark instances.

Where Pith is reading between the lines

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

  • The cone derivations could be reused to design solvers for other discrete nonconvex constraints that admit similar tangent-normal descriptions.
  • Warm-starting strategies or globalization techniques would likely be needed to reach the basin of superlinear convergence from arbitrary initial points.
  • The equation-system reduction may allow hybrid methods that combine the Newton step with outer approximation or cutting-plane schemes for global search.

Load-bearing premise

The Bouligand tangent and Fréchet normal cones of the 0/1 constraint can be derived explicitly and used to obtain optimality conditions that are equivalent to a solvable system of equations.

What would settle it

Apply the algorithm to a standard SAA chance-constrained test set and check whether observed local convergence rates are superlinear or quadratic and whether solution quality and speed remain competitive with binary reformulation solvers.

Figures

Figures reproduced from arXiv: 2210.11889 by Geoffrey Ye Li, Lili Pan, Naihua Xiu, Shenglong Zhou.

Figure 1
Figure 1. Figure 1: Effect of the starting points. 6.3. Benchmarks We will compare SNSCO with an NLP algorithm developed in [48], two algorithms proposed in [1]: regularized algorithm with a convex start (RegAC) and relaxed algorithm (RelA), and GUROBI. All algorithms use the same initial point, x 0 = 1. Other relevant parameters and implementations are described as follows: • For GUROBI, we employ it to solve problem (BIP). … view at source ↗
read the original abstract

Sample average approximation (SAA) is a tractable approach for dealing with chance constrained programming, a challenging stochastic optimization problem. The constraint of SAA is characterized by the $0/1$ loss function which results in considerable complexities in devising numerical algorithms. Most existing methods have been devised based on reformulations of SAA, such as binary integer programming or relaxed problems. However, the development of viable methods to directly tackle SAA remains elusive, let alone providing theoretical guarantees. In this paper, we investigate a general $0/1$ constrained optimization, providing a new way to address SAA rather than its reformulations. Specifically, starting with deriving the Bouligand tangent and Fr$\acute{e}$chet normal cones of the $0/1$ constraint, we establish several optimality conditions. One of them can be equivalently expressed by a system of equations, enabling the development of a semismooth Newton-type algorithm. The algorithm demonstrates a locally superlinear or quadratic convergence rate under standard assumptions, along with nice numerical performance compared to several leading solvers.

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 / 0 minor

Summary. The paper considers the sample-average approximation of chance-constrained programs, which yields a 0/1-constrained optimization problem. It derives the Bouligand tangent cone and Fréchet normal cone to the discrete set {0,1}^n, uses these to obtain first-order optimality conditions, shows that one such condition is equivalent to a nonsmooth equation system, and develops a semismooth Newton-type method whose local superlinear or quadratic convergence is proved under standard assumptions. Numerical comparisons with several solvers are reported.

Significance. A correct derivation of nontrivial stationarity conditions for the 0/1 set together with a convergent direct solver would constitute a genuine advance for SAA-based chance-constrained optimization, which currently relies on integer-programming reformulations or continuous relaxations. The claimed equivalence to a solvable equation system and the convergence theory would be the central contributions.

major comments (2)
  1. [cone derivations and optimality conditions] The section deriving the Bouligand tangent and Fréchet normal cones (abstract and the paragraph immediately following): the claim that these cones yield nontrivial optimality conditions is inconsistent with the geometry of the discrete set S = {0,1}^n. At any x ∈ S the Bouligand tangent cone is {0} and the Fréchet normal cone is all of R^n, so the stationarity condition −∇f(x) ∈ N^F_S(x) holds identically for every differentiable f. Consequently no such condition can be equivalent to a nontrivial system of equations to which a semismooth Newton method can be applied.
  2. [optimality conditions and algorithm development] The paragraph establishing equivalence to a system of equations (abstract): because the normal-cone stationarity condition is vacuous, the subsequent reduction to an equation system and the local convergence analysis built upon it rest on an incorrect foundation and cannot be salvaged without a fundamentally different treatment of the 0/1 constraint.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for identifying the critical issue with the cone derivations. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [cone derivations and optimality conditions] The section deriving the Bouligand tangent and Fréchet normal cones (abstract and the paragraph immediately following): the claim that these cones yield nontrivial optimality conditions is inconsistent with the geometry of the discrete set S = {0,1}^n. At any x ∈ S the Bouligand tangent cone is {0} and the Fréchet normal cone is all of R^n, so the stationarity condition −∇f(x) ∈ N^F_S(x) holds identically for every differentiable f. Consequently no such condition can be equivalent to a nontrivial system of equations to which a semismooth Newton method can be applied.

    Authors: We agree with this assessment. For the discrete set S = {0,1}^n, the Bouligand tangent cone at each x ∈ S is {0} and the Fréchet normal cone is R^n, making the normal-cone stationarity condition hold identically and thus vacuous. Our claimed derivation of nontrivial cones was erroneous. We will revise the manuscript to remove the incorrect cone derivations, the associated optimality conditions, and any claims that they yield a nontrivial equation system. revision: yes

  2. Referee: [optimality conditions and algorithm development] The paragraph establishing equivalence to a system of equations (abstract): because the normal-cone stationarity condition is vacuous, the subsequent reduction to an equation system and the local convergence analysis built upon it rest on an incorrect foundation and cannot be salvaged without a fundamentally different treatment of the 0/1 constraint.

    Authors: We concur that the reduction to a nonsmooth equation system, the semismooth Newton algorithm, and its local convergence analysis rest on the invalid stationarity condition and cannot be maintained. These elements require a fundamentally different treatment of the 0/1 constraint. In revision we will remove the algorithm development, convergence theory, and numerical comparisons tied to this foundation. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses standard variational analysis on discrete constraint without self-referential reduction

full rationale

The paper starts from the geometric definition of the 0/1 set and applies standard Bouligand/Fréchet cone constructions from variational analysis to obtain optimality conditions, one of which is rewritten as an equation system for a semismooth Newton solver. No step equates a derived quantity to its own input by construction, renames a fitted parameter as a prediction, or relies on a load-bearing self-citation whose content is itself unverified. The convergence claim rests on standard nonsmooth Newton theory under explicit assumptions that do not presuppose the target result. This is the normal case of a self-contained derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review prevents exhaustive audit; the work relies on standard results from variational analysis for the 0/1 set.

axioms (1)
  • domain assumption Existence and explicit form of Bouligand tangent and Fréchet normal cones for the 0/1 constraint set
    Invoked to derive optimality conditions in the abstract.

pith-pipeline@v0.9.0 · 5716 in / 1136 out tokens · 25222 ms · 2026-05-24T10:44:34.589349+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

68 extracted references · 68 canonical work pages

  1. [1]

    Adam L, Branda M (2016) Nonlinear chance constrained problems : optimality conditions, regularization and solvers. J. Optim. Theory. Appl. 170(2):419–436

    work page 2016

  2. [2]

    State-of-the-art decision-making tools in the informatio n-intensive age , 261–269 (Informs)

    Ahmed S, Shapiro A (2008) Solving chance-constrained stochas tic programs via sampling and inte- ger programming. State-of-the-art decision-making tools in the informatio n-intensive age , 261–269 (Informs)

    work page 2008

  3. [3]

    Nonlinear Anal

    Ban L, Mordukhovich BS, Song W (2011) Lipschitzian stability of pa rametric variational inequalities over generalized polyhedra in banach spaces. Nonlinear Anal. Theory Methods Appl. 74(2):441–461

    work page 2011

  4. [4]

    Beraldi P, Bruni ME (2010) An exact approach for solving intege r problems under probabilistic con- straints with random technology matrix. Ann. Oper. Res. 177(1):127–137

    work page 2010

  5. [5]

    Berthold H, Heitsch H, Henrion R, Schwientek J (2022) On the algo rithmic solution of optimization problems subject to probabilistic/robust (probust) constraints . Math. Methods Oper. Res. 96(1):1–37

    work page 2022

  6. [6]

    2008 42nd Annual Conference on Infor- mation Sciences and Systems , 16–21 (IEEE)

    Boufounos PT, Baraniuk RG (2008) 1-bit compressive sensing. 2008 42nd Annual Conference on Infor- mation Sciences and Systems , 16–21 (IEEE)

    work page 2008

  7. [7]

    Calafiore G, Campi MC (2005) Uncertain convex programs: rand omized solutions and confidence levels. Math. Program. 102:25–46

    work page 2005

  8. [8]

    Charnes A, Cooper WW, Symonds GH (1958) Cost horizons and ce rtainty equivalents: an approach to stochastic programming of heating oil. Manage. Sci. 4(3):235–263

    work page 1958

  9. [9]

    Chen X, Qi L, Sun D (1998) Global and superlinear convergence o f the smoothing newton method and its application to general box constrained variational inequalities. Math. Comput. 67(222):519–540. 32 S. Zhou, L. Pan, N. Xiu, G. Li: 0/ 1 Constrained Optimization Solving SAA for CCP

    work page 1998

  10. [10]

    Clarke FH (1990) Optimization and nonsmooth analysis (SIAM)

    work page 1990

  11. [11]

    Cortes C, Vapnik V (1995) Support-vector networks. Mach. Learn. 20(3):273–297

    work page 1995

  12. [12]

    Curtis FE, W¨ achter A, Zavala VM (2018) A sequential algorithm for solving nonlinear optimization problems with chance constraints. SIAM J. Optim. 28(1):930–958

    work page 2018

  13. [13]

    De Farias DP, Van Roy B (2004) On constraint sampling in the linear programming approach to approx- imate dynamic programming. Math. Oper. Res. 29(3):462–478

    work page 2004

  14. [14]

    Dontchev AL, Rockafellar RT (2010) Newton’s method for gene ralized equations: a sequential implicit function theorem. Math. Program. 123(1):139–159

    work page 2010

  15. [15]

    Erdo˘ gan E, Iyengar G (2006) Ambiguous chance constrained problems and robust optimization. Math. Program. 107:37–61

    work page 2006

  16. [16]

    Evgeniou T, Pontil M, Poggio T (2000) Regularization networks a nd support vector machines. Adv. Comput. Math. 13(1):1

    work page 2000

  17. [17]

    Farshbaf-Shaker MH, Gugat M, Heitsch H, Henrion R (2020) Op timal neumann boundary control of a vibrating string with uncertain initial data and probabilistic terminal constraints. SIAM J. Control Optim. 58(4):2288–2311

    work page 2020

  18. [18]

    Data Min

    Friedman JH (1997) On bias, variance, 0/1 loss, and the curse- of-dimensionality. Data Min. Knowl. Discov. 1(1):55–77

    work page 1997

  19. [19]

    Geletu A, Hoffmann A, Kl¨ oppel M, Li P (2017) An inner-outer ap proximation approach to chance constrained optimization. SIAM J. Optim. 27(3):1834–1857

    work page 2017

  20. [20]

    Gonzalez Grandon T, Heitsch H, Henrion R (2017) A joint model o f probabilistic/robust constraints for gas transport management in stationary networks. Comput. Manag. Sci. 14:443–460

    work page 2017

  21. [21]

    Gotzes C, Heitsch H, Henrion R, Schultz R (2016) On the quantifi cation of nomination feasibility in stationary gas networks with random load. Math. Methods Oper. Res. 84:427–457

    work page 2016

  22. [22]

    Hale ET, Yin W, Zhang Y (2008) Fixed-point continuation for ℓ1-minimization: Methodology and convergence. SIAM J. Optim. 19(3):1107–1130

    work page 2008

  23. [23]

    Hantoute A, Henrion R, P´ erez-Aros P (2019) Subdifferential characterization of probability functions under Gaussian distribution. Math. Program. 174:167–194

    work page 2019

  24. [24]

    Hastie T, Tibshirani R, Friedman J (2009) The elements of statistical learning: data mining, inferen ce, and prediction (Springer Science & Business Media)

    work page 2009

  25. [25]

    Optimization

    Heitsch H (2019) On probabilistic capacity maximization in a station ary gas network. Optimization

    work page 2019

  26. [26]

    Henrion R (2007) Structural properties of linear probabilistic c onstraints. Optim. 56(4):425–440

    work page 2007

  27. [27]

    Henrion R, M¨ oller A (2003) Optimization of a continuous distillation process under random inflow rate. Comput. Math. with Appl. 45(1-3):247–262

    work page 2003

  28. [28]

    Henrion R, M¨ oller A (2012) A gradient formula for linear chance constraints under Gaussian distribution. Math. Oper. Res. 37(3):475–488

    work page 2012

  29. [29]

    Hong LJ, Yang Y, Zhang L (2011) Sequential convex approxima tions to joint chance constrained pro- grams: A monte carlo approach. Oper. Res. 59(3):617–630

    work page 2011

  30. [30]

    Hu I (1985) A uniform bound for the tail probability of kolmogoro v-smirnov statistics. Ann. Stat. 821– 826

    work page 1985

  31. [31]

    Huang J, Jiao Y, Lu X, Zhu L (2018) Robust decoding from 1-bit c ompressive sampling with ordinary and regularized least squares. SIAM J. Sci. Comput. 40(4):A2062–A2086

    work page 2018

  32. [32]

    Izmailov AF, Solodov MV (2014) Newton-type methods for optimization and variational prob lems, vol- ume 3 (Springer)

    work page 2014

  33. [33]

    Kataoka S (1963) A stochastic programming model. J. Econom. 181–196

    work page 1963

  34. [34]

    Kojima M, Shindo S (1986) Extension of newton and quasi-newto n methods to systems of pcˆ 1 equa- tions. J. Oper. Res. Soc. Jpn. 29(4):352–375

    work page 1986

  35. [35]

    Lagoa CM, Li X, Sznaier M (2005) Probabilistically constrained line ar programs and risk-adjusted controller design. SIAM J. Optim. 15(3):938–951. S. Zhou, L. Pan, N. Xiu, G. Li: 0/ 1 Constrained Optimization Solving SAA for CCP 33

    work page 2005

  36. [36]

    Lejeune MA, Ruszczy´ nski A (2007) An efficient trajectory m ethod for probabilistic production- inventory-distribution problems. Oper. Res. 55(2):378–394

    work page 2007

  37. [37]

    2007 Interna- tional Joint Conference on Neural Networks , 749–754 (IEEE)

    Li L, Lin HT (2007) Optimizing 0/1 loss for perceptrons by rando m coordinate descent. 2007 Interna- tional Joint Conference on Neural Networks , 749–754 (IEEE)

    work page 2007

  38. [38]

    Luedtke J (2014) A branch-and-cut decomposition algorithm f or solving chance-constrained mathemat- ical programs with finite support. Math. Program. 146(1):219–244

    work page 2014

  39. [39]

    Luedtke J, Ahmed S (2008) A sample approximation approach fo r optimization with probabilistic con- straints. SIAM J. Optim. 19(2):674–699

    work page 2008

  40. [40]

    Luedtke J, Ahmed S, Nemhauser GL (2010) An integer program ming approach for linear programs with probabilistic constraints. Math. Program. 122(2):247–272

    work page 2010

  41. [41]

    Ma S, Goldfarb D, Chen L (2011) Fixed point and bregman iterativ e methods for matrix rank mini- mization. Math. Program. 128(1):321–353

    work page 2011

  42. [42]

    Massart P (1990) The tight constant in the dvoretzky-kiefer -wolfowitz inequality. Ann. Probab. 1269– 1283

    work page 1990

  43. [43]

    Miller BL, Wagner HM (1965) Chance constrained programming wit h joint constraints. Oper. Res. 13(6):930–945

    work page 1965

  44. [44]

    Nemirovski A, Shapiro A (2007) Convex approximations of chan ce constrained programs. SIAM J. Optim. 17(4):969–996

    work page 2007

  45. [45]

    Numerical optimization 448–492

    Nocedal J, Wright SJ (2006) Quadratic programming. Numerical optimization 448–492

    work page 2006

  46. [46]

    International Conference on Pattern Recognition (submitted)

    Osuna E, Girosi F (1998) Reducing the run-time complexity of su pport vector machines. International Conference on Pattern Recognition (submitted)

    work page 1998

  47. [47]

    Pagnoncelli BK, Ahmed S, Shapiro A (2009) Sample average appr oximation method for chance con- strained programming: theory and applications. J. Optim. Theory. Appl. 142(2):399–416

    work page 2009

  48. [48]

    Pe˜ na-Ordieres A, Luedtke JR, W¨achter A (2020) Solving chance-constrained problems via a smooth sample-based nonlinear approximation. SIAM J. Optim. 30(3):2221–2250

    work page 2020

  49. [49]

    Pr´ ekopa A (1973) Contributions to the theory of stochastic programming. Math. Program. 4(1):202–221

    work page 1973

  50. [50]

    Pr´ ekopa A (2013) Stochastic programming, volume 324 (Springer Science & Business Media)

    work page 2013

  51. [51]

    Qi L, Sun J (1993) A nonsmooth version of newton’s method. Math. Program. 58(1-3):353–367

    work page 1993

  52. [52]

    Robinson SM (1980) Strongly regular generalized equations. Math. Oper. Res. 5(1):43–62

    work page 1980

  53. [53]

    Rockafellar RT, Wets RJB (2009) Variational analysis, volume 317 (Springer Science & Business Media)

    work page 2009

  54. [54]

    Shapiro A, Dentcheva D, Ruszczy´ nski A (2021)Lectures on stochastic programming: modeling and theory (SIAM)

    work page 2021

  55. [55]

    INFORMS J

    Song Y, Luedtke JR, K¨ u¸ c¨ ukyavuz S (2014) Chance-constrained binary packing problems. INFORMS J. Comput. 26(4):735–747

    work page 2014

  56. [56]

    Sun H, Xu H, Wang Y (2014) Asymptotic analysis of sample averag e approximation for stochastic optimization problems with joint chance constraints via conditional v alue at risk and difference of convex functions. J. Optim. Theory. Appl. 161(1):257–284

    work page 2014

  57. [57]

    http : //www.optimization − online.org/DB HT M L/ 2019/ 11/ 7465.html

    Sun H, Zhang D, Chen Y (2019) Convergence analysis and a dc ap proximation method for data-driven mathematical programs with distributionally robust chance constr aints. http : //www.optimization − online.org/DB HT M L/ 2019/ 11/ 7465.html

    work page 2019

  58. [58]

    Water Resour

    Takyi AK, Lence BJ (1999) Surface water quality management using a multiple-realization chance constraint method. Water Resour. Res. 35(5):1657–1670

    work page 1999

  59. [59]

    Set-Valued Var

    Van Ackooij W, Aleksovska I, Munoz-Zuniga M (2018) (Sub-)Diff erentiability of probability functions with elliptical distributions. Set-Valued Var. Anal. 26:887–910

    work page 2018

  60. [60]

    Van Ackooij W, Henrion R (2014) Gradient formulae for nonlinear probabilistic constraints with Gaus- sian and Gaussian-like distributions. SIAM J. Optim. 24(4):1864–1889

    work page 2014

  61. [61]

    SIAM-ASA J

    Van Ackooij W, Henrion R (2017) (Sub-)Gradient formulae for p robability functions of random inequal- ity systems under Gaussian distribution. SIAM-ASA J. Uncertain. Quantif. 5(1):63–87. 34 S. Zhou, L. Pan, N. Xiu, G. Li: 0/ 1 Constrained Optimization Solving SAA for CCP

    work page 2017

  62. [62]

    Van Ackooij W, Malick J (2017) Second-order differentiability of p robability functions. Optim. Lett. 11(1):179–194

    work page 2017

  63. [63]

    Van Ackooij W, P´ erez-Aros P (2019) Generalized differentiatio n of probability functions acting on an infinite system of constraints. SIAM J. Optim. 29(3):2179–2210

    work page 2019

  64. [64]

    Van Ackooij W, P´ erez-Aros P (2020) Gradient formulae for no nlinear probabilistic constraints with non-convex quadratic forms. J. Optim. Theory Appl. 185(1):239–269

    work page 2020

  65. [65]

    Van Ackooij W, P´ erez-Aros P (2022) Generalized differentiatio n of probability functions: parameter dependent sets given by intersections of convex sets and complem ents of convex sets. Appl. Math. Optim. 85(1):2

    work page 2022

  66. [66]

    IEEE Trans

    Wang H, Shao Y, Zhou S, Zhang C, Xiu N (2021) Support vector m achine classifier via l0/ 1 soft-margin loss. IEEE Trans. Pattern Anal. and Mach. Intell. 44(10):7253–7265

    work page 2021

  67. [67]

    IEEE Trans

    Zhou S, Luo Z, Xiu N, Li GY (2022) Computing one-bit compressiv e sensing via double-sparsity con- strained optimization. IEEE Trans. Signal Process 70:1593–1608

    work page 2022

  68. [68]

    Zhou S, Pan L, Xiu N, Qi HD (2021) Quadratic convergence of sm oothing newton’s method for 0/1 loss optimization. SIAM J. Optim. 31(4):3184–3211

    work page 2021