一种改进的GDF多目标优化算法

本文提出一种交互式非线性多目标优化算法，该算法是ＧＤＦ多目标优化算法的改进，具有这样的特点：算法采用了既约设计空间策略，具有良好的收敛性；算法生成的迭代点是有效解；算法具有多种一维搜索准则；对于线性多目标问题，算法只需一次交互迭代即可示出多目标问题的最优解。     

An O(n) algorithm for quadratic knapsack problems

An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem.     

A linear programming reformulation of the standard quadratic optimization problem

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponentially sized) linear program (LP). This reformulation also suggests a hierarchy of polynomial-time solvable LP’s whose optimal values converge finitely to the optimal value of the SQO problem. The hierarchies of LP relaxations from the literature do not share this finite convergence property for SQO, and we review the relevant counterexamples.     

Exact relaxations for parametric robust linear optimization problems

We first show that the closedness of the characteristic cone of the constraint system of a parametric robust linear optimization problem is a necessary and sufficient condition for each robust linear program with the finite optimal value to admit exact semidefinite linear programming relaxations. We then provide the weakest regularity condition that guarantees exact second-order cone programming relaxations for parametric robust linear programs.     

Constructing efficient solutions structure of multiobjective linear programming

It is not a difficult task to find a weak Pareto or Pareto solution in a multiobjective linear programming (MOLP) problem. The difficulty lies in finding all these solutions and representing their structure. This paper develops an algorithm for solving this problem. We investigate the solutions and their relationships in the objective space. The algorithm determines finite number of weights, each of which corresponds to a weighted sum problems. By solving these problems, we further obtain all weak Pareto and Pareto solutions of the MOLP and their structure in the constraint space. The algorithm avoids the degeneration problem, which is a major hurdle of previous works, and presents an easy and clear solution structure.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

On the transformation of lexicographic nonlinear multiobjective programs to single objective programs

This paper deals with multiobjective optimization programs in which the objective functions are ordered by their degree of priority. A number of approaches have been proposed (and several implemented) for the solution of lexicographic (preemptive priority) multiobjective optimization programs. These approaches may be divided into two classes. The first encompasses the development of algorithms specifically designed to deal directly with the initial model. Considered only for linear multiobjective programs and multiobjective programs with a finite discrete feasible region, the second one attempts to transform, efficiently, the lexicographic multiobjective model into an equvivalent model, i.e. a single objective programming problem. In this paper, we deal with the second approach for lexicographic nonlinear multiobjective programs.     

Approximate Greatest Descent Methods for Optimization with Equality Constraints

In an optimization problem with equality constraints the optimal value function divides the state space into two parts. At a point where the objective function is less than the optimal value, a good iteration must increase the value of the objective function. Thus, a good iteration must be a balance between increasing or decreasing the objective function and decreasing a constraint violation function. This implies that at a point where the constraint violation function is large, we should construct noninferior solutions relative to points in a local search region. By definition, an accessory function is a linear combination of the objective function and a constraint violation function. We show that a way to construct an acceptable iteration, at a point where the constraint violation function is large, is to minimize an accessory function. We develop a two-phases method. In Phase I some constraints may not be approximately satisfied or the current point is not close to the solution. Iterations are generated by minimizing an accessory function. Once all the constraints are approximately satisfied, the initial values of the Lagrange multipliers are defined. A test with a merit function is used to determine whether or not the current point and the Lagrange multipliers are both close to the optimal solution. If not, Phase I is continued. If otherwise, Phase II is activated and the Newton method is used to compute the optimal solution and fast convergence is achieved.     

多目标决策问题及其求解方法研究

针对多目标决策问题的多目标最优化问题化为单目标最优化问题进行了研究.其主要方法有:理想点法、等级权重法、加权算术平均法、加权几何平均法、风险偏好系数法、乘除法、模糊规划法等.此外,还对多目标最大最小和多目标最小最大决策问题进行了处理.     

Parametric mixed-integer 0–1 linear programming: The general case for a single parameter

Two algorithms for the general case of parametric mixed-integer linear programs (MILPs) are proposed. Parametric MILPs are considered in which a single parameter can simultaneously influence the objective function, the right-hand side and the matrix. The first algorithm is based on branch-and-bound on the integer variables, solving a parametric linear program (LP) at each node. The second algorithm is based on the optimality range of a qualitatively invariant solution, decomposing the parametric optimization problem into a series of regular MILPs, parametric LPs and regular mixed-integer nonlinear programs (MINLPs). The number of subproblems required for a particular instance is equal to the number of critical regions. For the parametric LPs an improvement of the well-known rational simplex algorithm is presented, that requires less consecutive operations on rational functions. Also, an alternative based on predictor–corrector continuation is proposed. Numerical results for a test set are discussed.     

