Nondifferentiable Optimization - Revision history

Fall2024 Wiki Team21: /* Subgradient Method */

2024-12-15T20:18:36Z

Subgradient Method

@@ Line 14: / Line 14: @@
 =Solution Methods=
-Solution of differentiable problems and differentiable cost functions can in general forms be solved with gradient based analytical methods such as the Kuhn-Tucker model and through numerical methods such as steepest descent and conjugate gradient. However the introduction of non-differentiable points in the function invalidates these methods, steepest descent cannot be calculated for a vertical line. A common method for solution of a non-differentiable cost function is through transformation into a non-linear programming model where all of the of new functions involved are differentiable such that solution is now possible through ordinary means. <br/>
+Solution of differentiable problems and differentiable cost functions can in general forms be solved with gradient based analytical methods such as the Kuhn-Tucker model and through numerical methods such as steepest descent and conjugate gradient. However the introduction of non-differentiable points in the function invalidates these methods, steepest descent cannot be calculated for a vertical line. A common method for solution of a non-differentiable cost function is through transformation into a non-linear programming model where all of the of new functions involved are differentiable such that solution is now possible through ordinary means.
 ==Simple Kink Case==
@@ Line 90: / Line 104: @@
 <br/>
 This new minimization formulation is now differentiable and easier to deal with, however it is only an approximation of the original equation which will become a better approximation as more constraints are added to the new model.
 ==Illustrative Example==

Fall2024 Wiki Team21: /* Convex Relaxation */

2024-12-14T00:01:28Z

Convex Relaxation

← Older revision		Revision as of 20:01, 13 December 2024
Line 71:		Line 71:
	'''Relaxation''':		'''Relaxation''':

	Reformulate g<math>g_i(x)</math> and <math>h_j(x) </math> into convex constraints )<math>\bar{g_i(x)}</math> and <math>\bar{h_j(x)}</math> to create:		Reformulate <math>g_i(x)</math> and <math>h_j(x) </math> into convex constraints )<math>\bar{g_i(x)}</math> and <math>\bar{h_j(x)}</math> to create:

	<math>\min(f(x))		<math>\min(f(x))

Fall2024 Wiki Team21: /* Introduction */

2024-12-13T23:59:49Z

Introduction

@@ Line 58: / Line 58: @@
 Return to step 2 to iterate until convergence.
 This method is not only guaranteed to converge but progress towards convergence is made with each iteration.
 ==Cutting Plane Methods==

SYSEN5800TAs at 18:41, 10 December 2024

2024-12-10T18:41:04Z

← Older revision		Revision as of 14:41, 10 December 2024
Line 1:		Line 1:
	Author: Kevin Afoakwah (ka475), Meghna Sen (ms3398)		Author: Kevin Afoakwah (ka475), Meghna Sen (ms3398) (ChemE 6800 Fall 2024)

	Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu		Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

SYSEN5800TAs at 18:40, 10 December 2024

2024-12-10T18:40:47Z

← Older revision		Revision as of 14:40, 10 December 2024
Line 1:		Line 1:
	~~This web page is a duplicate of https~~:~~//optimization.mccormick.northwestern.edu/index.php/Nondifferentiable_Optimization<br />~~		Author: Kevin Afoakwah (ka475), Meghna Sen (ms3398)
	~~Author Name: Nathanael Robinson <br/>~~
	~~Steward~~: ~~Dajun Yue and Fenqui You~~		Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

	=Background=		=Background=

Btantisujjatham at 15:04, 1 April 2022

2022-04-01T15:04:15Z

← Older revision		Revision as of 11:04, 1 April 2022
Line 1:		Line 1:
	This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Nondifferentiable_Optimization		This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Nondifferentiable_Optimization<br />
	Author Name: Nathanael Robinson <br/>		Author Name: Nathanael Robinson <br/>
	Steward: Dajun Yue and Fenqui You		Steward: Dajun Yue and Fenqui You

Btantisujjatham at 15:03, 1 April 2022

2022-04-01T15:03:58Z

← Older revision		Revision as of 11:03, 1 April 2022
Line 1:		Line 1:
			This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Nondifferentiable_Optimization
	Author Name: Nathanael Robinson <br/>		Author Name: Nathanael Robinson <br/>
	Steward: Dajun Yue and Fenqui You		Steward: Dajun Yue and Fenqui You

