Abstract

There are many significant applied contexts that require the solution of discontinuous optimization problems in finite dimensions. Yet these problems are very difficult, both computationally and analytically. With the functions being discontinuous and a minimizer (local or global) of the problems, even if it exists, being impossible to verifiably compute, a foremost question is what kind of "stationary solutions" one can expect to obtain; these solutions provide promising candidates for minimizers; i.e., their defining conditions are necessary for optimality. Motivated by recent results on sparse optimization, we introduce in this paper such a kind of solution, termed "pseudo B- (for Bouligand) stationary solution", for a broad class of discontinuous optimization problems with objective and constraint defined by indicator functions of the positive real axis composite with functions that are possibly nonsmooth. We present two approaches for computing such a solution. One approach is based on lifting the problem to a higher dimension via the epigraphical formulation of the indicator functions; this requires the addition of some auxiliary variables. The other approach is based on certain continuous (albeit not necessarily differentiable) piecewise approximations of the indicator functions and the convergence to a pseudo B-stationary solution of the original problem is established. The conditions for convergence are discussed and illustrated by an example.

Author information

Contact details are reproduced from the original publication and may be historical.

Ying Cui

Dept. of Industrial and Systems Engineering, University of Minnesota, Minneapolis, U.S.A.

yingcui@umn.edu

Jong-Shi Pang

The D.-J.-Epstein Dept. of Industrial and Systems Engineering, University of Southern California, Los Angeles, U.S.A.

jongship@usc.edu

Keywords

  • Piecewise functions
  • stationarity
  • epigraphical formulation
  • nonifier approximation

Mathematics Subject Classification

90C26, 90C59

