Hölder behavior of optimal solutions and directional differentiability of marginal functions in nonlinear programming

This paper is concerned with the Hölder properties of optimal solutions of a nonlinear programming problem with perturbations in some fixed direction. The Hölder property is used to obtain the directional derivative for the marginal function.The authors are grateful for the referees' helpful comments, which led in particular to improvements in an early version of the paper.     

Stabilized SQP revisited

The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve superlinear convergence in situations when the Lagrange multipliers associated to a solution are not unique. Within the framework of Fischer (Math Program 94:91–124, 2002), the key to local superlinear convergence of sSQP are the following two properties: upper Lipschitzian behavior of solutions of the Karush-Kuhn-Tucker (KKT) system under canonical perturbations and local solvability of sSQP subproblems with the associated primal-dual step being of the order of the distance from the current iterate to the solution set of the unperturbed KKT system. According to Fernández and Solodov (Math Program 125:47–73, 2010), both of these properties are ensured by the second-order sufficient optimality condition (SOSC) without any constraint qualification assumptions. In this paper, we state precise relationships between the upper Lipschitzian property of solutions of KKT systems, error bounds for KKT systems, the notion of critical Lagrange multipliers (a subclass of multipliers that violate SOSC in a very special way), the second-order necessary condition for optimality, and solvability of sSQP subproblems. Moreover, for the problem with equality constraints only, we prove superlinear convergence of sSQP under the assumption that the dual starting point is close to a noncritical multiplier. Since noncritical multipliers include all those satisfying SOSC but are not limited to them, we believe this gives the first superlinear convergence result for any Newtonian method for constrained optimization under assumptions that do not include any constraint qualifications and are weaker than SOSC. In the general case when inequality constraints are present, we show that such a relaxation of assumptions is not possible. We also consider applying sSQP to the problem where inequality constraints are reformulated into equalities using slack variables, and discuss the assumptions needed for convergence in this approach. We conclude with consequences for local regularization methods proposed in (Izmailov and Solodov SIAM J Optim 16:210–228, 2004; Wright SIAM J. Optim. 15:673–676, 2005). In particular, we show that these methods are still locally superlinearly convergent under the noncritical multiplier assumption, weaker than SOSC employed originally.     

Solution differentiability for parametric nonlinear control problems with control-state constraints

This paper considers parametric nonlinear control problems subject to mixed control-state constraints. The data perturbations are modeled by a parameterp of a Banach space. Using recent second-order sufficient conditions (SSC), it is shown that the optimal solution and the adjoint multipliers are differentiable functions of the parameter. The proof blends numerical shooting techniques for solving the associated boundary-value problem with theoretical methods for obtaining SSC. In a first step, a differentiable family of extremals for the underlying parameteric boundary-value problem is constructed by assuming the regularity of the shooting matrix. Optimality of this family of extremals can be established in a second step when SSC are imposed. This is achieved by building a bridge between the variational system corresponding to the boundary-value problem, solutions of the associated Riccati ODE, and SSC.Solution differentiability provides a theoretical basis for performing a numerical sensitivity analysis of first order. Two numerical examples are worked out in detail that aim at reducing the considerable deficit of numerical examples in this area of research.This paper is dedicated to Professor J. Stoer on the occasion of his 60th birthday.The authors are indebted to K. Malanowski for helpful discussions.     

带有不等式约束的非线性规划问题的一个精确增广Lagrange函数

对求解带有不等式约束的非线性非凸规划问题的一个精确增广Lagrange函数进行了研究．在适当的假设下,给出了原约束问题的局部极小点与增广Lagrange函数,在原问题变量空间上的无约束局部极小点之间的对应关系．进一步地,在对全局解的一定假设下,还提供了原约束问题的全局最优解与增广Lagrange函数,在原问题变量空间的一个紧子集上的全局最优解之间的一些对应关系．因此,从理论上讲,采用该文给出的增广Lagrange函数作为辅助函数的乘子法,可以求得不等式约束非线性规划问题的最优解和对应的Lagrange乘子．     

Realtime control of robots with initial value perturbations via nonlinear programming methods

The mathematical model of an industrial robot with initial value perturbations is considered as a parametric nonlinear control problem subject to control and state constraints. Based on recent stability results for parametric control problems, a robust nonlinear programming method is proposed for computing the sensitivity derivatives of optimal solutions. Real-time control approximations of perturbed optimal solutions are obtained by evaluating a first order Taylor expansion of the perturbed solution. The efficiency of the real-time approximation is demonstrated for the robot model     

Local stability of solutions to differentiable optimization problems in banach spaces

