Test examples for nonlinear programming codes

The increasing importance of nonlinear programming software requires an enlarged set of test examples. The purpose of this note is to point out how an interested mathematical programmer could obtain computer programs of more than 120 constrained nonlinear programming problems which have been used in the past to test and compare optimization codes.     

On a pair of nonlinear mixed integer programming problems

We consider maximin and minimax nonlinear mixed integer programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed integer programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed integer programming.     

Optimal electric power scheduling: A large nonlinear programming test problem solved by recursive quadratic programming

This paper discusses a nonlinear programming problem which arises when the optimum scheduling of an electric power system is being considered. A realistic, moderately large text example is described in detail; and the solution of this example by a recent method based on quadratic programming is also reported.     

非线性-线性二层规划问题的罚函数方法

利用下层问题的K-T最优性条件将下层为线性规划的一类非线性二层规划转化成相应的单层规划,同时取下层问题的互补条件为罚项,构造了该类非线性二层规划的罚问题.通过对相应罚问题性质的分析,得到了该类非线性二层规划问题的最优性条件,同时设计了该类二层规划问题的求解方法.数值结果表明该方法是可行、有效的.     

Lipschitz properties of solutions in mathematical programming

This paper deals with the dependence of the solutions and the associated multipliers of a nonlinear programming problem when the data of the problem are subjected to small perturbations. Sufficient conditions are given which imply that the solutions and the multipliers of a perturbed nonlinear programming problem are Lipschitzian with respect to the perturbations.The authors wish to thank J. Drèze and J. P. Vial for many helpful discussions and J. B. Hiriart-Urruty for comments on a previous version of the paper.     

多约束非线性整数规划的一种改进的算法

多约束非线性整数规划是一类非常重要的问题,非线性背包问题是它的一类特殊而重要的问题.定义在有限整数集上极大化一个可分离非线性函数的多约束最优化问题.这类问题常常用于资源分配、工业生产及计算机网络的最优化模型中,运用一种新的割平面法来求解对偶问题以得到上界,不仅减少了对偶间隙,而且保证了算法的收敛性.利用区域割丢掉某些整数箱子,并把剩下的区域划分为一些整数箱子的并集,以便使拉格朗日松弛问题能有效求解,且使算法在有限步内收敛到最优解.算法把改进的割平面法用于求解对偶问题并与区域分割有效结合解决了多约束非线性背包问题的求解.数值结果表明了改进的割平面方法对对偶搜索更加有效.     

A modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

A decomposition-based solution method for stochastic mixed integer nonlinear programs

This is a summary of the main results presented in the author’s PhD thesis, supervised by D. Conforti and P. Beraldi and defended on March 2005. The thesis, written in English, is available from the author upon request. It describes one of the very few existing implementations of a method for solving stochastic mixed integer nonlinear programming problems based on deterministic global optimization. In order to face the computational challenge involved in the solution of such multi-scenario nonconvex problems, a branch and bound approach is proposed that exploits the peculiar structure of stochastic programming problem.     

Solving nonlinear principal-agent problems using bilevel programming

While significant progress has been made, analytic research on principal-agent problems that seek closed-form solutions faces limitations due to tractability issues that arise because of the mathematical complexity of the problem. The principal must maximize expected utility subject to the agent’s participation and incentive compatibility constraints. Linearity of performance measures is often assumed and the Linear, Exponential, Normal (LEN) model is often used to deal with this complexity. These assumptions may be too restrictive for researchers to explore the variety of relationships between compensation contracts offered by the principal and the effort of the agent. In this paper we show how to numerically solve principal-agent problems with nonlinear contracts. In our procedure, we deal directly with the agent’s incentive compatibility constraint. We illustrate our solution procedure with numerical examples and use optimization methods to make the problem tractable without using the simplifying assumptions of a LEN model. We also show that using linear contracts to approximate nonlinear contracts leads to solutions that are far from the optimal solutions obtained using nonlinear contracts. A principal-agent problem is a special instance of a bilevel nonlinear programming problem. We show how to solve principal-agent problems by solving bilevel programming problems using the ellipsoid algorithm. The approach we present can give researchers new insights into the relationships between nonlinear compensation schemes and employee effort.     

Generalized Lagrange multiplier technique for nonlinear programming

Our aim here is to present numerical methods for solving a general nonlinear programming problem. These methods are based on transformation of a given constrained minimization problem into an unconstrained maximin problem. This transformation is done by using a generalized Lagrange multiplier technique. Such an approach permits us to use Newton's and gradient methods for nonlinear programming. Convergence proofs are provided, and some numerical results are given.     

Piece-wise linear approximation of functions of two variables

The goal of increasing computational efficiency is one of the fundamental challenges of both theoretical and applied research in mathematical modeling. The pursuit of this goal has lead to wide diversity of efforts to transform a specific mathematical problem into one that can be solved efficiently. Recent years have seen the emergence of highly efficient methods and software for solving Mixed Integer Programming Problems, such as those embodied in the packages CPLEX, MINTO, XPRESS-MP. The paper presents a method to develop a piece-wise linear approximation of an any desired accuracy to an arbitrary continuous function of two variables. The approximation generalizes the widely known model for approximating single variable functions, and significantly expands the set of nonlinear problems that can be efficiently solved by reducing them to Mixed Integer Programming Problems. By our development, any nonlinear programming problem, including non-convex ones, with an objective function (and/or constraints) that can be expressed as sums of component nonlinear functions of no more than two variables, can be efficiently approximated by a corresponding Mixed Integer Programming Problem.     

An algorithmic framework for convex mixed integer nonlinear programs

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.     

灰色非线性约束规划的改进引力搜索算法求解

灰色非线性约束规划是灰色系统中一个重要的优化问题.为求解灰色非线性约束规划,给出了一种改进引力搜索算法的求解方法.实验结果表明改进引力搜索算法对求解灰色非线性约束规划可行有效.     

On the convergence of cross decomposition

Cross decomposition is a recent method for mixed integer programming problems, exploiting simultaneously both the primal and the dual structure of the problem, thus combining the advantages of Dantzig—Wolfe decomposition and Benders decomposition. Finite convergence of the algorithm equipped with some simple convergence tests has been proved. Stronger convergence tests have been proposed, but not shown to yield finite convergence.In this paper cross decomposition is generalized and applied to linear programming problems, mixed integer programming problems and nonlinear programming problems (with and without linear parts). Using the stronger convergence tests finite exact convergence is shown in the first cases. Unbounded cases are discussed and also included in the convergence tests. The behaviour of the algorithm when parts of the constraint matrix are zero is also discussed. The cross decomposition procedure is generalized (by using generalized Benders decomposition) in order to enable the solution of nonlinear programming problems.     

Sensitivity analysis in geometric programming

A unified approach to computing first, second, or higher-order derivatives of any of the primal and dual variables or multipliers of a geometric programming problem, with respect to any of the problem parameters (term coefficients, exponents, and constraint right-hand sides) is presented. Conditions under which the sensitivity equations possess a unique solution are developed, and ranging results are also derived. The analysis for approximating second and higher-order sensitivity generalizes to any sufficiently smooth nonlinear program.     

Global convergence analysis of the aggregate constraint homotopy method for nonlinear programming problems with both inequality and equality constraints

In this paper, we construct appropriate aggregate mappings and a new aggregate constraint homotopy (ACH) equation by converting equality constraints to inequality constraints and introducing two variable parameters. Then, we propose an ACH method for nonlinear programming problems with inequality and equality constraints. Under suitable conditions, we obtain the global convergence of this ACH method, which makes us prove the existence of a bounded smooth path that connects a given point to a Karush–Kuhn–Tucker point of nonlinear programming problems. The numerical tracking of this path can lead to an implementable globally convergent algorithm. A numerical procedure is given to implement the proposed ACH method, and the computational results are reported.     

Analysis of unbonded contact problems by means of quadratic programming

Two-body, elastic, unbonded contact problems are formulated as quadratic programming problems. Uniqueness theorems of quadratic programming theory are applied to show that the solution of a contact problem, if one exists, is unique and can be readily found by the modified simplex method of quadratic programming. A solution technique that is compatible with finite-element methods is developed, so that contact problems with complex boundary configurations can be routinely solved. A number of classical and nonclassical problems are solved. Good agreement is found for problems with previously known solutions.     

A sparse nonlinear optimization algorithm

One of the most effective numerical techniques for solving nonlinear programming problems is the sequential quadratic programming approach. Many large nonlinear programming problems arise naturally in data fitting and when discretization techniques are applied to systems described by ordinary or partial differential equations. Problems of this type are characterized by matrices which are large and sparse. This paper describes a nonlinear programming algorithm which exploits the matrix sparsity produced by these applications. Numerical experience is reported for a collection of trajectory optimization problems with nonlinear equality and inequality constraints.The authors wish to acknowledge the insightful contributions of Dr. William Huffman.     

灰色双矩阵博弈模型及其均衡解

在支付矩阵和约束条件都是灰色的情况下,给出灰双矩阵博弈的一般形式,并且定义了灰双矩阵博弈的均衡解,证明灰双矩阵博弈的均衡解可由求解一个非线性规划问题得到.     

Finding nonoscillatory solutions to difference schemes for the advection equation

The advection equation is solved using a weighted adaptive scheme that combines a monotone scheme with the central-difference approximation of the first spatial derivative. The determination of antidiffusion fluxes is treated as an optimization problem. The solvability of the optimization problem is analyzed, and the differential properties of the cost functional are examined. It is shown that the determination of antidiffusion fluxes is reduced to a linear programming problem in the case of an explicit scheme and to a nonlinear programming problem or a sequence of linear programming problems in the case of an implicit scheme. A simplified monotonization algorithm is proposed. Numerical results are presented.