|
<!DOCTYPE html> |
|
<html> |
|
<head> |
|
<meta charset="utf-8"> |
|
<script src="http://d3js.org/d3.v3.js"></script> |
|
<style> |
|
|
|
body { |
|
font: 13pt courier; |
|
font-weight: bold; |
|
background-color: #111; |
|
overflow-y:hidden; |
|
color: #ccc; |
|
} |
|
|
|
table { |
|
table-layout: fixed; |
|
} |
|
|
|
tr { |
|
white-space: nowrap; |
|
} |
|
|
|
td { |
|
width:150px; |
|
height: 40px; |
|
overflow: hidden; |
|
display: inline-block; |
|
white-space: nowrap; |
|
border:0; |
|
padding:0; |
|
margin:0; |
|
} |
|
|
|
td.small { |
|
width: 50px; |
|
} |
|
|
|
.step_line { |
|
fill: none; |
|
stroke: #6c6; /* rgb(120, 120, 120); */ |
|
stroke-width: 1.5px; |
|
stroke-opacity: .6; |
|
} |
|
|
|
.gradient_line { |
|
fill: none; |
|
stroke: #999; /* rgb(120, 120, 120); */ |
|
stroke-width: 1.5px; |
|
sroke-opacity: .8; |
|
} |
|
|
|
.line { |
|
fill: none; |
|
stroke-width: 1px; |
|
shape-rendering: optimizeSpeed; |
|
} |
|
|
|
.blue_line { |
|
fill: none; |
|
stroke: steelblue; |
|
stroke-width: 1.5px; |
|
} |
|
|
|
.green_line { |
|
fill: none; |
|
stroke: #090; |
|
stroke-width: 3px; |
|
} |
|
div { |
|
position: relative; |
|
height:50px; |
|
} |
|
input { |
|
position: absolute; |
|
right: 10px; |
|
width: 120px; |
|
} |
|
#atext, #btext { |
|
position: absolute; |
|
right: 150px; |
|
} |
|
|
|
@media all and (max-width: 940px) { |
|
input { |
|
left: 786px; |
|
} |
|
#atext, #btext { |
|
left: 676px; |
|
width: 100px; |
|
} |
|
} |
|
|
|
#coordText { |
|
position: absolute; |
|
left: 250px; |
|
top: 12px; |
|
} |
|
|
|
#fText { |
|
position: absolute; |
|
left: 20px; |
|
top: 12px; |
|
} |
|
|
|
sup, sub { |
|
line-height:0; |
|
} |
|
</style> |
|
</head> |
|
<body> |
|
<div> |
|
<span id="fText"></span> |
|
<span id="coordText"></span> |
|
<input min="-1" max="1" step=".01" type="range" id="aSlider" value="1" title="axis 1" autocomplete="off"> |
|
<span id="atext"></span> |
|
<br/> |
|
<input min="-1" max="1" step=".01" type="range" id="bSlider" value="1" title="axis 1" autocomplete="off"> |
|
<span id="btext"></span> |
|
<br/> |
|
</div> |
|
|
|
<script type="text/javascript"> |
|
var cleanup_lines = function() { |
|
d3.selectAll('.step_line') |
|
.transition() |
|
.duration(dur) |
|
.ease('linear') |
|
.style('opacity', 0) |
|
.remove() ; |
|
d3.selectAll('.gradient_line') |
|
.transition() |
|
.duration(dur) |
|
.ease('linear') |
|
.style('opacity', 0) |
|
.remove() ; |
|
drawing = false ; |
|
stepping = false ; |
|
} |
|
|
|
var aSlider = d3.select("#aSlider") |
|
.on("input", function() { |
|
cleanup_lines(); |
|
a = +this.value; |
|
ar = Math.sqrt(Math.abs(a)) ; |
|
// aText.text('a: ' + a) ; |
|
init_data() ; |
|
aText.html('<table><tbody><tr><td class="small">λ<sub>1</sub>:</td><td class="small">' + a.toPrecision(2) + '</td></tr></tbody></table>') |
|
}) ; |
|
|
|
var bSlider = d3.select("#bSlider") |
|
.on("input", function() { |
|
cleanup_lines() ; |
|
b = +this.value; |
|
br = Math.sqrt(Math.abs(b)) ; |
|
// aText.text('a: ' + a) ; |
|
init_data() ; |
|
bText.html('<table><tbody><tr><td class="small">λ<sub>2</sub>:</td><td class="small">' + b.toPrecision(2) + '</td></tr></tbody></table>') |
|
}) ; |
|
|
|
var a = Number(aSlider.attr("value")) ; |
|
var b = Number(bSlider.attr("value")) ; |
|
var ar = Math.sqrt(a) ; |
|
var br = Math.sqrt(b) ; |
|
|
|
var c = 0 ; // .1 ; |
|
|
|
var auxiliary_objective = function(v) { |
|
var x = v[0] ; |
|
var y = v[1] ; |
|
//return -c * Math.cos(x) - c * Math.cos(y) ; |
|
return c * x * x * x * x + c * y * y * y * y ; |
|
} ; |
|
|
|
var auxiliary_gradient = function(v) { |
|
//return [c * Math.sin(v[0]), c * Math.sin(v[1])] ; |
|
return [4 * c * v[0] * v[0] * v[0], 4 * c * v[1] * v[1] * v[1]] ; |
|
} |
|
|
|
var auxiliary_hessian = function(v) { |
|
return [[12 * c * v[0] * v[0], 0], [0, 12 * c * v[1] * v[1]]] ; |
|
} |
|
|
|
var objective_function = function(v) { |
|
var x = v[0] ; |
|
var y = v[1] ; |
|
//return 0.25 * (a * x * x + b * y * y) + auxiliary_objective(v) ; |
|
return 0.25 * (a * x * x + b * y * y) ; |
|
} ; |
|
|
|
var gradient_function = function(v) { |
|
// var g_aux = auxiliary_gradient(v) ; |
|
//return [0.5 * a * v[0] + g_aux[0], 0.5 * b * v[1] + g_aux[1]] ; |
|
return [0.5 * a * v[0], 0.5 * b * v[1]] ; |
|
} |
|
|
|
var hessian_function = function(v) { |
|
//var H = auxiliary_hessian(v) ; |
|
//return [[0.5 * a + H[0][0], 0 + H[0][1]], [0 + H[1][0], 0.5 * b + H[1][1]]] ; |
|
return [[0.5 * a, 0], [0, 0.5 * b]] ; |
|
} |
|
|
|
var width = 320 ; |
|
var height = 320 ; |
|
|
|
var x = d3.scale.linear() |
|
.domain([-2.5, 2.5]) |
|
.range([0, width]) ; |
|
|
|
var y = d3.scale.linear() |
|
.domain([-2.5, 2.5]) |
|
.range([height, 0]) ; |
|
|
|
var z = d3.scale.linear() |
|
.domain([-10, -2, 0, 2, 10]) |
|
.range(["rgb(0, 0, 102)", "rgb(33, 102, 172)", "rgb(140, 140, 140)", "rgb(178, 88, 43)", "rgb(102, 0, 0)"]); |
|
|
|
|
|
var line = d3.svg.line() |
|
.x(function(d) { return x(d.x); }) |
|
.y(function(d) { return y(d.y) ; }) ; |
|
|
|
var svg = d3 |
|
.select("body") |
|
.append("svg") |
|
.attr("viewBox", -width/2 + ' ' + 0 + ' ' + 2 * width + ' ' + height) |
|
.attr("preserveAspectRatio", "xMidYMin meet") |
|
.style('max-height', '90%') |
|
.style('min-height', '610px') ; |
|
//.attr("viewBox", '0 0 ' + width + ' ' + height) |
|
|
|
svg |
|
.append('defs') |
|
.append('marker') |
|
.attr('id', 'gradientMarker') |
|
.attr('orient', 'auto') |
|
.attr('markerWidth', 2) |
|
.attr('markerHeight', 4) |
|
.attr('refX', 0.1) |
|
.attr('refY', 2) |
|
.append('path') |
|
.attr('d', 'M0,0 V4 L2,2 Z') |
|
.attr('fill', '#999') |
|
.attr('opacity', .8) |
|
svg |
|
.append('marker') |
|
.attr('id', 'stepMarker') |
|
.attr('orient', 'auto') |
|
.attr('markerWidth', 2) |
|
.attr('markerHeight', 4) |
|
.attr('refX', 0.1) |
|
.attr('refY', 2) |
|
.append('path') |
|
.attr('d', 'M0,0 V4 L2,2 Z') |
|
.attr('fill', '#6c6') |
|
.attr('opacity', .6) |
|
|
|
d3 |
|
.select(document.body) |
|
.append("br") ; |
|
|
|
var g = svg |
|
.append("g") |
|
.attr("transform", "rotate(-60, 160, 160)") ; |
|
|
|
var g2 = svg |
|
.append("g") |
|
.attr("transform", "translate(160, 0)scale(.8)rotate(-60, 160, 160)") ; |
|
|
|
var aText = d3 |
|
.select('#atext') |
|
.html('<table><tbody><tr><td class="small">λ<sub>1</sub>:</td><td class="small">' + a.toPrecision(2) + '</td></tr></tbody></table>') |
|
|
|
var bText = d3 |
|
.select('#btext') |
|
.html('<table><tbody><tr><td class="small">λ<sub>2</sub>:</td><td class="small">' + b.toPrecision(2) + '</td></tr></tbody></table>') |
|
|
|
var Nline = 43 ; |
|
|
|
var Nt = 280 ; |
|
|
|
var spacing = .85 ; |
|
|
|
var start = 0.175 ; |
|
|
|
var t = d3 |
|
.scale |
|
.linear() |
|
.domain([0, Nt - 1]) |
|
.range([0, 2 * Math.PI]) ; |
|
|
|
var unitCircle = [] |
|
|
|
for(var k = 0 ; k < Nt ; k++) { |
|
unitCircle[k] = [Math.cos(t(k)), Math.sin(t(k))] ; |
|
} |
|
|
|
var contour = [] |
|
|
|
for(var k = 0 ; k < Nline ; k++) { |
|
contour[k] = g.append("path") ; |
|
contour[Nline + k] = g.append("path") ; |
|
contour[2 * Nline + k] = g.append("path") ; |
|
contour[3 * Nline + k] = g.append("path") ; |
|
contour[4 * Nline + k] = g.append("path") ; |
|
contour[5 * Nline + k] = g.append("path") ; |
|
contour[6 * Nline + k] = g.append("path") ; |
|
contour[7 * Nline + k] = g.append("path") ; |
|
} |
|
|
|
// var quiver = [] ; |
|
// for(var k = 0 ; k < Nline ; k++) { |
|
// quiver[k] = [] ; |
|
// for(var j = 0 ; j < Nt ; j++) { |
|
// quiver[k][j] = g.append("path") ; |
|
// } |
|
// } |
|
|
|
|
|
var dist2 = function(v, w) { |
|
return (v[0] - w[0]) * (v[0] - w[0]) + (v[1] - w[1]) * (v[1] - w[1]) ; |
|
} ; |
|
|
|
var init_data = function() { |
|
|
|
var contour_line = function(v, sign) { |
|
var d = [] ; |
|
var dx = .03 ; |
|
var f = objective_function(v) ; |
|
var df ; |
|
var xk, yk ; |
|
var v0 = [v[0], v[1]] ; |
|
d[0] = {x: v[0], y: v[1]} ; |
|
var count = 1 ; |
|
var skip = 5 ; |
|
var tol = .001 ; |
|
for(var k = 1 ; k < Nt + 1 ; k++) { |
|
grad = gradient_function(v) ; |
|
len = Math.sqrt(grad[0] * grad[0] + grad[1] * grad[1]) ; |
|
xk = v[0] - sign * dx * grad[1] / len ; |
|
yk = v[1] + sign * dx * grad[0] / len ; |
|
v[0] = xk ; |
|
v[1] = yk ; |
|
df = f - objective_function(v) ; |
|
var niter = 0 ; |
|
var maxiter = 100 ; |
|
while(Math.abs(df) > tol && niter < maxiter) { |
|
grad = gradient_function(v) ; |
|
len = Math.sqrt(grad[0] * grad[0] + grad[1] * grad[1]) ; |
|
var scale = df / len ; |
|
v[0] = v[0] + dx * scale * grad[0] ; |
|
v[1] = v[1] + dx * scale * grad[1] ; |
|
df = f - objective_function(v) ; |
|
niter++ ; |
|
} |
|
if(k === 1 || k % skip === 0 || k === Nt) { |
|
d[count] = {x: v[0], y: v[1]} ; |
|
//if(k > skip * 10 && dist2([d[count].x, d[count].y], v0) < .1) break ; |
|
count++ ; |
|
} |
|
} |
|
return d ; |
|
} |
|
|
|
for(var k = 0 ; k < Nline ; k++) { |
|
var d = contour_line([0, -Math.sqrt(start + k * spacing) / br], 1) ; |
|
contour[k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([0, -Math.sqrt(start + k * spacing) / br]))) ; |
|
d = contour_line([0, Math.sqrt(start + k * spacing) / br], 1) ; |
|
contour[Nline + k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([0, Math.sqrt(start + k * spacing) / br]))) ; |
|
d = contour_line([Math.sqrt(start + k * spacing) / ar, 0], 1) ; |
|
contour[2 * Nline + k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([Math.sqrt(start + k * spacing) / ar, 0]))) ; |
|
d = contour_line([-Math.sqrt(start + k * spacing) / ar, 0], 1) ; |
|
contour[3 * Nline + k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([-Math.sqrt(start + k * spacing) / ar, 0]))) ; |
|
|
|
d = contour_line([0, -Math.sqrt(start + k * spacing) / br], -1) ; |
|
contour[4 * Nline + k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([0, -Math.sqrt(start + k * spacing) / br]))) ; |
|
d = contour_line([0, Math.sqrt(start + k * spacing) / br], -1) ; |
|
contour[5 * Nline + k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([0, Math.sqrt(start + k * spacing) / br]))) ; |
|
d = contour_line([Math.sqrt(start + k * spacing) / ar, 0], -1) ; |
|
contour[6 * Nline + k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([Math.sqrt(start + k * spacing) / ar, 0]))) ; |
|
d = contour_line([-Math.sqrt(start + k * spacing) / ar, 0], -1) ; |
|
contour[7 * Nline + k] |
|
.datum(d) |
|
.attr("class", "line") |
|
.attr("d", line) |
|
.style('stroke', z(objective_function([-Math.sqrt(start + k * spacing) / ar, 0]))) ; |
|
} |
|
|
|
var grad_set = function(kline) { |
|
var d = [] ; |
|
var scaling = .05 ; |
|
|
|
for(var k = 0 ; k < Nt - 1 ; k++) { |
|
var xk = contour[kline].datum()[k].x ; |
|
var yk = contour[kline].datum()[k].y ; |
|
var grad = gradient_function([xk, yk]) ; |
|
var norm = Math.sqrt(grad[0] * grad[0] + grad[1] * grad[1]) ; |
|
grad[0] *= scaling * Math.sqrt(norm) / norm ; |
|
grad[1] *= scaling * Math.sqrt(norm) / norm ; |
|
if(isNaN(grad[0]) || isNaN(grad[1])) { |
|
grad[0] = 0 ; |
|
grad[1] = 0 ; |
|
} |
|
d[k] = [{x: xk, y: yk}, {x: xk - grad[0], y: yk - grad[1]}] ; |
|
} |
|
return d ; |
|
} |
|
|
|
for(var k = 0 ; k < Nline ; k++) { |
|
//var d = grad_set(k) ; |
|
var skip = 2 ; |
|
for(var j = 0 ; j < Nt - 1 ; j += skip) { |
|
//console.log(d[j]) ; |
|
//quiver[k][j] |
|
// .attr('class', 'gradient_line') |
|
// .datum(d[j]) |
|
// .attr("d", line) ; |
|
} |
|
} |
|
} |
|
|
|
init_data() ; |
|
|
|
var circle = g |
|
.append('circle') |
|
.style('stroke', 'none') |
|
.style('fill', 'green') |
|
.style('opacity', 0) |
|
.attr('r', 3) ; |
|
|
|
var dur = 333 ; |
|
|
|
var fadeIn = function(element, duration, delay) { |
|
if(duration === undefined) duration = dur ; |
|
if(delay === undefined) delay = 0 ; |
|
return element |
|
.transition() |
|
.duration(duration) |
|
.ease('linear') |
|
.style('opacity', 1) ; |
|
} |
|
|
|
var fadeOut = function(element, duration, delay) { |
|
if(duration === undefined) duration = dur ; |
|
if(delay === undefined) delay = 0 ; |
|
return element |
|
.transition() |
|
.duration(duration) |
|
.delay(delay) |
|
.ease('linear') |
|
.style('opacity', 0) ; |
|
} |
|
|
|
var drawing = false ; |
|
|
|
var draw_grad = function(xy) { |
|
if(drawing) return ; |
|
if(a === 0 && b === 0) return ; |
|
drawing = true |
|
var grad = gradient_function(xy) ; |
|
if(isNaN(grad[0]) || isNaN(grad[1]) || !isFinite(grad[0]) || !isFinite(grad[1])) { |
|
drawing = false ; |
|
return ; |
|
} |
|
var scale = 1 ; |
|
var d = [{x: xy[0], y: xy[1]}, {x: xy[0] - scale * grad[0], y: xy[1] - scale * grad[1]}] ; |
|
var dur = 1000 ; |
|
var gradLine = g |
|
.append('path') |
|
.attr('class', 'gradient_line') |
|
.attr('marker-end', 'url(#gradientMarker)') |
|
//.attr("stroke-dasharray", ("5, 2")) |
|
gradLine |
|
.style('opacity', 0) |
|
.datum(d) |
|
.attr("d", line) |
|
.transition() |
|
.duration(dur / 2) |
|
.ease('linear') |
|
.style('opacity', 1) |
|
.each('end', function() { drawing = false }) |
|
.transition() |
|
.duration(dur) |
|
.delay(2 * dur) |
|
.ease('linear') |
|
.style('opacity', 0) |
|
.remove() ; |
|
} ; |
|
|
|
var newton_step = function(xy) { |
|
// |
|
// solve the 2-by-2 system of equations for the Newton step p: H p = -g |
|
// |
|
H = hessian_function(xy) ; |
|
var grad = gradient_function(xy) ; |
|
var py = -grad[1] / (H[1][1] - H[1][0] * H[0][1] / H[0][0]) ; |
|
var px = (-grad[0] - H[0][1] * py) / H[0][0] ; |
|
var step = [px, py] ; |
|
return step ; |
|
} |
|
|
|
var stepping = false ; |
|
|
|
var draw_step = function(xy) { |
|
if(stepping) return ; |
|
if(a === 0 || b === 0) return ; |
|
stepping = true ; |
|
H = hessian_function(xy) ; |
|
var grad = gradient_function(xy) ; |
|
// var step = [-1/H[0][0] * grad[0], -1/H[1][1] * grad[1]] ; // assume that the Hessian is diagonal |
|
var py = -grad[1] / (H[1][1] - H[1][0] * H[0][1] / H[0][0]) ; |
|
var px = (-grad[0] - H[0][1] * py) / H[0][0] ; |
|
step = newton_step(xy) ; |
|
if(isNaN(step[0]) || isNaN(step[1]) || !isFinite(step[0]) || !isFinite(step[1])) { |
|
stepping = false ; |
|
return ; |
|
} |
|
var scale = .97 ; |
|
var d = [{x: xy[0], y: xy[1]}, {x: xy[0] + scale * step[0], y: xy[1] + scale * step[1]}] ; |
|
var dur = 1000 ; |
|
var stepLine = g |
|
.append('path') |
|
.attr('class', 'step_line') |
|
.attr('marker-end', 'url(#stepMarker)') |
|
stepLine |
|
.style('opacity', 0) |
|
.datum(d) |
|
.attr("d", line) |
|
.transition() |
|
.duration(dur / 2) |
|
.ease('linear') |
|
.style('opacity', 1) |
|
.each('end', function() { stepping = false }) |
|
.transition() |
|
.duration(dur) |
|
.delay(2 * dur) |
|
.ease('linear') |
|
.style('opacity', 0) |
|
.remove() ; |
|
} ; |
|
|
|
//svg.on('click', click_function) ; |
|
|
|
var coordText = d3.select('#coordText') |
|
.style('opacity', 0) ; |
|
var fText = d3.select('#fText') |
|
.style('opacity', 0) ; |
|
|
|
fText.html('f(x) = x<sup>T</sup> H x / 4') ; |
|
var delay = dur ; |
|
fadeIn(fText, 2 * dur, 2 * dur) ; |
|
|
|
|
|
var mouse_function = function() { |
|
var xy = d3.mouse(svg.node()) ; |
|
var xy0 = d3.mouse(g.node()) ; |
|
var textX = xy[0] - 35 ; |
|
if(xy[1] < 40) { |
|
textY = xy[1] + 40 ; |
|
} else { |
|
var textY = xy[1] - 30 ; |
|
} |
|
coordText |
|
.html('<table><tbody><tr><td>x<sub>1</sub>: ' + x.invert(xy[0]).toPrecision(3) + |
|
'</td><td>x<sub>2</sub>: ' + y.invert(xy[1]).toPrecision(3) + |
|
'</td><td>f(x): ' + objective_function([x.invert(xy0[0]), y.invert(xy0[1])]).toPrecision(3)) |
|
+ '</td></tr></tbody></table>' ; |
|
var dur = 1000 ; |
|
var delay = 2 * dur ; |
|
fadeOut(fadeIn(coordText), dur, delay) ; |
|
xy0[0] = x.invert(xy0[0]) ; |
|
xy0[1] = y.invert(xy0[1]) ; |
|
draw_grad(xy0) ; |
|
draw_step(xy0) ; |
|
} ; |
|
|
|
svg.on('mousemove', mouse_function) ; |
|
|
|
var run_newton = function(xy) { |
|
if(running) { |
|
return false ; // do nothing if already running |
|
} |
|
running = true ; // to prevent multiple visualizations from activating simultaneously |
|
} |
|
|
|
</script> |
|
</body> |
|
</html> |