A dynamic gradient approach to Pareto optimization with nonsmooth convex objective functions

In a general Hilbert framework, we consider continuous gradient-like dynamical systems for constrained multiobjective optimization involving nonsmooth convex objective functions. Based on the Yosida regularization of the subdifferential operators involved in the system, we obtain the existence of strong global trajectories. We prove a descent property for each objective function, and the convergence of trajectories to weak Pareto minima. This approach provides a dynamical endogenous weighting of the objective functions, a key property for applications in cooperative games, inverse problems, and numerical multiobjective optimization.     

Multiple subgradient descent bundle method for convex nonsmooth multiobjective optimization

The aim of this paper is to propose a new multiple subgradient descent bundle method for solving unconstrained convex nonsmooth multiobjective optimization problems. Contrary to many existing multiobjective optimization methods, our method treats the objective functions as they are without employing a scalarization in a classical sense. The main idea of this method is to find descent directions for every objective function separately by utilizing the proximal bundle approach, and then trying to form a common descent direction for every objective function. In addition, we prove that the method is convergent and it finds weakly Pareto optimal solutions. Finally, some numerical experiments are considered.     

Vector Ordinal Optimization

Ordinal optimization is a tool to reduce the computational burden in simulation-based optimization problems. So far, the major effort in this field focuses on single-objective optimization. In this paper, we extend this to multiobjective optimization and develop vector ordinal optimization, which is different from the one introduced in Ref. 1. Alignment probability and ordered performance curve (OPC) are redefined for multiobjective optimization. Our results lead to quantifiable subset selection sizes in the multiobjective case, which supplies guidance in solving practical problems, as demonstrated by the examples in this paper.This paper was supported in part by Army Contract DAAD19-01-1-0610, AFOSR Contract F49620-01-1-0288, and a contract with United Technology Research Center (UTRC). The first author received additional funding from NSF of China Grants 60074012 and 60274011, Ministry of Education (China), and a Tsinghua University (Beijing, China) Fundamental Research Funding Grant, and the NCET program of China.The authors are grateful to and benefited from two rounds of reviews from three anonymous referees.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

大规模系统的全局优化

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

Equality Constraints in Multiobjective Robust Design Optimization: Decision Making Problem

Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate our theoretical developments.     

Explicit gradient information in multiobjective optimization

This work presents an algorithm that converges to points that satisfy a first-order necessary condition of weakly Pareto solutions of multiobjective optimization problems. Hints on how to include second-order information are given. Preliminary numerical results are encouraging.     

Nonscalarized multiobjective global optimization

A new approach to multiobjective optimization is presented which is made possible due to our ability to obtain full global optimal solutions. A distinctive feature of this approach is that a vector cost function is nonscalarized. The method provides a means for the solution of vector optimization problems with nonreconcilable objectives.This work was supported by the Natural Sciences and Engineering Research Council of Canada, Grant No. A3492.     

A variational approach to define robustness for parametric multiobjective optimization problems

In contrast to classical optimization problems, in multiobjective optimization several objective functions are considered at the same time. For these problems, the solution is not a single optimum but a set of optimal compromises, the so-called Pareto set. In this work, we consider multiobjective optimization problems that additionally depend on an external parameter ${\lambda \in \mathbb{R}}$ , so-called parametric multiobjective optimization problems. The solution of such a problem is given by the λ-dependent Pareto set. In this work we give a new definition that allows to characterize λ-robust Pareto points, meaning points which hardly vary under the variation of the parameter λ. To describe this task mathematically, we make use of the classical calculus of variations. A system of differential algebraic equations will turn out to describe λ-robust solutions. For the numerical solution of these equations concepts of the discrete calculus of variations are used. The new robustness concept is illustrated by numerical examples.     

Bucket elimination for multiobjective optimization problems

Multiobjective optimization deals with problems involving multiple measures of performance that should be optimized simultaneously. In this paper we extend bucket elimination (BE), a well known dynamic programming generic algorithm, from mono-objective to multiobjective optimization. We show that the resulting algorithm, MO-BE, can be applied to true multi-objective problems as well as mono-objective problems with knapsack (or related) global constraints. We also extend mini-bucket elimination (MBE), the approximation form of BE, to multiobjective optimization. The new algorithm MO-MBE can be used to obtain good quality multi-objective lower bounds or it can be integrated into multi-objective branch and bound in order to increase its pruning efficiency. Its accuracy is empirically evaluated in real scheduling problems, as well as in Max-SAT-ONE and biobjective weighted minimum vertex cover problems.     

A decision-theoretic approach to robust optimization in multivalued graphs

This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach.     

Generalized Homotopy Approach to Multiobjective Optimization

