Decomposition and interval arithmetic applied to global minimization of polynomial and rational functions

A recent global optimization algorithm using decomposition (GOP), due to Floudas and Visweswaran, when specialized to the case of polynomial functions is shown to be equivalent to an interval arithmetic global optimization algorithm which applies natural extension to the cord-slope form of Taylor's expansion. Several more efficient variants using other forms of interval arithmetic are explored. Extensions to rational functions are presented. Comparative computational experiences are reported.     

Unconstrained and constrained global optimization of polynomial functions in one variable

In Floudas and Visweswaran (1990), a new global optimization algorithm (GOP) was proposed for solving constrained nonconvex problems involving quadratic and polynomial functions in the objective function and/or constraints. In this paper, the application of this algorithm to the special case of polynomial functions of one variable is discussed. The special nature of polynomial functions enables considerable simplification of the GOP algorithm. The primal problem is shown to reduce to a simple function evaluation, while the relaxed dual problem is equivalent to the simultaneous solution of two linear equations in two variables. In addition, the one-to-one correspondence between the x and y variables in the problem enables the iterative improvement of the bounds used in the relaxed dual problem. The simplified approach is illustrated through a simple example that shows the significant improvement in the underestimating function obtained from the application of the modified algorithm. The application of the algorithm to several unconstrained and constrained polynomial function problems is demonstrated.     

New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints

In Floudas and Visweswaran (1990, 1993), a deterministic global optimization approach was proposed for solving certain classes of nonconvex optimization problems. An algorithm, GOP, was presented for the solution of the problem through a series ofprimal andrelaxed dual problems that provide valid upper and lower bounds respectively on the global solution. The algorithm was proved to have finite convergence to an -global optimum. In this paper, new theoretical properties are presented that help to enhance the computational performance of the GOP algorithm applied to problems of special structure. The effect of the new properties is illustrated through application of the GOP algorithm to a difficult indefinite quadratic problem, a multiperiod tankage quality problem that occurs frequently in the modeling of refinery processes, and a set of pooling/blending problems from the literature. In addition, extensive computational experience is reported for randomly generated concave and indefinite quadratic programming problems of different sizes. The results show that the properties help to make the algorithm computationally efficient for fairly large problems.     

Validation of a Structural Optimization Algorithm Transforming Dynamic Loads into Equivalent Static Loads

Generally, structural optimization is carried out based on external static loads. However, all forces have dynamic characteristics in the real world. Mathematical optimization with dynamic loads is almost impossible in a large-scale problem. Therefore, in engineering practice, dynamic loads are often transformed into static loads via dynamic factors, design codes, and so on. Recently, a systematic transformation of dynamic loads into equivalent static loads has been proposed in Refs. 1–3. Equivalent static loads are made to generate at each time step the same displacement field as the one generated by the dynamic loads. In this research, it is verified that the solution obtained via the algorithm of Refs. 1–3 satisfies the Karush–Kuhn–Tucker necessary conditions. Application of the algorithm is discussed.     

On a Gap between Multiobjective Optimization and Scalar Optimization

We give a suitable example to show a gap between multiobjective optimization and single-objective optimization, which solves a problem proposed in Refs. 1–2.     

Decomposition based and branch and bound global optimization approaches for the phase equilibrium problem

An increasingly popular approach when solving the phase and chemical equilibrium problem is to pose it as an optimization problem. However, difficulties are encountered due to the highly nonlinear nature of the models used to represent the behavior of the fluids, and because of the existence of multiple local solutions. This work shows how it is possible to guarantee -global solutions for a certain important class of the phase and chemical equilibrium problem, namely when the liquid phase can be modeled using neither the Non-Random Two-Liquid (NRTL) equation, or the UNIversal QUAsi Chemical (UNIQUAC) equation. Ideal vapor phases are easily incorporated into the global optimization framework. A numberof interesting properties are described which drastically alter the structure of the respective problems. For the NRTL equation, it is shown that the formulation can be converted into a biconvex optimization problem. The GOP algorithm of Floudas and Visweswaran [8, 9] can then be used to obtain -global solutions in this case. For the UNIQUAC equation, the new properties show how the objective function can be transformed into the difference of two convex functions (i.e. a D.C. programming problem is obtained), where the concave portion is separable. A branch and bound algorithm based on that of Falk and Soland [6] is used to guarantee convergence to an -global solution. Examples are presented which demonstrate the performance of both algorithms.     

Some Extensions to a Direct Optimization Method

A direct method for the global extremization of a class of integrals, introduced in Refs. 1–3, is generalized to allow for constraints in the form of differential conditions and by considering the so-called infinite-horizon case.     

An existence theorem for a fractional control problem

