PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimality of Affine Policies in Multi-stage Robust Optimization

Dimitris Bertsimas, Dan A. Iancu, Pablo A. Parrilo

arXiv:0904.3986v1math.OC

TL;DR

The paper asks whether disturbance-affine policies can achieve optimal objective values in constrained one-dimensional multi-stage robust optimization. It uses a forward-induction proof based on feasible-set geometry and affine cost relaxations, showing that these policies are optimal and computationally tractable for piecewise affine state costs. The conclusions apply within the stated finite-horizon, worst-case, convex-cost setting.

  • Problem

    The paper addresses limited prior evidence about objective-value quality for disturbance-affine policies in constrained multi-stage robust optimization.

  • Method

    The paper combines forward induction, polyhedral geometry of feasible sets, and affine relaxations of convex state costs to construct robustly feasible disturbance-affine policies.

  • Results

    Affine disturbance policies are optimal for the stated problem, and piecewise affine state costs admit efficient computation of optimal affine policies.

  • Takeaways & Limitations

    Within its scope, the result provides theoretical support for using affine disturbance policies and connects them to a classical inventory management problem.

  • Takeaways & Limitations

    The results are developed for one-dimensional systems and bounded disturbance sets, with multidimensional systems and more complicated uncertainty sets left for future work.

Abstract

from arXiv · show

In this paper, we show the optimality of a certain class of disturbance-affine control policies in the context of one-dimensional, constrained, multi-stage robust optimization. Our results cover the finite horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a new proof methodology, which explores the relationship between the geometrical properties of the feasible set of solutions and the structure of the objective function. Apart from providing an elegant and conceptually simple proof technique, the approach also entails very fast algorithms for the case of piecewise affine state costs, which we explore in connection with a classical inventory management application.

1 Introduction.

The paper studies one-dimensional constrained multi-stage robust optimization with worst-case costs, contrasting classical state-based dynamic programming with affine policies parameterized by observed disturbances. Its main result is that these disturbance-affine policies are optimal under the stated convex-cost setting, with efficient computation for piecewise affine costs.

  • 1 Introduction.: Multi-stage robust optimization chooses constrained controls over a finite horizon while uncertainty maximizes a cost combining convex state penalties and linear control costs.The dynamics are linear and one-dimensional, disturbances are bounded, and control actions must remain within fixed bounds.
  • 1 Introduction.: Classical dynamic programming computes state-feedback policies and value functions backward from the planning horizon, yielding piecewise-affine policies.The state formulation is compact and its resulting policies are documented in prior inventory and control literature.
  • 1 Introduction.: The paper instead studies policies directly parameterized by previously observed disturbances, with robust feasibility required for every disturbance history.This parameterization has the form uk(wk) and must satisfy Lk ≤ uk(wk) ≤ Uk for all admissible histories.
  • 1 Introduction.: Disturbance-affine parameterizations can be compact and computationally attractive, but prior work offered little evidence about the quality of their objective values.Using them directly can enlarge the state to include past disturbances and possibly prior controls or states.
  • 1 Introduction.: For the stated problem, affine disturbance policies are optimal, and an affine relaxation of convex state costs preserves optimality for piecewise affine costs.The paper presents a forward-induction proof using polyhedral geometry and connects the resulting policies to inventory management.

2 Dynamic Programming Solution.

The dynamic-programming formulation solves the robust control problem backward in the scalar state, after normalizing the linear dynamics. Its solution has convex value functions and structured, piecewise-affine optimal control laws.

  • 2 Dynamic Programming Solution.: Dynamic programming computes optimal policies and value functions backward from k = T using the scalar state xk.The Bellman recursion is initialized at the end of the finite planning horizon.
  • 2 Dynamic Programming Solution.: Without loss of generality, the time-varying scalar dynamics can be normalized to xk+1 = xk + uk + wk.This uses time-varying, independently bounded disturbances and control constraints.
  • 2 Dynamic Programming Solution.: The optimal control law is continuous, non-increasing, and piecewise affine with three pieces.Its control bounds and the disturbance intervals determine the relevant cases in the closed-form recursion.
  • 2 Dynamic Programming Solution.: The optimal value function J∗k(xk) and the auxiliary function gk(yk) are convex.These convexity properties support the structural analysis used later in the paper.
  • 2 Dynamic Programming Solution.: The auxiliary function gk is decreasing below its minimizer interval and increasing above it, with subgradient bounds tied to the control cost ck.The minimizer set is defined through the convex function ck·y + gk(y).

3 Optimality of Affine Policies in wk.

