Signomial problems - Revision history

Fall2024 Wiki Team18: Formatting

2024-12-16T02:35:17Z

Formatting

Fall2024 Wiki Team18: Fixed some formatting

2024-12-16T02:32:34Z

Fixed some formatting

← Older revision		Revision as of 22:32, 15 December 2024
Line 77:		Line 77:
	Metaheuristic algorithms provide approximate solutions for large-scale, non-convex problems. They are stochastic in nature and balance exploration and exploitation.		Metaheuristic algorithms provide approximate solutions for large-scale, non-convex problems. They are stochastic in nature and balance exploration and exploitation.

	==== ~~'''~~Genetic Algorithms (GA)~~'''~~ ====		==== Genetic Algorithms (GA) ====
	GA mimics natural selection through population evolution.<ref name=":5">Hastie, T., Tibshirani, R., The Elements of Statistical Learning. Springer, 2009.</ref>		GA mimics natural selection through population evolution.<ref name=":5">Hastie, T., Tibshirani, R., The Elements of Statistical Learning. Springer, 2009.</ref>

Line 89:		Line 89:
	# '''Iteration''': Repeat until the stopping criterion is met.		# '''Iteration''': Repeat until the stopping criterion is met.

	==== ~~'''~~Particle Swarm Optimization (PSO)~~'''~~ ====		==== Particle Swarm Optimization (PSO) ====
	PSO models a swarm of particles moving in the search space, updating their positions based on personal and global bests.<ref name=":5" /><ref name=":6">Murphy, K., Machine Learning: A Probabilistic Perspective. MIT Press, 2012.</ref>		PSO models a swarm of particles moving in the search space, updating their positions based on personal and global bests.<ref name=":5" /><ref name=":6">Murphy, K., Machine Learning: A Probabilistic Perspective. MIT Press, 2012.</ref>

Line 115:		Line 115:
	# Linearization:		# Linearization:
	#* Approximate the non-linear terms <math>5x^{-0.5}</math> and <math>10y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).		#* Approximate the non-linear terms <math>5x^{-0.5}</math> and <math>10y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).
	#* Using Taylor series expansion or first-order approximation:		#* Using Taylor series expansion or first-order approximation:
	<math>5x^{-0.5}\approx 5x_0^{-0.5} +(-2.5x_0^{-1.5})(x - x_0)</math>		<math>5x^{-0.5}\approx 5x_0^{-0.5} +(-2.5x_0^{-1.5})(x - x_0)</math>
	<math>10y^{1.2}\approx 10y_0^{1.2} +(12y_0^{0.2})(y - y_0)</math>.		<math>10y^{1.2}\approx 10y_0^{1.2} +(12y_0^{0.2})(y - y_0)</math>.

	# Convex Subproblem: Solve the resulting convex optimization problem with the linearized objective function and constraints: Minimize: <math>\hat{f}(x,y) = a + b(x - x_0) + c(y - y_0)</math>, where <math>a, b, c</math> are the coefficients obtained from the linearization.		# Convex Subproblem: Solve the resulting convex optimization problem with the linearized objective function and constraints: Minimize: <math>\hat{f}(x,y) = a + b(x - x_0) + c(y - y_0)</math>, where <math>a, b, c</math> are the coefficients obtained from the linearization.
	# Update Variables: Solve the convex subproblem to get a new solution (<math>x_1, y_1</math>). Repeat the linearization process at (<math>x_1, y_1</math>) until convergence.		# Update Variables: Solve the convex subproblem to get a new solution (<math>x_1, y_1</math>). Repeat the linearization process at (<math>x_1, y_1</math>) until convergence.
	# Optimal Solution: After a few iterations, the optimal solution is found:<math>x^=30,</math> <math>y^ = 20</math>.		# Optimal Solution: After a few iterations, the optimal solution is found:
			<math>x^=30,</math> <math>y^ = 20</math>.

	'''Final Cost''':		'''Final Cost''':
