Optimality conditions in optimization problems with convex feasible set using convexificators

In this paper, we consider a nonsmooth optimization problem with a convex feasible set described by constraint functions which are neither convex nor differentiable nor locally Lipschitz necessarily. Utilizing upper regular convexificators, we characterize the normal cone of the feasible set and derive KKT type necessary and sufficient optimality conditions. Under some assumptions, we show that the set of KKT multipliers is bounded. We also characterize the set of optimal solutions and introduce a linear approximation corresponding to the original problem which is useful in checking optimality. The obtained outcomes extend various results existing in the literature to a more general setting.     

Nonsmooth Multiobjective Problems and Generalized Vector Variational Inequalities Using Quasi-Efficiency

In this paper, a multiobjective problem with a feasible set defined by inequality, equality and set constraints is considered, where the objective and constraint functions are locally Lipschitz. Here, a generalized Stampacchia vector variational inequality is formulated as a tool to characterize quasi- or weak quasi-efficient points. By using two new classes of generalized convexity functions, under suitable constraint qualifications, the equivalence between Kuhn–Tucker vector critical points, solutions to the multiobjective problem and solutions to the generalized Stampacchia vector variational inequality in both weak and strong forms will be proved.     

Weighting factor results in vector optimization

This paper deals with the study, in a convex vector optimization problem, of the set of efficient solutions and the set of properly efficient solutions, the latter being obtained by a weighting factor technique. Relationships between these two sets are discussed; they are shown to be nonempty when the objective functions have no common direction of recession and to be closed and equal when, moreover, the objective functions are locally polyhedral. An example is provided where the set of efficient solutions is not included in the closure of the nonempty set of properly efficient solutions.The author wishes to thank the unknown referee for the helpful comments that improved the quality of this paper.     

Extremal values of global tolerances in combinatorial optimization with an additive objective function

The currently adopted notion of a tolerance in combinatorial optimization is defined referring to an arbitrarily chosen optimal solution, i.e., locally. In this paper we introduce global tolerances with respect to the set of all optimal solutions, and show that the assumption of nonembededdness of the set of feasible solutions in the provided relations between the extremal values of upper and lower global tolerances can be relaxed. The equality between globally and locally defined tolerances provides a new criterion for the multiplicity (uniqueness) of the set of optimal solutions to the problem under consideration.     

A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search

Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities.     

Some equivalent problems in set optimization

Given a set-valued optimization problem (P), there is more than one way of defining the solutions associated with it. Depending on the decision maker’s preference, we consider the vector criterion or the set criterion. Both criteria of solution are considered together to solve problem (P) by reducing the feasible set.     

Global tolerances in the problems of combinatorial optimization with an additive objective function

It is known that by means of minimal values of tolerances one can obtain necessary and sufficient conditions for the uniqueness of the optimal solution of a combinatorial optimization problem (COP) with an additive objective function and the set of nonembedded feasible solutions. Moreover, the notion of a tolerance is defined locally, i.e., with respect to a chosen optimal solution. In this paper we introduce the notion of a global tolerance with respect to the whole set of optimal solutions and prove that the nonembeddedness assumption on the set of feasible solutions of the COP can be relaxed, which generalizes the well known relations for the extremal values of the tolerances. In particular, we formulate a new criterion for the uniqueness of the optimal solution of the COP with an additive objective function, which is based on certain equalities between locally and globally defined tolerances.     

A canonical dual approach for solving linearly constrained quadratic programs

This paper provides a canonical dual approach for minimizing a general quadratic function over a set of linear constraints. We first perturb the feasible domain by a quadratic constraint, and then solve a “restricted” canonical dual program of the perturbed problem at each iteration to generate a sequence of feasible solutions of the original problem. The generated sequence is proven to be convergent to a Karush-Kuhn-Tucker point with a strictly decreasing objective value. Some numerical results are provided to illustrate the proposed approach.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.     

Two level hierarchical time minimizing transportation problem

A two level hierarchical balanced time minimizing transportation problem is considered in this paper. The whole set of source-destination links consists of two disjoint partitions namely Level-I links and Level-II links. Some quantity of a homogeneous product is first shipped from sources to destinations by Level-I decision maker using only Level-I links, and on its completion the Level-II decision maker transports the remaining quantity of the product in an optimal fashion using only Level-II links. Transportation is assumed to be done in parallel in both the levels. The aim is to find that feasible solution for Level-I decision maker corresponding to which the optimal feasible solution for Level-II decision maker is such that the sum of shipment times in Level-I and Level-II is the least. To obtain the global optimal feasible solution of this non-convex optimization problem, related balanced time minimizing transportation problems are defined. Based upon the optimal feasible solutions of these related problems, standard cost minimizing transportation problems are constructed whose optimal feasible solutions provide various pairs for shipment times for Level-I and Level-II decision makers. The best out of these pairs is finally selected. Being dependent upon solutions of a finite number of balanced time minimizing and cost minimizing transportation problems, the proposed algorithm is a polynomial bound algorithm. The developed algorithm has been implemented and tested on a variety of test problems and performance is found to be quite encouraging.     

Minimization of Gerstewitz functionals extending a scalarization by Pascoletti and Serafini

