On a decomposition method for nonconvex global optimization

A rigorous foundation is presented for the decomposition method in nonconvex global optimization, including parametric optimization, partly convex, partly monotonic, and monotonic/linear optimization. Incidentally, some errors in the recent literature on this subject are pointed out and fixed.     

Zero duality gap for a class of nonconvex optimization problems

By an equivalent transformation using thepth power of the objective function and the constraint, a saddle point can be generated for a general class of nonconvex optimization problems. Zero duality gap is thus guaranteed when the primal-dual method is applied to the constructed equivalent form.The author very much appreciates the comments from Prof. Douglas J. White.     

Unified theory of augmented Lagrangian methods for constrained global optimization

We classify in this paper different augmented Lagrangian functions into three unified classes. Based on two unified formulations, we construct, respectively, two convergent augmented Lagrangian methods that do not require the global solvability of the Lagrangian relaxation and whose global convergence properties do not require the boundedness of the multiplier sequence and any constraint qualification. In particular, when the sequence of iteration points does not converge, we give a sufficient and necessary condition for the convergence of the objective value of the iteration points. We further derive two multiplier algorithms which require the same convergence condition and possess the same properties as the proposed convergent augmented Lagrangian methods. The existence of a global saddle point is crucial to guarantee the success of a dual search. We generalize in the second half of this paper the existence theorems for a global saddle point in the literature under the framework of the unified classes of augmented Lagrangian functions.     

Hidden convexity in some nonconvex quadratically constrained quadratic programming

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs. This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and by the Binational Science Foundation. This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871.     

Distributed stochastic nonsmooth nonconvex optimization

Distributed consensus optimization has received considerable attention in recent years and several distributed consensus-based algorithms have been proposed for (nonsmooth) convex and (smooth) nonconvex objective functions. However, the behavior of these distributed algorithms on nonconvex, nonsmooth and stochastic objective functions is not understood. Such class of functions and distributed setting are motivated by several applications, including problems in machine learning and signal processing. This paper presents the first convergence analysis of the decentralized stochastic subgradient method for such classes of problems, over networks modeled as undirected, fixed, graphs.     

A geometric framework for nonconvex optimization duality using augmented lagrangian functions

We provide a unifying geometric framework for the analysis of general classes of duality schemes and penalty methods for nonconvex constrained optimization problems. We present a separation result for nonconvex sets via general concave surfaces. We use this separation result to provide necessary and sufficient conditions for establishing strong duality between geometric primal and dual problems. Using the primal function of a constrained optimization problem, we apply our results both in the analysis of duality schemes constructed using augmented Lagrangian functions, and in establishing necessary and sufficient conditions for the convergence of penalty methods.     

Potential transformation methods for large-scale constrained global optimization

Several techniques for global optimization treat the objective functionf as a force-field potential. In the simplest case, trajectories of the differential equationmx=–f sample regions of low potential while retaining the energy to surmount passes which might block the way to regions of even lower local minima. Apotential transformation is an increasing functionV:. It determines a new potentialg=V(f), with the same minimizers asf and new trajectories satisfying . We discuss a class of potential transformations that greatly increase the attractiveness of low local minima.These methods can be applied to constrained problems through the use of Lagrange multipliers. We discuss several methods for efficiently computing approximate Lagrange multipliers, making this approach practical.     

Algorithms for parametric nonconvex programming

In this paper, we consider a general family of nonconvex programming problems. All of the objective functions of the problems in this family are identical, but their feasibility regions depend upon a parameter . This family of problems is called a parametric nonconvex program (PNP). Solving (PNP) means finding an optimal solution for every program in the family. A prototype branch-and-bound algorithm is presented for solving (PNP). By modifying a prototype algorithm for solving a single nonconvex program, this algorithm solves (PNP) in one branch-and-bound search. To implement the algorithm, certain compact partitions and underestimating functions must be formed in an appropriate manner. We present an algorithm for solving a particular (PNP) which implements the prototype algorithm by forming compact partitions and underestimating functions based upon rules given by Falk and Soland. The programs in this (PNP) have the same concave objective function, but their feasibility regions are described by linear constraints with differing right-hand sides. Computational experience with this algorithm is reported for various problems.The author would like to thank Professors R. M. Soland, T. L. Morin, and P. L. Yu for their helpful comments. Thanks also go to two anonymous reviewers for their useful comments concerning an earlier version of this paper.     

Synthetic realization approach to fuzzy global optimization via gamma algorithm

A new approach is proposed for global optimization problems with fuzzy cost functions and fuzzy box and equality constraints. It allows one to avoid complex operations with fuzzy sets and the use of various subjective indices of choice. To resolve the contradiction between economically better solutions with low possibility of realization and a little poorer solution with higher possibility of realization, the synthetic realization is defined as certain fixed -level cut for all membership functions. Consideration of such realizations guarantees a level of credibility not less than given (0, 1] for all globally optimal solutions. Then, so defined -cuts are rectified to cut off realizations with possibility less than and to retain higher possibility realizations which are assigned credibility μ = 1 for the whole interval of possible realizations. This construction results in a set-valued band of credibility not less than for a given fuzzy cost function f̃(x) which band has crisp Lipschitz continuous lower- and upper-value functions f_*(x), f*(x) such that f_*(x) ≤ f̃(x) ≤ f*(x) for all x X̃ Rⁿ. Then, the gamma algorithm is applied to obtain the interval global optimal solution f̄₀(x) = [f⁰_*(x), f*₀(x)]. To further simplify the computations, the fuzziness in the feasible set X̃ is transferred to the function value space transforming X̃ into the crisp unit cube in Rⁿ₊ common for all fuzzy optimization problems in Rⁿ with box and equality constraints.     

