Connectedness of the Efficient Set for Strictly Quasiconcave Sets

Given a closed subset X in , we show the connectedness of its efficient points or nondominated points when X is sequentially strictly quasiconcave. In the particular case of a maximization problem with n continuous and strictly quasiconcave objective functions on a compact convex feasible region of , we deduce the connectedness of the efficient frontier of the problem. This work solves the open problem of the efficient frontier for strictly quasiconcave vector maximization problems.     

Connectedness of the Efficient Set for Three-Objective Quasiconcave Maximization Problems

For three-objective maximization problems involving continuous, semistrictly quasiconcave functions over a compact convex set, it is shown that the set of efficient solutions is connected. With that, an open problem stated by Choo, Schaible, and Chew in 1985 is solved.     

锥有效拟凹集的有效点集的连通性

本文引进了锥有效拟凹集的概念，讨论了R ^m-严格拟凹与R ^m－有效拟凹的关系，证明了一个紧集为锥有效拟凹且其有效点集为闭集时，这个有效点集是连通的。     

Optimization over Spaces of Discontinuous 2D Functions

The existence of solution for optimization problems over a space of discontinuous 2D functions is addressed. The main result relies on the choice of a suitable topology making the feasible set compact. Application to image segmentation and/or identification problems is considered and robustness of the solution is discussed.     

On a class of quadratic programs

This paper considers a class of quadratic programs where the constraints ae linear and the objective is a product of two linear functions. Assuming the two linear factors to be non-negative, maximization and minimization cases are considered. Each case is analyzed with the help of a bicriteria linear program obtained by replacing the quadratic objective with the two linear functions. Global minimum (maximum) is attained at an efficient extreme point (efficient point) of the feasible set in the solution space and corresponds to an efficient extreme point (efficient point) of the feasible set in the bicriteria space. Utilizing this fact and certain other properties, two finite algorithms, including validations are given for solving the respective problems. Each of these, essentially, consists of solving a sequence of linear programs. Finally, a method is provided for relaxing the non-negativity assumption on the two linear factors of the objective function.     

Bilevel problems over polyhedra with extreme point optimal solutions

Bilevel programming involves two optimization problems where the constraint region of the upper level problem is implicitly determined by another optimization problem. In this paper we focus on bilevel problems over polyhedra with upper level constraints involving lower level variables. On the one hand, under the uniqueness of the optimal solution of the lower level problem, we prove that the fact that the objective functions of both levels are quasiconcave characterizes the property of the existence of an extreme point of the polyhedron defined by the whole set of constraints which is an optimal solution of the bilevel problem. An example is used to show that this property is in general violated if the optimal solution of the lower level problem is not unique. On the other hand, if the lower level objective function is not quasiconcave but convex quadratic, assuming the optimistic approach we prove that the optimal solution is attained at an extreme point of an ??enlarged?? polyhedron.     

On the construction of test problems for concave minimization algorithms

We construct some classes of test problems of minimizing a concave or, more general, quasiconcave function over a polyhedral set. These test problems fulfil the general requirement that they have a global solution at a known point which is suitably chosen on the boundary of the feasible set.     

带约束条件集值优化问题近似Henig有效解集的连通性

研究了带约束条件集值优化问题近似Henig有效解集的连通性.在实局部凸Hausdorff空间中,讨论了可行域为弧连通紧的,目标函数为C-弧连通的条件下,带约束条件集值优化问题近似Henig有效解集的存在性和连通性.并给出了带约束条件集值优化问题近似Henig有效解集的连通性定理.     

On the Quasiconcave Bilevel Programming Problem

Bilevel programming involves two optimization problems where the constraint region of the first-level problem is implicitly determined by another optimization problem. In this paper, we consider the case in which both objective functions are quasiconcave and the constraint region common to both levels is a polyhedron. First, it is proved that this problem is equivalent to minimizing a quasiconcave function over a feasible region comprised of connected faces of the polyhedron. Consequently, there is an extreme point of the polyhedron that solves the problem. Finally, it is shown that this model includes the most important case where the objective functions are ratios of concave and convex functions     

Stability and Scalarization of Weak Efficient, Efficient and Henig Proper Efficient Sets Using Generalized Quasiconvexities

The aim of this paper is to establish the stability of weak efficient, efficient and Henig proper efficient sets of a vector optimization problem, using quasiconvex and related functions. We establish the Kuratowski?CPainlevé set-convergence of the minimal solution sets of a family of perturbed problems to the corresponding minimal solution set of the vector problem, where the perturbations are performed on both the objective function and the feasible set. This convergence is established by using gamma convergence of the sequence of the perturbed objective functions and Kuratowski?CPainlevé set-convergence of the sequence of the perturbed feasible sets. The solution sets of the vector problem are characterized in terms of the solution sets of a scalar problem, where the scalarization function satisfies order preserving and order representing properties. This characterization is further used to establish the Kuratowski?CPainlevé set-convergence of the solution sets of a family of scalarized problems to the solution sets of the vector problem.     

