Optimization over the efficient set. (English) Zbl 0534.90077

Let \(X\subset {\mathbb{R}}^ n\) be a nonempty set and C a \(k\times n\) matrix. The author considers the vector maximization problem (V) VMAX: Cx subject to \(x\in X\) as a problem of finding all efficient solutions. Here a point \(x^ 0\) is said to be an efficient solution of (V) when \(x^ 0\in X\) and there is no \(x\in X\) such that \(Cx\geq Cx^ 0\) and \(Cx\neq Cx^ 0\). Let \(X_ E\) denote the set of all efficient solutions for the problem (V). Let \(d\in {\mathbb{R}}^ n\). Then the problem (P) of central concern in this paper is given by \(\phi(X_ E)=\sup<d,x>\). subject to \(x\in X_ E\). Necessary and sufficient conditions are given for the problem (P) to be unbounded and for efficient and for arbitrary solutions of problem (V) to be optimal solutions for problem (P). Some of these conditions are geometric in nature, others algebraic. Finally conditions are given under which the set of optimal solutions for the problem (P) possesses certain special properties.
Reviewer: R.Lepp


90C31 Sensitivity, stability, parametric optimization
Full Text: DOI


[1] Benson, H. P., An improved definition of proper efficiency for vector maximization with respect to cones, J. Math. Anal. Appl., 71, 232-241 (1979) · Zbl 0418.90081
[2] Benson, H. P., Efficiency and proper efficiency in vector maximization with respect to cones, J. Math. Anal. Appl., 93, 273-289 (1983) · Zbl 0519.90080
[3] Benson, H. P., Existence of efficient solutions for vector maximization problems, J. Optim. Theory Appl., 26, 569-580 (1978) · Zbl 0373.90085
[4] Benson, H. P., Optimization Over the Efficient Set, (Discussion Paper No. 35 (1981), Center for Econometrics and Decision Sciences, Univ. of Florida: Center for Econometrics and Decision Sciences, Univ. of Florida Gainesville, Fla) · Zbl 0794.90048
[5] Benson, H. P.; Morin, T. L., The vector maximization problem: Proper efficiency and stability, SIAM J. Appl. Math., 32, 64-72 (1977) · Zbl 0357.90059
[6] Bitran, G. R.; Magnanti, T. L., The structure of admissible points with respect to cone dominance, J. Optim. Theory Appl., 29, 573-614 (1979) · Zbl 0389.52021
[7] Borwein, J., Proper efficient points for maximizations with respect to cones, SIAM J. Control Optim., 15, 57-63 (1977) · Zbl 0369.90096
[8] Bragard, L.; Vangeldère, J., Points efficaces en programmation à objectifs multiples, Bull. Soc. Sci. Liège, 46, 27-41 (1977) · Zbl 0365.90124
[9] Dessouky, M. I.; Ghiassi, M.; Davis, W. J., Determining the Worst Value of an Objective Function within the Nondominated Solutions in Multiple Objective Linear Programming (1979), Department of Mechanical and Industrial Engineering, Univ. of Illinois: Department of Mechanical and Industrial Engineering, Univ. of Illinois Urbana, Ill
[10] Ecker, J. G.; Kouada, I. A., Finding all efficient extreme points for multiple objective linear programs, Math. Programming, 14, 249-261 (1978) · Zbl 0385.90105
[11] Ecker, J. G.; Kouada, I. A., Generating Maximal Efficient Faces for Multiple Objective Linear Programs, (Discussion Paper No. 7617 (1976), Center for Operations Research and Econometrics, Université Catholique de Louvain: Center for Operations Research and Econometrics, Université Catholique de Louvain Louvain, Belgium) · Zbl 0393.90087
[12] Epelman, M. S., On a property of polyhedral sets, Math. Programming, 16, 371-373 (1979) · Zbl 0404.52007
[13] Evans, J. P.; Steuer, R. E., A revised simplex method for linear multiple objective programs, Math. Programming, 5, 54-72 (1973) · Zbl 0281.90045
[14] Evans, J. P.; Steuer, R. E., Generating efficient extreme points in linear multiple objective programming: Two algorithms and computing experience, (Cochrane, J. L.; Zeleny, M., Multiple Criteria Decision Making (1973), Univ. of South Carolina Press: Univ. of South Carolina Press Columbia), 349-365
[15] Falk, J. E.; Hoffman, K. R., A successive underestimation method for concave minimization problems, Math. Oper. Res., 1, 251-259 (1976) · Zbl 0362.90082
[16] Gal, T., A general method for determining the set of all efficient solutions to a linear vector-maximum problem, European J. Oper. Res., 1, 307-322 (1977) · Zbl 0374.90044
[17] Gallo, G.; Ülkücü, A., Bilinear programming: An exact algorithm, Math. Programming, 12, 173-194 (1977) · Zbl 0363.90086
[18] Geoffrion, A. M., Proper efficiency and the theory of vector maximization, J. Math. Anal. Appl., 22, 618-630 (1968) · Zbl 0181.22806
[19] Hartley, R., On cone-efficiency, cone-convexity, and cone-compactness, SIAM J. Appl. Math., 34, 211-222 (1978) · Zbl 0379.90005
[20] Henig, M. I., Proper efficiency with respect to cones, J. Optim. Theory Appl., 36, 387-407 (1982) · Zbl 0452.90073
[21] Horst, R., An algorithm for nonconvex programming problems, Math. Programming, 10, 312-321 (1976) · Zbl 0337.90062
[22] Isermann, H., The enumeration of the set of all efficient solutions for a linear multiple objective program, Oper. Res. Quart., 28, 711-725 (1977) · Zbl 0372.90086
[23] Konno, H., A cutting plane algorithm for solving bilinear programs, Math. Programming, 11, 14-27 (1976) · Zbl 0353.90069
[24] Kuhn, H. W.; Tucker, A. W., Nonlinear programming, (Neyman, J., Proceedings, of the Second Berkeley Symposium on Mathematical Statistics and Probability (1950), Univ. of California Press: Univ. of California Press Berkeley), 481-492 · Zbl 0044.05903
[25] McCormick, G. P., Attempts to calculate global solutions of problems that may have local minima, (Lootsma, F. A., Numerical Methods for Nonlinear Optimization (1972), Academic Press: Academic Press New York), 209-221 · Zbl 0276.90049
[26] Naccache, P. H., Connectedness of the set of nondominated outcomes in multicriteria optimization, J. Optim. Theory Appl., 25, 459-467 (1978) · Zbl 0363.90108
[27] Philip, J., Algorithms for the vector maximization problem, Math. Programming, 2, 207-229 (1972) · Zbl 0288.90052
[28] Rockafellar, R. T., Convex Analysis (1970), Princeton Univ. Press: Princeton Univ. Press Princeton, N. J · Zbl 0202.14303
[29] Spivey, W. A.; Thrall, R. M., Linear Optimization (1970), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0224.90003
[30] Stadler, W., A survey of multicriteria optimization or the vector maximum problem, part I: 1776-1960, J. Optim. Theory Appl., 29, 1-52 (1979) · Zbl 0388.90001
[31] Yu, P. L., Cone convexity, cone extreme points, and nondominated solutions in decision problems with multiobjectives, J. Optim. Theory Appl., 14, 319-377 (1974) · Zbl 0268.90057
[32] Yu, P. L.; Zeleny, M., The set of all nondominated solutions in linear cases and a multicriteria simplex method, J. Math. Anal. Appl., 49, 430-468 (1975) · Zbl 0313.65047
[33] Zeleny, M., Linear Multiobjective Programming (1974), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0325.90033
[34] Zwart, P. B., Global maximization of a convex function with linear inequality constraints, Oper. Res., 22, 602-609 (1974) · Zbl 0322.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.