Crate totsu

Totsu (凸 in Japanese) means convex.

This crate for Rust provides a basic primal-dual interior-point method solver: PDIPM.

Target problem

A common target problem is continuous scalar convex optimization such as LP, QP and QCQP. SOCP and SDP can also be handled with a certain effort. More specifically, \[ \begin{array}{ll} {\rm minimize} & f_{\rm obj}(x) \\ {\rm subject \ to} & f_i(x) \le 0 \quad (i = 0, \ldots, m - 1) \\ & A x = b, \end{array} \] where

• variables \( x \in {\bf R}^n \)
• \( f_{\rm obj}: {\bf R}^n \rightarrow {\bf R} \), convex and twice differentiable
• \( f_i: {\bf R}^n \rightarrow {\bf R} \), convex and twice differentiable
• \( A \in {\bf R}^{p \times n} \), \( b \in {\bf R}^p \).

Algorithm and design concepts

The overall algorithm is based on the reference: S. Boyd and L. Vandenberghe, "Convex Optimization", http://stanford.edu/~boyd/cvxbook/.

PDIPM has a core method solve which takes objective and constraint (derivative) functions as closures. Therefore solving a specific problem requires an implementation of those closures. You can use a pre-defined implementations (see predef), as well as construct a user-defined tailored version for the reason of functionality and efficiency.

This crate has no dependencies on other crates at all. Necessary matrix operations are implemented in mat and matsvd.

Example: QP

use totsu::prelude::*;
use totsu::predef::*;

let n: usize = 2; // x0, x1
let m: usize = 1;
let p: usize = 0;

// (1/2)(x - a)^2 + const
let mat_p = Mat::new(n, n).set_iter(&[
    1., 0.,
    0., 1.
]);
let vec_q = Mat::new_vec(n).set_iter(&[
    -(-1.), // -a0
    -(-2.)  // -a1
]);

// 1 - x0/b0 - x1/b1 <= 0
let mat_g = Mat::new(m, n).set_iter(&[
    -1. / 2., // -1/b0
    -1. / 3.  // -1/b1
]);
let vec_h = Mat::new_vec(m).set_iter(&[
    -1.
]);

let mat_a = Mat::new(p, n);
let vec_b = Mat::new_vec(p);

let param = PDIPMParam::default();
let rslt = PDIPM::new().solve_qp(&param, &mut std::io::sink(),
                                 &mat_p, &vec_q,
                                 &mat_g, &vec_h,
                                 &mat_a, &vec_b).unwrap();

let exp = Mat::new_vec(n).set_iter(&[
    2., 0.
]);
println!("rslt = {}", rslt);
assert!((&rslt - exp).norm_p2() < param.eps);

You can find other test examples of pre-defined solvers in lib.rs.

Modules

lp	Linear program
mat	Matrix
matsvd	Matrix singular value decomposition
pdipm	Primal-dual interior point method
predef	Pre-defined solvers
prelude	Prelude
qcqp	Quadratically constrained quadratic program
qp	Quadratic program
sdp	Semidefinite program
socp	Second-order cone program