SGM-01.htm

Steepest Gradient Method

Direct differential gradient method

Climbing hill method

Example without constraint

Objective function: ZQ = CX2 * X ^ 2 + CY2 * Y ^ 2 + CX * X + CY * Y + CK

Constraint area: Nothing

Example 1

Objective function: Z = 9 * X ^ 2 + 4 * Y ^ 2 - 72 * X - 64 * Y

Objective function: ZQ
	CX2	CY2	CX	CY	CK
Example 1	9	4	-72	-64	0

Make ZQ , Max, or, Min

Function of 1 step:

q = S * p

, where, p= grad(ZQ), that is,

= [δz/δx , δz/δy]

S = constant: Example 1: 0.001

Start point, X, Y: 0, 0

Epsilon for stop: EP = 0.00001,

Repeat times for stop: NN= 10000

Answer 1

ZQ = 9 * (X-4) ^ 2 + 4*(Y-8) ^ 2 - 400

δz/δx = 18*(X-4)

δz/δy = 8*(Y-8)

ZQ min = -400

		X	Y	Z
Final value(Optimal value)		4.00	8.00	400.00
Repeat times	J =	10001

See sgm-01.xls: sgm-1-a

Example with constraint

Objective function: ZQ = CX2 * X ^ 2 + CY2 * Y ^ 2 + CX * X + CY * Y + CK

Constraint area: G = G (X, Y) = KX * X + KY * Y + KC <= 0

Example 2

Objective function: Z = 9 * X ^ 2 + 4 * Y ^ 2 - 72 * X - 64 * Y

Constraint area: G = 2 * X + Y - 8 <= 0

Objective function: ZQ
	CX2	CY2	CX	CY	CK
Example 2	9	4	-72	-64	0

Constraint area: G

	KX	KY	KC
Example 2	2	1	-8

Make ZQ , Max, or, Min

Function of 1 step:

q = S * p - u * r

where, p= grad(ZQ), that is,

= [δZQ/δx, δZQ/δy]

r = grad(G) , that is,

= [δG/δx, δG/δy]

u: u = 0 if G <= 0, u = G(X,Y) if G > 0

S = constant:

S = 0.001 if G <= 0,

S = 0 if G > 0

Answer 2

ZQ = 9 * (X-4) ^ 2 + 4*(Y-8) ^ 2 - 400

δz/δx = 18*(X-4)

δz/δy = 8*(Y-8)

δG/δx = 2

δG/δy = 1

		X	Y	Z
Final value(Optimal value)		1.44	5.12	307.84
Repeat times	J =	29395

see sgm-01.xls: sgm-2-a

return go to top

2004/8/18