// Copyright (c) 2016, 2017, 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/>
//
//! Problem description of a first-order convex optimization problem.
use crate::solver::UpdateState;
use crate::{Aggregatable, Minorant, Real};
use std::result::Result;
use std::vec::IntoIter;
/**
* Trait for results of an evaluation.
*
* An evaluation returns the function value at the point of evaluation
* and one or more subgradients.
*
* The subgradients (linear minorants) can be obtained by iterating over the result. The
* subgradients are centered around the point of evaluation.
*/
pub trait Evaluation<P>: IntoIterator<Item = (Minorant, P)> {
/// Return the function value at the point of evaluation.
fn objective(&self) -> Real;
}
/**
* Simple standard evaluation result.
*
* This result consists of the function value and a list of one or
* more minorants and associated primal information.
*/
pub struct SimpleEvaluation<P> {
pub objective: Real,
pub minorants: Vec<(Minorant, P)>,
}
impl<P> IntoIterator for SimpleEvaluation<P> {
type Item = (Minorant, P);
type IntoIter = IntoIter<(Minorant, P)>;
fn into_iter(self) -> Self::IntoIter {
self.minorants.into_iter()
}
}
impl<P> Evaluation<P> for SimpleEvaluation<P> {
fn objective(&self) -> Real {
self.objective
}
}
/// Problem update information.
///
/// The solver calls the `update` method of the problem regularly.
/// This method can modify the problem by adding (or removing)
/// variables. The possible updates are encoded in this type.
#[derive(Debug, Clone, Copy)]
pub enum Update {
/// Add a variable with bounds.
///
/// The initial value of the variable will be the feasible value
/// closest to 0.
AddVariable { lower: Real, upper: Real },
/// Add a variable with bounds and initial value.
AddVariableValue { lower: Real, upper: Real, value: Real },
/// Change the current value of a variable. The bounds remain
/// unchanged.
MoveVariable { index: usize, value: Real },
}
/**
* Trait for implementing a first-order problem description.
*
*/
pub trait FirstOrderProblem {
/// Error raised by this oracle.
type Err;
/// The primal information associated with a minorant.
type Primal: Aggregatable;
/// Custom evaluation result value.
type EvalResult: Evaluation<Self::Primal>;
/// Return the number of variables.
fn num_variables(&self) -> usize;
/**
* Return the lower bounds on the variables.
*
* If no lower bounds a 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 a 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 number of subproblems.
fn num_subproblems(&self) -> usize {
1
}
/**
* Evaluate the i^th subproblem at the given point.
*
* The returned evaluation result must contain (an upper bound on)
* the objective value at $y$ as well as at least one subgradient
* centered at $y$.
*
* If the evaluation process reaches a lower bound on the function
* value at $y$ and this bound is larger than $nullstep_bound$,
* the evaluation may stop and return the lower bound and a
* minorant. In this case the function value is guaranteed to be
* large enough so that the new point is rejected as candidate.
*
* The returned objective value should be an upper bound on the
* true function value within $relprec \cdot (\\|f(y)\\| + 1.0)$,
* otherwise the returned objective should be the maximum of all
* linear minorants at $y$.
*
* Note that `nullstep_bound` and `relprec` are usually only
* useful if there is only a `single` subproblem.
*/
fn evaluate(
&mut self,
i: usize,
y: &[Real],
nullstep_bound: Real,
relprec: Real,
) -> Result<Self::EvalResult, Self::Err>;
/// Return updates of the problem.
///
/// The default implementation returns no updates.
fn update(&mut self, _state: &UpdateState<Self::Primal>) -> Result<Vec<Update>, Self::Err> {
Ok(vec![])
}
/// Return new components for a subgradient.
///
/// The components are typically generated by some primal
/// information. The corresponding primal is passed as a
/// parameter.
///
/// The default implementation fails because it should never be
/// called.
fn extend_subgradient(&mut self, _primal: &Self::Primal, _vars: &[usize]) -> Result<Vec<Real>, Self::Err> {
unimplemented!()
}
}