A note on sensitivity of value functions of mathematical programs with complementarity constraints

Using standard nonlinear programming (NLP) theory, we establish formulas for first and second order directional derivatives of optimal value functions of parametric mathematical programs with complementarity constraints (MPCCs). The main point is that under a linear independence condition on the active constraint gradients, optimal value sensitivity of MPCCs is essentially the same as for nonlinear programs, in spite of the combinatorial nature of the MPCC feasible set. Unlike NLP however, second order directional derivatives of the MPCC optimal value function show combinatorial structure. Received: October 31, 2000 / Accepted: March 8, 2002?Published online June 25, 2002     

Optimal sensitivity based on IPOPT

We introduce a flexible, open source implementation that provides the optimal sensitivity of solutions of nonlinear programming (NLP) problems, and is adapted to a fast solver based on a barrier NLP method. The program, called sIPOPT evaluates the sensitivity of the Karush?CKuhn?CTucker (KKT) system with respect to perturbation parameters. It is paired with the open-source IPOPT NLP solver and reuses matrix factorizations from the solver, so that sensitivities to parameters are determined with minimal computational cost. Aside from estimating sensitivities for parametric NLPs, the program provides approximate NLP solutions for nonlinear model predictive control and state estimation. These are enabled by pre-factored KKT matrices and a fix-relax strategy based on Schur complements. In addition, reduced Hessians are obtained at minimal cost and these are particularly effective to approximate covariance matrices in parameter and state estimation problems. The sIPOPT program is demonstrated on four case studies to illustrate all of these features.     

Prox-Regularization Methods for Generalized Fractional Programming

If a fractional program does not have a unique solution or the feasible set is unbounded, numerical difficulties can occur. By using a prox-regularization method that generates a sequence of auxiliary problems with unique solutions, these difficulties are avoided. Two regularization methods are introduced here. They are based on Dinkelbach-type algorithms for generalized fractional programming, but use a regularized parametric auxiliary problem. Convergence results and numerical examples are presented.     

Generalized Derivatives for Solutions of Parametric Ordinary Differential Equations with Non-differentiable Right-Hand Sides

Sensitivity analysis provides useful information for equation-solving, optimization, and post-optimality analysis. However, obtaining useful sensitivity information for systems with nonsmooth dynamic systems embedded is a challenging task. In this article, for any locally Lipschitz continuous mapping between finite-dimensional Euclidean spaces, Nesterov’s lexicographic derivatives are shown to be elements of the plenary hull of the (Clarke) generalized Jacobian whenever they exist. It is argued that in applications, and in several established results in nonsmooth analysis, elements of the plenary hull of the generalized Jacobian of a locally Lipschitz continuous function are no less useful than elements of the generalized Jacobian itself. Directional derivatives and lexicographic derivatives of solutions of parametric ordinary differential equation (ODE) systems are expressed as the unique solutions of corresponding ODE systems, under Carathéodory-style assumptions. Hence, the scope of numerical methods for nonsmooth equation-solving and local optimization is extended to systems with nonsmooth parametric ODEs embedded.     

Second order sensitivity analysis and asymptotic theory of parametrized nonlinear programs

In this paper we study second-order differential properties of an optimal-value function(x). It is shown that under certain conditions(x) possesses second-order directional derivatives, which can be calculated by solving corresponding quadratic programs. Also upper and lower bounds on these derivatives are introduced under weaker assumptions. In particular we show that the second-order directional derivative is infinite if the corresponding quadratic program is unbounded. Finally sensitivity results are applied to investigate asymptotics of estimators in parametrized nonlinear programs.     

Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

Analyzing infeasible nonlinear programs