This paper considers a class of nonlinear differentiable optimization problems depending on a parameter. We show that, if constraint regularity, a second-order sufficient optimality condition, and a stability condition for the Lagrange multipliers hold, then for sufficiently smooth perturbations of the constraints and the objective function the optimal solutions locally obey a type of Lipschitz condition. The results are applied to finite-dimensional problems, equality constrained problems, and optimal control problems.     

On the existence and nonexistence of Lagrange multipliers in Banach spaces

The paper deals with the existence of Lagrange multipliers for a general nonlinear programming problem. Some regularity conditions are formulated which are, in a sense, the weakest to assure the existence of multipliers. A number of related conditions are discussed. The connection between the choice of suitable function spaces and the existence of multipliers is analyzed.This work was partly supported by the National Science Foundation, Grant No. GF-37298, to the Institute of Automatic Control, Technical University of Warsaw, Warsaw, Poland, and the Department of Computer and Control Sciences, University of Minnesota, Minneapolis, Minnesota.The author wishes to thank Professor A. P. Wierzbicki for many important remarks concerning the subject of this paper.     

Quantitative stability analysis for vector problems of 0–1 programming

We consider multiple objective 0–1 programming problems in the situation where parameters of objective functions and linear constraints are exposed to independent perturbations. We study quantitative characteristics of stability (stability radii) of problem solutions. An approach to deriving formulae and estimations of stability radii is presented. This approach is applied to stability analysis of the linear 0–1 programming problem and problems with two types of nonlinear objective functions: linear absolute value and quadratic.     

Modified Legendre–Gauss–Radau Collocation Method for Optimal Control Problems with Nonsmooth Solutions

A new method is developed for solving optimal control problems whose solutions are nonsmooth. The method developed in this paper employs a modified form of the Legendre–Gauss–Radau orthogonal direct collocation method. This modified Legendre–Gauss–Radau method adds two variables and two constraints at the end of a mesh interval when compared with a previously developed standard Legendre–Gauss–Radau collocation method. The two additional variables are the time at the interface between two mesh intervals and the control at the end of each mesh interval. The two additional constraints are a collocation condition for those differential equations that depend upon the control and an inequality constraint on the control at the endpoint of each mesh interval. The additional constraints modify the search space of the nonlinear programming problem such that an accurate approximation to the location of the nonsmoothness is obtained. The transformed adjoint system of the modified Legendre–Gauss–Radau method is then developed. Using this transformed adjoint system, a method is developed to transform the Lagrange multipliers of the nonlinear programming problem to the costate of the optimal control problem. Furthermore, it is shown that the costate estimate satisfies one of the Weierstrass–Erdmann optimality conditions. Finally, the method developed in this paper is demonstrated on an example whose solution is nonsmooth.

     

A Generalization of the Karush–Kuhn–Tucker Theorem for Approximate Solutions of Mathematical Programming Problems Based on Quadratic Approximation

In computations related to mathematical programming problems, one often has to consider approximate, rather than exact, solutions satisfying the constraints of the problem and the optimality criterion with a certain error. For determining stopping rules for iterative procedures, in the stability analysis of solutions with respect to errors in the initial data, etc., a justified characteristic of such solutions that is independent of the numerical method used to obtain them is needed. A necessary δ-optimality condition in the smooth mathematical programming problem that generalizes the Karush–Kuhn–Tucker theorem for the case of approximate solutions is obtained. The Lagrange multipliers corresponding to the approximate solution are determined by solving an approximating quadratic programming problem.     

Ranking in quadratic integer programming problems

The present paper develops an algorithm for ranking the integer feasible solutions of a quadratic integer programming (QIP) problem. A linear integer programming (LIP) problem is constructed which provides bounds on the values of the objective function of the quadratic problem. The integer feasible solutions of this related integer linear programming problem are systematically scanned to rank the integer feasible solutions of the quadratic problem in non-decreasing order of the objective function values. The ranking in the QIP problem is useful in solving a nonlinear integer programming problem in which some other complicated nonlinear restrictions are imposed which cannot be included in the simple linear constraints of QIP, the objective function being still quadratic.     

Application of He’s Variational Iteration Method for Solving Nonlinear BBMB Equations and Free Vibration of Systems

A new analytical method called He’s variational iteration method (VIM) is introduced to be applied to solve nonlinear Benjamin-Bona-Mahony-Burgers (BBMB) equations and free vibration of a nonlinear system having combined linear and nonlinear springs in series in this article. In this method, general Lagrange multipliers are introduced to construct correction functionals for the problems. The multipliers can be identified optimally via the variational theory. The results are compared with the results of the homotopy analysis method and also with the exact solution. He’s Variational iteration method in this problem functions so better than the homotopy analysis method and exact solutions one of them in per section.     

