/*
* Copyright (c) 2019-2023 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/>
*/
//! An asynchronous first-order oracle.
pub use crate::data::minorant::SubgradientExtender;
use crate::{DVector, Minorant, Real};
use std::sync::Arc;
use thiserror::Error;
#[derive(Debug, Error)]
#[non_exhaustive]
pub enum ResultSendError {
#[error("connection error")]
Connection,
}
/// Channel to send evaluation results to.
pub trait ResultSender<P>: Send
where
P: FirstOrderProblem,
{
/// Send a new objective `value`.
fn objective(&self, value: Real) -> Result<(), ResultSendError>;
/// Send a new `minorant` with associated `primal`.
fn minorant(&self, minorant: P::Minorant) -> Result<(), ResultSendError>;
/// Send an error message.
fn error(&self, err: P::Err) -> Result<(), ResultSendError>;
}
#[derive(Debug, Error)]
#[non_exhaustive]
pub enum UpdateSendError {
#[error("connection error")]
Connection,
}
/// Channel to send problem updates to.
pub trait UpdateSender<P>: Send
where
P: FirstOrderProblem,
{
/// Add new variables with given bounds.
///
/// The oracle must provide a "subgradient extension callback", that
/// computes subgradients for the given variables based on the associated
/// primals.
fn add_variables(
&self,
bounds: Vec<(Real, Real)>,
sgext: Box<dyn SubgradientExtender<P::Minorant, P::Err>>,
) -> Result<(), UpdateSendError>;
/// Send an error message.
fn error(&self, err: P::Err) -> Result<(), UpdateSendError>;
}
/// This trait provides information available in the
/// [`FirstOrderProblem::update`] method.
pub trait UpdateState<P>: Send + 'static {
/// Whether the last step was a descent step.
fn was_descent(&self) -> bool;
/// Whether the last step was a null step.
fn was_null(&self) -> bool {
!self.was_descent()
}
/// The (old) current center of stability.
fn center(&self) -> &DVector;
/// The candidate point.
///
/// After a descent step, i.e. if [`UpdateState::was_descent`] is `true`,
/// this is the new center of stability.
fn candidate(&self) -> &DVector;
/// The current aggregated primal information.
///
/// Return the aggregated primal information for the given subproblem.
fn aggregated_primal(&self, i: usize) -> &P;
}
/// Trait for implementing a first-order problem description.
///
/// Note that all computations made by an implementation are supposed to be
/// asynchronous.
pub trait FirstOrderProblem {
/// Error raised by this oracle.
type Err: Send + 'static;
/// The minorant information.
type Minorant: Minorant;
/// Return the number of variables.
fn num_variables(&self) -> usize;
/// TODO: maybe change to `lower_bound(i)`
/// Return the lower bounds on the variables.
///
/// If no lower bounds are specified, $-\infty$ is assumed.
///
/// The lower bounds must be less then or equal the upper bounds.
fn lower_bounds(&self) -> Option<Vec<Real>> {
None
}
/// Return the upper bounds on the variables.
///
/// If no lower bounds are specified, $+\infty$ is assumed.
///
/// The upper bounds must be greater than or equal the upper bounds.
fn upper_bounds(&self) -> Option<Vec<Real>> {
None
}
/// Return the group index of each variable.
///
/// Each variable may be part of exactly one convexity constraint
/// \\[ \sum_{i \in I_k} y_i = 1, \\] where $I_k$ is the index-set
/// of the constraint. This method determines the index $k$ of the
/// index-set the variable $y_i$ belongs to, i.e. `constraint_index(i)`
/// should return `k` and all variables with the same index $k$
/// form one constraint.
///
/// The default implementation returns `None` for all variables.
fn constraint_index(&self, _i: usize) -> Option<usize> {
None
}
/// Return the number of subproblems.
///
/// The default implementation returns `1`.
fn num_subproblems(&self) -> usize {
1
}
/// Start background processes.
///
/// This method is called right before the solver starts the solution process.
/// It can be used to setup any background tasks required for the evaluation
/// of the subfunctions.
///
/// Remember that background processes should be cleaned up when the problem
/// is deleted (e.g. by implementing the [`Drop`] trait).
///
/// The default implementation does nothing.
fn start(&mut self) {}
/// Stop background processes.
///
/// This method is called right after the solver stops the solution process.
/// It can be used to stop any background tasks required for the evaluation
/// of the subfunctions.
///
/// A correct implementation of should cleanup all processes from the [`Drop`]
/// thread.
///
/// The default implementation does nothing.
fn stop(&mut self) {}
/// Start the evaluation of the i-th subproblem at the given point.
///
/// The results of the evaluation must be passed to the provided
/// `ResultSender`. In order to work correctly, the results should contain
/// at least (an upper bound on) the objective value at $y$ as well as at
/// least one subgradient centered at $y$ eventually.
///
/// Note that the evaluation can be done asynchronously. The function
/// `evaluate` may return immediately while the computation happens in a
/// background task. The background task should pass its result to the
/// sender `tx` and finally drop `tx` when the computation is finished.
fn evaluate(&mut self, i: usize, y: Arc<DVector>, tx: impl ResultSender<Self> + 'static) -> Result<(), Self::Err>
where
Self: Sized;
/// Called to update the problem.
///
/// This method is called regularly by the solver. The problem should send problem update
/// information (e.g. adding new variables) to the provided channel.
///
/// The updates might be generated asynchronously.
///
/// The default implementation does nothing.
fn update(
&mut self,
_state: impl UpdateState<<Self::Minorant as Minorant>::Primal>,
_tx: impl UpdateSender<Self> + 'static,
) -> Result<(), Self::Err>
where
Self: Sized,
{
Ok(())
}
}