Nonlinear optimizers often report infeasibility during the process of initial construction of a model, or alterations to an existing model. Because solvers are unable to decide feasibility of a nonlinear constraint set with perfect accuracy, there are numerous possible explanations: the physical model really is infeasible, there is an error in the nonlinear constraint set causing infeasibility, or the model is feasible but the initial point or solver parameters are poorly chosen. It is difficult to proceed to a diagnosis of the problem in a large NLP.This paper presents an algorithm providing automated assistance in analyzing infeasible NLPs. The deletion filtering algorithm isolates a Minimal Intractable Subsystem (MIS) of constraints, a minimal set of constraints which appears infeasible to the solver given a specified initial point and parameter settings. The MIS may be as small as a few constraints from among the very much larger set defining the original model, and helps to focus the examination, thereby speeding the diagnosis. A computer tool embodying the algorithm, LSGRG (MIS), is developed and applied to demonstration examples.     

Parametric Sensitivity Analysis of Perturbed PDE Optimal Control Problems with State and Control Constraints

We study parametric optimal control problems governed by a system of time-dependent partial differential equations (PDE) and subject to additional control and state constraints. An approach is presented to compute the optimal control functions and the so-called sensitivity differentials of the optimal solution with respect to perturbations. This information plays an important role in the analysis of optimal solutions as well as in real-time optimal control.The method of lines is used to transform the perturbed PDE system into a large system of ordinary differential equations. A subsequent discretization then transcribes parametric ODE optimal control problems into perturbed nonlinear programming problems (NLP), which can be solved efficiently by SQP methods.Second-order sufficient conditions can be checked numerically and we propose to apply an NLP-based approach for the robust computation of the sensitivity differentials of the optimal solutions with respect to the perturbation parameters. The numerical method is illustrated by the optimal control and sensitivity analysis of the Burgers equation.Communicated by H. J. Pesch     

Solving mixed integer nonlinear programs by outer approximation

A wide range of optimization problems arising from engineering applications can be formulated as Mixed Integer NonLinear Programming problems (MINLPs). Duran and Grossmann (1986) suggest an outer approximation scheme for solving a class of MINLPs that are linear in the integer variables by a finite sequence of relaxed MILP master programs and NLP subproblems.Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I.The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm.An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for thel ₁ norm is also given.This work is supported by SERC grant no. SERC GR/F 07972.Corresponding author.     

Variational analysis of circular cone programs

This paper conducts variational analysis of circular programs, which form a new class of optimization problems in nonsymmetric conic programming, important for optimization theory and its applications. First, we derive explicit formulas in terms of the initial problem data to calculate various generalized derivatives/co-derivatives of the projection operator associated with the circular cone. Then we apply generalized differentiation and other tools of variational analysis to establish complete characterizations of full and tilt stability of locally optimal solutions to parameterized circular programs.     

Two-level value function approach to non-smooth optimistic and pessimistic bilevel programs

ABSTRACT

The authors' paper in Dempe et al. [Necessary optimality conditions in pessimistic bilevel programming. Optimization. 2014;63:505–533], was the first one to provide detailed optimality conditions for pessimistic bilevel optimization. The results there were based on the concept of the two-level optimal value function introduced and analysed in Dempe et al. [Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J. Optim. 22 (2012), 1309–1343], for the case of optimistic bilevel programs. One of the basic assumptions in both of these papers is that the functions involved in the problems are at least continuously differentiable. Motivated by the fact that many real-world applications of optimization involve functions that are non-differentiable at some points of their domain, the main goal of the current paper is to extend the two-level value function approach by deriving new necessary optimality conditions for both optimistic and pessimistic versions in bilevel programming with non-smooth data.     

Performance analysis of linear and nonlinear techniques for automatic scaling of discretized control problems

This paper introduces three (one linear and two nonlinear) automatic scaling techniques for NLPs with states and constraints spread over several orders of magnitude, without requiring complex off-the-shelf external tools. All of these methods have been compared to standard techniques and applied to three problems using SNOPT and IPOPT. The results confirm that the proposed techniques significantly improve the NLP conditioning, yielding more reliable and in some cases, faster NLP solutions.     

