Integrated simulation and optimization models for tracking international fixed income indices

Portfolio managers in the international fixed income markets must address jointly the interest rate risk in each market and the exchange rate volatility across markets. This paper develops integrated simulation and optimization models that address these issues in a common framework. Monte Carlo simulation procedures generate jointly scenarios of interest and exchange rates and, thereby, scenarios of holding period returns of the available securities. The portfolio manager’s risk tolerance is incorporated either through a utility function or a (modified) mean absolute deviation function. The optimization models prescribe asset allocation weights among the different markets and also resolve bond-picking decisions. Therefore several interrelated decisions are cast in a common framework. Two models – an expected utility maximization and a mean absolute deviation minimization – are implemented and tested empirically in tracking a composite index of the international bond markets. Backtesting over the period January 1997 to July 1998 illustrate the efficacy of the optimization models in dealing with uncertainty and tracking effectively the volatile index. Of particular interest is the empirical demostration that the integrative models generate portfolios that dominate the portfolios obtained using classical disintegrated approaches. Received: November 24, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Simultaneously inpainting in image and transformed domains

In this paper, we focus on the restoration of images that have incomplete data in either the image domain or the transformed domain or in both. The transform used can be any orthonormal or tight frame transforms such as orthonormal wavelets, tight framelets, the discrete Fourier transform, the Gabor transform, the discrete cosine transform, and the discrete local cosine transform. We propose an iterative algorithm that can restore the incomplete data in both domains simultaneously. We prove the convergence of the algorithm and derive the optimal properties of its limit. The algorithm generalizes, unifies, and simplifies the inpainting algorithm in image domains given in Cai et al. (Appl Comput Harmon Anal 24:131–149, 2008) and the inpainting algorithms in the transformed domains given in Cai et al. (SIAM J Sci Comput 30(3):1205–1227, 2008), Chan et al. (SIAM J Sci Comput 24:1408–1432, 2003; Appl Comput Harmon Anal 17:91–115, 2004). Finally, applications of the new algorithm to super-resolution image reconstruction with different zooms are presented. R. H. Chan’s research was supported in part by HKRGC Grant 400505 and CUHK DAG 2060257. L. Shen’s research was supported by the US National Science Foundation under grant DMS-0712827. Z. Shen’s research was supported in part by Grant R-146-000-060-112 at the National University of Singapore.     

On The Span Of A Random Channel Assignment Problem

In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0, 1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2), and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a ‘phase change’ in this behaviour, depending on the probabilities for the different lengths.     

Universal Jensen＇s Equations in Banach Modules over a C^＊-Algebra and Its Unitary Group

In this paper, we prove the generalized Hyers-Ulam-Rassias stability of universal Jensen‘s equations in Banach modules over a unital C^*-algebra. It is applied to show the stability of universal Jensen‘s equations in a Hilbert module over a unital C^*-algebra. Moreover, we prove the stability of linear operators in a Hilbert module over a unital C^*-algebra.     

Preemptive scheduling with rejection

 We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection. Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002 Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084 Supported by the START program Y43-MAT of the Austrian Ministry of Science.     

A geometric analysis of Renegar’s condition number,and its interplay with conic curvature

For a conic linear system of the form Ax ∈K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar’s condition number is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry, and computational complexity of algorithms. Nonetheless, is a representation-dependent measure which is usually difficult to interpret and may lead to overly conservative bounds of computational complexity and/or geometric quantities associated with the set of feasible solutions. Herein we show that Renegar’s condition number is bounded from above and below by certain purely geometric quantities associated with A and K; furthermore our bounds highlight the role of the singular values of A and their relationship with the condition number. Moreover, by using the notion of conic curvature, we show how Renegar’s condition number can be used to provide both lower and upper bounds on the width of the set of feasible solutions. This complements the literature where only lower bounds have heretofore been developed.     

The complexity of detecting crossingfree configurations in the plane

The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.Klaus Jansen acknowledges support by the Deutsche Forschungsgemeinschaft. Gerhard J. Woeginger acknowledges support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

A proximal cutting plane method using Chebychev center for nonsmooth convex optimization

An algorithm is developed for minimizing nonsmooth convex functions. This algorithm extends Elzinga–Moore cutting plane algorithm by enforcing the search of the next test point not too far from the previous ones, thus removing compactness assumption. Our method is to Elzinga–Moore’s algorithm what a proximal bundle method is to Kelley’s algorithm. Instead of lower approximations used in proximal bundle methods, the present approach is based on some objects regularizing translated functions of the objective function. We propose some variants and using some academic test problems, we conduct a numerical comparative study with Elzinga–Moore algorithm and two other well-known nonsmooth methods.      

