Rate of convergence for an estimator in a portfolio and consumption model

The rate of convergence in a sample path sense is given for a strongly consistent, recursive estimator. This estimator is for the unknown average return rate of the risky asset that is a parameter in a bilinear stochastic differential equation for the wealth in a portfolio selection and consumption model.This research was partially supported by NSF Grant No. ECS-84-03286-A01 and by University of Kansas General Research Allocation No. 3806-XO-0038.     

Adaptive control of a continuous-time portfolio and consumption model

In this paper, an adaptive control problem is formulated and solved using Merton's stochastic differential equation for the wealth in a portfolio selection and consumption model. Since the asset prices are assumed to satisfy a log normal distribution, it suffices to consider two assets. It is assumed that the drift parameter for the price of the risky asset is unknown. A recursive family of estimators for this unknown parameter is defined and is shown to converge almost surely to the true value of the parameter. The controls in the equation for the wealth are obtained from the optimal controls where the estimates of the unknown parameter are substituted for the unknown parameter.This research was partially supported by NSF Grant No. ECS-84-03286-A01.The authors wish to thank P. Varaiya for some useful comments on this paper.     

Adaptive control of three continuous-time portfolio and consumption models

An economic application of adaptive control is presented using three continuous time portfolio and consumption models that are natural generalizations of a model of Merton. In these models of the wealth of an individual investor, it is assumed that the various parameters are deterministic functions of time or stochastic processes. An adaptive control problem arises for each of these models when it is assumed that the average return rate of the risky asset, which is either a deterministic function or a stochastic process, is not observed. For these models, a recursive family of estimators of the average return rate of the risky asset is given based on the observations of the wealth. These estimates are used in the control of the wealth equation.This research was partially supported by NSF Grant No. ECS-84-03286-A01 and by University of Kansas General Research Allocation No. 3806-XO-0038.     

The efficient frontier for bounded assets

This paper develops a closed form solution of the mean-variance portfolio selection problem for uncorrelated and bounded assets when an additional technical assumption is satisfied. Although the assumption of uncorrelated assets is unduly restrictive, the explicit determination of the efficient asset holdings in the presence of bound constraints gives insight into the nature of the efficient frontier. The mean-variance portfolio selection problem considered here deals with the budget constraint and lower bounds or the budget constraint and upper bounds. For the mean-variance portfolio selection problem dealing with lower bounds the closed form solution is derived for two cases: a universe of only risky assets and a universe of risky assets plus an additional asset which is risk free. For the mean-variance portfolio selection problem dealing with upper bounds, the results presented are for a universe consisting only of risky assets. In each case, the order in which the assets are driven to their bounds depends on the ordering of their expected returns.     

Multi‐asset portfolio optimization with transaction cost

The inclusion of transaction costs in the optimal portfolio selection and consumption rule problem is accomplished via the use of perturbation analyses. The portfolio under consideration consists of more than one risky asset, which makes numerical methods impractical. The objective is to establish both the transaction and the no‐transaction regions that characterize the optimal investment strategy. The optimal transaction boundaries for two and three risky assets portfolios are solved explicitly. A procedure for solving the N risky assets portfolio is described. The formulation used also reduces the restriction on the functional form of the utility preference.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

A note on a theorem of Yamamuro

Conditions are presented which are necessary for the existence of a regular fixed point of aC ¹ map.Work supported in part by NSF Grant No. MCS 77-15509.Work supported in part by ONR Grant No. N0014-75-C-0495 and NSF Grant No. Eng. 76-81058.     

Analysis of heuristics for the design of tree networks

We analyze the tour partitioning heuristics for the Capacitated Minimum Spanning Tree problem. Lower bounds for the worst-case performance ratios of these heuristics are obtained by using worst-case examples. We also generalize the heuristics to the multi-center case with the same worst-case bounds.The work of the first author was supported by a Dean Summer Research Grant from Owen Graduate School of Management, Vanderbilt University.Work done in part in the Department of Industrial Engineering and Operations Research at Columbia University.The work of the last two authors was supported in part by ONR contract N00014-90-J-1649, NSF contract DDM-8922712 and the Center for Telecommunications Research under NSF contract CDR 84-21402.     

Rademacher complexity in Neyman-Pearson classification

Neyman-Pearson（NP） criterion is one of the most important ways in hypothesis testing. It is also a criterion for classification. This paper addresses the problem of bounding the estimation error of NP classification, in terms of Rademacher averages. We investigate the behavior of the global and local Rademacher averages, and present new NP classification error bounds which are based on the localized averages, and indicate how the estimation error can be estimated without a priori knowledge of the class at hand.     

Finding an interior point in the optimal face of linear programs

We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n ³ L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.Research supported in part by NSF Grant CCR-8810107, CCR-9019469 and a grant from GTE Laboratories.Research supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615 through Rice University.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

