We consider investment problems where an investor can invest in a savings account, stocks and bonds and tries to maximize her utility from terminal wealth. In contrast to the classical Merton problem we assume a stochastic interest rate. To solve the corresponding control problems it is necessary to prove averi cation theorem without the usual Lipschitz assumptions.
Many polynomially solvable combinatorial optimization problems (COP) become NP when we require solutions to satisfy an additional cardinality constraint. This family of problems has been considered only recently. We study a newproblem of this family: the k-cardinality minimum cut problem. Given an undirected edge-weighted graph the k-cardinality minimum cut problem is to find a partition of the vertex set V in two sets V 1 , V 2 such that the number of the edges between V 1 and V 2 is exactly k and the sum of the weights of these edges is minimal. A variant of this problem is the k-cardinality minimum s-t cut problem where s and t are fixed vertices and we have the additional request that s belongs to V 1 and t belongs to V 2 . We also consider other variants where the number of edges of the cut is constrained to be either less or greater than k. For all these problems we show complexity results in the most significant graph classes.
In the Black-Scholes type financial market, the risky asset S 1 ( ) is supposed to satisfy dS 1 ( t ) = S 1 ( t )( b ( t ) dt + Sigma ( t ) dW ( t ) where W ( ) is a Brownian motion. The processes b ( ), Sigma ( ) are progressively measurable with respect to the filtration generated by W ( ). They are known as the mean rate of return and the volatility respectively. A portfolio is described by a progressively measurable processes Pi1 ( ), where Pi1 ( t ) gives the amount invested in the risky asset at the time t. Typically, the optimal portfolio Pi1 ( ) (that, which maximizes the expected utility), depends at the time t, among other quantities, on b ( t ) meaning that the mean rate of return shall be known in order to follow the optimal trading strategy. However, in a real-world market, no direct observation of this quantity is possible since the available information comes from the behavior of the stock prices which gives a noisy observation of b ( ). In the present work, we consider the optimal portfolio selection which uses only the observation of stock prices.
We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet defining. We show its superior computational performance by benchmarking it on a well known data set.
We consider some continuous-time Markowitz type portfolio problems that consist of maximizing expected terminal wealth under the constraint of an upper bound for the Capital-at-Risk. In a Black-Scholes setting we obtain closed form explicit solutions and compare their form and implications to those of the classical continuous-time mean-variance problem. We also consider more general price processes which allow for larger uctuations in the returns.
In multicriteria optimization problems the connectedness of the set of efficient solutions (pareto set) is of special interest since it would allow the determination of the efficient solutions without considering non-efficient solutions in the process. In the case of the multicriteria problem to minimize matchings the set of efficient solutions is not connected. The set of minimal solutions E pot with respect to the power ordered set contains the pareto set. In this work theorems about connectedness of E pot are given. These lead to an automated process to detect all efficient solutions.
We consider the determination of optimal portfolios under the threat of a crash. Our main assumption is that upper bounds for both the crash size and the number of crashes occurring before the time horizon are given. We make no probabilistic assumption on the crash size or the crash time distribution. The optimal strategies in the presence of a crash possibility are characterized by a balance problem between insurance against the crash and good performance in the crash-free situation. Explicit solutions for the log-utility case are given. Our main finding is that constant portfolios are no longer optimal ones.
We consider the problem of locating a line or a line segment in three- dimensional space, such that the sum of distances from the linear facility to a given set of points is minimized. An example is planning the drilling of a mine shaft, with access to ore deposits through horizontal tunnels connecting the deposits and the shaft. Various models of the problem are developed and analyzed, and effcient solution methods are given.
This paper provides an annotated bibliography of multiple objective combinatorial optimization, MOCO. We present a general formulation of MOCO problems, describe the main characteristics of MOCO problems, and review the main properties and theoretical results for these problems. One section is devoted to a brief description of the available solution methodology, both exact and heuristic. The main part of the paper is devoted to an annotation of the existing literature in the field organized problem by problem. We conclude the paper by stating open questions and areas of future research. The list of references comprises more than 350 entries.
In this paper we address the question of how many objective functions are needed to decide whether a given point is a Pareto optimal solution for a multicriteria optimization problem. We extend earlier results showing that the set of weakly Pareto optimal points is the union of Pareto optimal sets of subproblems and show their limitations. We prove that for strictly quasi-convex problems in two variables Pareto optimality can be decided by consideration of at most three objectives at a time. Our results are based on a geometric characterization of Pareto, strict Pareto and weak Pareto solutions and Helly's Theorem. We also show that a generalization to quasi-convex objectives is not possible, and state a weaker result for this case. Furthermore, we show that a generalization to strictly Pareto optimal solutions is impossible, even in the convex case.