optimization_solvers/
lib.rs

1#[cfg(feature = "lbfgsb")]
2use lbfgsb_sys::lbfgsb as ffi;
3#[cfg(feature = "lbfgsb")]
4use lbfgsb_sys::string as ffi_string;
5use nalgebra::{DMatrix, DVector};
6#[cfg(feature = "lbfgsb")]
7use std::ffi::CStr;
8
9use tracing::{debug, error, info, trace, warn};
10use tracing_appender::non_blocking::WorkerGuard;
11use tracing_subscriber::{
12    fmt, layer::SubscriberExt, util::SubscriberInitExt, EnvFilter, Layer, Registry,
13};
14
15// Deriving new solvers for STRONGLY CONVEX functions in UNCONSTRAINED OPTIMIZATION setting (which assume EXACT LINE SEARCH, so a bit more optimistic than the general case in which you use inexact line search):
16// - Define a new line search method (or use existing one like backtracking)
17// - Define a new direction update method (or use existing one like steepest descent)
18// - Since the objective is strongly convex, there is a fixed range [m,M] in which the hessian of the function lives (at any point)
19// - Considering the upper bound of the hessian, assume EXACT line search minimizing the rhs of the inequality f(x_k + t*d_k) <= f(x_k) + t*grad_k.dot(d_k) + t^2*M/m
20//      - If instead you have bounds of the step length of a certain inexact line search (typically you infer them from the exit condition of the line search), substitute the step length with the min of the possible alternatives
21//      - notice that this is the simple inequality f(y) >= f(x) + grad_f(x).dot(y-x) + 1/2 * (y-x).dot(H(x).(y-x)) for y=x+t*d substituting the hessian with its upper bound (so we revert the inequality sign)
22// - Once that you have an optimal step length, inject it in the equation
23// - Using some known equalities get rid of the gradient of the function
24// - Put -p^* on both side of the equation (so that you can build the suboptimal error E_k = f(x_k) - p^*)
25// - Describe the inequality as a Differential Inequality in discrete time (E_{k+1} <= f(E_k)) and compute the general solution
26//      - The general solution draws the trajectory of the upper bound of the suboptimal error:
27//      - first check you want to do is that it converges asymptotically to zero
28//      - Define a tolerance level "q" and set the general solution <= q. Apply some transformations if needed to solve the inequality for the iteration number k: this gives you a lower bound of the number of iterations needed to achieve the desired tolerance. Typically this lower bound is increasing function of suboptimality of the initial point (f(x_0) - p^*) and the upper bound of the condition number of the hessian (M/m). Of course it should be decreasing of the tolerance level q (the more tolerance you have, the lower is the number of required iterations to achieve that convergence).
29//      - From the inequality of the general solution, apply some transformations to verify what is the convergence rate of the algorithm (for example in the gradient descent if you apply the log you come up with a function which is linear in k, describing a linear convergence rate).
30
31pub mod tracer;
32pub use tracer::*;
33
34pub mod ls_solver;
35pub use ls_solver::*;
36
37pub mod func_eval;
38pub use func_eval::*;
39
40pub mod line_search;
41pub use line_search::*;
42
43pub mod number;
44pub use number::*;
45
46pub mod quasi_newton {
47    use super::*;
48    pub mod bfgs;
49    pub use bfgs::*;
50    pub mod bfgs_b;
51    pub use bfgs_b::*;
52    pub mod broyden;
53    pub use broyden::*;
54    pub mod broyden_b;
55    pub use broyden_b::*;
56    pub mod dfp;
57    pub use dfp::*;
58    pub mod dfp_b;
59    pub use dfp_b::*;
60    pub mod sr1_b;
61    pub use sr1_b::*;
62
63    #[cfg(feature = "lbfgsb")]
64    pub mod lbfgsb;
65    #[cfg(feature = "lbfgsb")]
66    pub use lbfgsb::*;
67}
68pub use quasi_newton::*;
69
70pub mod steepest_descent {
71    use super::*;
72    pub mod gradient_descent;
73    pub use gradient_descent::*;
74
75    pub mod coordinate_descent;
76    pub use coordinate_descent::*;
77
78    pub mod pnorm_descent;
79    pub use pnorm_descent::*;
80
81    pub mod spg;
82    pub use spg::*;
83
84    pub mod projected_gradient_descent;
85    pub use projected_gradient_descent::*;
86}
87
88pub use steepest_descent::*;
89
90pub mod newton;
91pub use newton::*;
92
93#[cfg(not(target_arch = "wasm32"))]
94pub mod plotter_3d;
95#[cfg(not(target_arch = "wasm32"))]
96pub use plotter_3d::*;
97
98// WASM-specific modules and exports
99#[cfg(target_arch = "wasm32")]
100pub mod wasm;
101#[cfg(target_arch = "wasm32")]
102pub use wasm::*;
optimization_solvers/lib.rs

optimization_solvers/
lib.rs
