# A Novel Approach for Solving Nonsmooth Optimization Problems with Application to Nonsmooth Equations

Authors: Hamid Reza Erfanian; M. H. Noori Skandari; A. V. Kamyad
Journal: Journal of Mathematics
 (2013)

---

## Abstract

We present a new approach for solving nonsmooth optimization problems and  a system of nonsmooth equations which is based on generalized derivative. For this purpose, we introduce the first order of generalized Taylor expansion of nonsmooth functions and replace it with smooth functions. In other words, nonsmooth function is approximated by a piecewise linear function based on generalized derivative. In the next step, we solve smooth linear optimization problem whose optimal solution  is an approximate solution of main problem. Then, we apply the results for solving system of nonsmooth equations. Finally, for efficiency of our approach some numerical examples have been presented.


---

## Body

## 1. Introduction

As we all know, many problems of considerable practical importance can be related to the solution of nonsmooth optimization of problems (NSOPs) and system of nonsmooth equations. In general, optimization a function is one of the most important problems of real life and plays a fundamental role in mathematics and its applications in the other disciplines such as control theory, optimal control, engineering, and economics.Nonsmooth optimization is one of the research areas in computational mathematics, applied mathematics, and engineering design optimization and also is widely used in many of practical problems.   It is necessary to know that several important methods for solving difficult smooth problems lead directly to the need to solve nonsmooth problems, which are either smaller in dimension or simpler in structure. For instance, decomposition methods for solving very large scale smooth problems produce lower-dimensional nonsmooth problems; penalty methods for solving constrained smooth problems result in unconstrained nonsmooth problems; nonsmooth equation methods for solving smooth variational inequalities and smooth nonlinear complementarity problems give arise to systems of nonsmooth equations (see [1]).The well-known methods for nonsmooth optimization include subgradient method, cutting-planes method, analytic center cutting-planes method, bundle method, trust region method, and bundle trustering method (see [2]).Note that the most difficult type of optimization problem to solve is a nonsmooth problem. Nonsmooth optimization refers to the more general problem of minimizing functions that are typically not differentiable at their minimizers. The focus of this paper is the numerical solution of NSOPs and system of nonsmooth equations. The techniques for solving the minimization problems and nonsmooth equations are closely related.The outline of the paper is as follows. In Section2, we introduce the reader to a new generalized derivative (GD) for one variable and multivariable functions (see Kamyad et al. [3]). A new approach for NSOP based on GD is studied in Section 3. Also, using the last section, an approach for solving system of nonsmooth equations is considered in Section 4. Some conclusive remarks are given in Section 5. Finally, we present some examples of the efficiency of our approach in Section 6.


## 2. Preliminaries

In this section, we present definitions and results concerning with GD, which are needed in the remainder of the paper. Since the early 1960s several generalized theories of differentiation have been proposed by different authors. A first major step in this direction came with the dissertation of Rockafellar [4], who introduced subgradients for convex functions. Another breakthrough occurred when Clarke [5] found a way of extending Rockafellar’s ideas to the broader class of lower semicontinuous, proper functions. This line of ideas has given rise to an extensive amount of research, continuing to the present (see [6]). It is commonly recognized that these GDs are not practical and applicable for solving problems. We mainly utilize the new GD of Kamyad et al. [3] for nonsmooth functions. This kind of GD is particularly helpful and practical when dealing with nonsmooth continuous and discontinuous functions and it can be easily computed. In what follows, let us now devote just two short sections to the GD of Kamyad et al. in two cases, one and multivariable functions.


### 2.1. GD of One-Variable Nonsmooth Functions

