Subgradients of value functions in parametric dynamic programming

We study in this paper the first-order behavior of value functions in parametric dynamic programming with linear constraints and nonconvex cost functions. By establishing an abstract result on the Fréchet subdifferential of value functions of parametric mathematical programming problems, some new formulas on the Fréchet subdifferential of value functions in parametric dynamic programming are obtained.     

Minimization of marginal functions in mathematical programming based on continuous outer subdifferentials

Typically, exact information of the whole subdifferential is not available for intrinsically nonsmooth objective functions such as for marginal functions. Therefore, the semismoothness of the objective function cannot be proved or is even violated. In particular, in these cases standard nonsmooth methods cannot be used. In this paper, we propose a new approach to develop a converging descent method for this class of nonsmooth functions. This approach is based on continuous outer subdifferentials introduced by us. Further, we introduce on this basis a conceptual optimization algorithm and prove its global convergence. This leads to a constructive approach enabling us to create a converging descent method. Within the algorithmic framework, neither semismoothness nor calculation of exact subgradients are required. This is in contrast to other approaches which are usually based on the assumption of semismoothness of the objective function.     

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.

     

G-pre-invex functions in mathematical programming

In the present paper, we introduce the concept of G-pre-invex functions with respect to η defined on an invex set with respect to η. These function unify the concepts of nondifferentiable convexity, pre-invexity and r-pre-invexity. Furthermore, relationships of G-pre-invex functions to various introduced earlier pre-invexity concepts are also discussed. Some (geometric) properties of this class of functions are also derived. Finally, optimality results are established for optimization problems under appropriate G-pre-invexity conditions.     

Nondifferentiable mathematical programming and convex-concave functions

For a convex-concave functionL(x, y), we define the functionf(x) which is obtained by maximizingL with respect toy over a specified set. The minimization problem with objective functionf is considered. We derive necessary conditions of optimality for this problem. Based upon these necessary conditions, we define its dual problem. Furthermore, a duality theorem and a converse duality theorem are obtained. It is made clear that these results are extensions of those derived in studies on a class of nondifferentiable mathematical programming problems.This work was supported by the Japan Society for the Promotion of Sciences.     

Directional derivatives of optimal value functions in mathematical programming

This note discusses the existence of the directional derivatives of the optimal value functions in a class of nonlinear programming problems and gives the expressions of the directional derivatives. In the study, it is not assumed that the optimal set at the point discussed is not empty. Many well-known results of this area can be derived as special cases of the main theorems of this note.This research was supported by the National Science Foundation of China. The authors would like to thank Professor A. V. Fiacco and the referees for their helpful suggestions.     

Exact penalty functions method for mathematical programming problems involving invex functions

In this paper, some new results on the exact penalty function method are presented. Simple optimality characterizations are given for the differentiable nonconvex optimization problems with both inequality and equality constraints via exact penalty function method. The equivalence between sets of optimal solutions in the original mathematical programming problem and its associated exact penalized optimization problem is established under suitable invexity assumption. Furthermore, the equivalence between a saddle point in the invex mathematical programming problem and an optimal point in its exact penalized optimization problem is also proved.     

Asymptotic properties of penalized objective functions in regular mathematical programming problems

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 117–124, Moscow State University, 1989.     

Membership functions,some mathematical programming models and production scheduling

