Comparison of a special-purpose algorithm with general-purpose algorithms for solving geometric programming problems

We study the performance of four general-purpose nonlinear programming algorithms and one special-purpose geometric programming algorithm when used to solve geometric programming problems. Experiments are reported which show that the special-purpose algorithm GGP often finds approximate solutions more quickly than the general-purpose algorithm GRG2, but is usually not significantly more efficient than GRG2 when greater accuracy is required. However, for some of the most difficult test problems attempted, GGP was dramatically superior to all of the other algorithms. The other algorithms are usually not as efficient as GGP or GRG2. The ellipsoid algorithm is most robust.This work was supported in part by the National Science Foundation, Grant No. MCS-81-02141.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

非线性半定规划若干算法介绍

介绍近几年国际上求解非线性半定规划的若干有效新算法, 包括增广Lagrangian函数法、序列半定规划法、序列线性方程组法以及交替方向乘子法. 最后, 对非线性半定规划的算法研究前景进行了探讨.     

Extreme point programming with nonlinear constraints

This paper summarizes previous results obtained by the authors on methods of solving extreme point mathematical programming problems with linear constraints. It is also shown how these results can be extended to yield an algorithm for solving extreme point mathematical programming problems with nonlinear constraints. Numerical examples to illustrate the algorithms are included.     

使用非单调线搜索正割方法解约束优化的整体收敛性

基于Powell和Yuan所建议的近似Fetcher罚函数作为函数使用单调线搜索的技术,本文提供了一类正割方法解约束优化。在合理的条件下,证明了所提供的算法的整体收敛性和收敛速率。     

Convergence bounds for nonlinear programming algorithms

Bounds on convergence are given for a general class of nonlinear programming algorithms. Methods in this class generate at each interation both constraint multipliers and approximate solutions such that, under certain specified assumptions, accumulation points of the multiplier and solution sequences satisfy the Fritz John or the Kuhn—Tucker optimality conditions. Under stronger assumptions, convergence bounds are derived for the sequences of approximate solution, multiplier and objective function values. The theory is applied to an interior—exterior penalty function algorithm modified to allow for inexact subproblem solutions. An entirely new convergence bound in terms of the square root of the penalty controlling parameter is given for this algorithm.     

Numerical Methods for Optimal Dividend Payment and Investment Strategies of Markov-Modulated Jump Diffusion Models with Regular and Singular Controls

This work focuses on numerical methods for finding optimal dividend payment and investment policies to maximize the present value of the cumulative dividend payment until ruin; the surplus is modeled by a regime-switching jump diffusion process subject to both regular and singular controls. Using the dynamic programming principle, the optimal value function obeys a coupled system of nonlinear integro-differential quasi-variational inequalities. Since the closed-form solutions are virtually impossible to obtain, we use Markov chain approximation techniques to approximate the value function and optimal controls. Convergence of the approximation algorithms are proved. Examples are presented to illustrate the applicability of the numerical methods.     

Solving a gas-lift optimization problem by dynamic programming

Gas lift is a costly, however indispensable means to recover oil from high-depth reservoirs that entails solving the gas-lift optimization problem, GOP, often in response to variations in the dynamics of the reservoir and economic oscillations. GOP can be cast as a mixed integer nonlinear programming problem whose integer variables decide which oil wells should produce, while the continuous variables allocate the gas-compressing capacity to the active ones. This paper extends the GOP formulation to encompass uncertainties in the oil outflow and precedence constraints imposed on the activation of wells. Recursive solutions are suggested for instances devoid of precedence constraints, as well as instances arising from precedence constraints induced by forests and general acyclic graphs. For the first two classes, pseudo-polynomial algorithms are developed to solve a discretized version of GOP, while the most general version is shown to be NP-Hard in the strong sense. Numerical experiments provide evidence that the approximate algorithms obtained by solving the recurrences produce near-optimal solutions. Further, the family of cover inequalities of the knapsack problem is extended to the gas-lift optimization problem.     

Superlinearly convergent approximate Newton methods for LC1 optimization problems

In the literature, the proof of superlinear convergence of approximate Newton or SQP methods for solving nonlinear programming problems requires twice smoothness of the objective and constraint functions. Sometimes, the second-order derivatives of those functions are required to be Lipschitzian. In this paper, we present approximate Newton or SQP methods for solving nonlinear programming problems whose objective and constraint functions have locally Lipschitzian derivatives, and establishQ-superlinear convergence of these methods under the assumption that these derivatives are semismooth. This assumption is weaker than the second-order differentiability. The extended linear-quadratic programming problem in the fully quadratic case is an example of nonlinear programming problems whose objective functions have semismooth but not smooth derivatives.This work is supported by the Australian Research Council.This paper is dedicated to Professor O.L. Mangasarian on the occasion of his 60th birthday.     

On the approximate augmented Lagrangian for nonlinear symmetric cone programming

