Nir Halman, HUJI 28 / 1 Optimization (NLP) min G(x) subject to hi(x) 0, i =1,,m uj(x) = 0, j =1,,l n (G:R R) 28 / 2 Karush-Kuhn-Tucker Theorem (1951,1939)

Necessary conditions Stationary (Lagrange conditions) + Primal feasibility Dual feasibility Complementary slackness In general, many optimization algorithms can be interpreted as methods for numerically solving the KKT system of equations 28 / 3 Special cases Linear Programming (LP): G,h,u are all linear functions

Integer Linear Programming (ILP): As above, and vector x must be integer-valued Dynamic Optimization (DO): Special structure for G & constraints, e.g., in stochastic discrete-time finite-time single-item inventory control:+() subject to = 0 current inventory level + : transition function : state (stock at beginning of time t) action (production) to be made after observing (unknown) random event (the demand in time t) single-period cost function (production, holding & shortage) terminal cost function When are constants, this may be viewed as a T-dimensional NLP

28 / 4 Dynamic Optimization DO can be solved, e.g., via Pontryagins minimum principal in optimal control (1956) Bellman equation in dynamic programming (DP) (1953) Lev Pontryagin (1908-1988) Richard Bellman (1920-1984) The minimum principle is generally better when time is continuous and there is no uncertainty, DP in the opposite case of discrete time and uncertainty. Dixit, Optimization in Economic Theory 1990

28 / 5 Stochastic DPs Objective: z*(I1) = +() subject to : transition function : state (stock at beginning of time t) action (production) to be made after observing (unknown) random event (the demand in time t) single-period cost function (production, holding & shortage) terminal cost function Theorem [B57]: optimal cost is z1(I1) in the recursion: zt(I) = minxAt(I) EDt[gt (I, x, Dt)+ zt+1(ft (I, x, Dt))], where zt(I) = total opt. cost in periods t,,T+1

The scope of this work is: Design of apx. schemes for monotone/convex stochastic DPs with finite discrete univariate state/action spaces 28 / 6 Our DP Model zt(It) = minxtAt(It) EDt {gt (It, xt, Dt)+ zt+1(ft (It, xt, Dt))} Def 1: Let XQ and Y(x) Q xX. Then XY:=({x}Y(x)) Condition 1: St, At, Dt Z, t. Condition 2: gt :Q+, t. Condition 3: At least one of the following holds: Non-decreasing DP: gT+1 is non-decreasing. tT: gt(I,x,d),

ft(I,x,d) are non-decreasing in I and monotone in x Non-increasing DP: (similarly) Convex DP: gT+1 is convex. t T, and fixed d: St At is integrally convex, i.e., its convex closure is a quadruple with slopes{1,0}, ft(I,x,d)=atI+btx+ct(d), where bt{1,0} and gt(I,x,d)=gt(I,d)+g*t(x,d)+ut(ft(I,x,d)) is the 28 / 7 sum of 3 univariate convex functions Convex DPs zt(I) = minxAt(I) EDt[gt (I, x, Dt)+ zt+1(ft (I, x, Dt))], Convex DP: St At is integrally convex and ft(I,x,d)=atI+btx+ct (d) where bt{1,0} Proposition 1: Conditions on convex DP cannot be

relaxed Example: Let T=1, z2 (I)=I2, g10 and f(I,x) = I 2x (Note: Both functions are convex over their domain.) z1(I) = minxR z2 (f (I,x)) is convex over R z1(I) = minxZ z2 (f (I,x)) is NOT convex over R 28 / 8 Our Results Theorem 1 (computational): Any DP satisfying Conditions 1-3 admits an FPTAS Theorem 2 (structural): Convex DPs admit optimal limit OPT a minimization problem