Btantisujjatham: /* Introduction */

2022-04-01T15:03:08Z

Introduction

← Older revision		Revision as of 11:03, 1 April 2022
Line 5:		Line 5:
	==Introduction==		==Introduction==
	Non-differentiable optimization is a category of optimization that deals with objective that for a variety of reasons is non differentiable and thus non-convex. The functions in this class of optimization are generally non-smooth. These functions although continuous often contain sharp points or corners that do not allow for the solution of a tangent and are thus non-differentiable. In practice non-differentiable optimization encompasses a large variety of problems and a single one-size fits all solution is not applicable however solution is often reached through implementation of the subgradient method. Non-differentiable functions often arise in real world applications and commonly in the field of economics where cost functions often include sharp points. Early work in the optimization of non-differentiable functions was started by Soviet scientists Dubovitskii and Milyutin in the 1960's and led to continued research by Soviet Scientists. The subject has been a continued field of study since with different theories and methods being applied to solution in different cases.		Non-differentiable optimization is a category of optimization that deals with objective that for a variety of reasons is non differentiable and thus non-convex. The functions in this class of optimization are generally non-smooth. These functions although continuous often contain sharp points or corners that do not allow for the solution of a tangent and are thus non-differentiable. In practice non-differentiable optimization encompasses a large variety of problems and a single one-size fits all solution is not applicable however solution is often reached through implementation of the subgradient method. Non-differentiable functions often arise in real world applications and commonly in the field of economics where cost functions often include sharp points. Early work in the optimization of non-differentiable functions was started by Soviet scientists Dubovitskii and Milyutin in the 1960's and led to continued research by Soviet Scientists. The subject has been a continued field of study since with different theories and methods being applied to solution in different cases.

	[[File:03_continuous_functions-112.gif\|A non-differentiable function with several "kinks".\|=]]		[[File:03_continuous_functions-112.gif\|A non-differentiable function with several "kinks".\|=]]

Btantisujjatham: /* \varepsilon-Subgradient Method */

2022-04-01T15:01:45Z

\varepsilon-Subgradient Method

← Older revision		Revision as of 11:01, 1 April 2022
Line 41:		Line 41:
	With this method the constraints won't be considered explicitly but rather the objective function will be minimized to the value <math> + \infty </math>.		With this method the constraints won't be considered explicitly but rather the objective function will be minimized to the value <math> + \infty </math>.
	This makes it such that the minimization of <math> g(.) </math> over set <math> X </math> is equal to finding the minimum of the extended real value function <math> f(x) = g(x) + \delta(x\|X) </math> where		This makes it such that the minimization of <math> g(.) </math> over set <math> X </math> is equal to finding the minimum of the extended real value function <math> f(x) = g(x) + \delta(x\|X) </math> where
	<math> \delta(.\|X) </math> is the indicator function of <math>X</math>.		<math> \delta(\|X) </math> is the indicator function of <math>X</math>.
	The solution will converge through a 4 step system, the basis of these steps lies a series of propositions which are further detailed in [1]. <br/>		The solution will converge through a 4 step system, the basis of these steps lies a series of propositions which are further detailed in [1]. <br/>
	Step 1: Select a vector <math> x_{\circ} </math> such that <math> f(x_{\circ}) < \infty </math>, a scalar <math> \varepsilon_{\circ} > 0 </math> and a scalar <math> a, 0 < a < 1 </math> . <br/>		Step 1: Select a vector <math> x_{\circ} </math> such that <math> f(x_{\circ}) < \infty </math>, a scalar <math> \varepsilon_{\circ} > 0 </math> and a scalar <math> a, 0 < a < 1 </math> . <br/>

Btantisujjatham: Created page with "Author Name: Nathanael Robinson
Steward: Dajun Yue and Fenqui You =Background= ==Introduction== Non-differentiable optimization is a category of optimization that deals..."

2022-04-01T14:59:37Z

Created page with "Author Name: Nathanael Robinson Steward: Dajun Yue and Fenqui You =Background= ==Introduction== Non-differentiable optimization is a category of optimization that deals..."

New page

Author Name: Nathanael Robinson 
Steward: Dajun Yue and Fenqui You

