# On the Use of Biased-Randomized Algorithms for Solving Non-Smooth Optimization Problems
## 2 Non-Smooth Optimization Problems  
OPs can be broadly classified as convex or non-convex. Convex OPs are usually characterized by a convex objective function and a set of constraints that form a convex region. Each constraint restricts the solution space to a convex region, and the intersection of these regions, which form the feasible solutions, is also convex. The main feature that makes convex OPs easy to work with is that any local optimum is also a global optimum. This significantly reduces the computational time yielding exact solutions in reasonable times. Therefore, if doable, it is of interest to convert any optimization problem into a convex OP. Despite the specific structure needed for a convex OP, we find several applications of it in real-life problems. For example, those problems that can be modeled as a linear programming model are convex problems because all linear functions are by definition convex [28]. Nevertheless, there are some other problems that cannot be modeled as a convex OP. Non-convex problems have either non-convex objective functions or non-convex feasible regions (or both). This brings in several challenges to solve these problems. The main challenge is that the solution methods employed for convex OPs cannot be directly applied for non-convex ones because of the availability of many disjoint regions in the solution space, each of which usually has its own local optimum. Therefore, it is easy for the algorithm to get trapped into one of these local optima, which may indeed be far away from the global optimum. Also, it is usually time-consuming--or even impossible--to demonstrate that the algorithm reached the global optimum or whether a feasible solution can be obtained. Another way of classifying an OP is by whether it is a smooth or a non-smooth one. Smooth optimization problems have smooth objective functions and constraints. A smooth function has derivatives of all orders and is differentiable. On the contrary, a non-smooth one has an objective function--or at least one constraint--that does not possess at least one of the properties of a smooth function. Figure 2 shows an example of a one-dimensional function which is neither smooth nor convex. From a combinatorial point of view, non-smooth OPs possess similar properties as non-convex OPs because they are time consuming to solve. The lack of derivative information makes it almost impossible to determine the direction in which the function is increasing or decreasing. Likewise, the solution space may also have several disjoint regions, each of which has its own local optimum. Unfortunately, non-convex and non-smooth OPs arise in several application domains, including telecommunication networks, economic load dispatch, portfolio optimization, vehicle routing, regression, or clustering problems. For instance, the minimum sum-of-squares clustering problem is solved by [PERSON] et al. [29] and by [PERSON] et al. [30]. Both papers formulate the clustering problem as a non-smooth and non-convex optimization problem and make use of incremental algorithms. However, the former is based on the difference of convex functions and the latter is based on the limited memory bundle method. Real world data sets are used to test both approaches, demonstrating numerically their efficiency compared to other incremental algorithms. Difference of convex functions are also used by [PERSON] et al. [31] to solve the nonparametric regression estimation problem. These authors propose an algorithm to minimize a non-convex and non-smooth empirical \(L_{2}\)-risk function. Synthetic and real-world data sets are used to test it. Compared to other algorithms, this approach is proved to be a good alternative in terms of computational time and several prediction indicators. Several studies have investigated the applicability of well-known metaheuristic approaches--such as tabu search, artificial bee colony optimization, or particle swarm optimization--to solve non-smooth and non-convex OPs [32].