28:null 29:["$","title",null,{"children":"Optimization | Thomas Oberbichler | Observable"}] 2e:T15ce,{ const height = Math.ceil(width * screen.height / screen.width); const nx = parseInt(width / 5) const ny = parseInt(height / 5) const drawingTime = 200 const svg = d3.select(DOM.svg(width, height)).attr('id', 'canvas') const domainX = fun.domainX const domainY = fun.domainY const domainF = fun.domainF const contourStep = fun.contourStep const factorX = width / (domainX[1] - domainX[0]) const factorY = height / (domainY[1] - domainY[0]) const rescale = ([a, b], factor) => { const len = Math.abs(b - a) const mid = 0.5 * (a + b) const f = Math.min(factorX, factorY) return [mid - 0.5 * len * factor / f, mid + 0.5 * len * factor / f] } const scaleX = d3.scaleLinear() .domain([0, width]) .range(rescale(domainX, factorX)) const scaleY = d3.scaleLinear() .domain([0, height]) .range(rescale(domainY, factorY)) const thresholds = d3.range(domainF[0], domainF[1], contourStep) const colorScale = d3.scaleLinear() .domain(d3.extent(thresholds)) .interpolate(() => d3.interpolateYlGnBu) const lineFunction = d3.line() .x(d => d.x) .y(d => d.y) const drawPath = (pathData, type, color, visible) => { gradientPathG.selectAll(type) .data(pathData) .enter() .append('path') .attr('class', type) .attr('d', lineFunction(pathData.slice(0, 1))) .attr('stroke', color) .attr('stroke-width', 3) .attr('stroke-opacity', 0.7) .attr('fill', 'none') .attr('visibility', visible ? 'visible' : 'hidden') .transition() .duration(drawingTime) .delay((d, i) => drawingTime * i) .attr('d', (d, i) => lineFunction(pathData.slice(0, i + 1))) } const scale = (point) => ({ x: scaleX.invert(point.x), y: scaleY.invert(point.y) }) const settings = { maxIterations, rtol: 10**(-rtol), maxLineSearchIterations } const keys = ['Gradient-Descent', 'Momentum', 'Levenberg-Marquardt', 'Newton-Raphson'] const color = d3.scaleOrdinal() .domain(keys) .range(d3.schemeSet1) const paths = [ { key: 'gradient-descent', solve: (x, y) => new GradientDescent(settings).run(fun, x, y, 10**(-alpha0)), color: color('Gradient-Descent'), visible: true }, { key: 'momentum', solve: (x, y) => new Momentum(settings).run(fun, x, y, 10**(-alpha0), momentum), color: color('Momentum'), visible: true }, { key: 'lm', solve: (x, y) => new LevenbergMarquardt(settings).run(fun, x, y, tau == 9 ? 0 : 10**(-tau)), color: color('Levenberg-Marquardt'), visible: true }, { key: 'newton-raphson', solve: (x, y) => new NewtonRaphson(settings).run(fun, x, y, tau == 9 ? 0 : 10**(-tau)), color: color('Newton-Raphson'), visible: true } ] const minimize = (x0, y0) => { gradientPathG.selectAll('path').remove() for (const path of paths) { drawPath(path.solve(x0, y0).map(scale), path.key, path.color, path.visible) } } const mousedown = (event) => { const [x, y] = d3.pointer(event) minimize(scaleX(x), scaleY(y)) } const functionG = svg.append('g') .on('mousedown', mousedown) const gradientPathG = svg.append('g') .attr('id', 'paths') const contours = d3.contours().size([nx, ny]).thresholds(thresholds) const grid = new Array(nx * ny) for (let i = 0; i < nx; i++) { for (let j = 0; j < ny; j++) { const x = scaleX(parseFloat(i) / nx * width) const y = scaleY(parseFloat(j) / ny * height) grid[i + j * nx] = fun.f(x, y) } } functionG.selectAll('path') .data(contours(grid)) .enter().append('path') .attr('d', d3.geoPath(d3.geoIdentity().scale(width / nx))) .attr('fill', (d) => colorScale(d.value)) .attr('stroke', 'none') svg.selectAll('circle') .data(fun.extrema) .enter() .append('circle') .attr('cx', d => scaleX.invert(d[0])) .attr('cy', d => scaleY.invert(d[1])) .attr('r', 3) .attr('fill', 'none') .attr('stroke', 'green') .attr('stroke-width', 1) function menuMouseDown() { const dot = d3.select(this) const type = dot.attr('class') const p = d3.select('#paths').selectAll(`.${type}`) // if (paths.length == 0) return let index = 0 for (const path of paths) { if (path.key == type) break index += 1 } console.log(index) const visible = paths[index].visible if (visible) { dot.attr('fill-opacity', 0.2) p.attr('visibility', 'hidden') } else { dot.attr('fill-opacity', 1.0) p.attr('visibility', 'visible') } paths[index].visible = !paths[index].visible } svg.append('rect') .attr('x', 30) .attr('y', 30) .attr('width', 220) .attr('height', keys.length * 25 + 20) .attr('fill', 'white') .attr('opacity', 0.7) svg.selectAll('menu-dots') .data(keys) .enter() .append('circle') .attr('class', (d, i) => paths[i].key) .attr('cx', 50) .attr('cy', (d, i) => 50 + i * 25) .attr('r', 7) .style('stroke', color) .style('stroke-width', 2) .style('fill', color) .attr('fill-opacity', (d, i) => paths[i].visible ? 1.0 : 0.2) .on('mousedown', menuMouseDown) svg.selectAll('menu-labels') .data(keys) .enter() .append('text') .attr('x', 70) .attr('y', (d, i) => 50 + i * 25) .style('fill', color) .text(d => d) .attr('text-anchor', 'left') .style('alignment-baseline', 'middle') return svg.node() }2f:T653,generateFunction = (constraints, scope={}) => { const w = [] const _g = [] const _dg = [] for (const [expression, weight] of constraints) { w.push(math.evaluate(weight, scope)) const gi = math.simplify(expression, scope) _g.push(gi.compile()) const dx = math.derivative(gi, 'x') const dy = math.derivative(gi, 'y') _dg.push(dx.compile()) _dg.push(dy.compile()) } const g = (x, y) => _g.map(gi => gi.evaluate({x, y})) const dg = (x, y) => _dg.map(dgi => dgi.evaluate({x, y})) const dgtdg = (x, y) => { const _dg = dg(x, y) const m = _dg.length / 2 let dxx = 0 let dxy = 0 let dyy = 0 for (let k = 0; k < m; k++) { dxx += w[k] * _dg[k * 2 + 0]**2 dxy += w[k] * _dg[k * 2 + 0] * _dg[k * 2 + 1] dyy += w[k] * _dg[k * 2 + 1]**2 } return [dxx, dxy, dyy] } const fExpr = math.simplify(constraints.map((constraint, i) => `0.5 * ${w[i]} * (${constraint[0]})^2`).join(' + '), scope) const _f = fExpr.compile() const dfExpr = [ math.derivative(fExpr, 'x'), math.derivative(fExpr, 'y') ] const _df = dfExpr.map(expr => expr.compile()) const hmExpr = [ math.derivative(dfExpr[0], 'x'), math.derivative(dfExpr[0], 'y'), math.derivative(dfExpr[1], 'y') ] const _hm = hmExpr.map(expr => expr.compile()) const f = (x, y) => _f.evaluate({x, y}) const df = (x, y) => _df.map(dfi => dfi.evaluate({x, y})) const hm = (x, y) => _hm.map(ddfi => ddfi.evaluate({x, y})) return {f, df, hm, g, dg, dgtdg, w, fExpr, dfExpr, hmExpr} }30:T448,class LevenbergMarquardt { constructor({maxIterations=100, rtol=1e-8, maxLineSearchIterations=5}) { this.maxIterations = maxIterations this.rtol = rtol this.maxLineSearchIterations = maxLineSearchIterations } run(fun, x0, y0, tau=0) { const history = [{x: x0, y: y0}] let x1, y1 for (let iteration = 0; iteration < this.maxIterations; iteration++) { const f0 = fun.f(x0, y0) const [dx, dy] = fun.df(x0, y0) if (Math.sqrt(dx**2 + dy**2) < this.rtol) break const [dxx, dxy, dyy] = fun.dgtdg(x0, y0) const [vx, vy] = linearSolve([dxx + tau, dxy, dyy + tau], [-dx, -dy]) if (isNaN(vx) || isNaN(vy)) break var alpha = 1.0 for (let j = 0; j < this.maxLineSearchIterations; j++) { x1 = x0 + alpha * vx y1 = y0 + alpha * vy const f1 = fun.f(x1, y1) if (f1 < f0) break alpha /= 2 } history.push({x: x1, y: y1}) x0 = x1 y0 = y1 } return history } }31:T475,class NewtonRaphson { constructor({maxIterations=100, rtol=1e-8, maxLineSearchIterations=5}) { this.maxIterations = maxIterations this.rtol = rtol this.maxLineSearchIterations = maxLineSearchIterations } run(fun, x0, y0, tau=0) { const history = [{x: x0, y: y0}] let x1, y1 for (let i = 0; i < this.maxIterations; i++) { const f0 = fun.f(x0, y0) const [dx, dy] = fun.df(x0, y0) const rnorm = Math.sqrt(dx**2 + dy**2) if (rnorm < this.rtol) break const [dxx, dxy, dyy] = fun.hm(x0, y0) const det = dxx * dyy - dxy**2 const [vx, vy] = linearSolve([dxx + tau, dxy, dyy + tau], [-dx, -dy]) if (isNaN(vx) || isNaN(vy)) break let alpha = 1.0 for (let j = 0; j < this.maxLineSearchIterations; j++) { x1 = x0 + alpha * vx y1 = y0 + alpha * vy const f1 = fun.f(x1, y1) if (f1 < f0) break alpha /= 2 } history.push({x: x1, y: y1}) x0 = x1 y0 = y1 } return history } }32:[] 2c:{"id":"67f9b3c3a649ec3a","slug":"optimization","title":"Optimization","thumbnail":"d994ed112e7833e91a8f2bec4186b00da6d1551d4dc3f4a36b912f61c1e6e0bf","access_level":"public","create_time":"$D2021-01-08T10:59:29.816Z","update_time":"$D2021-06-30T15:33:45.586Z","view_time":null,"first_public_time":"$D2021-01-08T11:44:48.541Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"63ea0ba327c02e72","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":"starter_2024"},"version":227,"publish_version":227,"role":null,"authored":false,"authors":[{"type":"individual","id":"c69ce5b2b338318d","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":null}],"members":[{"type":"individual","id":"c69ce5b2b338318d","login":"oberbichler","name":"Thomas Oberbichler","avatar_url":"https://avatars-next.observableusercontent.com/265b4716883baf8f5978e349384c2921f054e6d4c37507f37a41a09745720cbe","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Optimization","cells":[{"id":0,"value":"md`# Optimization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"viewof selectFunction = radio({\n title: 'Function',\n options: [\n {value: 0, label: 'Circle'},\n {value: 1, label: 'Ellipse'},\n {value: 2, label: 'Rosenbrock'},\n {value: 3, label: 'Two-Bar-Truss'}\n ],\n value: 2\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"fullscreen = {\n const button = html`