We consider mixed-integernonlinear robust optimization problems with nonconvexities. In detail, the functions can be nonsmooth and generalized convex, i.e., f degrees-quasiconvex or f degrees-pseudoconvex. We propose...
详细信息
We consider mixed-integernonlinear robust optimization problems with nonconvexities. In detail, the functions can be nonsmooth and generalized convex, i.e., f degrees-quasiconvex or f degrees-pseudoconvex. We propose a robust optimization method that requires no certain structure of the adversarial problem, but only approximate worst-case evaluations. The method integrates a bundle method, for continuous subproblems, into an outer approximation approach. We prove that our algorithm converges and finds an approximately robust optimal solution and propose robust gas transport as a suitable application.
In this paper we propose to utilize a variation of the alternating direction method of multipliers (ADMM) as a simple heuristic for mixed-integer nonlinear optimization problems in structural optimization. Numerical e...
详细信息
In this paper we propose to utilize a variation of the alternating direction method of multipliers (ADMM) as a simple heuristic for mixed-integer nonlinear optimization problems in structural optimization. Numerical experiments suggest that using multiple restarts of ADMM with random initial points often yields a reasonable solution with small computational cost.
We present several mathematical-optimization formulations for a problem that commonly occurs in geometry processing and specifically in the design of so-called smooth direction fields on surfaces. This problem has dir...
详细信息
We present several mathematical-optimization formulations for a problem that commonly occurs in geometry processing and specifically in the design of so-called smooth direction fields on surfaces. This problem has direct applications in 3D shape parameterization, texture mapping, and shape design via rough concept sketches, among many others. A key challenge in this setting is to design a set of unit-norm directions, on a given surface, that satisfy some prescribed constraints and vary smoothly. This naturally leads to mixed-integeroptimization formulations, because the smoothness needs to be formulated with respect to angle-valued variables, which to compare one needs to fix the discrete jump between nearby points. Previous works have primarily attacked this problem via a greedy ad-hoc strategy with a specialized solver. We demonstrate how the problem can be cast in a standard mathematical-optimization form, and we suggest several relaxations that are especially adapted to modern mathematical-optimization solvers. .
This paper improves the adaptive metamodel-based global algorithm (AMGO), which is presented for unconstrained continuous problems, to solve mixed-integer nonlinear optimization involving black-box and expensive funct...
详细信息
This paper improves the adaptive metamodel-based global algorithm (AMGO), which is presented for unconstrained continuous problems, to solve mixed-integer nonlinear optimization involving black-box and expensive functions. The new proposed method is called as METADIR, which can be divided into two stages. In the first stage, the METADIR adopts extended DIRECT method to constantly subdivide the design space and identify the sub-region that may contain the optimal value. When iterative points gather into a sub-region to some extent, we terminate the search progress of DIRECT and turn to the next stage. In the second phase, a local metamodel is constructed in this potential optimal sub-region, and then an auxiliary optimization problem extended from AMGO is established based on the local metamodel to obtain the iterative points, which are then applied to update the metamodel adaptively. To show the performance of METADIR on both continuous and mixed-integer problems, numerical tests are presented on both kinds of problems. The METADIR method is compared with the original DIRECT on continuous problems, and compared with SO-MI and GA on mixed-integer problems. Test results show that the proposed method has better accuracy and needs less function evaluations. Finally, the new proposed method is applied into the component size optimization problem of fuel cell vehicle and achieves satisfied results.
Branch and bound (BB) is the primary deterministic approach that has been applied successfully to solve mixed-integernonlinear programming (MINLPs) problems in which the participating functions are nonconvex. Recentl...
详细信息
Branch and bound (BB) is the primary deterministic approach that has been applied successfully to solve mixed-integernonlinear programming (MINLPs) problems in which the participating functions are nonconvex. Recently, a decomposition algorithm was proposed to solve nonconvex MINLPs. In this work, a generalized branch and cut (GBC) algorithm is proposed and it is shown that both decomposition and BE algorithms are specific instances of the GBC algorithm with a certain set of heuristics. This provides a unified framework for comparing BE and decomposition algorithms. Finally, a set of heuristics which may be potentially more efficient computationally compared to all currently available deterministic algorithms is presented. (C) 2000 Elsevier Science Ltd. All rights reserved.
Hard problems of discrete geometry may be formulated as a global optimization problems, which may be solved by general purpose solvers implementing branch-and-bound (B&B) algorithm. A problem of densest packing of...
详细信息
ISBN:
(纸本)9783030365929;9783030365912
Hard problems of discrete geometry may be formulated as a global optimization problems, which may be solved by general purpose solvers implementing branch-and-bound (B&B) algorithm. A problem of densest packing of N equal circles in special geometrical object, so called Square Flat Torus, R-2/Z(2), with the induced metric, is considered. It is formulated as mixed-integer problem with linear and nonconvex quadratic constraints. The open-source B&B-solver SCIP and its parallel implementation ParaSCIP have been used to find optimal arrangements for N <= 9. The main result is a confirmation of the conjecture on optimal packing for N = 9 that was published in 2012 by O. Musin and A. Nikitenko.
Many practical engineering problems, for example, in the areas of power systems, transportation, and data science, have physical aspects that are naturally modeled by smooth nonlinear functions, as well as design aspe...
详细信息
Many practical engineering problems, for example, in the areas of power systems, transportation, and data science, have physical aspects that are naturally modeled by smooth nonlinear functions, as well as design aspects that are often modeled via discrete decision variables. By combining ideas from continuous and discrete optimization, research in mixed-integer nonlinear optimization (MINLO) seeks to develop efficient and scalable exact or approximate algorithm frameworks attacking these challenging models. The dissertation focuses on treating some difficulties related to algorithm design and modeling principle in MINLO. First, in the context of the spatial branch-and-bound approach for factorable MINLO models, which decomposes complicated functions into compositions of affine functions and low-dimensional "library'' functions, we investigate a smoothing technique for univariate library functions that are not sufficiently smooth (i.e., not twice continuously differentiable). Next, we study a more tractable relaxation of a special MINLO model involving indicator variables and univariate convex functions, and we use volume as a measure for comparing the tightness of relaxations to balance the trade-off between tightness and tractability. We also lift some univariate results to the multivariate case on a simplex. Finally, we introduce various sparse generalized inverses and present an efficient and practical local-search algorithms to construct approximate sparse generalized inverses with both a low-rank property and a block structure.
Branch and bound (BB) is the primary deterministic approach that has been applied successfully to solve mixed-integernonlinear programming (MINLPs) problems in which the participating functions are nonconvex. Recentl...
详细信息
Branch and bound (BB) is the primary deterministic approach that has been applied successfully to solve mixed-integernonlinear programming (MINLPs) problems in which the participating functions are nonconvex. Recently, a decomposition algorithm was proposed to solve nonconvex MINLPs. In this work, a generalized branch and cut (GBC) algorithm is proposed and it is shown that both decomposition and BE algorithms are specific instances of the GBC algorithm with a certain set of heuristics. This provides a unified framework for comparing BE and decomposition algorithms. Finally, a set of heuristics which may be potentially more efficient computationally compared to all currently available deterministic algorithms is presented. (C) 2000 Elsevier Science Ltd. All rights reserved.
Currently, few approaches are available for mixed-integernonlinear robust optimization. Those that do exist typically either require restrictive assumptions on the problem structure or do not guarantee robust protect...
详细信息
Currently, few approaches are available for mixed-integernonlinear robust optimization. Those that do exist typically either require restrictive assumptions on the problem structure or do not guarantee robust protection. In this work, we develop an algorithm for convex mixed-integernonlinear robust optimization problems where a key feature is that the method does not rely on a specific structure of the inner worst-case (adversarial) problem and allows the latter to be non-convex. A major challenge of such a general nonlinear setting is ensuring robust protection, as this calls for a global solution of the non-convex adversarial problem. Our method is able to achieve this up to a tolerance, by requiring worst-case evaluations only up to a certain precision. For example, the necessary assumptions can be met by approximating a non-convex adversarial via piecewise relaxations and solving the resulting problem up to any requested error as a mixed-integer linear problem. In our approach, we model a robust optimization problem as a nonsmooth mixed-integernonlinear problem and tackle it by an outer approximation method that requires only inexact function values and subgradients. To deal with the arising nonlinear subproblems, we render an adaptive bundle method applicable to this setting and extend it to generate cutting planes, which are valid up to a known precision. Relying on its convergence to approximate critical points, we prove, as a consequence, finite convergence of the outer approximation algorithm. As an application, we study the gas transport problem under uncertainties in demand and physical parameters on realistic instances and provide computational results demonstrating the efficiency of our method.
The numerical optimization of continuous parameters in electrotechnical design using electromagnetic field simulation is already standard. When integer-valued variables are involved, the complexity of the optimization...
详细信息
The numerical optimization of continuous parameters in electrotechnical design using electromagnetic field simulation is already standard. When integer-valued variables are involved, the complexity of the optimization problem rises drastically. In this paper, we describe a new sequential surrogate optimization approach for simulation-based mixed-integernonlinear programming (NLP) problems. We apply the method for the optimization of combined integer- and real-valued geometrical parameters of the coils of a superconductive magnet.
暂无评论