Subgradient optimization - Revision history

Fall2024 Team16 Wiki at 17:38, 15 December 2024

2024-12-15T17:38:12Z

← Older revision		Revision as of 13:38, 15 December 2024
Line 54:		Line 54:
	<math>\quad \lim_{k \to \infty} f^{(k)}_{\text{best}}-f*<\epsilon</math>		<math>\quad \lim_{k \to \infty} f^{(k)}_{\text{best}}-f*<\epsilon</math>

	This case however is slow and has poor performance. As such, ~~they are~~ largely used in specialized applications due to ~~their~~ simplicity and adaptability to specialized problem structures.		This case however is slow and has poor performance. As such, it is largely used in specialized applications due to the simplicity and adaptability for specialized problem structures.

	==Numerical Example==		==Numerical Example==

Fall2024 Team16 Wiki at 17:31, 15 December 2024

2024-12-15T17:31:46Z

← Older revision		Revision as of 13:31, 15 December 2024
Line 4:		Line 4:

	[[File:Subderivative_illustration.png\|right\|thumb\|A convex nondifferentiable function (blue) with red "subtangent" lines generalizing the derivative at the nondifferentiable point ''x''<sub>0</sub>.]]		[[File:Subderivative_illustration.png\|right\|thumb\|A convex nondifferentiable function (blue) with red "subtangent" lines generalizing the derivative at the nondifferentiable point ''x''<sub>0</sub>.]]
	The '''subgradient method''' is a simple algorithm for the optimization of non-differentiable functions, and it originated in the Soviet Union during the 1960s and 70s, primarily by the contributions of Naum Z. Shor (Sharma, Shashi). While the calculations for this approach are similar to that of the gradient method for differentiable functions, there are several key differences. First, as noted the subgradient method applies strictly to non-differentiable functions as it reduces to the gradient method when f is differentiable. Secondly the step size is fixed before the application of the algorithm rather than being determined “on-line” as in other approaches. Finally the subgradient method is not a descent method as the value of f can and often will increase.		The '''subgradient method''' is a simple algorithm for the optimization of non-differentiable functions, and it originated in the Soviet Union during the 1960s and 70s, primarily by the contributions of Naum Z. Shor (Sharma, Shashi). While the calculations for this approach are similar to that of the gradient method for differentiable functions, there are several key differences. First, as noted the subgradient method applies strictly to non-differentiable functions as it reduces to the gradient method when <math>f</math> is differentiable. Secondly the step size is fixed before the application of the algorithm rather than being determined “on-line” as in other approaches. Finally the subgradient method is not a descent method as the value of f can and often will increase.

	==Introduction==		==Introduction==
Line 68:		Line 68:


	[[File:SubGradientExampleChart.png\|~~350px~~\|thumb\|This graph illustrates the piecewise function, f(x).]]		[[File:SubGradientExampleChart.png\|450px\|thumb\|This graph illustrates the piecewise function, f(x).]]

	'''Table 1: Raw Data'''<br/>		'''Table 1: Raw Data'''<br/>

Fall2024 Team16 Wiki at 03:17, 15 December 2024

2024-12-15T03:17:52Z

← Older revision		Revision as of 23:17, 14 December 2024
Line 7:		Line 7:

	==Introduction==		==Introduction==
	The subgradient method is more computationally expensive when compared to Newton's method but applicable to a wider range of problems. Additionally, due to the method’s schema when applied numerically the memory requirements are smaller than other methods allowing larger problems to be approached. Further the combination of the subgradient method with the primal dual decomposition can simplify some applications to a distributed algorithm. ~~<br/>~~		The subgradient method is more computationally expensive when compared to Newton's method but applicable to a wider range of problems. Additionally, due to the method’s schema when applied numerically the memory requirements are smaller than other methods allowing larger problems to be approached. Further the combination of the subgradient method with the primal dual decomposition can simplify some applications to a distributed algorithm.

	==Algorithm Discussion==		==Algorithm Discussion==
	'''Basics:'''		'''Basics:'''

Fall2024 Team16 Wiki: /* Application */

2024-12-15T03:11:50Z

Application

