RsBundle  Artifact [3cdb1d704e]

Artifact 3cdb1d704e3c4df9702de57c2be044fda52954e4:

• File src/minorant.rs — part of check-in [f459ca047d] at 2019-07-24 08:00:41 on branch parallel-primal — Relax requirements of `Aggregatable::combine` to `Borrow`. Instead of an iterator over references the new implementation of `combine` requires the elements only to implement `Borrow`. This way it can be called with references as well as with values. (user: fifr size: 3635) [more...]

// Copyright (c) 2016, 2017, 2018, 2019 Frank Fischer <frank-fischer@shadow-soft.de>
//
// This program is free software: you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

//! A linear minorant.

use crate::{DVector, Real};

use std::borrow::Borrow;
use std::fmt;

/// An aggregatable object.
pub trait Aggregatable {
    /// Return $\sum\_{i=1}\^n alpha_i m_i$.
    fn combine<I, A>(aggregates: I) -> Self
    where
        I: IntoIterator<Item = (Real, A)>,
        A: Borrow<Self>;
}

/// Implement for empty tuples.
impl Aggregatable for () {
    fn combine<I, A>(_aggregates: I)
    where
        I: IntoIterator<Item = (Real, A)>,
        A: Borrow<Self>,
    {
    }
}

impl Aggregatable for Real {
    fn combine<I, A>(aggregates: I) -> Real
    where
        I: IntoIterator<Item = (Real, A)>,
        A: Borrow<Self>,
    {
        aggregates.into_iter().map(|(alpha, y)| alpha * y.borrow()).sum()
    }
}

/**
 * A linear minorant of a convex function.
 *
 * A linear minorant of a convex function $f \colon \mathbb{R}\^n \to
 * \mathbb{R}$ is a linear function of the form
 *
 *   \\[ l \colon \mathbb{R}\^n \to \mathbb{R}, x \mapsto \langle g, x
 *   \rangle + c \\]
 *
 * such that $l(x) \le f(x)$ for all $x \in \mathbb{R}\^n$.
 */
#[derive(Clone, Debug)]
pub struct Minorant {
    /// The constant term.
    pub constant: Real,

    /// The linear term.
    pub linear: DVector,
}

impl fmt::Display for Minorant {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} + y * {}", self.constant, self.linear)?;
        Ok(())
    }
}

impl Default for Minorant {
    fn default() -> Minorant {
        Minorant {
            constant: 0.0,
            linear: dvec![],
        }
    }
}

impl Minorant {
    /// Return a new 0 minorant.
    pub fn new(constant: Real, linear: Vec<Real>) -> Minorant {
        Minorant {
            constant,
            linear: DVector(linear),
        }
    }

    /**
     * Evaluate minorant at some point.
     *
     * This function computes $c + \langle g, x \rangle$ for this minorant
     *   \\[\ell \colon \mathbb{R}\^n \to \mathbb{R}, x \mapsto c + \langle g, x \rangle\\]
     * and the given point $x \in \mathbb{R}\^n$.
     */
    pub fn eval(&self, x: &DVector) -> Real {
        self.constant + self.linear.dot(x)
    }

    /**
     * Move the center of the minorant.
     */
    pub fn move_center(&mut self, alpha: Real, d: &DVector) {
        self.constant += alpha * self.linear.dot(d);
    }
}

impl Aggregatable for Minorant {
    fn combine<I, A>(aggregates: I) -> Minorant
    where
        I: IntoIterator<Item = (Real, A)>,
        A: Borrow<Minorant>,
    {
        let mut constant = 0.0;
        let mut linear = dvec![];
        for (i, (alpha, m)) in aggregates.into_iter().enumerate() {
            let m = m.borrow();
            if i == 0 {
                linear.resize(m.linear.len(), 0.0);
            }
            constant += alpha * m.constant;
            linear.add_scaled(alpha, &m.linear);
        }

        Minorant { constant, linear }
    }
}