=Background=
==Introduction==
Non-differentiable optimization is a category of optimization that deals with objective that for a variety of reasons is non differentiable and thus non-convex. The functions in this class of optimization are generally non-smooth. These functions although continuous often contain sharp points or corners that do not allow for the solution of a tangent and are thus non-differentiable. In practice non-differentiable optimization encompasses a large variety of problems and a single one-size fits all solution is not applicable however solution is often reached through implementation of the subgradient method. Non-differentiable functions often arise in real world applications and commonly in the field of economics where cost functions often include sharp points. Early work in the optimization of non-differentiable functions was started by Soviet scientists Dubovitskii and Milyutin in the 1960's and led to continued research by Soviet Scientists. The subject has been a continued field of study since with different theories and methods being applied to solution in different cases.
[[File:03_continuous_functions-112.gif|A non-differentiable function with several "kinks".|=]]

==Cost Functions==
In many cases, particularly economics the cost function which is the objective function of an optimization problem is non-differentiable. These non-smooth cost functions may include discontinuities and discontinuous gradients and are often seen in discontinuous physical processes. Optimal solution of these cost functions is a matter of importance to economists but presents a variety of issues when using numerical methods thus leading to the need for special solution methods.
[[File:nonsmoothcostfunction.jpg|thumb|right|An example of a non-differentiable cost function such as one that may be seen in economics]]

=Solution Methods=
Solution of differentiable problems and differentiable cost functions can in general forms be solved with gradient based analytical methods such as the Kuhn-Tucker model and through numerical methods such as steepest descent and conjugate gradient. However the introduction of non-differentiable points in the function invalidates these methods, steepest descent cannot be calculated for a vertical line. A common method for solution of a non-differentiable cost function is through transformation into a non-linear programming model where all of the of new functions involved are differentiable such that solution is now possible through ordinary means. 

==Simple Kink Case==
[[File:kinkexample.png|thumb|right|An example of a two parameter kink approximation.]]
A common case of a non-differentiable function is the simple kink. The function is of the form: 
<math>Min \quad f(x) </math> 
<math>S.t. \quad x \in Q \subset R^n </math>

The function <math> f(x) </math> is non-differentiable because of several simple kinks which can be modeled by: 
<math> \gamma [f_i(x)] = max\{0,f_i(x)\} \qquad i \in I </math> 
 
If these simple kinks were removed the function would be differentiable across the entire domain. Some other types of non-differentiable objective functions can be modeled as simple kinks to allow the same type of solution. 
The approach to solution of the simple kink case is to approximate each of the non-differentiable kinks with a smooth function that will allow conventional solution to the entire problem. This requires that the kinks be the only factor that renders the function non-differentiable. A simple kink can be modeled by a two-parameter approximation,<math> \tilde{\gamma}[f(x), y, c] </math>, of the simple kink <math> \gamma [f(x)] </math> 
 
<math> \tilde{\gamma}[f(x), y, c] = \begin{cases} f(x) - (1-y)^2 /2c, & \text{if } (1-y)/c \le f(x), \\ yf(x) + \tfrac{1}{2}c[f(x)]^2, & \text{if } -y/c \le f(x) \le (1-y)/c \\ -y^2/2c, & \text{if } f(x) \le -y/c \end{cases} </math> 
Where y and c are parameters with
<math> 0 \le y \le 1, 0 < c </math> 
 
Each kink <math> \gamma_i </math> will be replaced in the function with its two-parameter approximation such the new <math> \tilde{f(x)} </math> function is differentiable with the parameters <math> c >0 </math> and <math> 0<y<1 </math>. The solution can now be iteratively solved by adjusting the parameters c and y and solving the optimization problem 
<math>Min \quad \tilde{f(x)} </math> 
<math> s.t. \quad x \in Q \subset X </math> 
 
A solution <math> x_k </math> to the approximated objective function will be obtained. The problem is now resolved with an updated parameter for <math> c </math> which is obtained by multiplying <math> \beta c_k </math> which <math> = c_{k+1} </math> where <math> \beta > 0. \quad y_{k+1} </math> can also be updated if necessary. And a new minimization carried out with the <math> k+1</math> case. The procedure can be repeated until a value of <math> f(x) </math> that is consistent with the <math> c </math> and <math> y </math> parameters is reached.

== <math>\varepsilon</math>-Subgradient Method==