Connectedness of the efficient set in strictly quasiconcave vector maximization

In this paper, the concepts of quasiconcave set and strictly quasiconcave set are introduced. By using these concepts, we get a new sufficient condition for the efficient outcome set to be connected. This leads to the connectedness of the efficient solution set in strictly quasiconcave vector maximization under the mild condition that the efficient frontier is closed.The authors would like to thank Professor E. U. Choo and the referees for their many valuable comments and helpful suggestions.     

New results on a class of exact augmented Lagrangians

In this paper, a new continuously differentiable exact augmented Lagrangian is introduced for the solution of nonlinear programming problems with compact feasible set. The distinguishing features of this augmented Lagrangian are that it is radially unbounded with respect to the multiplier and that it goes to infinity on the boundary of a compact set containing the feasible region. This allows one to establish a complete equivalence between the unconstrained minimization of the augmented Lagrangian on the product space of problem variables and multipliers and the solution of the constrained problem.The author wishes to thank Dr. L. Grippo for having suggested the topic of this paper and for helpful discussions.     

Contractibility of the Efficient Frontier of Three-Dimensional Simply-Shaded Sets

The aim of this paper is to study the geometrical and topological structure of the efficient frontier of simply-shaded sets in a three-dimensional Euclidean space with respect to the usual positive cone. Our main result concerns the contractibility of the efficient frontier and refines a recent result of Daniilidis, Hadjisavvas, and Schaible (Ref. 1) regarding the connectedness of the efficient outcome set for three-criteria optimization problems involving continuous semistrictly quasiconcave objective functions.     

Robust optimization revisited via robust vector Farkas lemmas

This paper provides characterizations of the weakly minimal elements of vector optimization problems and the global minima of scalar optimization problems posed on locally convex spaces whose objective functions are deterministic while the uncertain constraints are treated under the robust (or risk-averse) approach, i.e. requiring the feasibility of the decisions to be taken for any possible scenario. To get these optimality conditions we provide Farkas-type results characterizing the inclusion of the robust feasible set into the solution set of some system involving the objective function and possibly uncertain parameters. In the particular case of scalar convex optimization problems, we characterize the optimality conditions in terms of the convexity and closedness of an associated set regarding a suitable point.     

A graphical characterization of the efficient set for?convex multiobjective problems

In this paper, a graphical characterization, in the decision space, of the properly efficient solutions of a convex multiobjective problem is derived. This characterization takes into account the relative position of the gradients of the objective functions and the active constraints at the given feasible solution. The unconstrained case with two objective functions and with any number of functions and the general constrained case are studied separately. In some cases, these results can provide a visualization of the efficient set, for problems with two or three variables. Besides, a proper efficiency test for general convex multiobjective problems is derived, which consists of solving a single linear optimization problem.     

Solving linear fractional bilevel programs

In this paper, we prove that an optimal solution to the linear fractional bilevel programming problem occurs at a boundary feasible extreme point. Hence, the Kth-best algorithm can be proposed to solve the problem. This property also applies to quasiconcave bilevel problems provided that the first level objective function is explicitly quasimonotonic.     

Computational Study of the Relationships Between Feasible and Efficient Sets and an Approximation

The computational difficulty of obtaining the efficient set in multi-objective programming, specially in nonlinear problems, suggest the need of considering an approximation approach to this problem. In this paper, we provide the computational results of the relationships between an approximation to the efficient set and the feasible and efficient sets. Random problem generation is considered for different sizes of the feasible set and we study the implications with respect to the number of objective functions and various kinds of objective functions. Computational experience with this approximation suggests that we obtain a substantial improvement when it increases the number of objective functions.     

Successive approximation technique for a class of large-scale NLP problems and its application to dynamic programming

In this paper, two successive approximation techniques are presented for a class of large-scale nonlinear programming problems with decomposable constraints and a class of high-dimensional discrete optimal control problems, respectively. It is shown that: (a) the accumulation point of the sequence produced by the first method is a Kuhn-Tucker point if the constraint functions are decomposable and if the uniqueness condition holds; (b) the sequence converges to an optimum solution if the objective function is strictly pseudoconvex and if the constraint functions are decomposable and quasiconcave; and (c) similar conclusions for the second method hold also for a class of discrete optimal control problems under some assumptions.     

VI-constrained hemivariational inequalities: distributed algorithms and power control in ad-hoc networks

We consider centralized and distributed algorithms for the numerical solution of a hemivariational inequality (HVI) where the feasible set is given by the intersection of a closed convex set with the solution set of a lower-level monotone variational inequality (VI). The algorithms consist of a main loop wherein a sequence of one-level, strongly monotone HVIs are solved that involve the penalization of the non-VI constraint and a combination of proximal and Tikhonov regularization to handle the lower-level VI constraints. Minimization problems, possibly with nonconvex objective functions, over implicitly defined VI constraints are discussed in detail. The methods developed in the paper are then used to successfully solve a new power control problem in ad-hoc networks.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.