← Older revision		Revision as of 23:11, 14 December 2024
Line 91:		Line 91:
	'''Step 6:''' Optimal solution is determined		'''Step 6:''' Optimal solution is determined

	==~~Application~~==		==Applications==
	Subgradient methods are generally for solving non-differentiable optimization problems. This algorithm is used in data science applications such as machine learning whenever the gradient method is not sufficient. It is also found in applications like engineering where it is utilized for problems in robotics and power systems (Licio, Romao).		Subgradient methods are generally for solving non-differentiable optimization problems. This algorithm is used in data science applications such as machine learning whenever the gradient method is not sufficient. It is also found in applications like engineering where it is utilized for problems in robotics and power systems (Licio, Romao).

	In some applications, the combination of the subgradient method and the primal dual decomposition can simplify to a distributed algorithm. This is shown in detail in Adaptive Subgradient Methods for Online Learning and Stochastic Optimization (Duchi et al.). The experiments outlined focus on different data sets such as text and images, and then use the subgradient method in order to flexibly be applied in various geometries. This adaptive characteristic provides unique benefits such as improved performance for identification of predictive attributes when compared to non-adaptive alternatives.		In some applications, the combination of the subgradient method and the primal dual decomposition can simplify to a distributed algorithm. This is shown in detail in Adaptive Subgradient Methods for Online Learning and Stochastic Optimization (Duchi et al.). The experiments outlined focus on different data sets such as text and images, and then use the subgradient method in order to flexibly be applied in various geometries. This adaptive characteristic provides unique benefits such as improved performance for identification of predictive attributes when compared to non-adaptive alternatives.

	Some commercial tools like MATLAB and optimization solvers like Gurobi, FICO, and MOSEK contain the subgradient method algorithm. There are also open-source solvers like Couenee and GLPK that support this function. Alternatively, CVXPY is an open-source Python embedded modeling language that contains subgradient methods in its library.		Some commercial tools like MATLAB and optimization solvers like Gurobi, FICO, and MOSEK contain the subgradient method algorithm. There are also open-source solvers like Couenee and GLPK that support this function. Alternatively, CVXPY is an open-source Python embedded modeling language that contains subgradient methods in its library.

	==Conclusion==		==Conclusion==

Fall2024 Team16 Wiki: /* Numerical Example */

2024-12-15T03:09:40Z

Numerical Example

← Older revision		Revision as of 23:09, 14 December 2024
Line 68:		Line 68:

	[[File:SubGradientExampleChart.png\|350px\|thumb\|This graph illustrates the piecewise function, f(x).]]		[[File:SubGradientExampleChart.png\|350px\|thumb\|This graph illustrates the piecewise function, f(x).]]


	'''Table 1: Raw Data'''<br/>		'''Table 1: Raw Data'''<br/>

Fall2024 Team16 Wiki: /* Numerical Example */

2024-12-15T03:08:49Z

Numerical Example

← Older revision		Revision as of 23:08, 14 December 2024
Line 67:		Line 67:


	~~'''Figure 1: Objective Function'''<br/>~~		[[File:SubGradientExampleChart.png\|350px\|thumb\|This graph illustrates the piecewise function, f(x).]]
	[[File:SubGradientExampleChart.png\|~~600px~~]]

Fall2024 Team16 Wiki: /* References */

2024-12-15T03:04:47Z

References

← Older revision		Revision as of 23:04, 14 December 2024
Line 104:		Line 104:

	==References==		==References==
	~~TBD~~		1. Boyd, Stephen. “Subgradient Methods.” web.stanford.edu, 2014, https://web.stanford.edu/class/ee364b/lectures/subgrad_method_notes.pdf <br/>
			2. Duchi, John, et al. “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization.” Journal of Machine Learning Research, 11 7 2011, https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf <br/>
			3. Sharma, Shashi. “Analysis on Sub-Gradient and Semi-Definite Optimization.” Journal of Advances and Scholarly Researches in Allied Education, vol. 12, no. 2, Jan. 2017 <br/>
			4. Romao, Licio, et al. “Subgradient Averaging for Multi-Agent Optimisation with Different Constraint Sets.” ScienceDirect, Pergamon, 2 June 2021, www.sciencedirect.com/science/article/abs/pii/S0005109821002582 <br/>
			5. Shor, N. Z. "Minimization Methods for Non-differentiable Functions". Springer Series in Computational Mathematics. Springer, 1985 <br/>

