Applications of the proximal difference-of-convex algorithm with extrapolation in optimal correction

Document Type : Research Article

Authors

Department of Applied Mathematics, Faculty of Mathematical Sciences University of Guilan, Rasht, Iran

Abstract

This paper proposes a proximal difference-of-convex algorithm with extrapolation ($PDCA_e$)  based on Dinkelbach's approach for the optimal correction of  two types of piecewise linear systems, classical obstacle problems and equilibrium problems, and linear inequalities. Using  Dinkelbach's theorem  leads  to getting  the roots of two single-variable functions. Considering the non-convex and level-bounded properties of the obtained problems, we use a proximal difference-of-convex algorithm programming to solve them. The experimental results on several randomly generated test problems show that the $PDCA_e$-generalized Newton method  outperforms other methods for both feasible and infeasible cases.

Keywords


[1] P. Amaral, P. Barahona, A framework for optimal correction of inconsistent linear constraints,
Constraints 10 (2005) 67–86.
[2] M.-S. Bazaraa, H.-D. Sherali, C.-M. Shetty, Nonlinear programming: theory and algorithms, John
Wiley and Sons, 2013.
[3] L. Brugnano, A. Sestini, Iterative solution of piecewise linear systems for the numerical solution
of obstacle problems, arXiv preprint: https://arxiv.org/abs/0912.3222.
[4] L. Brugnano, V. Casulli, Iterative solution of piecewise linear systems, SIAM J. Sci. Comput. 30
(2008) 463–472.
[5] D. Carp, C. Popa, C. Serban, Iterative solution of inconsistent systems of linear inequalities,
PAMM 13 (2013) 407–408.
[6] C. Chen, D. Yu, D. Han, Exact and inexact DouglasRachford splitting methods for solving large-
scale sparse absolute value equations, IMA J. Nume. Anal. 43 (2023) 1036–1060.
[7] J.P. Crouzeix, J.A. Ferland, Algorithms for generalized fractional programming, Math. Program.
52 (1991) 191–207.
[8] W. Dinkelbach, On nonlinear fractional programming, Manage. Sci. 13 (1967) 492–498.
[9] E.-D. Dolan, J.-J. Mor, Benchmarking optimization software with performance profiles, Math. Pro-
gram. 91 (2002) 201–213.
[10] J.-Y. Gotoh, A. Takeda, K. Tono, DC formulations and algorithms for sparse optimization prob-
lems, Math. Program. 169 (2018) 141–176.
[11] F. Hashemi, S. Ketabchi, Numerical comparisons of smoothing functions for optimal correction of
an infeasible system of absolute value equations, Numer. Algebra, Control. Optim. 10 (2020) 13.
[12] F. Hashemi, S. Ketabchi, lp Norm regularization method (0 < p < 1) and DC Programming for
correction system of inconsistency linear inequalities, Bull. Iran. Math. Soc. 45 (2019) 865–882.
[13] C. Kanzow, H. Qi, L. Qi, On the minimum norm solution of linear programs, J. Optim. Theory
Appl. 116 (2003) 333–345.
[14] A. Karppinen, M. Lee, H¨older continuity of the minimizer of an obstacle problem with generalized
Orlicz growth, arXiv preprint: https://arxiv.org/abs/2006.08244.
[15] S. Ketabchi, H. Moosaei, An efficient method for optimal correcting of absolute value equations
by minimal changes in the right hand side, Comput. Math. Appl. 64 (2012) 1882–1885.
[16] S. Ketabchi, H. Moosaei, S. Fallahi, 2013. Optimal error correction of the absolute value equation
using a genetic algorithm, Math. Comput. Model. 57 (2013) 2339–2342.
[17] S. Ketabchi, H. Moosaei, Minimum norm solution to the absolute value equation in the convex case,
J. Optim. Theory Appl. 154 (2012) 1080-1087.
[18] S. Ketabchi, H. Moosaei, Optimal error correction and methods of feasible directions, J. Optim.
Theory Appl. 154 (2012) 209–216.
[19] O.-L. Mangasarian, R.-R. Meyer, Absolute value equations, Linear Algebra Appl. 419 (2006) 359–
367.
[20] H. Moosaei, S. Ketabchi, M. Hladik, Optimal correction of the absolute value equations, J. Glob.
Optim. 79 (2021) 645–667.
[21] H. Moosaei, S. Ketabchi, P.-M. Pardalos, Tikhonov regularization for infeasible absolute value
equations, Optimization 65 (2016) 1531–1537.
[22] H. Moosaei, S. Ketabchi, Optimal correcting of absolute value equations by using smoothing tech-
niques, J. Interdiscip. Math. 22 (2019) 531–538.
[23] S. Nakayama, J.-Y. Gotoh, On the superiority of PGMs to PDCAs in nonsmooth nonconvex sparse
regression, Optim. Lett. 15 (2021) 28312860.
[24] N. Parikh, S. Boyd, Proximal algorithms, Found. Trends Syst. Control. 1 (2014) 127–239.
[25] C. Popa, C. Serban, Han-type algorithms for inconsistent systems of linear inequalitiesA unified
approach, Appl. Math. Comput. 246 (2014) 247–256.
[26] M. Radons, S.-M. Rump, Convergence results for some piecewise linear solvers, Optim. Lett. 16
(2022) 1663–1673.
[28] M. Salahi, S. Ketabchi, Correcting an inconsistent set of linear inequalities by the generalized
Newton method, Optim. Meth. Software 25 (2010) 457–465.
[29] S. Shahsavari, S. Ketabchi, The proximal methods for solving absolute value equation, Numer.
Algebra Control. Optim. 11 (2021) 449.
[30] G.-B. Thomas, R.-L. Finney, Calculus, Addison-Wesley Publishing Company, 1961.
[31] B. Wen, X. Chen, T.-K. Pong, A proximal difference-of-convex algorithm with extrapolation, Com-
put. Optim. Appl. 69 (2018) 297–324.
[32] L. Yang, L. Wang, A class of semi-supervised support vector machines by DC programming, Adv.
Data Anal. Classif. 7 (2013) 417–433.
[33] X.-T. Yuan, S. Yan, Nondegenerate piecewise linear systems: A finite newton algorithm and appli-
cations in machine learning, Neural Comput. 24 (2012) 1047–1084.