Direct trajectory optimization and costate estimation of finite-horizon and infinite-horizon optimal control problems using a Radau pseudospectral method

A method is presented for direct trajectory optimization and costate estimation of finite-horizon and infinite-horizon optimal control problems using global collocation at Legendre-Gauss-Radau (LGR) points. A key feature of the method is that it provides an accurate way to map the KKT multipliers of the nonlinear programming problem to the costates of the optimal control problem. More precisely, it is shown that the dual multipliers for the discrete scheme correspond to a pseudospectral approximation of the adjoint equation using polynomials one degree smaller than that used for the state equation. The relationship between the coefficients of the pseudospectral scheme for the state equation and for the adjoint equation is established. Also, it is shown that the inverse of the pseudospectral LGR differentiation matrix is precisely the matrix associated with an implicit LGR integration scheme. Hence, the method presented in this paper can be thought of as either a global implicit integration method or a pseudospectral method. Numerical results show that the use of LGR collocation as described in this paper leads to the ability to determine accurate primal and dual solutions for both finite and infinite-horizon optimal control problems.     

Stability of solutions for a class of nonlinear cone constrained optimization problems,part 1: Basic theory

We Gonsider a class of nonlinear cone constrained optimization problems depending on a parameter. Under the assumption of a constraint qualification, a second order sufficient optimality condition and a stability condition for the Lagrange multipliers it is shown, that for sufficiently smooth perturbations of the constraints and the objective function the optimal solutions obey a type of Lipschitz condition.     

Optimal control of constrained time lag systems: Necessary conditions and numerical treatment

We consider retarded optimal control problems with constant delays in state and control variables under mixed controlstate inequality constraints. First order necessary optimality conditions in the form of Pontryagin's minimum principle are presented and discussed as well as numerical methods based upon discretization techniques and nonlinear programming. The minimum principle for the considered problem class leads to a boundary value problem which is retarded in the state dynamics and advanced in the costate dynamics. It can be shown that the Lagrange multipliers associated with the programming problem provide a consistent discretization of the advanced adjoint equation for the delayed control problem. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

New approach for nonseparable dynamic programming problems

A general class of nonseparable dynamic problems is studied in a dynamic programming framework by introducingkth-order separability. The solution approach uses multiobjective dynamic programming as a separation strategy forkth-order separable dynamic problems. The theoretical grounding on which the optimal solution of the original nonseparable dynamic problem can be attained by a noninferior solution of the corresponding multiobjective dynamic programming problem is established. The relationship between the overall optimal Lagrangian multipliers and the stage-optimal Lagrangian multipliers and the relationship between the overall weighting vector and the stage weighting vector are explored, providing the basis for identifying the optimal solution of the original nonseparable problem from among the set of noninferior solutions generated by the envelope approach.This work was supported in part by NSF Grant No. CES-86-17984. The authors appreciate the comments from Dr. V. Chankong and the editorial work by Mrs. V. Benade and Dr. S. Hitchcock.     

New results on a class of exact augmented Lagrangians

In this paper, a new continuously differentiable exact augmented Lagrangian is introduced for the solution of nonlinear programming problems with compact feasible set. The distinguishing features of this augmented Lagrangian are that it is radially unbounded with respect to the multiplier and that it goes to infinity on the boundary of a compact set containing the feasible region. This allows one to establish a complete equivalence between the unconstrained minimization of the augmented Lagrangian on the product space of problem variables and multipliers and the solution of the constrained problem.The author wishes to thank Dr. L. Grippo for having suggested the topic of this paper and for helpful discussions.     

Numerical treatment of an asset price model with non-stochastic uncertainty

In contrast to stochastic differential equation models used for the calculation of the term structure of interest rates, we develop an approach based on linear dynamical systems under non-stochastic uncertainty with perturbations. The uncertainty is described in terms of known feasible sets of varying parameters. Observations are used in order to estimate these parameters by minimizing the maximum of the absolute value of measurement errors, which leads to a linear or nonlinear semi-infinite programming problem. A regularized logarithmic barrier method for solving (ill-posed) convex semi-infinite programming problems is suggested. In this method a multi-step proximal regularization is coupled with an adaptive discretization strategy in the framework of an interior point approach. A special deleting rule permits one to use only a part of the constraints of the discretized problems. Convergence of the method and its stability with respect to data perturbations in the cone of convexC ¹-functions are studied. On the basis of the solutions of the semi-infinite programming problems a technical trading system for future contracts of the German DAX is suggested and developed. Supported by the Stiftung Rheinland/Pfalz für Innovation, No. 8312-386261/307.     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.