Quadratic Hill-climbing (analysis) - Revision history

WikiBot: Class name added

2013-05-31T04:15:32Z

Class name added

WikiBot: Link to plugin page

2013-05-07T03:52:05Z

Link to plugin page

WikiBot: Plugin name added

2013-05-06T04:48:03Z

Plugin name added

WikiBot: Space after icon

2013-04-23T10:03:35Z

Space after icon

WikiBot: Analysis icon added

2013-04-23T09:58:28Z

Analysis icon added

WikiBot: Adding provider-specific categories

2013-04-19T04:08:49Z

Adding provider-specific categories

WikiBot: Provider information added

2013-04-18T08:43:40Z

Provider information added

WikiBot: Protected "Quadratic Hill-climbing (analysis)": Autogenerated page (‎[edit=sysop] (indefinite))

2013-04-04T09:28:51Z

Protected "Quadratic Hill-climbing (analysis)": Autogenerated page (‎[edit=sysop] (indefinite))

WikiBot: Added 'Autogenerated pages' category

2013-04-04T09:28:50Z

Added 'Autogenerated pages' category

WikiBot: Automatic synchronization with BioUML

2013-04-04T08:25:02Z

Automatic synchronization with BioUML

New page

=== Minimization by quadratic Hill-climbing1 ===