LetV={vk(·):vk(x)=sinkπx:x∈[0,1],k=1,2,…}. For function f(x) on [0,1],  we define the following functional optimization problem:
(1)MinimizeJ(g(·))=∑k=1∞|∫01vk(x)g(x)dx-λk|subjectto∫si-δsi+δ|f(x)-f(si)-(x-si)g(si)|dx≤εδ2,g(·)∈C[0,1],si∈(i-1m,im),i=1,2,…,m,
where  vk(·)∈V, λk=-∫01vk′(x)f(x)dx, k=1,2,3,… and ε, δ are positive sufficiently small numbers. Moreover, si∈((i-1)/m,i/m), i=1,2,…,m are arbitrary numbers. For instance, we can choose the middle points, that is,  si=(2i-1)/2m, i=1,2,…m.Theorem 1 (see [3]).
Letf(·)∈C1[0,1] and  g*(·)  be the optimal solution of the functional optimization problem (1). Then g*(·)∈C1[0,1] and f′(·)=g*(·).Definition 2.
Letf(·) be a continuous nonsmooth function on the interval [0,1] and g*(·) be the optimal solution of the functional optimization problem (1). We denote the generalized first derivative (GFD) of f(·)  by ∂xf(·)  and define as  ∂xf(·)=g*(·).Remark 3 (see [3]).
Note that iff(·) is a smooth function on [0,1] then the ∂xf(·) in Definition 2 isf′(·). Further, if f(·) is a nonsmooth integrable function on [0,1] then GFD of f(·) is an approximation for first derivative of f(·).
In what follows, the problem (1) is approximated to the following finite dimensional problem (see [3]):
(2)MinimizeJ(g(·))=∑k=1N|∫01vk(x)g(x)dx-λk|subjectto∫si-δsi+δ|f(x)-f(si)-(x-si)g(si)|dx≤εδ2,g(·)∈C[0,1],si∈(i-1m,im),i=1,2,…,m,
where N is a given large number. We assume that  gi=g(si), fi1=f(si-δ), fi2=f(si+δ), and fi=f(si) for all i=1,2,…,m. In addition, we choose the arbitrary points si∈((i-1)/m,i/m), i=1,2,…,m. By trapezoidal and midpoint integration rules, problem (2) can be approximated to the following problem in which  g1,g2,…,gm are its unknown variables:
(3)Minimize∑k=1N|δ∑i=1mvkigi-λk|subject to|fi1-fi+δgi|+|fi2-fi-δgi|≤εδ,i=1,2,…,m.Lemma 4.
Let pairs(vi*,ui*), i=1,2,…,m be the optimal solutions ofthe following LP problem:
(4)Minimizevi,ui∑i=1mvisubject  tovi≥ui,vi≥-ui,vi≥0,ui∈I.
Then  ui*, i=1,2,…,m are the optimal solutions of the following nonlinear programming (NLP) problem: Minimizeu∈I∑i=1m|ui| where I⊂ℝ is a compact set.Proof.
Since(vi*,ui*), i=1,2,…,m are the optimal solutions of the LP problem, so they satisfy the constraints. Thus we have vi*≥ui* and vi*≥-ui* for i=1,2,…,m. Hence, |ui*|≤vi*, i=1,2,…,m and so ∑i=1m|ui*|≤∑i=1mvi*. Now, let there exist u-i*∈I,i=1,2,…,m such that ∑i=1m|u-i*|<∑i=1m|ui*|. Define  v-i*=|u-i*|  for i=1,2,…,m. Then  v-i*≥u-i* and v-i*≥-u-i*. Moreover, ∑i=1mv-i*=∑i=1m|u-i*| and hence
(5)∑i=1mv-i*=∑i=1m|u-i*|<∑i=1m|ui*|<∑i=1mvi*.
So ∑i=1mv-i*<∑i=1mvi*; this is a contradiction.Now, by Lemma4 and techniques of mathematical programming, problem (3) may be converted to the following equivalent LP problem in which  gi, i=1,…,m, μk, k=1,2,…,N, and ωi, zi, ui, vi for i=1,2,…,m are decision variables of the problem:
(6)Minimize∑k=1Nμksubjectto-μk+δ∑i=0mvkigi≤λk,k=1,2,…,N-μk-δ∑i=0mvkigi≤-λk,k=1,2,…,N(ui+vi)+(ωi+zi)≤εδ,i=1,2,…,mui-vi-δgi=fi1-fi,i=1,2,…,mωi-zi+δgi=fi2-fi,i=1,2,…,mωi,zi,ui,vi,μk≥0,k=1,2,…,N;i=1,2,…,m.Remark 5.
Note thatε and δ must be selected as sufficiently small numbers and arbitrary points si∈((i-1)/m,i/m),  i=1,2,…,m can be chosen as arbitrary numbers.Remark 6.
Note that ifgi*, i=1,…,m are optimal solutions of problem (6), then we have  ∂xf(si)≈gi*,   i=1,2,…,m.


### 2.2. GD of Multivariable Functions

