×

zbMATH — the first resource for mathematics

Computing B-stationary points of nonsmooth DC programs. (English) Zbl 1359.90106
Summary: Motivated by a class of applied problems arising from physical layer based security in a digital communication system, in particular, by a secrecy sum-rate maximization problem, this paper studies a nonsmooth, difference-of-convex (dc) minimization problem. The contributions of this paper are (i) clarify several kinds of stationary solutions and their relations; (ii) develop and establish the convergence of a novel algorithm for computing a d-stationary solution of a problem with a convex feasible set that is arguably the sharpest kind among the various stationary solutions; (iii) extend the algorithm in several directions including a randomized choice of the subproblems that could help the practical convergence of the algorithm, a distributed penalty approach for problems whose objective functions are sums of dc functions, and problems with a specially structured (nonconvex) dc constraint. For the latter class of problems, a pointwise Slater constraint qualification is introduced that facilitates the verification and computation of a B(ouligand)-stationary point.

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90B18 Communication networks in operations research
Software:
OPECgen
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alvarado A (2014) Centralized and distributed resource allocation with applications to signal processing in communications. Ph.D. thesis, Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign.
[2] Alvarado A, Scutari G, Pang J-S (2014) A new decomposition method for multiuser DC-programming and its applications. IEEE Trans. Signal Processing 62(11):2984-2998. CrossRef · Zbl 1393.90091
[3] Attouch H, Bolte J, Svaiter B (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Programming 137(1):91-129. CrossRef · Zbl 1260.49048
[4] Bai L, Mitchell JE, Pang J-S (2013) On convex quadratic programs with linear complementarity constraints. Comput. Optim. Appl. 54(3):517-554. CrossRef · Zbl 1295.90035
[5] Bai L, Mitchell JE, Pang J-S (2016) On QPCCs, QCQPs and completely positive programs. Math. Programming, Ser. A 159(1):109-136. CrossRef · Zbl 1346.90624
[6] Bačák M, Borwein JM (2011) On difference convexity of locally lipschitz functions. Optim.: J. Math. Programming Oper. Res. 60(8-9):961-978.
[7] Bolte J, Shoham S, Teboulle M (2013) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming 146(1):1-36. · Zbl 1297.90125
[8] Clarke FH (1987) Optimization and Nonsmooth Analysis, Classics Series in Applied Mathematics, Book 5 (SIAM, Philadelphia) [Originally published by John Wiley & Sons, New York 1983].
[9] Facchinei F, Pang J-S (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, Vols. I and II (Springer-Verlag, New York). · Zbl 1062.90002
[10] Facchinei F, Sagratella S, Scutari G (2013) Flexible parallel algorithms for big data optimization. Preprint, arXiv:1311.2444. · Zbl 1394.94174
[11] Hiriart-Urruty JB (1985) Generalized differentiability, duality and optimization for problems dealing with differences of convex functions. Ponstein J, ed. Convexity and Duality Optim. (Springer, Berlin), 37-70. CrossRef
[12] Hong M, Chang TH, Wang X, Razaviyayn M, Ma S, Luo Z-Q (2013) A block successive upper bound minimization method of multipliers for linearly constrained convex optimization. Preprint, arXiv:1401.7079.
[13] Horst R, Thoai NV (1999) D.C. programming: Overview. J. Optim. Theory Appl. 103(1):1-43. CrossRef
[14] Jiang H, Ralph D (1999) QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints. Comput. Optim. Appl. 13(1):25-59. CrossRef · Zbl 1040.90500
[15] Jorswieck E, Wolf A, Gerbracht S (2010) Secrecy on the physical layer in wireless networks. Bouras CJ, ed. Trends in Telecommunications Technologies (INTECH, Rijeka, Croatia), 413-435.
[16] Kruskal J (1969) Two convex counterexamples: A discontinuous envelope function and a nondifferentiable nearest-point mapping. Proc. Amer. Math. Soc. 23(3):697-703. CrossRef · Zbl 0184.47401
[17] Le Thi HA, Pham DT (2005) The DC programming and DCA revised with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133:25-46. · Zbl 1116.90122
[18] Le Thi HA, Pham DT (2011) On solving linear complemetarity problems by DC programming and DCA. Comput. Optim. Appl. 50(3):507-524. CrossRef · Zbl 1237.90234
[19] Le Thi HA, Pham DT (2013) The state of the art in DC programming and DCA. Technical report, Lorraine University, Nancy, France.
[20] Le Thi HA, Pham DT (2014a) DC programming in communication systems: Challenging problems and methods. Vietnam J. Comput. Sci. 1(1):15-28. CrossRef
[21] Le Thi HA, Pham DT (2014b) Recent advances in DC programming and DCA. Nguyen N-T, Le Thi HA, eds. Trans. Comput. Collective IntelligenceLecture Notes in Computer Science, Vol. 8342 (Springer, Berlin), 1-37.
[22] Le Thi HA, Huynh VN, Pham DT (2014) DC programming and DCA for general DC programs. Do TV, Le Thi HA, Nguyen NT, eds. Advanced Comput. Methods for Knowledge Engineering. Chap. (Springer, Cham, Switzerland), 15-35. CrossRef · Zbl 1322.90072
[23] Le Thi HA, Pham DT, Huynh VN (2012) Exact penalty and error bounds in DC programming. J. Global Optim. 52(3):509-535. CrossRef · Zbl 1242.49037
[24] Le Thi HA, Pham DT, Le DM (1999) Exact penalty in d.c. programming. Vietnam J. Math. 27(2):169-178.
[25] Luo ZQ, Pang J-S, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK). CrossRef
[26] Maingé JE, Moudafi A (2006) On the convergence of an approximate proximal method for DC functions. J. Comput. Math. 24(4):475-480. · Zbl 1104.65058
[27] Maingé JE, Moudafi A (2008) Convergence of new inertial proximal methods for DC programming. SIAM J. Optim. 19(1):397-413. CrossRef · Zbl 1158.49034
[28] Moudafi A (2008) On the difference of two maximal monotone operators: Regularization and algorithmic approaches. Appl. Math. Comput. 202(2):446-452. CrossRef · Zbl 1181.65083
[29] Pang J-S (2007) Partially B-regular optimization and equilibrium problems. Math. Oper. Res. 32(3):687-699. Link · Zbl 1341.90145
[30] Pang J-S, Fukushima M (1999) Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints. Comput. Optim. Appl. 13(1):111-136. CrossRef · Zbl 1040.90560
[31] Pang J-S, Razaviyayn M (2016) Big Data Over Networks, Chap. A Unified Distributed Algorithm for Non-Cooperative Games with Non-Convex and Non-Differentiable Objectives (Cambridge University Press, Cambridge, UK), 101-134. CrossRef
[32] Pang J-S, Scutari G (2011) Nonconvex games with side constraints. SIAM J. Optim. 21(4):1491-1522. CrossRef · Zbl 1246.91022
[33] Pham DT, Le Thi HA (1997) Convex analysis approach to DC programming: Theory, algorithm and applications. Acta Mathematica Vietnamica 22(1):289-355.
[34] Qi L, Tseng P (2007) On piecewise smooth functions and almost smooth functions. Nonlinear Anal. 67(3):773-794. CrossRef · Zbl 1125.26019
[35] Razaviyayn M (2014) Successive convex approximation: Analysis and applications. Ph.D. thesis, Department of Electrical and Computer Engineering, University of Minnesota.
[36] Razaviyayn M, Hong M, Luo Z-Q (2013) A unified convergence analysis of block successive minimization methods for non-smooth optimization. SIAM J. Optim. 23(2):1126-1153. CrossRef · Zbl 1273.90123
[37] Razaviyayn M, Hong M, Luo Z-Q, Pang J-S (2014) Parallel successive convex approximation for nonsmooth nonconvex optimization. Adv. Neural Inform. Processing Systems 27 (NIPS 2014), 1440-1448.
[38] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ). CrossRef
[39] Sanjabi M, Razaviyayn M, Luo ZQ (2014) Optimal joint base station assignment and beamforming for heterogeneous networks. IEEE Trans. Signal Processing 62(8):1950-1961. CrossRef · Zbl 1394.94499
[40] Scheel H, Scholtes S (2000) Mathematical programs with equilibrium constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1):1-25. Link · Zbl 1073.90557
[41] Scholtes S (2004) Nonconvex structures in nonlinear programming. Oper. Res. 52(3):368-383. Link · Zbl 1165.90597
[42] Scutari G, Facchinei F, Lampariello L, Song P (2014a) Parallel and distributed methods for nonconvex optimization. Proc. IEEE Internat. Conf. Acoustics, Speech, and Signal Processing, ICASSP ’14 (IEEE, Piscataway, NJ), 840-844. CrossRef
[43] Scutari G, Facchinei F, Song P, Palomar DP, Pang J-S (2014b) Decomposition by partial linearization: Parallel optimization of multiuser systems. IEEE Trans. Signal Processing 62(3):641-656. CrossRef · Zbl 1394.94507
[44] Shapiro A (1994) Directionally nondifferentiable metric projection. J. Optim. Theory Appl. 81(1):203-204. CrossRef · Zbl 0807.90107
[45] Sriperumbudur BK, Lanckriet GRG (2012) A proof of convergence of the concave-convex procedure using Zangwill’s theory. Neural Comput. 24(6):1391-1407. CrossRef · Zbl 1254.90180
[46] Tuy H (1987) Global minimization of a difference of two convex functions. Math. Programming Stud. 30:150-187. CrossRef · Zbl 0619.90061
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.