If the non-differentiable function is convex and subject to convex constraints then the use of the <math>\varepsilon</math>-Subgradient Method can be applied. This method is a descent algorithm which can be applied to minimization optimization problems given that they are convex. 
With this method the constraints won't be considered explicitly but rather the objective function will be minimized to the value <math> + \infty </math>.
This makes it such that the minimization of <math> g(.) </math> over set <math> X </math> is equal to finding the minimum of the extended real value function <math> f(x) = g(x) + \delta(x|X) </math> where
<math> \delta(.|X) </math> is the indicator function of <math>X</math>.
The solution will converge through a 4 step system, the basis of these steps lies a series of propositions which are further detailed in [1]. 
Step 1: Select a vector <math> x_{\circ} </math> such that <math> f(x_{\circ}) < \infty </math>, a scalar <math> \varepsilon_{\circ} > 0 </math> and a scalar <math> a, 0 < a < 1 </math> . 
Step 2: Given <math> x_n, \quad \varepsilon_n > 0, </math> set <math> \varepsilon_{n+1} = a^k\varepsilon_n , </math> where <math> k </math> is the smallest non-negative integer such that
<math> 0 \not\in \delta_{\varepsilon_{n+1}}f(x^n) </math> 
Step 3: Find a vector <math> y_n </math> such that 
<math> \begin{align} sup \quad & \langle y_n , x^* \rangle < 0 \\
x^* \in \delta_{\varepsilon_{n+1}}f(x) & \\
\end{align}
</math>
 
Step 4: Set <math> x_{n+1} = x_n + \lambda_n y_n, </math> where <math> \lambda_n > 0 </math> is such that 
<math> f(x_n) - f(x_{n+1}) > \varepsilon_{n+1} </math> 
Return to step 2 to iterate until convergence.
This method is not only guaranteed to converge but progress towards convergence is made with each iteration.

==Cutting Plane Methods==
Cutting planes were first utilized for the convergence of convex non-differentiable equations. The application of cutting planes will use the subgradient inequality to change the function <math> f </math> by approximating it as 
<math> f(x) \cong \tfrac{max}{i \in I} f(x_i) + \xi_i^T(x-x_i) </math> 
 
Where <math> \xi_i^f , \quad i \in I </math> are subgradients of <math> f </math> at <math> x_i, \quad i \in I </math>. Thus, The original problem is now formulated as 
 
<math> \tfrac{min}{x} \{ \tfrac{max}{i \in I} f(x_i) + \xi_i^T(x-x_i) \} </math>
 
Which is equivalent to the new problem 
 
<math> Min \quad v </math> 
<math> s.t. \quad f(x_i) + \xi_i^T(x-x_i) \le v \quad \forall i \in I </math> 
 
This new minimization formulation is now differentiable and easier to deal with, however it is only an approximation of the original equation which will become a better approximation as more constraints are added to the new model.

==Subgradient Method==
The subgradient optimization method is among the most common methods for convergence of non-differentiable optimization problems. It extends the gradient methods used in smooth optimization but is more complicated as search direction of subgradients is not necessarily the same as improving direction. Details can be further enumerated in the Subgradient Optimization page in this Wiki Textbook.

==Illustrative Example==
A simple example of non-differentiable optimization is approximation of a kink origination from an absolute value function. The simple function <math> f = |x| </math>
is an example of a function that while continuous for an infinite domain is non-differentiable at <math> f(x) = 0 </math> due to the presence of a "kink" or point that will not allow for the solution of a tangent. Since the non-differentiable point of the function is known an approximation can be added to relax and smooth the function with parameter <math> t </math>. This new approximation can be modeled 
<math> \begin{cases}
-x & x \ge t, \\
\tfrac{x^2}{t} & -t \le x \le t, \\
x & x \ge t, \\
\end{cases} </math>

=References=

1. Bertsekas,D. Mitter, S. "A Descent Numerical Method for Optimization Problems with Nondifferentiable Cost Functionals*" Vol 11, No 4 of Siam Journal of Control, 1973. 
2. Bertsekas, D. "Nondifferentiable Optimization Via Approximation" Vol 1, No 25 of Mathematical Programming Study 3, 1975. 
3. Elhedhli, S. Goffin, J-L. Vial, J-P. "Nondifferentiable Optimization: Introduction, Applications and Algorithms" Encyclopedia of Optimization, 2000.