A class of parameter-free filled functions for box-constrained system of nonlinear equations

In this paper, a class of parameter-free filled functions is proposed for solving box-constrained system of nonlinear equations. Firstly, the original problem is converted into an equivalent global optimization problem. Subsequently, a class of parameter-free filled functions is proposed for solving the problem. Some properties of the new class of filled functions are studied and discussed. Finally, an algorithm which neither computes nor explicitly approximates gradients during minimizing the filled functions is presented. The global convergence of the algorithm is also established. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.     

A global optimization algorithm for linear fractional and bilinear programs

In this paper a deterministic method is proposed for the global optimization of mathematical programs that involve the sum of linear fractional and/or bilinear terms. Linear and nonlinear convex estimator functions are developed for the linear fractional and bilinear terms. Conditions under which these functions are nonredundant are established. It is shown that additional estimators can be obtained through projections of the feasible region that can also be incorporated in a convex nonlinear underestimator problem for predicting lower bounds for the global optimum. The proposed algorithm consists of a spatial branch and bound search for which several branching rules are discussed. Illustrative examples and computational results are presented to demonstrate the efficiency of the proposed algorithm.     

Merit functions for nonsmooth complementarity problems and related descent algorithm

Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.     

An algorithm based on the generalized D-gap function for equilibrium problems

The equilibrium problem (EP) can be reformulated as an unconstrained minimization problem through the generalized D-gap function. In this paper, we propose an algorithm for minimizing the problem and analyze some convergence properties of the proposed algorithm. Under some reasonable conditions, we show that the iteration sequence generated by the algorithm is globally convergent and converges to a solution to the EP and the generalized D-gap function provides a global error bound for the algorithm.     

Properties of a family of merit functions and a merit function method for the NCP

A family of merit functions are proposed, which are the generalization of several existing merit functions. A number of favorable properties of the proposed merit functions are established. By using these properties, a merit function method for solving nonlinear complementarity problem is investigated, and the global convergence of the proposed algorithm is proved under some standard assumptions. Some preliminary numerical results are given.     

一般线性或非线性约束下的共轭投影变尺度方法

梯度投影法是一类有效的约束最优化算法，在最优化领域中占有重要的地位．但是，梯度投影法所采用的投影是正交投影，不包含目标函数和约束函数的二阶导数信息·因而；收敛速度不太令人满意．本文介绍一种共轭投影概念，利用共轭投影构造了一般线性或非线性约束下的共轭投影变尺度算法，并证明了算法在一定条件下具有全局收敛性．由于算法中的共轭投影恰当地包含了目标函数和约束函数的二阶导数信息，因而收敛速度有希望加快．数值试验的结果表明算法是有效的．     

A smoothing inexact Newton method for P 0 nonlinear complementarity problem

We first propose a new class of smoothing functions for the nonlinear complementarity function which contains the well-known Chen-Harker-Kanzow-Smale smoothing function and Huang-Han-Chen smoothing function as special cases, and then present a smoothing inexact Newton algorithm for the P ₀ nonlinear complementarity problem. The global convergence and local superlinear convergence are established. Preliminary numerical results indicate the feasibility and efficiency of the algorithm.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

一类新的罚函数与罚算法(英)

在本文中,我们提出了带不等式约束的非线性规划问题的一类新的罚函数,它的一个子类可以光滑逼近$l_1$罚函数. 基于此类新的罚函数我们给出了一种罚算法,这个算法的特点是每次迭代求出罚函数的全局精确解或非精确解. 在很弱的条件下算法总是可行的. 我们在不需要任何约束规范的情况下,证明了算法的全局收敛性. 最后给出了数值实验.     

A discrete dynamic convexized method for nonlinear integer programming

In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust.     

A new class of smoothing functions and a smoothing Newton method for complementarity problems

In this paper, we introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.     

A reformulation framework for global optimization

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

A genetic algorithm approach to nonlinear least squares estimation

A common type of problem encountered in mathematics is optimizing nonlinear functions. Many popular algorithms that are currently available for finding nonlinear least squares estimators, a special class of nonlinear problems, are sometimes inadequate. They might not converge to an optimal value, or if they do, it could be to a local rather than global optimum. Genetic algorithms have been applied successfully to function optimization and therefore would be effective for nonlinear least squares estimation. This paper provides an illustration of a genetic algorithm applied to a simple nonlinear least squares example.     

一种基于自适应混合遗传算法的非线性函数优化方法

遗传算法因其具有的特性,它采用交换、复制和突变等方法,获取的解为全局最优解,而且无需计算函数的导数,是一种只考虑输入与输出关系的黑箱问题,适用于处理各种复杂问题.此文基于最优保存的思想,把最速下降法与最优保存和自适应遗传算法相结合,用于求解非线性函数优化问题,提出一种基于自适应混合遗传算法的非线性函数全局优化方法.     

Global optimization of polynomial-expressed nonlinear optimal control problems with semidefinite programming relaxation

In this paper, we propose a new deterministic global optimization method for solving nonlinear optimal control problems in which the constraint conditions of differential equations and the performance index are expressed as polynomials of the state and control functions. The nonlinear optimal control problem is transformed into a relaxed optimal control problem with linear constraint conditions of differential equations, a linear performance index, and a matrix inequality condition with semidefinite programming relaxation. In the process of introducing the relaxed optimal control problem, we discuss the duality theory of optimal control problems, polynomial expression of the approximated value function, and sum-of-squares representation of a non-negative polynomial. By solving the relaxed optimal control problem, we can obtain the approximated global optimal solutions of the control and state functions based on the degree of relaxation. Finally, the proposed global optimization method is explained, and its efficacy is proved using an example of its application.     

Integral global optimization method for solution of nonlinear complementarity problems

The mapping in a nonlinear complementarity problem may be discontinuous. The integral global optimization algorithm is proposed to solve a nonlinear complementarity problem with a robust piecewise continuous mapping. Numerical examples are given to illustrate the effectiveness of the algorithm.     

A nonlinear Lagrangian for constrained optimization problems

A novel nonlinear Lagrangian is presented for constrained optimization problems with both inequality and equality constraints, which is nonlinear with respect to both functions in problem and Lagrange multipliers. The nonlinear Lagrangian inherits the smoothness of the objective and constraint functions and has positive properties. The algorithm on the nonlinear Lagrangian is demonstrated to possess local and linear convergence when the penalty parameter is less than a threshold (the penalty parameter in the penalty method has to approximate zero) under a set of suitable conditions, and be super-linearly convergent when the penalty parameter is decreased following Lagrange multiplier update. Furthermore, the dual problem based on the nonlinear Lagrangian is discussed and some important properties are proposed, which fail to hold for the dual problem based on the classical Lagrangian. At last, the preliminary and comparing numerical results for several typical test problems by using the new nonlinear Lagrangian algorithm and the other two related nonlinear Lagrangian algorithms, are reported, which show that the given nonlinear Lagrangian is promising.     

Unconstrained optimization reformulations of equilibrium problems

We generalize the D-gap function developed in the literature for variational inequalities to a general equilibrium problem （EP）. Through the D-gap function, the equilibrium problem is cast as an unconstrained minimization problem. We give conditions under which any stationary point of the D-gap function is a solution of EP and conditions under which it provides a global error bound for EP. Finally, these results are applied to box-constrained EP and then weaker conditions are established to obtain the desired results for box-constrained EP.