A gradient method for minimazing general function -''H''(''x''), where variable ''x'' denotes the column vector of variables (''x''1,...,''x''''n''). This method rests on maximizing a quadratic approximation to the function ''H''(''x'') on a suitably chosen spherical region. Computational technique for maximization take the form of an iterative procedure. The method is specifically designed to work for functions which are not concave and for starting points which are not necessarily near a maximum.

Let us denote by ''F''''x'' the vector of first partial derivatives evaluated at ''x'' and by ''S''''x'' the symmetric (''n'' x ''n'') matrix of second partial derivatives evaluated at ''x''.

Assume that ''H''(''x'') admits of a second-order Taylor series expansion around a point ''a'' = (''a''1,...,''a''''n''):

{|
|-
|

:: [[File:Optimization-Quadratic-Hill-climbing-goldfeld1.png]]

|'''(1)'''
|}
where the subscripts indicate the point of evaluation.

The iterative procedure for finding the maximum of the function is, given point ''x'' ''p'' at which ''S''''x''''p'' and ''F''''x''''p'' are evaluated, to define the next point, ''x'' ''p''+1, as the maximum of the quadratic approximation (1) on a spherical region centered at ''x'' ''p''. Ideally, the region should be taken as large as possible provided that it is small enough that in the region the quadratic approximation is a satisfactory guide to the actual behavior of the function. The following procedure attempts to approximate this ideal.

Two distinct cases arise:

'''(a)''' ''F''''x''''p'' significantly different from 0. In this event we choose a number

{|
|-
|

:: [[File:Optimization-Quadratic-Hill-climbing-goldfeld2.png]]

|'''(2)'''
|}
where λ1 is the largest eigenvalue of ''S''''x''''p'', and ''R'' is a positive parameter determined by the following rule.

Let Δ''H'' be the actual change in the function due to the proposed Δ''x'' and let Δ''Q'' be the corresponding change in the quadratic approximation. Let ''z'' = Δ''H''/Δ''Q''. If ''z'' ≤ 0, the proposed Δ''x'' implies overshooting; it is therefore not accepted, ''R'' is increased by a factor of 4 and a new (''S'' - ''αI'')-1 is calculated. If ''z'' > 0 and close to unity (in practice, if ''z'' is between 0.7 and 1.3) ''R'' is decreased by multiplying ''R'' by a factor of 0.4. If ''z'' > 2, ''R'' is again increased by a factor of 4. For other values of ''z'' (0 ≤ ''z'' ≤ 0.7 and 1.3 ≤ ''z'' ≤ 2) the magnitude of the factor multiplying ''R'' is determined by linear interpolation between 0.4 and 4. We now take

:: [[File:Optimization-Quadratic-Hill-climbing-goldfeld3.png]]

or

:: [[File:Optimization-Quadratic-Hill-climbing-goldfeld4.png]]

according to whether ''α'' is positive or not. If ''α'' = 0 at this point, we generally directly computed the step size necessary to produce a positive ''α''. This typically saved a number of iterations.

Now ''x'' ''p''+1 is the maximum of the quadratic approximation to the function on a region ''B''''α'' of radius

:: [[File:Optimization-Quadratic-Hill-climbing-goldfeld5.png]]

with the center at ''x'' ''p''.

'''(b)''' ''F''''x''''p''is so near 0 that the length of the step taken is within a preset tolerance of 0. Then, if ''S''''x''''p'' is negative definite, the process is terminated and ''x'' ''p'' is accepted as the location of the maximum. If ''S''''x''''p'' is not negative definite, we are at a saddle point or at the bottom of a cylindrical valley. A step is taken along the eigenvector corresponding λ1 and the algorithm recycles in the usual manner.

One final feature, incorporated for reason of computational efficiency rather than theoretical elegance, was the introduction of a scalar ''h''''p'' into (2), writing it as

:: [[File:Optimization-Quadratic-Hill-climbing-goldfeld6.png]]

At each step the computation is first performed with ''h'' ''p'' = 1. If this gives an improvement in ''H''(''x''), ''h'' ''p'' is multiplied by a constant, which magnitude is a decreasing function of the absolute value of the angle between the current step and the immediately preceding step. Then the function is examined at the new point so obtained. This process is repeated until the function declines in which event the last step is accepted. It should be noted that these attempts at stretching the step are relatively cheap since they require only an evaluation of the function. This is in contrast to changes in ''α'' within each iteration which require reinversion of (''S''''x''''p'' − ''α'' ''I'').
==== References ====

# SM Goldfeld et al, "Maximization by Quadratic Hill-climbing". Econometric Research Program, Research Memorandum #72, January 19, 1965.

[[Category:Analyses]]
[[Category:Optimization (analyses group)]]

@@ Line 3: / Line 3: @@
 ;Provider
 :[[Institute of Systems Biology]]
 ;Plugin
 :[[Ru.biosoft.analysis.optimization (plugin)|ru.biosoft.analysis.optimization (Common methods of data optimization analysis plug-in)]]

@@ Line 4: / Line 4: @@
 :[[Institute of Systems Biology]]
 ;Plugin
-:ru.biosoft.analysis.optimization (Common methods of data optimization analysis plug-in)
+:[[Ru.biosoft.analysis.optimization (plugin)|ru.biosoft.analysis.optimization (Common methods of data optimization analysis plug-in)]]
 === Minimization by quadratic Hill-climbing<sup>1</sup> ===

@@ Line 3: / Line 3: @@
 ;Provider
 :[[Institute of Systems Biology]]
 === Minimization by quadratic Hill-climbing<sup>1</sup> ===

@@ Line 1: / Line 1: @@
 ;Analysis title
-:[[File:Optimization-Quadratic-Hill-climbing-icon.png]]Quadratic Hill-climbing
+:[[File:Optimization-Quadratic-Hill-climbing-icon.png]] Quadratic Hill-climbing
 ;Provider
 :[[Institute of Systems Biology]]

@@ Line 1: / Line 1: @@
 ;Analysis title
-:Quadratic Hill-climbing
+:[[File:Optimization-Quadratic-Hill-climbing-icon.png]]Quadratic Hill-climbing
 ;Provider
 :[[Institute of Systems Biology]]

@@ Line 67: / Line 67: @@
 [[Category:Analyses]]
 [[Category:Optimization (analyses group)]]
 [[Category:Autogenerated pages]]

← Older revision		Revision as of 08:43, 18 April 2013
Line 1:		Line 1:
		+	;Analysis title
		+	:Quadratic Hill-climbing
		+	;Provider
		+	:[[Institute of Systems Biology]]
		+
	=== Minimization by quadratic Hill-climbing<sup>1</sup> ===		=== Minimization by quadratic Hill-climbing<sup>1</sup> ===

← Older revision		Revision as of 09:28, 4 April 2013
Line 62:		Line 62:
	[[Category:Analyses]]		[[Category:Analyses]]
	[[Category:Optimization (analyses group)]]		[[Category:Optimization (analyses group)]]
		+	[[Category:Autogenerated pages]]