Conditions Characterizing Minima of the Difference of Functions

 Optimization problems involving differences of functions arouse interest as generalizations of so-called d.c. problems, i.e. problems involving the difference of two convex functions. The class of d.c. functions is very rich, so d.c. problems are rather general optimization problems. Several global optimality conditions for these d.c. problems have been proposed in the optimization literature. We provide a survey of these conditions and try to detect their common basis. This enables us to give generalizations of the conditions to situations when the objective function is no longer a difference of convex functions, but the difference of two functions which are representable as the upper envelope of an arbitrary family of functions. (Received 6 February 2001; in revised form 11 October 2001)     

Numerical solution of a linear bilevel problem

The linear bilevel programming problem in the optimistic formulation is studied. It is reduced to an optimization problem with a nonconvex constraint in the form of a d.c. function (that is, the difference of two convex functions). For this problem, local and global search methods are developed. Numerical experiments performed for numerous specially generated problems, including large-scale ones, demonstrate the efficiency of the proposed approach.     

Branch-and-bound decomposition approach for solving quasiconvex-concave programs

A class of branch-and-bound methods is proposed for minimizing a quasiconvex-concave function subject to convex and quasiconvex-concave inequality constraints. Several important special cases where the subproblems involved by the bounding-and-branching operations can be solved quite effectively include certain d.c. programming problems, indefinite quadratic programming with one negative eigenvalue, affine multiplicative problems, and fractional multiplicative optimization.This research was accomplished while the second author was a Fellow of the Alexander von Humboldt Foundation at the University of Trier, Trier, Germany.     

A sequential quadratically constrained quadratic programming method with an augmented Lagrangian line search function

Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered.     

A branch and reduce approach for solving a class of low rank d.c. programs

Various classes of d.c. programs have been studied in the recent literature due to their importance in applicative problems. In this paper we consider a branch and reduce approach for solving a class of d.c. problems. Seven partitioning rules are analyzed and some techniques aimed at improving the overall performance of the algorithm are proposed. The results of a computational experience are provided in order to point out the performance effectiveness of the proposed techniques.     

Two algorithms for global optimization

In this paper, we develop and compare two methods for solving the problem of determining the global maximum of a function over a feasible set. The two methods begin with a random sample of points over the feasible set. Both methods then seek to combine these points into “regions of attraction” which represent subsets of the points which will yield the same local maximums when an optimization procedure is applied to points in the subset. The first method for constructing regions of attraction is based on approximating the function by a mixture of normal distributions over the feasible region and the second involves attempts to apply cluster analysis to form regions of attraction. The two methods are then compared on a set of well-known test problems.     

Hybrid stress analysis of boundary and finite elements by a super-element method

This paper is concerned with the hybrid method of boundary element and finite element techniques by means of an “external-super-element” function of the commercial finite element method code . The proposed super-element method preserves the modelling simplicity of the boundary element method and the generality of . Two- and three-dimensional elastostatic analyses are performed to demonstrate the accuracy of this method as well as its applicability to practical problems.     

Decomposition Methods for Solving Nonconvex Quadratic Programs via Branch and Bound*

The aim of this paper is to suggest branch and bound schemes, based on a relaxation of the objective function, to solve nonconvex quadratic programs over a compact polyhedral feasible region. The various schemes are based on different d.c. decomposition methods applied to the quadratic objective function. To improve the tightness of the relaxations, we also suggest solving the relaxed problems with an algorithm based on the so called “optimal level solutions” parametrical approach. *This paper has been partially supported by M.I.U.R. and C.N.R.     

Limited memory discrete gradient bundle method for nonsmooth derivative-free optimization

Typically, practical nonsmooth optimization problems involve functions with hundreds of variables. Moreover, there are many practical problems where the computation of even one subgradient is either a difficult or an impossible task. In such cases derivative-free methods are the better (or only) choice since they do not use explicit computation of subgradients. However, these methods require a large number of function evaluations even for moderately large problems. In this article, we propose an efficient derivative-free limited memory discrete gradient bundle method for nonsmooth, possibly nonconvex optimization. The convergence of the proposed method is proved for locally Lipschitz continuous functions and the numerical experiments to be presented confirm the usability of the method especially for medium size and large-scale problems.     

Single cell discretization of O(kh2 + h4) for the estimates of ${\partial u}\over{\partial n}$ for the two‐space dimensional quasi‐linear parabolic equation

In this article, new stable two‐level explicit difference methods of O(kh² + h⁴) for the estimates of for the two‐space dimensional quasi‐linear parabolic equation are derived, where k > 0 and h > 0 are grid sizes in time and space directions, respectively. We use a single computational cell for the methods, which are applicable to the problems both in cartesian and polar coordinates. The proposed methods have the simplicity in nature and employ the same marching type technique of solution. Numerical results obtained by the proposed methods for several different problems were compared with the exact solutions. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 250–261, 2001     

A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems

In this paper, a discrete filled function algorithm embedded with continuous approximation is proposed to solve max-cut problems. A new discrete filled function is defined for max-cut problems, and properties of the function are studied. In the process of finding an approximation to the global solution of a max-cut problem, a continuation optimization algorithm is employed to find local solutions of a continuous relaxation of the max-cut problem, and then global searches are performed by minimizing the proposed filled function. Unlike general filled function methods, characteristics of max-cut problems are used. The parameters in the proposed filled function need not to be adjusted and are exactly the same for all max-cut problems that greatly increases the efficiency of the filled function method. Numerical results and comparisons on some well known max-cut test problems show that the proposed algorithm is efficient to get approximate global solutions of max-cut problems.     

隐互补问题的极小化变形及其稳定点

