More Like this

1. On the convex hull of convex quadratic optimization problems with indicators

   https://doi.org/10.1007/s10107-023-01982-0  

   Wei, Linchuan ; Atamtürk, Alper ; Gómez, Andrés ; Küçükyavuz, Simge ( June 2023 , Mathematical Programming)

   We consider the convex quadratic optimization problem in$$\mathbb {R}^{n}$$$R^n$with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an$$(n+1) \times (n+1)$$$(n+1)\times (n+1)$positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.

    

   more » « less
2. Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization

   https://doi.org/10.1007/s10107-022-01875-8  

   Zhang, Shixuan ; Sun, Xu Andy ( August 2022 , Mathematical Programming)

   In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization withnon-Lipschitzianvalue functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a$$(T+1)$$$(T+1)$-stage stochastic MINLP satisfyingL-exact Lipschitz regularization withd-dimensional state spaces, to obtain an$$\varepsilon $$$\epsilon$-optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$$O\left({\left(\frac{2LT}{\epsilon }\right)}^d\right)$, and is lower bounded by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$$O\left({\left(\frac{\mathrm{LT}}{4\epsilon }\right)}^d\right)$for the general case or by$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$$O\left({\left(\frac{\mathrm{LT}}{8\epsilon }\right)}^{d/2-1}\right)$for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity dependspolynomiallyon the number of stages. We further show that the iteration complexity dependslinearlyonT, if all the state spaces are finite sets, or if we seek a$$(T\varepsilon )$$$\left(T\epsilon \right)$-optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale withT. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization.

    

   more » « less
3. Generalized Parking Function Polytopes

   https://doi.org/10.1007/s00026-023-00671-1  

   Hanada, Mitsuki ; Lentfer, John ; Vindas-Meléndez, Andrés R. ( November 2023 , Annals of Combinatorics)

   A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$$(a_1,a_2,\dots ,a_n)$whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$$b_1\le b_2\le \cdots \le b_n$satisfies$$b_i \le i$$$b_i\le i$. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$$R^n$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$$x$-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$$x=(a,b,\cdots ,b)$, which we refer to as$${\textbf{x}}$$$x$-parking function polytopes. We explore connections between these$${\textbf{x}}$$$x$-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$$x$-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    

   more » « less
4. Fertilitopes

   https://doi.org/10.1007/s00454-023-00488-y  

   Defant, Colin ( June 2023 , Discrete & Computational Geometry)

   We introduce tools from discrete convexity theory and polyhedral geometry into the theory of West’s stack-sorting map s. Associated to each permutation$$\pi $$$\pi$is a particular set$$\mathcal V(\pi )$$$V\left(\pi \right)$of integer compositions that appears in a formula for the fertility of $$\pi $$$\pi$, which is defined to be$$|s^{-1}(\pi )|$$$|s^{-1}\left(\pi \right)|$. These compositions also feature prominently in more general formulas involving families of colored binary plane trees calledtroupesand in a formula that converts from free to classical cumulants in noncommutative probability theory. We show that$$\mathcal V(\pi )$$$V\left(\pi \right)$is a transversal discrete polymatroid when it is nonempty. We define thefertilitopeof$$\pi $$$\pi$to be the convex hull of$$\mathcal V(\pi )$$$V\left(\pi \right)$, and we prove a surprisingly simple characterization of fertilitopes as nestohedra arising from full binary plane trees. Using known facts about nestohedra, we provide a procedure for describing the structure of the fertilitope of$$\pi $$$\pi$directly from$$\pi $$$\pi$using Bousquet-Mélou’s notion of the canonical tree of $$\pi $$$\pi$. As a byproduct, we obtain a new combinatorial cumulant conversion formula in terms of generalizations of canonical trees that we callquasicanonical trees. We also apply our results on fertilitopes to study combinatorial properties of the stack-sorting map. In particular, we show that the set of fertility numbers has density 1, and we determine all infertility numbers of size at most 126. Finally, we reformulate the conjecture that$$\sum _{\sigma \in s^{-1}(\pi )}x^{\textrm{des}(\sigma )+1}$$${\sum }_{\sigma \in s^{-1}\left(\pi \right)}{x}^{\text{des}\left(\sigma \right)+1}$is always real-rooted in terms of nestohedra, and we propose natural ways in which this new version of the conjecture could be extended.

    

   more » « less
5. A novel stochastic optimization method for handling misalignments of proton and photon doses in combined treatments

   https://doi.org/10.1088/1361-6560/ac858f  

   Fabiano, Silvia ; Torelli, Nathan ; Papp, Dávid ; Unkelbach, Jan ( September 2022 , Physics in Medicine & Biology)

   Objective.Combined proton–photon treatments, where most fractions are delivered with photons and only a few are delivered with protons, may represent a practical approach to optimally use limited proton resources. It has been shown that, when organs at risk (OARs) are located within or near the tumor, the optimal multi-modality treatment uses protons to hypofractionate parts of the target volume and photons to achieve near-uniform fractionation in dose-limiting healthy tissues, thus exploiting the fractionation effect. These plans may be sensitive to range and setup errors, especially misalignments between proton and photon doses. Thus, we developed a novel stochastic optimization method to directly incorporate these uncertainties into the biologically effective dose (BED)-based simultaneous optimization of proton and photon plans.Approach.The method considers the expected value$E\left(b\right)$and standard deviation$\sigma \left(b\right)$of the cumulative BED$b$in every voxel of a structure. For the target, a piecewise quadratic penalty function of the form${\left[b^{\min }-\left(E\left(b\right)-2\sigma \left(b\right)\right)\right]}_{+}^2$is minimized, aiming for plans in which the expected BED minus two times the standard deviation exceeds the prescribed BED$b^{\min }.$Analogously,${\left[\left(E\left(b\right)+2\sigma \left(b\right)\right)-b^{\max }\right]}_{+}^2$is considered for OARs.Main results.Using a spinal metastasis case and a liver cancer patient, it is demonstrated that the novel stochastic optimization method yields robust combined treatment plans. Tumor coverage and a good sparing of the main OARs are maintained despite range and setup errors, and especially misalignments between proton and photon doses. This is achieved without explicitly considering all combinations of proton and photon error scenarios.Significance.Concerns about range and setup errors for safe clinical implementation of optimized proton–photon radiotherapy can be addressed through an appropriate stochastic planning method.

    

   more » « less