RsBundle  Check-in [a6d869f640]

use super::masterprocess::{self, MasterConfig, MasterProcess, MasterResponse, Response};
use crate::data::Minorant;
use crate::master::{Builder as MasterBuilder, MasterProblem};
use crate::problem::{FirstOrderProblem, UpdateState};
use crate::terminator::{StandardTerminatable, StandardTerminator, Terminator};
use crate::weighter::{HKWeightable, HKWeighter, Weighter};

pub mod guessmodels;
use guessmodels::{Guess, GuessModel, NearestValue};

/// The default iteration limit.
pub const DEFAULT_ITERATION_LIMIT: usize = 10_000;

/// The default solver.
pub type DefaultSolver<P> = Solver<P, StandardTerminator, HKWeighter, crate::master::FullMasterBuilder>;

    fn aggregated_primal(&self, i: usize) -> &Pr {
        &self.primal_aggrs[i]
    }
}

/// An evaluation point.
#[derive(Clone)]
pub struct Point {
    /// The globally unique index of the evaluation point.
    index: usize,

    /// The evaluation point itself.
    point: Arc<DVector>,
}

impl Point {
    fn distance(&self, p: &Point) -> Real {
        if self.index != p.index {
            let mut d = self.point.as_ref().clone();
            d.add_scaled(-1.0, &p.point);
            d.norm2()
        } else {
            Real::zero()
        }
    }
}












































































/// Model data of a single subproblem.
///
/// This struct does not handle the subproblem model itself. However, it handles
/// the asynchronous precision data, i.e. the guessed Lipschitz-constant and the
/// distance of the evaluation points to the candidate.
///
/// The concrete model used for computing the guessed values in the candidate
/// and the center must be provided by an implementation of `SubProblem`.
struct SubData {
    /// The index associated with this subproblem.
    fidx: usize,
    /// The subproblem.
    sub: Box<dyn GuessModel>,
    /// The current candidate index.
    candidate_index: usize,
    /// The last index at which the evaluation has been started.
    last_eval_index: usize,
    /// Whether a subproblem evaluation is currently running.
    is_running: bool,
    /// Whether the last evaluation has been sufficiently close.
    is_close_enough: bool,
    /// The guess value and its evaluation distance in the current center.
    center_guess: Guess,
    /// The current guess of the Lipschitz constant.
    l_guess: Real,
}

impl SubData {
    fn new(fidx: usize, sub: Box<dyn GuessModel>) -> SubData {
        SubData {
            fidx,
            sub,
            last_eval_index: 0,
            candidate_index: 0,
            is_running: false,
            is_close_enough: false,

            tx,
            &mut self.threadpool,
        ));

        debug!("Initial problem evaluation");
        // We need an initial evaluation of all oracles for the first center.
        self.data.subs = (0..m)
            .map(|fidx| SubData::new(fidx, Box::new(NearestValue::new())))
            .collect();
        self.data.nxt_y = self.data.cur_y.clone();

