IDEAS home Printed from https://ideas.repec.org/p/pur/prukra/1315.html
   My bibliography  Save this paper

Convexification of Permutation-Invariant Sets

Author

Listed:
  • Jinhak Kim
  • Mohit Tawarmalani
  • Jean-Philippe P. Richard

Abstract

In this paper, we characterize the convex hull of a set, which does not change when variables are permuted, as a projection of a set in a higher-dimensional space. In particular, we show that as long as the set can be convexified after imposing an ordering on the constituent variables, the convex hull of the set can be written using a polynomial number of additional variables and constraints.

Suggested Citation

  • Jinhak Kim & Mohit Tawarmalani & Jean-Philippe P. Richard, 2019. "Convexification of Permutation-Invariant Sets," Purdue University Economics Working Papers 1315, Purdue University, Department of Economics.
    • Handle: RePEc:pur:prukra:1315
    as

    Download full text from publisher

    File URL: https://business.purdue.edu/research/working-papers-series/2019/1315.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Anonymous, 2011. "Notes from the Editors," American Political Science Review, Cambridge University Press, vol. 105(1), pages 1-1, February.
    2. Egon Balas, 2004. "Logical Constraints as Cardinality Rules: Tight Representation," Journal of Combinatorial Optimization, Springer, vol. 8(2), pages 115-128, June.
    3. Anonymous, 2011. "Notes from the Editors," American Political Science Review, Cambridge University Press, vol. 105(4), pages 1-1, November.
    4. Brendan O’Donoghue & Eric Chu & Neal Parikh & Stephen Boyd, 2016. "Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding," Journal of Optimization Theory and Applications, Springer, vol. 169(3), pages 1042-1068, June.
    5. J. N. R. Jeffers, 1967. "Two Case Studies in the Application of Principal Component Analysis," Journal of the Royal Statistical Society Series C, Royal Statistical Society, vol. 16(3), pages 225-236, November.
    6. Anonymous, 2011. "Notes from the Editors," American Political Science Review, Cambridge University Press, vol. 105(3), pages 1-1, August.
    7. Anonymous, 2011. "Notes from the Editors," American Political Science Review, Cambridge University Press, vol. 105(2), pages 1-1, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tai-Yin Chiu & Hui-Ju K Chiang & Ruei-Yang Huang & Jie-Hong R Jiang & François Fages, 2015. "Synthesizing Configurable Biochemical Implementation of Linear Systems from Their Transfer Function Specifications," PLOS ONE, Public Library of Science, vol. 10(9), pages 1-27, September.
    2. Bassma Ghali & Nayanashri Thalanki Anantha & Jennifer Chan & Tom Chau, 2013. "Variability of Grip Kinetics during Adult Signature Writing," PLOS ONE, Public Library of Science, vol. 8(5), pages 1-10, May.
    3. Christian Bayer & Chiheb Ben Hammouda & Ra'ul Tempone, 2021. "Numerical Smoothing with Hierarchical Adaptive Sparse Grids and Quasi-Monte Carlo Methods for Efficient Option Pricing," Papers 2111.01874, arXiv.org, revised Jun 2022.
    4. Naomi Prachi Hazarika, 2020. "Spaces of Intermediation and Political Participation: a Study of KuSumpur pahadI redevelopment project," CSH-IFP Working Papers 0016, Centre de Sciences Humaines, New Delhi, revised Jul 2020.
    5. Denis Bouyssou & Marc Pirlot, 2015. "A consolidated approach to the axiomatization of outranking relations: a survey and new results," Annals of Operations Research, Springer, vol. 229(1), pages 159-212, June.
    6. Andrew Butler & Roy H. Kwon, 2023. "Efficient differentiable quadratic programming layers: an ADMM approach," Computational Optimization and Applications, Springer, vol. 84(2), pages 449-476, March.
    7. Zaijun Li & Jianquan Cheng & Qiyan Wu, 2016. "Analyzing regional economic development patterns in a fast developing province of China through geographically weighted principal component analysis," Letters in Spatial and Resource Sciences, Springer, vol. 9(3), pages 233-245, October.
    8. Enzo Busseti, 2019. "Derivative of a Conic Problem with a Unique Solution," Papers 1903.05753, arXiv.org, revised Mar 2019.
    9. Bernardo Freitas Paulo da Costa & Silvana M. Pesenti & Rodrigo S. Targino, 2023. "Risk Budgeting Portfolios from Simulations," Papers 2302.01196, arXiv.org.
    10. Leo Liberti, 2020. "Distance geometry and data science," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 271-339, July.
    11. Johannes Friedrich & Pengcheng Zhou & Liam Paninski, 2017. "Fast online deconvolution of calcium imaging data," PLOS Computational Biology, Public Library of Science, vol. 13(3), pages 1-26, March.
    12. Andrew Butler & Roy Kwon, 2021. "Efficient differentiable quadratic programming layers: an ADMM approach," Papers 2112.07464, arXiv.org.
    13. Choulakian, V., 2001. "Robust Q-mode principal component analysis in L1," Computational Statistics & Data Analysis, Elsevier, vol. 37(2), pages 135-150, August.
    14. Sun, Qinghe & Chen, Li & Meng, Qiang, 2022. "Evaluating port efficiency dynamics: A risk-based approach," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 333-347.
    15. Elsy Garnica Olmos, 1996. "Principal component analysis of household budget," Economía, Instituto de Investigaciones Económicas y Sociales (IIES). Facultad de Ciencias Económicas y Sociales. Universidad de Los Andes. Mérida, Venezuela, vol. 21(11), pages 55-90, January-D.
    16. Chen, Ying & Koch, Thorsten & Zakiyeva, Nazgul & Zhu, Bangzhu, 2020. "Modeling and forecasting the dynamics of the natural gas transmission network in Germany with the demand and supply balance constraint," Applied Energy, Elsevier, vol. 278(C).
    17. Amir Beck & Yakov Vaisbourd, 2016. "The Sparse Principal Component Analysis Problem: Optimality Conditions and Algorithms," Journal of Optimization Theory and Applications, Springer, vol. 170(1), pages 119-143, July.
    18. Run Chen & Andrew L. Liu, 2021. "A distributed algorithm for high-dimension convex quadratically constrained quadratic programs," Computational Optimization and Applications, Springer, vol. 80(3), pages 781-830, December.
    19. Nikitas Rontsis & Paul Goulart & Yuji Nakatsukasa, 2022. "Efficient Semidefinite Programming with Approximate ADMM," Journal of Optimization Theory and Applications, Springer, vol. 192(1), pages 292-320, January.
    20. Davood Hajinezhad & Qingjiang Shi, 2018. "Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications," Journal of Global Optimization, Springer, vol. 70(1), pages 261-288, January.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pur:prukra:1315. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Business PHD (email available below). General contact details of provider: https://edirc.repec.org/data/kspurus.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.