Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2018 | OriginalPaper | Buchkapitel

Algorithms for Sparse k-Monotone Regression

verfasst von : Sergei P. Sidorov, Alexey R. Faizliev, Alexander A. Gudkov, Sergei V. Mironov

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The problem of constructing k-monotone regression is to find a vector \(z\in \mathbb {R}^n\) with the lowest square error of approximation to a given vector \(y\in \mathbb {R}^n\) (not necessary k-monotone) under condition of k-monotonicity of z. The problem can be rewritten in the form of a convex programming problem with linear constraints. The paper proposes two different approaches for finding a sparse k-monotone regression (Frank-Wolfe-type algorithm and k-monotone pool adjacent violators algorithm). A software package for this problem is developed and implemented in R. The proposed algorithms are compared using simulated data.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Ahuja, R., Orlin, J.: A fast scaling algorithm for minimizing separable convex functions subject to chain constraints. Oper. Res. 49(1), 784–789 (2001)MathSciNetCrossRef
2.
Altmann, D., Grycko, E., Hochstättler, W., Klützke, G.: Monotone smoothing of noisy data. Diskrete Mathematik und Optimierung. Technical report feu-dmo034.15. Fern Universität in Hagen, Fakultät für Mathematik und Informatik (2014)
3.
Bach, F.: Efficient algorithms for non-convex isotonic regression through submodular optimization (2017), Working paper or preprint
4.
Balabdaoui, F., Rufibach, K., Santambrogio, F.: Least-squares estimation of two-ordered monotone regression curves. J. Nonparametr. Stat. 22(8), 1019–1037 (2010)MathSciNetCrossRef
5.
Barlow, R., Brunk, H.: The isotonic regression problem and its dual. J. Am. Stat. Assoc. 67(337), 140–147 (1972)MathSciNetCrossRef
6.
Best, M.J., Chakravarti, N.: Active set algorithms for isotonic regression: a unifying framework. Math. Progr.: Ser. A B 47(3), 425–439 (1990)MathSciNetCrossRef
7.
Best, M., Chakravarti, N., Ubhaya, V.: Minimizing separable convex functions subject to simple chain constraints. SIAM J. Optim. 10(3), 658–672 (2000)MathSciNetCrossRef
8.
Bor, H.: A study on local properties of Fourier series. Nonlinear Anal.: Theory Methods Appl. 57(2), 191–197 (2004)MathSciNetCrossRef
9.
Bor, H.: A note on local property of factored Fourier series. Nonlinear Anal.: Theory Methods Appl. 64(3), 513–517 (2006)MathSciNetCrossRef
10.
Boytsov, D.I., Sidorov, S.P.: Linear approximation method preserving \(k\)-monotonicity. Sib. Electron. Math. Rep. 12, 21–27 (2015)MathSciNetMATH
11.
Brezger, A., Steiner, W.J.: Monotonic regression based on bayesian P-splines. J. Bus. Econ. Stat. 26(1), 90–104 (2008)CrossRef
12.
Burdakov, O., Grimvall, A., Hussian, M.: A generalised PAV algorithm for monotonic regression in several variables. In: Antoch, J. (ed.) Proceedings of the 16th Symposium in Computational Statistics, COMPSTAT, vol. 10, no. 1, pp. 761–767 (2004)
13.
Burdakov, O., Sysoev, O.: A dual active-set algorithm for regularized monotonic regression. J. Optim. Theory Appl. 172(3), 929–949 (2017)MathSciNetCrossRef
14.
15.
Cai, Y., Judd, K.L.: Advances in numerical dynamic programming and new applications. In: Handbook of Computational Economics, vol. 3, pp. 479–516. Elsevier (2014)CrossRef
16.
Chen, Y.: Aspects of shape-constrained estimation in statistics. Ph.D. thesis. University of Cambridge (2013)
17.
Chepoi, V., Cogneau, D., Fichet, B.: Polynomial algorithms for isotonic regression. Lect. Notes-Monogr. Ser. 31(1), 147–160 (1997)MathSciNetCrossRef
18.
Cullinan, M.P.: Piecewise convex-concave approximation in the minimax norm. In: Demetriou, I., Pardalos, P. (eds.) Abstracts of Conference on Approximation and Optimization: Algorithms, Complexity, and Applications, Athens, Greece, 29–30 June 2017, p. 4. National and Kapodistrian University of Athens (2017)
19.
Diggle Peter, M.S., Tony, M.J.: Case-control isotonic regression for investigation of elevation in risk around a point source. Stat. Med. 18(1), 1605–1613 (1999)CrossRef
20.
21.
Dykstra, R., Robertson, T.: An algorithm for isotonic regression for two or more independent variables. Ann. Stat. 10(1), 708–719 (1982)MathSciNetCrossRef
22.
Faizliev, A.R., Gudkov, A.A., Mironov, S.V., Levshunov, M.A.: Greedy algorithm for sparse monotone regression. In: CEUR Workshop Proceedings, vol. 2018, pp. 23–31 (2017)
23.
24.
Gal, S.G.: Shape-Preserving Approximation by Real and Complex Polynomials. Birkhäuser, Boston (2008)CrossRef
25.
Gorinevsky, D.: Monotonic regression filters for trending deterioration faults. In: Proceedings of the American Control Conference, vol. 6, pp. 5394–5399 (2004)
26.
Gorinevsky, D.: Efficient filtering using monotonic walk model. In: Proceedings of the American Control Conference, pp. 2816–2821. IEEE (2008)
27.
Gudkov, A.A., Mironov, S.V., Faizliev, A.R.: On the convergence of a greedy algorithm for the solution of the problem for the construction of monotone regression. Izv. Sarat. Univ. (N. S.) Ser. Math. Mech. Inform. 17(4), 431–440 (2017)CrossRef
28.
Hansohm, J.: Algorithms and error estimations for monotone regression on partially preordered sets. J. Multivar. Anal. 98(5), 1043–1050 (2007)MathSciNetCrossRef
29.
Hastie, T., Tibshirani, R., Wainwright, M.: Statistical Learning with Sparsity. Chapman and Hall/CRC, New York (2015)MATH
30.
Hazelton, M., Turlach, B.: Semiparametric regression with shape-constrained penalized splines. Comput. Stat. Data Anal. 55(10), 2871–2879 (2011)MathSciNetCrossRef
31.
Jaggi, M.: Revisiting Frank-Wolfe: projection-free sparse convex optimization. In: Proceedings of the 30th International Conference on Machine Learning, ICML 2013, pp. 427–435 (2013)
32.
Judd, K.: Numerical Methods in Economics. The MIT Press, Cambridge (1998)MATH
33.
Latreuch, Z., Belaïdi, B.: New inequalities for convex sequences with applications. Int. J. Open Probl. Comput. Math. 5(3), 15–27 (2012)CrossRef
34.
Leeuw, J., Hornik, K., Mair, P.: Isotone optimization in R: pool-adjacent-violators algorithm (PAVA) and active set methods. J. Stat. Softw. 32(5), 1–24 (2009)CrossRef
35.
36.
Leitenstorfer, F., Tutz, G.: Generalized monotonic regression based on B-splines with an application to air pollution data. Biostatistics 8(3), 654–673 (2007)CrossRef
37.
38.
Gorinevsky, D., Kim, S.J., Beard, S., Boyd, S., Gordon, G.: Optimal estimation of deterioration from diagnostic image sequence. IEEE Trans. Signal Process. 57(3), 1030–1043 (2009)MathSciNetCrossRef
39.
40.
Milovanović, I.Z., Milovanović, E.I.: Some properties of \(l_p^k\)-convex sequences. Bull. Int. Math. Virtual Inst. 5(1), 33–36 (2015)MathSciNetMATH
41.
Niezgoda, M.: Inequalities for convex sequences and nondecreasing convex functions. Aequ. Math. 91(1), 1–20 (2017)MathSciNetCrossRef
42.
Robertson, T., Wright, F., Dykstra, R.: Order Restricted Statistical Inference. Wiley, New York (1988)MATH
43.
Shevaldin, V.T.: Local approximation by splines. UrO RAN, Ekaterinburg (2014)
44.
45.
46.
Sidorov, S.: On the saturation effect for linear shape-preserving approximation in Sobolev spaces. Miskolc Math. Notes 16(2), 1191–1197 (2015)MathSciNetCrossRef
47.
48.
Siem, A.Y.D., den Hertog, D., Hoffmann, A.L.: Multivariate convex approximation and least-norm convex data-smoothing. In: Gavrilova, M., Gervasi, O., Kumar, V., Tan, C.J.K., Taniar, D., Laganá, A., Mun, Y., Choo, H. (eds.) ICCSA 2006. LNCS, vol. 3982, pp. 812–821. Springer, Heidelberg (2006). https://​doi.​org/​10.​1007/​11751595_​86CrossRefMATH
49.
Stromberg, U.: An algorithm for isotonic regression with arbitrary convex distance function. Comput. Stat. Data Anal. 11(1), 205–219 (1991)MathSciNetCrossRef
50.
Toader, G.: The representation of \(n\)-convex sequences. L’Anal. Numér. et la Théorie de L’Approx. 10(1), 113–118 (1981)MathSciNetMATH
51.
Wu, S., Debnath, L.: Inequalities for convex sequences and their applications. Comput. Math. Appl. 54(4), 525–534 (2007)MathSciNetCrossRef
52.
Wu, W.B., Woodroofe, M., Mentz, G.: Isotonic regression: another look at the changepoint problem. Biometrika 88(3), 793–804 (2001)MathSciNetCrossRef
Metadaten
Titel
Algorithms for Sparse k-Monotone Regression
verfasst von
Sergei P. Sidorov
Alexey R. Faizliev
Alexander A. Gudkov
Sergei V. Mironov
Copyright-Jahr
2018
Buch
Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Print ISBN: 978-3-319-93030-5

Electronic ISBN: 978-3-319-93031-2

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-93031-2_39