References

  1. W. Achtziger, C. Kanzow: Mathematical programs with vanishing constraints: Optimality conditions and constraint qualifications, Math. Programming 114/1 (2008) 69–99.https://doi.org/10.1007/s10107-006-0083-3Google Scholar
  2. M. Ahn, J. S. Pang, J. Xin: Difference-of-convex learning: Directional stationarity, optimality, and sparsity, SIAM J. Optimization 27/3 (2017) 1637–1665.https://doi.org/10.1137/16M1084754Google Scholar
  3. V. D. Batukhtin: On solving discontinuous extremal problems, J. Optimization Theory Appl. 77/3 (1993) 575–589.https://doi.org/10.1007/BF00940451Google Scholar
  4. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  5. W. Bian, X. Chen: A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty, SIAM J. Numer. Analysis58 (2020) 858–883.https://doi.org/10.1137/18M1186009Google Scholar
  6. P. Bonami, A. Lodi, A. Tramontani, S. Wiese: On mathematical programming with indicator constraints, Math. Programming, Ser. B 151 (2015) 191–223.https://doi.org/10.1007/s10107-015-0891-4Google Scholar
  7. X. Chen: Smoothing methods for nonsmooth, nonconvex minimization, Math. Programming, Ser. B 134 (2012) 71–99.https://doi.org/10.1007/s10107-012-0569-0Google Scholar
  8. F. H. Clarke: Optimization and Nonsmooth Analysis, Classics in Applied Mathematics 5, SIAM, Philadelphia (1990).https://doi.org/10.1137/1.9781611971309Google Scholar
  9. P. L. Combettes: Perspective functions: Properties, constructions, and examples, Set-Valued Var. Analysis 26 (2018) 247–264.https://doi.org/10.1007/s11228-017-0407-xGoogle Scholar
  10. Y. Cui: Individualized decision making under partial identification: Three perspectives, two optimality results, and one paradox, Harvard Data Sci. Review 3.3 (2021).https://doi.org/10.1162/99608f92.d07b8d16Google Scholar
  11. Y. Cui, J. Liu, J. S. Pang: Nonconvex and nonsmooth approaches for affine chance constrained stochastic programs, J. Set-Valued Var. Analysis 30 (2022) 1149–1211.https://doi.org/10.1007/s11228-022-00639-yGoogle Scholar
  12. Y. Cui, J. S. Pang: Modern Nonconvex and Nondifferentiable Optimization, SIAM Publications, Philadelphia (2021).https://doi.org/10.1137/1.9781611976748Google Scholar
  13. H. Dong, K. Chen, J. Linderoth: Regularization vs. relaxation: A conic optimization perspective of statistical variable selection, arXiv: 1510.06083 (2015).Google Scholar
  14. J. P. Dussault, M. Haddoub, T. Migot: Mathematical programs with vanishing constraints: Constraint qualifications, their applications, and a new regularization method, Optimization 68/2-3 (2019) 509–538.https://doi.org/10.1080/02331934.2018.1542531Google Scholar
  15. I. Ekeland: On the variational principle, J. Math. Analysis Appl. 47 (1974) 324–354.https://doi.org/10.1016/0022-247X(74)90025-0Google Scholar
  16. Y. Ermoliev, V. Norkin: On constrained discontinuous optimization, in: Stochastic Programming Methods and Technical Applications, Springer, Berlin (1998), 128–144.https://doi.org/10.1007/978-3-642-45767-8_7Google Scholar
  17. Y. Ermoliev, V. Norkin: Stochastic optimization of risk functions via parametric smoothing, in: Dynamic Stochastic Optimization, Springer, Berlin (2004) 225–247.https://doi.org/10.1007/978-3-642-55884-9_11Google Scholar
  18. Y. M. Ermoliev, V. I. Norkin, R. J.-B. Wets: The minimization of semicontinuous functions: Mollifier subgradients, SIAM J. Control Optimization 3 (1995) 149–167.https://doi.org/10.1137/S0363012992238369Google Scholar
  19. F. Facchinei, J. S. Pang: Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Ser. Oper. Research, Springer, New York (2003).https://doi.org/10.1007/b97543Google Scholar
  20. J. Fan, R. Li: Variable selection via nonconcave penalized likelihood and its oracle properties, J. Amer. Statist. Assoc. 96/456 (2001) 1348–1360.https://doi.org/10.1198/016214501753382273Google Scholar
  21. J. Fan, L. Xue, H. Zou: Strong oracle optimality of folded concave penalized estimation, Ann. Statistics 42/3 (2014) 819–849.https://doi.org/10.1214/13-AOS1198Google Scholar
  22. M. Feng, J. E. Mitchell, X. Shen, A. Wächter: Complementarity formulations of ℓ0 - norm optimization problems, Pacific J. Optimization 14/2 (2018) 273–305.Google Scholar
  23. M. C. Ferris: Weak Sharp Minima and Exact Penalty Functions, Ph. D. Thesis, Department of Computer Sciences, University of Wisconsin, Madison (1988).Google Scholar
  24. M. Fukushima, J. S. Pang: Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints, Comp. Optimization Appl. 13 (1998) 111–136.https://doi.org/10.1023/A:1008656806889Google Scholar
  25. A. Gomez, Z. He, J. S. Pang: Linear-step solvability of some folded concave and singlyparametric sparse optimization problems, Math. Program. B 198/2 (2023) 1339–1380.https://doi.org/10.1007/s10107-021-01766-4Google Scholar
  26. O. Günlük, J. Linderoth: Perspective reformulations of mixed integer nonlinear programs with indicator variables, Math. Programming, Ser. B 124 (2010) 183–205.https://doi.org/10.1007/s10107-010-0360-zGoogle Scholar
  27. A. M. Gupal, V. I. Norkin: Algorithm for the minimization of discontinuous functions, Cybernetics 13 (1977) 220–223.https://doi.org/10.1007/BF01073313Google Scholar
  28. T. Hastie, R. Tibshirani, M. Wainwright: Statistical Learning with Sparsity: The Lasso and Generalizations, Monographs on Statistics and Applied Probability 143, CRC Press, Boca Raton (2015).https://doi.org/10.1201/b18401Google Scholar
  29. O. Heaviside: Electromagnetic waves, the propagation of potential, and the electromagnetic effects of a moving charge, The Electrician (1888).Google Scholar
  30. H. Hijazi, P. Bonami, G. Cornéjols, A. Ouorou: Mixed-integer nonlinear programs featuring “on/off” constraints, Comp. Optimization Appl. 52 (2012) 537–558.https://doi.org/10.1007/s10589-011-9424-0Google Scholar
  31. J. B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms, Springer, New York (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  32. T. Hoheisel, C. Kanzow, A. Schwartz: Mathematical programs with vanishing constraints: A new regularization approach with strong convergence properties, Optimization 61/6 (2012) 619–636.https://doi.org/10.1080/02331934.2011.608164Google Scholar
  33. A. F. Izmailov, M. V. Solodov: Mathematical programs with vanishing constraints: Optimality conditions, sensitivity, and a relaxation method, J. Optimization Theory Appl. 142/3 (2009) 501–532.https://doi.org/10.1007/s10957-009-9517-4Google Scholar
  34. H. Th. Jongen, O. Stein: Smoothing by mollifiers. I: Semi-infinite optimization, J. Global Optimization 41 (2008) 319–334.https://doi.org/10.1007/s10898-007-9232-3Google Scholar
  35. H. Th. Jongen, O. Stein: Smoothing by mollifiers. II: Nonlinear optimization, J. Global Optimization 41 (2008) 335–350.https://doi.org/10.1007/s10898-007-9231-4Google Scholar
  36. A. I. Kibzun, A. V. Naumov, V. I. Norkin: On reducing a quantile optimization problem with discrete distribution to a mixed integer programming problem, Automation Remote Control 74/6 (2013) 951–967.https://doi.org/10.1134/S0005117913060064Google Scholar
  37. H. A. Le Thi, D. T. Pham: The DC programming and DCA revised with DC models of real world nonconvex optimization problems, Ann. Oper. Research 133 (2015) 25–46.Google Scholar
  38. H. A. Le Thi, T. Pham Dinh, X. T. Vo: DC approximation approaches for sparse optimization, Eur. J. Oper. Research 244/1 (2015) 26–46.https://doi.org/10.1016/j.ejor.2014.11.031Google Scholar
  39. G. Libri: Note sur les valeurs de la fonction x 00, J. Reine Angew. Math. 6 (1830) 67–72.https://doi.org/10.1515/crll.1830.6.67Google Scholar
  40. G. Libri: Mémoire sur les fonctions discontinues, J. Reine Angew. Math. 10 (1833) 303–316.https://doi.org/10.1515/crll.1833.10.303Google Scholar
  41. Z. Long, P. Yin, J. Xin: Learning quantized neural nets by coarse gradient method for nonlinear classification, Res. Math. Sciences 8/48 (2021), 19 pages.https://doi.org/10.1007/s40687-021-00281-4Google Scholar
  42. Z. Lu, Z. Zhou, Z. Sun: Enhanced proximal DC algorithms with extrapolation for a class of structured nonsmooth DC minimization, Math. Program. 176/12 (2019) 369–401.https://doi.org/10.1007/s10107-018-1318-9Google Scholar
  43. B. Pagnoncelli, S. Ahmed, A. Shapiro: Sample average approximation method for chance-constrained programming: Theory and applications, J. Optimization Theory Appl. 142 (2009) 399–416.https://doi.org/10.1007/s10957-009-9523-6Google Scholar
  44. J. S. Pang, M. Razaviyayn, A. Alvarado: Computing B-stationary points of nonsmooth DC programs, Math. Oper. Res. 42/1 (2017) 95–118.https://doi.org/10.1287/moor.2016.0795Google Scholar
  45. T. Pham Dinh, H. A. Le Thi: Convex analysis approach to DC programming: Theory, algorithm and applications, Acta Math. Vietnamica 22/1 (1997) 289–355.Google Scholar
  46. G. D. Pillo, F. Facchinei: Exact penalty functions for nondifferentiable programming problems, in: Nonsmooth Optimization and Related Topics, Springer, Boston (1989) 89–107.https://doi.org/10.1007/978-1-4757-6019-4_7Google Scholar
  47. Z. Qi, Y. Cui, Y. Liu, J. S. Pang: Estimation of individualized decision rules based on an optimized covariate-dependent equivalent of random outcomes, SIAM J. Optimization 29/3 (2019) 2337–2362.https://doi.org/10.1137/18M1190975Google Scholar
  48. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  49. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, 3rd printing, Grundlehren der mathematischen Wissenschaften 317, Springer, Berlin (2009).Google Scholar
  50. J. Royset: Consistent approximations in composite optimization, Math. Programming A 201/1-2 (2023) 339–372.https://doi.org/10.1007/s10107-022-01909-1Google Scholar
  51. H. D. Sherali, L. D. Brizendine, T. S. Glickman, S. Subramanian: Low probability high consequence considerations in routing hazardous material shipments, Transportation Science 31/3 (1997) 237–251.https://doi.org/10.1287/trsc.31.3.237Google Scholar
  52. W. Takahashi: Existence theorems generalizing fixed point theorems for multivalued mappings, in: Fixed Point Theory and Applications, M. A. Théra and J. B. Baillon (eds.), Pitman Research Notes in Mathematics 252, Longman Scientific & Technical, Harlow (1991) 397–406.Google Scholar
  53. Y. Wu, Y. Liu: Robust truncated hinge loss support vector machines, J. Amer. Statist. Assoc. 102 (2007) 974–983.https://doi.org/10.1198/016214507000000617Google Scholar
  54. J. Xin: Training quantized deep neural networks and applications with blended coarse gradient descent, SIAM News 52/4 (2019).Google Scholar
  55. P. Yin, S. Zhang, Y. Qi, J. Xin: Quantization and training of low bit-width convolutionary neural networks for object detection J. Comput. Math. 37/3 (2019) 349–359.https://doi.org/10.4208/jcm.1803-m2017-0301Google Scholar
  56. G. Yu, H. Fu, Y. Liu: High-dimensional cost-constrained regression via non-convex optimization, Technometrics 64/1 (2022) 52–64.https://doi.org/10.1080/00401706.2021.1905071Google Scholar
  57. L. H. Yue: Cost-efficient variable selection using branching lars, Electronic Thesis and Dissertation Repository 43 (2010), https://ir.lib.uwo.ca/etd/43/.Google Scholar
  58. C. Zhang: Nearly unbiased variable selection under minimax concave penalty, Ann. Statistics 38/2 (2010) 894–942.https://doi.org/10.1214/09-AOS729Google Scholar
  59. V. W. Zheng, K. C. C. Chang: Regularizing structured classifier with conditional probabilistic constraints for semi-supervised learning, in: CIKM 2016, Proc. 2016 ACM Conf. Information and Knowledge Management (2016) 1029–1038.https://doi.org/10.1145/2983323.2983860Google Scholar

Suggested citation

Y. Cui, J. Liu, J.-S. Pang. “The Minimization of Piecewise Functions: Pseudo Stationarity.” Journal of Convex Analysis 30 (2023), No. 3, 793–834. https://doi.org/10.68381/jca30038

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press LLC.