Global Optimization Issues in Multiparametric Continuous and Mixed-Integer Optimization Problems

In this paper, a number of theoretical and algorithmic issues concerning the solution of parametric nonconvex programs are presented. In particular, the need for defining a suitable overestimating subproblem is discussed in detail. The multiparametric case is also addressed, and a branch and bound (B&B) algorithm for the solution of parametric nonconvex programs is proposed.     

基于粒子群算法的非线性二层规划问题的求解算法

粒子群算法（Particle Swarm Optimization，PSO）是一种新兴的优化技术，其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现，可调参数少，已得到了广泛研究和应用。本文根据该算法能够有效的求出非凸数学规划全局最优解的特点，对非线性二层规划的上下层问题求解，并根据二层规划的特点，给出了求解非线性二层规划问题全局最优解的有效算法。数值计算结果表明该算法有效。     

An Exact Solution Method for Reliability Optimization in Complex Systems

Systems reliability plays an important role in systems design, operation and management. Systems reliability can be improved by adding redundant components or increasing the reliability levels of subsystems. Determination of the optimal amount of redundancy and reliability levels among various subsystems under limited resource constraints leads to a mixed-integer nonlinear programming problem. The continuous relaxation of this problem in a complex system is a nonconvex nonseparable optimization problem with certain monotone properties. In this paper, we propose a convexification method to solve this class of continuous relaxation problems. Combined with a branch-and-bound method, our solution scheme provides an efficient way to find an exact optimal solution to integer reliability optimization in complex systems. This research was partially supported by the Research Grants Council of Hong Kong, grants CUHK4056/98E, CUHK4214/01E and 2050252, and the National Natural Science Foundation of China under Grants 79970107 and 10271073.     

New Reflection Generator for Simulated Annealing in Mixed-Integer/Continuous Global Optimization

To reduce the well-known jamming problem in global optimization algorithms, we propose a new generator for the simulated annealing algorithm based on the idea of reflection. Furthermore, we give conditions under which the sequence of points generated by this simulated annealing algorithm converges in probability to the global optimum for mixed-integer/continuous global optimization problems. Finally, we present numerical results on some artificial test problems as well as on a composite structural design problem.     

Discrete Filled Function Method for Discrete Global Optimization

A discrete filled function method is developed in this paper to solve discrete global optimization problems over strictly pathwise connected domains. Theoretical properties of the proposed discrete filled function are investigated and a solution algorithm is proposed. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method.     

Mathematical Properties of Optimization Problems Defined by Positively Homogeneous Functions

We consider the nonlinear programming problem

求无约束连续全局优化问题的单参数填充函数法

填充函数法是求解全局优化问题的一个重要的确定性算法,这种方法的关键是构造具有良好性质的填充函数.构造了一个新的求解无约束全局优化问题的填充函数.函数连续可微且只包含一个参数.通过分析该函数的相关性质,设计了相应的算法.数值实验表明该算法简单有效.     

Global Optimization of Nonlinear Bilevel Programming Problems

A novel technique that addresses the solution of the general nonlinear bilevel programming problem to global optimality is presented. Global optimality is guaranteed for problems that involve twice differentiable nonlinear functions as long as the linear independence constraint qualification condition holds for the inner problem constraints. The approach is based on the relaxation of the feasible region by convex underestimation, embedded in a branch and bound framework utilizing the basic principles of the deterministic global optimization algorithm, BB [2, 4, 5, 11]. Epsilon global optimality in a finite number of iterations is theoretically guaranteed. Computational studies on several literature problems are reported.     

一般无约束优化问题的广义拟牛顿法

对一般目标函数极小化问题的拟牛顿法及其全局收敛性的研究,已经成为拟牛顿法理论中最基本的开问题之一．本文对这个问题做了进一步的研究,对无约束优化问题提出一类新的广义拟牛顿算法,并结合Goldstein线搜索证明了算法对一般非凸目标函数极小化问题的全局收敛性．     

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

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...     

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.     

一类特殊多项式整数规划问题的最优化算法