In this section, we are going to introduce functional optimization problems that their optimal solutions are the partial derivatives of smooth function onΩ⊂ℝn.  First, we select arbitrary (but fixed) index i∈{1,2,…,n} and calculate the partial differentiation of f(·):Ω→ℝ respect to xi. Without loss of generality, assume Ω=[0,1]n and define  Ω- as follows:
(7)Ω-={(x1,…,xi-1,xi+1,…,xn):xi∈[0,1]}⊂[0,1]n-1.Now, selectN as a sufficiently large number and part Ω- to the similar grids Ω-j, j=1,2,…,Nn-1 such that these grids cover set Ω-. In the next step, we consider arbitrary points sj∈Ω-j, j=1,2,…,Nn-1  as sj=(sj1,…,sji-1,sji+1,…,sjn). Moreover, we define the following vector for all sj∈Ω-j:
(8)rj(t)=(sj1,…,sji-1,t,sji+1…,sjn),t∈[0,1],j=1,2,…,Nn-1.Letf(·):Ω→ℝ and define hj(t)=f(rj(t)),   t∈[0,1] for j=1,2,…,Nn-1. Now, suppose ε>0 and δ>0 are two sufficiently small given numbers and N∈ℕ   be sufficiently large number. For given continuous function f:Ω→ℝ, we define the following functional optimization problem for any j=1,2,…,Nn-1:
(9)Minimizeg(·)∈C[0,1],Jj(g(·))=∑k=1∞|∫01vk(t)g(t)dt-λj,k|,subjectto∫wp-δwp+δ|hj(t)-hj(wp)-(t-wp)g(wp)|dx≤εδ2,
where wp∈((p-1)/N,p/N), p=1,2,…,N are fixed and arbitrary points; for example, it can be chosen by wp=(2p-1)/2N, p=1,2,…,N.Also,vk(·)∈V, λj,k=-∫01vk′(t)hj(t)dt and for all  j=1,2,…,Nn-1, k=1,2,3,….Theorem 7.
Letf∈C1(ℝ) and gj*(.) be the optimal solution of the functional optimization problem Pj, for j=1,2,…,Nn-1 defined by (9). Then gj*(·)∈C1([0,1])(10)∂f∂xi(sj1,…,sji-1,t,sji+1,…,sjn)=gj*(t),t∈[0,1],
where sj=(sj1,…,sji-1,sji+1,…,sjn)∈Ω-j, j=1,2,…,Nn-1.Proof.
(see [3]).Now, the generalized partial derivative (GPD) of nonsmooth functionf:Ω⊂ℝn→ℝ may be defined as follows.Definition 8.
Leti∈{1,2,…,n} be a fixed and arbitrary index and  sj=(sj1,…,sji-1,sji+1,…,sjn)∈Ω-j,  j=1,2,…,Nn-1. Moreover, let function f:Ω⊂ℝn→ℝ be a continuous nonsmooth function and gj*(·), j=1,2,…,Nn-1 is the optimal solution of the functional optimization problem (9). We denote the GPD of  f(·) with respect to variable xi by ∂if and define as ∂if(sj1,…,sji-1,t,sji+1,…,sjn)=gj*(t), t∈[0,1].Remark 9.
Note that iff:Ω⊂ℝn→ℝ is a smooth function then for fixed index i∈{1,2,…,n} and sj=(sj1,…,sji-1,sji+1,…,sjn)∈Ω-j,  j=1,2,…,Nn-1,
(11)∂if(sj1,…,sji-1,t,sji+1,…,sjn)=∂f∂xi(sj1,…,sji-1,t,sji+1,…,sjn),t∈[0,1].
Further, if f(·) is a continuous nonsmooth function, then the GPD of f(·) with respect to variable xi is an approximation for first derivative of function f(·) with  respect to variable xi.
However, the optimization problem (9) is an infinite dimensional problem and hence it is approximated as the following finite dimensional problems:
(12)MinimizeJj(g(·))=∑k=1M|∫01vk(t)g(t)dt-λji,k|subjectto∫wp-δwp+δ|hji(t)-hji(wp)-(t-wp)g(wp)|Minimizedx≤εδ2,g(·)∈Cggg(·)∈C[0,1],wp∈(p-1N,pN),g(·)∈C[0,1],p=1,2,…,N,
where M is a given large number. We assume that vkp=vk(wp), gp=g(wp), hj1,p=hj(wp-δ), hj2,p=hj(wp+δ) and hjp=hj(wp), for all p=1,2,…,N. In addition, we choose the arbitrary points wp∈((p-1)/N,p/N), p=1,2,…,N.
Similar to the Section 2.1, problem (12) may be converted to the following equivalent finite linear programming (FLP) problem which gjp, p=1,…,m, μk, k=1,2,…,N, and  yp, zp, up, qp  for  p=1,2,…,M are decision variables of the problem:
(13)Minimize∑k=1Mμksubjectto-μk+δ∑p=1Nvkpgjp≤λj,k,-μk-δ∑p=1Nvkpgjp≤λji,k,(up+qp)+(yp+zp)≤εδ,up-qp-δgjp=hj1,p-hjp,yp-zp+δgjp=hj2,p-hjp,yp,zp,up,qp,μk≥0,k=1,2,…,M,p=1,2,…,N,
where  λjk for  i=1,2,…,n, j=1,2,…,Nn, and k=1,2,3,…,M satisfy the relations
(14)λj,k=-∫01vk′(t)hj(t)dt.Remark 10.
Note that ifgjp*, p=1,…,N are optimal solutions of problem (13), then  ∂if(sj1,…,sji-1,wp,sji+1,…,sjn)=gjp*  for  p=1,…,N.


## 2.1. GD of One-Variable Nonsmooth Functions

