Search

Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a weighted-sum scalarization of the MOIP. At unsupported solutions, the convex hull relaxation is not tight and a Lagrangian relaxation may provide a tighter bound. Using the Lagrangian relaxation, we define a Lagrangian dual of an MOIP that satisfies weak duality and is strong at supported solutions under certain conditions on the primal feasible region. We include a numerical experiment to illustrate that bound sets obtained via Lagrangian duality may yield tighter bounds than those from a convex hull relaxation. Subsequently, we generalize the integer programming value function to MOIPs and use its properties to motivate a set-valued superadditive dual that is strong at supported solutions. We also define a simpler vector-valued superadditive dual that exhibits weak duality but is strongly dual if and only if the primal has a unique nondominated point. [ABSTRACT FROM AUTHOR]

The paper is devoted to the existence of global optimal solutions for a general class of nonsmooth problems of constrained vector optimization without boundedness assumptions on constraint set. The main attention is paid to the two major notions of optimality in vector problems: Pareto efficiency and proper efficiency in the sense of Geoffrion. Employing adequate tools of variational analysis and generalized differentiation, we first establish relationships between the notions of properness, M-tameness, and the Palais–Smale conditions formulated for the restriction of the vector cost mapping on the constraint set. These results are instrumental to derive verifiable necessary and sufficient conditions for the existence of Pareto efficient solutions in vector optimization. Furthermore, the developed approach allows us to obtain new sufficient conditions for the existence of Geoffrion-properly efficient solutions to such constrained vector problems. [ABSTRACT FROM AUTHOR]

A nonlinear stepsize control framework for unconstrained optimization was recently proposed by Toint (Optim Methods Softw 28:82-95, ), providing a unified setting in which the global convergence can be proved for trust-region algorithms and regularization schemes. The original analysis assumes that the Hessians of the models are uniformly bounded. In this paper, the global convergence of the nonlinear stepsize control algorithm is proved under the assumption that the norm of the Hessians can grow by a constant amount at each iteration. The worst-case complexity is also investigated. The results obtained for unconstrained smooth optimization are extended to some algorithms for composite nonsmooth optimization and unconstrained multiobjective optimization as well. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to characterize the weak efficient solutions, the efficient solutions, and the isolated efficient solutions of a given vector optimization problem with finitely many convex objective functions and infinitely many convex constraints. To do this, we introduce new and already known data qualifications (conditions involving the constraints and/or the objectives) in order to get optimality conditions which are expressed in terms of either Karusk-Kuhn-Tucker multipliers or a new gap function associated with the given problem. [ABSTRACT FROM AUTHOR]

The paper is devoted to new applications of advanced tools of modern variational analysis and generalized differentiation to the study of broad classes of multiobjective optimization problems subject to equilibrium constraints in both finite-dimensional and infinite-dimensional settings. Performance criteria in multiobjective/vector optimization are defined by general preference relationships satisfying natural requirements, while equilibrium constraints are described by parameterized generalized equations/variational conditions in the sense of Robinson. Such problems are intrinsically nonsmooth and are handled in this paper via appropriate normal/coderivative/subdifferential constructions that exhibit full calculi. Most of the results obtained are new even in finite dimensions, while the case of infinite-dimensional spaces is significantly more involved requiring in addition certain “sequential normal compactness” properties of sets and mappings that are preserved under a broad spectrum of operations. [ABSTRACT FROM AUTHOR]

Motivated by the binary classification problem in machine learning, we study in this paper a class of decision problems where the decision maker has a list of goals, from which he aims to attain the maximal possible number of goals. In binary classification, this essentially means seeking a prediction rule to achieve the lowest probability of misclassification, and computationally it involves minimizing a (difficult) non-convex, 0–1 loss function. To address the intractability, previous methods consider minimizing the cumulative loss—the sum of convex surrogates of the 0–1 loss of each goal. We revisit this paradigm and develop instead an axiomatic framework by proposing a set of salient properties on functions for goal scoring and then propose the coherent loss approach, which is a tractable upper-bound of the loss over the entire set of goals. We show that the proposed approach yields a strictly tighter approximation to the total loss (i.e., the number of missed goals) than any convex cumulative loss approach while preserving the convexity of the underlying optimization problem. Moreover, this approach, applied to for binary classification, also has a robustness interpretation which builds a connection to robust SVMs. [ABSTRACT FROM AUTHOR]

