A vector variational inequality and optimization over an efficient set

Some relations are obtained between weak vector minimization, a vector variational inequality, and the optimization of a utility function over a set of efficient points.

---

Zusammenfassung Es werden einige Beziehungen über schwache Vektorminimierung, einer vektoriellen Variationsgleichung und der Optimierung einer Nutzenfunktion über einer Menge effizienter Punkte hergeleitet.

     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

A new hybrid method for solving global optimization problem

In this paper we present a new hybrid method, called the SASP method. The purpose of this method is the hybridization of the simulated annealing (SA) with the descent method, where we estimate the gradient using simultaneous perturbation. Firstly, the new hybrid method finds a local minimum using the descent method, then SA is executed in order to escape from the currently discovered local minimum to a better one, from which the descent method restarts a new local search, and so on until convergence.The new hybrid method can be widely applied to a class of global optimization problems for continuous functions with constraints. Experiments on 30 benchmark functions, including high dimensional functions, show that the new method is able to find near optimal solutions efficiently. In addition, its performance as a viable optimization method is demonstrated by comparing it with other existing algorithms. Numerical results improve the robustness and efficiency of the method presented.     

A global optimization approach for solving the convex multiplicative programming problem

We consider a convex multiplicative programming problem of the form% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaGG7bGaam% OzamaaBaaaleaacaaIXaaabeaakiaacIcacaWG4bGaaiykaiabgwSi% xlaadAgadaWgaaWcbaGaaGOmaaqabaGccaGGOaGaamiEaiaacMcaca% GG6aGaamiEaiabgIGiolaadIfacaGG9baaaa!4A08!\[\{ f_1 (x) \cdot f_2 (x):x \in X\} \]where X is a compact convex set of ⁿ and f ₁, f ₂ are convex functions which have nonnegative values over X.Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the (n+2) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in ² ₂. This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm is finite when the functions f _i, (i=1, 2) are affine-linear and X is a polytope and it is convergent for the general convex case.Partly supported by the Deutsche Forschungsgemeinschaft Project CONMIN.     

Z-eigenvalue methods for a global polynomial optimization problem

As a global polynomial optimization problem, the best rank-one approximation to higher order tensors has extensive engineering and statistical applications. Different from traditional optimization solution methods, in this paper, we propose some Z-eigenvalue methods for solving this problem. We first propose a direct Z-eigenvalue method for this problem when the dimension is two. In multidimensional case, by a conventional descent optimization method, we may find a local minimizer of this problem. Then, by using orthogonal transformations, we convert the underlying supersymmetric tensor to a pseudo-canonical form, which has the same E-eigenvalues and some zero entries. Based upon these, we propose a direct orthogonal transformation Z-eigenvalue method for this problem in the case of order three and dimension three. In the case of order three and higher dimension, we propose a heuristic orthogonal transformation Z-eigenvalue method by improving the local minimum with the lower-dimensional Z-eigenvalue methods, and a heuristic cross-hill Z-eigenvalue method by using the two-dimensional Z-eigenvalue method to find more local minimizers. Numerical experiments show that our methods are efficient and promising. This work is supported by the Research Grant Council of Hong Kong and the Natural Science Foundation of China (Grant No. 10771120).     

Balancing global and local search in parallel efficient global optimization algorithms

Most parallel efficient global optimization (EGO) algorithms focus only on the parallel architectures for producing multiple updating points, but give few attention to the balance between the global search (i.e., sampling in different areas of the search space) and local search (i.e., sampling more intensely in one promising area of the search space) of the updating points. In this study, a novel approach is proposed to apply this idea to further accelerate the search of parallel EGO algorithms. In each cycle of the proposed algorithm, all local maxima of expected improvement (EI) function are identified by a multi-modal optimization algorithm. Then the local EI maxima with value greater than a threshold are selected and candidates are sampled around these selected EI maxima. The results of numerical experiments show that, although the proposed parallel EGO algorithm needs more evaluations to find the optimum compared to the standard EGO algorithm, it is able to reduce the optimization cycles. Moreover, the proposed parallel EGO algorithm gains better results in terms of both number of cycles and evaluations compared to a state-of-the-art parallel EGO algorithm over six test problems.     

线性半向量二层规划问题的全局优化方法

研究了线性半向量二层规划问题的全局优化方法. 利用下层问题的对偶间隙构造了线性半向量二层规划问题的罚问题, 通过分析原问题的最优解与罚问题可行域顶点之间的关系, 将线性半向量二层规划问题转化为有限个线性规划问题, 从而得到线性半向量二层规划问题的全局最优解. 数值结果表明所设计的全局优化方法对线性半向量二层规划问题是可行的.     

The minimal criterion for the equivalence between local and global optimal solutions in nondifferentiable optimization problem

In the paper, a necessary and sufficient criterion it provided such that any local optimal solution is also global in a not necessarily differentiable constrained optimization problem. This criterion is compared to others earlier appeared in the literature, which are sufficient but not necessary for a local optimal solution to be global. The importance of the established criterion is illustrated by suitable examples of nonconvex optimization problems presented in the paper.     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

Problems with resource allocation constraints and optimization over the efficient set

