Theoretical and Natural Science
- The Open Access Proceedings Series for Conferences
Theoretical and Natural Science
Vol. 19, 08 December 2023
Open
Access | Article
Solving the smallest ball problem based on convex programming theories
* Author to whom correspondence should be addressed.
Abstract
The mathematical method known to be Quadratic Programming is a branch of Convex Programming or Convex Optimization, which is then a peculiar case of Mathematical Optimization given a series of restrictions including a convex function to minimize. The Smallest Ball Problem is a problem where we seek to find the smallest enclosing ball of given points on a plane. Convex Optimization provides a solution to the Smallest Ball Problem. There are several ways to characterize a convex programming problem and its solutions, the most important of which is called the KKT conditions. By relating the Smallest Ball Problem to solving a Convex Programming Problem and using the Python packages, the radius, as well as the central point of the Smallest Ball, will be found. In addition, the underlying algorithm for solving Convex Programming Problems is studied. It can be concluded that Convex Programming, or more specifically, Quadratic Programming, gives a feasible solution to the Smallest Ball Problem.
Keywords
Convex Optimization, Quadratic Programming, Convex Programming, Mathematical Optimization, Smallest Ball Problem.
References
1. Mordukhovich, B., Nguyen, M.N., Villalobos, C.: The smallest enclosing ball problem and the smallest intersecting ball problem: existence and uniqueness of solutions (2012)
2. Fischer, K., Gartner, B., Kutz, M.: Fast Smallest-Enclosing-Ball Computation in High Dimensions (2003)
3. Giorgi, G., Jiménez, B., Novo, V.: Approximate Karush–Kuhn–Tucker Condition in Multiobjective Optimization (2016)
4. Haeser, G., Schuverdt, M.L.: On Approximate KKT Condition and its Extension to Continuous Variational Inequalities (2011)
5. Ghosh, D., Singh, A., Shukla, K.K., Manchanda, K.: Extended Karush-Kuhn-Tucker condition for constrained interval optimization problems and its application in support vector machines (2019)
6. Fischer, K., Gartner, B.: The Smallest Enclosing Ball of Balls: Combinatorial Structure and Algorithms (2003)
7. Pan, S., Li, X.: An efficient algorithm for the smallest enclosing ball problem in high dimensions (2006)
8. Samuel Zürcher. Smallest Enclosing Ball for a Point Set with Strictly Convex Level Sets. Institute of Theoretical Computer Science, 2007.
9. Elizabeth Wong. Active-Set Methods for Quadratic Programming. University of California, San Diego, 2011.
10. Juan C. Meza. Steepest Descent. Lawrence Berkeley National Laboratory, 2017.
Data Availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open Access Instruction).
- Volume Title
- Proceedings of the 2nd International Conference on Computing Innovation and Applied Physics
- ISBN (Print)
- 978-1-83558-203-9
- ISBN (Online)
- 978-1-83558-204-6
- Published Date
- 08 December 2023
- Series
- Theoretical and Natural Science
- ISSN (Print)
- 2753-8818
- ISSN (Online)
- 2753-8826
- DOI
- 10.54254/2753-8818/19/20230500
- Copyright
- 08 December 2023
- Open Access
- This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited