An Efficient Algorithm for Quadratic Sum-of-Ratios Fractional Programs Problem

The quadratic sum-of-ratios fractional program problem has a broad range of applications in practical problems. This article will present an e?cient branch-and-bound algorithm for globally solving the quadratic sum-of-ratios fractional program problem. In this algorithm, lower bounds are computed by solving a series of parametric relaxation linear programming problems, which are established by utilizing new parametric linearizing technique. To enhance the computational speed of the proposed algorithm, a rectangle reducing tactic is used to reject a part of the investigated rectangle or the whole rectangle where there does not contain any global optimal solution of the quadratic sum-of-ratios fractional program problem. Compared with the known approaches, the proposed algorithm does not need to introduce new variables and constraints. Therefore, the proposed algorithm is more suitable for application in engineering.     

A predictor-corrector smoothing Newton method for symmetric cone complementarity problems

In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

A SUPERLINEARLY CONVERGENT TRUST REGION ALGORITHM FOR LC^1 CONSTRAINED OPTIMIZATION PROBLEMS

In this paper, a new trust region algorithm for nonlinear equality constrained LC^1 optimization problems is given. It obtains a search direction at each iteration not by solving a quadratic programming subproblem with a trust region bound, but by solving a system of linear equations. Since the computational complexity of a QP-Problem is in general much larger than that of a system of linear equations, this method proposed in this paper may reduce the computational complexity and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and super-linearly convergent to a solution of the original problem. Some numerical examples are reported, showing the proposed algorithm can be beneficial from a computational point of view.     

一类非线性互补问题的信赖域算法

In this paper,an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed.A feature of this algorithm is that only the solution of linear systems of equations is required at each iteration,thus avoiding the need for solving a quadratic subproblem with a trust region bound.Under some conditions,it is proven that this algorithm is globally and locally superlinear convergent.The limited numerical examples show its efficiency.     

求解Minimax优化问题的SQP方法

本文提出一类求解minimax优化问题的有效算法,该算法属于序列二次规划方法.它具有全局收敛性和超线性收敛速率.数值例子表明,该算法是非常有效的,这与算法具有良好的理论结果是分不开的.     

Global optimization for the generalized polynomial sum of ratios problem

In this paper, a new deterministic global optimization algorithm is proposed for solving a fractional programming problem whose objective and constraint functions are all defined as the sum of generalized polynomial ratios, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. The proposed algorithm is based on reformulating the problem as a monotonic optimization problem, and it turns out that the optimal solution which is provided by the algorithm is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and numerical examples are given to illustrate the feasibility and efficiency of the present algorithm.     

A new one‐step smoothing newton method for the second‐order cone complementarity problem

In this paper, we present a new one‐step smoothing Newton method for solving the second‐order cone complementarity problem (SOCCP). Based on a new smoothing function, the SOCCP is approximated by a family of parameterized smooth equations. At each iteration, the proposed algorithm only need to solve one system of linear equations and perform only one Armijo‐type line search. The algorithm is proved to be convergent globally and superlinearly without requiring strict complementarity at the SOCCP solution. Moreover, the algorithm has locally quadratic convergence under mild conditions. Numerical experiments demonstrate the feasibility and efficiency of the new algorithm. Copyright © 2010 John Wiley & Sons, Ltd.     

Globally convergent algorithm for nonlinearly constrained optimization problems

A new globally convergent algorithm for minimizing an objective function subject to equality and inequality constraints is presented. The algorithm determines a search direction by first solving a linear program and using the information gained thereby to define a quadratic approximation, with a guaranteed solution, to the original problem; the solution of the quadratic problem is the desired search direction. The algorithm incorporates a new method for choosing the penalty parameter. Numerical results illustrate the performance of the algorithm.The author wishes to thank Professor D. Q. Mayne and Dr. F. A. Pantoja for critically reviewing the first draft of this paper, for their suggestions, criticism, and contributions to some of the proofs. Support of the UK Science Research and Engineering Council is gratefully acknowledged.     

Scatter Search—Wellsprings and Challenges

This article is concerned with two global optimization problems (P1) and (P2). Each of these problems is a fractional programming problem involving the maximization of a ratio of a convex function to a convex function, where at least one of the convex functions is a quadratic form. First, the article presents and validates a number of theoretical properties of these problems. Included among these properties is the result that, under a mild assumption, any globally optimal solution for problem (P1) must belong to the boundary of its feasible region. Also among these properties is a result that shows that problem (P2) can be reformulated as a convex maximization problem. Second, the article presents for the first time an algorithm for globally solving problem (P2). The algorithm is a branch and bound algorithm in which the main computational effort involves solving a sequence of convex programming problems. Convergence properties of the algorithm are presented, and computational issues that arise in implementing the algorithm are discussed. Preliminary indications are that the algorithm can be expected to provide a practical approach for solving problem (P2), provided that the number of variables is not too large.     