Quasi-planar graphs have a linear number of edges

A graph is calledquasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph withn vertices isO(n).Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995.     

Analysis of a linearization heuristic for single-machine scheduling to maximize profit

We consider the problem of schedulingn jobs without preemption on a single machine to maximize total profit, where profit is given by a nonincreasing, concave separable function of job starting times. A heuristic is given in which jobs are sequenced optimally relative to a specific linear approximation of the profit, function. This heuristic always obtains at least 2/3 of the optimal profit, and examples exist where the heuristic obtains only 2/3 of the optimal profit. A large class of alternative linearizations is considrred and shown to give arbitrarily bad results. Work supported in part by NSF Grant ECS 82-05438 to the University of Pennsylvania and ONR Contract N00014-81-C-0302.     

Static and dynamic VaR constrained portfolios with application to delegated portfolio management

We give a closed-form solution to the single-period portfolio selection problem with a Value-at-Risk (VaR) constraint in the presence of a set of risky assets with multivariate normally distributed returns and the risk-less account, without short sales restrictions. The result allows to obtain a very simple, myopic dynamic portfolio policy in the multiple period version of the problem. We also consider mean-variance portfolios under a probabilistic chance (VaR) constraint and give an explicit solution. We use this solution to calculate explicitly the bonus of a portfolio manager to include a VaR constraint in his/her portfolio optimization, which we refer to as the price of a VaR constraint.     

Strongly polynomial dual simplex methods for the maximum flow problem

This paper presents dual network simplex algorithms that require at most 2nm pivots and O(n ² m) time for solving a maximum flow problem on a network ofn nodes andm arcs. Refined implementations of these algorithms and a related simplex variant that is not strictly speaking a dual simplex algorithm are shown to have a complexity of O(n ³). The algorithms are based on the concept of apreflow and depend upon the use of node labels that are underestimates of the distances from the nodes to the sink node in the extended residual graph associated with the current flow. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research was supported by NSF Grants DMS 91-06195, DMS 94-14438 and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.Research was supported by NSF Grant CDR 84-21402 at Columbia University.     

A least-squares-based method for a class of nonsmooth minimization problems with applications in plasticity

This paper introduces a globally convergent algorithm for solving a class of nonsmooth optimization problems, involving square roots of quadratic forms. The class includes in particular limit analysis problems in plasticity. The algorithm combines smoothing with successive approximation. The main computational effort in each iteration is solving a linear weighted least-squares problem. The convergence of the algorithm is proved and ana priori error estimate is obtained. Numerical results are presented for two limit analysis problems.The work of the first author was partially supported by NSF Grant DDM-89-96112. Parts of the work was done during his stay at the University of Bayreuth as a guest of the DFG. The work of the second author was supported in part by the Air Force Office of Scientific Research under contract AFOSR-88-0218 and by a National Science Foundation Grant ECS-8802239 at the University of Maryland, Baltimore County Campus.     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

On Automorphic Tuples of Elements in Computable Models

A criterion is obtained for existence of two isomorphic but not hyperarithmetically isomorphic tuples in a hyperarithmetical model. This criterion is used to show that such a situation occurs in the models of well-known classes.Original Russian Text Copyright © 2005 Goncharov S. S., Harizanov V. S., Knight J. F., Morozov A. S., Romina A. V.The first four authors are supported by the Binational Grant NSF DMS-0075899; the first and fourth authors are partially supported by the Russian Foundation for Basic Research (Grant 02-01-00953) and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2112.03.1).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 3, pp. 523–532, May–June, 2005.     

Mean–Variance portfolio selection in presence of infrequently traded stocks

This paper deals with a mean–variance optimal portfolio selection problem in presence of risky assets characterized by low-frequency trading and, therefore, low liquidity. To model the dynamics of illiquid assets, we introduce pure-jump processes. This leads to the development of a portfolio selection model in a mixed discrete/continuous time setting. We pursue the twofold scope of analyzing and comparing either long-term investment strategies as well as short-term trading rules. The theoretical model is analyzed by applying extensive Monte Carlo experiments, in order to provide useful insights from a financial perspective.     

Finding minimum-cost flows by double scaling

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log logU) log(nC)) time on networks withn vertices,m edges, maximum arc capacityU, and maximum arc cost magnitudeC. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.Research partially supported by an NSF Presidential Young Investigator Fellowship, Contract 8451517ECS, and grants from Analog Devices, Apple Computer Inc., and Prime Computer.On leave from Indian Institute of Technology, Kanpur, India.Research partially supported by an NSF Presidential Young Investigator Award.Research at Princeton University partially supported by National Science Foundation Grant DCR-8605962 and Office of Naval Research Contract N00014-87-K-0467.