多目标应急物流中心选址的鲁棒优化模型

针对重大突发事件的应急物资救援,研究了应急物流中心的选址及应急物资的调运问题。利用离散的情景集合描述受灾点应急物资需求的不确定性以及应急物资运输成本和运输时间的不确定性,同时考虑应急救援成本和应急救援时间两个目标,建立了多目标应急物流中心选址的确定型模型和鲁棒优化模型。为将多目标问题转化为单目标问题,利用成本单目标和时间单目标的最优结果将多目标转化为相对值再加权处理,该方法既可消除多个目标之间的单位及数量级差异,还可以根据问题的数据变化进行动态调整。以提供应急物资救援服务的设施作为编码,设计了一种通用的混合蛙跳算法。为检验模型和算法的有效性,设计了一个多情景的算例,结果表明两个模型和算法具备良好的可行性和有效性,且鲁棒优化模型能较好地保持对各种不确定性的抗干扰能力;最后,讨论分析了成本偏好权重和鲁棒约束系数的影响,结果表明可根据成本偏好权重的取值范围来区分各种应急救援阶段,体现不同救援阶段的救援要求及特征,并给出了成本偏好权重和鲁棒约束系数的取值建议。     

大规模系统的全局优化

本文讨论了可分非凸大规模系统的全局优化控制问题 .提出了一种 3级递阶优化算法 .该算法首先把原问题转化为可分的多目标优化问题 ,然后凸化非劣前沿 ,再从非劣解集中挑出原问题的全局最优解 .建立了算法的理论基础 ,证明了算法的收敛性 .仿真结果表明算法是有效的 .     

A revisit of numerical approach for solving linear fractional programming problem in a fuzzy environment

In the article, Veeramani and Sumathi [10] presented an interesting algorithm to solve a fully fuzzy linear fractional programming (FFLFP) problem with all parameters as well as decision variables as triangular fuzzy numbers. They transformed the FFLFP problem under consideration into a bi-objective linear programming (LP) problem, which is then converted into two crisp LP problems. In this paper, we show that they have used an inappropriate property for obtaining non-negative fuzzy optimal solution of the same problem which may lead to the erroneous results. Using a numerical example, we show that the optimal fuzzy solution derived from the existing model may not be non-negative. To overcome this shortcoming, a new constraint is added to the existing fuzzy model that ensures the fuzzy optimal solution of the same problem is a non-negative fuzzy number. Finally, the modified solution approach is extended for solving FFLFP problems with trapezoidal fuzzy parameters and illustrated with the help of a numerical example.     

On sufficient second order optimality conditions in multiobjective optimization

A second order sufficient optimality criterion is presented for a multiobjective problem subject to a constraint given just as a set. To this aim, we first refine known necessary conditions in such a way that the sufficient ones differ by the replacement of inequalities by strict inequalities. Furthermore, we show that no relationship holds between this criterion and a sufficient multipliers rule, when the constraint is described by inequalities and equalities. Finally, improvements of this criterion for the unconstrained case are presented, stressing the differences with single-objective optimization     

A gap between multiobjective optimization and scalar optimization

We give an example to illustrate a gap between multiobjective optimization and single-objective optimization, which solves a problem proposed in Ref. 1.     

Duality of Nonscalarized Multiobjective Linear Programs: Dual Balance,Level Sets,and Dual Clusters of Optimal Vectors

A new concept of duality is proposed for multiobjective linear programs. It is based on a set expansion process for the computation of optimal solutions without scalarization. The duality gap qualifications are investigated; the primal–dual balance set and level set equations are derived. It is demonstrated that the nonscalarized dual problem presents a cluster of optimal dual vectors that corresponds to a unique optimal primal vector. Comparisons are made with linear utility, minmax and minmin scalarizations. Connections to Pareto optimality are studied and relations to sensitivity and parametric programming are discussed. The ideas are illustrated by examples.     

Separations and Optimality of Constrained Multiobjective Optimization via Improvement Sets

In this paper, we investigate the separations and optimality conditions for the optimal solution defined by the improvement set of a constrained multiobjective optimization problem. We introduce a vector-valued regular weak separation function and a scalar weak separation function via a nonlinear scalarization function defined in terms of an improvement set. The nonlinear separation between the image of the multiobjective optimization problem and an improvement set in the image space is established by the scalar weak separation function. Saddle point type optimality conditions for the optimal solution of the multiobjective optimization problem are established, respectively, by the nonlinear and linear separation methods. We also obtain the relationships between the optimal solution and approximate efficient solution of the multiobjective optimization problem. Finally, sufficient and necessary conditions for the (regular) linear separation between the approximate image of the multiobjective optimization problem and a convex cone are also presented.