More Like this

1. Circuit-based Inverse Design of Metastructured MIMO Devices

   https://doi.org/10.23919/EuCAP51087.2021.9411442  

   Szymanski, Luke; Gok, Gurkan; Grbic, Anthony (March 2021, 2021 15th European Conference on Antennas and Propagation (EuCAP))

   null (Ed.)

   In this work, an inverse design method for multi-input multi-output (MIMO) metastructured devices is developed. Large-scale inverse design problems are difficult to solve directly and often require heuristic methods or design optimization to find a solution. Inherent errors introduced by heuristic methods makes design optimization a more promising route to the realization of high performance devices. Here, a fast frequency domain solver for grids of Y-parameter matrices is developed. The solver is used together with an adjoint-based optimization routine to solve inverse metastructured design problems. The design procedure is demonstrated through the realization of a planar beamforming network for a multi-beam antenna. 

   more » « less
2. Memetic Algorithms for Spatial Partitioning Problems

   https://doi.org/10.1145/3544779  

   Biswas, Subhodip; Chen, Fanglan; Chen, Zhiqian; Lu, Chang-Tien; Ramakrishnan, Naren (March 2023, ACM Transactions on Spatial Algorithms and Systems)

   Spatial optimization problems (SOPs) are characterized by spatial relationships governing the decision variables, objectives, and/or constraint functions. In this article, we focus on a specific type of SOP called spatial partitioning, which is a combinatorial problem due to the presence of discrete spatial units. Exact optimization methods do not scale with the size of the problem, especially within practicable time limits. This motivated us to develop population-based metaheuristics for solving such SOPs. However, the search operators employed by these population-based methods are mostly designed for real-parameter continuous optimization problems. For adapting these methods to SOPs, we apply domain knowledge in designing spatially aware search operators for efficiently searching through the discrete search space while preserving the spatial constraints. To this end, we put forward a simple yet effective algorithm called s warm-based s p atial meme ti c al gorithm (SPATIAL) and test it on the school (re)districting problem. Detailed experimental investigations are performed on real-world datasets to evaluate the performance of SPATIAL. Besides, ablation studies are performed to understand the role of the individual components of SPATIAL. Additionally, we discuss how SPATIAL is helpful in the real-life planning process and its applicability to different scenarios and motivate future research directions. 

   more » « less
3. An adaptive half-space projection method for stochastic optimization problems with group sparse regularization

   Dai, Yutong; Chen, Tianyi; Wang, Guanyi; Robinson, Daniel P. (June 2023, Transactions on machine learning research)

   Optimization problems with group sparse regularization are ubiquitous in various popular downstream applications, such as feature selection and compression for Deep Neural Networks (DNNs). Nonetheless, the existing methods in the literature do not perform particularly well when such regularization is used in combination with a stochastic loss function. In particular, it is challenging to design a computationally efficient algorithm with a convergence guarantee and can compute group-sparse solutions. Recently, a half-space stochastic projected gradient ({\tt HSPG}) method was proposed that partly addressed these challenges. This paper presents a substantially enhanced version of {\tt HSPG} that we call~{\tt AdaHSPG+} that makes two noticeable advances. First, {\tt AdaHSPG+} is shown to have a stronger convergence result under significantly looser assumptions than those required by {\tt HSPG}. This improvement in convergence is achieved by integrating variance reduction techniques with a new adaptive strategy for iteratively predicting the support of a solution. Second, {\tt AdaHSPG+} requires significantly less parameter tuning compared to {\tt HSPG}, thus making it more practical and user-friendly. This advance is achieved by designing automatic and adaptive strategies for choosing the type of step employed at each iteration and for updating key hyperparameters. The numerical effectiveness of our proposed {\tt AdaHSPG+} algorithm is demonstrated on both convex and non-convex benchmark problems. The source code is available at \url{https://github.com/tianyic/adahspg}. 

   more » « less
4. Scaling Package Queries to a Billion Tuples via Hierarchical Partitioning and Customized Optimization

   https://doi.org/10.14778/3641204.3641222  

   Mai, Anh L; Wang, Pengyu; Abouzied, Azza; Brucato, Matteo; Haas, Peter J; Meliou, Alexandra (January 2024, Proceedings of the VLDB Endowment)

   A package query returns a package---a multiset of tuples---that maximizes or minimizes a linear objective function subject to linear constraints, thereby enabling in-database decision support. Prior work has established the equivalence of package queries to Integer Linear Programs (ILPs) and developed the SketchRefine algorithm for package query processing. While this algorithm was an important first step toward supporting prescriptive analytics scalably inside a relational database, it struggles when the data size grows beyond a few hundred million tuples or when the constraints become very tight. In this paper, we present Progressive Shading, a novel algorithm for processing package queries that can scale efficiently to billions of tuples and gracefully handle tight constraints. Progressive Shading solves a sequence of optimization problems over a hierarchy of relations, each resulting from an ever-finer partitioning of the original tuples into homogeneous groups until the original relation is obtained. This strategy avoids the premature discarding of high-quality tuples that can occur with SketchRefine. Our novel partitioning scheme, Dynamic Low Variance, can handle very large relations with multiple attributes and can dynamically adapt to both concentrated and spread-out sets of attribute values, provably outperforming traditional partitioning schemes such as kd-tree. We further optimize our system by replacing our off-the-shelf optimization software with customized ILP and LP solvers, called Dual Reducer and Parallel Dual Simplex respectively, that are highly accurate and orders of magnitude faster. 

   more » « less
5. A Mixed-Integer Fractional Optimization Approach to Best Subset Selection

   https://doi.org/10.1287/ijoc.2020.1031  

   Gómez, Andrés; Prokopyev, Oleg A. (March 2021, INFORMS Journal on Computing)

   null (Ed.)

   We consider the best subset selection problem in linear regression—that is, finding a parsimonious subset of the regression variables that provides the best fit to the data according to some predefined criterion. We are primarily concerned with alternatives to cross-validation methods that do not require data partitioning and involve a range of information criteria extensively studied in the statistical literature. We show that the problem of interest can be modeled using fractional mixed-integer optimization, which can be tackled by leveraging recent advances in modern optimization solvers. The proposed algorithms involve solving a sequence of mixed-integer quadratic optimization problems (or their convexifications) and can be implemented with off-the-shelf solvers. We report encouraging results in our computational experiments, with respect to both the optimization and statistical performance. Summary of Contribution: This paper considers feature selection problems with information criteria. We show that by adopting a fractional optimization perspective (a well-known field in nonlinear optimization and operations research), it is possible to leverage recent advances in mixed-integer quadratic optimization technology to tackle traditional statistical problems long considered intractable. We present extensive computational experiments, with both synthetic and real data, illustrating that the new fractional optimization approach is orders of magnitude faster than existing approaches in the literature. 

   more » « less