×

zbMATH — the first resource for mathematics

Smoothing methods for nonsmooth, nonconvex minimization. (English) Zbl 1266.90145
The author considers the optimization problem \[ f(x)\to\min,\quad\text{subject to }x\in X, \] where \(X\) is a closed convex subset of \(\mathbb{R}^n\) and \(f:\mathbb{R}^n\to \mathbb{R}\) is continuous and almost everywhere differentiable in \(X\). Special attention is devoted to the case of a nonsmooth and nonconvex objective function, which is not in general locally Lipschitzian. For solving such optimization problems, smoothing methods are proposed using smoothing functions. Properties of the smoothing functions and conditions ensuring the convergence of the proposed methods to a stationary point of the original problem are presented. The last section of the paper is devoted to the numerical implementation of the proposed procedures.

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
65K10 Numerical optimization and variational techniques
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alefeld G., Chen X.: A regularized projection method for complementarity problems with non-Lipschitzian functions. Math. Comput. 77, 379–395 (2008) · Zbl 1171.90015
[2] Auslender A.: How to deal with the unbounded in optimization: theory and algorithm. Math. Program. 79, 3–18 (1997) · Zbl 0887.90131
[3] Ben-Tal A., EI Ghaoui L., Nemirovski A.: Robust Optimization. Princeton University Press, Princeton (2009) · Zbl 1221.90001
[4] Bian W., Chen X.: Smoothing neural network for constrained non-Lipschitz optimization with applications. IEEE Trans. Neural Netw. Learn. Syst. 23, 399–411 (2012)
[5] Bian, W., Chen, X.: Neural network for nonsmooth, nonconvex constrained minimization via smooth approximation. Preprint (2011)
[6] Bian, W., Chen, X.: Smoothing SQP algorithm for non-Lipschitz optimization with complexity analysis. Preprint (2012)
[7] Bian W., Xue X.P.: Subgradient-based neural network for nonsmooth nonconvex optimization problem. IEEE Trans. Neural Netw. 20, 1024–1038 (2009)
[8] Bruckstein A.M., Donoho D.L., Elad M.: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51, 34–81 (2009) · Zbl 1178.68619
[9] Burke J.V.: Descent methods for composite nondifferentiable optimization problems. Math. Program. 33, 260–279 (1985) · Zbl 0581.90084
[10] Burke J.V., Lewis A.S., Overton M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15, 751–779 (2005) · Zbl 1078.65048
[11] Burke J.V., Henrion D., Lewis A.S., Overton M.L.: Stabilization via nonsmooth, nonconvex optimization. IEEE Trans. Automat. Control 51, 1760–1769 (2006) · Zbl 1366.93490
[12] Catis C., Gould N.I.M., Toint P.: On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. SIAM J. Optim. 21, 1721–1739 (2011) · Zbl 1236.90118
[13] Chartrand R.: Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Proc. Lett. 14, 707–710 (2007)
[14] Chen B., Chen X.: A global and local superlinear continuation-smoothing method for P 0 and R 0 NCP or monotone NCP. SIAM J. Optim. 9, 624–645 (1999) · Zbl 0955.90132
[15] Chen B., Harker P.T.: A non-interior-point continuation method for linear complementarity problems. SIAM J. Matrix Anal. Appl. 14, 1168–1190 (1993) · Zbl 0788.65073
[16] Chen B., Xiu N.: A global linear and local quadratic noninterior continuation method for nonlinear complementarity problems based on Chen–Mangasarian smoothing functions. SIAM J. Optim. 9, 605–623 (1999) · Zbl 1037.90052
[17] Chen C., Mangasarian O.L.: A class of smoothing functions for nonlinear and mixed complementarity problems. Math. Program. 71, 51–70 (1995) · Zbl 0855.90124
[18] Chen X.: Smoothing methods for complementarity problems and their applications: a survey. J. Oper. Res. Soc. Japan 43, 32–46 (2000) · Zbl 0998.90078
[19] Chen X.: A superlinearly and globally convergent method for reaction and diffusion problems with a non-Lipschitzian operator. Computing[Suppl] 15, 79–90 (2001) · Zbl 0998.65095
[20] Chen X.: First order conditions for nonsmooth discretized constrained optimal control problems. SIAM J. Control Optim. 42, 2004–2015 (2004) · Zbl 1058.49025
[21] Chen X., Fukushima M.: Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 1022–1038 (2005) · Zbl 1162.90527
[22] Chen X., Fukushima M.: A smoothing method for a mathematical program with P-matrix linear complementarity constraints. Comput. Optim. Appl. 27, 223–246 (2004) · Zbl 1046.90086
[23] Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained L 2 p minimization. Preprint (2011)
[24] Chen X., Nashed Z., Qi L.: Smoothing methods and semismooth methods for nondifferentiable operator equations. SIAM J. Numer. Anal. 38, 1200–1216 (2000) · Zbl 0979.65046
[25] Chen, X., Niu, L., Yuan, Y.: Optimality conditions and smoothing trust region Newton method for non-Lipschitz optimization. Preprint (2012)
[26] Chen X., Qi L.: A parameterized Newton method and a quasi-Newton method for nonsmooth equations. Comput. Optim. Appl. 3, 157–179 (1994) · Zbl 0821.65029
[27] Chen X., Qi L., Sun D.: Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comput. 67, 519–540 (1998) · Zbl 0894.90143
[28] Chen, X., Wets, R.J-B., Zhang, Y.: Stochastic variational inequalities: residual minimization smoothing/sample average approximations SIAM J. Optim. (to appear) · Zbl 1263.90098
[29] Chen X., Womersley R., Ye J.: Minimizing the condition number of a Gram matrix. SIAM J. Optim. 21, 127–148 (2011) · Zbl 1220.65055
[30] Chen X., Xu F., Ye Y.: Lower bound theory of nonzero entries in solutions of l 2 p minimization. SIAM J. Sci. Comput. 32, 2832–2852 (2012) · Zbl 1242.90174
[31] Chen X., Ye Y.: On homotopy-smoothing methods for variational inequalities. SIAM J. Control Optim. 37, 587–616 (1999) · Zbl 0973.65051
[32] Chen X., Zhang C., Fukushima M.: Robust solution of monotone stochastic linear complementarity problems. Math. Program. 117, 51–80 (2009) · Zbl 1165.90012
[33] Chen X., Zhou W.: Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 3, 765–790 (2010) · Zbl 1200.65031
[34] Clarke F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[35] Conn A.R., Scheinberg K., Vicente L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Book Series on Optimization. SIAM, Philadelphia (2009) · Zbl 1163.49001
[36] Cottle R.W., Pang J.S., Stone R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)
[37] Daniilidis A., Sagastizbal C., Solodov M.: Identifying structure of nonsmooth convex functions by the bundle technique. SIAM J. Optim. 20, 820–840 (2009) · Zbl 1191.90066
[38] Delage E., Ye Y.: Distributionally robust optimization under monment uncertainty with application to data-driven problems. Oper. Res. 58, 595–612 (2010) · Zbl 1228.90064
[39] Facchinei F., Jiang H., Qi L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85, 107–134 (1999) · Zbl 0959.65079
[40] Facchinei F., Pang J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[41] Fan J.: Comments on ”Wavelets in Statistic: a review” by A. Antoniadis. Stat. Method. Appl. 6, 131–138 (1997)
[42] Fan J., Li R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96, 1348–1360 (2001) · Zbl 1073.62547
[43] Fang H., Chen X., Fukushima M.: Stochastic R0 matrix linear complementarity problems. SIAM J. Optim. 18, 482–506 (2007) · Zbl 1151.90052
[44] Ferris M.: Extended mathematical programming: competition and stochasticity. SIAM News 45, 1–2 (2012)
[45] Fischer A.: A special Newton-type optimization method. Optimization 24, 269–284 (1992) · Zbl 0814.65063
[46] Fukushima M., Luo Z.-Q., Pang J.-S.: A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints. Comput. Optim. Appl. 10, 5–34 (1998) · Zbl 0904.90153
[47] Fukushima M., Luo Z.-Q., Tseng P.: Smoothing functions for second-order-cone complementarity problems. SIAM J. Optim. 12, 436–460 (2002) · Zbl 0995.90094
[48] Fukushima M., Pang J.-S.: Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: Thera, M., Tichatschke, R. (eds) Lecture Notes in Economics and Mathematical Systems, vol. 477, pp. 99–110. Springer, Berlin (1999) · Zbl 0944.65070
[49] Gabriel S.A., More J.J.: Smoothing of mixed complementarity problems. In: Ferris, M.C., Pang, J.S. (eds.) Complementarity and Variational Problems: State of the Art, pp. 105–116. SIAM, Philadelphia (1997) · Zbl 0886.90154
[50] Garmanjani, R., Vicente, L.N.: Smoothing and worst case complexity for direct-search methods in non-smooth optimization. Preprint (2011) · Zbl 1272.65050
[51] Ge D., Jiang X., Ye Y.: A note on the complexity of L p minimization. Math. Program. 21, 1721–1739 (2011) · Zbl 1226.90076
[52] Geman D., Reynolds G.: Constrained restoration and the recovery of discontinuities. IEEE Trans. Pattern Anal. Mach. Intell. 14, 357–383 (1992)
[53] Gürkan G., Özge A.Y., Robinson S.M.: Sample-path solution of stochastic variational inequalities. Math. Program. 84, 313–333 (1999) · Zbl 0972.90079
[54] Hamatani K., Fukushima M.: Pricing American options with uncertain volatility through stochastic linear complementarity models. Comput. Optim. Appl. 50, 263–286 (2011) · Zbl 1236.91133
[55] Hastie T., Tibshirani R., Friedman J.: The Elements of Statistical Learning Data Mining, Inference, and Prediction. Springer, New York (2009) · Zbl 1273.62005
[56] Hayashi S., Yamashita N., Fukushima M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593–615 (2005) · Zbl 1114.90139
[57] Heinkenschloss M., KelleyC.T. Tran H.T.: Fast algorithms for nonsmooth compact fixed-point problems. SIAM J. Numer. Anal. 29, 1769–1792 (1992) · Zbl 0763.65040
[58] Hintermueller, M., Wu, T.: Nonconvex TV q -models in image restoration: analysis and a trust-region regularization based superlinearly convergent solver. Preprint (2011)
[59] Hiriart-Urruty J.B., Lemareéchal C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Boundle Methods. Springer, Berlin (1993) · Zbl 0795.49002
[60] Hu, M., Fukushima, M.: Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints. Comput. Optim. Appl. (to appear) · Zbl 1275.90107
[61] Huang J., Horowitz J.L., Ma S.: Asymptotic properties of bridge estimators in sparse high-dimensional regression models. Ann. Stat. 36, 587–613 (2008) · Zbl 1133.62048
[62] Huang J., Ma S., Xie H., Zhang C.-H.: A group bridge approach for variable selection. Biometrika 96, 339–355 (2009) · Zbl 1163.62050
[63] Huang Z., Qi L., Sun D.: Sub-quadratic convergence of a smoothing Newton algorithm for the P 0- and monotone LCP. Math. Program. 99, 423–441 (2004) · Zbl 1168.90646
[64] Jiang H., Ralph D.: Smooth SQP methods for mathematical programs with nonlinear complementarity constraints. Comput. Optim. Appl. 25, 123–150 (2002) · Zbl 1038.90100
[65] Jiang H., Xu H.: Stochastic approximation approaches to the stochastic variational inequality problem. IEEE. Trans. Autom. Control 53, 1462–1475 (2008) · Zbl 1367.90072
[66] Kanzow C.: Some noninterior continuation methods for linear cornplementarity problems. SIAM J. Matrix Anal. Appl. 17, 851–868 (1996) · Zbl 0868.90123
[67] Knight K., Fu W.J.: Asymptotics for lasso-type estimators. Ann. Stat. 28, 1356–1378 (2000) · Zbl 1105.62357
[68] Kiwiel K.C.: Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Math, vol. 1133. Springer, Berlin (1985) · Zbl 0561.90059
[69] Kiwiel K.C.: Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 18, 379–388 (2007) · Zbl 1149.65043
[70] Lewis A.S., Pang C.H.J.: Lipschitz behavior of the robust regularization. SIAM, J. Control Optim. 48, 3080–3104 (2010) · Zbl 1202.49047
[71] Lewis A.S., Overton M.L.: Eigenvalue optimization. Acta Numerica 5, 149–190 (1996) · Zbl 0870.65047
[72] Li D., Fukushima M.: Smoothing Newton and quasi-Newton methods for mixed complementarity problems. Comput. Optim. Appl. 17, 203–230 (2000) · Zbl 1168.90623
[73] Lin G.H., Chen X., Fukushima M.: Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization. Math. Program. 116, 343–368 (2009) · Zbl 1168.90008
[74] Lin G.H., Fukushima M.: Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: a survey. Pac. J. Optim. 6, 455–482 (2010) · Zbl 1200.65052
[75] Luo Z-Q., Pang J-S., Ralph D., Wu S.: Exact penalization and stationarity conditions of mathematical programs with equilibrium constraints. Math. Program. 75, 19–76 (1996) · Zbl 0870.90092
[76] Maréchal P., Ye J.J.: Optimizing condition numbers. SIAM J. Optim. 20, 935–947 (2009) · Zbl 1198.90328
[77] Martínez J.M., Moretti A.C.: A trust region method for minimization of nonsmooth functions with linear constraints. Math. Program. 76, 431–449 (1997) · Zbl 0871.90088
[78] Meng K., Yang X.: Optimality conditions via exact penalty functions. SIAM J. Optim. 20, 3205–3231 (2010) · Zbl 1229.90202
[79] Mifflin R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977) · Zbl 0376.90081
[80] Mordukhovich B.S.: Variational Analysis and Generalized Differentiation I and II. Springer, Berlin (2006)
[81] Nesterov Y.: Smooth minimization of nonsmooth functions. Math. Program. 103, 127–152 (2005) · Zbl 1079.90102
[82] Nesterov Y.: Smoothing technique and its applications in semidefinite optimization. Math. Program. 110, 245–259 (2007) · Zbl 1126.90058
[83] Newey, W.K., McFadden, D.: Large sample estimation and hypothesis testing. In: Handbook of econometrics, vol. IV, pp. 2111–2245. North-Holland, Amsterdam (1994)
[84] Nikolova M.: Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares. SIAM J. Multiscale Model. Simul. 4, 960–991 (2005) · Zbl 1091.94007
[85] Nikolova M., Ng M.K., Zhang S., Ching W.: Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 1, 2–25 (2008) · Zbl 1207.94017
[86] Nocedal J., Wright S.J.: Numerical Optimization. 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[87] Osborne M.R.: Finite Algorithms in Optimizations in Optimization and Data Analysis. Wiley, Chichester (1985) · Zbl 0573.65044
[88] Polyak R.A.: A nonlinear rescaling vs. smoothing technique in convex optimization. Math. Program. 92, 197–235 (2002) · Zbl 1022.90014
[89] Qi H.D., Liao L.Z.: A smoothing Newton method for extended vertical linear complementarity problems. SIAM J. Matrix Anal. Appl. 21, 45–66 (1999) · Zbl 1017.90114
[90] Qi L., Chen X.: A globally convergent successive approximation method for severely nonsmooth equations. SIAM J. Control Optim. 33, 402–418 (1995) · Zbl 0833.90109
[91] Qi L., Ling C., Tong X., Zhou G.: A smoothing projected Newton-type algorithm for semi-infinite programming. Comput. Optim. Appl. 42, 1–30 (2009) · Zbl 1153.90556
[92] Qi L., Sun D., Zhou G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87, 1–35 (2000) · Zbl 0989.90124
[93] Rockafellar R.T.: A property of piecewise smooth functions. Comput. Optim. Appl. 25, 247–250 (2003) · Zbl 1042.90045
[94] Rockafellar R.T., Wets R.J-B.: Variational Analysis. Springer, New York (1998)
[95] Ruszczynski A., Shapiro A.: Stochastic Programming, Handbooks in Operations Research and Management Science. Elsevier, Amsterdam (2003)
[96] Smale, S.: Algorithms for solving equations. In: Proceedings of the International Congress of Mathematicians, Berkeley, CA, pp. 172–195 (1986)
[97] Sun J., Sun D., Qi L.: A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems. SIAM J. Optim. 14, 783–806 (2004) · Zbl 1079.90094
[98] Tassa, Y., Todorov, E.: Stochastic complementarity for local control of discontinuous dynamics. In: Proceedings of Robotics: Science and Systems (RSS) (2010)
[99] Wright S.J.: Convergence of an inexact algorithm for composite nonsmooth optimization. IMA J. Numer. Anal. 9, 299–321 (1990) · Zbl 0705.65041
[100] Xu H.: Sample average approximation methods for a class of stochastic variational inequality problems. Asia Pac. J. Oper. Res. 27, 103–119 (2010) · Zbl 1186.90083
[101] Xu Z., Zhang H., Wang Y., Chang X.: L 1/2 regularizer. Sci. China Ser. F-Inf Sci. 53, 1159–1169 (2010)
[102] Yuan Y.: Conditions for convergence of a trust-region method for nonsmooth optimization. Math. Program. 31, 220–228 (1985) · Zbl 0576.90080
[103] Zang I.: A smoothing-out technique for min-max optimization. Math. Program. 19, 61–71 (1980) · Zbl 0468.90064
[104] Zhang C., Chen X.: Smoothing projected gradient method and its application to stochastic linear complementarity problems. SIAM J. Optim. 20, 627–649 (2009) · Zbl 1204.65073
[105] Zhang C., Chen X., Sumalee A.: Wardrop’s user equilibrium assignment under stochastic environment. Transp. Res. B 45, 534–552 (2011)
[106] Zhang C.-H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38, 894–942 (2010) · Zbl 1183.62120
[107] Zhou G.L., Caccetta L., Teo K.L: A superlinearly convergent method for a class of complementarity problems with non-Lipschitzian functions. SIAM J. Optim. 20, 1811–1827 (2010) · Zbl 1206.90197
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.