LetV={vk(·):vk(x)=sinkπx:x∈[0,1],k=1,2,…}. For function f(x) on [0,1],  we define the following functional optimization problem:
(1)MinimizeJ(g(·))=∑k=1∞|∫01vk(x)g(x)dx-λk|subjectto∫si-δsi+δ|f(x)-f(si)-(x-si)g(si)|dx≤εδ2,g(·)∈C[0,1],si∈(i-1m,im),i=1,2,…,m,
where  vk(·)∈V, λk=-∫01vk′(x)f(x)dx, k=1,2,3,… and ε, δ are positive sufficiently small numbers. Moreover, si∈((i-1)/m,i/m), i=1,2,…,m are arbitrary numbers. For instance, we can choose the middle points, that is,  si=(2i-1)/2m, i=1,2,…m.Theorem 1 (see [3]).
Letf(·)∈C1[0,1] and  g*(·)  be the optimal solution of the functional optimization problem (1). Then g*(·)∈C1[0,1] and f′(·)=g*(·).Definition 2.
Letf(·) be a continuous nonsmooth function on the interval [0,1] and g*(·) be the optimal solution of the functional optimization problem (1). We denote the generalized first derivative (GFD) of f(·)  by ∂xf(·)  and define as  ∂xf(·)=g*(·).Remark 3 (see [3]).
Note that iff(·) is a smooth function on [0,1] then the ∂xf(·) in Definition 2 isf′(·). Further, if f(·) is a nonsmooth integrable function on [0,1] then GFD of f(·) is an approximation for first derivative of f(·).
In what follows, the problem (1) is approximated to the following finite dimensional problem (see [3]):
(2)MinimizeJ(g(·))=∑k=1N|∫01vk(x)g(x)dx-λk|subjectto∫si-δsi+δ|f(x)-f(si)-(x-si)g(si)|dx≤εδ2,g(·)∈C[0,1],si∈(i-1m,im),i=1,2,…,m,
where N is a given large number. We assume that  gi=g(si), fi1=f(si-δ), fi2=f(si+δ), and fi=f(si) for all i=1,2,…,m. In addition, we choose the arbitrary points si∈((i-1)/m,i/m), i=1,2,…,m. By trapezoidal and midpoint integration rules, problem (2) can be approximated to the following problem in which  g1,g2,…,gm are its unknown variables:
(3)Minimize∑k=1N|δ∑i=1mvkigi-λk|subject to|fi1-fi+δgi|+|fi2-fi-δgi|≤εδ,i=1,2,…,m.Lemma 4.
Let pairs(vi*,ui*), i=1,2,…,m be the optimal solutions ofthe following LP problem:
(4)Minimizevi,ui∑i=1mvisubject  tovi≥ui,vi≥-ui,vi≥0,ui∈I.
Then  ui*, i=1,2,…,m are the optimal solutions of the following nonlinear programming (NLP) problem: Minimizeu∈I∑i=1m|ui| where I⊂ℝ is a compact set.Proof.
Since(vi*,ui*), i=1,2,…,m are the optimal solutions of the LP problem, so they satisfy the constraints. Thus we have vi*≥ui* and vi*≥-ui* for i=1,2,…,m. Hence, |ui*|≤vi*, i=1,2,…,m and so ∑i=1m|ui*|≤∑i=1mvi*. Now, let there exist u-i*∈I,i=1,2,…,m such that ∑i=1m|u-i*|<∑i=1m|ui*|. Define  v-i*=|u-i*|  for i=1,2,…,m. Then  v-i*≥u-i* and v-i*≥-u-i*. Moreover, ∑i=1mv-i*=∑i=1m|u-i*| and hence
(5)∑i=1mv-i*=∑i=1m|u-i*|<∑i=1m|ui*|<∑i=1mvi*.
So ∑i=1mv-i*<∑i=1mvi*; this is a contradiction.Now, by Lemma4 and techniques of mathematical programming, problem (3) may be converted to the following equivalent LP problem in which  gi, i=1,…,m, μk, k=1,2,…,N, and ωi, zi, ui, vi for i=1,2,…,m are decision variables of the problem:
(6)Minimize∑k=1Nμksubjectto-μk+δ∑i=0mvkigi≤λk,k=1,2,…,N-μk-δ∑i=0mvkigi≤-λk,k=1,2,…,N(ui+vi)+(ωi+zi)≤εδ,i=1,2,…,mui-vi-δgi=fi1-fi,i=1,2,…,mωi-zi+δgi=fi2-fi,i=1,2,…,mωi,zi,ui,vi,μk≥0,k=1,2,…,N;i=1,2,…,m.Remark 5.
Note thatε and δ must be selected as sufficiently small numbers and arbitrary points si∈((i-1)/m,i/m),  i=1,2,…,m can be chosen as arbitrary numbers.Remark 6.
Note that ifgi*, i=1,…,m are optimal solutions of problem (6), then we have  ∂xf(si)≈gi*,   i=1,2,…,m.


## 2.2. GD of Multivariable Functions

