共查询到20条相似文献,搜索用时 15 毫秒
1.
Convexity and concavity properties of the optimal value function in parametric nonlinear programming 总被引:1,自引:0,他引:1
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. 相似文献
2.
Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective valuez
*. These new methods combine the approach of Goldfarb and Mehrotra for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds forz
* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402, and ONR Contract N0014-87-K0214. 相似文献
3.
In this paper we consider generalized convexity and concavity properties of the optimal value functionf
* for the general parametric optimization problemP(ε) of the form min
x
f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off
* were presented by the authors in a previous paper. 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.
We give sufficient conditions for several types of generalized convexity and concavity off
*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided.
Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research. 相似文献
4.
Alexander Shapiro 《Mathematical Programming》1995,70(1-3):149-157
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. 相似文献
5.
Alireza Ghaffari-Hadigheh Habib Ghaffari-Hadigheh Tamás Terlaky 《Central European Journal of Operations Research》2008,16(2):215-238
In bi-parametric linear optimization (LO), perturbation occurs in both the right-hand-side and the objective function data
with different parameters. In this paper, the bi-parametric LO problem is considered and we are interested in identifying
the regions where the optimal partitions are invariant. These regions are referred to as invariancy regions. It is proved
that invariancy regions are separated by vertical and horizontal lines and generate a mesh-like area. It is proved that the
boundaries of these regions can be identified in polynomial time. The behavior of the optimal value function on these regions
is investigated too. 相似文献
6.
J. H. Dulá 《Journal of Optimization Theory and Applications》1994,81(1):35-52
In 1967, Wets and Witzgall (Ref. 1) made, in passing, a connection between frames of polyhedral cones and redundancy in linear programming. The present work elaborates and formalizes the theoretical details needed to establish this relation. We study the properties of optimal value functions in order to derive the correspondence between problems in redundancy and the frame of a polyhedral cone. The insights obtained lead to schemes to improve the efficiency of procedures to detect redundancy in the areas of linear programming, stochastic programming, and computational geometry.The author is indebted to G. Dewan for his review and discussions. 相似文献
7.
Conditions for the uniqueness of the optimal solution in linear semi-infinite programming 总被引:1,自引:0,他引:1
In this paper, we establish different conditions for the uniqueness of the optimal solution of a semi-infinite programming problem. The approach here is based on the differentiability properties of the optimal value function and yields the corresponding extensions to the general linear semi-infinite case of many results provided by Mangasarian and others. In addition, detailed optimality conditions for the most general problem are supplied, and some features of the optimal set mapping are discussed. Finally, we obtain a dimensional characterization of the optimal set, provided that a usual closedness condition (Farkas-Minkowski condition) holds. 相似文献
8.
When all the involved data in indefinite quadratic programs change simultaneously,we show the locally Lipschtiz continuity of the KKT set of the quadratic programming problem firstly, then we establish the locally Lipschtiz continuity of the KKT solution set. Finally, the similar conclusion for the corresponding optimal value function is obtained. 相似文献
9.
Okitsugu Fujiwara 《Operations Research Letters》1984,3(4):219-224
We consider a parametrized family of nonlinear programs where the feasible region is defined by equality constraints in a ball. The global optimal value is shown to be twice continuously differentiable over an open and dense set in the perturbation parameter space. 相似文献
10.
Parametric analysis in linear fractional programming is significantly more complicated in case of an unbounded feasible region. We propose procedures which are based on a modified version of Martos' algorithm or a modification of Charnes-Cooper's algorithm, applying each to problems where either the objective function or the right-hand side is parametrized. 相似文献
11.
J. B. Lasserre 《Journal of Optimization Theory and Applications》1981,34(2):197-205
In this paper, we present a property of certain linear multistage problems. To solve them, a method which takes this property into account is presented. It requires the resolution of 2N–1 subproblems, if there areN stages in the original problem. A sufficient condition is given on the matrix of the constraints for the property to be true. When only a submatrix has this property, we propose to use the Dantzig-Wolfe decomposition principle. We then can solve the subproblem with the proposed method. Applications to linear and nonlinear programming are presented.This work was done while the author was Visiting Scholar at the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California. 相似文献
12.
Designing a majorization scheme for the recourse function in two-stage stochastic linear programming
José H. Dulá 《Computational Optimization and Applications》1993,1(4):399-414
We discuss issues pertaining to the domination from above of the second-stage recourse function of a stochastic linear program and we present a scheme to majorize this function using a simpler sublinear function. This majorization is constructed using special geometrical attributes of the recourse function. The result is a proper, simplicial function with a simple characterization which is well-suited for calculations of its expectation as required in the computation of stochastic programs. Experiments indicate that the majorizing function is well-behaved and stable. 相似文献
13.
R.K Ahuja 《Operations Research Letters》1985,4(3):131-134
In this paper, we consider the following minimax linear programming problem: min z = max1 ≤ j ≤ n{CjXj}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem. 相似文献
14.
On characterizing the solution sets of pseudolinear programs 总被引:8,自引:0,他引:8
This paper provides several new and simple characterizations of the solution sets of pseudolinear programs. By means of the basic properties of pseudolinearity, the solution set of a pseudolinear program is characterized, for instance, by the equality that
, for each feasible pointx, where
is in the solution set. As a consequence, we give characterizations of both the solution set and the boundedness of the solution set of a linear fractional program. 相似文献
15.
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. 相似文献
16.
ABSTRACTThe aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization. 相似文献
17.
《Optimization》2012,61(2):123-130
We study the lower semicontinuity of the optimal solution set of a parametric optimization problem. Our results sharpen the main results of Zhao (1997, The lower semicontinuity of optimal solution sets. Journal of Mathematical Analysis and Applications, 207, 240–254. Ref. ). Namely, it is shown that the conclusion of Theorem 1 of is still valid under weaker assumptions, and the conditions on “ε-nontriviality” and uniform continuity of the objective function in Theorems 2 and 3 of can be omitted. 相似文献
18.
We study the set of points of nondifferentiability, called the singular set, of the value function of a Bolza optimal control problem. The value function is a viscosity solution to an associated Hamilton-Jacobi equation. The method of characteristics associates to this equation a Hamiltonian system, that in turn can be used to study the propagation of singularities of the value function. In particular, we obtain an extension of the Rankine-Hugoniot type condition, which is well-known in the conservation law theory. 相似文献
19.
M. C. Ferris 《Journal of Optimization Theory and Applications》1990,65(1):53-65
An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper. 相似文献
20.
A penalty function approach for solving bi-level linear programs 总被引:8,自引:0,他引:8
The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems. 相似文献