Fall2024 Team16 Wiki: /* Numerical Example Adding Chart and Table

2024-12-15T02:59:32Z

/* Numerical Example Adding Chart and Table

← Older revision		Revision as of 22:59, 14 December 2024
Line 65:		Line 65:

	7 < x, 3x + 9\end{align} </math>		7 < x, 3x + 9\end{align} </math>


			'''Figure 1: Objective Function'''<br/>
			[[File:SubGradientExampleChart.png\|600px]]


			'''Table 1: Raw Data'''<br/>
			[[File:SubGradientExampleTable.PNG]]

Fall2024 Team16 Wiki: /* Algorithm Discussion */ Improvement to step size formatting

2024-12-15T02:46:30Z

Algorithm Discussion: Improvement to step size formatting

← Older revision		Revision as of 22:46, 14 December 2024
Line 31:		Line 31:
	The step size for this algorithm is determined externally to the algorithm itself. There are a number of methods for determining the step size:<br/>		The step size for this algorithm is determined externally to the algorithm itself. There are a number of methods for determining the step size:<br/>
	*Constant step size:		*Constant step size:
	<math>\alpha_k = \alpha</math>		**<math>\alpha_k = \alpha</math>

	*Constant step length:		*Constant step length:
	<math>\alpha_k = \frac{\gamma}{\\| g^{(k)} \\|_2} \quad </math> which gives <math>\quad \\| x^{(k+1)} - x^{(k)} \\|_2 = \gamma</math>		**<math>\alpha_k = \frac{\gamma}{\\| g^{(k)} \\|_2} \quad </math> which gives <math>\quad \\| x^{(k+1)} - x^{(k)} \\|_2 = \gamma</math>

	*Square Summable but not summable step size:		*Square Summable but not summable step size:
	<math>\alpha_k \geq 0, \quad \sum_{k=1}^\infty \alpha_k^2 < \infty, \quad \sum_{k=1}^\infty \alpha_k = \infty</math>		**<math>\alpha_k \geq 0, \quad \sum_{k=1}^\infty \alpha_k^2 < \infty, \quad \sum_{k=1}^\infty \alpha_k = \infty</math>

	*Non Summable diminishing:		*Non Summable diminishing:
	<math>\alpha_k \geq 0, \quad \lim_{k \to \infty} \alpha_k = 0, \quad \sum_{k=1}^\infty \alpha_k = \infty</math>		**<math>\alpha_k \geq 0, \quad \lim_{k \to \infty} \alpha_k = 0, \quad \sum_{k=1}^\infty \alpha_k = \infty</math>

	*Non Summable diminishing step lengths:		*Non Summable diminishing step lengths:
	<math>\gamma_k \geq 0, \quad \lim_{k \to \infty} \gamma_k = 0, \quad \sum_{k=1}^\infty \gamma_k = \infty</math>		**<math>\gamma_k \geq 0, \quad \lim_{k \to \infty} \gamma_k = 0, \quad \sum_{k=1}^\infty \gamma_k = \infty</math>

	Polyak’s Step length: <math>\alpha_k = \frac{f(x^{(k)}) - f^}{\\| g^{(k)} \\|_2^2}</math>		*Polyak’s Step length:
			*<math>\alpha_k = \frac{f(x^{(k)}) - f^}{\\| g^{(k)} \\|_2^2}</math>

	'''Convergence:'''		'''Convergence:'''

Fall2024 Team16 Wiki: /* References */ Removing Previous References

2024-12-15T02:41:02Z

References: Removing Previous References

← Older revision		Revision as of 22:41, 14 December 2024
Line 95:		Line 95:

	==References==		==References==
	~~1. Akgul, M. "Topics in Relaxation and Ellipsoidal Methods", volume 97 of Research Notes in Mathematics. Pitman, 1984. <br/>~~		TBD
	~~2. Bazaraa, M. S., Sherali, H. D. "On the choice of step size in subgradient optimization." European Journal of Operational Research 7.4, 1981 <br/>~~
	~~3. Bertsekas, D. P. "Nonlinear Programming", (2nd edition), Athena Scientific, Belmont, MA, 1999. <br/>~~
	~~4. Goffin, J. L. "On convergence rates of subgradient optimization methods." Mathematical Programming 13.1, 1977. <br/>~~
	~~5. Shor, N. Z. "Minimization Methods for Non-differentiable Functions". Springer Series in Computational Mathematics. Springer, 1985. <br/>~~
	~~6. Shor, N. Z. "Nondifferentiable Optimization and Polynomial Problems". Nonconvex Optimization and its Applications. Kluwer, 1998. <br/>~~