The paper studies a nonlinear optimization problem under resource allocation constraints. Using quasi-gradient duality it is shown that the feasible set of the problem is a singleton (in the case of a single resource) or the set of Pareto efficient solutions of an associated vector maximization problem (in the case of $k>1$ resources). As a result, a nonlinear optimization problem under resource allocation constraints reduces to an optimization over the efficient set. The latter problem can further be converted into a quasiconvex maximization over a compact convex subset of $\mathbb{R }^k_+.$ Alternatively, it can be approached as a bilevel program and converted into a monotonic optimization problem in $\mathbb{R }^k_+.$ In either approach the converted problem falls into a common class of global optimization problems for which several practical solution methods exist when the number $k$ of resources is relatively small, as it often occurs.     

A global optimization algorithm for solving the minimum multiple ratio spanning tree problem

This paper studies the sum-of-ratios version of the classical minimum spanning tree problem. We describe a branch-and-bound algorithm for solving the general version of the problem based on its image space representation. The suggested approach specifically addresses the difficulties arising in the case when the number of ratios exceeds two. The efficacy of our approach is demonstrated on randomly generated complete and sparse graph instances.     

Mathematical modeling and efficient optimization methods for the distance-dependent rearrangement clustering problem

In this article we present a computational study for solving the distance-dependent rearrangement clustering problem using mixed-integer linear programming (MILP). To address sparse data sets, we present an objective function for evaluating the pair-wise interactions between two elements as a function of the distance between them in the final ordering. The physical permutations of the rows and columns of the data matrix can be modeled using mixed-integer linear programming and we present three models based on (1) the relative ordering of elements, (2) the assignment of elements to a final position, and (3) the assignment of a distance between a pair of elements. These models can be augmented with the use of cutting planes and heuristic methods to increase computational efficiency. The performance of the models is compared for three distinct re-ordering problems corresponding to glass transition temperature data for polymers and two drug inhibition data matrices. The results of the comparative study suggest that the assignment model is the most effective for identifying the optimal re-ordering of rows and columns of sparse data matrices.     

Ant colony optimization for solving an industrial layout problem

This paper presents ACO_GLS, a hybrid ant colony optimization approach coupled with a guided local search, applied to a layout problem. ACO_GLS is applied to an industrial case, in a train maintenance facility of the French railway system (SNCF). Results show that an improvement of near 20% is achieved with respect to the actual layout. Since the problem is modeled as a quadratic assignment problem (QAP), we compared our approach with some of the best heuristics available for this problem. Experimental results show that ACO_GLS performs better for small instances, while its performance is still satisfactory for large instances.     

An efficient method for solving an inverse problem for the Richards equation

A parameter identification problem for the hydraulic properties of porous media is considered. Numerically, this inverse problem is solved by minimizing an output least-squares functional. The unknown hydraulic properties which are nonlinear coefficients of a partial differential equation are approximated by spline functions. The identification is embedded into a multi-level algorithm and coupled with a linear sensitivity analysis to describe the ill-posedness of the inverse problem.     

Bounding the set of solutions of a perturbed global optimization problem

Consider a global optimization problem in which the objective function and/or the constraints are expressed in terms of parameters. Suppose we wish to know the set of global solutions as the parameters vary over given intervals. In this paper we discuss procedures using interval analysis for computing guaranteed bounds on the solution set. This provides a means for doing a sensitivity analysis or simply bounding the effect of errors in data.     

A finite,nonadjacent extreme-point search algorithm for optimization over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.The author owes thanks to two anonymous referees for their helpful comments.     

Optimization over the efficient set

This paper deals with the problem of maximizing a function over the efficient set of a linear multiple objective program. The approach is to formulate a biobjective program with an appropriate efficient set. The penalty function approach is motivated by an auxiliary problem due to Benson.     

Outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem

This article presents a finite, outcome-based algorithm for optimizing a lower semicontinuous function over the efficient set of a bicriteria linear programming problem. The algorithm searches the efficient faces of the outcome set of the bicriteria linear programming problem. It exploits the fact that the dimension of the outcome set of the bicriteria problem is at most two. As a result, in comparison to decisionbased approaches, the number of efficient faces that need to be found is markedly reduced. Furthermore, the dimensions of the efficient faces found are always at most one. The algorithm can be implemented for a wide variety of lower semicontinuous objective functions.     

Optimizing a linear function over an efficient set

The problem (P) of optimizing a linear functiond ^T x over the efficient set for a multiple-objective linear program (M) is difficult because the efficient set is typically nonconvex. Given the objective function directiond and the set of domination directionsD, ifd ^T 0 for all nonzero D, then a technique for finding an optimal solution of (P) is presented in Section 2. Otherwise, given a current efficient point , if there is no adjacent efficient edge yielding an increase ind ^T x, then a cutting plane is used to obtain a multiple-objective linear program ( ) with a reduced feasible set and an efficient set . To find a better efficient point, we solve the problem (I_i) of maximizingc _i ^T x over the reduced feasible set in ( ) sequentially fori. If there is a that is an optimal solution of (I_i) for somei and , then we can choosex ⁱ as a current efficient point. Pivoting on the reduced feasible set allows us to find a better efficient point or to show that the current efficient point is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.The authors would like to thank an anonymous referee, H. P. Benson, and P. L. Yu for numerous helpful comments on this paper.