Published
Edited
Mar 27, 2020
Insert cell
md`# gradient descent with backtracking line search

* objective: squared norm of a trivector, with a fixed ${tex `\mathbf{v}`}
* try to find the othoginal unit bivector

* result is initialization dependent, need momentum?
`
Insert cell
Algebra(3,0, ()=>{
// squared norm
const cost = (plane, v)=>{var volume_v = plane.Normalized ^ v.Normalized; return (-1)*volume_v.Reverse << volume_v;}
//const cost = (v, plane)=>{var volume_v = plane.Normalized ^ v.Normalized; return (-1)*volume_v.Reverse << volume_v;}
var d = this.D(cost)
var dt = this.Dt(cost);
function line_search_meta(...args){ // backtracking line search
const alpha = 0.25, beta = 0.8; // alpha in (0,0.5); bata in (0,1)
const ls_th = 50; // maximum line search iteration number
const x = args[0];
const tail_args = args.slice(1);
const fx = cost.apply(null, args);
const delta_x = dt.apply(null,args);
const nabla_f = d.apply(null,args);
const alpha_nabla_f_delta_x = alpha * nabla_f * delta_x;
var t = 1; // initial line search rate t=1
for (var i = 0; i < ls_th; i++){
if (cost.apply(null, [].concat(x + t * delta_x, tail_args)) > fx + t * alpha_nabla_f_delta_x){
t = beta * t; // update rate t
} else {
break;
}
}
return t;
}
function gradient_descent(...args){ // gradient descent
// inilization
var i_th = 50; // var i_th = 500,
var th_break = 10e-5; // var th_break = Math.sqrt(Number.EPSILON)*10;
var p_cost = Number.MAX_SAFE_INTEGER; // assign a large number to previous cost, for checking improvement

var log_cost = [], log_x = [], log_rate_t = []; // temp log var
for (var i = 0; i < i_th; i++) {
var t = line_search_meta.apply(null,args); log_rate_t.push(t); // line search
args[0] = args[0] - t * dt.apply(null, args)[0]; log_x.push(args[0]); // update x

var temp_cost = cost.apply(null, args); log_cost.push(temp_cost[0]);
if (Math.abs(p_cost - temp_cost) < th_break){break;} else {p_cost = temp_cost;} // check improvement
}// end, gradient descent loop

return {'x':args[0].Normalized+'', log_cost, log_rate_t};
} // end, gradient_descent function

var guess = 1e12+1e23+0.5e13, v = 1e3;
return gradient_descent(guess, v);
// return gradient_descent(v, guess);
})
Insert cell
Algebra = require('ganja.js')
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more