The paper proves that affine policies in disturbance histories are optimal for the robust dynamic program. It constructs these policies and affine cost relaxations geometrically, with a compact linear-program reformulation for piecewise affine costs.

  • 3 Optimality of Affine Policies in wk.: Theorem 3.1 establishes the existence of affine control policies qk(wk) satisfying robust control bounds for every admissible disturbance history.The policies are feasible simultaneously across the finite horizon.
  • 3 Optimality of Affine Policies in wk.: The proof constructs an affine running cost that dominates the original convex state cost while preserving the overall min-max value.The two maximization problems therefore have the same worst-case value despite the relaxed cost.
  • 3 Optimality of Affine Policies in wk.: Affine policies qk(wk) are optimal for the robust problem, not merely feasible approximations.This is the theorem’s existential result for the stated one-dimensional problem.
  • 3 Optimality of Affine Policies in wk.: When each convex state cost is piecewise affine, the optimal affine policies can be computed through a compact linear-program reformulation.The reformulation exploits bi-affine robust inequalities and has constraint complexity stated as O(T^2 · maxk mk).
  • 3 Optimality of Affine Policies in wk.: State constraints can be incorporated, when feasible, by adding convex barrier terms to the stage costs.This makes the constrained problem equivalent to one without explicit state constraints.

4 Proof of Main Theorem.

The proof of Theorem 3.1 uses forward induction rather than the usual backward-induction structure of dynamic programming. It constructs affine policies and affine cost relaxations while preserving robust feasibility and the min-max value, then identifies counterexamples limiting generalization.

  • Proof strategy: The proof proceeds by forward induction, beginning with a first-step test and analyzing consequences of the induction hypothesis.This differs from most dynamic-programming proofs, which use backward induction over time periods.
  • Policy construction: The first inductive part uses the optimal control law and value function to construct a candidate affine policy q_k(w_k).The policy is then shown to be robustly feasible and to preserve the overall min-max value under the original convex state costs.
  • Cost relaxation: The second inductive part reanalyzes feasible sets after applying q_k(w_k) to construct an affine cost z_k(w_{k+1}).The affine cost dominates the original convex state cost, yet the overall min-max value remains unchanged when it is incurred.
  • Scope: The proof concludes with Theorem 3.1 and counterexamples that prevent immediate extension to more general cases.These counterexamples define the boundary of the result beyond the stated setting.

4.1 Induction Hypothesis.

The induction hypothesis reduces worst-case analysis from the disturbance hyper-rectangle to geometrically structured two-dimensional sets. Convexity then restricts candidate maximizers to selected zonogon vertices, enabling affine policy and cost constructions.

  • Base case: The induction is verified at k = 1, where q_1 is a constant and is robustly feasible.The initial control satisfies the feasibility condition for the first stage.
  • Base case: For fixed x_1 and q_1, z_1(w_1) linearly interpolates h_1(x_1 + q_1 + w_1) and dominates it by convexity.The min-max value is achieved at the interpolation endpoints, satisfying the induction conditions.
  • Geometric reduction: Affine policies and costs make the effect of disturbances depend on affine combinations lying in a zonogon Θ, rather than all 2^k hyper-rectangle vertices.Θ is a two-dimensional affine projection of the disturbance hyper-rectangle and has at most 2^k vertices.
  • Geometric reduction: Lemma 4.1 shows that maximizing the relevant convex objective over Θ requires checking only the vertices v_0, …, v_k on its right side.The proof uses maximization of a convex function over a convex set, central symmetry, and the bound on the number of zonogon vertices.
  • Geometric reduction: The zonogon hull preserves the right-side vertices relevant to maximizing θ_1 + f(θ_2), even when the original polygon is non-convex.The resulting chain of equalities permits switching among the polygon, its convex hull, its right side, and the zonogon hull without changing the maximum.
  • Further analysis: Lemma 4.2 restricts maximization over ˜Γ to the right side of points transformed by the optimal control law.Each transformed point has coordinates (θ_1[v_i] + c · u*(v_i), θ_2[v_i] + u*(v_i)).

4.2 Construction of the Affine Control Law.

The construction computes an affine controller by matching and aligning transformed points so its zonogon reproduces the relevant feasible geometry, preserving robust feasibility and the min-max objective.

  • Objective preservation: The maximization compares the same convex objective over Γ and ˜Γ, so reproducing the relevant right-side geometry preserves the optimal objective value.Problem (OPT) uses ˜Γ, while problem (AFF) uses Γ; their maxima coincide under the zonogon-hull construction.
  • Geometric construction: The construction seeks an affine control law q(w) whose feasible zonogon Γ matches the zonogon hull of transformed points {˜v0, …, ˜vk}.This geometric match lets the two maximization problems share the same optimal value.
  • Algorithm 1: Algorithm 1 handles three trivial geometric cases directly and otherwise maps points, forms ∆Γ, and identifies its right-side points.The nontrivial case uses the mapping (27), convex hull construction, and r-side(∆Γ).
  • Matching and alignment: Matching constraints reproduce the optimal control values at selected transformed points, while alignment constraints make the corresponding zonogon generators share prescribed cotangents.The matching and alignment stages ensure the right-side vertices of Γ correspond to those of ∆Γ.
  • Robust feasibility: Algorithm 1 does not explicitly impose robust feasibility, but the matching-and-alignment construction makes q(w) robustly feasible.The paper states that the resulting controller satisfies the required conditions and preserves JmM with the original convex state costs.

4.3 Construction of the Affine State Cost.

