SICOpt: Solution Approach for Nonlinear Integer Stochastic Programming Problems

We propose a novel solution approach for the class of two-stage nonlinear integer stochastic programming models. These problems are characterized by large scale dimensions, as the number of constraints and variables depend on the number of realizations (scenarios) used to capture the underlying distributions of the random data. In addition, the integrality constraints on the decision variables make the solution process even much more difficult preventing the application of general purpose solvers. The proposed solution approach integrates the branch-and-bound framework with the interior point method. The main advantage of this choice is the effective exploitation of the specific structure exhibited by the different subproblems at each node of the search tree. A specifically designed warm start procedure and an early branching technique improve the overall efficiency. Our contribution is well founded from a theoretical point of view and is characterized by good computational efficiency, without any loss in terms of effectiveness. Some preliminary numerical results, obtained by solving a challenging real-life problem, prove the robustness and the efficiency of the proposed approach.     

Shooting Methods for Numerical Solution of Nonlinear Stochastic Boundary-Value Problems

Abstract

In the present investigation, shooting methods are described for numerically solving nonlinear stochastic boundary-value problems. These stochastic shooting methods are analogous to standard shooting methods for numerical solution of ordinary deterministic boundary-value problems. It is shown that the shooting methods provide accurate approximations. An error analysis is performed and computational simulations are described.     

Stabilization of Interior-Point Methods for Linear Programming

The paper studies numerical stability problems arising in the application of interior-point methods to primal degenerate linear programs. A stabilization procedure based on Gaussian elimination is proposed and it is shown that it stabilizes all path following methods, original and modified Dikin's method, Karmarkar's method, etc.     

非线性整规划的连续化

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

Upper and Lower Solution Methods for Fully Nonlinear Boundary Value Problems

Sufficient conditions are given for the existence of a solution of a fourth order nonlinear boundary value problem with nonlinear boundary conditions. The conditions assume the existence of a strong upper solution-lower solution pair, a concept that is defined in the paper. The differential equation has nonlinear dependence on all lower order derivatives of the unknown; in particular, appropriate Nagumo conditions are obtained and employed.     

非线性规划的QP-free方法

该文提出一种QP-free可行域方法用来解满足光滑不等式约束的最优化问题.此方法把QP-free方法和3-1线性互补函数相结合一个等价于原约束问题的一阶KKT条件的方程组,并在此基础上给出解这个方程组的迭代算法. 这个方法的每一步迭代都可以看作是对求KKT条件解的牛顿或拟牛顿迭代的扰动,且在该方法中每一步的迭代均具有可行性. 该方法是可实行的且具有全局性, 且不需要严格互补条件、聚点的孤立性和积极约束函数梯度的线性独立等假设. 在与文献[2]中相同的适当条件下,此方法还具有超线性收敛性. 数值检验结果表示,该文提出的QP-free可行域方法是切实有效的方法.     

Solving Problems with Semidefinite and Related Constraints Using Interior-Point Methods for Nonlinear Programming

 In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided. Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002 Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

The p-Factor-Lagrange Methods for Degenerate Nonlinear Programming

The paper presents a new approach to solving nonlinear programming (NLP) problems for which the strict complementarity condition (SCC), a constraint qualification (CQ), and a second-order sufficient condition (SOSC) for optimality are not necessarily satisfied at a solution. Our approach is based on the construction of p-regularity and on reformulating the inequality constraints as equalities. Namely, by introducing the slack variables, we get the equality constrained problem, for which the Lagrange optimality system is singular at the solution of the NLP problem in the case of the violation of the CQs, SCC and/or SOSC. To overcome the difficulty of singularity, we propose the p-factor method for solving the Lagrange system. The method has a superlinear rate of convergence under a mild assumption. We show that our assumption is always satisfied under a standard second-order sufficient condition (SOSC) for optimality. At the same time, we give examples of the problems where the SOSC does not hold, but our assumption is satisfied. Moreover, no estimation of the set of active constraints is required. The proposed approach can be applied to a variety of problems.     

On the Newton Interior-Point Method for Nonlinear Programming Problems

Interior-point methods have been developed largely for nonlinear programming problems. In this paper, we generalize the global Newton interior-point method introduced in Ref. 1 and we establish a global convergence theory for it, under the same assumptions as those stated in Ref. 1. The generalized algorithm gives the possibility of choosing different descent directions for a merit function so that difficulties due to small steplength for the perturbed Newton direction can be avoided. The particular choice of the perturbation enables us to interpret the generalized method as an inexact Newton method. Also, we suggest a more general criterion for backtracking, which is useful when the perturbed Newton system is not solved exactly. We include numerical experimentation on discrete optimal control problems.     

On the Practical Stabilization of Nonlinear Systems via Hybrid Feedback Control

Mathematical Notes - In this paper, we propose a class of hybrid control strategy with time-varying delay in order to guarantee the global uniform exponential practical stabilization of nonlinear...     

非线性规划的摄动可行方向法

本文提出了二类新的摄动可行方向法,发展和完善了这类方法.新方法形式简单而且不必用Polak程序.适当选择算法中有关参数可减少计算量,还可加快算法的收敛速度.     

非线性规划的拟罚函数—强次可行方向法

本文首先提出非线性规划的拟Ｋｕｈｎ—Ｔｕｃｋｅｒ点和拟罚函数法的概念和思想，然后结合强次可行方向法思想给出问题的两个新型算法，称之为拟罚函数—强次可行方向法．证明了该算法收敛到原问题的拟Ｋｕｈｎ—Ｔｕｃｋｅｒ点．     

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

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

Exact Penalty Functions for Nonlinear Integer Programming Problems

In this work, we study exact continuous reformulations of nonlinear integer programming problems. To this aim, we preliminarily state conditions to guarantee the equivalence between pairs of general nonlinear problems. Then, we prove that optimal solutions of a nonlinear integer programming problem can be obtained by using various exact penalty formulations of the original problem in a continuous space.     

Sequential Quadratic Programming Methods for Large-Scale Problems

Sequential quadratic (SQP) programming methodsare the method of choice when solving small or medium-sized problems. Sincethey are complex methods they are difficult (but not impossible) to adapt tosolve large-scale problems. We start by discussing the difficulties that needto be addressed and then describe some general ideas that may be used toresolve these difficulties. A number of SQP codes have been written to solve specific applications and there is a general purposed SQP code called SNOPT,which is intended for general applications of a particular type. These aredescribed briefly together with the ideas on which they are based. Finally wediscuss new work on developing SQP methods using explicit second derivatives.     

Smoothing Methods for Nonlinear Complementarity Problems

In this paper, we present some new smoothing techniques to solve general nonlinear complementarity problems. Under a weaker condition than monotonicity as on the original problems, we prove convergence of our methods. We also present an error estimate under a general monotonicity condition. Some numerical tests confirm the efficiency of the proposed methods.