In this section, we are going to introduce functional optimization problems that their optimal solutions are the partial derivatives of smooth function onΩ⊂ℝn.  First, we select arbitrary (but fixed) index i∈{1,2,…,n} and calculate the partial differentiation of f(·):Ω→ℝ respect to xi. Without loss of generality, assume Ω=[0,1]n and define  Ω- as follows:
(7)Ω-={(x1,…,xi-1,xi+1,…,xn):xi∈[0,1]}⊂[0,1]n-1.Now, selectN as a sufficiently large number and part Ω- to the similar grids Ω-j, j=1,2,…,Nn-1 such that these grids cover set Ω-. In the next step, we consider arbitrary points sj∈Ω-j, j=1,2,…,Nn-1  as sj=(sj1,…,sji-1,sji+1,…,sjn). Moreover, we define the following vector for all sj∈Ω-j:
(8)rj(t)=(sj1,…,sji-1,t,sji+1…,sjn),t∈[0,1],j=1,2,…,Nn-1.Letf(·):Ω→ℝ and define hj(t)=f(rj(t)),   t∈[0,1] for j=1,2,…,Nn-1. Now, suppose ε>0 and δ>0 are two sufficiently small given numbers and N∈ℕ   be sufficiently large number. For given continuous function f:Ω→ℝ, we define the following functional optimization problem for any j=1,2,…,Nn-1:
(9)Minimizeg(·)∈C[0,1],Jj(g(·))=∑k=1∞|∫01vk(t)g(t)dt-λj,k|,subjectto∫wp-δwp+δ|hj(t)-hj(wp)-(t-wp)g(wp)|dx≤εδ2,
where wp∈((p-1)/N,p/N), p=1,2,…,N are fixed and arbitrary points; for example, it can be chosen by wp=(2p-1)/2N, p=1,2,…,N.Also,vk(·)∈V, λj,k=-∫01vk′(t)hj(t)dt and for all  j=1,2,…,Nn-1, k=1,2,3,….Theorem 7.
Letf∈C1(ℝ) and gj*(.) be the optimal solution of the functional optimization problem Pj, for j=1,2,…,Nn-1 defined by (9). Then gj*(·)∈C1([0,1])(10)∂f∂xi(sj1,…,sji-1,t,sji+1,…,sjn)=gj*(t),t∈[0,1],
where sj=(sj1,…,sji-1,sji+1,…,sjn)∈Ω-j, j=1,2,…,Nn-1.Proof.
(see [3]).Now, the generalized partial derivative (GPD) of nonsmooth functionf:Ω⊂ℝn→ℝ may be defined as follows.Definition 8.
Leti∈{1,2,…,n} be a fixed and arbitrary index and  sj=(sj1,…,sji-1,sji+1,…,sjn)∈Ω-j,  j=1,2,…,Nn-1. Moreover, let function f:Ω⊂ℝn→ℝ be a continuous nonsmooth function and gj*(·), j=1,2,…,Nn-1 is the optimal solution of the functional optimization problem (9). We denote the GPD of  f(·) with respect to variable xi by ∂if and define as ∂if(sj1,…,sji-1,t,sji+1,…,sjn)=gj*(t), t∈[0,1].Remark 9.
Note that iff:Ω⊂ℝn→ℝ is a smooth function then for fixed index i∈{1,2,…,n} and sj=(sj1,…,sji-1,sji+1,…,sjn)∈Ω-j,  j=1,2,…,Nn-1,
(11)∂if(sj1,…,sji-1,t,sji+1,…,sjn)=∂f∂xi(sj1,…,sji-1,t,sji+1,…,sjn),t∈[0,1].
Further, if f(·) is a continuous nonsmooth function, then the GPD of f(·) with respect to variable xi is an approximation for first derivative of function f(·) with  respect to variable xi.
However, the optimization problem (9) is an infinite dimensional problem and hence it is approximated as the following finite dimensional problems:
(12)MinimizeJj(g(·))=∑k=1M|∫01vk(t)g(t)dt-λji,k|subjectto∫wp-δwp+δ|hji(t)-hji(wp)-(t-wp)g(wp)|Minimizedx≤εδ2,g(·)∈Cggg(·)∈C[0,1],wp∈(p-1N,pN),g(·)∈C[0,1],p=1,2,…,N,
where M is a given large number. We assume that vkp=vk(wp), gp=g(wp), hj1,p=hj(wp-δ), hj2,p=hj(wp+δ) and hjp=hj(wp), for all p=1,2,…,N. In addition, we choose the arbitrary points wp∈((p-1)/N,p/N), p=1,2,…,N.
Similar to the Section 2.1, problem (12) may be converted to the following equivalent finite linear programming (FLP) problem which gjp, p=1,…,m, μk, k=1,2,…,N, and  yp, zp, up, qp  for  p=1,2,…,M are decision variables of the problem:
(13)Minimize∑k=1Mμksubjectto-μk+δ∑p=1Nvkpgjp≤λj,k,-μk-δ∑p=1Nvkpgjp≤λji,k,(up+qp)+(yp+zp)≤εδ,up-qp-δgjp=hj1,p-hjp,yp-zp+δgjp=hj2,p-hjp,yp,zp,up,qp,μk≥0,k=1,2,…,M,p=1,2,…,N,
where  λjk for  i=1,2,…,n, j=1,2,…,Nn, and k=1,2,3,…,M satisfy the relations
(14)λj,k=-∫01vk′(t)hj(t)dt.Remark 10.
Note that ifgjp*, p=1,…,N are optimal solutions of problem (13), then  ∂if(sj1,…,sji-1,wp,sji+1,…,sjn)=gjp*  for  p=1,…,N.


## 3. Nonsmooth Optimization Problems