This paper proposes a new generalized homotopy algorithm for the solution of multiobjective optimization problems with equality constraints. We consider the set of Pareto candidates as a differentiable manifold and construct a local chart which is fitted to the local geometry of this Pareto manifold. New Pareto candidates are generated by evaluating the local chart numerically. The method is capable of solving multiobjective optimization problems with an arbitrary number k of objectives, makes it possible to generate all types of Pareto optimal solutions, and is able to produce a homogeneous discretization of the Pareto set. The paper gives a necessary and sufficient condition for the set of Pareto candidates to form a (k-1)-dimensional differentiable manifold, provides the numerical details of the proposed algorithm, and applies the method to two multiobjective sample problems.     

Robustness to uncertain optimization using scalarization techniques and relations to multiobjective optimization

In this paper, we propose two kinds of robustness concepts by virtue of the scalarization techniques (Benson’s method and elastic constraint method) in multiobjective optimization, which can be characterized as special cases of a general non-linear scalarizing approach. Moreover, we introduce both constrained and unconstrained multiobjective optimization problems and discuss their relations to scalar robust optimization problems. Particularly, optimal solutions of scalar robust optimization problems are weakly efficient solutions for the unconstrained multiobjective optimization problem, and these solutions are efficient under uniqueness assumptions. Two examples are employed to illustrate those results. Finally, the connections between robustness concepts and risk measures in investment decision problems are also revealed.     

Solving circle packing problems by global optimization: Numerical results and industrial applications

A (general) circle packing is an optimized arrangement of N arbitrary sized circles inside a container (e.g., a rectangle or a circle) such that no two circles overlap. In this paper, we present several circle packing problems, review their industrial applications, and some exact and heuristic strategies for their solution. We also present illustrative numerical results using ‘generic’ global optimization software packages. Our work highlights the relevance of global optimization in solving circle packing problems, and points towards the necessary advancements in both theory and numerical practice.     

Duality for multiobjective optimization problems with convex objective functions and D.C. constraints

In this paper we provide a duality theory for multiobjective optimization problems with convex objective functions and finitely many D.C. constraints. In order to do this, we study first the duality for a scalar convex optimization problem with inequality constraints defined by extended real-valued convex functions. For a family of multiobjective problems associated to the initial one we determine then, by means of the scalar duality results, their multiobjective dual problems. Finally, we consider as a special case the duality for the convex multiobjective optimization problem with convex constraints.     

Sequential Semidefinite Program for Maximum Robustness Design of Structures under Load Uncertainty

A robust structural optimization scheme as well as an optimization algorithm are presented based on the robustness function. Under the uncertainties of the external forces based on the info-gap model, the maximization of the robustness function is formulated as an optimization problem with infinitely many constraints. By using the quadratic embedding technique of uncertainty and the S-procedure, we reformulate the problem into a nonlinear semidefinite programming problem. A sequential semidefinite programming method is proposed which has a global convergent property. It is shown through numerical examples that optimum designs of various linear elastic structures can be found without difficulty.The authors are grateful to the Associate Editor and two anonymous referees for handling the paper efficiently as well as for helpful comments and suggestions.     

Weak sharp minima for piecewise linear multiobjective optimization in normed spaces

In a general normed space, we consider a piecewise linear multiobjective optimization problem. We prove that a cone-convex piecewise linear multiobjective optimization problem always has a global weak sharp minimum property. By a counter example, we show that the weak sharp minimum property does not necessarily hold if the cone-convexity assumption is dropped. Moreover, under the assumption that the ordering cone is polyhedral, we prove that a (not necessarily cone-convex) piecewise linear multiobjective optimization problem always has a bounded weak sharp minimum property.     

Heuristic for a new multiobjective scheduling problem

We consider a telecommunication problem in which the objective is to schedule data transmission to be as fast and as cheap as possible. The main characteristic and restriction in solving this multiobjective optimization problem is the very limited computational capacity available. We describe a simple but efficient local search heuristic to solve this problem and provide some encouraging numerical test results. They demonstrate that we can develop a computationally inexpensive heuristic without sacrificing too much in the solution quality.     

求多目标优化问题Pareto最优解集的方法

主要讨论了无约束多目标优化问题Pareto最优解集的求解方法,其中问题的目标函数是C1连续函数.给出了Pareto最优解集的一个充要条件,定义了α强有效解,并结合区间分析的方法,建立了求解无约束多目标优化问题Pareto最优解集的区间算法,理论分析和数值结果均表明该算法是可靠和有效的.     

解线性等式约束优化问题的模式搜索过滤集方法

提出一个解线性等式约束无导数优化的模式搜索过滤集算法,该算法将过滤集技术嵌入无导数优化算法中以改善算法的效率. 建立了新算法的总体收敛性, 初步的数值试验结果表明新算法是有效的.