Line 141:		Line 143:
	# Linearization:		# Linearization:
	#* Approximate the non-linear terms <math>100x^{-0.5}</math> and <math>200y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).		#* Approximate the non-linear terms <math>100x^{-0.5}</math> and <math>200y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).
	#* Using Taylor series expansion or first-order approximation:		#* Using Taylor series expansion or first-order approximation:
	<math>100x^{-0.5}\approx 100x_0^{-0.5} +(-50x_0^{-1.5})(x - x_0)</math>		<math>100x^{-0.5}\approx 100x_0^{-0.5} +(-50x_0^{-1.5})(x - x_0)</math>
	<math>200y^{1.2}\approx 200y_0^{1.2} +(240y_0^{0.2})(y - y_0)</math>.		<math>200y^{1.2}\approx 200y_0^{1.2} +(240y_0^{0.2})(y - y_0)</math>.

	# Convex Subproblem: Solve the resulting convex optimization problem with the linearized objective function and constraints: Minimize: <math>\hat{f}(x,y) = a + b(x - x_0) + c(y - y_0)</math>, where <math>a, b, c</math> are the coefficients obtained from the linearization.		# Convex Subproblem: Solve the resulting convex optimization problem with the linearized objective function and constraints: Minimize: <math>\hat{f}(x,y) = a + b(x - x_0) + c(y - y_0)</math>, where <math>a, b, c</math> are the coefficients obtained from the linearization.
	# Update Variables: Solve the convex subproblem to get a new solution (<math>x_1, y_1</math>). Repeat the linearization process at (<math>x_1, y_1</math>) until convergence.		# Update Variables: Solve the convex subproblem to get a new solution (<math>x_1, y_1</math>). Repeat the linearization process at (<math>x_1, y_1</math>) until convergence.
	# Optimal Solution: After a few iterations, the optimal solution is found:<math>x^=60,</math> <math>y^ = 40</math>.		# Optimal Solution: After a few iterations, the optimal solution is found:
			<math>x^=60,</math> <math>y^ = 40</math>.

	'''Final Cost''':		'''Final Cost''':

Fall2024 Wiki Team18: Editing updates. Resolved all TA comments.

2024-12-16T02:29:36Z

Editing updates. Resolved all TA comments.

← Older revision		Revision as of 22:29, 15 December 2024
Line 54:		Line 54:
	Global optimization methods aim to find the global optimum of a non-convex problem, avoiding convergence to local optima. These methods include branch-and-bound, cutting-plane, and interval-based techniques.<ref name=":2" /><ref>Ben-Tal, A., Robust Optimization. Princeton University Press, 2009.</ref>		Global optimization methods aim to find the global optimum of a non-convex problem, avoiding convergence to local optima. These methods include branch-and-bound, cutting-plane, and interval-based techniques.<ref name=":2" /><ref>Ben-Tal, A., Robust Optimization. Princeton University Press, 2009.</ref>

	==== ~~'''~~Branch-and-Bound~~'''~~ ====		==== Branch-and-Bound ====
	This method divides the search space into smaller regions (branches) and evaluates bounds on the objective function to prune regions that cannot contain the global optimum.		This method divides the search space into smaller regions (branches) and evaluates bounds on the objective function to prune regions that cannot contain the global optimum.

Line 65:		Line 65:
	# '''Iteration''': Repeat branching, bounding, and pruning until convergence.		# '''Iteration''': Repeat branching, bounding, and pruning until convergence.

	==== ~~'''~~Cutting-Plane Techniques~~'''~~ ====		==== Cutting-Plane Techniques ====
	These methods iteratively refine a feasible region by adding hyperplanes (cuts) that exclude suboptimal solutions.<ref name=":0" /><ref name=":4">Grossmann, I.E., Advanced Nonlinear Programming. SIAM, 2015.</ref>		These methods iteratively refine a feasible region by adding hyperplanes (cuts) that exclude suboptimal solutions.<ref name=":0" /><ref name=":4">Grossmann, I.E., Advanced Nonlinear Programming. SIAM, 2015.</ref>

