craam/fastopt.hpp
inline
pair<numvec,prec_t> worstcase_l1(numvec const& z, numvec const& q, prec_t t){
    assert(*min_element(q.cbegin(), q.cend()) >= - THRESHOLD);
    assert(*max_element(q.cbegin(), q.cend()) <= 1 + THRESHOLD);
    assert(z.size() > 0);
    assert(t >= 0.0 && t <= 2.0);
    assert(z.size() == q.size());

    size_t sz = z.size();

    vector<size_t> smallest = sort_indexes<prec_t>(z);
    numvec o(q);

    auto k = smallest[0];
    auto epsilon = min(t/2, 1-q[k]);

    o[k] += epsilon;

    auto i = sz - 1;
    while(epsilon > 0){
        k = smallest[i];
        auto diff = min( epsilon, o[k] );
        o[k] -= diff;
        epsilon -= diff;
        i -= 1;
    }

    auto r = inner_product(o.begin(),o.end(),z.begin(), (prec_t) 0.0);
    return make_pair(move(o),r);
}
/**
Computes the solution of:
min_p   p^T * z
s.t.    ||p - q|| <= t
        1^T p = 1
        p >= 0

Notes
-----
This implementation works in O(n log n) time because of the sort. Using
quickselect to choose the right quantile would work in O(n) time.

This function does not check whether the probability distribution sums to 1.
**/
Computes the solution of:
min_p   p^T * z
s.t.

Notes

This implementation works in O(n log n) time because of the sort. Using
quickselect to choose the right quantile would work in O(n) time.

This function does not check whether the probability distribution sums to 1.
Computes the solution of : min_p p^T * z s . t . Notes This implementation works in O ( n log n ) time because of the sort . Using quickselect to choose the right quantile would work in O ( n ) time . This function does not check whether the probability distribution sums to 1 .
inline
pair<numvec,prec_t> worstcase_l1(numvec const& z, numvec const& q, prec_t t){
    assert(*min_element(q.cbegin(), q.cend()) >= - THRESHOLD);
    assert(*max_element(q.cbegin(), q.cend()) <= 1 + THRESHOLD);
    assert(z.size() > 0);
    assert(t >= 0.0 && t <= 2.0);
    assert(z.size() == q.size());
    size_t sz = z.size();
    vector<size_t> smallest = sort_indexes<prec_t>(z);
    numvec o(q);
    auto k = smallest[0];
    auto epsilon = min(t/2, 1-q[k]);
    o[k] += epsilon;
    auto i = sz - 1;
    while(epsilon > 0){
        k = smallest[i];
        auto diff = min( epsilon, o[k] );
        o[k] -= diff;
        epsilon -= diff;
        i -= 1;
    }
    auto r = inner_product(o.begin(),o.end(),z.begin(), (prec_t) 0.0);
    return make_pair(move(o),r);
}
inline pair < numvec , prec_t > worstcase_l1 ( numvec const & z , numvec const & q , prec_t t ) { assert ( * min_element ( q . cbegin ( ) , q . cend ( ) ) >= - THRESHOLD ) ; assert ( * max_element ( q . cbegin ( ) , q . cend ( ) ) <= 1 + THRESHOLD ) ; assert ( z . size ( ) > 0 ) ; assert ( t >= 0.0 && t <= 2.0 ) ; assert ( z . size ( ) == q . size ( ) ) ; size_t sz = z . size ( ) ; vector < size_t > smallest = sort_indexes < prec_t > ( z ) ; numvec o ( q ) ; auto k = smallest [ 0 ] ; auto epsilon = min ( t / 2 , 1 - q [ k ] ) ; o [ k ] += epsilon ; auto i = sz - 1 ; while ( epsilon > 0 ) { k = smallest [ i ] ; auto diff = min ( epsilon , o [ k ] ) ; o [ k ] -= diff ; epsilon -= diff ; i -= 1 ; } auto r = inner_product ( o . begin ( ) , o . end ( ) , z . begin ( ) , ( prec_t ) 0.0 ) ; return make_pair ( move ( o ) , r ) ; }
Computes the solution of:
min_p   p^T * z
s.t.
Computes the solution of : min_p p^T * z s . t .