Properties, Extensions and Application of Piecewise Linearization for Euclidean Norm Optimization in $$\mathbb {R}^2$$ R 2

Aloïs Duguet (), Christian Artigues (), Laurent Houssin () and Sandra Ulrich Ngueveu ()
Additional contact information
Aloïs Duguet: Université de Toulouse, CNRS, INP
Christian Artigues: Université de Toulouse, CNRS, INP
Laurent Houssin: Université de Toulouse
Sandra Ulrich Ngueveu: Université de Toulouse, CNRS, INP

Journal of Optimization Theory and Applications, 2022, vol. 195, issue 2, No 3, 418-448

Abstract: Abstract This work considers nonconvex mixed integer nonlinear programming where nonlinearity comes from the presence of the two-dimensional euclidean norm in the objective or the constraints. We build from the euclidean norm piecewise linearization proposed by Camino et al. (Comput. Optim. Appl. https://doi.org/10.1007/s10589-019-00083-z , 2019) that allows to solve such nonconvex problems via mixed-integer linear programming with an arbitrary approximation guarantee. Theoretical results are established that prove that this linearization is able to satisfy any given approximation level with the minimum number of pieces. An extension of the piecewise linearization approach is proposed. It shares the same theoretical properties for elliptic constraints and/or objective. An application shows the practical appeal of the elliptic linearization on a nonconvex beam layout mixed optimization problem coming from an industrial application.

Keywords: Mixed integer linear programming; Mixed integer nonlinear programming; Euclidean norm linearization; Approximation guarantee; Multibeam satellites; 41A60; 65D99; 68U99 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02083-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:195:y:2022:i:2:d:10.1007_s10957-022-02083-2

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02083-2

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().