1 引言 互补问题在最优化中有着广泛的应用,例如线性规划中的对偶问题,非线性规划中求稳定点的KKT条件以及变分不等式的求解都可以转化为互补问题,另外,某些均衡网络设计问题、信号最优化问题以及交通配置等问题也可利用互补问题来求解.     

Nonlinear analysis of elastic thin-walled shell structures

Theoretical principles, methodology and algorithms presented herein are to analyze and design the elastic thin-walled engineering structures and components, with emphasis on the important nonlinear behavior. The methodology of the consequent analysis of single-parametric nonlinear problems is applied to structural syntheses. The numerical algorithm for this analysis is based on the parameter continuation methods and the “control parameter subspace changing”. The effectiveness of the proposed approach is illustrated through several examples in thin-walled structures.     

Active-Set Projected Trust-Region Algorithm for Box-Constrained Nonsmooth Equations

In this paper, by means of an active-set strategy, we present a trust-region method for solving box-constrained nonsmooth equations. Nice properties of the proposed method include: (a) all iterates remain feasible; (b) the search direction, as adequate combination of the projected gradient direction and the trust-region direction, is an asymptotic Newton direction under mild conditions; (c) the subproblem of the proposed method, possessing the form of an unconstrained trust-region subproblem, can be solved by existing methods; (d) the subproblem of the proposed method is of reduced dimension, which is potentially cheaper when applied to solve large-scale problems. Under appropriate conditions, we establish global and local superlinear/quadratic convergence of the method. Preliminary numerical results are given.     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

A new method for solving fuzzy transportation problems using ranking function

In the literature, several methods are proposed for solving transportation problems in fuzzy environment but in all the proposed methods the parameters are represented by normal fuzzy numbers. [S.H. Chen, Operations on fuzzy numbers with function principal, Tamkang Journal of Management Sciences 6 (1985) 13–25] pointed out that in many cases it is not to possible to restrict the membership function to the normal form and proposed the concept of generalized fuzzy numbers. There are several papers in the literature in which generalized fuzzy numbers are used for solving real life problems but to the best of our knowledge, till now no one has used generalized fuzzy numbers for solving the transportation problems. In this paper, a new method is proposed for solving fuzzy transportation problems by assuming that a decision maker is uncertain about the precise values of the transportation cost, availability and demand of the product. In the proposed method transportation cost, availability and demand of the product are represented by generalized trapezoidal fuzzy numbers. To illustrate the proposed method a numerical example is solved and the obtained results are compared with the results of existing methods. Since the proposed method is a direct extension of classical method so the proposed method is very easy to understand and to apply on real life transportation problems for the decision makers.     

A new discrete filled function method for solving large scale max-cut problems

The global optimization method based on discrete filled function is a new method that solves large scale max-cut problems. We first define a new discrete filled function based on the structure of the max-cut problem and analyze its properties. Unlike the continuous filled function methods, by the characteristic of the max-cut problem, the parameters in the proposed filled function does not need to be adjusted. By combining a procedure that randomly generates initial points for minimization of the proposed filled function, the proposed algorithm can greatly reduce the computational time and be applied to large scale max-cut problems. Numerical results and comparisons with several heuristic methods indicate that the proposed algorithm is efficient and stable to obtain high quality solution of large scale max-cut problems.     

A discrete filled function algorithm for approximate global solutions of max-cut problems

A discrete filled function algorithm is proposed for approximate global solutions of max-cut problems. A new discrete filled function is defined for max-cut problems and the properties of the filled function are studied. Unlike general filled function methods, using the characteristic of max-cut problems, the parameters in proposed filled function need not be adjusted. This greatly increases the efficiency of the filled function method. By combining a procedure that randomly generates initial points for minimization of the filled function, the proposed algorithm can greatly reduce the calculation cost and be applied to large scale max-cut problems. Numerical results on different sizes and densities test problems indicate that the proposed algorithm is efficient and stable to get approximate global solutions of max-cut problems.     

Parallel iteration across the steps of high-order Runge-Kutta methods for nonstiff initial value problems

For the parallel integration of nonstiff initial value problems (IVPs), three main approaches can be distinguished: approaches based on “parallelism across the problem”, on “parallelism across the method” and on “parallelism across the steps”. The first type of parallelism does not require special integration methods and can be exploited within any available IVP solver. The method-parallelism approach received much attention, particularly within the class of explicit Runge-Kutta methods originating from fixed point iteration of implicit Runge-Kutta methods of Gaussian type. The construction and implementation on a parallel machine of such methods is extremely simple. Since the computational work per processor is modest with respect to the number of data to be exchanged between the various processors, this type of parallelism is most suitable for shared memory systems. The required number of processors is roughly half the order of the generating Runge-Kutta method and the speed-up with respect to a good sequential IVP solver is about a factor 2. The third type of parallelism (step-parallelism) can be achieved in any IVP solver based on predictor-corrector iteration and requires the processors to communicate after each full iteration. If the iterations have sufficient computational volume, then the step-parallel approach may be suitable for implementation on distributed memory systems. Most step-parallel methods proposed so far employ a large number of processors, but lack the property of robustness, due to a poor convergence behaviour in the iteration process. Hence, the effective speed-up is rather poor. The dynamic step-parallel iteration process proposed in the present paper is less massively parallel, but turns out to be sufficiently robust to achieve speed-up factors up to 15.     

A D.C. optimization method for single facility location problems

The single facility location problem with general attraction and repulsion functions is considered. An algorithm based on a representation of the objective function as the difference of two convex (d.c.) functions is proposed. Convergence to a global solution of the problem is proven and extensive computational experience with an implementation of the procedure is reported for up to 100,000 points. The procedure is also extended to solve conditional and limited distance location problems. We report on limited computational experiments on these extensions.This research was supported in part by the National Science Foundation Grant DDM-91-14489.