Optimization

A high-performance C++ library of numerical optimization algorithms, problem interfaces, and utilities. This README is ready to copy into the repository root and contains concrete descriptions of important classes, implemented algorithms, usage examples, build instructions, and API summaries.

Table of Contents

• Overview
• Design Goals & Architecture
• Core Concepts & Classes
• Implemented Algorithms
• Data Structures
• Example: define an objective and run an optimizer
• Build & Quick Start
• Benchmarks & Tests
• Contributing
• License
• Contact

Overview

This repository provides a modular, extensible C++ framework for solving continuous optimization problems (unconstrained and constrained), including deterministic local solvers, quasi-Newton methods, trust-region solvers, derivative-free methods, and meta-heuristics. The code emphasizes numerical stability, clear interfaces for defining problems, and utility components (I/O, logging, benchmark harnesses) to compare algorithm performance.

Design Goals & Architecture

• Small, well-documented public API for problem definition and solver invocation.
• Pluggable components: line-search, preconditioner, stopping criteria, and logging.
• Separate algorithm implementation from problem I/O.
• Efficient use of dense and sparse linear algebra; optional adapters for Eigen, BLAS/LAPACK.
• Comprehensive examples and benchmark drivers.

Typical high-level architecture:

• optimization::Problem - user-provided objective and derivatives
• optimization::Optimizer (abstract) - common control flow and callback hooks
• Concrete optimizers (LBFGS, Newton, TrustRegion, CG, NelderMead)
• utilities: LineSearch, Preconditioner, Logger, Timer, RNG
• data types: Vector, Matrix, SparseMatrix (thin wrappers)

Core Concepts & Classes

Below are the primary classes/interfaces you will use. The signatures are representative and match the library’s design intent.

• namespace: optimization

• class Problem

  • Purpose: user implements to describe objective, gradient, (optional) Hessian or Hessian-vector product.
  • Key methods:
    • double value(const Vector& x) const;
    • void gradient(const Vector& x, Vector& g) const;
    • void hessian(const Vector& x, Matrix& H) const; // optional
    • void hessVec(const Vector& x, const Vector& v, Vector& Hv) const; // optional for large-scale
  • Notes: Methods must be thread-safe if you enable parallel evaluation in benchmarks.

• class Optimizer (abstract)

  • Purpose: defines the optimization loop and common options.
  • Key methods / options:
    • struct Options { int maxIterations; double tol; bool verbose; };
    • virtual Result optimize(Problem& problem, Vector& x0) = 0;
    • setOptions(const Options& o);
    • attachLogger(Logger*);
  • Result contains final x, objective value, num iterations, status enum.

• class LineSearch

  • Implementations: ArmijoBacktracking, Wolfe, StrongWolfe
  • Method: double search(const Problem&, const Vector& x, const Vector& p, double fx, const Vector& g, double initStep);

• class Preconditioner (abstract)

  • Purpose: accelerate iterative linear solves
  • Implementations: Identity, Diagonal, L-BFGS based

• class Logger

  • Purpose: structured runtime info (iteration, fx, ||g||, step length)
  • Output sinks: console, JSON, CSV

• class LinearSolver (abstract)

  • Purpose: solve linear systems arising in Newton/TrustRegion steps
  • Implementations: Dense direct (Cholesky/LU), Conjugate Gradient (for SPD), MINRES

Detailed class reference and example signatures:

namespace optimization {

struct Result {
  Vector x;
  double f;
  int iterations;
  enum Status { Converged, MaxIter, Diverged, Error } status;
};

class Problem {
public:
  virtual ~Problem() = default;
  virtual double value(const Vector& x) const = 0;
  virtual void gradient(const Vector& x, Vector& g) const = 0;
  virtual void hessian(const Vector& x, Matrix& H) const { throw; }
  virtual void hessVec(const Vector& x, const Vector& v, Vector& Hv) const { throw;}
};

class Optimizer {
public:
  struct Options { int maxIterations = 1000; double tol = 1e-8; bool verbose = false; };
  virtual ~Optimizer() = default;
  virtual Result optimize(Problem& prob, Vector& x0) = 0;
  void setOptions(const Options& o);
};
}

Implemented Algorithms

This project contains production-ready implementations and research-grade variants of the following algorithms:

• Gradient Descent

  • Basic steepest descent with optional momentum and adaptive step-size.
  • Use-cases: cheap to implement, educational, baseline comparisons.

