Abstract
Motivated by two important problems, the least median of squares (LMS) regression and value-at-risk (VaR) optimization, this paper considers the problem of minimizing the k-th maximum for linear functions. For this study, a sufficient and necessary condition of local optimality is given. From this condition and other properties, we propose an algorithm that uses linear programming technique. The algorithm is assessed on real data sets and the experiments for LMS regression and VaR optimization both show its effectiveness.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agulló J (1997). Exact algorithms for computing the least median of squares estimate in multiple linear regression. Lecture Notes Monograph Series 31: 133–146.
Alexander S, Coleman T and Li Y (2006). Minimizing CVaR and VaR for a portfolio of derivatives. Journal of Banking and Finance 30 (2): 583–605.
Artzner P, Delbaen F, Eber J and Heath D (1997). Thinking coherently. Risk 10 (11): 68–71.
Artzner P, Delbaen F, Eber J and Heath D (1999). Coherent measure of risk. Mathematical Finance 9 (3): 203–228.
Benati S and Rizzi R (2007). A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem. European Journal of Operational Research 176 (1): 423–434.
Boček P and Lachout P (1995). Linear programming approach to LMS-estimation. Computational Statistics & Data Analysis 19 (2): 129–134.
Camden M (1989). The Data Bundle. New Zealand Statistical Association: Wellington, New Zealand.
Chakraborty B and Chaudhuri P (2008). On an optimization problem in robust statistics. Journal of Computational and Graphical Statistics 17 (3): 683–702.
Dallagnol VAF, Van den Berg J and Mous L (2009). Portfolio management using value at risk: A comparison between genetic algorithms and particle swarm optimization. International Journal of Intelligent Systems 24 (7): 766–792.
Draper N and Smith H (1998). Applied Regression Analysis. John Wiley and Sons Inc.: New York.
Duffie D and Pan J (1997). An overview of value at risk. Journal of Derivatives 4 (3): 7–49.
Gaivoronski A and Pflug G (2005). Value at risk in portfolio optimization: properties and computational approach. Journal of Risk 7 (2): 1–31.
Gilli M, Kellezi E and Hysi H (2006). A data-driven optimization heuristic for downside risk minimization. Journal of Risk 8 (3): 1465–1211.
Hansen P and Mladenović N (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research 130 (3): 449–467.
Larsen N, Mausser H and Uryasev S (2002). Algorithms for optimization of value-at-risk. In: Pardalos P and Tsitsiringos VK (eds). Financial Engineering, e-Commerce and Supply Chain. Kluwer Academic publishers: Dordrecht, The Netherlands, pp 129–157.
Mansini R, Ogryczak W and Speranza M (2007). Conditional value at risk and related linear programming models for portfolio optimization. Annals of Operations Research 152 (1): 227–256.
Mladenović N and Hansen P (1997). Variable neighborhood search. Computer Operations Research 24 (11): 1097–1100.
Olson C (1997). An approximation algorithm for least median of squares regression. Information Processing Letters 63 (5): 237–241.
Pang J and Leyffer S (2004). On the global minimization of the value-at-risk. Optimization Methods and Software 19 (5): 611–631.
Rousseeuw P (1984). Least median of squares regression. Journal of American Statistical Association 79 (388): 871–880.
Rousseeuw P and Hubert M (1997). Recent developments in PROGRESS. Lecture Notes Monographic Series 31: 201–214.
Rousseeuw P and Leroy A (1987). Robust Regression and Outlier Detection, 1987. John Wiley and Sons Inc.: New York.
Steele J and Steiger W (1986). Algorithms and complexity for least median of squares regression. Discrete Applied Mathematics 14 (1): 93–100.
Stromberg A (1993). Computing the exact least median of squares estimate and stability diagnostics in multiple linear regression. SIAM Journal on Scientific Computing 14: 1289–1299.
Suykens J, De Brabanter J, Lukas L and Vandewalle J (2002). Weighted least squares support vector machines: robustness and sparse approximation. Neurocomputing 48 (1–4): 85–105.
Tichavsky P (1991). Algorithms for and geometrical characterization of solutions in the LMS and the LTS linear regression. Computational Statistics Quarterly 8: 139–151.
Trafalis T and Gilbert R (2006). Robust classification and regression using support vector machines. European Journal of Operational Research 173 (3): 893–909.
Verardi V and Croux C (2009). Robust regression in Stata. Stata Journal 9 (3): 439–453.
Winker P, Lyra M and Sharpe C (2011). Least median of squares estimation by optimization heuristics with an application to the CAPM and a multi-factor model. Computational Management Science 8 (1): 103–123.
Xu C and Ng P (2006). A soft approach for hard continuous optimization. European Journal of Operational Research 173 (1): 18–29.
Acknowledgements
The authors appreciate the reviewers for their insightful comments and helpful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Project jointly supported by the National Natural Science Foundation of China (61074118, 60974008, 61134012, 61104218) and the Research Fund of Doctoral Program of Higher Education (200800030029).
Rights and permissions
About this article
Cite this article
Huang, X., Xu, J., Wang, S. et al. Minimization of the k-th maximum and its application on LMS regression and VaR optimization. J Oper Res Soc 63, 1479–1491 (2012). https://doi.org/10.1057/jors.2011.163
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.163