Directional derivative estimates for the optimal value function of a quasidifferentiable programming problem

This paper is concerned with the optimal value function arising in the primal decomposition of a quasidifferentiable programming problem. In particular, estimates for the upper Dini directional derivative of this function are derived. They involve certain Lagrange multipliers occurring in the necessary minimum conditions to the lower level problems. This study generalizes some previously published results on this subject.     

One-sided derivatives for the value function in convex parametric programming

In [9] it is shown that the one-sided derivatives of parametric linear semi-infinite programs can be expressed in terms of one-sided cluster points of solutions and Lagrange-multipliers of the perturbed problem.

In this paper convex programs on Banach-spaces are studied. We generalize the results in [9] to this case. The analysis is based on convex duality theory [2].     

Directional differentiability of the optimal value function in convex semi-infinite programming

In this paper, directional differentiability properties of the optimal value function of a parameterized semi-infinite programming problem are studied. It is shown that if the unperturbed semi-infinite programming problem is convex, then the corresponding optimal value function is directionally differentiable under mild regularity assumptions. A max-min formula for the directional derivatives, well-known in the finite convex case, is given.     

Image of a parametric optimization problem and continuity of the perturbation function

In this note, we consider the notion of the image of a parametric optimization problem and show that the lower semicontinuity and upper semicontinuity properties of its marginal function can be equivalently expressed as two geometric relations in the image space. These results generalize some existing statements in the literature.     

Convexity and concavity properties of the optimal value function in parametric nonlinear programming

Convexity and concavity properties of the optimal value functionf* are considered for the general parametric optimization problemP() of the form min _x f(x, ), s.t.x R(). Such properties off* and the solution set mapS* form an important part of the theoretical basis for sensitivity, stability, and parametric analysis in mathematical optimization. Sufficient conditions are given for several standard types of convexity and concavity off*, in terms of respective convexity and concavity assumptions onf and the feasible region point-to-set mapR. Specializations of these results to the general parametric inequality-equality constrained nonlinear programming problem and its right-hand-side version are provided. To the authors' knowledge, this is the most comprehensive compendium of such results to date. Many new results are given.This paper is based on results presented in the PhD Thesis of the second author completed at The George Washington University under the direction of the first author.This work was partly supported by the Office of Naval Research, Program in Logistics, Contract No. N00014-75-C-0729 and by the National Science Foundation, Grant No. ECS-82-01370 to the Institute for Management Science and Engineering, The George Washington University, Washington, DC.     

Coderivatives in parametric optimization

We consider parametric families of constrained problems in mathematical programming and conduct a local sensitivity analysis for multivalued solution maps. Coderivatives of set-valued mappings are our basic tool to analyze the parametric sensitivity of either stationary points or stationary point-multiplier pairs associated with parameterized optimization problems. An implicit mapping theorem for coderivatives is one key to this analysis for either of these objects, and in addition, a partial coderivative rule is essential for the analysis of stationary points. We develop general results along both of these lines and apply them to study the parametric sensitivity of stationary points alone, as well as stationary point-multiplier pairs. Estimates are computed for the coderivative of the stationary point multifunction associated with a general parametric optimization model, and these estimates are refined and augmented by estimates for the coderivative of the stationary point-multiplier multifunction in the case when the constraints are representable in a special composite form. When combined with existing coderivative formulas, our estimates are entirely computable in terms of the original data of the problem. Key words.parametric optimization – variational analysis – sensitivity – Lipschitzian stability – generalized differentiation – coderivativesThis research was partly supported by the National Science Foundation under grant DMS-0072179.     

Directional derivatives in nonsmooth optimization

In this note, we consider two notions of second-order directional derivatives and discuss their use in the characterization of minimal points for nonsmooth functions.This research was supported by NSF Grant No. ECS-8214081, by the Fund for Promotion of Research at the Technion, and by Deutsche Forschungsgemeinschaft.     

Mordukhovich subgradients of the value function to a parametric discrete optimal control problem

This paper is devoted to the study of the first-order behavior of the value function of a parametric discrete optimal control problem with nonconvex cost functions and control constraints. By establishing an abstract result on the Mordukhovich subdifferential of the value function of a parametric mathematical programming problem, we derive a formula for computing the Mordukhovich subdifferential of the value function to a parametric discrete optimal control problem.     

Critical sets in parametric optimization