the FPTAS calculates (rt*, st*) t, st) and policies OPT(x) (rvalue of problem on instance x A K-approximation A(x) (K>1) returns A(x) K OPT(x) A PTAS (Polynomial Time Approximation Scheme) is a (1+ )-apx. that runs in poly(|x|) time, e.g., O(|x|3/ ) An FPTAS (Fully Polynomial Time Approximation Scheme) is a PTAS that runs in poly(|x|,1/) time, e.g., O((|x|/ )2) FPTASs are considered as the Holy Grail among apx. algs. because

one can get close to opt(x) as much as one wants in poly. time 28 / 9 Talk Outline Stochastic Dynamic Programming Our framework Applications K-approximation sets and functions Algorithm 28 / 10 Applications

1. Lifetime consumption strategy with risk exposure [Phe62] 2. Cash management of mutual funds [HW01] 3. Stochastic ordered knapsack [DGV04] All problems: 1. Admit pseudo polynomial DP formulations 2. Do not admit worst-case approximations 3. Known frameworks for deriving approximations such as Woegingers Framework [Wo00] do not apply since do not handle stochastic DP, nor exponential action spaces Complexity of probs. 1-2 is not known 28 / 11 Lifetime Consumption consume xt return rate Dt capital at

t t+1 Nondecreasing concave utility function ut(xt) Stochastic return rate Dt Maximize t EDt ut(xt) (expected total utility) zt(It) = maxxt It EDt{ut(xt) + zt+1(Dt(It-xt)+at)}= expected total utility from time t onwards, starting with capital It zT+1(IT+1) = 0; z1(I1) = ?

28 / 12 Cash Management buy xt withdrawals Dt interest t t+1 Transaction costs ct(xt) = V shape function Stochastic withdrawals Dt (Dt<0 deposits) Interest costs ht(xt) = V shape function Minimize t EDt t-1(ct(xt) + ht(It-xt-Dt)) (total costs)

zt(It) = minxt EDt{t-1(ct(xt)+ ht(It-xt-Dt))+ zt+1(It-xt-Dt)} total costs from time t onwards, starting with cash It zT+1(IT+1) = 0; z1(I1) = ? 28 / 13 Stochastic Ordered Knapsack place item t? volume Dt t If Dt It recieve pt t+1

Knapsack size B, T items, profit pt, volume Dt Maximize t EDt pt xt s.t. xt{0,1} and t Dt xt B Let gt (It, xt, Dt)= pt xt DtIt (1-period profits) zt(It) = maxxt=0,1 EDt {gt (It, xt, Dt) + zt+1(It-Dt xt)+} zT+1(IT+1) = 0; z1(B) = ? 28 / 14 Knapsack and our Framework zt(It) = maxxt=0,1 EDt {gt (It, xt, Dt) + zt+1(It-Dt xt)+} gt(It, xt, Dt)= pt xt DtIt

Condition 1: St, At, Dt Z, t. Condition 2: gt :Q+, t. (Non-decreasing DP): gt(It, xt, Dt), ft(It, xt, Dt)=(It-Dtxt)+ are non-decreasing in It and monotone in xt Lifetime consumption is a Non-decreasing DP. Cash management is a Convex DP 28 / 15 More Applications Already applied to derive first FPTAS to: variants of knapsack machine scheduling logistics and supply chain management project management

revenue management economics Can handle important cases of non-independent stochastic RVs (Markov-modulated RVs) Proposition 2: Cannot handle general nonindependent stochastic RVs unless P=NP 28 / 16 Talk Outline Stochastic Dynamic Programming

Our framework Applications K-approximation sets and functions Algorithm 28 / 17 K-approximations of Functions Definition: Let ,*:[0, U] R+. We say that *() is a K-approximation of () if (x) *(x) K(x), x [ [0, U]. We denote it as * K 28 / 18 1. Calculus of K-apx. Functions

Let , 0, i* Ki i , and K1 K2 Operation name Operation and apx. ratio summation +1*+2* K1 +1+2 minimization min{1*, 2*} K1 min{1, 2} composition

1*() K1 1() approximation 2* K1 K2 1 when 2= 1* zt(I) = min xAt(I) {gt (x) + zt+1(I+x)} Corollary: (mimization of summation of composition) gt*, z*t+1 be K1,K2-apx. functions of gt, zt+1 (K1 K2) then zt*(I)=minxAt(I){gt*(x)+z*t+1(I+x))} is a K1-apx of zt(I) Let 28 / 19

A Question Under what conditions a (oracle) function :[0,...,U]R+ admits an efficient succinct K-approximation? ( Let M= max. Input size = log U + log M) Definition: a K-approximation * is: succinct if stored in space logarithmic in U, M efficient if built in logarithmic time (# of oracle queries) 28 / 20 2. K-approximation Sets Definition: Let :[0,...,U]R+ be unimodal (i.e., x* so is nonincreasing until x* and nondecreasing afterwards). A K-apx. set of is W [0,...,U] with argmin ,0,UW and:

:Construction: * is the apx. of induced by W W K * K Question: How small a K-apx. set of can be? 28 / 21 Approximating a Unimodal Function: The Compress Operator Answer: Logarithmic in U, M. Moreover, it can be

constructed in logarithmic time (# of oracle queries). I.e., If is either monotone, convex, or unimodal with given argmin, then it admits a succinct/efficient K-apx. function g := Compress(, K). g is a piecewise step function g K Number of pieces is O(logK M) Running time is O(logK M log U) Query time is O(log logK M) 28 / 22 Calculus of K-apx. Functions cont zt(I) = min xAt(I) {gt (x) + zt+1(I+x)} Corollary: (mimization of summation of composition)

Let gt*, z*t+1 be L1,L2-apx. functions of (unimodal) gt, zt+1 (L1 L2) then zt*(I)=minxAt(I){gt*(x)+z*t+1(I+x))} is a L1-apx. of zt(I) Theorem: Let Wg,Wz be Ki-apx. sets of gt* L1 gt and z*t+1 L2 zt+1 Then zt*(I):=minxWgWz{g*t (x) + z*t+1(I+x)} max{K apx. of 1zLt(I 1,L t)2} apx. of zt(It) is a controlled 28 / 23 Talk Outline

Stochastic Dynamic Programming Our framework Applications K-approximation sets and functions Algorithm 28 / 24

FPTAS for Convex DP zt(I) = min xAt(I) {gt (x) + zt+1(I+x)} begin K:=. zT+1:= gT+1 each query = O(logA logK M) for t=T+1 to 1 do zt(I):= minxAt(I) {gt(x)+zt+1(I+x)} O(logU logK M) queries to

zt:=compress(zt ,K) endfor end Running time:O(T logU logK M logA logK M) = O( ) (using K<1+/T<2logK/ T) Apx. Ratio: By first line KT=1+ 28 / 25 Our Approach / Future Research Functional point of view (other classes of functions, continuous domains)

Approximating functions via apx. sets Propagation of errors via Calculus of approximation (specialize the calculi to other recursive structures to plug into the framework, e.g., graph networks or infinite time horizon) Modular framework for deriving FPTASs Accelerate (worst-case) running time and further implementation in practice 28/26 Generalization to multivariate DP? Monotone DP: FPTAS for 2-dim knapsack P=NP [GL79,KS81] Can be formulated as a non-decreasing 2-dim DP Convex DP:

28 / 27 Discrete convexity 28 / 28 Thank you ! 28 / 29