Abstract
In many engineering applications, it is necessary to minimize smooth functions plus penalty (or regularization) terms that violate smoothness and convexity. Specific algorithms for this type of problems are available in recent literature. Here, a smooth reformulation is analyzed and equivalence with the original problem is proved both from the points of view of global and local optimization. Moreover, for the cases in which the objective function is much more expensive than the constraints, model-intensive algorithms, accompanied by their convergence and complexity theories, are introduced. Finally, numerical experiments are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andreani, R., Birgin, E.G., Martínez, M.J., Schuverdt, M.L.: On augmented Lagrangian methods with general lower-level constraints. SIAM J. Optim. 18, 1286–1309 (2008)
Andreani, R., Haeser, G., Martínez, M.J.: On sequential optimality conditions for smooth constrained optimization. Optimization 60, 627–641 (2011)
Bertsekas, D.P.: Nonlinear programming, Athenas Scientific (1999)
Bian, W., Chen, X.: From sparse solutions of systems of equations to sparse modeling of signals and image. SIAM Rev. 51, 34–81 (2009)
Bian, W., Chen, X.: Linearly constrained non Lipschitz optimization for image restoration. SIAM J. Imaging Sci. 8, 2294–2322 (2015)
Bian, W., Chen, X., Ye, Y.: Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Program. 149, 301–327 (2015)
Birgin, E.G., Martínez, M.J.: Practical augmented Lagrangian methods for constrained optimization society for industrial and applied mathematics, Philadelphia (2014)
Birgin E.G., Martínez, M.J.: Complexity and performance of an augmented Lagrangian algorithm, Optimization Methods and Software, to appear. https://doi.org/10.1080/10556788.2020.1746962
Birgin, E.G., Gardenghi, J.L., Martínez, M.J., Santos, S.A.: On the use of third-order models with fourth-order regularization for unconstrained optimization, Optimization Letters, to appear. https://doi.org/10.1007/s11590-019-01395-z
Birgin, E.G., Gardenghi, J.L., Martínez, M.J., Santos, S.A., Toint, P.L.: Worst-case evaluation complexity for unconstrained nonlinear optimization using higher order regularized models. Math. Progr. 163, 359–368 (2017)
Birgin, E.G., Martínez, M.J.: On regularization and active-set methods with complexity for constrained optimization. SIAM J. Optim. 28, 1367–1395 (2018)
Browne, S.: The risk and rewards of minimizing shortfall probability. J. Portf. Manag. 25, 76–85 (1999)
Candes, E., Wakin, M., Boyd, S.: Enhancing sparsity by reweighted L1 minimization. J. Fourier Anal. Appl. 14, 877–905 (2008)
Cartis, C., Gould, N.I.M., Toint, P.h.L.: Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization. Found. Comput. Math. 18, 1073–1107 (2018)
Chen, X., Guo, L., Lu, Z., Ye, J.: An augmented Lagrangian method for non-Lipschitz nonconvex programming. SIAM J. Numer. Anal. 55, 168–193 (2017)
Chen, X., Niu, L., Yuan, Y.: Optimality conditions and a smoothing trust region Newton method for non-Lipschitz optimization. SIAM J. Optim. 23, 1528–1552 (2013)
Chen, X., Zhou, W.: Convergence of the reweighted L1 minimization algorithm for L2-Lp minimization. Comput. Optim. Appl. 59, 47–61 (2014)
Cortes, C., Vapnik, V.: Support vector networks. Mach. Learn. 20, 273–297 (1995)
Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96, 1348–1360 (2001)
Fang, J., Peng, H.: Nonconcave penalized likelihood with a diverging number of parameters. Ann. Stat. 32, 928–961 (2004)
Frank, L.E., Friedman, J.H.: A statistical view of some chemometrics regression tools. Technometrics 35, 109–135 (1993)
Haeser, G., Liu, H., Ye, Y.: Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary, Mathematical Programming, to appear. https://doi.org/10.1007/s10107-018-1290-4
Lai, M., Wang, J.: An unconstrained Lq minimization with 0 < q ≤ 1 for sparse solution of underdetermined linear systems. SIAM J. Optim. 21, 82–101 (2010)
Liu, Y.F., Ma, S., Dai, Y.H., Zhang, S.: A smoothing SQP framework for a class of composite Lq minimization over polyhedron. Math. Program. 158, 467–500 (2016)
Lu, Z.: Iterative reweighted minimization methods for Lp regularized unconstrained nonlinear programming. Math. Program. 147, 277–307 (2014)
Martínez, M.J.: On high-order model regularization for constrained optimization. SIAM J. Optim. 27, 2447–2458 (2017)
Moré, J.J., Garbow, B.S., Hillstrom, K. E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981)
Nikolova, M., Ng, M.K., Zhang, S., Ching, W.K.: Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J. Imaging Sci. 1, 2–25 (2008)
Nocedal, J., Wright, S.J.: Numerical optimization. Springer-Verlag, New York (2006)
Vogel, C.R.: Computational methods for inverse problems, Society for industrial and applied mathematics, Philadelphia (2002)
Zhang, C.H.: Nearly unbiased variable selection under minimax nonconcave penalty. Ann. Stat. 38, 894–942 (2010)
Funding
This work was supported by FAPESP (grants 2013/07375-0, 2016/01860-1, and 2018/24293-0) and CNPq (grants 438185/2018-8, 302538/2019-4, and 302682/2019-8).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Birgin, E.G., Martínez, J.M. & Ramos, A. On constrained optimization with nonconvex regularization. Numer Algor 86, 1165–1188 (2021). https://doi.org/10.1007/s11075-020-00928-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-020-00928-3