The section constructs an affine state cost that dominates the original convex cost while preserving the overall min-max value. This geometric construction supports the proof of the main theorem and efficient computation for piecewise affine costs.

  • Affine cost construction: The construction replaces the convex state cost h(π2(w)) with an affine cost z(w) while preserving the overall min-max value.The two maximization problems have equal optimal values, even though one uses the original convex cost and the other uses z(w).
  • Affine cost construction: The affine coefficients are chosen so that the transformed zonogon represents the zonogon hull of the transformed vertices.This geometric alignment lets Corollary 4.1 equate the optimal values of the original and affine-cost problems.
  • Feasibility and value preservation: System (48) is always feasible, and its solution z(w) satisfies the value-preservation equation.Feasibility and equality of the two maximization values are established together in Lemma 4.7.
  • Dominance and theorem completion: Algorithm 2 produces an affine cost that always dominates the convex cost h(π2(w)) over the uncertainty set.The proof reduces the comparison to extreme points of the hypercube, where the relevant convex maximum is attained.
  • Dominance and theorem completion: Together, cost dominance and unchanged min-max value complete the affine-cost construction and the induction step proving Theorem 3.1.The preceding control construction is robustly feasible and preserves the min-max value under the original convex state costs.
  • Counterexamples: The claimed optimality does not generally extend to cumulative control constraints or multiple dimensions.A counterexample yields 873.248 versus the true optimum 838.493, while using both affine controls and affine costs yields 876.057.

5 An application in inventory management.

The paper applies its affine-policy result to a robust single-product inventory problem with uncertain periodic demand. Affine orders and affine cost relaxations preserve optimality and reduce the resulting computation to a linear program.

  • Inventory model: The application considers a single-product, single-echelon, multi-period supply chain with uncertain customer demands and periodic replenishment orders.Inventory is observed at the beginning of each period, and orders incur control costs over a finite planning horizon.
  • Inventory model: Demand uncertainty is modeled by intervals around nominal demands, with uncertainty level ρ ∈[0, 1], and worst-case Newsvendor costs.The resulting model is an instance of the paper’s robust optimization problem with convex state costs.
  • Affine inventory policies: Theorem 3.1 implies no loss of optimality when orders are affine in the history of observed demands and Newsvendor costs are replaced by affine costs.The affine costs may be larger than the original costs, but the optimal value is preserved.
  • Affine inventory policies: With affine orders and affine state-cost substitutions, finding the optimal policies becomes a linear-programming problem.This is the principal computational advantage of applying the theorem to the inventory setting.
  • Interpretation of affine orders: Once demand wt is fully satisfied, later affine orders no longer depend on wt.The result follows because the corresponding inventory coefficient reaches zero and subsequent coefficients remain zero.
  • Interpretation of affine orders: Each future order coefficient qk,t lies in [0, 1], representing the fraction of demand wt satisfied by order qk.Every demand is at most satisfied by the sequence of orders placed after it appears.

6 Conclusions. Future Directions.

The paper presents a geometric approach for robust, multi-stage decision problems and connects its theoretical results to inventory management. Future work targets broader constraints, dimensions, uncertainty sets, cost structures, and applications.

  • The approach uses relationships between feasible-set geometry, represented by zonogons, and objective functions to prune relevant points and characterize optimal policies.The authors present this as a novel theoretical method for robust, multi-stage decision problems.
  • The theoretical results have an implication for a classical inventory-management problem.
  • Future directions: Future work would study mixed polyhedral state and control constraints, multi-dimensional problems, and more complicated uncertainty sets.
  • Future directions: The authors also seek extensions to non-convex costs, nonlinear control costs, robust portfolio optimization, and operations management.
  • Future directions: Another proposed direction is quantifying affine-policy performance when such policies are suboptimal, potentially producing fast approximation algorithms with theoretical foundations.

7 Appendix.

The appendix develops the dynamic-programming proof and records geometric properties of zonotopes used in the analysis. It shows that optimal controls are piecewise affine and monotone, while optimal value functions are convex.

  • Dynamic Programming Solution: The appendix formulates the solution through backward Dynamic Programming and Bellman recursions over the finite planning horizon.The recursion starts from terminal cost J*_{T+1}=0 and proceeds backward in time.
  • Dynamic Programming Solution: At each stage, the inner worst-case maximization preserves convexity, while the control minimization is performed over bounded control constraints.The appendix explicitly derives this structure at the terminal stage and extends it inductively.
  • Dynamic Programming Solution: The optimal control policy is continuous, monotonically decreasing, and piecewise affine with at most three pieces.This property is established at the terminal stage and propagated by induction across stages.
  • Dynamic Programming Solution: The optimal objective or value function is convex in the state variable.The appendix attributes this to partial minimization of a convex function.
  • Geometric preliminaries: Zonotopes are affine projections of cubes and can equivalently be represented as Minkowski sums of line segments.The appendix uses these descriptions to establish symmetry, vertex, and adjacency properties for zonogons.
  • Geometric preliminaries: Zonogons are centrally symmetric two-dimensional polygons arising as projections of hypercubes, with structured vertex and edge relationships.The appendix states that zonogons are centrally symmetric 2p-gons and summarizes their vertex properties.
Loading 0904.3986v1…