Decomposition of optimization problems is a fundamental technique to reduce the computational cost and enable efficient solution of very large-scale models. Key decomposition approaches are presented in this chapter, discussing …
Decomposition of optimization problems is a fundamental technique to reduce the computational cost and enable efficient solution of very large-scale models. Key decomposition approaches are presented in this chapter, discussing primal and dual decomposition methods, Generalized Benders Decomposition, and related applications.
This paper indicates that the filled function which appeared in one of the papers by Y. L. Shang et al. (2007) is also a tunneling function; that is, we prove …
This paper indicates that the filled function which appeared in one of the papers by Y. L. Shang et al. (2007) is also a tunneling function; that is, we prove that under some general assumptions this function has the characters of both tunneling function and filled function. A solution algorithm based on this T‐F function is given and numerical tests from test functions show that our T‐F function method is very effective in finding better minima.
A novel filled function is given in this paper to find a global minima for a nonsmooth constrained optimization problem. First, a modified concept of the filled function for nonsmooth …
A novel filled function is given in this paper to find a global minima for a nonsmooth constrained optimization problem. First, a modified concept of the filled function for nonsmooth constrained global optimization is introduced, and a filled function, which makes use of the idea of the filled function for unconstrained optimization and penalty function for constrained optimization, is proposed. Then, a solution algorithm based on the proposed filled function is developed. At last, some preliminary numerical results are reported. The results show that the proposed approach is promising.
Let a polyhedron $P$ be defined by one of the following ways: (i) $P = \{x \in R^n \colon A x \leq b\}$, where $A \in Z^{(n+k) \times n}$, $b …
Let a polyhedron $P$ be defined by one of the following ways:
(i) $P = \{x \in R^n \colon A x \leq b\}$, where $A \in Z^{(n+k) \times n}$, $b \in Z^{(n+k)}$ and $rank\, A = n$;
(ii) $P = \{x \in R_+^n \colon A x = b\}$, where $A \in Z^{k \times n}$, $b \in Z^{k}$ and $rank\, A = k$.
And let all rank order minors of $A$ be bounded by $\Delta$ in absolute values. We show that the short rational generating function for the power series $$ \sum\limits_{m \in P \cap Z^n} x^m $$ can be computed with the arithmetic complexity $ O\left(T_{SNF}(d) \cdot d^{k} \cdot d^{\log_2 \Delta}\right), $ where $k$ and $\Delta$ are fixed, $d = \dim P$, and $T_{SNF}(m)$ is the complexity to compute the Smith Normal Form for $m \times m$ integer matrix. In particular, $d = n$ for the case (i) and $d = n-k$ for the case (ii).
The simplest examples of polyhedra that meet conditions (i) or (ii) are the simplicies, the subset sum polytope and the knapsack or multidimensional knapsack polytopes.
We apply these results to parametric polytopes, and show that the step polynomial representation of the function $c_P(y) = |P_{y} \cap Z^n|$, where $P_{y}$ is parametric polytope, can be computed by a polynomial time even in varying dimension if $P_{y}$ has a close structure to the cases (i) or (ii). As another consequence, we show that the coefficients $e_i(P,m)$ of the Ehrhart quasi-polynomial $$ \left| mP \cap Z^n\right| = \sum\limits_{j = 0}^n e_i(P,m)m^j $$ can be computed by a polynomial time algorithm for fixed $k$ and $\Delta$.
The nonlinear complementarity problem has been converted into a system of nonsmooth equations by means of Fischer-Burmeister functional, which may be called the Fischer-Burmeister equation. The local superlinear convergence of …
The nonlinear complementarity problem has been converted into a system of nonsmooth equations by means of Fischer-Burmeister functional, which may be called the Fischer-Burmeister equation. The local superlinear convergence of the generalized Newton method applied to the Fischer-Burmeister equation has been established under certain regularity assumptions. In contrast to the damped Newton method for systems of smooth equations, global convergence of the damped generalized Newton method for systems of nonsmooth equations cannot be proved in general. In this paper, we show that the natural globalization of the Newton method for smooth equations can be extended to the Fischer-Burmeister equation without any hybrid strategy. Moreover, we are also able to demonstrate that the damped modified Gauss-Newton method can be extended to the Fischer-Burmeister equation. This shows that the elegant convergence analysis of the traditional Newton, damped Newton and damped Gauss-Newton methods can be naturally generalized to the Fischer-Burmeister equation.
In this paper a new class of multidimensional global optimization algorithms (called "divide the best" algorithms) is proposed. The class unifies and generalizes the classes of the characteristic methods and …
In this paper a new class of multidimensional global optimization algorithms (called "divide the best" algorithms) is proposed. The class unifies and generalizes the classes of the characteristic methods and the adaptive partition algorithms introduced by Grishagin and Pinter respectively. The new scheme includes also some methods which do not fit either the characteristic or the adaptive partition families. A detailed convergence study is presented. A special attention is paid to cases where sufficient conditions of everywhere dense, local and global convergence are fulfilled only over subregions of the search domain.
This paper presents the development of fuzzy logic representations using the notion of normalized fuzzy matrices developed by Gabr and Dorrah [1–4] for solving quadratic programming problems in a fully …
This paper presents the development of fuzzy logic representations using the notion of normalized fuzzy matrices developed by Gabr and Dorrah [1–4] for solving quadratic programming problems in a fully fuzzy environment. The first is the arithmetic type based on dual cell representation, expressed by replacing each parameter with a pair of parentheses, the first is the actual value and the second is corresponding fuzzy level, (Value, Fuzzy Level). The second is the visual type based on colored cells representation expressed by replacing each parameter by its value and coded (negative or positive) colors based on the color Hue circle corresponding to its fuzzy level. The quadratic programming problem formulation in its general form is developed in a fully fuzzy environment. A modified dual simplex method algorithm is depicted for the representation of the equivalent linear optimization problem. The problem is represented in a spreadsheet model with built-in programmed Visual Basic Applications macros. The proposed fuzzy logic algebra is then used in a straightforward manner inside this spreadsheet model. The fuzzy logic levels can be easily transferred at the end of the solution to equivalent uncertainties (each level is substituted by a corresponding actual mean and actual standard deviation). Finally, a numerical example is given to illustrate the efficacy of the developed formulations.
The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems with both twice differentiable function and constraint, we can propose an efficient algorithm based …
The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems with both twice differentiable function and constraint, we can propose an efficient algorithm based on Branch and Bound techniques. The method is first displayed in the simple case with an interval constraint. The extension is displayed afterwards to the general case with an additional nonconvex twice differentiable constraint. A quadratic bounding function which is better than the well known linear underestimator is proposed while w-subdivision is added to support the branching procedure. Computational results on several and various types of functions show the efficiency of our algorithms and their superiority with respect to the existing methods.
In this paper, the global minimization problem of a multi-dimensional black-box Lipschitzian function is considered. In order to pass from the original Lipschitz multi-dimensional problem to a univariate one, an …
In this paper, the global minimization problem of a multi-dimensional black-box Lipschitzian function is considered. In order to pass from the original Lipschitz multi-dimensional problem to a univariate one, an approach using space-filling curves to reduce the dimension is applied. The method does not use derivatives and, at each iteration, works with a set of estimates of the Hölder constant of the reduced one-dimensional problem. A two-phase technique is applied to accelerate the search of the global minimum. Numerical experiments carried out on several hundreds of test functions show a promising performance of the discussed algorithm in comparison with its direct competitors.
Contents: Some Important Classes of Global Optimization Problems.- Outer Approximation.- Concavity Cut.- Branch and Bound.- Cutting Methods.- Successive Approximation Methods.- Successive Partition Methods.- Decomposition of Large Scale Problems.- Special Problems …
Contents: Some Important Classes of Global Optimization Problems.- Outer Approximation.- Concavity Cut.- Branch and Bound.- Cutting Methods.- Successive Approximation Methods.- Successive Partition Methods.- Decomposition of Large Scale Problems.- Special Problems of Concave Minimization.- D.C. Programming.- Lipschitz and Continuous Optimization.
Abstract : The report presents selected applications of nonlinear programming in some detail. The first chapter, which is a general introduction to nonlinear programming, contains definitions, classifications of problems, mathematical …
Abstract : The report presents selected applications of nonlinear programming in some detail. The first chapter, which is a general introduction to nonlinear programming, contains definitions, classifications of problems, mathematical characteristics, and solution procedures. The remaining chapters deal with various problems and their nonlinear programming models.
A bibliography in fractional programming is provided which contains 551 references. It was attempted to include all publications in this area of nonlinear programming as they have appeared in more …
A bibliography in fractional programming is provided which contains 551 references. It was attempted to include all publications in this area of nonlinear programming as they have appeared in more than 45 years now.
article Free AccessTesting Unconstrained Optimization Software Authors: Jorge J. Moré Argonne National Labortory, 9700 South Cass Avenue, Argonne, IL Argonne National Labortory, 9700 South Cass Avenue, Argonne, ILView Profile , …
article Free AccessTesting Unconstrained Optimization Software Authors: Jorge J. Moré Argonne National Labortory, 9700 South Cass Avenue, Argonne, IL Argonne National Labortory, 9700 South Cass Avenue, Argonne, ILView Profile , Burton S. Garbow Argonne National Labortory, 9700 South Cass Avenue, Argonne, IL Argonne National Labortory, 9700 South Cass Avenue, Argonne, ILView Profile , Kenneth E. Hillstrom Argonne National Labortory, 9700 South Cass Avenue, Argonne, IL Argonne National Labortory, 9700 South Cass Avenue, Argonne, ILView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 7Issue 1pp 17–41https://doi.org/10.1145/355934.355936Published:01 March 1981Publication History 1,046citation5,094DownloadsMetricsTotal Citations1,046Total Downloads5,094Last 12 Months516Last 6 weeks82 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Distance geometry problems arise in the determination of protein structure. We consider the case where only a subset of the distances between atoms is given and formulate this distance geometry …
Distance geometry problems arise in the determination of protein structure. We consider the case where only a subset of the distances between atoms is given and formulate this distance geometry problem as a global minimization problem with special structure. We show that global smoothing techniques and a continuation approach for global optimization can be used to determine global solutions of this problem reliably and efficiently. The global continuation approach determines a global solution with less computational effort than is required by a standard multistart algorithm. Moreover, the continuation approach usually finds the global solution from any given starting point, while the multistart algorithm tends to fail.
From the Publisher: Mathematica has defined the state of the art in technical computing for over a decade, and has become a standard in many of the world's leading companies …
From the Publisher:
Mathematica has defined the state of the art in technical computing for over a decade, and has become a standard in many of the world's leading companies and universities. From simple calculator operations to large-scale programming and the preparation of interactive documents, Mathematica is the tool of choice.