We deal with one-parameter families of optimization problems in finite dimensions. The constraints are both of equality and inequality type. The concept of a generalized critical point (g.c. point) is introduced. In particular, every local minimum, Kuhn-Tucker point, and point of Fritz John type is a g.c. point. Under fairly weak (even generic) conditions we study the set consisting of all g.c. points. Due to the parameter, the set is pieced together from one-dimensional manifolds. The points of can be divided into five (characteristic) types. The subset of nondegenerate critical points (first type) is open and dense in (nondegenerate means: strict complementarity, nondegeneracy of the corresponding quadratic form and linear independence of the gradients of binding constraints). A nondegenerate critical point is completely characterized by means of four indices. The change of these indices along is presented. Finally, the Kuhn-Tucker subset of is studied in more detail, in particular in connection with the (failure of the) Mangasarian-Fromowitz constraint qualification.     

Directional derivatives of the solution of a parametric nonlinear program

Consider a parametric nonlinear optimization problem subject to equality and inequality constraints. Conditions under which a locally optimal solution exists and depends in a continuous way on the parameter are well known. We show, under the additional assumption of constant rank of the active constraint gradients, that the optimal solution is actually piecewise smooth, hence B-differentiable. We show, for the first time to our knowledge, a practical application of quadratic programming to calculate the directional derivative in the case when the optimal multipliers are not unique.This author's research was supported by the Australian Research Council.     

Continuity of the optimal value function and optimal solutions of parametric mixed-integer quadratic programs

To properly describe and solve complex decision problems, research on theoretical properties and solution of mixed-integer quadratic programs is becoming very important. We establish in this paper different Lipschitz-type continuity results about the optimal 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 the linear constraints. The obtained results extend some existing results for continuous quadratic programs, and, more importantly, lay the foundation for further theoretical study and corresponding algorithm analysis on mixed-integer quadratic programs.     

Directional derivative estimates for Berezin's operator calculus

Directional derivative estimates for Berezin symbols of bounded operators on Bergman spaces of arbitrary bounded domains in are obtained. These estimates also hold in the setting of the Segal-Bargmann space on . It is also shown that our estimates are sharp at every point of by exhibiting the optimizers explicitly.

     

On parametric optimization in hilbert spaces

We consider parametric optimization problems of the following type; Minimize p(x,t) subject to x?C, for all t?T, where C is a weakly locally compact, closed, and convex subset of a Hilbert space H, T is a topological space, and p is a real-valued function on H×T lower semicontinuous if H is provided with the weak topology, and continuous in the second variable for all x?H. We investigate how the optimal value, and the set of optimal solutions depend on tET, We apply our results to show that the discrete eigenvalues, and the corresponding normed eigenelements of certain self-adjoint operators in Hilbert spaces depend (the latter strongly) continuous on parameters under reasonable conditions.     

Continuous approximate solutions in parametric optimization

The question of the existence of approximate solutions in parametric optimization is considered. Most results show that (under hypotheses) if a certain optimization problem has an approximate solution x ₀ for a value p ₀ of a parameter, then an approximate solution x=b(p) can be found for p in P, with b continuous, b(p ₀)=x₀, and any two such bs are homotopic. Some topological methods (use of fibrations) are used to weaken the usual convex hypotheses of such results. An equisemicontinuity condition (relative to a constraint) is introduced to allow some noncompactness. The results are applied to get approximate Nash equilibrium results for games with some nonconvexity in the strategy sets.     

A practicable way for computing the directional derivative of the optimal value function in convex programming

Formulas for computing the directional derivative of the optimal value function or of lower or upper bounds of it are well-known from literature. Because they have as a rule a minmax structure, methods from nondifferentiable optimization are required.

Considering a fully parametrized convex problem, in the paper the mentioned minmax formulas are transformed into usual programming problems. Although they are nonconvex in general, the computational effort is much lower than that for minmax problems. In several special cases, for instance, for linear least squares problems, linear programming problems arise.     

Optimal value functions in parametric programming

Optimal value functions in parametric programming are studied as compositions of objective functions and point-to-set mappings which define the constrained sets. Sufficiency conditions for the common regularity properties of optimal value functions are derived.

---

Zusammenfassung Der Optimalwert eines parametrischen Programms wird aufgefaßt als Verknüpfung der Zielfunktion mit einer mengenwertigen Abbildung, die den zulässigen Bereich definiert. Es werden hinreichende Bedingungen für einige häufig benutzte Regularitätseigenschaften der Optimalwertfunktion hergeleitet.

     

Three kinds of convexity and concavity properties of optimal value function in parametric nonlinear programming

This work is concerned with exploring the new convexity and concavity properties of the optimal value function in parametric programming. Some convex (concave) functions are discussed and sufficient conditions for new convexity and concavity of the optimal value function in parametric programming are given. Many results in this paper can be considered as deepen the convexity and concavity studies of convex (concave) functions and the optimal value functions.