An interactive algorithm to find the most preferred solution of multi-objective integer programs

In this paper, we develop an interactive algorithm that finds the most preferred solution of a decision maker (DM) for multi-objective integer programming problems. We assume that the DM’s preferences are consistent with a quasiconcave value function unknown to us. Based on the properties of quasiconcave value functions and pairwise preference information obtained from the DM, we generate constraints to restrict the implied inferior regions. The algorithm continues iteratively and guarantees to find the most preferred solution for integer programs. We test the performance of the algorithm on multi-objective assignment, knapsack, and shortest path problems and show that it works well.     

A posterior preference articulation approach to multiresponse surface optimization

In multiresponse surface optimization (MRSO), responses are often in conflict. To obtain a satisfactory compromise, the preference information of a decision maker (DM) on the tradeoffs among the responses should be incorporated into the problem. In most existing work, the DM expresses a subjective judgment on the responses through a preference parameter before the problem-solving process, after which a single solution is obtained. In this study, we propose a posterior preference articulation approach to MRSO. The approach initially finds a set of nondominated solutions without the DM’s preference information, and then allows the DM to select the best solution from among the nondominated solutions. An interactive selection method based on pairwise comparisons made by the DM is adopted in our method to facilitate the DM’s selection process. The proposed method does not require that the preference information be specified in advance. It is easy and effective in that a satisfactory compromise can be obtained through a series of pairwise comparisons, regardless of the type of the DM’s utility function.     

Solving multiple criteria problems by interactive decomposition

An interactive decomposition method is developed for solving the multiple criteria (MC) problem. Based on nonlinear programming duality theory, the MC problem is decomposed into a series of subproblems and relaxed master problems. Each subproblem is a bicriterion problem, and each relaxed master problem is a standard linear program. The prime objective of the decomposition is to simplify and facilitate the process of making preference assessments and tradeoffs across many conflicting objectives. Therefore, the decision-maker's preference function is not assumed to be known explicitly; rather, the decision maker is required to make only limited local preference assessments in the context of feasible and nondominated alternatives. Also, the preference assessments are of the form of ordinal paired comparisons, and in most of them only two criteria are allowed to change their values simultaneously, while the remaining (l–2) criteria are held fixed at certain levels.     

Hölder estimates for Green’s functions on convex polyhedral domains and their applications to finite element methods

A model second-order elliptic equation on a general convex polyhedral domain in three dimensions is considered. The aim of this paper is twofold: First sharp Hölder estimates for the corresponding Green’s function are obtained. As an applications of these estimates to finite element methods, we show the best approximation property of the error in \({W^1_{\infty}}\) . In contrast to previously known results, \({W_p^{2}}\) regularity for p > 3, which does not hold for general convex polyhedral domains, is not required. Furthermore, the new Green’s function estimates allow us to obtain localized error estimates at a point.     

A smoothing homotopy method for variational inequality problems on polyhedral convex sets

In this paper, based on the Robinson’s normal equation and the smoothing projection operator, a smoothing homotopy method is presented for solving variational inequality problems on polyhedral convex sets. We construct a new smoothing projection operator onto the polyhedral convex set, which is feasible, twice continuously differentiable, uniformly approximate to the projection operator, and satisfies a special approximation property. It is computed by solving nonlinear equations in a neighborhood of the nonsmooth points of the projection operator, and solving linear equations with only finite coefficient matrices for other points, which makes it very efficient. Under the assumption that the variational inequality problem has no solution at infinity, which is a weaker condition than several well-known ones, the existence and global convergence of a smooth homotopy path from almost any starting point in $R^n$ are proven. The global convergence condition of the proposed homotopy method is same with that of the homotopy method based on the equivalent KKT system, but the starting point of the proposed homotopy method is not necessarily an interior point, and the efficiency is more higher. Preliminary test results show that the proposed method is practicable, effective and robust.     

An interactive desirability function method to multiresponse optimization

Multiresponse optimization problems often involve incommensurate and conflicting responses. To obtain a satisfactory compromise in such a case, a decision maker (DM)’s preference information on the tradeoffs among the responses should be incorporated into the problem. This paper proposes an interactive method based on the desirability function approach to facilitate the preference articulation process. The proposed method allows the DM to adjust any of the preference parameters, namely, the shape, bound, and target of a desirability function in a single, integrated framework. The proposed method would be highly effective in generating a compromise solution that is faithful to the DM’s preference structure.     

Piecewise polyhedral formulations for a multilinear term

In this paper, we present a mixed-integer linear programming (MILP) formulation of a piecewise, polyhedral relaxation (PPR) of a multilinear term using its convex-hull representation. Based on the PPR’s solution, we also present a MILP formulation whose solutions are feasible for nonconvex, multilinear equations. We then present computational results showing the effectiveness of proposed formulations on standard benchmark nonlinear programs (NLPs) with multilinear terms and compare with a traditional formulation that is built using recursive bilinear groupings of multilinear terms.     