The focus of this paper is the following NSOP:(15)Minx∈Ωf(x),
where the objective function f:Ω→ℝ is assumed to be nonsmooth function and the feasible set  Ω⊆ℝn is a compact set. Throughout the whole paper we assume that there exists a solution for problem (15). NSOP has been used in many of branches of sciences such as engineering, economics, and mathematics. An increasing number of practical problems require minimizing a nonsmooth, nonconvex function on a convex set, including image restoration, signal reconstruction, variable selection, optimal control, stochastic equilibrium problems, and spherical approximations. Also, a number of constrained optimization problems can be reformulated as problem (15) by using exact penalty methods (see [7]). However, many well-known optimization algorithms lack effectiveness and efficiency in dealing with nonsmooth, nonconvex objective functions. Furthermore, for non-Lipschitz continuous functions, the Clarke generalized gradients [8] cannot be used directly in the analysis. Further, smooth approximations for optimization problems have been studied for decades, including complementarity problems, variational inequalities, second order cone complementarity problems, semidefinite programming, semi-infinite programming, optimal control, and eigenvalue optimization (see [9]).A well known way to seek numerical solution of problem (15) is to replace it by a suitable piecewise linear function. With this linearization we can construct a piecewise linear approximation to the NSOP.In this paper, we describe a class of approximations which are constructed as piecewise linear functions based on GD of nonsmooth functions.Without less of generality, we firstly letΩ=[0,1] be a closed interval and let us take a partition of Ω,
(16)0=x0<x1<⋯<xi-1<xi<⋯<xn=1,
where  xi=x0+iδ,  i=0,1,…,n  and  δ>0  is a sufficiency small number. In addition, we select mid points si∈(xi-1,xi), i=1,2,…,n. In order to derive piecewise linear approximations, we introduce the generalized first order Taylor expansion of continuous nonsmooth function f(x) on Ωi=[xi-1,xi], i=1,2,…,n based on the GD as follow:
(17)f(x)≅fi(x)=f(si)+(x-si)∂xf(si),x∈[xi-1,xi],i=1,2,…,n.Moreover, we can approximate functionf(x) on interval [0,1] as follows:
(18)f(x)≅∑i=1nfi(x)χ[xi-1,xi](x),x∈[0,1].
We restrict our treatment to first order generalized derivative for obtaining a practical and useful general approach.  In this connection, we note that fi(x) is a linear approximation for nonsmooth function f(x) on [xi-1,xi].Theorem 11.
Letf(x) be a continuous nonsmooth function on the interval Ω=[0,1] and ε,δ>0 are sufficiency small numbers. The best linear approximation for function f(x) on interval [xi-1,xi], i=1,2,…,n,  in passing points (si,f(si)),   i=1,2,…,n, is function fi(x), i=1,2,…,n defined by (17).Proof.
Letφ(·)∈C[0,1], and define
(19)μiφ(x)=f(si)+(x-si)φ(si),x∈[xi-1,xi],i=1,2,…,n.
Now, assume that αiφ=∥f(·)-μiφ(·)∥[xi-1,xi]  where  ∥K(·)∥[xi-1,xi]=∫xi-1xi|K(t)|dt.  Since ε,δ>0  are sufficiency small numbers, we have  εδ<αiφ. On the other hand, by constraints of problem (1),  ∥f(·)-fi(·)∥[xi-1,xi]≤εδ2. Thus
(20)∥f(·)-fi(·)∥[xi-1,xi]<∥f(·)-μiφ(·)∥[xi-1,xi],i=1,2,…,n
and this shows that the best linear approximation for function f(x) on interval [xi-1,xi] in passing points (si,f(si)),   i=1,2,…,n,  is function fi(x).The approximation (17) will be used in nonsmooth optimization approach in the next part. The next theorem indicates how to find minimum of nonsmooth function in our approach.Theorem 12.
Letf(x) be a nonsmooth function on the interval Ω=[0,1] and ε,δ>0 are sufficiency small numbers. Then
(21)Minx∈[0,1]f(x)=Limn→∞(Mini=1,2…,n(Minx∈[xi-1,xi]fi(x))),
where fi(x), i=1,2,…,n,  is defined by (17).Proof.
Ifn  tends to infinity then by definition of points xj, j=1,2,…,n we have δ→0. So by the constraints of the problem (2), we have ∥f(·)-fj(·)∥[xj-1,xj]≤εδ2. Hence, Limn→∞∥f(·)-fj(·)∥[xj-1,xj]=0 and we can write Limn→∞fj(·)=f(·) for j=1,2,…,n. So for x∈[0,1], there exits an index j∈{1,2,…,n} such that fj(x)=∑i=1nfi(x)χ[xi-1,xi](x). Thus, achieve the following relation  Limn→∞(∑i=1nfi(x)χ[xi-1,xi](x))=f(x). Now, assume that f(x*)=Minx∈[0,1]f(x). So
(22)Limn→∞(∑i=1nfi(x*)χ[xi-1,xi](x*))=Minx∈[0,1]f(x),
On the other hand, there is an indexk∈{1,2,…,n} such that x*∈[xk-1,xk] and
(23)fk(x*)=∑i=1nfi(x*)χ[xi-1,xi](x*)=Mini=1,2,…,nMinx∈[xi-1,xi]fi(x).
Hence, by the relations (22) and (23) we conclude
(24)Limn→∞(Mini=1,2…,n(Minx∈[xi-1,xi]fi(x)))=Minx∈[0,1]f(x).For the main result of Theorem12, we can approximate the problem (15) with the following problem:
(25)Mini=1,2,…,nMinx∈[xi-1,xi](f(si)+(x-si)∂xf(si)),
where n is a sufficiency big number.A well known way to seek optimal solution of the problem (25) is to convert it to a min-max problem based on the following remark.Remark 13.
Finding the minimum of functionf on a certain domain is really the same as finding the maximum of  -f on that domain.
So for attaining to feasible solution of problem (25) we have the following problem:
(26)Mini=1,2,…,nMaxx∈[xi-1,xi](-f(si)-(x-si)∂xf(si)).
Now, we assume
(27)z=Maxx∈[xi-1,xi](-f(si)-(x-si)∂xf(si)),∀i=1,2,…,n.
It has become clear that the problem (26) is equivalent to the following linear programming problem:
(28)Minzsubjecttoz≥-f(zi)-(zi-si)∂if(si)xi-1≤zi≤xi,i=1,2,…,n,
where the decision variables are  zi, i=1,2,…,n and z. After solving the LP problem (28), we obtain optimal solutions  zi*, i=1,2,…,n and z*. Then, we choose zp* such that z*=-f(zp*)-(zp*-sp)∂pf(sp).  Now, x*=zp* is an approximate optimal solution for main problem (15).
Note that in the connection of multivariable functionsf:Ω⊂ℝm→ℝ,  also above-mentioned theorems hold for problem (15). Without less of generality, we let Ω=[0,1]m. Here, we can approximate function f(·) with a linear approximation as follows:
(29)f(x1,…,xm)≅fi(x1,…,xm)=f(si1,…,sim)+(x1-si1)∂x1f(si1,…,sim)+⋯+(xm-sim)∂xmf(si1,…,sim),
where ∂xif(si1,…,sim),    i=1,2,…,n  are the GDs of  f(·)  with respect to xi in point  (si1,si2,…,sim)∈[0,1]m.  Here, we select similar sets  Δi, i=1,2,…,n  such that  ∪i=1nΔi=[0,1]m.  Moreover, similar to Theorem 11, we can prove that
(30)Minx∈[0,1]mf(x1,…,xm)=Mini=1,2…,nMinx∈Δifi(x1,…,xm).
Similar to one-variable case, we obtain a LP problem to the approximate optimal solution of nonsmooth problemMinx∈Ω=[0,1]mf(x) as follows:
(31)Minzsubjecttoz≥-f(si1,…,sim)z≥-(zi1-si1)∂x1f(si1,…,sim)z≥-⋯-(zim-sim)∂xmf(si1,…,sim),zim∈Δi,i=1,2,…,n,
where the decision variables are  zij, for i=1,2,…,n, j=1,2,…,m and  z.  After solving the LP  Problem (31), we obtain optimal solutions  zij*  for i=1,2,…,n, j=1,2,…,m and z*. Then, we choose  zpj*, j=1,2,…,m  such that
(32)z*=-f(sp1,…,sim)-(zp1*-sp1)∂x1f(sp1,…,spm)-⋯-(zpm*-spm)∂xmf(sp1,…,spm).
Now, (x1*,…,xm*)=(zp1*,…,zpm*) is an approximate optimal solution for main problem (15).


