一些类型的数学规划问题的全局最优解

本文对严格单调函数给出了几个凸化和凹化的方法，利用这些方法可将一个严格单调的规划问题转化为一个等价的标准D．C．规划或凹极小问题．本文还对只有一个严格单调的约束的非单调规划问题给出了目标函数的一个凸化和凹化方法，利用这些方法可将只有一个严格单调约束的非单调规划问题转化为一个等价的凹极小问题．再利用已有的关于D．C．规划和凹极小的算法，可以求得原问题的全局最优解．     

Robust Solution of Nonconvex Global Optimization Problems

The concept of ɛ-approximate optimal solution as widely used in nonconvex global optimization is not quite adequate, because such a point may correspond to an objective function value far from the true optimal value, while being infeasible. We introduce a concept of essential ɛ-optimal solution, which gives a more appropriate approximate optimal solution, while being stable under small perturbations of the constraints. A general method for finding an essential ɛ-optimal solution in finitely many steps is proposed which can be applied to d.c. programming and monotonic optimization.     

一些约束规划问题的近似全局最优解

首先将一个具有多个约束的规划问题转化为一个只有一个约束的规划问题,然后通过利用这个单约束的规划问题,对原来的多约束规划问题提出了一些凸化、凹化的方法,这样这些多约束的规划问题可以被转化为一些凹规划、反凸规划问题．最后,还证明了得到的凹规划和反凸规划的全局最优解就是原问题的近似全局最优解．     

Lagrange Duality and Partitioning Techniques in Nonconvex Global Optimization

It is shown that, for very general classes of nonconvex global optimization problems, the duality gap obtained by solving a corresponding Lagrangian dual in reduced to zero in the limit when combined with suitably refined partitioning of the feasible set. A similar result holds for partly convex problems where exhaustive partitioning is applied only in the space of nonconvex variables. Applications include branch-and-bound approaches for linearly constrained problems where convex envelopes can be computed, certain generalized bilinear problems, linearly constrained optimization of the sum of ratios of affine functions, and concave minimization under reverse convex constraints.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.     

类Broyden族非拟牛顿算法对一般目标函数的全局收敛性

应用双参数的类Broyden族校正公式,为研究求解无约束最优化问题的拟牛顿类算法对一般目标函数的收敛性这个开问题提供了一种新的方法．     

多重集非凸分裂可行问题的非精确均值投影算法

在本文中,我们引入了非精确均值投影算法来求解多重集非凸分裂可行问题,其中这些非凸集合为半代数邻近正则集合.通过借助著名的Kurdyka-Lojasiewicz不等式理论,我们建立了算法的收敛性.     

The Brunn–Minkowski Inequality and Nonconvex Sets

We improve the Brunn–Minkowski inequality for nonconvex sets. Besides the volume of the sets, our estimate depends on the volume of the convex hull of one of the sets. The estimate is asymptotically the best possible if this set is fixed and the size of the other tends to infinity.     

Global Optimality Conditions for Nonconvex Optimization

In this paper we give an analytical equivalent for the inclusion of a set to the Lebesque set of a convex function. Using this results, we obtain global optimality conditions (GOC) related to classical optimization theory for convex maximization and reverse-convex optimization. Several examples illustrate the effectiveness of these optimality conditions allowing to escape from stationary points and local extremums.     

Global Optimization of Nonconvex Polynomial Programming Problems Having Rational Exponents

This paper considers the solution of nonconvex polynomial programming problems that arise in various engineering design, network distribution, and location-allocation contexts. These problems generally have nonconvex polynomial objective functions and constraints, involving terms of mixed-sign coefficients (as in signomial geometric programs) that have rational exponents on variables. For such problems, we develop an extension of the Reformulation-Linearization Technique (RLT) to generate linear programming relaxations that are embedded within a branch-and-bound algorithm. Suitable branching or partitioning strategies are designed for which convergence to a global optimal solution is established. The procedure is illustrated using a numerical example, and several possible extensions and algorithmic enhancements are discussed.     

非凸无约束优化问题的广义拟牛顿法的全局收敛性

本文对无约束优化问题提出一类新的广义拟牛顿法,并采用一类非精确线搜索证明了算法对一般非凸目标函数极小化问题的全局收敛性.     

Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization

This contribution gives an overview on the state-of-the-art and recent advances in mixed integer optimization to solve planning and design problems in the process industry. In some case studies specific aspects are stressed and the typical difficulties of real world problems are addressed. Mixed integer linear optimization is widely used to solve supply chain planning problems. Some of the complicating features such as origin tracing and shelf life constraints are discussed in more detail. If properly done the planning models can also be used to do product and customer portfolio analysis. We also stress the importance of multi-criteria optimization and correct modeling for optimization under uncertainty. Stochastic programming for continuous LP problems is now part of most optimization packages, and there is encouraging progress in the field of stochastic MILP and robust MILP. Process and network design problems often lead to nonconvex mixed integer nonlinear programming models. If the time to compute the solution is not bounded, there are already a commercial solvers available which can compute the global optima of such problems within hours. If time is more restricted, then tailored solution techniques are required.     

An Improved Spectral Conjugate Gradient Algorithm for Nonconvex Unconstrained Optimization Problems

In this paper, an improved spectral conjugate gradient algorithm is developed for solving nonconvex unconstrained optimization problems. Different from the existent methods, the spectral and conjugate parameters are chosen such that the obtained search direction is always sufficiently descent as well as being close to the quasi-Newton direction. With these suitable choices, the additional assumption in the method proposed by Andrei on the boundedness of the spectral parameter is removed. Under some mild conditions, global convergence is established. Numerical experiments are employed to demonstrate the efficiency of the algorithm for solving large-scale benchmark test problems, particularly in comparison with the existent state-of-the-art algorithms available in the literature.     

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.     

Concave functions,blaschke products,and polygonal mappings

We consider the class Co(p) of all conformal maps of the unit disk onto the exterior of a bounded convex set. We prove that the triangle mappings, i.e., the functions that map the unit disk onto the exterior of a triangle, are among the extreme points of the closed convex hull of Co(p). Moreover, we prove a conjecture on the closed convex hull of Co(p) for all p ∈ (0, 1) which had partially been proved by the authors for some values of p ∈ (0, 1).     

On Solving Nonconvex Optimization Problems by Reducing The Duality Gap

Lagrangian bounds, i.e. bounds computed by Lagrangian relaxation, have been used successfully in branch and bound bound methods for solving certain classes of nonconvex optimization problems by reducing the duality gap. We discuss this method for the class of partly linear and partly convex optimization problems and, incidentally, point out incorrect results in the recent literature on this subject.     

Optimality Conditions for Nonconvex Constrained Optimization Problems

Abstract

We present optimality conditions for a class of nonsmooth and nonconvex constrained optimization problems. To achieve this aim, various well-known constraint qualifications are extended based on the concept of tangential subdifferential and the relations between them are investigated. Moreover, local and global necessary and sufficient optimality conditions are derived in the absence of convexity of the feasible set. In addition to the theoretical results, several examples are provided to illustrate the advantage of our outcomes.     

A Dynamic Domain Contraction Algorithm for Nonconvex Piecewise Linear Network Flow Problems*

We consider the Nonconvex Piecewise Linear Network Flow Problem (NPLNFP) which is known to be -hard. Although exact methods such as branch and bound have been developed to solve the NPLNFP, their computational requirements increase exponentially with the size of the problem. Hence, an efficient heuristic approach is in need to solve large scale problems appearing in many practical applications including transportation, production-inventory management, supply chain, facility expansion and location decision, and logistics. In this paper, we present a new approach for solving the general NPLNFP in a continuous formulation by adapting a dynamic domain contraction. A Dynamic Domain Contraction (DDC) algorithm is presented and preliminary computational results on a wide range of test problems are reported. The results show that the proposed algorithm generates solutions within 0 to 0.94 % of optimality in all instances that the exact solutions are available from a branch and bound method.     

非线性比式和问题的全局优化算法

In this paper,a global optimization algorithm is proposed for nonlinear sum of ratios problem(P).The algorithm works by globally solving problem(P1) that is equivalent to problem(P),by utilizing linearization technique a linear relaxation programming of the (P1) is then obtained.The proposed algorithm is convergent to the global minimum of(P1) through the successive refinement of linear relaxation of the feasible region of objective function and solutions of a series of linear relaxation programming.Nume...     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.