This paper investigates the potential of Lagrangian relaxations to generate quality bounds on non-dominated images of multiobjective integer programs (MOIPs). Under some conditions on the relaxed constraints, we show that a set of Lagrangian relaxations can provide bounds that coincide with every bound generated by the convex hull relaxation. We also provide a guarantee of the relative quality of the Lagrangian bound at unsupported solutions. These results imply that, if the relaxed feasible region is bounded, some Lagrangian bounds will be strictly better than some convex hull bounds. We demonstrate that there exist Lagrangian multipliers which are sparse, satisfy a complementary slackness property, and generate tight relaxations at supported solutions. However, if all constraints are dualized, a relaxation can never be tight at an unsupported solution. These results characterize the strength of the Lagrangian dual at efficient solutions of an MOIP. [ABSTRACT FROM AUTHOR]

This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes low-rank matrix recovery feasible in more practical settings. Theoretically, we prove that the proposed estimator achieves fast rates of convergence under different settings. Computationally, we propose an alternating direction method of multipliers algorithm to efficiently compute the estimator, which bridges a gap between theory and practice of machine learning methods with max-norm regularization. Further, we provide thorough numerical studies to evaluate the proposed method using both simulated and real datasets. [ABSTRACT FROM AUTHOR]

In this paper we introduce and study enhanced notions of relative Pareto minimizers for constrained multiobjective problems that are defined via several kinds of relative interiors of ordering cones and occupy intermediate positions between the classical notions of Pareto and weak Pareto efficiency/minimality. Using advanced tools of variational analysis and generalized differentiation, we establish the existence of relative Pareto minimizers for general multiobjective problems under a refined version of the subdifferential Palais-Smale condition for set-valued mappings with values in partially ordered spaces and then derive necessary optimality conditions for these minimizers (as well as for conventional efficient and weak efficient counterparts) that are new in both finite-dimensional and infinite-dimensional settings. Our proofs are based on variational and extremal principles of variational analysis; in particular, on new versions of the Ekeland variational principle and the subdifferential variational principle for set-valued and single-valued mappings in infinite-dimensional spaces. [ABSTRACT FROM AUTHOR]