A new smoothing and regularization Newton method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP

The nonlinear complementarity problem (denoted by NCP(F)) can be reformulated as the solution of a nonsmooth system of equations. In this paper, we propose a new smoothing and regularization Newton method for solving nonlinear complementarity problem with P ₀-function (P ₀-NCP). Without requiring strict complementarity assumption at the P ₀-NCP solution, the proposed algorithm is proved to be convergent globally and superlinearly under suitable assumptions. Furthermore, the algorithm has local quadratic convergence under mild conditions. Numerical experiments indicate that the proposed method is quite effective. In addition, in this paper, the regularization parameter ε in our algorithm is viewed as an independent variable, hence, our algorithm seems to be simpler and more easily implemented compared to many previous methods.     

带有P0函数的非线性互补问题的一个新的非内点连续算法

研究带有P₀函数的非线性互补问题. 基于一个新的光滑函数, 把问题近似成参数化的光滑方程组, 并且给出一个新的非内点连续算法. 所给算法在每步迭代只需要求解一个线性方程组和执行一次Armijo类型的线搜索. 在不需要严格互补条件的情况下, 证明了算法是全局收敛和超线性收敛的. 并且, 在一个较弱的条件下该算法具有局部二阶收敛性. 数值实验证实了算法的可行性和有效性.     

求解正定二次规划的一个全局收敛的滤子内点算法

现有的大多数分类问题都能转化成一个正定二次规划问题的求解.通过引入滤子方法,并结合求解非线性规划的原始对偶内点法,给出求解正定二次规划的滤子内点算法.该算法避免了使用效益函数时选取罚因子的困难,在较弱的假设条件下,算法具有全局收敛性.     

A new reduced gradient method for solving linearly constrained multiobjective optimization problems

In this paper, we consider the linearly constrained multiobjective minimization, and we propose a new reduced gradient method for solving this problem. Our approach solves iteratively a convex quadratic optimization subproblem to calculate a suitable descent direction for all the objective functions, and then use a bisection algorithm to find an optimal stepsize along this direction. We prove, under natural assumptions, that the proposed algorithm is well-defined and converges globally to Pareto critical points of the problem. Finally, this algorithm is implemented in the MATLAB environment and comparative results of numerical experiments are reported.     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

一类变分不等式问题的信赖域算法

基于J.M.Peng研究一类变分不等式问题（简记为VIP）时所提出的价值函数，本文提出了求解强单调的VIP的一个新的信赖域算法。和已有的处理VIP的信赖域方法不同的是：它在每步迭代时，不必求解带信赖域界的子问题，仅解一线性方程组而求得试验步。这样，计算的复杂性一般来说可降低。在通常的假设条件下，文中还证明了算法的整体收敛性。最后，在梯度是半光滑和约束是矩形域的假设下，该算法还是超线性收敛的。     

Branch-reduction-bound algorithm for generalized geometric programming

This article presents a branch-reduction-bound algorithm for globally solving the generalized geometric programming problem. To solve the problem, an equivalent monotonic optimization problem whose objective function is just a simple univariate is proposed by exploiting the particularity of this problem. In contrast to usual branch-and-bound methods, in the algorithm the upper bound of the subproblem in each node is calculated easily by arithmetic expressions. Also, a reduction operation is introduced to reduce the growth of the branching tree during the algorithm search. The proposed algorithm is proven to be convergent and guarantees to find an approximative solution that is close to the actual optimal solution. Finally, numerical examples are given to illustrate the feasibility and efficiency of the present algorithm.     

Global Linear and Quadratic One-step Smoothing Newton Method for P 0-LCP

We propose a new smoothing Newton method for solving the P ₀-matrix linear complementarity problem (P ₀-LCP) based on CHKS smoothing function. Our algorithm solves only one linear system of equations and performs only one line search per iteration. It is shown to converge to a P ₀-LCP solution globally linearly and locally quadratically without the strict complementarity assumption at the solution. To the best of author's knowledge, this is the first one-step smoothing Newton method to possess both global linear and local quadratic convergence. Preliminary numerical results indicate that the proposed algorithm is promising.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

A dynamical model for solving degenerate quadratic minimax problems with constraints

This paper presents a new neural network model for solving degenerate quadratic minimax (DQM) problems. On the basis of the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, the equilibrium point of the proposed network is proved to be equivalent to the optimal solution of the DQM problems. It is also shown that the proposed network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.