The authors have studied in [5] alternative real variable models based on the function $\text{d(x) =}\text{x}\text{(α + x)}\text{, α >0}$, for certain integer or mixed-interger programming problems. Mainly, we have shown that there exists a vector α > 0 such that the solution to the problem min $\text{σ}{}_1\text{(x, α) = Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{x}{}_{\mathrm{i}}\text{(ga}{}_{\mathrm{i}}\text{+x}{}_{\mathrm{i}}\text{)}\text{, Ax = b, x ? 0}$, is a solution to the problem min σxσ⁺, Ax = b, x ? 0, where σxσ⁺ denotes the cardinal of x, i.e. the number of strictly positive components of x, thus obtaining a new model for solving in real numbers a Generalized Lattice Point Problem (Cabot, [3]).The function d(x) has been introduced by use as a general tool for solving integer or mixed-integer problems due to its property of having almost everywhere almost discrete values. In the meantime we noticed that this function may represent a membership function of a fuzzy set.In this paper, we study in detail the features of this membership function and show that Cabot's results [3] may be derived in this more general setting using the complementary function $\text{s(x) =}\text{1 ? x}\text{(α + x)}\text{=}\text{α}\text{(α+x)}$.At the same time, in the paper there are some production scheduling models within the framework of fuzzy-sets theory. To this end, a nonconvex production model is presented and it is shown that the value of the objective function $\text{μ}{}_2\text{=}\text{1 ? σ}{}_1\text{n}$ for a production programming model whose deman and/or resource vector components are parametrized, may be considered as a grade of membership of the solution of the parametrized model to the feasible set of the nonparametrized production programming model.Consequently, we get a nonconvex production programming model whose convex envelope is linear with coefficients which are in an inverse proportior to the magnitude of the nonparametrized demand or resource vector components. This result agrees with the intuitive idea that a high level of demand or resource allows a greater interval of variation in the production process than a lower level of demand or resource.     

Duality in mathematical programming of set functions: On Fenchel duality theorem

The optimization problem of a set function defined on a family a′ of measurable subsets in an atomless finite measure space (X, a, m) is investigated. The generalized Fenchel theorem is formulated and proved in this note.     

Constructions of economic functions and calculations of marginal rates in DEA using parametric optimization methods

The aim of the paper is to present and substantiate a technique to visualize DEA modelling results without any loss of mathematical rigour. The proposed family of parametric optimization methods allows one to construct an intersection of the multidimensional frontier with a two-dimensional plane determined by any pair of given directions. This approach reduces the efficiency analysis of production units to the investigation of well-known functions in economics. We also propose constructive methods to calculate marginal rates of substitution, marginal rates of transformation and so on.     

Exact penalty functions and calmness for mathematical programming under nonlinear perturbations

In the present paper, the effects of nonlinear perturbations of constraint systems are considered over the relationship between calmness and exact penalization, within the context of mathematical programming with equilibrium constraints. Two counterexamples are provided showing that the crucial link between the existence of penalty functions and the property of calmness for perturbed problems is broken in the presence of general perturbations. Then, some properties from variational analysis are singled out, which are able to restore to a certain extent the broken link. Consequently, conditions on the value function associated to perturbed optimization problems are investigated in order to guarantee the occurrence of the above properties.     

A property of convex piecewise linear functions with applications to mathematical programming

Summary It is proved a lemma on convex piecewise linear functions and there are given some applications of this result to non-linear and parametric programming.

---

Zusammenfassung Es wird ein Hilfssatz über konvexe stückweise lineare Funktionen bewiesen und einige Anwendungen des erlangten Ergebnisses bei nichtlinearer und parametrischer Programmierung werden gegeben.

---

---

Vorgel. v.:H. P. Künzi     

Bifurcations in parametric nonlinear programming

Bifurcation and continuation techniques are introduced as a class of methods for investigating the parametric nonlinear programming problem. Motivated by the Fritz John first-order necessary conditions, the parametric programming problem is first reformulated as a closed system of nonlinear equations which contains all Karush-Kuhn-Tucker and Fritz John points, both feasible and infeasible solutions, and relative minima, maxima, and saddle points. Since changes in the structure of the solution set and critical point type can occur only at singularities, necessary and sufficient conditions for the existence of a singularity are developed in terms of the loss of a complementarity condition, the linear dependence constraint qualification, and the singularity of the Hessian of the Lagrangian on a tangent space. After a brief introduction to elementary bifurcation theory, some simple singularities in this parametric problem are analyzed for both branching and persistence of local minima. Finally, a brief introduction to numerical continuation and bifurcation procedures is given to indicate how these facts can be used in a numerical investigation of the problem.This research was supported by the Air force Office of Scientific Research through grant number AFOSR-88-0059.     

On parametric nonlinear programming

In this tutorial survey we study finite dimensional optimization problems which depend on parameters. It is our aim to work out several basic connections with different mathematical areas. In particular, attention will be paid to unfolding and singularity theory, structural analysis of families of constraint sets, constrained optimization problems and semi-infinite optimization.     

Stable parametric programming *

Stable parametric programs (abbreviation: SPP) are parametric programs with a

particular continuity (stability) requirement. Optimal solutions of SPP are paths in the space of “parameters” (inputs, data) that preserve continuity of the feasible set point-to set mapping in the space of “decision variables”. The end points of these paths optimize the optimal value function on a region of stability

In this paper we study only convex SPP. First we study optimality conditions. If the constraints enjoy the locally-flat-surface (“LFS”) property in the decision variable component, then the usual separation arguments apply and we can characterize local and global optimal solutions. Then we consider a well-known marginal value formula for the optimal value function. We prove the formula under new assumptions and then use it to modify a class of quasi-Newton methods in order to solve convex SPP. Finally, several solved case are reported     

Potential-reduction methods in mathematical programming

We provide a survey of interior-point methods for linear programming and its extensions that are based on reducing a suitable potential function at each iteration. We give a fairly complete overview of potential-reduction methods for linear programming, focusing on the possibility of taking long steps and the properties of the barrier function that are necessary for the analysis. We then describe briefly how the methods and results can be extended to certain convex programming problems, following the approach of Nesterov and Todd. We conclude with some open problems. Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550. Some of this work was done while the author was on a sabbatical leave from Cornell University visiting the Department of Mathematics at the University of Washington.     

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.