A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs

We consider a special class of two-stage stochastic integer programming problems with binary variables appearing in both stages. The class of problems we consider constrains the second-stage variables to belong to the intersection of sets corresponding to first-stage binary variables that equal one. Our approach seeks to uncover strong dual formulations to the second-stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. We demonstrate how these DPs can be formed by use of binary decision diagrams, which then yield traditional Benders inequalities that can be strengthened based on observations regarding the structure of the underlying DPs. We demonstrate the efficacy of our approach on a set of stochastic traveling salesman problems.

     

A non–interior predictor–corrector path following algorithm for the monotone linear complementarity problem

We present a predictor–corrector non–interior path following algorithm for the monotone linear complementarity problem based on Chen–Harker–Kanzow–Smale smoothing techniques. Although the method is modeled on the interior point predictor–corrector strategies, it is the first instance of a non–interior point predictor–corrector algorithm. The algorithm is shown to be both globally linearly convergent and locally quadratically convergent under standard hypotheses. The approach to global linear convergence follows the authors’ previous work on this problem for the case of (P ₀+R ₀) LCPs. However, in this paper we use monotonicity to refine our notion of neighborhood of the central path. The refined neighborhood allows us to establish the uniform boundedness of certain slices of the neighborhood of the central path under the standard hypothesis that a strictly positive feasible point exists. Received September 1997 / Revised version received May 1999?Published online December 15, 1999     

<Emphasis Type="Italic">q</Emphasis>-deformation of Witt-Burnside rings

In this paper, we construct a q-deformation of the Witt-Burnside ring of a profinite group over a commutative ring, where q ranges over the set of integers. When q = 1, it coincides with the Witt-Burnside ring introduced by Dress and Siebeneicher (Adv. Math. 70, 87–132 (1988)). To achieve our goal we first show that there exists a q-deformation of the necklace ring of a profinite group over a commutative ring. As in the classical case, i.e., the case q = 1, q-deformed Witt-Burnside rings and necklace rings always come equipped with inductions and restrictions. We also study their properties. As a byproduct, we prove a conjecture due to Lenart (J. Algebra. 199, 703-732 (1998)). Finally, we classify up to strict natural isomorphism in case where G is an abelian profinite group. The author gratefully acknowledges support from the following grants: KOSEF Grant # R01-2003-000-10012-0; KRF Grant # 2006-331-C00011.     

Extensions of covariantly finite subcategories

Gentle and Todorov proved that in an abelian category with enough projective objects, the extension subcategory of two covariantly finite subcategories is covariantly finite. We give an example to show that Gentle–Todorov’s theorem may fail in an arbitrary abelian category; however we prove a triangulated version of Gentle–Todorov’s theorem which holds for arbitrary triangulated categories; we apply Gentle–Todorov’s theorem to obtain short proofs of a classical result by Ringel and a recent result by Krause and Solberg. This project is partially supported by China Postdoctoral Science Foundation (No.s 20070420125 and 200801230). The author also gratefully acknowledges the support of K. C. Wong Education Foundation, Hong Kong.     

Approximation of analytic functions with prescribed boundary conditions by circle-packing maps

We use recent advances in circle-packing theory to develop a constructive method for the approximation of an analytic functionF: Ω →C by circle packing maps providing we have only been given ΩF’_dΩ, and the set of critical points ofF. This extends the earlier results of Carter and Rodin and of Colin de Verdière and Mathéus, for functionsF with no critical points. The author gratefully acknowledges support of the Tennessee Science Alliance and the National Science Foundation. Research at MSRI is supported in part by Grant No. DMS-9022140.     

Kantorovich’s majorants principle for Newton’s method

We prove Kantorovich’s theorem on Newton’s method using a convergence analysis which makes clear, with respect to Newton’s method, the relationship of the majorant function and the non-linear operator under consideration. This approach enables us to drop out the assumption of existence of a second root for the majorant function, still guaranteeing Q-quadratic convergence rate and to obtain a new estimate of this rate based on a directional derivative of the derivative of the majorant function. Moreover, the majorant function does not have to be defined beyond its first root for obtaining convergence rate results. The research of O.P. Ferreira was supported in part by FUNAPE/UFG, CNPq Grant 475647/2006-8, CNPq Grant 302618/2005-8, PRONEX–Optimization(FAPERJ/CNPq) and IMPA. The research of B.F. Svaiter was supported in part by CNPq Grant 301200/93-9(RN) and by PRONEX–Optimization(FAPERJ/CNPq).     