Computational algorithms in mathematical programming have been much in use in the theory of optimal control (see, for example Refs. 1–2). In the present work, we use the algorithm devised by Dinkelback (Ref. 3) for a nonlinear fractional programming problem to prove an existence theorem for a control problem with the cost functional having a fractional form which subsumes the control problem considered by Lee and Marcus (Ref. 4) as a particular case.The author is thankful to the referee for suggestions.     

Optimal input for identification versus sensitivity reduction of systems with large parameter variations

In this article, we present an algorithm leading to an optimal controller gain for the automatic regulation of a linear system (closed-loop policy) and to an optimal auxiliary input. This is used for the purpose of either system identification, resulting in the maximum sensitivity measure and thus increased accuracy (Refs. 1–25), or system sensitivity reduction, resulting in the minimum sensitivity measure and thus reliable operation (Refs. 26–46). These results, which are robust in terms of parameter variations, are developed without constraints on the input functions.     

Finite Convergence of the Partial Inverse Algorithm

In Refs. 1–2, Lefebvre and Michelot proved the finite convergence of the partial inverse algorithm applied to a polyhedral convex function by means of some suitable tools of convex analysis. They obtained their result under some assumptions on the primal and dual solution sets. The aim of this note is to show that the proof can be extended to remove the nasty assumption on the dual solution set. The result is in conformity with the proof given in Ref. 3, which has been obtained using the concept of folding.     

Anchoring conditions for the sequential gradient-restoration algorithm and the modified quasilinearization algorithm for optimal control problems with bounded state

In Refs. 1–2, the sequential gradient-restoration algorithm and the modified quasilinearization algorithm were developed for optimal control problems with bounded state. These algorithms have a basic property: for a subarc lying on the state boundary, the state boundary equations are satisfied at every iteration, if they are satisfied at the beginning of the computational process. Thus, the subarc remains anchored on the state boundary. In this paper, the anchoring conditions employed in Refs. 1–2 are derived.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-72-2185.     

On the Extremization of Linear Integrals

By means of a suitable variational inequality, we consider an extremization method for a particular class of integrals with the integrand of the objective functional linear with respect to the derivative of the unknown function. This method is closely related to the one proposed by Miele (Refs. 1–3) and, based on an application of the Green theorem concerning the transformation of line integrals into surface integrals, it can be extended to vector extremum problems under suitable regularity assumptions.     

Generalized Variational Principle and Vector Optimization

In this note, we present a generalization of the celebrated Ekeland variational principle and its equivalent forms. The results presented in this paper unify, improve, and extend the corresponding result in Refs. 1–7.     

On solving discontinuous extremal problems

An approach to solving discontinuous problems of optimization and control is described. The approach is based on the concept of approximate gradient introduced in Ref. 1. Generalizations of the theorems of Kuhn-Tucker and Dubovitsky-Milyutin and the maximum principle of Pontryagin are proved. The mathematical constructions described allow one to solve a wide variety of applied problems of optimization and control within the class of nonsmooth (including discontinuous) functions. The paper continues the investigations of Refs. 1–2.     

Extensions of the method of quasilinearization

Recently, the method of quasilinearization has been generalized, extended, and refined (Refs. 1–2). In this paper, various results are obtained which offer monotone sequences that provide lower and upper bounds for the solution and converge quadratically, when the function involved admits a decomposition of the difference of two convex functions.     

General Ekeland's Variational Principle for Set-Valued Mappings

In this paper, we introduce the concept of approximate solutions for set-valued optimization problems. A sufficient condition for the existence of approximate solutions is obtained. A general Ekeland's variational principle for set-valued mappings in complete ordered metric spaces and complete metric spaces are derived. These results are generalizations of results for vector-valued functions in Refs. 1–4.     

Differential dynamic programming and separable programs

This paper deals with differential dynamic programming for solving nonlinear separable programs. The present algorithm and its derivation are rather different from differential dynamic programming algorithms and their derivations by Mayne and Jacobson, who have not proved the convergence of their algorithms. The local convergence of the present algorithm is proved, and numerical examples are given.The author would like to express his appreciation to Professors H. Mine and T. Katayama for their helpful discussions. The author is also indebted to Professor D. Q. Mayne for drawing his attention to Refs. 1–2.     

A Modified L-Shaped Method

This paper presents a modified version of the L-shaped method (Refs. 1–5), used to solve two-stage stochastic linear programs with fixed recourse, by employing the implicit LX method and the implicit LP method (Refs. 6–9) of the ABS class of methods. By exploiting the properties and special structure of the ABS class and applying these to the simplex method, the number of arithmetic operations is greatly decreased.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77–84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems.