Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.     

Nonlinear Model Predictive Control via Feasibility-Perturbed Sequential Quadratic Programming

Model predictive control requires the solution of a sequence of continuous optimization problems that are nonlinear if a nonlinear model is used for the plant. We describe briefly a trust-region feasibility-perturbed sequential quadratic programming algorithm (developed in a companion report), then discuss its adaptation to the problems arising in nonlinear model predictive control. Computational experience with several representative sample problems is described, demonstrating the effectiveness of the proposed approach.     

关于非线性多目标规划问题非劣解解法的探讨

非线性多目标规划是一类复杂的规划问题，由于其往往没有最优解，因此求其非劣解具有重要的意义。本首先探讨了无约束条件下非线性多目标规划的解法，然后提出了有约束条件下非线性多目标规划的一种解法。所述方法具有一定的普遍意义。     

一个解不等式约束非线性规划问题的有效方法

本文提出了一个解不等式约束非线性规划问题有效方法．在这个方法中,考虑解一个等价Ｋｕｈｎ－Ｔｕｃｋｅｒ条件的非线性方程组．这个方程组中ＮＣＰ函数的使用消去了对应于不等式约束的Ｌａｇｒａｎｇｅ乘子的非负性．截断牛顿方法被用来解这个非线性方程组．为了保证全局收敛性,一个强健的损失函数被选为寻查函数,同时方法中插入修正最速下降方向．本文证明了方法的分Ｑ－二阶收敛性,同时指出新方法可以有效地解稀疏大规模非线性规划问题。     

求解非线性规划问题的两个微分方程系统

本文给出Evtushenko与Zhadan（1974）提出的求解数学规划问题微分方程系统的两个校正形式,它们可用于求解具有等式和不等式约束的非线性规化问题。第一个校正系统拓宽了Evtushenko与Zhadan微分方程方法;第二个校正系统通过引入新的方程系统导出乘子函数得到,它无需使用Evtushenko与Zhadan所用的那样强的约束规范。我们建立了这两个微分方程方法及其离散迭代方法的收敛性定理,给出了基于第二个微分方程离散格式的数值算法及其某些数值结果。     

一个解非线性0-1整数规划问题基于罚函数的混合粒子群优化算法

利用罚函数思想把非线性0-1整数规划问题转化为无约束最优化问题,然后把粒子群优化和罚函数方法结合构造出一个基于罚函数的混合粒子群优化算法,数值结果表明所提出的算法是有效的.     

对等式约束非线性规划问题的Hestenes-Powell增广拉格朗日函数的进一步研究

本文对用无约束极小化方法求解等式约束非线性规划问题的Hestenes-Powell 增广拉格朗日函数作了进一步研究．在适当的条件下,我们建立了Hestenes-Powell增广拉格朗日函数在原问题变量空间上的无约束极小与原约束问题的解之间的关系,并且也给出了Hestenes-Powell增广拉格朗日函数在原问题变量和乘子变量的积空间上的无约束极小与原约束问题的解之间的一个关系．因此,从理论的观点来看,原约束问题的解和对应的拉格朗日乘子值不仅可以用众所周知的乘子法求得,而且可以通过对Hestenes-Powell 增广拉格朗日函数在原问题变量和乘子变量的积空间上执行一个单一的无约束极小化来获得．     

非线性整规划的连续化

本文讨论了非线性整规划问题的连续化途径．结论是可以将无约束和有约束的非线性整规划全局解问题化为非线性连续规划问题求解．     

A Null Space Approach for Solving Nonlinear Complementarity Problems

In this work, null space techniques are employed to tackle nonlinear complementarity problems （NCPs）. NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.     

Globally Convergent Inexact Quasi-Newton Methods for Solving Nonlinear Systems

Large scale nonlinear systems of equations can be solved by means of inexact quasi-Newton methods. A global convergence theory is introduced that guarantees that, under reasonable assumptions, the algorithmic sequence converges to a solution of the problem. Under additional standard assumptions, superlinear convergence is preserved.     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

Novel Algorithms for Noisy Minimization Problems with Applications to Neural Networks Training

The supervisor and searcher cooperation framework (SSC), introduced in Refs. 1 and 2, provides an effective way to design efficient optimization algorithms combining the desirable features of the two existing ones. This work aims to develop efficient algorithms for a wide range of noisy optimization problems including those posed by feedforward neural networks training. It introduces two basic SSC algorithms. The first seems suited for generic problems. The second is motivated by neural networks training problems. It introduces also inexact variants of the two algorithms, which seem to possess desirable properties. It establishes general theoretical results about the convergence and speed of SSC algorithms and illustrates their appealing attributes through numerical tests on deterministic, stochastic, and neural networks training problems.     

一种求解序列二次规划结合信赖域的多维滤子算法

求解非线性规划问题最有效的方法之一为序列二次规划。但是,由于序列二次规划结合信赖域时,会出现可能无解的情况(即不相容性)。而本文针对不相容性提出了一类序列二次规划结合信赖域的多维相容滤子算法。首先,本文根据一般文献中提及的方法对其约束条件引进参数变量,对其目标函数加以惩罚,即实行了可行化处理(也就是无需可行性恢复阶段),从而克服了不相容性。其次,本文提出了多维滤子条件来对迭代步进行选择性的接受,从而避免了传统二维滤子算法的严格条件,使得对迭代步的接受程度大大的放松。最后针对可能出现的maratos效应,我们通过二阶校正策略提出了一种修改后的多维滤子算法。同时,在一定的假设条件下算法具有全局收敛性。     

An Interior-Point Algorithm for Nonconvex Nonlinear Programming

The paper describes an interior-point algorithm for nonconvex nonlinear programming which is a direct extension of interior-point methods for linear and quadratic programming. Major modifications include a merit function and an altered search direction to ensure that a descent direction for the merit function is obtained. Preliminary numerical testing indicates that the method is robust. Further, numerical comparisons with MINOS and LANCELOT show that the method is efficient, and has the promise of greatly reducing solution times on at least some classes of models.     

Solving Posynomial Geometric Programming Problems via Generalized Linear Programming

This paper revisits an efficient procedure for solving posynomial geometric programming (GP) problems, which was initially developed by Avriel et al. The procedure, which used the concept of condensation, was embedded within an algorithm for the more general (signomial) GP problem. It is shown here that a computationally equivalent dual-based algorithm may be independently derived based on some more recent work where the GP primal-dual pair was reformulated as a set of inexact linear programs. The constraint structure of the reformulation provides insight into why the algorithm is successful in avoiding all of the computational problems traditionally associated with dual-based algorithms. Test results indicate that the algorithm can be used to successfully solve large-scale geometric programming problems on a desktop computer.     

一种基于LVI求解二次规划问题的数值算法

给出并研究了一种数值算法(简称94LVI算法),用于求解带等式和双端约束的二次规划问题. 这类带约束的二次规划问题首先被转换为线性变分不等式问题,该问题等价于分段线性投影等式.接着使用94LVI算法求解上述分段线性投影等式,从而得到QP问题的最优解. 进一步给出了94LVI算法的全局收敛性证明. 94LVI算法与经典有效集算法的对比实验结果证实了给出的94LVI算法在求解二次规划问题上的高效性与优越性.     

A Structured Reduced Sequential Quadratic Programming and Its Application to a Shape Design Problem

The objective of this work is to solve a model one dimensional duct design problem using a particular optimization method. The design problem is formulated as an equality constrained optimization, called all at once method, so that the analysis problem is not solved until the optimal design is reached. Furthermore, the sparsity structure in the Jacobian of the linearized constraints is exploited by decomposing the variables into the design and flow parts. To achieve this, sequential quadratic programming with BFGS update for the reduced Hessian of the Lagrangian function is used with the variable reduction method which preserves the structure of the Jacobian in representing the null space basis matrix. By updating the reduced Hessians of which the dimension is the number of design variables, the storage requirement for the Hessians is reduced by a large amount. In addition, the flow part of the Jacobian can be computed analytically.The algorithm with a line search globalization is described. A global and local analysis is provided with a modification of the paper by Byrd and Nocedal [Mathematical Programming 49(1991) pp 285-323] in which they analyzed a similar algorithm with the orthogonal factorization method which assumes the orthogonality of the null space basis matrix. Numerical results are obtained and compared favorably with results from the black box method, unconstrained optimization formulation.     

带有极值函数的多目标双层规划问题的对偶

For a multiobjective bilevel programming problem(P) with an extremal-value function,its dual problem is constructed by using the Fenchel-Moreau conjugate of the functions involved.Under some convexity and monotonicity assumptions,the weak and strong duality assertions are obtained.     

Nonlinear Proximal Decomposition Method for Convex Programming

In this paper, we propose a new decomposition method for solving convex programming problems with separable structure. The proposed method is based on the decomposition method proposed by Chen and Teboulle and the nonlinear proximal point algorithm using the Bregman function. An advantage of the proposed method is that, by a suitable choice of the Bregman function, each subproblem becomes essentially the unconstrained minimization of a finite-valued convex function. Under appropriate assumptions, the method is globally convergent to a solution of the problem.     

求解线性约束的区间二次规划问题的神经网络

在本文中,基于神经网络,提出了一类求解具有线性约束区间二次规划问题的方法,使用增广拉格朗日函数,建立了求解规划问题的神经网络模型。基于压缩不动点理论,证明了所提出神经网络的平衡点就是等式约束区间二次规划问题的最优解。使用适当的Lyapunov函数,证明了所提出的神经网络的平衡点是全局指数稳定的。最后,两个数值仿真结果验证了本文所用方法的可行性与有效性。