        // The initial evaluation point.
        let point = Point {
            index: self.data.candidate_index,
            point: self.data.cur_y.clone(),

/*
 * Copyright (c) 2020 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/>
 */

use super::Point;
use crate::{data::Minorant, Real};

use num_traits::{Float, Zero};
use std::sync::Arc;

mod nearestvalue;
pub use nearestvalue::NearestValue;

/// A guessed function value.
#[derive(Clone, Copy)]
pub struct Guess {
    /// The guessed value.
    pub value: Real,
    /// The accuracy distance.
    pub dist: Real,
}

impl Guess {
    /// Create a new guess value.
    ///
    /// If `dist` is zero the value is assumed to be exact.
    pub fn new(value: Real, dist: Real) -> Guess {
        Guess { value, dist }
    }

    /// Create an approximate guess value.
    pub fn new_approx(value: Real, dist: Real) -> Guess {
        Guess { value, dist }
    }

    /// Create an exact guess value.
    pub fn new_exact(value: Real) -> Guess {
        Guess {
            value,
            dist: Real::zero(),
        }
    }

    /// Return `true` if this is an exact guess value.
    ///
    /// In other words, the value is not `guessed` anymore.
    pub fn is_exact(&self) -> bool {
        self.dist.is_zero()
    }
}

impl Default for Guess {
    fn default() -> Guess {
        Guess {
            value: Real::zero(),
            dist: Real::infinity(),
        }
    }
}

/// A subproblem model for guessing candidate and center values.
pub trait GuessModel {
    /// Set the center of this model.
    fn set_center(&mut self, y: &Point);

    /// Set the candidate of this model.
    fn set_candidate(&mut self, y: &Point);

    /// Add a function value to this model.
    fn add_function_value(&mut self, y: &Point, value: Real);

    /// Add a minorant to this model.
    ///
    /// The minorant must be centered at the global 0.
    fn add_minorant(&mut self, y: &Point, m: &Arc<Minorant>);

    /// Return the current guess value at the current candidate.
    ///
    /// The function might return `None` if no guess value is available.
    fn candidate_value(&self) -> Option<Guess>;

    /// Return the current lower bound value at the center.
    ///
    /// In case no lower bound is available, the function should return
    /// -infinity.
    fn center_lb(&self) -> Real;
}

/*
 * Copyright (c) 2020 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/>
 */

//! Asynchronous subproblem with zero-order approximation.

use num_traits::{Float, Zero};
use std::collections::VecDeque;
use std::sync::Arc;

use crate::data::Minorant;
use crate::Real;

use super::{Guess, GuessModel, Point};

/// The maximal number of last evaluation points to be kept in the model.
#[allow(non_upper_case_globals)]
const MaxEvalPoints: usize = 5;
/// The maximal number of last minorants to be kept in the model.
#[allow(non_upper_case_globals)]
const MaxMinorants: usize = 5;

/// Information associated with one subproblem.
pub struct NearestValue {
    /// The current center point and the known lower bound.
    center: Option<(Point, Real)>,

    /// The current candidate point.
    candidate: Option<Point>,

    /// The last evaluation points (y, function_value).
    eval_points: VecDeque<(Point, Real)>,

    /// The last minorants.
    minorants: VecDeque<Arc<Minorant>>,

    /// The candidate guess value and distance.
    candidate_value: Option<Guess>,
}

impl NearestValue {
    pub fn new() -> NearestValue {
        NearestValue {
            center: None,
            candidate: None,
            eval_points: VecDeque::new(),
            minorants: VecDeque::new(),
            candidate_value: None,
        }
    }
}

impl Default for NearestValue {
    fn default() -> NearestValue {
        NearestValue::new()
    }
}

impl GuessModel for NearestValue {
    fn set_center(&mut self, y: &Point) {
        // compute the best lower bound for the new center.
        let lb = self
            .minorants
            .iter()
            .map(|m| m.eval(&y.point))
            .max_by(|a, b| a.partial_cmp(b).unwrap())
            .unwrap_or_else(|| -Real::infinity());
        self.center = Some((y.clone(), lb));
    }

    fn set_candidate(&mut self, y: &Point) {
        // find the closest known evaluation point.
        if let Some(evalpoint) = self
            .eval_points
            .iter()
            .map(|(x, value)| Guess::new(*value, x.distance(y)))
            .min_by(|a, b| a.dist.partial_cmp(&b.dist).unwrap())
        {
            self.candidate_value = Some(evalpoint);
        } else {
            self.candidate_value = None;
        }
        self.candidate = Some(y.clone());
    }

    fn add_function_value(&mut self, y: &Point, value: Real) {
        if let Some(ref c) = self.candidate {
            let dist = y.distance(c);
            if self
                .candidate_value
                .map(|old| old.dist > dist || dist.is_zero())
                .unwrap_or(true)
            {
                self.candidate_value = Some(Guess::new(value, dist));
            }
        }

        // Add evaluation point to list.
        self.eval_points.push_back((y.clone(), value));
        while self.eval_points.len() > MaxEvalPoints {
            self.eval_points.pop_front();
        }
    }

    fn add_minorant(&mut self, _y: &Point, m: &Arc<Minorant>) {
        if let Some(ref mut center) = self.center {
            let cut_value = m.eval(&center.0.point);
            if cut_value > center.1 {
                center.1 = cut_value;
            }
        }

        // Add minorant to list.
        self.minorants.push_back(m.clone());
        while self.minorants.len() > MaxMinorants {
            self.minorants.pop_front();
        }
    }

    fn candidate_value(&self) -> Option<Guess> {
        self.candidate_value
    }

    fn center_lb(&self) -> Real {
        self.center.as_ref().map(|c| c.1).unwrap_or_else(|| -Real::infinity())
    }
}