Robust spectral risk optimization when the subjective risk aversion is ambiguous: a moment-type approach

Choice of a risk measure for quantifying risk of an investment portfolio depends on the decision maker’s risk preference. In this paper, we consider the case when such a preference can be described by a law invariant coherent risk measure but the choice of a specific risk measure is ambiguous. We propose a robust spectral risk approach to address such ambiguity. Differing from Wang and Xu (SIAM J Optim 30(4):3198–3229, 2020), the new robust model allows one to elicit the decision maker’s risk preference through pairwise comparisons and use the elicited preference information to construct an ambiguity set of risk spectra. The robust spectral risk measure (RSRM) is based on the worst case risk spectrum from the set. To calculate RSRM and solve the associated optimal decision making problem, we use a technique from Acerbi and Simonetti (Portfolio optimization with spectral measures of risk. Working paper, 2002) to develop a new computational approach which is independent of order statistics and reformulate the robust spectral risk optimization problem as a single deterministic convex programming problem when the risk spectra in the ambiguity set are step-like. Moreover, we propose an approximation scheme when the risk spectra are not step-like and derive a bound for the model approximation error and its propagation to the optimal decision making problems. Some preliminary numerical test results are reported about the performance of the robust model and the computational scheme.

     

Experiments with an interactive paired comparison simplex method for molp problems

In this paper, an interactive paired comparison simplex based method formultiple objective linear programming (MOLP) problems is developed and compared to other interactive MOLP methods. The decision maker (DM)’s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of ‘strength of preference ’ is developed for the assessment of the DM’s unknown utility function where he can express his preference for a pair of extreme points as ‘strong ’, ‘weak ’, or ‘almost indifferent ’. The problem of ‘inconsistency of the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed. All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors.     

Coalitional unanimity versus strategy-proofness in coalition formation problems

This paper examines coalition formation problems from the viewpoint of mechanism design. We consider the case where (i) the list of feasible coalitions (those coalitions which are permitted to form) is given in advance; and (ii) each individual’s preference is a ranking over those feasible coalitions which include this individual. We are interested in requiring the mechanism to guarantee each coalition the “right” of forming that coalition at least when every member of the coalition ranks the coalition at the top. We name this property coalitional unanimity. We examine the compatibility between coalitional unanimity and incentive requirements, and prove that if the mechanism is strategy-proof and respects coalitional unanimity, then for each preference profile, there exists at most one strictly core stable partition, and the mechanism chooses such a partition whenever available. Further, the mechanism is coalition strategy-proof and respects coalitional unanimity if, and only if, the strictly core stable partition uniquely exists for every preference profile.     

Theory of convex cones in multicriteria decision making

We develop the theory of convex polyhedral cones in the objective-function space of a multicriteria decision problem. The convex cones are obtained from the decision-maker's pairwise judgments of decision alternatives and are applicable to any quasiconcave utility function. Therefore, the cones can be used in any progressively articulated solution procedure that employs pairwise comparisons. The cones represent convex sets of solutions that are inferior to known solutions to a multicriteria problem. Therefore, these convex sets can be eliminated from consideration while solving the problem. We develop the underlying theory and a framework for representing knowledge about the decision-maker's preference structure using convex cones. This framework can be adopted in the interactive solution of any multicriteria problem after taking into account the characteristics of the problem and the solution procedure. Our computational experience with different multicriteria problems shows that this approach is both viable and efficient in solving practical problems of moderate size.     

A combination between the reduced basis method and the ANOVA expansion: On the computation of sensitivity indices

We consider a method to efficiently evaluate in a real-time context an output based on the numerical solution of a partial differential equation depending on a large number of parameters. We state a result allowing to improve the computational performance of a three-step RB–ANOVA–RB method. This is a combination of the reduced basis (RB) method and the analysis of variations (ANOVA) expansion, aiming at compressing the parameter space without affecting the accuracy of the output. The idea of this method is to compute a first (coarse) RB approximation of the output of interest involving all the parameter components, but with a large tolerance on the a posteriori error estimate; then, we evaluate the ANOVA expansion of the output and freeze the least important parameter components; finally, considering a restricted model involving just the retained parameter components, we compute a second (fine) RB approximation with a smaller tolerance on the a posteriori error estimate. The fine RB approximation entails lower computational costs than the coarse one, because of the reduction of parameter dimensionality. Our result provides a criterion to avoid the computation of those terms in the ANOVA expansion that are related to the interaction between parameters in the bilinear form, thus making the RB–ANOVA–RB procedure computationally more feasible.     