Line 175:		Line 175:
	Grossmann highlighted the application of signomial optimization in optimizing multi-echelon supply chains, where inventory holding and transportation costs followed non-linear patterns due to economies of scale.<ref name=":4" />		Grossmann highlighted the application of signomial optimization in optimizing multi-echelon supply chains, where inventory holding and transportation costs followed non-linear patterns due to economies of scale.<ref name=":4" />

	=== ~~'''~~Healthcare~~'''~~ ===		=== Healthcare ===
	Signomial optimization has been employed in healthcare applications such as optimizing treatment plans or medical imaging systems. These applications often involve non-linear relationships between variables like dosage levels, side effects, and treatment outcomes.		Signomial optimization has been employed in healthcare applications such as optimizing treatment plans or medical imaging systems. These applications often involve non-linear relationships between variables like dosage levels, side effects, and treatment outcomes.

	Nemirovski used signomial models in radiotherapy optimization, where the goal was to minimize radiation exposure to healthy tissues while ensuring effective tumor targeting under non-linear dose-response constraints.<ref>Nemirovski, A., Robust Optimization Techniques in Nonlinear Programming. Springer, 2010.</ref>		Nemirovski used signomial models in radiotherapy optimization, where the goal was to minimize radiation exposure to healthy tissues while ensuring effective tumor targeting under non-linear dose-response constraints.<ref>Nemirovski, A., Robust Optimization Techniques in Nonlinear Programming. Springer, 2010.</ref>

	=== ~~'''~~Aerospace~~'''~~ ===		=== Aerospace ===
	In aerospace, signomial optimization is used for trajectory design, system reliability assessments, and performance optimization. These problems often involve non-linear aerodynamic constraints and system dynamics.		In aerospace, signomial optimization is used for trajectory design, system reliability assessments, and performance optimization. These problems often involve non-linear aerodynamic constraints and system dynamics.

Fall2024 Wiki Team18: - Citations numbered by the order of their appearance. Can you provide more details on the Global Optimization Techniques and Metaheuristics approach that you mentioned. Please provide step-by-step calculation processes for the numerical examples. Please check some minor grammer issues in the file. GH Guoqing Hu at Fri Dec 6, 2024 9:03pmat Fri Dec 6, 2024 9:03pm Minor revision: For applications, please try to use coher

2024-12-16T02:27:05Z

- Citations numbered by the order of their appearance. Can you provide more details on the Global Optimization Techniques and Metaheuristics approach that you mentioned. Please provide step-by-step calculation processes for the numerical examples. Please check some minor grammer issues in the file. GH Guoqing Hu at Fri Dec 6, 2024 9:03pmat Fri Dec 6, 2024 9:03pm Minor revision: For applications, please try to use coher

Show changes

Fall2024 Wiki Team18: Added new sections, did not delete previous ones yet.

2024-12-15T22:56:12Z

Added new sections, did not delete previous ones yet.

Show changes

Fall2024 Wiki Team18: Author class

2024-12-15T21:13:21Z

Author class