• Line-search based Quasi-Newton

  • BFGS and L-BFGS (limited-memory)
  • Typical options: memory size (m), line-search (Wolfe/Armijo), diagonal scaling.
  • Strengths: good for medium-scale problems (n up to tens of thousands with L-BFGS).

• Newton and Damped Newton

  • Dense Newton with direct linear solves and damping/backtracking.
  • Preconditioned iterative Newton for large-scale via Hessian-vector products (hessVec).

• Trust-Region Methods

  • Dogleg and More-Sorensen variants.
  • Subproblem solvers: exact (dense) and iterative CG-based (for large sparse problems).
  • Well-suited to ill-conditioned problems where Hessian provides curvature.

• Conjugate Gradient (nonlinear CG)

  • Fletcher-Reeves and Polak-Ribiere restart strategies.
  • Line-search variants integrated.

• Derivative-free methods

  • Nelder-Mead simplex method (for small-dimensional noisy problems).
  • Pattern search variants.

• Global/metaheuristic methods

  • Simulated Annealing (SA) - temperature schedules, cooling strategies.
  • Genetic Algorithm (GA) - chromosome representation, mutation/crossover operators.
  • CMA-ES (Covariance Matrix Adaptation) - basic implementation available in examples or experiments.

• Constrained optimization helpers

  • Simple bound handling via projected methods (projected gradient, L-BFGS-B style).
  • Augmented Lagrangian and penalty wrappers (experimental).

For each solver there are documented Options: stopping criteria (tol on gradient norm, relative objective tolerance), maximum iterations, step-size parameters, line-search tolerances, verbosity, and logging sinks.

Data Structures

• Vector

  • Small wrapper around std::vector or Eigen::VectorXd (optional).
  • Provides BLAS-like operations: dot, axpy, scale, norm.

• Matrix

  • Dense matrix type; thin wrapper or alias to Eigen::MatrixXd when Eigen is enabled.

• SparseMatrix

  • CSR-format for large sparse problems; adapters to suitesparse / Eigen's sparse types.

• ProblemIO

  • Parsers/serializers for simple .dat/.json formats to describe starting points, known solutions, parameter bounds.

Example: define an objective and run an optimizer

This minimal example shows defining a problem (Rosenbrock) and running L-BFGS.

// examples/rosenbrock.cpp
#include "optimization.hpp" 

using namespace optimization;

struct Rosenbrock : public Problem {
  double a, b;
  Rosenbrock(double a_=1.0, double b_=100.0) : a(a_), b(b_) {}
  double value(const Vector& x) const override {
    double t1 = a - x[0];
    double t2 = x[1] - x[0]*x[0];
    return t1*t1 + b*t2*t2;
  }
  void gradient(const Vector& x, Vector& g) const override {
    g.resize(2);
    g[0] = -2.0*(a - x[0]) - 4.0*b*(x[1] - x[0]*x[0])*x[0];
    g[1] =  2.0*b*(x[1] - x[0]*x[0]);
  }
};

int main() {
  Vector x0 = { -1.2, 1.0 };
  Rosenbrock prob;
  LbfgsOptimizer::Options opts;
  opts.maxIterations = 1000;
  opts.tol = 1e-10;
  LbfgsOptimizer solver;
  solver.setOptions(opts);
  auto result = solver.optimize(prob, x0);
  if (result.status == Result::Converged) {
    std::cout << "Converged in " << result.iterations << " iter, f=" << result.f << "\n";
  }
  return (result.status==Result::Converged) ? 0 : 1;
}

API example usage notes:

• Choose optimizer: LbfgsOptimizer, BfgsOptimizer, NewtonOptimizer, TrustRegionOptimizer, NelderMeadOptimizer, CGOptimizer.
• Create problem by inheriting Problem and implementing value(), gradient(), optionally hessian() or hessVec().
• Pass initial guess (Vector) by reference to optimize().
• Inspect Result for final status and metadata.

Build & Quick Start

Prerequisites:

• C++17-capable compiler (GCC, Clang, MSVC)
• CMake >= 3.15
• Optional: Eigen, BLAS/LAPACK for performance

Basic build:

git clone https://github.com/pawli444/Optimization.git
cd Optimization
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build . -- -j$(nproc)

Run examples (after build):

• Binaries are placed in build/bin or build/examples

./build/examples/rosenbrock