Characterizing strict efficiency for convex multiobjective programming problems

The article pertains to characterize strict local efficient solution (s.l.e.s.) of higher order for the multiobjective programming problem (MOP) with inequality constraints. To create the necessary framework, we partition the index set of objectives of MOP to give rise to subproblems. The s.l.e.s. of order m for MOP is related to the local efficient solution of a subproblem. This relationship inspires us to adopt the D.C. optimization approach, the convex subdifferential sum rule, and the notion of ε-subdifferential to derive the necessary and sufficient optimality conditions for s.l.e.s. of order m \geqq 1{m \geqq 1} for the convex MOP. Further, the saddle point criteria of higher order are also presented.     

The double-layer potential operator over polyhedral domains II: Spline Galerkin methods

We examine the numerical approximation of the integral equation (λ ? K)u =f, where K is the double layer (harmonic) potential operator on a closed polyhedral surface in ?³ and λ, ∣λ∣≥1, is a complex constant. The solution is approximated by Galerkin's method, which is based on piecewise polynomials of arbitrary degree on graded triangulations. By utilizing spline spaces which are modified in that the trial functions vanish on some of the triangles closest to the vertices and edges, we investigate the stability of this method in L². Furthermore, the use of suitably graded meshes leads to the same quasioptimal error estimates as in the case of a smooth surface.     

Two issues in using mixtures of polynomials for inference in hybrid Bayesian networks

We discuss two issues in using mixtures of polynomials (MOPs) for inference in hybrid Bayesian networks. MOPs were proposed by Shenoy and West for mitigating the problem of integration in inference in hybrid Bayesian networks. First, in defining MOP for multi-dimensional functions, one requirement is that the pieces where the polynomials are defined are hypercubes. In this paper, we discuss relaxing this condition so that each piece is defined on regions called hyper-rhombuses. This relaxation means that MOPs are closed under transformations required for multi-dimensional linear deterministic conditionals, such as Z = X + Y, etc. Also, this relaxation allows us to construct MOP approximations of the probability density functions (PDFs) of the multi-dimensional conditional linear Gaussian distributions using a MOP approximation of the PDF of the univariate standard normal distribution. Second, Shenoy and West suggest using the Taylor series expansion of differentiable functions for finding MOP approximations of PDFs. In this paper, we describe a new method for finding MOP approximations based on Lagrange interpolating polynomials (LIP) with Chebyshev points. We describe how the LIP method can be used to find efficient MOP approximations of PDFs. We illustrate our methods using conditional linear Gaussian PDFs in one, two, and three dimensions, and conditional log-normal PDFs in one and two dimensions. We compare the efficiencies of the hyper-rhombus condition with the hypercube condition. Also, we compare the LIP method with the Taylor series method.     

On polyhedral approximations in an <Emphasis Type="Italic">n</Emphasis>-dimensional space

The polyhedral approximation of a positively homogeneous (and, in general, nonconvex) function on a unit sphere is investigated. Such a function is presupporting (i.e., its convex hull is the supporting function) for a convex compact subset of Rⁿ. The considered polyhedral approximation of this function provides a polyhedral approximation of this convex compact set. The best possible estimate for the error of the considered approximation is obtained in terms of the modulus of uniform continuous subdifferentiability in the class of a priori grids of given step in the Hausdorff metric.     

Method for constructing an external polyhedral estimate of the trajectory tube for a nonlinear dynamic system

A numerical method is proposed for constructing an external polyhedral estimate for the trajectory tube of a nonlinear dynamic system described by a differential inclusion. The method is based on the approximation of cross sections of the trajectory tube (reachable sets) for an auxiliary system described by the convex hull of the graph of the differential inclusion. It produces polyhedral estimates suitable for the direct study of tubes via computer visualization and for the solution of more general problems.

     

Convergence analysis of non-conforming Trigonometric Finite Wave Elements

Trigonometric Finite Wave Elements (TFWE) are finite elements for solving problems in computational optics. The solution of those problems consist of highly oscillatory waves. TFWE are designed for obtaining optimal approximation properties for such kinds of waves with a changing wave number k. In this article, we study the convergence properties of 2-dimensional non-conforming TFWE by applying Strang’s Lemma.     

Adaptive wavelet methods for the stochastic Poisson equation

We study the Besov regularity as well as linear and nonlinear approximation of random functions on bounded Lipschitz domains in ? ^d . The random functions are given either (i) explicitly in terms of a wavelet expansion or (ii) as the solution of a Poisson equation with a right-hand side in terms of a wavelet expansion. In the case (ii) we derive an adaptive wavelet algorithm that achieves the nonlinear approximation rate at a computational cost that is proportional to the degrees of freedom. These results are matched by computational experiments.