Representation of piecewise affine functions as a difference of polyhedral

T. A. Angelov

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 1 (2016), pp. 4-18

Résumé

The problem of representation of any analytic expression of a piecewise affine function as a sum of a convex and a concave polyhedral function, or an equivalent difference of two convex (d.c.) polyhedral functions, is observed. Two algorithms, solving this problem, are proposed. The first algorithm reconstructs a piecewise affine function using its codifferential mapping and the function’s value at a point. The second algorithm provides direct conversion of a piecewise affine function into a sum of a convex and a concave polyhedral functions. Refs 39. Figs 4.

Détail

Keywords: piecewise affine function, representation, d.c. functions, codifferential.

Bibliographie

[1] Shary S. P., “Solvability of Interval Linear Equations and Data Analysis under Uncertainty”, Automation and Remote Control, 73:2 (2012), 310–322 | DOI | MR | Zbl

[2] Shary S. P., “New characterizations for the solution set to interval linear systems of equations”, Applied Mathematics and Computation, 265 (2015), 570–573 | DOI | MR

[3] Vasin V. V., Korotkii M. A., “Tikhonov regularization with nondifferentiable stabilizing functionals”, Journal of Inverse and Ill-posed Problems, 15:8 (2007), 853–865 | DOI | MR | Zbl

[4] Velichko A. S., “Dual algorithm for regularization problems with nondifferentiable stabilizing functionals”, Computational Technologies, 19:2 (2014), 14–19 (In Russian)

[5] Tamasyan G. Sh., Chumakov A. A., “Finding the distance between the ellipsoids”, J. Appl. Ind. Math., 8:3 (2014), 400–410 | DOI | MR | Zbl

[6] Demyanov V. F., Giannessi F., Karelin V. V., “Optimal Control Problems via Exact Penalty Functions”, J. Global Optim., 12:3 (1998), 215–223 | DOI | MR | Zbl

[7] Filimonov N. B., “Polyhedral programming methods in discrete problems of control and observation”, Methods of classical and modern theory of automatic control, In 5 vol., v. 5, ch. 7, Bauman Moscow State Technical University Press, M., 2004, 647–720 (In Russian)

[8] Demenkov M. N., Filimonov N. B., “Variable Horizon Robust Predictive Control via Adjustable Controllability Sets”, European J. Control, 7:6 (2001), 596–604 | DOI | Zbl

[9] Demyanov V. F., Conditions of Extremum and Calculus of Variations, Vysshaja shkola Publ., M., 2005, 335 pp. (In Russian)

[10] Demyanov V. F., Tamasyan G. Sh., “On direct methods for solving variational problems”, Works of Institute of mathematics and mechanics UrB RAS, 16, no. 5 (2010), 36–47 (In Russian)

[11] Tamasyan G. Sh., “On Methods of Steepest and Hypodiffernetial Descent in one Problem of Calculus of Variations”, Comp. Methods and Comp. Sci., 13 (2012), 197–217 (In Russian) | MR

[12] Dolgopolik M. V., Tamasyan G. Sh., “On Equivalence of the Method of Steepest Descent and the Method of Hypodifferential Descent in Some Constrained Optimization Problems”, Izv. of Saratovsk. State University. New Series. Series Mathematics. Mechanics. Computer science, 14:4 (2014), 532–542 (In Russian) | Zbl

[13] Rockafellar R., Convex analysis, Prinston University Press, Prinston, 1970, 472 pp. | MR | Zbl

[14] Clarke F. H., “Generalized gradients and applications”, Trans. Amer. Math. Soc., 205 (1975), 247–262 | DOI | MR | Zbl

[15] Clarke F. H., Optimization and nonsmooth analysis, Wiley, New York, 1983, 308 pp. | MR | Zbl

[16] Shor N. Z., Minimization Methods for Non-differentiable Functions, Springer, Berlin, 1985, 162 pp. | MR | Zbl

[17] Tuy H., “D.c. optimization: theory, methods and algorithms”, Handbook of Global Optimization, eds. R. Horst, P. M. Pardalos, Kluwer, Dordrecht, 1995, 149–216 | DOI | MR | Zbl

