×

Stadium norm and Douglas-Rachford splitting: a new approach to road design optimization. (English) Zbl 1338.90381

Summary: The basic optimization problem of road design is quite challenging due to an objective function that is the sum of nonsmooth functions and the presence of set constraints. In this paper, we model and solve this problem by employing the Douglas-Rachford splitting algorithm. This requires a careful study of new proximity operators related to minimizing area and to the stadium norm. We compare our algorithm to a state-of-the-art projection algorithm. Our numerical results illustrate the potential of this algorithm to significantly reduce cost in road design.

MSC:

90C30 Nonlinear programming

Software:

UNLocBoX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bauschke HH, Borwein JM (1996) On projection algorithms for solving convex feasibility problemsSIAM Rev. 38:367-426. CrossRef · Zbl 0865.47039
[2] Bauschke HH, Combettes PL (2011) Convex Analysis and Monotone Operator Theory in Hilbert Spaces (Springer, New York). CrossRef
[3] Bauschke HH, Koch VR (2015) Projection methods: Swiss Army knives for solving feasibility and best approximation problems with halfspaces. Reich S, Zaslavski A, eds. Proc. Workshop Infinite Products of Operators and Their Applications (American Mathematical Society, Providence, RI), 1-40. CrossRef · Zbl 1325.65080
[4] Bauschke HH, Iorio F, Koch VR (2004) The method of cyclic intrepid projections: Convergence analysis and numerical experiments. Wakayama M, Anderssen RS, Cheng J, Fukumoto Y, McKibbin R, Polthier K, Takagi T, Toh K-C, eds. The Impact of Applications on Mathematics, Proceedings of the Forum of Mathematics for Industry 2013 (Springer, Tokyo), 187-200.
[5] Bauschke HH, Lucet Y, Phan HM (2015) On the convexity of piecewise-defined functions. ESAIM: Control, Optim. Calculus of Variations. ePub ahead of print, April 14, http://dx.doi.org/10.1051/cocv/2015023.
[6] Boţ RI, Csetnek ER, Heinrich A (2013) A primal-dual splitting algorithm for finding zeros of sums of maximally monotone operators. SIAM J. Optim. 23:2011-2036. CrossRef · Zbl 1314.47102
[7] Briceño-Arias LM, Combettes PL (2011) A monotone + skew splitting model for composite monotone inclusions in duality. SIAM J. Optim. 21:1230-1250. CrossRef · Zbl 1239.47053
[8] Cegielski A (2012) Iterative Methods for Fixed Point Problems in Hilbert Spaces (Springer, Berlin).
[9] Censor Y, Zenios SA (1997) Parallel Optimization (Oxford University Press, Oxford, UK).
[10] Combettes PL (1997) Hilbertian convex feasibility problems: Convergence of projection methods. Appl. Math. Optim. 35:311-330. CrossRef · Zbl 0872.90069
[11] Combettes PL, Pesquet J-C (2011) Proximal splitting methods in signal processing. Bauschke HH, Burachik RS, Combettes PL, Elser V, Luke DR, Wolkowicz H, eds. Fixed-Point Algorithms for Inverse Problems in Science and Engineering (Springer, New York),185-212. CrossRef
[12] Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming (Ser. A) 91:201-213. CrossRef · Zbl 1049.90004
[13] Douglas J, Rachford HH (1956) On the numerical solution of heat conduction problems in two and three space variables. Trans. AMS 82:421-439. CrossRef · Zbl 0070.35401
[14] Herman GT (1975) A relaxation method for reconstructing objects from noisy x-rays. Math. Programming 8:1-19. CrossRef · Zbl 0298.65028
[15] Lions P-L, Mercier B (1979) Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16:964-970. CrossRef · Zbl 0426.65050
[16] Moreau J-J (1965) Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France 93:273-299. · Zbl 0136.12101
[17] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ). CrossRef
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.