## 4. System of Nonsmooth Equations

We consider the system ofn nonsmooth equations with n variables
(33)G(x)=0,
where G:Ω⊂ℝn→ℝn is assumed to be nonsmooth function. We assume that there exists a unique solution x*∈Ω such that G(x*)=0. Many efforts have been done for solving nonsmooth system of equations (for more details refer [10, 11]). These methods are very useful but they are not simple and practical in the nonsmooth case. Here, according to Section 3, we introduce an approach based on GD which is useful for nonsmooth equations.In what follows, we firstly convert the problem (33) to the corresponding NLP problem and in the next step, by the linearization method of previous section, we obtain an LP problem for approximating solution of the problem (33). Define the following NLP problem:
(34)Minx∈Ω∑i=1nGi2(x),
where  G(x)=(G1(x),G2(x),…,Gn(x))T and  x=(x1,x2,…,xn).Lemma 14.
Letx*=(x1*,x2*,…,xn*)∈Ω be the optimal solution of the problem (34).  Then x*=(x1*,x2*,…,xn*) is a solution for problem (33), that is, G(x*)=0.Proof.
It is trivial thatG12(x)+G22(x)+⋯+Gn2(x)≥0,   x∈Ω,  and
(35)Minx∈Ω∑i=1nGi2(x)≥0.
On the other hand, there is an  x-∈Ω such that G(x-)=0 and hence Gi(x-)=0,i=0,1,…,n.  So we have
(36)0=∑i=1nGi2(x-)=Minx∈Ω∑i=1nGi2(x),
hence x-=x*  and  G(x*)=0.Now, we can replace the problem (33) with the NLP problem (34). Here, we assume f(x)=∑i=1nGi2(x),  x∈Ω, and corresponding to the Section 3, use the linearization method based on GD and solve the LP problem (28) for the one variable functions or the problem (31) for the multivariable functions (for more details of GD, see Sections 2.1 and 2.2).


## 5. Numerical Examples