Scalarization in vector optimization is often closely connected to the minimization of Gerstewitz functionals. In this paper, the minimizer sets of Gerstewitz functionals are investigated. Conditions are given under which such a set is nonempty and compact. Interdependencies between solutions of problems with different parameters or with different feasible point sets are shown. Consequences for the parameter control in scalarization methods are proved. It is pointed out that the minimization of Gerstewitz functionals is equivalent to an optimization problem which generalizes the scalarization by Pascoletti and Serafini. The results contain statements about minimizers of certain Minkowski functionals and norms. Some existence results for solutions of vector optimization problems are derived.     

Inverse multi-objective combinatorial optimization

Inverse multi-objective combinatorial optimization consists of finding a minimal adjustment of the objective functions coefficients such that a given set of feasible solutions becomes efficient. An algorithm is proposed for rendering a given feasible solution into an efficient one. This is a simplified version of the inverse problem when the cardinality of the set is equal to one. The adjustment is measured by the Chebyshev distance. It is shown how to build an optimal adjustment in linear time based on this distance, and why it is right to perform a binary search for determining the optimal distance. These results led us to develop an approach based on the resolution of mixed-integer linear programs. A second approach based on a branch-and-bound is proposed to handle any distance function that can be linearized. Finally, the initial inverse problem is solved by a cutting plane algorithm.     

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

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

Portfolio optimization with an envelope-based multi-objective evolutionary algorithm

The problem of portfolio selection is a standard problem in financial engineering and has received a lot of attention in recent decades. Classical mean–variance portfolio selection aims at simultaneously maximizing the expected return of the portfolio and minimizing portfolio variance. In the case of linear constraints, the problem can be solved efficiently by parametric quadratic programming (i.e., variants of Markowitz’ critical line algorithm). However, there are many real-world constraints that lead to a non-convex search space, e.g., cardinality constraints which limit the number of different assets in a portfolio, or minimum buy-in thresholds. As a consequence, the efficient approaches for the convex problem can no longer be applied, and new solutions are needed.In this paper, we propose to integrate an active set algorithm optimized for portfolio selection into a multi-objective evolutionary algorithm (MOEA). The idea is to let the MOEA come up with some convex subsets of the set of all feasible portfolios, solve a critical line algorithm for each subset, and then merge the partial solutions to form the solution of the original non-convex problem. We show that the resulting envelope-based MOEA significantly outperforms existing MOEAs.     

Levitin–Polyak well-posedness for constrained quasiconvex vector optimization problems

In this paper, a notion of Levitin–Polyak (LP in short) well-posedness is introduced for a vector optimization problem in terms of minimizing sequences and efficient solutions. Sufficient conditions for the LP well-posedness are studied under the assumptions of compactness of the feasible set, closedness of the set of minimal solutions and continuity of the objective function. The continuity assumption is then weakened to cone lower semicontinuity for vector-valued functions. A notion of LP minimizing sequence of sets is studied to establish another set of sufficient conditions for the LP well-posedness of the vector problem. For a quasiconvex vector optimization problem, sufficient conditions are obtained by weakening the compactness of the feasible set to a certain level-boundedness condition. This in turn leads to the equivalence of LP well-posedness and compactness of the set of efficient solutions. Some characterizations of LP well-posedness are given in terms of the upper Hausdorff convergence of the sequence of sets of approximate efficient solutions and the upper semicontinuity of an approximate efficient map by assuming the compactness of the set of efficient solutions, even when the objective function is not necessarily quasiconvex. Finally, a characterization of LP well-posedness in terms of the closedness of the approximate efficient map is provided by assuming the compactness of the feasible set.     

A general method for solving constrained optimization problems

In this paper a general problem of constrained minimization is studied. The minima are determined by searching for the asymptotical values of the solutions of a suitable system of ordinary differential equations.For this system, if the initial point is feasible, then any trajectory is always inside the set of constraints and tends towards a set of critical points. Each critical point that is not a relative minimum is unstable. For formulas of one-step numerical integration, an estimate of the step of integration is given, so that the above mentioned qualitative properties of the system of ordinary differential equations are kept.     

集值优化问题超有效解的Lagrange最优性条件

在局部凸空间中考虑约束集值优化问题（VP）在超有效解意义下的Lagrange最优性条件．在近似锥-次类凸假设下，利用择一性定理得到了（VP）取得强有效解的必要条件，利用超有效解集的性质及超有效解的定义给出了（VP）取得超有效解的充分条件，最后给出了一种与（VP）等价的无约束规划．     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

Semivectorial Bilevel Optimization Problem: Penalty Approach

We consider a bilevel optimization problem where the upper level is a scalar optimization problem and the lower level is a vector optimization problem. For the lower level, we deal with weakly efficient solutions. We approach our problem using a suitable penalty function which vanishes over the weakly efficient solutions of the lower-level vector optimization problem and which is nonnegative over its feasible set. Then, we use an exterior penalty method.Communicated by H. P. Benson(Formerly Serban Bolintinéanu) Professor, University of New Caledonia, ERIM, Nouméa, New Caledonia. This author thanks the University of Naples Federico II for its support and the Department of Mathematics and Statistics for its hospitality.     

Connectedness of the sets of weak efficient solutions for generalized vector equilibrium problems

In this paper, a generalized vector equilibrium problem is introduced and studied. A scalar characterization of weak efficient solutions for the generalized vector equilibrium problem is obtained. By using the scalarization result, the existence of the weak efficient solutions and the connectedness of the set of weak efficient solutions for the generalized vector equilibrium problem are proved in locally convex spaces.