Local saddle point and a class of convexification methods for nonconvex optimization problems

A class of general transformation methods are proposed to convert a nonconvex optimization problem to another equivalent problem. It is shown that under certain assumptions the existence of a local saddle point or local convexity of the Lagrangian function of the equivalent problem (EP) can be guaranteed. Numerical experiments are given to demonstrate the main results geometrically.     

The regularized feasible directions method for nonconvex optimization

This paper develops and studies a feasible directions approach for the minimization of a continuous function over linear constraints in which the update directions belong to a predetermined finite set spanning the feasible set. These directions are recurrently investigated in a cyclic semi-random order, where the stepsize of the update is determined via univariate optimization. We establish that any accumulation point of this optimization procedure is a stationary point of the problem, meaning that the directional derivative in any feasible direction is nonnegative. To assess and establish a rate of convergence, we develop a new optimality measure that acts as a proxy for the stationarity condition, and substantiate its role by showing that it is coherent with first-order conditions in specific scenarios. Finally we prove that our method enjoys a sublinear rate of convergence of this optimality measure in expectation.     

A note on adapting methods for continuous global optimization to the discrete case

In this note we show that various branch and bound methods for solving continuous global optimization problems can be readily adapted to the discrete case. As an illustration, we present an algorithm for minimizing a concave function over the integers contained in a compact polyhedron. Computational experience with this algorithm is reported.     

On robustness in nonconvex optimization with application to defense planning

We estimate the increase in minimum value for a decision that is robust to parameter perturbations as compared to the value of a nominal nonconvex problem. The estimates rely on expressions for subgradients and local Lipschitz moduli of min-value functions and require only the solution of the nominal problem. Across 54 mixed-integer optimization models, the median error in estimating the increase in minimum value is 12%. The results inform analysts about the possibility of obtaining cost-effective, parameter-robust decisions.     

A generalized duality and applications

The aim of this paper is to present a nonconvex duality with a zero gap and its connection with convex duality. Since a convex program can be regarded as a particular case of convex maximization over a convex set, a nonconvex duality can be regarded as a generalization of convex duality. The generalized duality can be obtained on the basis of convex duality and minimax theorems. The duality with a zero gap can be extended to a more general nonconvex problems such as a quasiconvex maximization over a general nonconvex set or a general minimization over the complement of a convex set. Several applications are given.On leave from the Institute of Mathematics, Hanoi, Vietnam.     

A unified approach to global convergence of trust region methods for nonsmooth optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Corresponding author.     

On nonconvex optimization problems with separated nonconvex variables

A mathematical programming problem is said to have separated nonconvex variables when the variables can be divided into two groups: x=(x ₁,...,x _n ) and y=( y ₁,...,y _n ), such that the objective function and any constraint function is a sum of a convex function of (x, y) jointly and a nonconvex function of x alone. A method is proposed for solving a class of such problems which includes Lipschitz optimization, reverse convex programming problems and also more general nonconvex optimization problems.     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.     

Enhancing PSO methods for global optimization

The Particle Swarm Optimization (PSO) method is a well-established technique for global optimization. During the past years several variations of the original PSO have been proposed in the relevant literature. Because of the increasing necessity in global optimization methods in almost all fields of science there is a great demand for efficient and fast implementations of relative algorithms. In this work we propose three modifications of the original PSO method in order to increase the speed and its efficiency that can be applied independently in almost every PSO variant. These modifications are: (a) a new stopping rule, (b) a similarity check and (c) a conditional application of some local search method. The proposed were tested using three popular PSO variants and a variety test functions. We have found that the application of these modifications resulted in significant gain in speed and efficiency.     

Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem

This paper presents a set of complete solutions and optimality conditions for a nonconvex quadratic-exponential optimization problem. By using the canonical duality theory developed by the first author, the nonconvex primal problem in n-dimensional space can be converted into an one-dimensional canonical dual problem with zero duality gap, which can be solved easily to obtain all dual solutions. Each dual solution leads to a primal solution. Both global and local extremality conditions of these primal solutions can be identified by the triality theory associated with the canonical duality theory. Several examples are illustrated.     

On the convergence of global methods in multiextremal optimization

A general class of derivative-free optimization procedures is presented including the corresponding convergence theory. This theory turns out to be very constructive, in the sense that the convergence conditions not only can be verified easily for many existing algorithms, but also allow one to construct new procedures. It is shown that popular methods such as branch-and-bound concepts, Pintér's general class of procedures, the algorithms of Pijavskii, Shubert, and Mladineo, and the approach of Zheng and Galperin can not only be subsumed under this class of methods, but also partly be improved by regarding them within the framework presented.