In this section, we present some numerical results in order to illustrate the performance of established approach. Three NSOPs and three nonsmooth equations were solved; some of them are multidimensional problems. One of the aims is to show the efficiency of our approach in the connections with nonsmooth functions.Example 1.
Consider the following problem of one variable of nonsmooth optimization:(37)Minx∈[0,1]f(x)=||x-0.25|-0.5|.
The exact solution of Example 1 is x*=0.75, f*=0 in x∈[0,1].  The function f(x) is nondifferentiable at x=0.25,0.75 in the interval [0,1] and according to the problem (28), the acheived approximate solution for n=50 is x*=0.750000, f*=4.2974512887×10-12. Here,  the function f(x) is illustrated in Figure 1 and the GD of  f(x) has been shown in Figure 2.Figure 1
The graph off(x) of Example 1.Figure 2
The graph of GD of Example1.Example 2.
Consider the following NSOP which has been introduced by Zhang et al. in [2]:
(38)Minx∈[-10,10]f(x)=|x-14|+|sin(π(1+x-14))|+1.
According to Figure3, the exact global minimizer is x*=1. The comparison results of our approach and [2] show that our approach has acceptable precision and accuracy (see Table 1). The GD of  f(x) has been shown in Figure 4.Table 1
Comparison of the Zhang’s method and our approach.
Zhang’s method (NFFM1)
Zhang’s  method (NFFM2)
Our approach (n=200)
Our Approach (n=400)
Exact solution
0.999832
1.000041
1.000017
0.999997
1Figure 3
The graph off(x) of Example 2.Figure 4
The graph of GD of Example2.Example 3.
Let the following NSOP:(39)Minx∈[0,1],y∈[0,1]f(x,y)=xy2-|sinπ(y-0.5)|-y|x-0.5|,
which has its minimum at  x*=0, y*=1 (see Figure 5) and the minimum exact value of f(x,y) is f*=-1.5. According to the problem (31), produces the following approximate solutions for different values of N (see Table 2). Figures 6 and 7 have been shown in the graph of GD of  f(x,y) with respect to x and y.Table 2
Numerical results of Example3.
N
Approximate optimal solution
Approximate optimal value
20
x
=
0.02500000
f
(
x
,
y
)
=
-
1
.
43627670
y
=
0.97500000
100
x
=
0.00500000
f
(
x
,
y
)
=
-
1.48745150
y
=
0.99500000
200
x
=
0.00250000
f
(
x
,
y
)
=
-
1.49373789
y
=
0.99750000
500
x
=
0.00100000
f
(
x
,
y
)
=
-
1.49749806
y
=
0.99900000Figure 5
The graph of functionf(·,·) of Example 3.Figure 6
The graph of GD off(·,·)  with respect to  x  for Example 3.Figure 7
The graph of GD off(·,·)  with respect to y for Example 3.Example 4.
Consider the following nonsmooth equation(40)f(x)=1-|0.5-cos(πx)|=0,x∈[0,1].
The above problem has an exact root x*=2/3≈0.6666667. According to the problem (34), the approximate solution for  n=100 is x=0.66499999 and the approximate f(x)  for this root is f(0.66499999)=0.004541.  Figures 8 and 9 have been shown in the graph of function  f(x) and the graph of GD of  f2(x), respectively.Figure 8
The graph of functionf(x) of Example 4.Figure 9
The graph of GD of Example4.Example 5.
Consider the following nonsmooth equation:(41)f(x)=|x+0.25|-|x-0.75|+0.5|sinπx|=0,x∈[-1,1].
The functionf(x) is nondifferentiable at x=-0.25,0,0.75   in the interval [-1,1].  It can be viewed as the place of the root in Figure 10 and the achived approximate solution for n=400 is x=0.1424999. Also the approximate value function for this solution is f(0.1424999)=0.001436. The graph of GD of f2(x) is illustrated in Figure 11.Figure 10
The graph of functionf(x) of Example 5.Figure 11
The graph of GD of Example5.Example 6.
Consider the following system of nonsmooth equations:(42)f1(x,y)=|x-y|+|x-0.5|=0,f2(x,y)=|x-0.75|-y+0.25=0,
where  x∈[0,1], y∈[0,1]. The exact solution of the above system is  x*=y*=0.5 (see Figure 12).
According to the problem (34), f(x,y)=f12(x,y)+f22(x,y) and so we solve Minf(x,y). Table 3 presents the results of approximate solution for different values of N.Table 3
Numerical results of Example6.
N
Approximate optimal solution
Approximate optimal value
50
x
=
0.49000000
f
1
(
x
,
y
)
=
0.01000000
y
=
0.49000000
f
2
(
x
,
y
)
=
0.02000000
100
x
=
0.49500000
f
1
(
x
,
y
)
=
0.00500000
y
=
0.49500000
f
2
(
x
,
y
)
=
0.01000000
200
x
=
0.49750000
f
1
(
x
,
y
)
=
0.00250000
y
=
0.49750000
f
2
(
x
,
y
)
=
0.00500000
500
x
=
0.49900000
f
1
(
x
,
y
)
=
0.00100000
y
=
0.49900000
f
2
(
x
,
y
)
=
0.00200000Figure 12
The graph off(x,y) of Example 6.


## 6. Conclusions

We have shown that NSOP can be approximated by a linear optimization problem whose  solution can be used for that problem. In this approach, we utilize new GD which it is practical and useful for nonsmooth functions. Also by this approach, it is possible to solve system of nonsmooth equations. The results of numerical examples imply that our approach is useful with respect to  results and more applicable to computational assignments.



---

*Source: 750834-2013-02-12.xml*