Geodesic
Dual active-set algorithm for optimal 3-monotone regression
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 2, pp. 216-223.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper considers a shape-constrained optimization problem of constructing monotone regression which has gained much attention over the recent years. This paper presents the results of constructing the nonlinear regression with 3-monotone constraints. Monotone regression of high orders can be applied in many fields, including non-parametric mathematical statistics and empirical data smoothing. In this paper, an iterative algorithm is proposed for constructing a sparse 3-monotone regression, i.e. for finding a 3-monotone vector with the lowest square error of approximation to a given (not necessarily 3-monotone) vector. The problem can be written as a convex programming problem with linear constraints. It is proved that the proposed dual active-set algorithm has polynomial complexity and obtains the optimal solution. 
@article{ISU_2022_22_2_a7,
     author = {A. A. Gudkov and S. P. Sidorov and K. A. Spiridonov},
     title = {Dual active-set algorithm for optimal 3-monotone regression},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {216--223},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ISU_2022_22_2_a7/}
}
TY  - JOUR
AU  - A. A. Gudkov
AU  - S. P. Sidorov
AU  - K. A. Spiridonov
TI  - Dual active-set algorithm for optimal 3-monotone regression
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2022
SP  - 216
EP  - 223
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ISU_2022_22_2_a7/
LA  - en
ID  - ISU_2022_22_2_a7
ER  - 
%0 Journal Article
%A A. A. Gudkov
%A S. P. Sidorov
%A K. A. Spiridonov
%T Dual active-set algorithm for optimal 3-monotone regression
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2022
%P 216-223
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2022_22_2_a7/
%G en
%F ISU_2022_22_2_a7
A. A. Gudkov; S. P. Sidorov; K. A. Spiridonov. Dual active-set algorithm for optimal 3-monotone regression. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 2, pp. 216-223. http://geodesic.mathdoc.fr/item/ISU_2022_22_2_a7/

[1] Chen Y., Aspects of Shape-constrained Estimation in Statistics, Ph. D. thesis, University of Cambridge, 2013, 143 pp.

[2] Burdakov O., Sysoev O., “A dual active-set algorithm for regularized monotonic regression”, Journal of Optimization Theory and Applications, 172:3 (2017), 929–949 | DOI

[3] Robertson T., Wright F., Dykstra R., Order Restricted Statistical Inference, John Wiley Sons, New York, 1988, 488 pp.

[4] Dykstra R., “An isotonic regression algorithm”, Journal of Statistical Planning and Inference, 5:4 (1981), 355–363 | DOI

[5] Bach F. R., “Efficient algorithms for non-convex isotonic regression through submodular optimization”, Advances in Neural Information Processing Systems 32$^{nd}$: Annual Conference on Neural Information Processing Systems, NeurIPS 2018 (December 3–8, 2018, Montréal, Canada), eds. S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett, 2018, 1–10

[6] Hastie T., Tibshirani R., Wainwright M., Statistical Learning with Sparsity: The Lasso and Generalizations, Chapman and Hall/CRC, New York, USA, 2015, 367 pp. | DOI

[7] Altmann D., Grycko E., Hochstättler W., Klützke G., Monotone smoothing of noisy data. Diskrete Mathematik und Optimierung, Technical Report feu-dmo034.15, FernUniversität in Hagen, Fakultät für Mathematik und Informatik, 2014, 6 pp.

[8] Diggle P., Morris S., Morton-Jones T., “Case-control isotonic regression for investigation of elevation in risk around a point source”, Statistics in Medicine, 18:13 (1999), 1605–1613 | 3.0.co;2-v class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[9] Cai Y., Judd K. L., “Chapter 8 – Advances in numerical dynamic programming and new applications”, Handbook of Computational Economics, 3, 2014, 479–516 | DOI

[10] Shevaldin V. T., Approximation by Local Splines, UMC UPI Publ, Ekaterinburg, 2014, 198 pp. (in Russian)

[11] Boytsov D. I., Sidorov S. P., “Linear approximation method preserving $k$-monotonicity”, Siberian Electronic Mathematical Reports, 12 (2015), 21–27

[12] Milovanović I. Z., Milovanović E. I., “Some properties of $l_p^k$-convex sequences”, Bulletin of the International Mathematical Virtual Institute, 5:1 (2015), 33–36

[13] Niezgoda M., “Inequalities for convex sequences and nondecreasing convex functions”, Aequationes Mathematicae, 91:1 (2017), 1–20 | DOI

[14] Latreuch Z., Bela\"{i}di B., “New inequalities for convex sequences with applications”, International Journal of Open Problems in Computer Science and Mathematics, 5:3 (2012), 15–27 | DOI

[15] Marshall A. W., Olkin I., Arnold B. C., Inequalities: Theory of Majorization and Its Applications, Springer, New York, USA, 2011, 909 pp. | DOI

[16] Gudkov A., Mironov S. V., Sidorov S. P., Tyshkevich S. V., “A dual active set algorithm for optimal sparse convex regression”, Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, 23:1 (2019), 113–130 | DOI

[17] Sidorov S. P., Faizliev A. R., Gudkov A. A., Mironov S. V., “Algorithms for sparse $k$-monotone regression”, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018, Lecture Notes in Computer Science, 10848, ed. W. J. van Hoeve, Springer, Cham, 2018, 546–566 | DOI