Published by Dimitris Kougioumtzis · Updated
Follow the negative gradient of f(x,y)=(x-a)^2+(y-b)^2, with a stated learning rate, gradient tolerance and iteration limit.
Evaluate the gradient of f(x,y)=(x-a)^2+(y-b)^2 and move in its negative direction with a constant learning rate. Measure the gradient norm after each step and stop only when it meets tolerance or the iteration budget ends.
When to use Gradient descent on a quadratic surface
Exploring how learning rate affects convergence, oscillation and progress on a known convex objective surface.
Choosing an alternative
The quadratic has a known minimizer and closed-form iterates, making it useful for checking a numerical implementation. Simulated annealing explores a nonconvex grid and can accept uphill moves; this method follows the local negative gradient.
Worked example: input and state changes
Example input
2.5,2.5,0,0,0.2,0.00001,32
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Start: f=12.5, gradient norm 7.0710678118654755.
State at this checkpoint
{ "values": [ 0, 1, 2 ], "active": [ 2 ], "kind": "graph", "points": [ [ -0.5, -0.5 ], [ 3, 3 ], [ 2.5, 2.5 ] ], "nodeLabels": [ "", "", "(2.5, 2.5); f=12.5" ], "pointMarkerIndices": [ 2, 2 ], "pointLabelIndices": [ 2 ], "directed": true, "chosen": [], "visited": [ 2 ], "result": 0, "output": [], "surface": { "xs": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "ys": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "heights": [ 0.5, 0.3291015625, 0.25390625, 0.2744140625, 0.390625, 0.6025390625, 0.91015625, 1.3134765625, 1.8125, 2.4072265625, 3.09765625, 3.8837890625, 4.765625, 5.7431640625, 6.81640625, 7.9853515625, 9.25, 0.3291015625, 0.158203125, 0.0830078125, 0.103515625, 0.2197265625, 0.431640625, 0.7392578125, 1.142578125, 1.6416015625, 2.236328125, 2.9267578125, 3.712890625, 4.5947265625, 5.572265625, 6.6455078125, 7.814453125, 9.0791015625, 0.25390625, 0.0830078125, 0.0078125, 0.0283203125, 0.14453125, 0.3564453125, 0.6640625, 1.0673828125, 1.56640625, 2.1611328125, 2.8515625, 3.6376953125, 4.51953125, 5.4970703125, 6.5703125, 7.7392578125, 9.00390625, 0.2744140625, 0.103515625, 0.0283203125, 0.048828125, 0.1650390625, 0.376953125, 0.6845703125, 1.087890625, 1.5869140625, 2.181640625, 2.8720703125, 3.658203125, 4.5400390625, 5.517578125, 6.5908203125, 7.759765625, 9.0244140625, 0.390625, 0.2197265625, 0.14453125, 0.1650390625, 0.28125, 0.4931640625, 0.80078125, 1.2041015625, 1.703125, 2.2978515625, 2.98828125, 3.7744140625, 4.65625, 5.6337890625, 6.70703125, 7.8759765625, 9.140625, 0.6025390625, 0.431640625, 0.3564453125, 0.376953125, 0.4931640625, 0.705078125, 1.0126953125, 1.416015625, 1.9150390625, 2.509765625, 3.2001953125, 3.986328125, 4.8681640625, 5.845703125, 6.9189453125, 8.087890625, 9.3525390625, 0.91015625, 0.7392578125, 0.6640625, 0.6845703125, 0.80078125, 1.0126953125, 1.3203125, 1.7236328125, 2.22265625, 2.8173828125, 3.5078125, 4.2939453125, 5.17578125, 6.1533203125, 7.2265625, 8.3955078125, 9.66015625, 1.3134765625, 1.142578125, 1.0673828125, 1.087890625, 1.2041015625, 1.416015625, 1.7236328125, 2.126953125, 2.6259765625, 3.220703125, 3.9111328125, 4.697265625, 5.5791015625, 6.556640625, 7.6298828125, 8.798828125, 10.0634765625, 1.8125, 1.6416015625, 1.56640625, 1.5869140625, 1.703125, 1.9150390625, 2.22265625, 2.6259765625, 3.125, 3.7197265625, 4.41015625, 5.1962890625, 6.078125, 7.0556640625, 8.12890625, 9.2978515625, 10.5625, 2.4072265625, 2.236328125, 2.1611328125, 2.181640625, 2.2978515625, 2.509765625, 2.8173828125, 3.220703125, 3.7197265625, 4.314453125, 5.0048828125, 5.791015625, 6.6728515625, 7.650390625, 8.7236328125, 9.892578125, 11.1572265625, 3.09765625, 2.9267578125, 2.8515625, 2.8720703125, 2.98828125, 3.2001953125, 3.5078125, 3.9111328125, 4.41015625, 5.0048828125, 5.6953125, 6.4814453125, 7.36328125, 8.3408203125, 9.4140625, 10.5830078125, 11.84765625, 3.8837890625, 3.712890625, 3.6376953125, 3.658203125, 3.7744140625, 3.986328125, 4.2939453125, 4.697265625, 5.1962890625, 5.791015625, 6.4814453125, 7.267578125, 8.1494140625, 9.126953125, 10.2001953125, 11.369140625, 12.6337890625, 4.765625, 4.5947265625, 4.51953125, 4.5400390625, 4.65625, 4.8681640625, 5.17578125, 5.5791015625, 6.078125, 6.6728515625, 7.36328125, 8.1494140625, 9.03125, 10.0087890625, 11.08203125, 12.2509765625, 13.515625, 5.7431640625, 5.572265625, 5.4970703125, 5.517578125, 5.6337890625, 5.845703125, 6.1533203125, 6.556640625, 7.0556640625, 7.650390625, 8.3408203125, 9.126953125, 10.0087890625, 10.986328125, 12.0595703125, 13.228515625, 14.4931640625, 6.81640625, 6.6455078125, 6.5703125, 6.5908203125, 6.70703125, 6.9189453125, 7.2265625, 7.6298828125, 8.12890625, 8.7236328125, 9.4140625, 10.2001953125, 11.08203125, 12.0595703125, 13.1328125, 14.3017578125, 15.56640625, 7.9853515625, 7.814453125, 7.7392578125, 7.759765625, 7.8759765625, 8.087890625, 8.3955078125, 8.798828125, 9.2978515625, 9.892578125, 10.5830078125, 11.369140625, 12.2509765625, 13.228515625, 14.3017578125, 15.470703125, 16.7353515625, 9.25, 9.0791015625, 9.00390625, 9.0244140625, 9.140625, 9.3525390625, 9.66015625, 10.0634765625, 10.5625, 11.1572265625, 11.84765625, 12.6337890625, 13.515625, 14.4931640625, 15.56640625, 16.7353515625, 18 ], "label": "f(x,y)=(x-0)²+(y-0)²", "pathIndices": [ 2 ], "pathHeights": [ 12.5 ] } }Step 7: Step 7: f=0.009795520511999993, gradient norm 0.19794464389823732.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ], "active": [ 9 ], "kind": "graph", "points": [ [ -0.5, -0.5 ], [ 3, 3 ], [ 2.5, 2.5 ], [ 1.5, 1.5 ], [ 0.8999999999999999, 0.8999999999999999 ], [ 0.5399999999999999, 0.5399999999999999 ], [ 0.32399999999999995, 0.32399999999999995 ], [ 0.19439999999999996, 0.19439999999999996 ], [ 0.11663999999999997, 0.11663999999999997 ], [ 0.06998399999999998, 0.06998399999999998 ] ], "nodeLabels": [ "", "", "(2.5, 2.5); f=12.5", "(1.5, 1.5); f=4.5", "(0.9, 0.9); f=1.62", "(0.54, 0.54); f=0.5832", "(0.324, 0.324); f=0.209952", "(0.1944, 0.1944); f=0.0755827", "(0.11664, 0.11664); f=0.0272098", "(0.069984, 0.069984); f=0.00979552" ], "pointMarkerIndices": [ 2, 9 ], "pointLabelIndices": [ 9 ], "directed": true, "chosen": [ 0, 1, 2, 3, 4, 5, 6 ], "visited": [ 2, 3, 4, 5, 6, 7, 8, 9 ], "result": 0, "output": [], "surface": { "xs": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "ys": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "heights": [ 0.5, 0.3291015625, 0.25390625, 0.2744140625, 0.390625, 0.6025390625, 0.91015625, 1.3134765625, 1.8125, 2.4072265625, 3.09765625, 3.8837890625, 4.765625, 5.7431640625, 6.81640625, 7.9853515625, 9.25, 0.3291015625, 0.158203125, 0.0830078125, 0.103515625, 0.2197265625, 0.431640625, 0.7392578125, 1.142578125, 1.6416015625, 2.236328125, 2.9267578125, 3.712890625, 4.5947265625, 5.572265625, 6.6455078125, 7.814453125, 9.0791015625, 0.25390625, 0.0830078125, 0.0078125, 0.0283203125, 0.14453125, 0.3564453125, 0.6640625, 1.0673828125, 1.56640625, 2.1611328125, 2.8515625, 3.6376953125, 4.51953125, 5.4970703125, 6.5703125, 7.7392578125, 9.00390625, 0.2744140625, 0.103515625, 0.0283203125, 0.048828125, 0.1650390625, 0.376953125, 0.6845703125, 1.087890625, 1.5869140625, 2.181640625, 2.8720703125, 3.658203125, 4.5400390625, 5.517578125, 6.5908203125, 7.759765625, 9.0244140625, 0.390625, 0.2197265625, 0.14453125, 0.1650390625, 0.28125, 0.4931640625, 0.80078125, 1.2041015625, 1.703125, 2.2978515625, 2.98828125, 3.7744140625, 4.65625, 5.6337890625, 6.70703125, 7.8759765625, 9.140625, 0.6025390625, 0.431640625, 0.3564453125, 0.376953125, 0.4931640625, 0.705078125, 1.0126953125, 1.416015625, 1.9150390625, 2.509765625, 3.2001953125, 3.986328125, 4.8681640625, 5.845703125, 6.9189453125, 8.087890625, 9.3525390625, 0.91015625, 0.7392578125, 0.6640625, 0.6845703125, 0.80078125, 1.0126953125, 1.3203125, 1.7236328125, 2.22265625, 2.8173828125, 3.5078125, 4.2939453125, 5.17578125, 6.1533203125, 7.2265625, 8.3955078125, 9.66015625, 1.3134765625, 1.142578125, 1.0673828125, 1.087890625, 1.2041015625, 1.416015625, 1.7236328125, 2.126953125, 2.6259765625, 3.220703125, 3.9111328125, 4.697265625, 5.5791015625, 6.556640625, 7.6298828125, 8.798828125, 10.0634765625, 1.8125, 1.6416015625, 1.56640625, 1.5869140625, 1.703125, 1.9150390625, 2.22265625, 2.6259765625, 3.125, 3.7197265625, 4.41015625, 5.1962890625, 6.078125, 7.0556640625, 8.12890625, 9.2978515625, 10.5625, 2.4072265625, 2.236328125, 2.1611328125, 2.181640625, 2.2978515625, 2.509765625, 2.8173828125, 3.220703125, 3.7197265625, 4.314453125, 5.0048828125, 5.791015625, 6.6728515625, 7.650390625, 8.7236328125, 9.892578125, 11.1572265625, 3.09765625, 2.9267578125, 2.8515625, 2.8720703125, 2.98828125, 3.2001953125, 3.5078125, 3.9111328125, 4.41015625, 5.0048828125, 5.6953125, 6.4814453125, 7.36328125, 8.3408203125, 9.4140625, 10.5830078125, 11.84765625, 3.8837890625, 3.712890625, 3.6376953125, 3.658203125, 3.7744140625, 3.986328125, 4.2939453125, 4.697265625, 5.1962890625, 5.791015625, 6.4814453125, 7.267578125, 8.1494140625, 9.126953125, 10.2001953125, 11.369140625, 12.6337890625, 4.765625, 4.5947265625, 4.51953125, 4.5400390625, 4.65625, 4.8681640625, 5.17578125, 5.5791015625, 6.078125, 6.6728515625, 7.36328125, 8.1494140625, 9.03125, 10.0087890625, 11.08203125, 12.2509765625, 13.515625, 5.7431640625, 5.572265625, 5.4970703125, 5.517578125, 5.6337890625, 5.845703125, 6.1533203125, 6.556640625, 7.0556640625, 7.650390625, 8.3408203125, 9.126953125, 10.0087890625, 10.986328125, 12.0595703125, 13.228515625, 14.4931640625, 6.81640625, 6.6455078125, 6.5703125, 6.5908203125, 6.70703125, 6.9189453125, 7.2265625, 7.6298828125, 8.12890625, 8.7236328125, 9.4140625, 10.2001953125, 11.08203125, 12.0595703125, 13.1328125, 14.3017578125, 15.56640625, 7.9853515625, 7.814453125, 7.7392578125, 7.759765625, 7.8759765625, 8.087890625, 8.3955078125, 8.798828125, 9.2978515625, 9.892578125, 10.5830078125, 11.369140625, 12.2509765625, 13.228515625, 14.3017578125, 15.470703125, 16.7353515625, 9.25, 9.0791015625, 9.00390625, 9.0244140625, 9.140625, 9.3525390625, 9.66015625, 10.0634765625, 10.5625, 11.1572265625, 11.84765625, 12.6337890625, 13.515625, 14.4931640625, 15.56640625, 16.7353515625, 18 ], "label": "f(x,y)=(x-0)²+(y-0)²", "pathIndices": [ 2, 3, 4, 5, 6, 7, 8, 9 ], "pathHeights": [ 12.5, 4.5, 1.6199999999999997, 0.5831999999999998, 0.20995199999999994, 0.07558271999999996, 0.027209779199999985, 0.009795520511999993 ] } }Step 14: Step 14: f=0.00000767617776808101, gradient norm 0.005541183183429695.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ], "active": [ 16 ], "kind": "graph", "points": [ [ -0.5, -0.5 ], [ 3, 3 ], [ 2.5, 2.5 ], [ 1.5, 1.5 ], [ 0.8999999999999999, 0.8999999999999999 ], [ 0.5399999999999999, 0.5399999999999999 ], [ 0.32399999999999995, 0.32399999999999995 ], [ 0.19439999999999996, 0.19439999999999996 ], [ 0.11663999999999997, 0.11663999999999997 ], [ 0.06998399999999998, 0.06998399999999998 ], [ 0.04199039999999998, 0.04199039999999998 ], [ 0.02519423999999999, 0.02519423999999999 ], [ 0.015116543999999992, 0.015116543999999992 ], [ 0.009069926399999994, 0.009069926399999994 ], [ 0.005441955839999997, 0.005441955839999997 ], [ 0.003265173503999998, 0.003265173503999998 ], [ 0.0019591041023999988, 0.0019591041023999988 ] ], "nodeLabels": [ "", "", "(2.5, 2.5); f=12.5", "(1.5, 1.5); f=4.5", "(0.9, 0.9); f=1.62", "(0.54, 0.54); f=0.5832", "(0.324, 0.324); f=0.209952", "(0.1944, 0.1944); f=0.0755827", "(0.11664, 0.11664); f=0.0272098", "(0.069984, 0.069984); f=0.00979552", "(0.04199, 0.04199); f=0.00352639", "(0.025194, 0.025194); f=0.0012695", "(0.015117, 0.015117); f=0.00045702", "(0.0090699, 0.0090699); f=0.000164527", "(0.005442, 0.005442); f=0.0000592298", "(0.0032652, 0.0032652); f=0.0000213227", "(0.0019591, 0.0019591); f=0.00000767618" ], "pointMarkerIndices": [ 2, 16 ], "pointLabelIndices": [ 16 ], "directed": true, "chosen": [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ], "visited": [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ], "result": 0, "output": [], "surface": { "xs": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "ys": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "heights": [ 0.5, 0.3291015625, 0.25390625, 0.2744140625, 0.390625, 0.6025390625, 0.91015625, 1.3134765625, 1.8125, 2.4072265625, 3.09765625, 3.8837890625, 4.765625, 5.7431640625, 6.81640625, 7.9853515625, 9.25, 0.3291015625, 0.158203125, 0.0830078125, 0.103515625, 0.2197265625, 0.431640625, 0.7392578125, 1.142578125, 1.6416015625, 2.236328125, 2.9267578125, 3.712890625, 4.5947265625, 5.572265625, 6.6455078125, 7.814453125, 9.0791015625, 0.25390625, 0.0830078125, 0.0078125, 0.0283203125, 0.14453125, 0.3564453125, 0.6640625, 1.0673828125, 1.56640625, 2.1611328125, 2.8515625, 3.6376953125, 4.51953125, 5.4970703125, 6.5703125, 7.7392578125, 9.00390625, 0.2744140625, 0.103515625, 0.0283203125, 0.048828125, 0.1650390625, 0.376953125, 0.6845703125, 1.087890625, 1.5869140625, 2.181640625, 2.8720703125, 3.658203125, 4.5400390625, 5.517578125, 6.5908203125, 7.759765625, 9.0244140625, 0.390625, 0.2197265625, 0.14453125, 0.1650390625, 0.28125, 0.4931640625, 0.80078125, 1.2041015625, 1.703125, 2.2978515625, 2.98828125, 3.7744140625, 4.65625, 5.6337890625, 6.70703125, 7.8759765625, 9.140625, 0.6025390625, 0.431640625, 0.3564453125, 0.376953125, 0.4931640625, 0.705078125, 1.0126953125, 1.416015625, 1.9150390625, 2.509765625, 3.2001953125, 3.986328125, 4.8681640625, 5.845703125, 6.9189453125, 8.087890625, 9.3525390625, 0.91015625, 0.7392578125, 0.6640625, 0.6845703125, 0.80078125, 1.0126953125, 1.3203125, 1.7236328125, 2.22265625, 2.8173828125, 3.5078125, 4.2939453125, 5.17578125, 6.1533203125, 7.2265625, 8.3955078125, 9.66015625, 1.3134765625, 1.142578125, 1.0673828125, 1.087890625, 1.2041015625, 1.416015625, 1.7236328125, 2.126953125, 2.6259765625, 3.220703125, 3.9111328125, 4.697265625, 5.5791015625, 6.556640625, 7.6298828125, 8.798828125, 10.0634765625, 1.8125, 1.6416015625, 1.56640625, 1.5869140625, 1.703125, 1.9150390625, 2.22265625, 2.6259765625, 3.125, 3.7197265625, 4.41015625, 5.1962890625, 6.078125, 7.0556640625, 8.12890625, 9.2978515625, 10.5625, 2.4072265625, 2.236328125, 2.1611328125, 2.181640625, 2.2978515625, 2.509765625, 2.8173828125, 3.220703125, 3.7197265625, 4.314453125, 5.0048828125, 5.791015625, 6.6728515625, 7.650390625, 8.7236328125, 9.892578125, 11.1572265625, 3.09765625, 2.9267578125, 2.8515625, 2.8720703125, 2.98828125, 3.2001953125, 3.5078125, 3.9111328125, 4.41015625, 5.0048828125, 5.6953125, 6.4814453125, 7.36328125, 8.3408203125, 9.4140625, 10.5830078125, 11.84765625, 3.8837890625, 3.712890625, 3.6376953125, 3.658203125, 3.7744140625, 3.986328125, 4.2939453125, 4.697265625, 5.1962890625, 5.791015625, 6.4814453125, 7.267578125, 8.1494140625, 9.126953125, 10.2001953125, 11.369140625, 12.6337890625, 4.765625, 4.5947265625, 4.51953125, 4.5400390625, 4.65625, 4.8681640625, 5.17578125, 5.5791015625, 6.078125, 6.6728515625, 7.36328125, 8.1494140625, 9.03125, 10.0087890625, 11.08203125, 12.2509765625, 13.515625, 5.7431640625, 5.572265625, 5.4970703125, 5.517578125, 5.6337890625, 5.845703125, 6.1533203125, 6.556640625, 7.0556640625, 7.650390625, 8.3408203125, 9.126953125, 10.0087890625, 10.986328125, 12.0595703125, 13.228515625, 14.4931640625, 6.81640625, 6.6455078125, 6.5703125, 6.5908203125, 6.70703125, 6.9189453125, 7.2265625, 7.6298828125, 8.12890625, 8.7236328125, 9.4140625, 10.2001953125, 11.08203125, 12.0595703125, 13.1328125, 14.3017578125, 15.56640625, 7.9853515625, 7.814453125, 7.7392578125, 7.759765625, 7.8759765625, 8.087890625, 8.3955078125, 8.798828125, 9.2978515625, 9.892578125, 10.5830078125, 11.369140625, 12.2509765625, 13.228515625, 14.3017578125, 15.470703125, 16.7353515625, 9.25, 9.0791015625, 9.00390625, 9.0244140625, 9.140625, 9.3525390625, 9.66015625, 10.0634765625, 10.5625, 11.1572265625, 11.84765625, 12.6337890625, 13.515625, 14.4931640625, 15.56640625, 16.7353515625, 18 ], "label": "f(x,y)=(x-0)²+(y-0)²", "pathIndices": [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ], "pathHeights": [ 12.5, 4.5, 1.6199999999999997, 0.5831999999999998, 0.20995199999999994, 0.07558271999999996, 0.027209779199999985, 0.009795520511999993, 0.003526387384319997, 0.001269499458355199, 0.00045701980500787153, 0.0001645271298028337, 0.000059229766729020136, 0.000021322716022447253, 0.00000767617776808101 ] } }Step 21: Step 21: f=6.015372542479671e-9, gradient norm 0.00015511766556365746.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 ], "active": [ 23 ], "kind": "graph", "points": [ [ -0.5, -0.5 ], [ 3, 3 ], [ 2.5, 2.5 ], [ 1.5, 1.5 ], [ 0.8999999999999999, 0.8999999999999999 ], [ 0.5399999999999999, 0.5399999999999999 ], [ 0.32399999999999995, 0.32399999999999995 ], [ 0.19439999999999996, 0.19439999999999996 ], [ 0.11663999999999997, 0.11663999999999997 ], [ 0.06998399999999998, 0.06998399999999998 ], [ 0.04199039999999998, 0.04199039999999998 ], [ 0.02519423999999999, 0.02519423999999999 ], [ 0.015116543999999992, 0.015116543999999992 ], [ 0.009069926399999994, 0.009069926399999994 ], [ 0.005441955839999997, 0.005441955839999997 ], [ 0.003265173503999998, 0.003265173503999998 ], [ 0.0019591041023999988, 0.0019591041023999988 ], [ 0.0011754624614399992, 0.0011754624614399992 ], [ 0.0007052774768639995, 0.0007052774768639995 ], [ 0.0004231664861183997, 0.0004231664861183997 ], [ 0.0002538998916710398, 0.0002538998916710398 ], [ 0.0001523399350026239, 0.0001523399350026239 ], [ 0.00009140396100157433, 0.00009140396100157433 ], [ 0.0000548423766009446, 0.0000548423766009446 ] ], "nodeLabels": [ "", "", "(2.5, 2.5); f=12.5", "(1.5, 1.5); f=4.5", "(0.9, 0.9); f=1.62", "(0.54, 0.54); f=0.5832", "(0.324, 0.324); f=0.209952", "(0.1944, 0.1944); f=0.0755827", "(0.11664, 0.11664); f=0.0272098", "(0.069984, 0.069984); f=0.00979552", "(0.04199, 0.04199); f=0.00352639", "(0.025194, 0.025194); f=0.0012695", "(0.015117, 0.015117); f=0.00045702", "(0.0090699, 0.0090699); f=0.000164527", "(0.005442, 0.005442); f=0.0000592298", "(0.0032652, 0.0032652); f=0.0000213227", "(0.0019591, 0.0019591); f=0.00000767618", "(0.0011755, 0.0011755); f=0.00000276342", "(0.00070528, 0.00070528); f=9.94833e-7", "(0.00042317, 0.00042317); f=3.5814e-7", "(0.0002539, 0.0002539); f=1.2893e-7", "(0.00015234, 0.00015234); f=4.64149e-8", "(0.000091404, 0.000091404); f=1.67094e-8", "(0.000054842, 0.000054842); f=6.01537e-9" ], "pointMarkerIndices": [ 2, 23 ], "pointLabelIndices": [ 23 ], "directed": true, "chosen": [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ], "visited": [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 ], "result": 0, "output": [], "surface": { "xs": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "ys": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "heights": [ 0.5, 0.3291015625, 0.25390625, 0.2744140625, 0.390625, 0.6025390625, 0.91015625, 1.3134765625, 1.8125, 2.4072265625, 3.09765625, 3.8837890625, 4.765625, 5.7431640625, 6.81640625, 7.9853515625, 9.25, 0.3291015625, 0.158203125, 0.0830078125, 0.103515625, 0.2197265625, 0.431640625, 0.7392578125, 1.142578125, 1.6416015625, 2.236328125, 2.9267578125, 3.712890625, 4.5947265625, 5.572265625, 6.6455078125, 7.814453125, 9.0791015625, 0.25390625, 0.0830078125, 0.0078125, 0.0283203125, 0.14453125, 0.3564453125, 0.6640625, 1.0673828125, 1.56640625, 2.1611328125, 2.8515625, 3.6376953125, 4.51953125, 5.4970703125, 6.5703125, 7.7392578125, 9.00390625, 0.2744140625, 0.103515625, 0.0283203125, 0.048828125, 0.1650390625, 0.376953125, 0.6845703125, 1.087890625, 1.5869140625, 2.181640625, 2.8720703125, 3.658203125, 4.5400390625, 5.517578125, 6.5908203125, 7.759765625, 9.0244140625, 0.390625, 0.2197265625, 0.14453125, 0.1650390625, 0.28125, 0.4931640625, 0.80078125, 1.2041015625, 1.703125, 2.2978515625, 2.98828125, 3.7744140625, 4.65625, 5.6337890625, 6.70703125, 7.8759765625, 9.140625, 0.6025390625, 0.431640625, 0.3564453125, 0.376953125, 0.4931640625, 0.705078125, 1.0126953125, 1.416015625, 1.9150390625, 2.509765625, 3.2001953125, 3.986328125, 4.8681640625, 5.845703125, 6.9189453125, 8.087890625, 9.3525390625, 0.91015625, 0.7392578125, 0.6640625, 0.6845703125, 0.80078125, 1.0126953125, 1.3203125, 1.7236328125, 2.22265625, 2.8173828125, 3.5078125, 4.2939453125, 5.17578125, 6.1533203125, 7.2265625, 8.3955078125, 9.66015625, 1.3134765625, 1.142578125, 1.0673828125, 1.087890625, 1.2041015625, 1.416015625, 1.7236328125, 2.126953125, 2.6259765625, 3.220703125, 3.9111328125, 4.697265625, 5.5791015625, 6.556640625, 7.6298828125, 8.798828125, 10.0634765625, 1.8125, 1.6416015625, 1.56640625, 1.5869140625, 1.703125, 1.9150390625, 2.22265625, 2.6259765625, 3.125, 3.7197265625, 4.41015625, 5.1962890625, 6.078125, 7.0556640625, 8.12890625, 9.2978515625, 10.5625, 2.4072265625, 2.236328125, 2.1611328125, 2.181640625, 2.2978515625, 2.509765625, 2.8173828125, 3.220703125, 3.7197265625, 4.314453125, 5.0048828125, 5.791015625, 6.6728515625, 7.650390625, 8.7236328125, 9.892578125, 11.1572265625, 3.09765625, 2.9267578125, 2.8515625, 2.8720703125, 2.98828125, 3.2001953125, 3.5078125, 3.9111328125, 4.41015625, 5.0048828125, 5.6953125, 6.4814453125, 7.36328125, 8.3408203125, 9.4140625, 10.5830078125, 11.84765625, 3.8837890625, 3.712890625, 3.6376953125, 3.658203125, 3.7744140625, 3.986328125, 4.2939453125, 4.697265625, 5.1962890625, 5.791015625, 6.4814453125, 7.267578125, 8.1494140625, 9.126953125, 10.2001953125, 11.369140625, 12.6337890625, 4.765625, 4.5947265625, 4.51953125, 4.5400390625, 4.65625, 4.8681640625, 5.17578125, 5.5791015625, 6.078125, 6.6728515625, 7.36328125, 8.1494140625, 9.03125, 10.0087890625, 11.08203125, 12.2509765625, 13.515625, 5.7431640625, 5.572265625, 5.4970703125, 5.517578125, 5.6337890625, 5.845703125, 6.1533203125, 6.556640625, 7.0556640625, 7.650390625, 8.3408203125, 9.126953125, 10.0087890625, 10.986328125, 12.0595703125, 13.228515625, 14.4931640625, 6.81640625, 6.6455078125, 6.5703125, 6.5908203125, 6.70703125, 6.9189453125, 7.2265625, 7.6298828125, 8.12890625, 8.7236328125, 9.4140625, 10.2001953125, 11.08203125, 12.0595703125, 13.1328125, 14.3017578125, 15.56640625, 7.9853515625, 7.814453125, 7.7392578125, 7.759765625, 7.8759765625, 8.087890625, 8.3955078125, 8.798828125, 9.2978515625, 9.892578125, 10.5830078125, 11.369140625, 12.2509765625, 13.228515625, 14.3017578125, 15.470703125, 16.7353515625, 9.25, 9.0791015625, 9.00390625, 9.0244140625, 9.140625, 9.3525390625, 9.66015625, 10.0634765625, 10.5625, 11.1572265625, 11.84765625, 12.6337890625, 13.515625, 14.4931640625, 15.56640625, 16.7353515625, 18 ], "label": "f(x,y)=(x-0)²+(y-0)²", "pathIndices": [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 ], "pathHeights": [ 12.5, 4.5, 1.6199999999999997, 0.5831999999999998, 0.20995199999999994, 0.07558271999999996, 0.027209779199999985, 0.009795520511999993, 0.003526387384319997, 0.001269499458355199, 0.00045701980500787153, 0.0001645271298028337, 0.000059229766729020136, 0.000021322716022447253, 0.00000767617776808101, 0.0000027634239965091633, 9.948326387432987e-7, 3.5813974994758756e-7, 1.289303099811315e-7, 4.641491159320734e-8, 1.670936817355464e-8, 6.015372542479671e-9 ] } }Step 28: Converged: gradient norm satisfies tolerance.
State at this checkpoint
{ "values": [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 ], "active": [ 29 ], "kind": "graph", "points": [ [ -0.5, -0.5 ], [ 3, 3 ], [ 2.5, 2.5 ], [ 1.5, 1.5 ], [ 0.8999999999999999, 0.8999999999999999 ], [ 0.5399999999999999, 0.5399999999999999 ], [ 0.32399999999999995, 0.32399999999999995 ], [ 0.19439999999999996, 0.19439999999999996 ], [ 0.11663999999999997, 0.11663999999999997 ], [ 0.06998399999999998, 0.06998399999999998 ], [ 0.04199039999999998, 0.04199039999999998 ], [ 0.02519423999999999, 0.02519423999999999 ], [ 0.015116543999999992, 0.015116543999999992 ], [ 0.009069926399999994, 0.009069926399999994 ], [ 0.005441955839999997, 0.005441955839999997 ], [ 0.003265173503999998, 0.003265173503999998 ], [ 0.0019591041023999988, 0.0019591041023999988 ], [ 0.0011754624614399992, 0.0011754624614399992 ], [ 0.0007052774768639995, 0.0007052774768639995 ], [ 0.0004231664861183997, 0.0004231664861183997 ], [ 0.0002538998916710398, 0.0002538998916710398 ], [ 0.0001523399350026239, 0.0001523399350026239 ], [ 0.00009140396100157433, 0.00009140396100157433 ], [ 0.0000548423766009446, 0.0000548423766009446 ], [ 0.00003290542596056676, 0.00003290542596056676 ], [ 0.000019743255576340053, 0.000019743255576340053 ], [ 0.000011845953345804031, 0.000011845953345804031 ], [ 0.0000071075720074824184, 0.0000071075720074824184 ], [ 0.000004264543204489451, 0.000004264543204489451 ], [ 0.0000025587259226936704, 0.0000025587259226936704 ] ], "nodeLabels": [ "", "", "(2.5, 2.5); f=12.5", "(1.5, 1.5); f=4.5", "(0.9, 0.9); f=1.62", "(0.54, 0.54); f=0.5832", "(0.324, 0.324); f=0.209952", "(0.1944, 0.1944); f=0.0755827", "(0.11664, 0.11664); f=0.0272098", "(0.069984, 0.069984); f=0.00979552", "(0.04199, 0.04199); f=0.00352639", "(0.025194, 0.025194); f=0.0012695", "(0.015117, 0.015117); f=0.00045702", "(0.0090699, 0.0090699); f=0.000164527", "(0.005442, 0.005442); f=0.0000592298", "(0.0032652, 0.0032652); f=0.0000213227", "(0.0019591, 0.0019591); f=0.00000767618", "(0.0011755, 0.0011755); f=0.00000276342", "(0.00070528, 0.00070528); f=9.94833e-7", "(0.00042317, 0.00042317); f=3.5814e-7", "(0.0002539, 0.0002539); f=1.2893e-7", "(0.00015234, 0.00015234); f=4.64149e-8", "(0.000091404, 0.000091404); f=1.67094e-8", "(0.000054842, 0.000054842); f=6.01537e-9", "(0.000032905, 0.000032905); f=2.16553e-9", "(0.000019743, 0.000019743); f=7.79592e-10", "(0.000011846, 0.000011846); f=2.80653e-10", "(0.0000071076, 0.0000071076); f=1.01035e-10", "(0.0000042645, 0.0000042645); f=3.63727e-11", "(0.0000025587, 0.0000025587); f=1.30942e-11" ], "pointMarkerIndices": [ 2, 29 ], "pointLabelIndices": [ 29 ], "directed": true, "chosen": [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ], "visited": [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 ], "result": 1, "output": [ 0.0000025587259226936704, 0.0000025587259226936704, 1.3094156694929149e-11, 0.000007237169804538001, 27 ], "surface": { "xs": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "ys": [ -0.5, -0.28125, -0.0625, 0.15625, 0.375, 0.59375, 0.8125, 1.03125, 1.25, 1.46875, 1.6875, 1.90625, 2.125, 2.34375, 2.5625, 2.78125, 3 ], "heights": [ 0.5, 0.3291015625, 0.25390625, 0.2744140625, 0.390625, 0.6025390625, 0.91015625, 1.3134765625, 1.8125, 2.4072265625, 3.09765625, 3.8837890625, 4.765625, 5.7431640625, 6.81640625, 7.9853515625, 9.25, 0.3291015625, 0.158203125, 0.0830078125, 0.103515625, 0.2197265625, 0.431640625, 0.7392578125, 1.142578125, 1.6416015625, 2.236328125, 2.9267578125, 3.712890625, 4.5947265625, 5.572265625, 6.6455078125, 7.814453125, 9.0791015625, 0.25390625, 0.0830078125, 0.0078125, 0.0283203125, 0.14453125, 0.3564453125, 0.6640625, 1.0673828125, 1.56640625, 2.1611328125, 2.8515625, 3.6376953125, 4.51953125, 5.4970703125, 6.5703125, 7.7392578125, 9.00390625, 0.2744140625, 0.103515625, 0.0283203125, 0.048828125, 0.1650390625, 0.376953125, 0.6845703125, 1.087890625, 1.5869140625, 2.181640625, 2.8720703125, 3.658203125, 4.5400390625, 5.517578125, 6.5908203125, 7.759765625, 9.0244140625, 0.390625, 0.2197265625, 0.14453125, 0.1650390625, 0.28125, 0.4931640625, 0.80078125, 1.2041015625, 1.703125, 2.2978515625, 2.98828125, 3.7744140625, 4.65625, 5.6337890625, 6.70703125, 7.8759765625, 9.140625, 0.6025390625, 0.431640625, 0.3564453125, 0.376953125, 0.4931640625, 0.705078125, 1.0126953125, 1.416015625, 1.9150390625, 2.509765625, 3.2001953125, 3.986328125, 4.8681640625, 5.845703125, 6.9189453125, 8.087890625, 9.3525390625, 0.91015625, 0.7392578125, 0.6640625, 0.6845703125, 0.80078125, 1.0126953125, 1.3203125, 1.7236328125, 2.22265625, 2.8173828125, 3.5078125, 4.2939453125, 5.17578125, 6.1533203125, 7.2265625, 8.3955078125, 9.66015625, 1.3134765625, 1.142578125, 1.0673828125, 1.087890625, 1.2041015625, 1.416015625, 1.7236328125, 2.126953125, 2.6259765625, 3.220703125, 3.9111328125, 4.697265625, 5.5791015625, 6.556640625, 7.6298828125, 8.798828125, 10.0634765625, 1.8125, 1.6416015625, 1.56640625, 1.5869140625, 1.703125, 1.9150390625, 2.22265625, 2.6259765625, 3.125, 3.7197265625, 4.41015625, 5.1962890625, 6.078125, 7.0556640625, 8.12890625, 9.2978515625, 10.5625, 2.4072265625, 2.236328125, 2.1611328125, 2.181640625, 2.2978515625, 2.509765625, 2.8173828125, 3.220703125, 3.7197265625, 4.314453125, 5.0048828125, 5.791015625, 6.6728515625, 7.650390625, 8.7236328125, 9.892578125, 11.1572265625, 3.09765625, 2.9267578125, 2.8515625, 2.8720703125, 2.98828125, 3.2001953125, 3.5078125, 3.9111328125, 4.41015625, 5.0048828125, 5.6953125, 6.4814453125, 7.36328125, 8.3408203125, 9.4140625, 10.5830078125, 11.84765625, 3.8837890625, 3.712890625, 3.6376953125, 3.658203125, 3.7744140625, 3.986328125, 4.2939453125, 4.697265625, 5.1962890625, 5.791015625, 6.4814453125, 7.267578125, 8.1494140625, 9.126953125, 10.2001953125, 11.369140625, 12.6337890625, 4.765625, 4.5947265625, 4.51953125, 4.5400390625, 4.65625, 4.8681640625, 5.17578125, 5.5791015625, 6.078125, 6.6728515625, 7.36328125, 8.1494140625, 9.03125, 10.0087890625, 11.08203125, 12.2509765625, 13.515625, 5.7431640625, 5.572265625, 5.4970703125, 5.517578125, 5.6337890625, 5.845703125, 6.1533203125, 6.556640625, 7.0556640625, 7.650390625, 8.3408203125, 9.126953125, 10.0087890625, 10.986328125, 12.0595703125, 13.228515625, 14.4931640625, 6.81640625, 6.6455078125, 6.5703125, 6.5908203125, 6.70703125, 6.9189453125, 7.2265625, 7.6298828125, 8.12890625, 8.7236328125, 9.4140625, 10.2001953125, 11.08203125, 12.0595703125, 13.1328125, 14.3017578125, 15.56640625, 7.9853515625, 7.814453125, 7.7392578125, 7.759765625, 7.8759765625, 8.087890625, 8.3955078125, 8.798828125, 9.2978515625, 9.892578125, 10.5830078125, 11.369140625, 12.2509765625, 13.228515625, 14.3017578125, 15.470703125, 16.7353515625, 9.25, 9.0791015625, 9.00390625, 9.0244140625, 9.140625, 9.3525390625, 9.66015625, 10.0634765625, 10.5625, 11.1572265625, 11.84765625, 12.6337890625, 13.515625, 14.4931640625, 15.56640625, 16.7353515625, 18 ], "label": "f(x,y)=(x-0)²+(y-0)²", "pathIndices": [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 ], "pathHeights": [ 12.5, 4.5, 1.6199999999999997, 0.5831999999999998, 0.20995199999999994, 0.07558271999999996, 0.027209779199999985, 0.009795520511999993, 0.003526387384319997, 0.001269499458355199, 0.00045701980500787153, 0.0001645271298028337, 0.000059229766729020136, 0.000021322716022447253, 0.00000767617776808101, 0.0000027634239965091633, 9.948326387432987e-7, 3.5813974994758756e-7, 1.289303099811315e-7, 4.641491159320734e-8, 1.670936817355464e-8, 6.015372542479671e-9, 2.1655341152926812e-9, 7.795922815053652e-10, 2.806532213419314e-10, 1.0103515968309531e-10, 3.6372657485914315e-11, 1.3094156694929149e-11 ] } }
Expected final state
Converged: gradient norm satisfies tolerance.
Complexity and input bounds
Family: Optimization. Time complexity: O(I).
Implementation detail: Starting point and target coordinates -3..3, rate .05..1, gradient tolerance 1e-8..0.1, iterations 1..32. Downloads return 1 converged, 0 iteration limit or -1 invalid parameters without writes, and output [x,y,objective,gradientNorm,completedSteps]. Closed-form fixtures check contraction, one-step convergence and oscillation in every language. WebGL lifts the trajectory to the actual objective height with an explicit vertical scale; the fallback shows an overhead objective heat map.
Space complexity: O(1) numerical state excluding output, recorded path and surface samples.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
x,y,a,b,learningRate,gradientTolerance,maxIterations. Starts/target -3..3, rate .05..1, tolerance 1e-8..0.1, iterations 1..32. A rate of one can oscillate.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A finite sequence is not proof of convergence. A rate of one can oscillate on this quadratic, while one half reaches its minimizer in one step. State the stopping criterion and separate an exhausted budget from success.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 | // Gradient descent for f(x,y)=(x-a)^2+(y-b)^2. Starts/target -3..3, learning rate .05..1, gradient-norm tolerance 1e-8..0.1, iteration limit 1..32. Return 1 gradient norm <= tolerance, 0 iteration limit, -1 invalid parameters without writes. Output five doubles [x,y,objective,gradientNorm,completedSteps]. A rate of one can oscillate; finite iteration is not proof of convergence. O(I) time, O(1) numerical state. Compare real outputs with explicit tolerances. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(x, y, a, b, rate, tolerance, limit, output) { if (Math.abs(x) > 3.0 || Math.abs(y) > 3.0 || Math.abs(a) > 3.0 || Math.abs(b) > 3.0 || rate < 0.05 || rate > 1.0 || tolerance < 1e-8 || tolerance > 0.1 || limit < 1 || limit > 32) { return -1; } let steps = 0; let dx = x-a; let dy = y-b; let objective = dx*dx+dy*dy; while (steps < limit && 4.0*objective > tolerance*tolerance) { x -= 2.0*rate*(x-a); y -= 2.0*rate*(y-b); steps++; dx = x-a; dy = y-b; objective = dx*dx+dy*dy; } output[0] = x; output[1] = y; output[2] = objective; output[3] = 2.0*Math.sqrt(objective); output[4] = steps; if (4.0*objective <= tolerance*tolerance) { return 1; } return 0; } |
Source
Authoritative author-provided convex-optimization text covering gradient methods, not a claim to the original Cauchy paper. The playground uses an explicit isotropic quadratic, constant rate and gradient-norm stopping rule.
- Convex Optimization
Stephen Boyd; Lieven Vandenberghe (2004). Author reference book.