Abstract
In this paper, a new hybrid method is proposed which combines the advantages of descent methods and cutting plane approaches. The new method gets fast to near-optimal region by using cutting planes and preserves the good convergence properties of descent methods near the optimum. The method is tested on convex functions, least squares problems and on parameter estimation by comparing its performance to well-known methods. Numerical experiments show that the proposed method is very efficient on all the examined problem types and performs in average much better than the benchmark methods.
Similar content being viewed by others
References
Aknouche A, Guerbyenne H (2006) Recursive estimation of GARCH models. Commun Stat Simul Comput 35(4): 925–938
Armijo L (1966) Minimization of functions having Lipschitz continuous first partial derivatives. Pac J Math 16(1): 1–3
Auslender A, Silva PJ, Teboulle M (2007) Nonmonotone projected gradient methods based on barrier and euclidean distances. Comput Optim Appl 38(3): 305–327
Berkes I, Horváth L, Kokoszka P (2003) GARCH processes: structure and estimation. Bernoulli 9: 201–217
Berndt E, Hall B, Hall R, Hausman J (1974) Estimation and inference in nonlinear structural models. Ann Econ Soc Meas 3: 653–665
Bollerslev T (1986) Generalized autoregressive conditional. Heteroscedasticity. J Econ 31(3): 307–327
Bollerslev T, Wooldridge JM (1992) Quasi-maximum likelihood estimation and inference in dynamic models with time-varying covariances. Econ Rev 11: 143–172
Boyd S (2008) Notes on subgradient methods. Unpublished note for EE364B available at http://www.stanford.edu/class/ee364b/(2008)
Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge
Crummey TP, Farshadnia R, Fleming PJ, Grace ACW, Hancock SD (1991) An optimization toolbox for MATLAB. IEE Conf Pub 2(332): 744–749
Engle RF (1982) Autoregressive conditional heteroscedasticity with estimates of the variance of united kingdom inflation. Econometrica 50(4): 987–1007
Fletcher R (1980) Practical methods of optimization, vol 1: unconstrained optimization, 1st edn. Wiley, New York (1980)
Gerencsér L, Molnár-Sáska G, Orlovits Z (2005) Recursive estimation of Hidden Markov models. In: 44th IEEE conference on decision and control and European control conference, pp 1209–1214
Kelley CT (1999) Iterative methods for optimization. Frontiers in applied mathematics. SIAM, Philadelphia, PA, USA
Luenberger DG (1973) Introduction to linear and nonlinear programming. Addison-Wesley, Reading
Moré JJ, Garbow BS, Hillstrom KE (1981) Testing unconstrained optimization software. ACM Trans Math Softw 7(1): 17–41
Murray W, Overton ML (1978) Steplength algorithms for minimizing a class of nondifferentiable functions. Tech. rep. Stanford University, Stanford
Polyak RA (2007) Regularized Newton method for unconstrained convex optimization. Math. Prog. Published online
Shi ZJ (2004) Convergence of line search methods for unconstrained optimization. Appl Math Comput 157(2): 393–405
Soderstrom T, Stoica P (1989) System identification. Prentice Hall, Englewood Cliffs
Sonnevend G (1988) New algorithms in convex programming based on a notion of “centre” (for systems of analytic inequalities) and on rational extrapolation. In: Hoffman K, Hiriat-Urruty J, Lemarechal C, Zowe J (eds) Trends in mathematical optimization: proceedings of the 4th French–German conference in optimization in Irsee, vol 84. Birkhauser, Baesl, pp 311–327
Ye Y (1997) Complexity analysis of the analytic center cutting plane method that uses multiple cuts. Math Program 78(1): 85–104
Zhang H, Hager WW (2004) A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim 14(4): 1043–1056
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has been supported by grants from the Ministry of Science and Innovation of Spain (TIN2008-01117, SEJ2005-06273/ECON, ECO2008-00667/ECON), Junta de Andalucía (P08-TIC-3518), and OTKA TS 49835.
Rights and permissions
About this article
Cite this article
Torma, B., G.-Tóth, B. An efficient descent direction method with cutting planes. Cent Eur J Oper Res 18, 105–130 (2010). https://doi.org/10.1007/s10100-009-0085-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-009-0085-3