Interior epigraph directions method for nonsmooth and nonconvex optimization via generalized augmented Lagrangian duality. (English) Zbl 1327.90227

Summary: We propose and study a new method, called the Interior Epigraph Directions (IED) method, for solving constrained nonsmooth and nonconvex optimization. The IED method considers the dual problem induced by a generalized augmented Lagrangian duality scheme, and obtains the primal solution by generating a sequence of iterates in the interior of the dual epigraph. First, a deflected subgradient (DSG) direction is used to generate a linear approximation to the dual problem. Second, this linear approximation is solved using a Newton-like step. This Newton-like step is inspired by the Nonsmooth Feasible Directions Algorithm (NFDA), recently proposed by Freire and co-workers for solving unconstrained, nonsmooth convex problems. We have modified the NFDA so that it takes advantage of the special structure of the epigraph of the dual function. We prove that all the accumulation points of the primal sequence generated by the IED method are solutions of the original problem. We carry out numerical experiments by using test problems from the literature. In particular, we study several instances of the Kissing Number Problem, previously solved by various approaches such as an augmented penalty method, the DSG method, as well as several popular differentiable solvers. Our experiments show that the quality of the solutions obtained by the IED method is comparable with (and sometimes favourable over) those obtained by the differentiable solvers.


90C26 Nonconvex programming, global optimization
49M29 Numerical methods involving duality
49M37 Numerical methods based on nonlinear programming
90C90 Applications of mathematical programming


Full Text: DOI


[1] Bagirov, AM; Karasözen, B; Sezer, M, Discrete gradient method: a derivative free method for nonsmooth optimization, J. Optim. Theory Appl., 137, 317-334, (2008) · Zbl 1165.90021
[2] Bagirov, AM; Ganjehlou, AN, A quasisecant method for minimizing nonsmooth functions, Optim. Methods Softw., 25, 3-18, (2010) · Zbl 1202.65072
[3] Burachik, RS, On primal convergence for augmented Lagrangian duality, Optimization, 60, 979-990, (2011) · Zbl 1231.90316
[4] Burachik, RS; Gasimov, RN; Ismayilova, NA; Kaya, CY, On a modified subgradient algorithm for dual problems via sharp augmented Lagrangian, J. Glob. Optim., 34, 55-78, (2006) · Zbl 1098.90091
[5] Burachik, RS; Iusem, AN; Melo, JG, A primal dual modified subgradient algorithm with sharp Lagrangian, J. Glob. Optim., 46, 347-361, (2010) · Zbl 1188.90200
[6] Burachik, RS; Iusem, AN; Melo, JG, Strong duality and exact penalization for general augmented Lagrangians, J. Optim. Theory Appl., 147, 125-140, (2010) · Zbl 1211.90284
[7] Burachik, RS; Kaya, CY, An update rule and a convergence result for a penalty function method, J. Ind. Manag. Opt., 3, 381-398, (2007) · Zbl 1288.49010
[8] Burachik, RS; Kaya, CY, An augmented penalty function method with penalty parameter updates for nonconvex optimization, Nonlinear Anal. Theory Methods Appl., 75, 1158-1167, (2012) · Zbl 1229.90135
[9] Burachik, RS; Kaya, CY; Burachik, RS (ed.); Yao, JC (ed.), A deflected subgradient algorithm using a general augmented Lagrangian duality with implications on penalty methods, 109-132, (2010), New York · Zbl 1227.90031
[10] Burachik, RS; Kaya, CY; Mammadov, M, An inexact modified subgradient algorithm for nonconvex optimization, Comput. Optim. Appl., 45, 1-24, (2010) · Zbl 1208.90137
[11] Freire, W. P.: A feasible directions algorithm for convex nondifferentiable optimization. Ph.D. Thesis. COPPE/UFRJ. Rio de Janeiro. (2005) http://www.optimize.ufrj.br/files/WilhelmPassarellaFreire.pdf
[12] Gasimov, RN, Augmented Lagrangian duality and nondifferentiable optimization methods in nonconvex programming, J. Glob. Optim., 24, 187-203, (2002) · Zbl 1047.90048
[13] Haarala, M; Miettinen, K; Mäkelä, MM, New limited memory bundle method for large-scale nonsmooth optimization, Optim. Methods Softw., 19, 673-692, (2004) · Zbl 1068.90101
[14] Haarala, N; Miettinen, K; Mäkelä, MM, Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Math. Program., 109, 181-205, (2007) · Zbl 1278.90451
[15] Herskovits, J, Feasible directions interior point technique for nonlinear optimization, J. Optim. Theory Appl., 99, 121-146, (1998) · Zbl 0911.90303
[16] Herkovits, J; Freire, WP; Tanaka, M; Canelas, A, A feasible directions method for nonsmooth convex optimization, Struct. Multidisc. Optim., 44, 363-377, (2011) · Zbl 1274.90261
[17] Hock, W., Schittkowski, K.: In: Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer, New York (1981) · Zbl 0452.90038
[18] Kappel, F; Kuntsevich, AV, An implementation of shor’s \(r\)-algorithm, Comput. Optim. Appl., 15, 193-205, (2000) · Zbl 0947.90112
[19] Karmitsa, N; Bagirov, A; Mäkelä, MM, Comparing different nonsmooth minmization methods and software, Optim. Methods Softw., 47, 131-153, (2012) · Zbl 1242.90233
[20] Karmitsa, N; Tanaka, M; Herskovits, J, Globally convergent cutting plane method for nonconvex nonsmooth minimization, J. Optim. Theory Appl., 148, 528-549, (2011) · Zbl 1229.90140
[21] Krejić, N; Martínez, JM; Mello, M; Pilotta, EA, Validation of an augmented Lagrangian algorithm with a Gauss-Newton Hessian approximation using a set of hard-spheres problems, Comput. Optim. Appl., 16, 247-263, (2000) · Zbl 0997.90103
[22] Lukšan, L; Vlcěk, J, A bundle-Newton method for nonsmooth unconstrained minimization, Math. Program., 83, 373-391, (1998) · Zbl 0920.90132
[23] Mäkelä, M.M.: Multiobjective proximal bundle method for nonconvex nonsmooth optimization: Fortran subroutine MPBNGC 2.0, Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing, B. 13/2003 University of Jyväskylä, Jyväskylä (2003) · Zbl 1098.90091
[24] Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific Publishing Co., Singapore (1992) · Zbl 0757.49017
[25] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001
[26] Shor, N.Z.: Minimization Methods for Non-differentiable Functions. Springer, Berlin (1985) · Zbl 0561.90058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.