In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans-Steuer) algorithm (Math Program 5(1):54-72, 1973). Different from it, the proposed algorithm works in the parameter space and does not aim to find the set of all efficient solutions. Instead, it finds a solution in the sense of Löhne (Vector optimization with infimum and supremum. Springer, Berlin, 2011), that is, it finds a subset of efficient solutions that allows to generate the whole efficient frontier. In that sense, it can also be seen as a generalization of the parametric self-dual simplex algorithm, which originally is designed for solving single objective linear optimization problems, and is modified to solve two objective bounded LVOPs with the positive orthant as the ordering cone in Ruszczyński and Vanderbei (Econometrica 71(4):1287-1297, 2003). The algorithm proposed here works for any dimension, any solid pointed polyhedral ordering cone C and for bounded as well as unbounded problems. Numerical results are provided to compare the proposed algorithm with an objective space based LVOP algorithm [Benson's algorithm in Hamel et al. (J Global Optim 59(4):811-836, 2014)], that also provides a solution in the sense of Löhne (2011), and with the Evans-Steuer algorithm (1973). The results show that for non-degenerate problems the proposed algorithm outperforms Benson's algorithm and is on par with the Evans-Steuer algorithm. For highly degenerate problems Benson's algorithm (Hamel et al. 2014) outperforms the simplex-type algorithms; however, the parametric simplex algorithm is for these problems computationally much more efficient than the Evans-Steuer algorithm. [ABSTRACT FROM AUTHOR]

A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In more detail, we obtain the following main results: Using iterative rounding for the first time in multi-objective optimization, we obtain multi-criteria PTASs (which slightly violate the budget constraints) for spanning tree, matroid basis, and bipartite matching with $$k=O(1)$$ budget constraints. We present a simple mechanism to transform multi-criteria approximation schemes into pure approximation schemes for problems whose feasible solutions define an independence system. This gives improved algorithms for several problems. In particular, this mechanism can be applied to the above bipartite matching algorithm, hence obtaining a pure PTAS. We show that points in low-dimensional faces of any matroid polytope are almost integral, an interesting result on its own. This gives a deterministic approximation scheme for $$k$$ -budgeted matroid independent set. We present a deterministic approximation scheme for $$k$$ -budgeted matching (in general graphs), where $$k=O(1)$$ . Interestingly, to show that our procedure works, we rely on a non-constructive result by Stromquist and Woodall, which is based on the Ham Sandwich Theorem. [ABSTRACT FROM AUTHOR]

We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of non-linear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme does not require the assumption of quasi-concavity on the objective function. For the special case of quasi-concave function minimization, we give an alternative FPTAS, which always returns a solution which is an extreme point of the polytope. Our technique can also be used to obtain an FPTAS for combinatorial optimization problems with non-linear objective functions, for example when the objective is a product of a fixed number of linear functions. We also show that it is not possible to approximate the minimum of a general concave function over the unit hypercube to within any factor, unless P = NP. We prove this by showing a similar hardness of approximation result for supermodular function minimization, a result that may be of independent interest. [ABSTRACT FROM AUTHOR]

To make a decision that is defined by multiple, conflicting objectives it is necessary to know the relative importance of the different objectives. In this paper we present an interactive method and the underlying theory for solving multiple objective mathematical programming problems defined by a convex feasible region and concave, continuously differentiable objective functions. The relative importance of the different objectives for a decision maker is elicited by using binary comparisons of objective function vectors. The method is cognitively easy to use and in test problems has rapidly converged to an optimal solution. [ABSTRACT FROM AUTHOR]

This paper provides an answer to the following basic problem of convex multi-objective optimization: Find a saddle-point condition that is both necessary and sufficient that a given point be Pareto optimal. No regularity condition is assumed for the constraints or the objectives. [ABSTRACT FROM AUTHOR]

This work presents an algorithm for multiobjective optimization that is structured as: (i) a descent direction is calculated, within the cone of descent and feasible directions, and (ii) a multiobjective line search is conducted over such direction, with a new multiobjective golden section segment partitioning scheme that directly finds line-constrained efficient points that dominate the current one. This multiobjective line search procedure exploits the structure of the line-constrained efficient set, presenting a faster compression rate of the search segment than single-objective golden section line search. The proposed multiobjective optimization algorithm converges to points that satisfy the Kuhn-Tucker first-order necessary conditions for efficiency (the Pareto-critical points). Numerical results on two antenna design problems support the conclusion that the proposed method can solve robustly difficult nonlinear multiobjective problems defined in terms of computationally expensive black-box objective functions. [ABSTRACT FROM AUTHOR]

We study a multiobjective optimization program with a feasible set defined by equality constraints and a generalized inequality constraint. We suppose that the functions involved are Fréchet differentiable and their Fréchet derivatives are continuous or stable at the point considered. We provide necessary second order optimality conditions and also sufficient conditions via a Fritz John type Lagrange multiplier rule and a set-valued second order directional derivative, in such a way that our sufficient conditions are close to the necessary conditions. Some consequences are obtained for parabolic directionally differentiable functions and C1,1 functions, in this last case, expressed by means of the second order Clarke subdifferential. Some illustrative examples are also given. [ABSTRACT FROM AUTHOR]

We are interested in the existence of Pareto solutions to the vector optimization problem Min R + m { f (x) | x ∈ R n } , where f : R n → R m is a polynomial map. By using the tangency variety of f we first construct a semi-algebraic set of dimension at most m - 1 containing the set of Pareto values of the problem. Then we establish connections between the Palais–Smale conditions, M-tameness, and properness for the map f. Based on these results, we provide some sufficient conditions for the existence of Pareto solutions of the problem. We also introduce a generic class of polynomial vector optimization problems having at least one Pareto solution. [ABSTRACT FROM AUTHOR]

A trust-region-based algorithm for the nonconvex unconstrained multiobjective optimization problem is considered. It is a generalization of the algorithm proposed by Fliege et al. (SIAM J Optim 20:602-626, 2009), for the convex problem. Similarly to the scalar case, at each iteration a subproblem is solved and the step needs to be evaluated. Therefore, the notions of decrease condition and of predicted reduction are adapted to the vectorial case. A rule to update the trust region radius is introduced. Under differentiability assumptions, the algorithm converges to points satisfying a necessary condition for Pareto points and, in the convex case, to a Pareto points satisfying necessary and sufficient conditions. Furthermore, it is proved that the algorithm displays a q-quadratic rate of convergence. The global behavior of the algorithm is shown in the numerical experience reported. [ABSTRACT FROM AUTHOR]

Convexity has long had an important role in economic theory, but some recent developments have featured it all the more in problems of equilibrium. Here the tools of convex analysis are applied to a basic model of incomplete financial markets in which assets are traded and money can be lent or borrowed between the present and future. The existence of an equilibrium is established with techniques that include bounds derived from the duals to problems of utility maximization. Composite variational inequalities furnish the modeling platform. Models with and without short-selling are handled, moreover in the absence of any requirement that agents must initially have a positive amount of every asset, as is typical in equilibrium work in economics. [ABSTRACT FROM AUTHOR]

We consider a quadratic programming (QP) problem (Π) of the form min x C x subject to Ax ≥ b, x ≥ 0 where $${C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}$$ and $${A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}$$ . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and 'rounding' the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0-1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions. [ABSTRACT FROM AUTHOR]

In this work nonlinear non-convex multiobjective bilevel optimization problems are discussed using an optimistic approach. It is shown that the set of feasible points of the upper level function, the so-called induced set, can be expressed as the set of minimal solutions of a multiobjective optimization problem. This artificial problem is solved by using a scalarization approach by Pascoletti and Serafini combined with an adaptive parameter control based on sensitivity results for this problem. The bilevel optimization problem is then solved by an iterative process using again sensitivity theorems for exploring the induced set and the whole efficient set is approximated. For the case of bicriteria optimization problems on both levels and for a one dimensional upper level variable, an algorithm is presented for the first time and applied to two problems: a theoretical example and a problem arising in applications. [ABSTRACT FROM AUTHOR]

We study the weak domination property and weakly efficient solutions in vector optimization problems. In particular scalarization of these problems is obtained by virtue of some suitable merit functions. Some natural conditions to ensure the existence of error bounds for merit functions are also given. [ABSTRACT FROM AUTHOR]

We present a geometrical interpretation of the weighting method for constrained (finite dimensional) vector optimization. This approach is based on rigid movements which separate the image set from the negative of the ordering cone. We study conditions on the existence of such translations in terms of the boundedness of the scalar problems produced by the weighting method. Finally, using recession cones, we obtain the main result of our work: a sufficient condition under which weighting vectors yield solvable scalar problems. [ABSTRACT FROM AUTHOR]

We analyze the logarithmic barrier method for nonsmooth convex optimization in the setting of point-to-set theory. This general framework allows us to both extend and include classical results. We also propose an application for finding efficient points of nonsmooth constrained convex vector-valued problems. [ABSTRACT FROM AUTHOR]

We consider the constrained vector optimization problem min C f( x), g( x) ∈ − K, where f:ℝ n→ℝ m and g:ℝ n→ℝ p are C1,1 functions, and Cℝ m and Kℝ p are closed convex cones with nonempty interiors. Two type of solutions are important for our considerations, namely w-minimizers (weakly efficient points) and i-minimizers (isolated minimizers). We formulate and prove in terms of the Dini directional derivative second-order necessary conditions for a point x0 to be a w-minimizer and second-order sufficient conditions for x0 to be an i-minimizer of order two. We discuss the reversal of the sufficient conditions under suitable constraint qualifications of Kuhn-Tucker type. The obtained results improve the ones in Liu, Neittaanmäki, Křížek [21]. [ABSTRACT FROM AUTHOR]

Using variational analysis, we study vector optimization problems with objectives being closed multifunctions on Banach spaces or in Asplund spaces. In particular, in terms of the coderivatives, we present Fermat’s rules as necessary conditions for an optimal solution of the above problems. As applications, we also provide some necessary conditions (in terms of Clarke’s normal cones or the limiting normal cones) for Pareto efficient points. [ABSTRACT FROM AUTHOR]

We introduce and characterize a class of differentiable convex functions for which the Karush-Kuhn-Tucker condition is necessary for optimality. If some constraints do not belong to this class, then the characterization of optimality generally assumes an asymptotic form. We also show that for the functions that belong to this class in multi-objective optimization, Pareto solutions coincide with strong Pareto solutions,. This extends a result, well known for the linear case. [ABSTRACT FROM AUTHOR]