本文考虑了一类特殊的多项式整数规划问题。此类问题有很广泛的实际应用,并且是NP难问题。对于这类问题,最优性必要条件和最优性充分条件已经给出。我们在本文中将要利用这些最优性条件设计最优化算法。首 先,利用最优性必要条件,我们给出了一种新的局部优化算法。进而我们结合最优性充分条件、新的局部优化算法和辅助函数,设计了新的全局最优化算法。本文给出的算例展示出我们的算法是有效的和可靠的。     

Construction of Test Problems for Concave Minimization Under Linear and Nonlinear Constraints

This paper presents a method for constructing test problems with known global solutions for concave minimization under linear constraints with an additional convex constraint and for reverse convex programs with an additional convex constraint. The importance of such a construction can be realized from the fact that the well known d.c. programming problem can be formulated in this form. Then, the method is further extended to generate test problems with more than one convex constraint, tight or untight at the global solution.     

Functional Optimal Estimation Problems and Their Solution by Nonlinear Approximation Schemes

The design of state estimators for nonlinear dynamic systems affected by disturbances is addressed in a functional optimization framework. The estimator contains an innovation function that has to be chosen within a suitably defined class of functions in such a way to minimize a cost functional given by the worst-case ratio of the ℒ _p norms of the estimation error and the disturbances. Since this entails an infinite-dimensional optimization problem that under general hypotheses cannot be solved analytically, an approximate solution is sought by minimizing the cost functional over linear combinations of simple “basis functions,” represented by computational units with adjustable parameters. The selection of the parameters is made by solving a constrained nonlinear programming problem, where the constraints are given by pointwise conditions that ensure the well-definiteness of the functional and the existence of a solution. Penalty terms are introduced in the cost function to account for constraints imposed on points that result from sampling the sets to which the trajectories of the state and of the estimation error belong. To ensure an efficient covering of the sets, low-discrepancy sampling techniques are exploited that generate samples deterministically spread in a uniform way, without leaving regions of the space undersampled. Work supported by a PRIN grant from the Italian Ministry of University and Research (Project “New Techniques for the Identification and Adaptive Control of Industrial Systems”) and by the EU and the Regione Liguria trough the Regional Programs of Innovative Action of the European Regional Development Fund.     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

Global Solution of Optimization Problems with Parameter-Embedded Linear Dynamic Systems

This paper develops a theory for the global solution of nonconvex optimization problems with parameter-embedded linear dynamic systems. A quite general problem formulation is introduced and a solution is shown to exists. A convexity theory for integrals is then developed to construct convex relaxations for utilization in a branch-and-bound framework to calculate a global minimum. Interval analysis is employed to generate bounds on the state variables implied by the bounds on the embedded parameters. These bounds, along with basic integration theory, are used to prove convergence of the branch-and-bound algorithm to the global minimum of the optimization problem. The implementation of the algorithm is then considered and several numerical case studies are examined thoroughly     

Optimization of generalized desirability functions under model uncertainty

Desirability functions are increasingly used in multi-criteria decision-making which we support by modern optimization. It is necessary to formulate desirability functions to obtain a generalized version with a piecewise max type-structure for optimizing them in different areas of mathematics, operational research, management science and engineering by nonsmooth optimization approaches. This optimization problem needs to be robustified as regression models employed by the desirability functions are typically built under lack of knowledge about the underlying model. In this paper, we contribute to the theory of desirability functions by our robustification approach. We present how generalized semi-infinite programming and disjunctive optimization can be used for this purpose. We show our findings on a numerical example. The robustification of the optimization problem eventually aims at variance reduction in the optimal solutions.     

Min-Max Optimization of Several Classical Discrete Optimization Problems

In this paper, we study discrete optimization problems with min-max objective functions. This type of problems has direct applications in the recent development of robust optimization. The following well-known classes of problems are discussed: minimum spanning tree problem, resource allocation problem with separable cost functions, and production control problem. Computational complexities of the corresponding min-max version of the above-mentioned problems are analyzed. Pseudopolynomial algorithms for these problems are provided under certain conditions.     

Discrete global descent method for discrete global optimization and nonlinear integer programming

A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function. The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer variables and up to 1.38 × 10¹⁰⁴ feasible points have demonstrated the applicability and efficiency of the proposed method.