← Older revision		Revision as of 17:13, 15 December 2024
Line 1:		Line 1:
	Author: Megan Paonessa (map465) (~~ChemE 6800~~ Fall 2024)		Author: Megan Paonessa (map465) (SYSEN 5800 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:29, 10 December 2024

2024-12-10T18:29:27Z

← Older revision		Revision as of 14:29, 10 December 2024
Line 1:		Line 1:
	Author: Megan Paonessa (ChemE 6800 Fall 2024)		Author: Megan Paonessa (map465) (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:17, 10 December 2024

2024-12-10T18:17:08Z

← Older revision		Revision as of 14:17, 10 December 2024
Line 1:		Line 1:
	Author: ~~Matthew Hantzmon~~ (~~Che_345 Spring 2015~~)		Author: Megan Paonessa (ChemE 6800 Fall 2024)

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

	=Introduction=		=Introduction=

Btantisujjatham: Created page with "Author: Matthew Hantzmon (Che_345 Spring 2015) =Introduction= Sigmoid problems are a class of optimization problems with the objective of maximizing the sum of multiple sigmo..."

2022-04-01T15:30:53Z

Created page with "Author: Matthew Hantzmon (Che_345 Spring 2015) =Introduction= Sigmoid problems are a class of optimization problems with the objective of maximizing the sum of multiple sigmo..."

New page

Author: Matthew Hantzmon (Che_345 Spring 2015)

=Introduction=
Sigmoid problems are a class of optimization problems with the objective of maximizing the sum of multiple sigmoid functions. They are defined by their limits at negative and positive infinity.
Similar to the unit step function the function approaches 1 as it approaches infinity and approaches -1 as it approaches negative infinity. Sigmoid functions are shaped like an “S”, having both a convex and concave portion. The concave attributes will make solving the problems require a non-linear optimization, increasing computational burden. Though sigmoid problems are harder to solve than ordinary convex programs, they have many useful real-world applications which have encouraged their development. Sigmoid problems have become especially useful in the creation of artificial neural networks that simulate learning. The functionality of sigmoid problems allow in statistical models and other artificial learning.

The S-shape of the individual sigmoid functions made them good representatives of economies of scale, or other situations where the supplier is facing a declining demand function and increased investment leads to a lower average cost to produce each good. Within the sigmoidal problem, the sigmoidal functions within the objective represent that initial increases in investment will increase profitability when there is excess demand at the current price. The inflection point in the sigmoidal functions represents the point where the marginal profit for producing another good becomes 0. At this point the decrease in marginal cost from investing in more production is matched by an equal decrease in willingness to pay by the marginal consumer. Past this point the function determines that increased investment will not increase profitability. These properties of the sigmoid functions allow them to be ideal representatives of situations where initial investment is profitable though a threshold is reached where no additional inputs will be profitable. Other situations that exhibit these characteristics and can be modeled with sigmoidal problems include election planning, lottery prize design, and bidding at an auction. Election planners always desire to find the locations where spending on advertising will have the greatest effect on election results. When designing a lotter, the company wants to design a prize value that encourages many people to buy tickets while still being net profitable for the lottery. At an auction, a bidder may not have enough capital to buy every item they may desire so it is important early on to not waste a disproportionate amount of money winning an item that is not important. A sigmoidal problem maximizing utility can help determine the threshold value to bid on each item.

=Sigmoidal Functions=
[[File:matt4.png|thumb|right|350px|Figure 1: Logistic Sigmoid Function]]
Generally, a sigmoid function is any function having an “S” shape. One portion of the function will be convex while the other portion will be concave. The most common example of the sigmoid function is the logistic function shown in figure 1. However, the definition of sigmoidal functions is very broad: Any function that has real values, one inflection point and has a bell shaped first derivative function. With this definition, all logistic functions, the error function, the cumulative distribution function and many more can be considered sigmoidal functions and may be included in the objective function of a sigmoidal problem.
In figure 1, the coefficient 1/c is the temperature constant. As the value of c increases in the sigmoid function, the sigmoid function will approach the shape of a step function.

=Sigmoidal Problems=
[[File:matt2.jpg|thumb|right|350px|Figure 2: "S" Shape Curve]]
In practice, sigmoid problems consist of an optimization where the objective function is the sum of a set of sigmoid functions. Each of the sigmoid functions only has one input variable that determines the output value. Unless a certain threshold of input value has been exceeded, usually the value of the sigmoid function will be very close to zero. As a result, the solution of a sigmoid problem will consist of all the function input values either being 0 or a number exceeding the sigmoid function threshold. This threshold is depicted as being near z in figure 2. When optimizing inputs to achieve a desired output, usually there is a scarcity of inputs that must be allocated optimally; otherwise there would be no cause for a problem. Thus, the solution of the optimization will exceed the threshold z in as many indexes as possible. Any indexes that were not able to reach z input usually would have an input of 0. This is because, below z total inputs, two functions each with one unit of input will always have a lower combined utility than one sigmoid function with two units of input.

==Applications of Sigmoidal Problems==
These characteristics of sigmoidal problems make them very useful for certain types of optimizations. In presidential election planning, it is always important to spend campaign advertising dollars in a way which will have the largest impact on electoral count. Since the format of our election is winner-take-all in each state, the states that have the tightest poll results would be the states where the smallest change in poll numbers would most greatly change the overall electoral count. If a campaign team were trying to optimize their advertising spending they would want to create an objective that illustrated how their advertising would have an effect on each state. The campaign would only want to spend money on states that have a feasible change of voting in favor of their candidate. Money spend on states eventually lost is completely wasted. Sigmoidal functions will behave in the same way, only recommending to spend money in a state if they can pass the threshold of getting a majority of voters. They will predict that it is better to spend a lot of money on one state they have a good chance to influence than spend half each on two states where they may end up losing both.

The same logic follows for why sigmoidal problems are useful for optimizing bidding within an auction. Utility is only gained when a desired item is won, so it is always important to set up a function that only calculates utility when the necessary bidding threshold has been passed. There is no use or utility gained from bidding half the value on every item, and sigmoidal functions would appropriately capture this fact.

Sigmoid functions can be very useful in situations where utility gained is not continuous based on proportion but is more of a binary either/or result. They are not as extreme of a binary result as a step function, and the fact that they are fully differentiable makes them much more easily solved. However, since they have concave portions, their solution is not as simple as a linear program and may require software or approximations.

Large arrays of sigmoid problems have also been combined to simulate an artificial neural networks. These neural networks are sets of sigmoid functions used to approximate interconnected neurons, which are very powerful in statistical modeling. The neural networks are created by the aggregation of sigmoidal functions using the back-propagation algorithm. The most common applications of the sigmoidal problems is the density problem. The density of a linear space with uniform convergence can be calculated for a compact set using Cybenko's approximation theorem.

==Solving Sigmoidal Problems==
[[File:matt3.jpg|thumb|right|350px|Figure 3: Concave Envelope]]
As one of the properties of a sigmoid function is concave portions, simple simplex optimization will not suffice. As computation power has increased in recent decades, solutions of sigmoidal problems has become much more feasible using software available online. Though, solutions with the appropriate software are fairly straightforward and simple, these sorts of problems can be highly difficult to solve by hand. They can rarely be solved at all in the original format and frequently need several creative approximations to leave a problem that is computable by hand.
One method that allows simpler by-hand computation is the creation of a convex envelope. Depicted in figure 3, the concave envelope is an approximation of the sigmoidal function that adds a linear portion where the function had been previously convex. This addition, greatly simplifies the function’s computational difficulty. However, it must be noticed, that this approximation will only give an upper bound on the solution as it is including area that it not part of the original constraints.
Even with function simplification and approximation, usually there is a large set of functions to be optimized. Depending on the level of approximation, the solution found may not even contain a relevant level of accuracy. In general, software will be the method of choice when dealing with sigmoidal problems.

=References=
1. J. Birge, F. Louveaux, Introduction to Stochastic Programming, Springer, 2011.

2. Udell, Madeline, and Stephen Boyd. "Maximizing a Sum of Sigmoids." Stanford University, May 2015. Web. May 2015. <http%3A%2F%2Fweb.stanford.edu%2F~udell%2Fdoc%2Fmax_sum_sigmoids>.

3. Srivastava, Vaibhav, and Francesco Bullo. "Knapsack Problems with Sigmoid Utilities." Princeton, July 2013. Web. May 2015. <http%3A%2F%2Fwww.princeton.edu%2F~vaibhavs%2Fpapers%2F2012d-sb>.

4. Rojas, R. "Backpropagation." SpringerReference (2011): n. pag. UBerlin. UBerlin. Web.

← Older revision		Revision as of 22:35, 15 December 2024
Line 27:		Line 27:

	<math>x_j > 0, </math> <math> j=1,...,n.</math>		<math>x_j > 0, </math> <math> j=1,...,n.</math>



	This formulation<ref name=":0" /><ref name=":1" /><ref name=":2">Nocedal, J., Wright, S.J., Numerical Optimization. Springer, 1999.</ref> allows for negative coefficients (), which differentiates it from posynomials in geometric programming that restrict coefficients to be positive. This flexibility makes signomial problems applicable to a wider range of non-convex optimization scenarios.		This formulation<ref name=":0" /><ref name=":1" /><ref name=":2">Nocedal, J., Wright, S.J., Numerical Optimization. Springer, 1999.</ref> allows for negative coefficients (), which differentiates it from posynomials in geometric programming that restrict coefficients to be positive. This flexibility makes signomial problems applicable to a wider range of non-convex optimization scenarios.
Line 116:		Line 114:
	#* Approximate the non-linear terms <math>5x^{-0.5}</math> and <math>10y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).		#* Approximate the non-linear terms <math>5x^{-0.5}</math> and <math>10y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).
	#* Using Taylor series expansion or first-order approximation:		#* Using Taylor series expansion or first-order approximation:
	<math>5x^{-0.5}\approx 5x_0^{-0.5} +(-2.5x_0^{-1.5})(x - x_0)</math>		<math>5x^{-0.5}\approx 5x_0^{-0.5} +(-2.5x_0^{-1.5})(x - x_0)</math>,
	~~<math>10y^{1.2}\approx 10y_0^{1.2} +(12y_0^{0.2})(y - y_0)</math>.~~

			<math>10y^{1.2}\approx 10y_0^{1.2} +(12y_0^{0.2})(y - y_0)</math>.
	# Convex Subproblem: Solve the resulting convex optimization problem with the linearized objective function and constraints: Minimize: <math>\hat{f}(x,y) = a + b(x - x_0) + c(y - y_0)</math>, where <math>a, b, c</math> are the coefficients obtained from the linearization.		# Convex Subproblem: Solve the resulting convex optimization problem with the linearized objective function and constraints: Minimize: <math>\hat{f}(x,y) = a + b(x - x_0) + c(y - y_0)</math>, where <math>a, b, c</math> are the coefficients obtained from the linearization.
	# Update Variables: Solve the convex subproblem to get a new solution (<math>x_1, y_1</math>). Repeat the linearization process at (<math>x_1, y_1</math>) until convergence.		# Update Variables: Solve the convex subproblem to get a new solution (<math>x_1, y_1</math>). Repeat the linearization process at (<math>x_1, y_1</math>) until convergence.
Line 144:		Line 142:
	#* Approximate the non-linear terms <math>100x^{-0.5}</math> and <math>200y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).		#* Approximate the non-linear terms <math>100x^{-0.5}</math> and <math>200y^{1.2}</math> at the current solution (<math>x_0, y_0</math>).
	#* Using Taylor series expansion or first-order approximation:		#* Using Taylor series expansion or first-order approximation:
	<math>100x^{-0.5}\approx 100x_0^{-0.5} +(-50x_0^{-1.5})(x - x_0)</math>		<math>100x^{-0.5}\approx 100x_0^{-0.5} +(-50x_0^{-1.5})(x - x_0)</math>,

	<math>200y^{1.2}\approx 200y_0^{1.2} +(240y_0^{0.2})(y - y_0)</math>.		<math>200y^{1.2}\approx 200y_0^{1.2} +(240y_0^{0.2})(y - y_0)</math>.