Geodesic
Methods of nonsmooth analysis in application to the problem of minimizing the sum of affine functions' modules
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 168-185 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

An application of constructive nonsmooth analysis methods to the problem of minimizing a convex piecewise affine function defined as the sum of absolute values of affine functions is demonstrated. Hypodifferential calculus was used in the general (multidimensional) case, while subdifferential calculus was employed in the scalar case. Analyzing the optimality criterion, one can reveal that the point delivering the global minimum can be found by solving the corresponding linear programming problem. In the scalar case, the solution can also be found in closed form as the weighted median of the nodes of a broken line. Bibliogr. 30.
Keywords: piecewise affine function, broken line, least absolute values, subdifferential, hypodifferential, weighted median. 
@article{DA_2024_31_4_a8,
     author = {G. Sh. Tamasyan and G. S. Shulga},
     title = {Methods of nonsmooth analysis in~application~to~the~problem of minimizing the~sum~of~affine functions' modules},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {168--185},
     year = {2024},
     volume = {31},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_4_a8/}
}
TY  - JOUR
AU  - G. Sh. Tamasyan
AU  - G. S. Shulga
TI  - Methods of nonsmooth analysis in application to the problem of minimizing the sum of affine functions' modules
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 168
EP  - 185
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_4_a8/
LA  - ru
ID  - DA_2024_31_4_a8
ER  - 
%0 Journal Article
%A G. Sh. Tamasyan
%A G. S. Shulga
%T Methods of nonsmooth analysis in application to the problem of minimizing the sum of affine functions' modules
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 168-185
%V 31
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2024_31_4_a8/
%G ru
%F DA_2024_31_4_a8
G. Sh. Tamasyan; G. S. Shulga. Methods of nonsmooth analysis in application to the problem of minimizing the sum of affine functions' modules. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 168-185. http://geodesic.mathdoc.fr/item/DA_2024_31_4_a8/

[1] V. I. Mudrov and V. L. Kushko, Methods of Processing Measurements: Quasiplausible Estimates, Radio Svyaz', M., 1983 (In Russian)

[2] S. I. Zukhovitskii, “On the approximation of an incompatible system of linear equations using the principle of minimizing the sum of the moduli of all deviations”, Dokl. Akad. Nauk SSSR, 143:5 (1962), 1030–1033

[3] P. A. Akimov and A. I. Matasov, “An iterative algorithm for $l_1$-norm approximation in dynamic estimation problems”, Autom. Remote Control, 76:5 (2015), 733–748 | DOI | MR

[4] A. V. Lakeev and S. I. Noskov, “The method of least moduli for linear regression: The number of zero approximation errors”, Sovrem. Tekhnol., Sist. Anal., Model., 2012, no. 2, 48–50 (In Russian)

[5] V. A. Gorelik and O. S. Trembacheva, “Solution of the linear regression problem using matrix correction methods in the $l_1$-metric”, Comput. Math. Math. Phys., 56:2 (2016), 200–205 | DOI | DOI | MR

[6] V. A. Surin and A. N. Tyrsin, “Application of the generalized method of least moduli in problems of image processing and analysis”, Vestn. Astrakhan. Gos. Tekhn. Univ., Ser. Upr. Vychisl. Tekhn. Inform., 2020, no. 2, 45–55 (In Russian) | DOI

[7] G. Sh. Tamasyan, “On wild points”, Sel. Talks Semin. Optimization, Machine Learning and Artificial Intelligence, St. Petersb. Gos. Univ., St. Petersburg, 2023 (In Russian) (accessed: Oct. 27, 2024) http://oml.cmlaboratory.com/reps23.shtml

[8] S. P. Sharyi, “Strong consistency in the problem of dependence recovery under interval data uncertainty”, Vychisl. Tekhnol., 22:2 (2017), 150–172 (In Russian)

[9] S. P. Sharyi and I. A. Sharaya, “Recognition of solvability of interval equations and its applications to data analysis”, Vychisl. Tekhnol., 18:3 (2013), 80–109 (In Russian)

[10] I. I. Eremin, “The “penalty” method in convex programming”, Dokl. Akad. Nauk SSSR, 173:4 (1967), 748–751 (In Russian)