[18] Hiriart-Urruty J. B., “From convex minimization to nonconvex minimization: necessary and sufficient conditions for global optimality”, Nonsmooth optimization and related topics, eds. F. N. Clarke, V. F. Demyanov, F. Gianessi, Plenum, New York, 1989, 219–240 | DOI | MR

[19] Strekalovsky A. S., Elements of nonconvex optimization, Nauka Publ., Novosibirsk, 2003, 356 pp. (In Russian)

[20] Strekalovsky A. S., “Global optimality conditions for nonconvex optimization”, J. Global Optim., 12:4 (1998), 415–434 | DOI | MR | Zbl

[21] Polyakova L. N., “On global unconstrained minimization of the difference of polyhedral functions”, J. Global Optim., 50 (2011), 179–195 | DOI | MR | Zbl

[22] Alexandrov A. D., “On surfaces which may be represented by a difference of convex functions”, Izv. of Acad. of Sciences of Kazakh. SSR. Series Physics and mathematics, 1949, no. 3, 3–20 (In Russian)

[23] Alexandrov A. D., “On surfaces which may be represented by difference of convex functions”, Proc. of Acad. of Sciences of USSR, 72:4 (1950), 513–616 (In Russian)

[24] Zalgaller V. A., “On the representation of functions of two variables as a difference of convex functions”, Vestnik of Leningrad University, 1963, no. 1, 44–45 (In Russian)

[25] Melzer D., “On the Expressibility of Piecewise-Linear Continuous Functions as the Difference of two Piecewise-Linear Convex Functions”, Math. Programming Study, 29 (1986), 118–134 | DOI | MR | Zbl

[26] Plotnikov S. V., Projection methods in nonlinear programming problems, Unpublished doctoral thesis, Ural State University, Sverdlovsk, 1983, 126 pp. (In Russian)

[27] Volokitin E. P., “On the representation of continuous piecewise affine functions”, Management systems, 19, Nauka Publ., Novosibirsk, 1979, 14–21 (In Russian) | Zbl

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

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

[30] Bartels S., Knutz L., Scholtes S., “Continous Selection of Linear Functions and Nonsmooth Critical Point Theory”, Nonlinear Analysis, Theory, Meth. Appl., 24 (1995), 385–407 | DOI | MR | Zbl

[31] Eremin I. I., “Some questions of piecewise linear programming”, Izv. Higher educational institutuions. Mathematics, 1997, no. 12, 49–61 (In Russian)

[32] Gratzer G., Lattice Theory: First Concepts and Distributive Lattices, Freeman, San Francisco, 1971, 212 pp. | MR | Zbl

[33] Demyanov V. F., Rubinov A. M., Foundations of Nonsmooth Analysis and Quasidifferential Calculus, Nauka Publ., M., 1990, 432 pp. (In Russian) | MR

[34] Preparata F. P., Shamos M. I., Computational Geometry: An Introduction, Springer, New York, 1985, 398 pp. | MR

[35] Malozemov V. N., “Some properties of the discrete maximum”, Seminar "CNSA $\$ NDO", Selected reports (14th May 2015) (In Russian) (accessed: 23.06.2015)

[36] Leichtveiss K., Convex Mengen, Springer, Berlin, 1980, 330 pp. | MR

[37] Andramonov M. Ju., Tamasyan G. Sh., “Implementation of analytical codifferentiation in MATLAB”, Calculation Methods and Programming, 8:1 (2007), 1–5 (In Russian)

[38] Angelov T. A., “On evaluation of codifferentials”, Calculation Methods and Programming, 14:1 (2013), 113–122 (In Russian)

[39] Pogorzelski H. A., “Reviewed work(s): Remarks on Nicod's Axiom and on “Generalizing Deduction” by Jan Lukasiewicz; Jerzy Slupecki; Panstwowe Wydawnictwo Naukowe”, The Journal of Symbolic Logic, 30:3 (1965), 376–377