This paper studies the approximate augmented Lagrangian for nonlinear symmetric cone programming. The analysis is based on some results under the framework of Euclidean Jordan algebras. We formulate the approximate Lagrangian dual problem and study conditions for approximate strong duality results and an approximate exact penalty representation. We also show, under Robinson’s constraint qualification, that the sequence of stationary points of the approximate augmented Lagrangian problems converges to a stationary point of the original nonlinear symmetric cone programming.     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

Minimum and Worst-Case Performance Ratios of Rollout Algorithms

Rollout algorithms are heuristic algorithms that can be applied to solve deterministic and stochastic dynamic programming problems. The basic idea is to use the cost obtained by applying a well known heuristic, called the base policy, to approximate the value of the optimal cost-to-go. We develop a theoretical approach to prove, for the 0-1 knapsack problem, that the minimum performance ratio of the rollout algorithms tends to be significantly greater when the performance ratio of the corresponding base policy is poor and that the worst-case performance ratio is significantly better than the one of the corresponding base policies.     

Interactions between nonlinear programming and modeling systems

Modeling systems are very important for bringing mathematical programming software to nonexpert users, but few nonlinear programming algorithms are today linked to a modeling system. The paper discussed the advantages of linking modeling systems with nonlinear programming. Traditional algorithms can be linked using black-box function and derivatives evaluation routines for local optimization. Methods for generating this information are discussed. More sophisticated algorithms can get access to almost any type of information: interval evaluations and constraint restructuring for detailed preprocessing, second order information for sequential quadratic programming and interior point methods, and monotonicity and convex relaxations for global optimization. Some of the sophisticated information is available today; the rest can be generated on demand.     

Iterative algorithms for nonlinear problems in remote sensing

First a brief review of the Backus and Gilbert method for the linear problems is given. Then a comprehensive presentation of iterative algorithms for constructing approximate solutions of nonlinear problems from erroneous inadequate data is given. Proofs of convergence and error estimates of these iterative algorithms are obtained. It is found that locally the limit of the iterates does not satisfy the original nonlinear operator equation, but a somewhat different nonlinear equation which depends on the initial iterate. A nonlinear radiative transfer equation in remote sensing of the atmospheric temperature profiles is used as an example to demonstrate the applicability of the iterative algorithms. Finally, a discussion of the present status of research in this domain and some personal views on what should be the useful lines for future research is given.     

一类拟互补问题的迭代法

本文研究一类非线性算子的拟互补问题,获得了在新的条件下的解的存在唯一性定理,并给出了两个Schwarz算法,所产生的近似解序列单调收敛于真解。     

Projected equation methods for approximate solution of large linear systems

We consider linear systems of equations and solution approximations derived by projection on a low-dimensional subspace. We propose stochastic iterative algorithms, based on simulation, which converge to the approximate solution and are suitable for very large-dimensional problems. The algorithms are extensions of recent approximate dynamic programming methods, known as temporal difference methods, which solve a projected form of Bellman’s equation by using simulation-based approximations to this equation, or by using a projected value iteration method.     

Equality and inequality constrained optimization algorithms with convergent stepsizes

In this paper, we consider two algorithms for nonlinear equality and inequality constrained optimization. Both algorithms utilize stepsize strategies based on differentiable penalty functions and quadratic programming subproblems. The essential difference between the algorithms is in the stepsize strategies used. The objective function in the quadratic subproblem includes a linear term that is dependent on the penalty functions. The quadratic objective function utilizes an approximate Hessian of the Lagrangian augmented by the penalty functions. In this approximation, it is possible to ignore the second-derivative terms arising from the constraints in the penalty functions.The penalty parameter is determined using a strategy, slightly different for each algorithm, that ensures boundedness as well as a descent property. In particular, the boundedness follows as the strategy is always satisfied for finite values of the parameter.These properties are utilized to establish global convergence and the condition under which unit stepsizes are achieved. There is also a compatibility between the quadratic objective function and the stepsize strategy to ensure the consistency of the properties for unit steps and subsequent convergence rates.This research was funded by SERC and ESRC research contracts. The author is grateful to Professors Laurence Dixon and David Mayne for their comments. The numerical results in the paper were obtained using a program written by Mr. Robin Becker.     

集值非线性混合变分包含问题的一类新的迭代算法

在Hilbert空间中讨论一类广义集值非线性混合变分包含问题近似解的存在性，建立变分包含与广义预解方程的等价性，形成了迭代算法并研究了算法的收敛性．     

Solution of Delay Differential Equation by Means of Homotopy Analysis Method

The algorithm of approximate analytical solution for delay differential equations (DDE) is obtained via homotopy analysis method (HAM) and modified homotopy analysis method (MHAM). Various examples of linear, nonlinear and system of initial value problems of DDE are solved and the results obtained show that these algorithms are accurate and efficient for the DDE. The convergence of this algorithm is also proved.