[11] M. V. Dolgopolik, “Fundamentals of the theory of exact penalty functions”, Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization, St. Petersb. Gos. Univ., St. Petersburg, 2015 (In Russian) (accessed: Oct. 27, 2024) http://cnsa.cmlaboratory.com/reps15.shtml

[12] L. N. Polyakova, “The Method of exact penalties: Another approach”, Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization, St. Petersb. Gos. Univ., St. Petersburg, 2014 (In Russian) (accessed: Oct. 27, 2024) http://cnsa.cmlaboratory.com/reps14.shtml

[13] V. F. Demyanov and V. N. Malozyomov, Introduction to Minimax, Nauka, M., 1972 (In Russian) | MR

[14] V. F. Demyanov and L. V. Vasilyev, Nondifferentiable Optimization, Nauka, M., 1981 (In Russian) | MR

[15] V. F. Demyanov and A. M. Rubinov, Fundamentals of Nonsmooth Analysis and Quasidifferential Calculus, Nauka, M., 1990 (In Russian)

[16] L. N. Polyakova, “Continuous methods for unconditional minimization of hypodifferentiable functions”, Vestn. St. Petersb. Univ., Ser. 10, 2007, no. 3, 71–81 (In Russian)

[17] M. V. Dolgopolik, “On continuous codifferentiability”, Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization, St. Petersb. Gos. Univ., St. Petersburg, 2019 (In Russian) (accessed: Oct. 27, 2024) http://cnsa.cmlaboratory.com/reps19.shtml

[18] V. A. Zalgaller, “Representation of functions of several variables by differences of convex functions”, J. Math. Sci., New York, 100:3 (2000), 2209–2227 | DOI | MR

[19] Melzer D., “On the expressibility of piecewise linear continuous functions as the difference of two piecewise linear convex functions”, Quasidifferential calculus, Math. Program. Stud., 29, North-Holland, Amsterdam, 1986, 118–134 | DOI | MR

[20] Kripfganz A., Schulze R., “Piecewise affine functions as a difference of two convex functions”, Optimization, 18:1 (1987), 23–29 | DOI | MR

[21] Gorokhovik V. V., Zorko O. I., Birkhoff G., “Piecewise affine functions and polyhedral sets”, Optimization, 31:3 (1994), 209–221 | DOI | MR

[22] Gorokhovik V. V., Geometrical and analytical characteristic properties of piecewise affine mappings, Cornell Univ., Ithaca, NY, 2011, 12 pp., arXiv: 1111.1389 | DOI

[23] T. A. Angelov, “Representation of piecewise affine functions as a difference of polyhedral ones”, Vestn. St. Petersb. Univ., Ser. 10, 2016, no. 1, 4–18 (In Russian)

[24] G. Sh. Tamasyan, “On a compact representation of the codifferential of a continuous broken line given in the Bernstein form”, Sel. Talks Semin. Optimization, Machine Learning and Artificial Intelligence, St. Petersb. Gos. Univ., St. Petersburg, 2023 (In Russian) (accessed: Oct. 27, 2024) http://oml.cmlaboratory.com/reps23.shtml

[25] M. K. Gavurin and V. N. Malozyomov, Extremum Problems with Linear Constraints, Izd. LGU, Leningrad, 1984 (In Russian)

[26] F. P. Vasilyev and A. Yu. Ivanitskii, Linear Programming, MTsNMO, M., 2020 (In Russian)

[27] G. Sh. Tamasyan and G. S. Shulga, “To the question of minimization of a convex piecewise affine function”, Sel. Talks Semin. Optimization, Machine Learning and Artificial Intelligence, St. Petersb. Gos. Univ., St. Petersburg, 2022 (In Russian) (accessed: Oct. 27, 2024) http://oml.cmlaboratory.com/reps22.shtml

[28] A. S. Malistov, “On finding the median of an array in linear time”, Mat. Prosveshch., Ser. 3, 21, MTsNMO, M., 2017, 265–270 (In Russian)

[29] G. Sh. Tamasyan and G. S. Shulga, “Fast algorithm for minimizing a convex broken line”, Sel. Talks Semin. Constructive Nonsmooth Analysis and Nondifferentiable Optimization, St. Petersb. Gos. Univ., St. Petersburg, 2021 (In Russian) (accessed: Oct. 27, 2024) http://cnsa.cmlaboratory.com/reps21.shtml

[30] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, MA, 2009 | MR