一类参数二次规划参数延拓的作用集法和稳定性分析

本文用作用集法考虑一类参数二次规划的参数延拓问题，并研究稳定性问题。     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.     

A Global Optimization Method,QBB, for Twice-Differentiable Nonconvex Optimization Problem

A global optimization method, QBB, for twice-differentiable NLPs (Non-Linear Programming) is developed to operate within a branch-and-bound framework and require the construction of a relaxed convex problem on the basis of the quadratic lower bounding functions for the generic nonconvex structures. Within an exhaustive simplicial division of the constrained region, the rigorous quadratic underestimation function is constructed for the generic nonconvex function structure by virtue of the maximal eigenvalue analysis of the interval Hessian matrix. Each valid lower bound of the NLP problem with the division progress is computed by the convex programming of the relaxed optimization problem obtained by preserving the convex or linear terms, replacing the concave term with linear convex envelope, underestimating the special terms and the generic terms by using their customized tight convex lower bounding functions or the valid quadratic lower bounding functions, respectively. The standard convergence properties of the QBB algorithm for nonconvex global optimization problems are guaranteed. The preliminary computation studies are presented in order to evaluate the algorithmic efficiency of the proposed QBB approach.     

Semicontinuity of the solution mappings to weak generalized parametric Ky Fan inequality problems with trifunctions

In this article, we discuss the lower semicontinuity of solution maps without the condition of C-strict monotonicity for two classes of weak generalized parametric Ky Fan inequalities under the case that the f-solution set be a general set-valued one. Our results extend the recent ones in the literature (e.g. Cheng, Y.H., Zhu, D.L.: Global stability results for the weak vector variational inequality. J. Glob. Optim. 32, 543–550 (2005); C.R. Chen and S.J. Li, On the solution continuity of parametric generalized systems, Pac. J. Optim. 6 (2010), pp. 141–151; Gong, X.H., Yao, J.C.: Lower semicontinuity of the set of efficient solutions for generalized systems. J. Optim. Theory Appl. 138, 197–205 (2008); Gong, X.H.: Continuity of the solution set to parametric weak vector equilibrium problems. J. Optim. Theory Appl. 139, 35–46 (2008)). Several examples are given for the illustration of our results.     

Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse

For mixed-integer quadratic program where all coefficients in the objective function and the right-hand sides of constraints vary simultaneously, we show locally Lipschitz continuity of its optimal value function, and derive the corresponding global estimation; furthermore, we also obtain quantitative estimation about the change of its optimal solutions. Applying these results to two-stage quadratic stochastic program with mixed-integer recourse, we establish quantitative stability of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. The obtained results generalize available results on continuity properties of mixed-integer quadratic programs and extend current results on quantitative stability of two-stage quadratic stochastic programs with mixed-integer recourse.     

Sensitivity analysis of discontinuous parametric periodic systems

The paper concerns the complex eigensolutions sensitivity analysis of parametric periodic system. The derivatives of (so called) monodromy matrix (Floquet transient matrix) were the first calculated. Then the first derivatives of multiplicators, which are the complex eigenvalues of monodromy matrix, were obtained. The theory has been expanded to cover a class of discontinuous parametric periodic excitation. Furthermore, the method was generalized, so that the system parameters, on which the parametric excitation period depends, can now be a design parameter. In particular, it has become possible to use the parametric excitation period as a design parameter. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On differentiability with respect to parameter of solutions to convex optimal control problems subject to state space constraints

A family of convex optimal control problems that depend on a real parameterh is considered. The optimal control problems are subject to state space constraints.It is shown that under some regularity conditions on data the solutions of these problems as well as the associated Lagrange multipliers are directionally-differentiable functions of the parameter.The respective right-derivatives are given as the solution and respective Lagrange multipliers for an auxiliary quadratic optimal control problem subject to linear state space constraints.If a condition of strict complementarity type holds, then directional derivatives become continuous ones.     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.