soco 1.0.1

Algorithms for Smoothed Online Convex Optimization
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

use crate::algorithms::capacity_provisioning::{Bounded, BoundsMemory};
use crate::algorithms::online::Step;
use crate::config::Config;
use crate::model::{ModelOutputFailure, ModelOutputSuccess};
use crate::numerics::PRECISION;
use crate::problem::{Online, Problem};
use crate::result::{Failure, Result};
use crate::schedule::Schedule;
use crate::utils::{assert, project};
use crate::value::Value;
use num::{NumCast, ToPrimitive};
use pyo3::prelude::*;
use serde_derive::{Deserialize, Serialize};

#[derive(Clone, Debug, Deserialize, Serialize)]
pub struct Memory<T> {
    /// Lower and upper bounds from times $t$ (in order).
    pub bounds: Vec<BoundsMemory<T>>,
}
impl<T> Default for Memory<T> {
    fn default() -> Self {
        Memory { bounds: vec![] }
    }
}
impl<T> IntoPy<PyObject> for Memory<T>
where
    T: IntoPy<PyObject>,
{
    fn into_py(self, py: Python) -> PyObject {
        self.bounds.into_py(py)
    }
}

/// Lazy Capacity Provisioning
pub fn lcp<'a, T, P, C, D>(
    o: Online<P>,
    t: i32,
    xs: &Schedule<T>,
    Memory { mut bounds }: Memory<T>,
    _: (),
) -> Result<Step<T, Memory<T>>>
where
    T: Value<'a>,
    P: Bounded<T> + Problem<T, C, D>,
    C: ModelOutputSuccess,
    D: ModelOutputFailure,
{
    assert(o.p.d() == 1, Failure::UnsupportedProblemDimension(o.p.d()))?;
    assert(
        t - 1 == bounds.len() as i32,
        Failure::OnlineOutOfDateMemory {
            previous_time_slots: t - 1,
            memory_entries: bounds.len() as i32,
        },
    )?;

    let (t_start, x_start) = find_initial_time(&bounds);

    let i = xs.now_with_default(Config::single(NumCast::from(0).unwrap()))[0];
    let lower = o.p.find_lower_bound(o.w, o.p.t_end(), t_start, x_start)?;
    let upper = o.p.find_upper_bound(o.w, o.p.t_end(), t_start, x_start)?;
    let j = project(i, lower, upper);

    bounds.push(BoundsMemory { lower, upper });
    let m = Memory { bounds };

    Ok(Step(Config::single(j), Some(m)))
}

/// Finds a valid reference time and initial condition to base the optimization
/// on (alternatively to time $0$).
fn find_initial_time<'a, T>(bounds: &Vec<BoundsMemory<T>>) -> (i32, T)
where
    T: Value<'a>,
{
    for t in (2..=bounds.len() as i32).rev() {
        let prev_bound = &bounds[t as usize - 2];
        let bound = &bounds[t as usize - 1];
        if is_valid_initial_time(prev_bound, bound) {
            // this should always be true, however, it may be false due to numerical inaccuracies
            if ToPrimitive::to_f64(&(prev_bound.lower - prev_bound.upper))
                .unwrap()
                .abs()
                < PRECISION * 10.
            // without multiplying by $10$, numerical optimization is too imprecise
            {
                return (t - 1, prev_bound.upper);
            }
        }
    }

    (0, NumCast::from(0).unwrap())
}

/// Returns `true` if the time $t$ with current bounds $m$ and previous bounds
/// (at $t - 1$) $prev_m$ may be used as reference time.
fn is_valid_initial_time<'a, T>(
    BoundsMemory {
        lower: prev_lower,
        upper: prev_upper,
    }: &BoundsMemory<T>,
    BoundsMemory { lower, upper }: &BoundsMemory<T>,
) -> bool
where
    T: Value<'a>,
{
    upper < prev_upper || lower > prev_lower
}