1 Introduction
Optimization plays a key role in communication systems since most of issues of this domain are related to optimization problems. Convex programming has been studied for about a century. It has provided both a powerful tool and an intriguing mentality for the analysis and design of communication systems over several years in the past. During the last decade, an increasing amount of effort has been put into nonconvex optimization to deal with challenge problems appeared in many applications of this filed (in fact, most real-life problems are of nonconvex nature). The absence of convexity creates a source of difficulties of all kinds, in particular, the distinction between the local and global minima, the nonexistence of verifiable characterizations of global solutions, etc., that causes all the computational complexity while passing from convex to nonconvex programming. In general, unlike the convex programming, there is no iterative algorithm converging directly to a global solution of a nonconvex program. Finding a global solution of a nonconvex program, especially in the large-scale setting, is the holy grail of optimizers.
The special context of practical problems in CS, along with the dramatic progress of novel technologies, requires well-adapted optimization techniques. For example, solution methods to network management in the context of mobile service should take into account the following questions:Many challenging issues arise from nonconvex optimization in communication systems, especially how to design suitable models and develop efficient, fast, scalable and distributed algorithms to tackle large-scale practical problems in the areas of wireless networking, internet engineering, mobile services in self-organized hybrid networks.
-
The topology of networks is dynamic and real-time data transmissions are needed. Hence, real-time algorithms are expected.
-
Self-organization and self-configuration require all protocols in mobile networks to be distributive and collaborative. By the way, distributed algorithms are necessary.
-
Location/tracking management, in addition to the handover management and routing. In the case of hybrid communication networks, the choice of the best access gateway among a number of available access technologies becomes one of the important considerations. Routing in hybrid networks should be handled by finding a suitable mathematical model and efficient algorithms.
-
Multi-user communications service involves large scale setting optimization problems. Therefore, the algorithms should be able to solve large-size problems.
Anzeige
A variety of nonconvex optimization techniques have been recently developed by researchers in optimization on one side and in communications systems on another side for studying communication theory as well as for solving practical problems in CS (see e.g, [1‐9, 12, 14‐21, 24‐33, 38‐54]. Generally, there are two different, but complementary approaches: global approaches such as Cutting Plane (CP), Branch and Bound (B&B), Branch and Cut (B&C) can guarantee the globality of the solutions but they are very expensive, and cannot handle problems of high dimensionality; and local approaches, on the contrary, are much faster while only local minima are available. Many current approaches are not generally effective for practical large-scale problems. Finding efficient algorithms that realize a compromise to overcome these drawbacks is a challenge of nonconvex programming. Such algorithms must exploit domain-specific structures of the problems being considered.
As an innovative approach to nonconvex programming, Difference of Convex functions (DC) programming and DC Algorithms (DCA) are increasingly used by researchers in CS (see e.g. [1, 2, 16, 22, 45, 54] and references therein). The objective of this paper is to show that many challenging problems in CS can be modeled as DC programs and solved by DCA-based algorithms. We offer the community of researchers in CS promising approaches in a unified DC programming framework to tackle various applications such as routing, power control, congestion control of the Internet, resource allocation in networks, etc.
1.1 Nonconvex optimization problems in CS
In terms of optimization, nonconvex problems appeared in CS can be divided into three classes:The reader will see that these classes of nonconvex programs in CS can be formulated or reformulated as DC programs and solved by DCA.
-
minimizing a nonconvex function on a convex set;
-
minimizing a convex/nonconvex function on a nonconvex set;
-
minimizing a convex/nonconvex function on a convex/nonconvex set with integer variables.
1.2 Why DC programming and DCA?
DC programming is an extension of convex programming which is sufficiently large to cover almost all nonconvex optimization problems, but not much to still allow using the arsenal of powerful tools in convex analysis and convex optimization. DC programming and DCA constitute the backbone of nonconvex programming and global optimization. The use of DCA for solving nonconvex optimization problems in CS is motivated by the following facts:We will show how to solve these three classes of problems in CS by DC programming and DCA. For beginning, let us give in Sect. 2, a brief introduction of DCA programming and DCA. The solution methods of each class of problem will be presented in Sects. 3, 4, and 5 where, in addition to development of generic models and algorithms, methods for typical applications in CS will be illustrated. In Sect. 6, we mention another issue in CS for which DCA can also be investigated. Section 7 concludes the paper.
-
DCA is a philosophy rather than an algorithm. For each problem, we can design a family of DCA-based algorithms. The flexibility of DCA on the choice of DC decomposition offers DCA schemes having the potential to outperform standard methods.
-
By exploiting the nice effect of DC decomposition of the objective function we can build distributed algorithms. This issue is very important in communication networks that involve multi-users, in particular in the purpose of personalized mobile services.
-
Convex analysis provides powerful tools to prove the convergence of DCA in a generic framework. Hence, any DCA-based algorithm enjoys (at least) general convergence properties of the generic DCA scheme that are already available.
-
DCA is an efficient, fast and scalable method for smooth/nonsmooth nonconvex programming. To the best of our knowledge, DCA is actually one of the rare algorithms for nonsmooth nonconvex programming which allows to solve large-scale DC programs. DCA was successfully applied to a lot of different and various nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods. In particular, DCA has already efficiently solved large-scale DC programs in network optimization (see [1, 2, 24‐27, 29‐31, 45‐51, 54] and the list of references in [22] ).
Anzeige
2 DC programming and DCA
2.1 A brief introduction
We are working with the space \(X={\mathbb {R}}^{n}\) which is equipped with the canonical inner product \(\langle \cdot ,\cdot \rangle \) and the corresponding Euclidean norm \(\Vert \cdot \Vert \), thus the dual space \(Y\) of \(X\) can be identified with \(X\) itself. We follow [13, 37], for definitions of usual tools in modern convex analysis, where functions could take the infinite values \(+\infty .\) A function \(\theta :X\rightarrow \)\({\mathbb {R}}\cup \{+\infty \}\) is said to be proper if it is not identically equal to \(+\infty \). The effective domain of \(\theta \), denoted by dom \(\theta \), isThe indicator function \(\chi _{C}\) of a nonempty closed convex \(C\) set is defined by \(\chi _{C}(x)=0\) if \(x\in C,+\infty \) otherwise. The set of all lower semicontinuous proper convex functions on \(X\) is denoted by \(\Gamma _{0}(X).\) Let \(\theta \in \Gamma _{0}(X)\), then the conjugate function of \( \theta \), denoted \(\theta ^{*},\) is defined byWe have \(\theta ^{*}\in \Gamma _{0}(Y)\) and \(\theta ^{**}=\theta \).
$$\begin{aligned} \text{ dom } \theta =\{x\in X:\theta (x)<+\infty \}. \end{aligned}$$
$$\begin{aligned} \theta ^{*}(y)=\sup \{\langle x,y\rangle -\theta (x):\ x\in X\}. \end{aligned}$$
Nonsmooth convex functions are handled using the concept of subdifferentials. For \(\theta \in \)\(\Gamma _{0}(X)\) and \(x_{0}\in \) dom \( \theta ,\)\(\partial \theta (x_{0})\) denotes the subdifferential of \(\theta \) at \(x_{0},\) and is defined byEach \(y\in \partial \theta (x_{0})\) is called a subgradient of \(\theta \) at \( x_{0}.\) The subdifferential \(\partial \theta (x_{0})\) is a closed convex set in \(Y.\) It generalizes the derivative in the sense that \(\theta \) is differentiable at \(x_{0}\) if and only if \(\partial \theta (x_{0})\equiv \{\nabla \theta (x_{0})\}.\) Recall the well-known properties related to subdifferential calculus of \(\theta \in \Gamma _{0}(X)\):A function \(\theta \in \Gamma _{0}(X)\) is said to be polyhedral convex ifwhere \(C\) is a nonempty polyhedral convex set in \(X\).
$$\begin{aligned} \partial \theta (x_{0}){:=}\{y\in Y:\theta (x)\ge \theta (x_{0})+\langle x-x_{0},y\rangle ,\,\forall x\in X\}.\nonumber \\ \end{aligned}$$
(1)
$$\begin{aligned}&\!\!\!\!y_{0}\in \partial \theta (x_{0})\Leftrightarrow x_{0}\in \partial \theta ^{*}(y_{0}){\Leftrightarrow } \langle x_{0},y_{0}\rangle =\theta (x_{0})+\theta ^{*}(y_{0});\nonumber \\ \end{aligned}$$
(2)
$$\begin{aligned}&\partial \theta ^{*}(y_{0})={\mathrm{argmin}} \{\theta (x)-\langle x,y_{0}\rangle :x\in X\}. \end{aligned}$$
(3)
$$\begin{aligned} \theta (x)=\max \{\langle a_{i},x\rangle -\beta _{i}:i=1,\ldots ,m\}+\chi _{C}(x)\,\forall x\in X, \end{aligned}$$
A DC program is of the formwith \(g,h\,\in \Gamma _{0}\,(X).\) Such a function \(f\) is called a DC function, and \(g-h\), a DC decomposition of \(f\), while the convex functions \( g \) and \(h\) are DC components of \(f.\) In \((P_{\mathrm{dc}})\) the nonconvexity comes from the concavity of the function—\(h\) (except the case \(h\) is affine since \((P_{\mathrm{dc}})\) then is a convex program). It should be noted that a convex constrained DC program can be expressed in the form (4) by using the indicator function on \(C\), that isHence, throughout this paper, DC program of the form (4) is referred to as “standard DC program”.
$$\begin{aligned} (P_{\mathrm{dc}})\,\alpha =\inf \{f(x):=g(x)-h(x):\ x\in X\}, \end{aligned}$$
(4)
$$\begin{aligned} \inf \{f(x)&:= g(x)-h(x):\ x\in C\}\\&= \inf \{\varphi (x)-h(x)\ :\ x\in X\}, \text {with}\,\varphi :=g+\chi _{C}. \end{aligned}$$
Polyhedral DC programs \((P_{\mathrm{dc}})\) (i.e., when \(g\) or \(h\) are polyhedral convex) play a key role in nonconvex programming (see [25, 34, 35] and references therein), and enjoy interesting properties related to local optimality and DCA’s convergence.
The DC duality is based on the conjugate functions and the fundamental characterization of a convex function \(\theta \in \)\(\Gamma _{0}(X)\) as the pointwise supremum of a collection of affine minorants:That associates the primal DC program (4) \((P_{\mathrm{dc}})\) with its dual DC program \((D_{\mathrm{dc}})\) defined byand investigates their mutual relations. We observe the perfect symmetry between primal and dual DC programs: the dual to \((D_{\mathrm{dc}})\) is exactly \((P_{\mathrm{dc}}).\)
$$\begin{aligned} \theta (x)=\sup \{\langle x,y\rangle -\theta ^{*}(y):y\in Y\},\quad \quad \forall x\in X. \end{aligned}$$
(5)
$$\begin{aligned} (D_{\mathrm{dc}})\quad \alpha =\inf \{h^{*}(y)-g^{*}(y):y\in Y\}, \end{aligned}$$
(6)
It is worth noting the wealth of the vector space \({\mathrm{DC}}(X) = \Gamma _{0}(X)-\Gamma _{0}(X)\) spanned by the “convex cone” \(\Gamma _{0}(X)\) [34, 35]: it contains most realistic objective functions and is closed under operations usually considered in optimization.
The complexity of DC programs resides, of course, in the lack of verifiable globality conditions. Lets recall the general local optimality conditions in DC programming (subdifferential’s inclusion): if \(\ x^{*}\) is a local solution of \((P_{\mathrm{dc}})\) thenThe condition (7) is also sufficient (for local optimality) in many important classes of DC programs (see [34, 35]).
$$\begin{aligned} \emptyset \ne \partial h(x^{*})\subset \partial g(x^{*}). \end{aligned}$$
(7)
A point \(x^{*}\) is said to be a critical point of \(g\)—\(h\) (or generalized KKT point for \((P_{\mathrm{dc}})\)) ifNote that, by symmetry, the dual part of (7) and (8) are trivial.
$$\begin{aligned} \partial h(x^{*})\cap \partial g(x^{*})\ne \emptyset . \end{aligned}$$
(8)
DC Programming and DCA were introduced by Pham Dinh Tao in their preliminary form in 1985. These theoretical and algorithmic tools are extensively developed by Le Thi Hoai An and Pham Dinh Tao since 1994 to become now classic and increasingly popular. DCA is a continuous primal dual subgradient approach based on local optimality and duality in DC programming for solving standard DC programs \((P_{\mathrm{dc}}).\)
DCA’s philosophy
The key idea behind DCA is to replace in \((P_{\mathrm{dc}})\), at the current point \( x^{k}\), the second component \(h\) with its affine minorant defined byto give birth to the primal convex program of the formwhose solution set is \(\partial g^{*}(y^{k}).\)The next iterate \(x^{k+1}\) is taken in \(\partial g^{*}(y^{k}).\)
$$\begin{aligned} h_{k}(x):=h(x^{k})+\ \langle x-x^{k},y^{k}\rangle ,\,y^{k}\in \partial h(x^{k}) \end{aligned}$$
$$\begin{aligned}&(P_{k})\ \ \ \inf \{g(x)-h_{k}(x):\;x\in X\}\\&\Longleftrightarrow \inf \{g(x)-\langle x,y^{k}\rangle \;:x\in X\} \end{aligned}$$
Dually, a solution \(x^{k+1}\) of \((P_{k})\) is then used to define the dual convex program \((D_{k+1})\) obtained from \((D_{\mathrm{dc}})\) by replacing \(g^{*}\) with its affine minorantto obtain the convex programwhose solution set is \(\partial h(x^{k+1}).\) The next iterate \(y^{k+1}\) is chosen in \(\partial h(x^{k+1}).\)
$$\begin{aligned} (g^{*})_{k}(y):=g^{*}(y^{k})+\langle y-y^{k}x^{k+1}\rangle \end{aligned}$$
$$\begin{aligned}&\!\!\!(D_{k+1})\,\inf \{h^{*}(y)-[g^{*}(y^{k})+\langle y-y^{k},x^{k+1}\rangle ]:y\in Y\}\\&\!\Leftrightarrow \inf \{h^{*}(y)-\langle y,x^{k+1}\rangle \;:y\in Y\} \end{aligned}$$
DCA scheme
Initialization: Let \(x^{0}\in {\mathbb {R}}^{n} \) be a guess, \(k\leftarrow 0.\)
RepeatUntil convergence of \(\left\{ x^{k}\right\} .\)
-
Calculate \(\ y^{k}\in \partial h(x^{k})\)
-
Calculate \(x^{k+1}\in \partial g^{*}(y^{k})\), which is equivalent to$$\begin{aligned} x^{k+1}\in {\mathrm{argmin}} \{g(x)-\langle x,y^{k}\rangle :x\in {\mathbb {R}}^{n}\}\quad (P_{k}) \end{aligned}$$
-
\(k\leftarrow k+1\)
DCA’s convergence properties:
Convergence properties of DCA and its theoretical basis can be found in [25, 34, 35]. For instance, it is important to mention thatFor a complete study of DC programming and DCA, the reader is referred to [25, 34, 35] and the references therein. Without going into details, let us mention the key properties of DCA.
i)
DCA is a descent method without linesearch but with global convergence: the sequences \(\{g(x^{k})-h(x^{k})\}\) and \(\{h^{*}(y^{k})-g^{*}(y^{k})\}\) are decreasing.
ii)
If the optimal value \(\alpha \ \)of problem \((P_{\mathrm{dc}})\) is finite and the infinite sequences \(\{x^{k}\}\ \)and \(\{y^{k}\}\) are bounded, then every limit point \(x^{*}\ \)(resp. \(y^{*}\)) of the sequence \(\{x^{k}\}\) (resp. \(\{y^{k}\})\) is a critical point of \(g\)\(-\)\(h\) (resp. \(h^{*}-g^{*}\)), i.e. \(\partial h(x^{*})\cap \partial g(x^{*})\ne \emptyset \) (resp. \(\partial h^{*}(y^{*})\cap \partial g^{*}(y^{*})\ne \emptyset ).\)
iii)
DCA has a linear convergence for DC programs.
iv)
DCA has a finite convergence for polyhedral DC programs.
2.2 Key properties of DCA
a.
Flexibility the construction of DCA is based on \(g\) and \(h\) but not on \(f\) itself, and there are as many DCA as there are DC decompositions. This is a crucial fact in DC programming. It is important to study various equivalent DC forms of a DC program, because each DC function \( f\)has infinitely many DC decompositions which have crucial implications for the qualities (speed of convergence, robustness, efficiency, globality of computed solutions, etc.) of DCA.
b.
DCA is a descent method without linesearch, with global convergence (i.e. DCA converges from an arbitrary initial point).
c.
Return from DC programming to convex programming DCA consists in an iterative approximation of a DC program by a sequence of convex programs that will be solved by appropriate convex optimization algorithms. This property is called successive convex approximation (SCA) in some recent works in CS.
d.
Versatility With suitable DC decompositions DCA generates most standard algorithms in convex and nonconvex optimization. Hence DCA offers a wide framework for solving convex/nonconvex optimization problems. In particular, DCA is a global approach to convex programming, i.e., it converges to optimal solutions of convex programs reformulated as DC programs. Consequently, it can be used to build efficient customized algorithms for solving convex programs generated by DCA.
2.3 How to apply DCA for solving practical problems
It would be wrong to think that using DCA for solving a practical problem is a simple procedure. Indeed, the generic DCA scheme is an overall philosophical idea rather than a single algorithm. There is not only one DCA but a family of DCAs for a considered problem. While DC decompositions exist for a very large class of functions, there are no general procedure for determining such DC decompositions. The design of an efficient DCA for a concrete problem is an art which should be based on theoretical tools and on its special structure. It consists of the five steps :It goes without saying that the two steps (c) and (d) and solution methods for convex programs \((P_{k})\) (if necessary) constitute thekey issues for successful applications of DC programming and DCA.
a.
Find a DC formulation of the considered optimization problem: this can be done if the feasible domain \(C\) is a convex set and the objective function \(f\) is DC, otherwise we must use the approximation or reformulation technique based on relevant theoretical tools.
b.
Design a DCA scheme for \((P_{\mathrm{dc}})\). This consists of i) computing a subgradient of \(h\) and ii) solving the convex program of the form \((P_{k})\). In the ideal case (what is not always possible, especially for nondifferentiable DC programs) an optimal solution of \((P_{k})\) is explicitly determined, which corresponds to the explicit computation of a subgradient of \(g^{*}.\) Otherwise one should find efficient convex optimization algorithms suitably adapted to \((P_{k})\)’s specific structures in order to save computation time.
c.
Search for “good” DC decompositions. If the computations in i) and ii) are not satisfactory (costly, computed solutions by DCA are not sufficiently good, ...) then one has to find more suitable DC decomposition. That is a difficult issue and should be done by exploiting distinctive features of the class of DC programs at hand. Here reformulation techniques play a key role to obtain suitable models. Reformulation techniques should be diversified and have recourse to good mathematical backgrounds in numerical analysis and optimization.
d.
Search for “good” starting points. That can be done by combining with other approaches (heuristic or local search methods, solutions of convex relaxation problems in global optimization methods). Another efficient way in finding a convex minorant consists of the objective function on the feasible set \(C\) and solving the resulting convex program whose solution is used to initialize DCA. This strategy must be developed in depth and specifically, by exploiting the structure of the problem \((P_{\mathrm{dc}}).\)
e.
Globalize DCA : to guarantee globality of sought solutions or to improve their quality it is advised to combine DCA with global optimization techniques.
We show below how to use DCA for solving the three classes of nonconvex problems in CS.
3 Minimizing a nonconvex function under a convex constraint set
The mathematical formulation of this class of problem is given bywhere \(C\subset {\mathbb {R}}^{n}\) is a closed nonempty convex set and \(f\) is a nonconvex function on \({\mathbb {R}}^{n}\). Many applications in CS can be formulated in the form of (P) whose typical examples are Network Utility Maximization (NUM) [9, 30], power control problem [2, 6, 48, 54]), dynamic spectrum management in DSL systems [27, 53] MIMO relay optimization [15], sum-rate maximization, proportional-fairness and max–min optimization of SISO/MISO/MIMO ad hoc networks [14, 17, 43, 44].
$$\begin{aligned} \text {(P)}\,\,\inf \{f(x):x\in \mathrm{C}\} \end{aligned}$$
(9)
We will consider two examples of applications of DCA on NUM [30] and DSL [27]. Complete works on NUM and power control using DCA can be found in [24, 31, 48].
3.1 Can one get a DC formulation for any problem in this class?
The answer is “yes”, one can always formulate (\(P\)) as a standard DC program of the form \((P_{\mathrm{dc}}).\) In fact, as indicated above, the vector space \(\mathcal {DC}(X)\) contains most realistic objective functions. In the rare cases where \(f\) is not DC (for example, when \(f\) is a discontinous function), one can approximate \(f\) by a DC function or use reformulation techniques to get an equivalent DC program.
3.2 Useful DC decompositions and corresponding DCA
To illustrate the way to construct DC decompositions and design the resulting DCA, let us show the two useful DC decompositions of the problem (P) in (9) and discuss on their effectiveness.
Assume that there exists a nonnegative number \(\eta \) (resp. \(\rho \)) such that the function \(\frac{1}{2}\eta \Vert x\Vert ^{2}+f(x)\) (resp. \(\frac{1}{2 }\rho \Vert x\Vert ^{2}-f(x)\)) is convex. We can now write (P) in the form of DC program (P\(_{\mathrm{dc}}\)) with, for example, two following DC decompositions:andThe DCA applied to (P) with decomposition (10) and/or (11) can be described as follows.
$$\begin{aligned} g(x):=\chi _{C}(x)+\frac{1}{2}\eta \Vert x\Vert ^{2}+f(x);\quad h(x):=\frac{1 }{2}\eta \Vert x\Vert ^{2}\nonumber \\ \end{aligned}$$
(10)
$$\begin{aligned} g(x):=\chi _{C}(x)+\frac{1}{2}\rho \Vert x\Vert ^{2};\quad h(x):=\frac{1}{2} \rho \Vert x\Vert ^{2}-f(x).\nonumber \\ \end{aligned}$$
(11)
Algorithm DCAP1 Let \(x^{0}\) be given in \( {\mathbb {R}}^{n}\). Set \(k\leftarrow 0.\)
RepeatUntil convergence of \(\left\{ x^{k}\right\} .\)
-
Calculate \(x^{k+1}\) by solving the convex program$$\begin{aligned} \!\!\!\!\!\min \left\{ \frac{1}{2}\eta \Vert x\Vert ^{2}+f(x)-\langle x,\eta x^{k}\rangle :x\in C\right\} , \end{aligned}$$(12)
-
\(k\leftarrow k+1\)
Algorithm DCAP2: Let \(x^{0}\) be given in \({\mathbb {R}}^{n}\). Set \(k\leftarrow 0.\)RepeatUntil convergence of \(\left\{ x^{k}\right\} .\)
-
Calculate \(y^{k}\in \partial \left( \frac{1}{2}\rho \Vert .\Vert ^{2}-f(.))(x^{k}\right) \)
-
Calculate \(x^{k+1}\) by solving the convex programi.e. \(x^{k+1}={\mathrm{Proj}}_{C}(y^{k}/\rho ).\)$$\begin{aligned} \!\min \left\{ \frac{1}{2}\rho \Vert x\Vert ^{2}-\langle x,y^{k}\rangle :x\in C\right\} , \end{aligned}$$(13)
-
\(k\leftarrow k+1\)
Here, \({\mathrm{Proj}}_{C}\) stands for the orthogonal projection on \(C\).
As indicated above, we are greatly interested in the choice of DC decompositions: what is “the best’ among (10) and (11)? The answer depends on \(C\) and \(f\). In fact, the performance of the DCA depends upon that of the algorithm for solving convex programs (12) and (13). For certain problems, for example, box constrained quadratic programming and ball constrained quadratic programming, Algorithm DCAP2 is greatly less expensive than Algorithm DCAP1, because the orthogonal projection onto \(C\) in these cases is given in explicit form (see for example [35]). In practice, when \( f\) is differentiable and the computation of its gradient is not difficult, and the projection on \(C\) can be inexpensively determined, the use of DCAP2 is very recommended.
For using the above DC decompositions the crucial question is how to determine a nonnegative number \(\eta \) (resp. \(\rho \)) such that the function \(\frac{1}{2}\eta \Vert x\Vert ^{2}+f(x)\) (resp. \(\frac{1}{2}\rho \Vert x\Vert ^{2}-f(x)\)) is convex. In many practical problems such \(\eta \) and \(\rho \) exist and can be computed according to the properties of the function \(f\). For example, when \(f\) is a smooth function with Lipschitz continuous gradient\(\rho \) is nothing but the Lipschitz constant of \(\nabla f.\)
3.3 DCA for network utility maximization
Network utility maximization (NUM) has many applications in network rate allocation algorithms and Internet congestion control protocols. Consider a communication network with \(L\) links, each with a fixed capacity of \(c_{l}\) bps, and \(S\) sources (i.e., end users), each transmitting at a source rate of \(x_{s}\) bps. Each source \(s\) emits one flow, using a fixed set \(L(s)\) of links in its path, and has a utility function \(U_{s}(x_{s})\). Each link \(l\) is shared by a set of sources denoted \(S(l),\) (the set of users using link \( l)\). NUM, in its basic version, consists of maximizing the total utility of the network \(\sum _{s}U_{s}(x_{s})\) over the source rates \(x\), subject to linear flow constraints for all links \(l\):where \(\mathcal {S}\) denotes the set of users. Here the vector variable is \( x=(x_{s})_{s{\in } \mathcal {S}}{\in }\mathbb {R}^{S}\) and the constraint set is a well-defined convex polytope. There are many nice properties of the basic NUM model due to several simplifying assumptions of the utility functions and flow constraints, which provide the mathematical tractability of problem (14) but also limit its applicability. In particular, the utility functions \(U_{s}\) are usually assumed to be concave increasing. In such a case, the optimization problem (14) is a convex program, and so far is easy to solve. In the past, maximization of concave utility functions and the resulting distributed rate allocation for elastic traffic have gained extensive attention. Based on the concavity and continuity assumptions on utility functions and the elasticity assumption on application traffic, rigorous mathematical frameworks for standard price-based distributed algorithms have been investigated.
$$\begin{aligned} \mathrm{maximize}&\sum _{s\in \mathcal {S}}U_{s}(x_{s}) \nonumber \\ \mathrm{s.t}&\displaystyle \>\sum \limits _{s\in S(l)}x_{s}\le c_{l}&\quad \forall l,\,x_{s}\ge 0\quad \forall s\in \mathcal {S}, \end{aligned}$$
(14)
However, it is known that for many multimedia applications, user satisfaction may assume nonconcave shape as a function of the allocated rate. Furthermore, in some other models of utility functions, the concavity assumption on \(U_{s}(x_{s})\) is also related to the elasticity assumption on rate demands by users. When demands for \(x_{s}\) are not perfectly elastic, \( U_{s}(x_{s})\) may not be concave. In this case, the resulting NUM becomes nonconvex and significantly harder to be analyzed and solved. Since inelastic flows with nonconcave utility functions represent important applications in practice, today solving the NUM problem with nonconcave utility function is a challenge of the analysis and design of communication systems by nonconvex optimization techniques.
As an illustrative example, we consider the NUM problem with Sigmoidal-like utility functions [30] that are used in many multimedia applications and Internet congestion control (for example, the utility for voice applications is modeled by a Sigmoidal function with a convex part at low rate and a concave part at high rate). Other useful utility functions can also be solved by DCA-based algorithms (see [24]).
Consider Sigmoidal utilities in a standard form:where \(a_{s}>0,\,b_{s}<0\) and \(a_{s},\,b_{s}\) are integers. The Sigmoidal function is neither convex nor concave, but it is DC (difference of convex functions). Then the resulting NUM problem is a DC program. We are going to present a DC decomposition for the Sigmoidal function.
$$\begin{aligned} U_{s}(x_{s})=\frac{1}{1+{\mathrm{e}}^{-(a_{s}x_{s}+b_{s})}}, \end{aligned}$$
We haveIt is easy to verify that the functionsare convex (their derivative is increasing). Therefore, \(U_{s}\) is a DC function, and so is \(-U_{s}.\)
$$\begin{aligned} U_{s}(x_{s})\ ={\mathrm{e}}^{(a_{s}x_{s}+b_{s})}-\frac{{\mathrm{e}}^{2(a_{s}x_{s}+b_{s})}}{ 1+{\mathrm{e}}^{(a_{s}x_{s}+b_{s})}}. \end{aligned}$$
$$\begin{aligned} h_{s}(x_{s}):={\mathrm{e}}^{(a_{s}x_{s}+b_{s})}\quad \text { and }\quad g_{s}(x_{s}):=\frac{ {\mathrm{e}}^{2(a_{s}x_{s}+b_{s})}}{1+{\mathrm{e}}^{(a_{s}x_{s}+b_{s})}} \end{aligned}$$
Let \(K\) be the set defined by the constraints of Problem (14), sayand denote by \(\chi _{K}\) the indicator function on \(K\). Then the Sigmoidal NUM problem can be expressed asSince \(g_{s}\) and \(h_{s}\) are convex functions, the function \(g\) and \(h\) are convex too (note also that \(g\) and \(h\) are differentiable). Hence the Sigmoidal NUM problem is a DC program that can be written in the standard form asAccording to the general DCA scheme, applying DCA to (15) amounts to computing two sequences \(\{y^{k}\}\) and \(\{x^{k}\}\) in the way thatHence the algorithm can be described as follows.
$$\begin{aligned} K:=\left\{ \sum _{s\in S(l)}x_{s}\le c_{l}\,\quad \forall l\in \left\{ 1\ldots L\right\} ,\,x_{s}\ge 0\,\quad \forall s\in \mathcal {S}\right\} \end{aligned}$$
$$\begin{aligned}&\!\!\!\max _{x\in K}\left\{ U(x):=\sum _{s\in \mathcal {S}}U_{s}(x_{s})\right\} \\&\!\!\!\quad =-\min _{x\in K}\left\{ \sum _{s\in \mathcal {S}}\frac{{\mathrm{e}}^{2(a_{s}x_{s}+b_{s})}}{ 1+{\mathrm{e}}^{(a_{s}x_{s}+b_{s})}}-{\mathrm{e}}^{(a_{s}x_{s}+b_{s})}\ \right\} \\&\!\!\!\quad =-\min \left\{ g(x)-h(x):x\in K\right\} \text { where }g(x)\\&\!\!\!\quad := \sum _{s\in \mathcal {S}}g_{s}(x_{s}),\,h(x):=\sum _{s\in \mathcal {S}}h_{s}(x_{s}). \end{aligned}$$
$$\begin{aligned} \min \left\{ \left[ \chi _{K}(x)+g(x)\right] -h(x):x\in {\mathbb {R}}^\mathrm{S} \right\} . \end{aligned}$$
(15)
$$\begin{aligned}&\!\!\!\!y^{k}=\nabla h(x^{k}),\nonumber \\&\quad \!\!\!\!x^{k+1}\in {\mathrm{argmin}} \Bigg \{ \left[ \chi _{K}(x)+g(x) \right] -\ \langle x,\>y^{k}\rangle :x\in {\mathbb {R}}^\mathrm{S}\Bigg \}. \end{aligned}$$
Algorithm: DCA for Sigmoidal utility maximization:
1. Choose \(x^{0}\in \mathbb {R^{S}}\) as the initial point. Let \(\epsilon >0 \) be sufficiently small, \(k\leftarrow 0.\) 2. Repeat Set \(y^{k}=(a_{1}{\mathrm{e}}^{a_{1}x_{1}^{k}+b_{1}},\ldots ,a_{s}{\mathrm{e}}^{a_{s}x_{1}^{k}+b_{1}})\). Set \(x^{k+1}\) as an optimal solution of the convex program
$$\begin{aligned} \min \left\{ \sum _{s\in \mathcal {S}}\frac{{\mathrm{e}}^{2(a_{s}x_{s}+b_{s})}}{ 1+{\mathrm{e}}^{(a_{s}x_{s}+b_{s})}}-\langle x,y^{k}\rangle :x\in K\right\} \end{aligned}$$
(16)
\(k\leftarrow k+1\)
until
\(\>||x^{k+1}-x^{k}||\le \epsilon (1+||x^{k}||).\)
3.4 Spectrum management problem (SMP)
Discrete multitone (DMT) [42] has been adopted as standard in various DSL applications such as asymmetric DSL (ADSL) and more recently for very-high-bit-rate digital subscriber line (VDSL) by International Telecommunication Union (ITU). For a sufficiently large number of sub-carriers, DMT transmission over a frequency-selective fading channel can be modeled as a set of \(K\) parallel independent flat-fading sub-carrier AWGN channels (Additive white Gaussian noise). Under this Gaussian assumption, the achievable bit-loading rate of user \(n\) on tone \(k\) iswhere \(p_{k}^{n}\) denotes user \(n\)’s transmit power spectral density (PSD) on tone \(k\); \(\omega _{k}^{n}\) denotes user \(n\)’s transmit noise power on tone \( k \); \(g_{k}^{n,m}\) is the channel path gain from user \(m\) to user \(n\) on tone \(k\); \(h_{k}^{n,m}=\frac{|g_{k}^{n,m}|^{2}}{|g_{k}^{n,n}|^{2}}\) is the normalized interference path power gain from user \(m\) to user \(n\) on tone \(k\) ; \(\sigma _{k}^{n}=\frac{\omega _{k}^{n}}{|g_{k}^{n,n}|^{2}}\) is the noise variance of user \(n\) on tone \(k\), and \(\Gamma \) is the SNR-gap to capacity. The data rate of user \(n\) is \(R_{n}=f_{s}\sum _{k=1}^{K}r_{k}^{n},\) where \(f_{s}\) is the DMT symbol rate.
$$\begin{aligned} r_{k}^{n}&= \log _{2}\left( 1+\frac{1}{\Gamma }\frac{{\left| {g_{k}^{n,n}} \right| ^{2}p_{k}^{n}}}{{\sum _{m\ne n}{\left| {g_{k}^{n,m}} \right| ^{2}p_{k}^{m}+\omega _{k}^{n}}}}\right) \\&= \log _{2}\left( 1+\frac{ 1}{\Gamma }\frac{{p_{k}^{n}}}{{\sum _{m\ne n}{h_{k}^{n,m}p_{k}^{m}+ \sigma _{k}^{n}}}}\right) , \end{aligned}$$
The goal of spectrum management problem is to achieve best possible user rates tradeoff among users in the network, i.e., to find the boundary of rate region. Assume that each user is subject to an individual total transmission power constraint. One way to define the SMP in the literature is consider the following optimization problemwhere \(T_{n}\) is minimum target rates of user \(n\) and \(P_{n}\) is maximum total transmission power of user \(n\). The SMP (17) aims to maximize the rate of user \(1\) while guarantees the achievable rates of other users higher than their required minimum target rates \(T_{n}\). \(P_{n}\) denotes the maximum total transmission power of user \(n\). Spectral mask constraints \(p_{k}^{n,\mathrm{{mask}}}\) may also be applied if needed.
$$\begin{aligned}&\!\!\!\!\max \limits _{p_{1},p_{2},\ldots ,p_{K}}\Bigg \{ R_{1}:R_{n}\ge T_{n},\quad \forall n\ge 1;\,\sum \limits _{k}p_{k}^{n}\le P_{n},\forall n,k;\nonumber \\&\qquad \qquad \qquad p_{k}^{n}\le p_{k}^{n,{\mathrm{mask}}},\;\quad \forall n,k\Bigg \} , \end{aligned}$$
(17)
Among various Dynamic Spectrum Management (DSM) techniques, centralized Optimal Spectrum Balancing (OSB) achieves the maximum data rates by computing the optimal PSDs (power spectral density) for all modems in DSL systems. The centralized algorithm based on dual decomposition for OSB, proposed in [3], decouples joint optimization across all tones to make the problem solvable per-tone basis. If the rate region is convex (the assumption that the rate region is convex is justified in [3] for two-user in DSL system, and the same logic for two-user can be applied to justify the convexity of rate region for multiple-user case), solving the problem (17) amounts to solving the following weighted sum rate optimization problem [5]:where the weight for user 1, \(\omega _{1}\), is set to unity, resulting in the maximization of the rate of user 1; whereas \(\omega _{n}\ge 0,\,n\ne 1 \) can be adjusted to guarantee the target rate of user \(n\). In [27], we have investigated DC programming and DCA for solving (18).
$$\begin{aligned}&\!\!\!\max \limits _{p_{1},\ldots ,p_{K}}\Bigg \{ \sum \limits _{n}\omega _{n}R_{n}:\sum \limits _{k}p_{k}^{n}\le P_{n}\;\quad \forall n;\,0\le p_{k}^{n}\nonumber \\&\qquad \qquad \quad \le p_{k}^{n,{\mathrm{mask}}}\;\quad \forall k,n\Bigg \} , \end{aligned}$$
(18)
3.4.1 A nice DC formulation of SMP (18)
First, we write Problem (18) in the form of a minimization programA natural DC decomposition of \(f\) (easily deduced from the definition of \( r_{k}^{n}\)) has been given in [27]. However, as indicated in [27], from numerical point of views, the DCA scheme corresponding to this DC decomposition is not interesting because it requires an iterative algorithm for solving a convex program at each iteration. In an elegant way we introduced in [27] a nice DC reformulation of the problem (19) (based on the second DC decomposition discussed in Sect. 2) for which the resulting DCA is explicitly determined via a very simple formula. Such a DC decomposition of \( f\) is inspired by the following result.
$$\begin{aligned}&\!\!\!\min \limits _{p=(p_{1},\ldots ,p_{K)}}\left\{ f(p):=-\sum \limits _{n=1}^{N}\omega _{n}R_{n}:\sum \limits _{k=1}^{K}p_{k}^{n}\le P_{n}\;\forall n;\right. \nonumber \\&\qquad \qquad \qquad \left. \,0\le p_{k}^{n}\le p_{k}^{n,{\mathrm{mask}}}\;\forall k{=}1\ldots K,n{=}1\ldots N\right\} .\nonumber \\ \end{aligned}$$
(19)
Theorem 1
There exists \(\rho >0\) such that the function is convex on \(C,\) the feasible set of (19), say \(C:=\{p\in {\mathbb {R}}^{K\times N}\ |\sum _{k=1}^{K}p_{k}^{n}\le P_{n},0\le p_{k}^{n}\le p_{k}^{n,{\mathrm{mask}}}\quad \forall n=1,2,\ldots ,N;\;k=1,2,\ldots ,K\}.\)
$$\begin{aligned} \;h(p):=\frac{1}{2}\rho ||p||^{2}-f(p) \end{aligned}$$
(20)
Proof
See [27]. \(\square \)
Using the theorem above, we get the next DC decomposition of \(f\):and Problem (19) can be now written in the formor again, in the standard form of DC program:Then, DCA apply to Problem (19) is described as follows.
$$\begin{aligned} g(p)=\frac{1}{2}\rho ||p||^{2},\;\;h(p)=\frac{1}{2}\rho ||p||^{2}-f(p), \end{aligned}$$
(21)
$$\begin{aligned} \min \{\;f(p):=g(p)-h(p)\;|\;p\ \in C\} \end{aligned}$$
$$\begin{aligned} \min \{\chi _{C}(x)+\;f(p)\ )\;|\;p\ \in \mathbf {R}^{N\times K}\}. \end{aligned}$$
DCA-SMP
Initialization: Let \(\epsilon >0\) be given, \(\mathbf {p}^{(0)}\in C\) be an initial point, set \(r:=0;\)
Repeat: setand calculate \(\mathbf {p}^{(r+1)}\in \partial (g+\chi _{C})^{*}(\mathbf {q }^{(r)})\) by solving the linear constrained quadratic programSet \(r+1\leftarrow r\)
$$\begin{aligned} \mathbf {q}^{(r)}=\nabla h(\mathbf {p}^{(r)})=\rho \;\mathbf {p}^{(r)}-\nabla f( \mathbf {p}^{(r)}) \end{aligned}$$
$$\begin{aligned} \min \left\{ \frac{1}{2}\rho ||p||^{2}-\langle p,\mathbf {q}^{(r)}\rangle |p\in C\right\} \end{aligned}$$
(22)
until either \(||\mathbf {p}^{(r+1)}-\mathbf {p} ^{(r)}||\le \epsilon (||\mathbf {p}^{(r)}||+1)\) or \(|f(\mathbf {p}^{(r+1)})\)\(-f( \mathbf {p}^{(r)})|\le \epsilon (|f(\mathbf {p}^{(r)})|+1)\).
4 Nonconvex constraint set
A typical application of this class of problems is Internet routing (see for example [5]). Mathematically, the nonconvex constraint set is expressed aswhere \(C\) is a closed nonempty convex set in \({\mathbb {R}}^{n},\,g_{i},h_{i}\in \Gamma _{0}({\mathbb {R}}^{n}),\)\(i=0,\ldots ,m,\) and \( f_{i}(x)\le 0\) are called DC constraints. The generic formulation of this class of problems takes the formwhere \(E\) is assumed to be nonempty.
$$\begin{aligned} E:=\left\{ x\in C,\,f_{i}(x):=g_{i}(x)-h_{i}(x)\le 0,\,i=1, \ldots , m\right\} \end{aligned}$$
$$\begin{aligned} \alpha =\inf \,\{f_{0}(x):=g_{0}(x)-h_{0}(x)\ :x\in E\quad (P_{\mathrm{dcg}}) \end{aligned}$$
(23)
This class of nonconvex programs (called general DC programs) is the most general in DC Programming and, a fortiori, more difficult to treat than that of standard DC programs \((P_{\mathrm{dc}})\) because of the nonconvexity of the constraints. It is not new and has been addressed in [34]. Its renewed interests is due to the fact that this class appears, increasingly, in many models of nonconvex variational approaches.
We can solve \((P_{\mathrm{dcg}})\) by DCA via penalty techniques. First, we transform \( (P_{\mathrm{dcg}})\)-(23) into \((P_{\mathrm{dc}})\) via penalty techniques in DC programming.
Let the functions \(p\) and \(p^{+}\) be defined bywhich are DC functions with the following DC decompositions (in case \( g_{i}, \)\(h_{i}\) are finite on \(C\) for \(i=1,\ldots ,m,\)(see, e.g., [34] ), obtained directly from those of \(f_{i},i=1,\ldots ,m.\)The general DC program \((P_{\mathrm{dcg}})\)-(23) can then be formulated asand its penalized is a standard DC programLet DC decompositions of \(f_{0}\) and \(p^{+}\) be given bywhere \(g_{0},\,h_{0}\,,p_{1},\,p_{2}\) are convex functions defined on the whole space. Then, we have the following DC decomposition for \(\varphi _{\tau }\)where,Exact penalty (relative the constraint \(p^{+}(x)\le 0)\) for (26) means that there is \(\tau _{0}\,\ge 0\) such that for all \(\tau >\,\tau _{0}\) both DC programs \((P_{\mathrm{dcg}})\)-(23) and \((P_{\tau })\)-\((\)27) are equivalent in the sense that \(\alpha (\tau )=\alpha \) and \((P_{\mathrm{dcg}})\)-(23) et \((P_{\tau })\)-\((\)27) have the same (global) solution set. In this case, the solution of \((P_{\mathrm{dcg}})\)-(23) can be achieved by applying DCA to a standard DC program \((P_{\tau })\)-( 27) with \(\tau >\,\tau _{0}.\)
$$\begin{aligned} \begin{array}{l} p(x):=\max \{f_{i}(x):i=1,\ldots ,m\};\\ I(x):=\left\{ i\in \{1,\ldots ,m\}:\;f_{i}(x)=p(x)\right\} \\ p^{+}(x):=\max \{0,p(x)\},\\ \end{array} \end{aligned}$$
$$\begin{aligned}&\!\!\!p(x)=\max _{i=1,\ldots ,m}\left\{ g_{i}(x)+\sum _{j=1,j\not =i}^{m}h_{j}(x)\right\} -\sum _{j=1}^{m}h_{j}(x)\nonumber \\ \end{aligned}$$
(24)
$$\begin{aligned}&\!\!\!p^{+}(x)=\max _{i=1,\ldots ,m}\left\{ \sum _{j=1}^{m}h_{j}(x),g_{i}(x)+\sum _{j=1,j\not =i}^{m}h_{j}(x)\right\} \nonumber \\&\qquad \qquad \;-\sum _{j=1}^{m}h_{j}(x). \end{aligned}$$
(25)
$$\begin{aligned} \alpha =\inf \{f_{0}(x):=g_{0}(x)-h_{0}(x)\ :\ x\in C,\,p^{+}(x)\le 0\}\nonumber \\ \end{aligned}$$
(26)
$$\begin{aligned} \alpha (\tau )=\inf \{\varphi _{\tau }(x):=f(x)+\ \tau p^{+}(x):\ x\in C\}.\ \ (P_{\tau })\nonumber \\ \end{aligned}$$
(27)
$$\begin{aligned}&\!\!\!\!f_{0}(x)=g_{0}(x)-h_{0}(x); \end{aligned}$$
(28)
$$\begin{aligned}&\!\!\!\!p^{+}(x)=p_{1}(x)-p_{2}(x), \end{aligned}$$
(29)
$$\begin{aligned} \varphi _{\tau }(x)=g_{\tau }(x)-h_{\tau }(x),\quad \end{aligned}$$
(30)
$$\begin{aligned} g_{\tau }(x){:=}g_{0}(x)+\tau p_{1}(x);\quad h_{\tau }(x){:=}h_{0}(x)+\tau p_{2}(x). \end{aligned}$$
(31)
Exact penalty techniques in DC programming have been widely investigated in our works [25, 28, 34]. However, from a computational point of view, an inconvenience of this exact penalty method is that the penalty parameter is generally unknown. Moreover, there are practical optimization problems for which the exact penalization is not satisfied. In [28], we proposed to develop the DCA for solving general DC program \((P_{\mathrm{dcg}})\)-( 23) by using a penalty technique with updated parameter.
The generalized DCA can be deduced from DCA as follows: instead of fixing the penalty parameter \(\tau \), DCA is applied to the sequence of \((P_{\tau _{k}})\) with an increasing sequence of penalty parameters \(\{\tau _{k}\}\) given by a updating rule from the current iteration \(x^{k}\) such that \( x^{k+1}\) is the next iteration of DCA applied to \((P_{\tau _{k}})\) from \( x^{k}\). Our work consists in the statement of appropriate updating rules for the sequence \(\{\tau _{k}\}\) and the refinement of constraint qualifications used, in order to ensure global convergence (to a critical point of \( (P_{\mathrm{dcg}})\)-(23)\()\) and efficiency of DCA1. It is also important that the sequence \(\{\tau _{k}\}\) is constant after a certain rank. The penalty introduced uses \(l_{\infty }\)- norm, but we can also consider the \(l_{1}\) -norm where \(q(x):=\sum _{i=1}^{m}f_{i}^{+}(x)\) replaces \(p^{+}(x)\).
5 Integer variables
Several applications in CS can be formulated as an optimization problem with (mixed) integer variables. Here we mention some classes of problems which have been successfully solved by DCA.
5.1 Cross-layer optimization in multi-hop time division multiple access (TDMA) networks
Efficient design of wireless networks is a challenging task due to the interference nature of shared wireless medium. Recently, the concept of cross-layer design has been investigated extensively. In [26, 29] a cross-layer optimization framework, i.e., joint rate control, routing, link scheduling and power control for multi-hop TDMA networks, has been considered. Particularly, we studied a centralized controller that coordinates the routing process and transmissions of links such that the network lifetime is maximized [29] and the quality of-service (QoS) constraints on the minimum source rates are satisfied. Alternatively, the energy consumption is an important design criterion for a multi-hop wireless network. In [26], we considered the energy minimization-based cross-layer design problem. We will show below that the aforementioned problems can be formulated as mixed integer-linear programs (MILP) and then efficiently solved by DCA.
In the considered TDMA network, time is partitioned into fixed-length frames, and each frame is further divided into \(J\) time slots with unit duration. Since the resource allocation is the same in all frames, we concentrate our design on a single frame. A node may need to transmit in one or more slots for its own traffic and/or relay traffic from other nodes. If a node transmits in a slot, while its transmission power can be varied from [0, \(P_{\max }\)], its transmission rate is fixed at a unit rate. In the TDMA-based network, a channel is specified by two elements \((j,l),\,j\in { \mathcal {J}},\,l\in {\mathcal {L}}\), where \({\mathcal {J}}=\{1,2,\ldots ,J\}\). For the channel, the resource allocation is denoted by (\(s_{j}^{l},P_{j}^{l}\) ), where \(s_{j}^{l}=1\) means link \(l\) is active at slot \(j\) while \( s_{j}^{l}=0\) otherwise, and \(P_{j}^{l}>0\) denotes the transmission power of link \(l\) at slot \(j\) if \(s_{j}^{l}=1\), \(P_{j}^{l}=0\) otherwise.
At each node, the difference of its outgoing traffic and its incoming traffic should be the traffic generated by itself, i.e.,where \({\mathcal {O}}(n)\) and \({\mathcal {I}}(n)\) are the set of outgoing links and incoming links at node \(n\), respectively. The values of \(s_n\) for the non-source nodes are set to zero, or equivalently all the traffic entering such nodes must be routed.
$$\begin{aligned} \sum _{l \in {\mathcal {O}}(n)} \sum _{j=1}^J s_j^{l} - \sum _{l \in {\mathcal {I} }(n)} \sum _{j=1}^J s_j^{l} = r_n, \quad n \in {\mathcal {N}} \end{aligned}$$
(32)
The energy consumption at node \(n\in \mathcal {N}\) can be written aswhere \(\epsilon _{l}\hbox { and }\varepsilon _{l}\) denote the energy needed to transmit and receive a unit of traffic over link \(l\), respectively. Note that \( \epsilon _{l},\,\varepsilon _{l}\) include the energy consumed by the signal processing blocks at the link ends.
$$\begin{aligned} \mathcal {E}_{n}&= \sum _{l\in {\mathcal {O}}(n)}\sum _{j=1}^{J}P_{j}^{l}+\sum _{l \in {\mathcal {O}}(n)}\sum _{j=1}^{J}\epsilon _{l}s_{j}^{l}\nonumber \\&+\sum _{l\in { \mathcal {I}}(n)}\sum _{j=1}^{J}\varepsilon _{l}s_{j}^{l},\quad n\in {\mathcal { N}} \end{aligned}$$
(33)
Interference Model
Wireless channel is a shared medium and interference-limited where links contend with each other for channel use. Moreover, interference relations among the nodes and/or links can be modeled in various ways, for example, by using the signal-to-interference-plus-noise-ratio (SINR)-based model [32, 52]. Specifically, if the link \(l\in {\mathcal {L}}\) is active at slot \(j\) (i.e., \(s_{j}^{l}=1\)), the following inequality should hold so as to guarantee the transmission quality of the linkwhere \({\mathrm {SINR}}_{j}^{l}\) is the SINR for link \(l\) at slot \(j\), \(h_{kl}\) is the path gain from the transmitter of link \(k\) to the receiver of link \(l\) , \(\eta _{l}\) is the noise power at receiver of link \(l\), and \(\gamma \mathrm{th}\) is the required SINR threshold for accurate information transmission.
$$\begin{aligned} {\mathrm {SINR}}_{j}^{l}=\frac{P_{j}^{l}h_{ll}}{\sum _{k\ne l}P_{j}^{k}h_{kl}+\eta _{l}}\ge \mathrm {\gamma ^{th}} \end{aligned}$$
(34)
We assume that all wireless nodes are low-mobility devices and/or the topology of the network is static or changes slowly allowing enough time for computing the new scheduler. An example of such networks is a wireless sensor network for environmental monitoring with fixed sensor locations. In this case, the need for distributed implementation is not necessary.
From the preceding discussions, the energy minimization-based cross-layer design, i.e., joint rate control, routing, link scheduling, and power allocation problem can be mathematically formulated as where \(\hat{n}\) denotes the common sink node for all data generated in the network, \(D\) is a very large positive constant. The objective function is the energy consumption in the network.1 Constraints (35b) ensure that the data generated by source nodes are routed properly. Constraints (35c ) guarantee that the rate for each node is no less than a minimum rate. The minimum rates are possibly different for nodes and are usually determined by the network QoS. Nodes which do not generate traffic have \(r_{n}=r_{n}^{\min }=0\). Constraint (35d) is the flow conservation at the traffic destination for all the sources. Constraints (35e) state that a node can not receive and transmit simultaneously in one particular time slot. Constraints (35f) make sure the \({\mathrm {SINR}}\) requirement is met: if a link \(l\) is active in time slot \(j\), then the \( {\mathrm {SINR}}\) at receiver of link \(l\) must be larger than the given threshold \(\gamma ^\mathrm{th}\) which also depends on the system implementation. Constraint (35f) is automatically satisfied if link \(l\) is not scheduled in time slot \(j\). Constraint (35g) states that if a link \(l\) is scheduled for time slot \(j\), i.e., \(s_{j}^{l}=1\) , then the corresponding power value \(P_{j}^{l}\) must be less than \(P_{\mathrm{max}}\). Otherwise, \(P_{j}^{l}\) obviously equals to zero. We also impose binary integer constraints on \(s_{j}^{l}\).
$$\begin{aligned}&\!\!\!\min _{r_{n},P_{j}^{l},\;s_{j}^{l}}\qquad \;\sum _{n\in \mathcal {N}}\mathcal {E}_{n} \end{aligned}$$
(35a)
$$\begin{aligned}&\!\!\!\text {subject to:}\nonumber \\&\!\!\!\sum _{l\in {\mathcal {O}}(n)}\sum _{j=1}^{J}s_{j}^{l}- \sum _{l\in {\mathcal {I}}(n)}\sum _{j=1}^{J}s_{j}^{l}=r_{n},\;n\in \mathcal {N} \end{aligned}$$
(35b)
$$\begin{aligned}&\!\!\! r_{n}\ge r_{n}^{\min },\;n\in {\mathcal {N}} \end{aligned}$$
(35c)
$$\begin{aligned}&\!\!\!\sum _{l\in \mathcal {I}(\hat{n})} \sum _{j=1}^{J}s_{j}^{l}=\sum _{n\in \mathcal {N}}r_{n} \end{aligned}$$
(35d)
$$\begin{aligned}&\!\!\!\!\sum _{l\in \mathcal {O}(n)}s_{j}^{l}+\sum _{l\in \mathcal {I}(n)}s_{j}^{l}\le 1,\;\quad \forall n\in \{\mathcal {N}\cup \hat{n} \},\;j\!\!=\!\!1,\ldots ,J\nonumber \\ \end{aligned}$$
(35e)
$$\begin{aligned}&\!\!\!h_{ll}P_{j}^{l}\ge \mathrm {\gamma ^{th}}\sum _{k\ne l}P_{j}^{k}h_{kl}+\mathrm {\gamma ^{th}}\eta _{l}+D(s_{j}^{l}-1),\nonumber \\&\qquad \qquad \qquad \qquad \quad \quad \forall l\in \mathcal {L},\;j=1,\ldots ,J \end{aligned}$$
(35f)
$$\begin{aligned}&\!\!\!0\le P_{j}^{l}\le P_{\mathrm{max}}s_{j}^{l},\;\quad \forall l\in \mathcal {L},\;j=1,\ldots ,J \end{aligned}$$
(35g)
$$\begin{aligned}&\!\!\!s_{j}^{l}\in \{0,1\},\quad \quad \forall l\in \mathcal {L} ,\;j=1,\ldots ,J \end{aligned}$$
(35h)
It can be seen that the cross-layer optimization problem (35a)–(35h) belongs to a class of well-known mixed-integer linear programs (MILPs). The combinatorial nature of the optimization (35a)–(35h) is not surprising and it has been shown in some previous works, albeit with different objective functions and formulations [7, 32, 52]. Theoretically, MILPs are NP-hard which is clearly inviable for practical scenarios when the dimension is large. It has been shown in [26] that, at optimality, the source rate constraints (35c) must be met with equalities for all sources.
Note that by considering (35a), one aims to minimize the total energy consumption, it may cause some particular nodes spending more energy than the other nodes, and thus, running out of energy quicker. Therefore, equal energy distribution among nodes is not optimal. Another design objective which may help to prevent such situation is as follows The optimization problem (36a)–(36b) aims at minimizing the maximum energy consumed at nodes(s). As a result, more nodes are likely to be involved in the routing algorithm, i.e., relaying information for other nodes. For simplicity, the optimization problem (35a)–(35h) is often considered in the literature.
$$\begin{aligned}&\!\!\!\min _{r_{n},P_{j}^{l},\;s_{j}^{l}}\quad \;\max _{n\in \mathcal {N}}\;\mathcal {E}_{n} \end{aligned}$$
(36a)
$$\begin{aligned}&\!\!\!\text {subject to:}\quad \text {The constraints (35b)--(35h)}. \end{aligned}$$
(36b)
The cross-layer optimization problem (35a)–(35h) has worst case exponential complexity when BnB methods are used to compute the solution. Moreover, when modeling practical networks and depending on the number of links, nodes and time slots, problem with large sizes may arise. As a result, it is extremely difficult to schedule links optimally. Most research in literature is based on heuristic at the cost of performance degradation, for example, see [7, 8, 52]. In [26] , we investigated a DCA scheme to solve the mixed 0–1 linear program (35a)–(35h) efficiently.
5.2 Quality of service (QoS) routing problems
The Unicast (resp. Multicast) QoS routing emphasizes to find paths (resp. a set of paths) from a source node to a destination node (resp. a set of destination nodes) satisfying the QoS requirements. The Routing problems become more complex as far as we consider mobile networks or hybrid networks, because of dynamic topology and real time routing procedure. As an example, we consider a scenario in Multicast routing problem, such as we are staying in a car parking place. The mobile services are provided in each moving car, equipped with a mobile device, via a car service center likes in the car parking place. There are \(m\) cars sending their requests to a mobile car service center, they need help to find the route to go to their destinations under the travel time constraint, the less latency traffic jam, the jitter time delay constraint, the travel cost (same sources, different destinations, considering local constraints to each mobile vehicle). Therefore, based on the temporary update data of the network state, the mobile car service system has to calculate the route and given the answer for each car in a few seconds. In this context, we need a centralized and efficient algorithm to calculate the routes.
The problem of finding a path in network with multiple constraints (the MCP problem) is NP-complete. We reformulated the MCP [46] and MCOP (multi-constrained optimal path problem) [47, 51] problem as Binary Integer Linear Programs (BILP) and investigated DCA-based algorithms for solving them. The DCA is fast and furnished an optimal solution in almost all cases, and a near-optimal solution in the remaining cases. For large scale problems we investigated the proximal decomposition technique to solve convex subprograms at each iteration of DCA. Computational results show that this approach is efficient, especially for large-scale settings where the powerful CPLEX fails to be applicable.
5.3 The partitioning-hub location-routing problem
The Partitioning-Hub Location-Routing Problem (PHLRP) is a hub location problem involving graph partitioning and routing features. PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. There are various important applications of PHLRP, such as the deployment of network routing protocol problems and the planning of freight distribution problems. In [50] we formulated this problem as an Binary Integer Linear Programming (BILP) and then investigate DCA for solving it. Preliminary numerical results are compared with the well-known commercial solver CPLEX, they show the efficiency and the superiority of DCA.
5.4 The car pooling problem
Car pooling is a well-known transport solution that consists of sharing a car between a driver and passengers sharing the same route, or part of it. The challenge is to minimize both the number of required cars and the additional cost in terms of time for the drivers. To solve the problem, several tasks should be performed: choosing drivers and passengers, allocating passengers to cars, computing an optimal route for the cars. As such, the car pooling transport problem may be described as some kind of fleet management problem. In [49], we formulated this problem as a Mixed Integer Linear Program for which DCA has been efficiently applied. In order to globally solve the problem, we combine DCA with classical Branch and Bound algorithm. DCA is used to calculate upper bound while lower bound is obtained from a linear relaxation problem. Preliminary numerical results are compared with CPLEX. They show the efficiency and the superiority of DCA-based algorithms.
5.5 The minimum m-dominating set problem
Let \(G=(V,E)\) be a graph, where \(V\) is the set of nodes and \(E\) is the set of edges of \(G\). A dominating set \(D\) of a graph \(G=(V,E)\) is a subset of nodes \(D\subseteq V\) such that every vertex not in \(D\) is joined to at least one member of \(D\) by some edge. The domination number \(\gamma (G)\) is the number of vertices in a smallest dominating set for \(G\). The dominating set problem is a classical NP-complete decision problem [10] and has various applications in CS. A classical network application for this problem would be to choose a set of locations to install relay antennas. In ad hoc networks, creating a dominating set is a way to organize the network and is generally used as a first step for generating a connected dominating set [11]. This problem is formulated as a BILP for which DCA is investigated in [39]. Numerical results show that the DCA is efficient even for very large instances of problem. Moreover, our algorithm obtained better solution in significantly less time than CPLEX.
In a general framework, we show below how to solve optimization problems with integer variables by DCA.
5.6 From combinatorial optimization to DC programming: reformulation
5.6.1 Mixed zero-one concave minimization programming problem
Let \(D \ne \emptyset \) be a bounded polyhedral convex set in \({\mathrm {I\!R}} ^{n}\) and let \(J \subset \{1,\ldots ,n\}\).where \(f\) is a finite concave function on \(D\).
$$\begin{aligned} \min \left\{ f(x):x\in D,\,x_{i}\in \{0,1\},\quad \forall i\in J\right\} , \end{aligned}$$
(37)
Let \(K:=\{x\in D:0\le x_{i}\le 1,\quad \forall i\in J\}\) and define \( p(x)=\sum _{i\in J}{x_{i}(1-x_{i})}.\) Clearly, \(p\) is a concave function with nonnegative values on \(K\) andHence (37) can be reformulated as (by Theorem below)which is equivalent to, for any \(t>t_{o}\)
$$\begin{aligned}&\!\!\!\{x\in D,\,x_{i}\in \{0,1\}\}= \{x\in K:p(x)=0\}\nonumber \\&\quad \!\!\!=\{x\in K: p(x)\le 0\}. \end{aligned}$$
$$\begin{aligned} \min \left\{ f(x): x\in K,\,p(x)\le 0\right\} \end{aligned}$$
$$\begin{aligned} \min \left\{ f(x)+tp(x):x\in K\right\} . \end{aligned}$$
(38)
Theorem 2
[23] Let \(K\) be a nonempty-bounded polyhedral convex set in \( \mathrm{I\!R}^{n}\) and \(f,\,p\) be finite concave on \(K\). Assume the feasible set of (P) be nonempty and \(p\) be nonnegative on \(K\). Then there exists \(t_{o}\ge 0 \) such that for every \(t>t_{o}\) the following problems have the same solution sets:Furthermore
$$\begin{aligned}&\!\!\!(P_t)\quad \alpha (t)=\inf \{f(x)+tp(x):x\in K\},\\&\!\!\!(P)\quad \alpha =\inf \{f(x):x\in K,p(x)\le 0\}. \end{aligned}$$
(i)
if the vertex set of \(K\), denoted by \(V(K)\), is contained in \(\left\{ x\in K: p(x)\le 0\right\} \), then \(t_{o}=0\).
(ii)
if \(V(K)\) is not contained in \(\left\{ x\in K:p(x)\le 0\right\} \), then \(t_{o}\le \frac{f(x^{o})-\alpha (0)}{S}\) for every \(x^o \in K, \, p(x^o) \le 0\), where \(S:=\min \left\{ p(x):x\in V(K),\,p(x)>0\right\} .\)
DCA for solving (P\(_{\varvec{t}}\))Assuming that a subgradient of \(-f\) is computable. One DC decomposition of \( F_{t}\) can be chosen asIn this case, (\(P_{t}\)) is a polyhedral DC program because \(\chi _{K}\) is a polyhedral convex function, and the general DCA scheme becomes:Besides the computation of subgradients of \(-f\) and set \(\nabla (-p)(x)=\sum _{i\in J}{(2x_{i}-1)},\) the algorithm requires one linear program at each iteration The convergence properties can be stated as follows:
$$\begin{aligned}&\!\!\!\!(\mathrm{P}_t)\quad \alpha (t)=\inf _{x\in K} \left\{ f(x)+tp(x) \right\} \nonumber \\&\quad =\inf _{x\in {\mathrm {I\!R}}^{n}} \left\{ F_{t}(x):=\chi _{K}(x)+f(x)+tp(x) \right\} . \end{aligned}$$
$$\begin{aligned} F_{t}(x)&:= g(x)-h(x) \text{ with } g(x):=\chi _{K}(x),\nonumber \\&h(x):=-f(x)-tp(x). \end{aligned}$$
(39)
$$\begin{aligned}&\!\!\!y^{k}\in \partial (-f(x^{k})-tp(x^{k})); \nonumber \\&\!\!\!\quad x^{k+1}\in {\mathrm{argmin}} \left\{ -\langle x,y^{k}\rangle :x\in K\right\} . \end{aligned}$$
(40)
Theorem 3
i)
DCA generates a finite sequence \(x^{1},\ldots ,x^{k_{*}}\) contained in V(K) such that \(\ f(x^{k+1})+tp(x^{k+1})\le f(x^{k})+tp(x^{k})\), \(p(x^{k+1})\le p(x^{k})\) for each k , and \(x^{k_{*}}\) is a critical point of \(g-h\).
ii)
If, in addition, \(h\) is differentiable at \(x^{k_{*}}\), then \( x^{k_{*}}\) is actually a local minimizer to (P\(_{t}\)).
iii)
Let \(t>t_{1}:=\max \bigg \{ \frac{f(x)-\alpha (0)}{S}:x\in V(K)\cap \ \left\{ x\in K:p(x)=0\right\} \bigg \}.\) If at an iteration \(q\) one has p(\( x^{q})=0\), then \(\ p(x^{k}\))=0 and \(f(x^{k+1})\le f(x^{k})\)\(\forall k \ge q.\)
5.6.2 Extension cases
Based on new results related to exact penalty and error bounds in DC programming [28], the same reformulation technique via exact penalty can be used for
-
Linear constrained mixed zero-one DC programming problems.
-
Linear constrained mixed integer DC programming problems.
6 Another issue: solving convex programs by DCA
Another issue which is also important in CS but were not discussed in this paper is how to solve large-size convex programs. Although convex programming has been studied for about a century, an increasing amount of effort has been put recently into developing fast and scalable algorithms to deal with large scale problems. While some convex regularizations involve convex quadratic programs (QP) for which standard QP solvers can be certainly used, many first-order methods have been developed in the last years for large scale convex problems. Since DC programming and DCA encompass convex programming and convex programs can be recast as (infinitely many) DC programs to which DCAs become global, (i.e. providing optimal solutions), one can make use of these theoretical and algorithmic tools to better reformulate and solve convex programs.
7 Conclusion
We have presented DC programming and DCA for modeling and solving three challenging classes that cover most nonconvex programs in communication systems. These theoretical and algorithmic tools have been outlined in an appropriate way to make them understandable to the reader. They highlight the distinctive features (flexibility, versatility, inexpensiveness, scalability, efficiency and globality) of DC programming and DCA. It is desirable that our approaches will help researchers and practitioners tackle efficiently their nonconvex programs, especially in the large-scale setting.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.