Lower and upper regularizations of frame semicontinuous real functions

As discovered recently, Li and Wang’s 1997 treatment of semicontinuity for frames does not faithfully reflect the classical concept. In this paper we continue our study of semicontinuity in the pointfree setting. We define the pointfree concepts of lower and upper regularizations of frame semicontinuous real functions. We present characterizations of extremally disconnected frames in terms of these regularizations that allow us to reprove, in particular, the insertion and extension type characterizations of extremally disconnected frames due to Y.-M. Li and Z.-H. Li [Algebra Universalis 44 (2000), 271–281] in the right semicontinuity context. It turns out that the proof of the insertion theorem becomes very easy after having established a number of basic results regarding the regularizations. Notably, our extension theorem is a much strengthened version of Li and Li's result and it is proved without making use of the insertion theorem. The first and second named authors acknowledge financial support from the Ministry of Education and Science of Spain and FEDER under grant MTM2006-14925-C02-02. The first named author also acknowledges financial support from the University of the Basque Country under grant UPV05/101. The third named author acknowledges financial support from the Centre of Mathematics of the University of Coimbra/FCT.     

Exact order of Hoffman’s error bounds for elliptic quadratic inequalities derived from vector-valued Chebyshev approximation

In this paper, we introduce the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities. Elliptic quadratic inequalities are closely related to Chebyshev approximation of vector-valued functions (including complex-valued functions). The set of Chebyshev approximations of a vector-valued function defined on a finite set is shown to be Hausdorff strongly unique of order exactly 2 ^s for some nonnegative integer s. As a consequence, the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities is exactly 2 ^-s for some nonnegative integer s. The integer s, called the order of deficiency (which is computable), quantifies how much the Abadie constraint qualification is violated by the elliptic quadratic inequalities. Received: April 15, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

Two-stage stochastic programming under multivariate risk constraints with an application to humanitarian relief network design

In this study, we consider two classes of multicriteria two-stage stochastic programs in finite probability spaces with multivariate risk constraints. The first-stage problem features multivariate stochastic benchmarking constraints based on a vector-valued random variable representing multiple and possibly conflicting stochastic performance measures associated with the second-stage decisions. In particular, the aim is to ensure that the decision-based random outcome vector of interest is preferable to a specified benchmark with respect to the multivariate polyhedral conditional value-at-risk or a multivariate stochastic order relation. In this case, the classical decomposition methods cannot be used directly due to the complicating multivariate stochastic benchmarking constraints. We propose an exact unified decomposition framework for solving these two classes of optimization problems and show its finite convergence. We apply the proposed approach to a stochastic network design problem in the context of pre-disaster humanitarian logistics and conduct a computational study concerning the threat of hurricanes in the Southeastern part of the United States. The numerical results provide practical insights about our modeling approach and show that the proposed algorithm is computationally scalable.

     

Computing Minimal Forecast Horizons:An Integer Programming Approach

In this paper, we use integer programming (IP) to compute minimal forecast horizons for the classical dynamic lot-sizing problem (DLS). As a solution approach for computing forecast horizons, integer programming has been largely ignored by the research community. It is our belief that the modelling and structural advantages of the IP approach coupled with the recent significant developments in computational integer programming make for a strong case for its use in practice. We formulate some well-known sufficient conditions, and necessary and sufficient conditions (characterizations) for forecast horizons as feasibility/optimality questions in 0–1 mixed integer programs. An extensive computational study establishes the effectiveness of the proposed approach.     

Dominance-based Rough Set Approach to decision under uncertainty and time preference

We consider a problem of decision under uncertainty with outcomes distributed over time. We propose a rough set model based on a combination of time dominance and stochastic dominance. For the sake of simplicity we consider the case of traditional additive probability distribution over the set of states of the world, however, we show that the model is rich enough to handle non-additive probability distributions, and even qualitative ordinal distributions. The rough set approach gives a representation of decision maker’s time-dependent preferences under uncertainty in terms of “if…, then…” decision rules induced from rough approximations of sets of exemplary decisions.