Patent ID: 7730000

Claim:
A system for iteratively improving a chosen solution to an online convex optimization problem, the system executing procedures for: collecting known information with a computer known by a decision maker at time T, the collection of known information comprising a set of past decisions x 1 , . . . , x t−1 made by a decision maker prior to time T, a set of state variables k 1 , . . . , k t , and a sequence of T−1 convex functions of the form ƒ t , each convex function mapping a convex set P into a set R of real numbers ( : → R ) ⁢ ⁢ ⁢ for ⁢ ⁢ t = 1 , 2 , … ⁢ , T - 1 ; selecting a state vector {tilde over (k)}, from a plurality of known state vectors for which a distance between the selected state vector and each state vector from the plurality of state vectors is less than a threshold value ε, wherein the selecting of the state vector {tilde over (k)} t is based on weights that are updated in a multiplicative fashion, wherein a weight function w t ⁡ ( y ) = w t - 1 ⁡ ( y ) · exp ⁢ { - α ⁢ ⁢ g t - 1 ⁡ ( y ) } , ⁢ and y t = ∫ ⁢ y · w t ⁡ ( y ) ⁢ ⅆ y ∫ ⁢ w t ⁡ ( y ) ⁢ ⅆ y ∈ , represented with respect to pay-off function g t−1 , and wherein a worst-case regret is ( 4 ⁢ n 2 / ρ ) · log ⁢ ⁢ T ; developing a new state vector based upon the selected state vector; and determining a cost associated with the new state vector; determining a level of regret that the decision maker has regarding the decision maker's past decisions x 1 , . . . , x t−1 based on a difference between a total cost the decision maker incurred and a minimum cost the decision maker could have incurred by a repeated choice; and transforming the cost associated with the new state vector for display on an output device.