# Discrete Analysis of Portfolio Selection with Optimal Stopping Time

Authors: Jianfeng Liang
Journal: Journal of Applied Mathematics and Decision Sciences
 (2009)

---

## Abstract

Most of the investments in practice are carried out without certain horizons. There are many factors to drive investment to a stop. In this paper, we consider a portfolio selection policy with market-related stopping time. Particularly, we assume that the investor exits the market once his wealth reaches a given investment target or falls below a bankruptcy threshold. Our objective is to minimize the expected time when the investment target is obtained, at the same time, we guarantee the probability that bankruptcy happens is no larger than a given level. We formulate the problem as a mix integer linear programming model and make analysis of the model by using a numerical example.


---

## Body

## 1. Introduction

Portfolio theory deals with the
question of how to find an optimal policy to invest among various assets. The mean-variance
analysis of Markowitz [1, 2] plays a key role in the theory of portfolio selection,
which quantifies the return and the risk in computable terms. The mean-variance
model is
later extended to the multistage dynamic case. For this and other expected
utility-maximization models in dynamic portfolio selection, one is referred to Dumas
and Luciano [3], Elton and Gruber [4], Li and Ng [5], Merton [6], and Mossion [7].An important assumption of the previous portfolio
selection model is that the investment horizon is definite. That means an investor knows with certainty the exit
time at the beginning of the investment. However, most of the investments in
practice are carried out
without certain horizons. There are many factors, related to the market or not,
which can drive the investment stop. For example, sudden huge consumption,
serious illness, and retirement are market-unrelated reasons. Also, those
market-related reasons may more strongly affect the investment horizon. A
natural example is that the investor may exit the market once his wealth reaches
an investment target, which is closely related to the market and also the
investment policy itself. Because of the disparity between theory and practice,
it seems sympathetic to relax the restrictive assumption that the investment
horizon is preknown with certainty.Research on this subject has been investigated in continuous
setting. Yaari [8] first deals
with the problem of optimal consumption for an individual with uncertain date
of death, under a pure deterministic investment environment. In 2000, Karatzas and Wang [9] address the optimal dynamic
investment problem in a complete market with assumption that the uncertain
investment horizon is a stopping time of asset price filtration. Multiperiod
mean-variance portfolio optimization problem with uncertain exit time is
studied by Guo and Hu [10], where the uncertain exit
time is market unrelated. A continuous time problem with minimizing the
expected time to beat a benchmark is addressed in Browne [11, 12], where the exit time is a random
variable related to the portfolio. Literatures of portfolio selection focus on
the case that the stopping time is market-state independent. While, the
state-dependent exogenous stopping time is considered by Blanchet-Scalliet et al. [13] in dynamic asset pricing theory.In this paper, we consider a portfolio selection problem
with endogenous stopping time in
discrete framework, which has not been well discussed in literatures.
Specially, we assume that the investor exits the market once his wealth hits an
investment target or he is bankrupt. This assumption actually reflects most investors’ investment
behavior in real life. Our objective is to minimize the expected time that the
investment target is obtained, at the same time we guarantee that the probability of which bankruptcy happens is no larger than a given threshold. The investment process is
represented by a multistage scenarios tree, in which the discrete stages and
notes denote the decision time points and the market states, respectively.The rest part of the paper is organized as follows. In
Section2, we introduce the statement of the problem, including notations and
the general form of the
problem. Following, Section 3 is devoted to derive the deterministic
formulation of the problem, in which we define a
list of integer variables to indicate different states
during the investment process. Finally, we make analysis of the model by using a numerical example in Section 4.


## 2. The Problem Statement

Consider the following investment
problem. We distribute the investment budget among a set of assets, and the portfolio
can be adjusted at several discrete decision time points during the investment process.
At the beginning of the investment, we assign a target wealth and also a bankruptcy
threshold. Our objective is to obtain this target wealth and stop the
investment as soon as possible. At the same time, we also need to avoid that
the bankruptcy occurs before the target wealth obtained.The problem is
based on a finite multistage scenarios tree structure. Our portfolio includes a
set ofm assets. The underlying dynamic scenarios tree
is constructed as follows. There are T stages denoted from time 0 to T.
The portfolios can be constructed at the beginning of each stage in the scenarios
tree. We denote Nt to
be the index set of the scenarios at time t,
and Snt as
the nth scenario at time t,
for n∈Nt,t=0,1,…,T.
For those data at this scenario, the price vector of the risky assets is
denoted by unt∈ℜm,
and the payoff vector of the assets is denoted by vnt∈ℜm.
The decision variables at this scenario are the number of shares of holdings of
the assets xnt∈ℜm.
We denote the wealth at this scenario to be Wnt, and the initial wealth to be B.
We denote a(n) and c(n) as the parent node and the children nodes of
node n,
respectively. Moreover, let Sa(n),t−1 be
the parent scenario of Snt,
and Sc(n),t+1 be the
set of immediate children of Snt.
The probability of scenario Snt happens
is pnt.We consider an objective related to the
achievement of performance goal and bankruptcy. The investment stops once the
goal is reached or the bankruptcy occurs,
the related stopping time is
denoted astu and tl, respectively. Specifically, for given wealth
levels l and u,
with l<B<u,
we say that the performance goal u is reached if Wnt≥u,
denoting this time as tu, that is, tu=inf{t>0;Wnt≥u};
that the bankruptcy occurs if Wnt<l,
denoting this time as tl, that is, tl=inf{t>0;Wnt<l}.
Our objective is to minimize the expected time that the goal is reached, at the
same time we guarantee the probability that the bankruptcy happens before the goal is reached is no more than a
given level, say q, 0<q<1. Thus, the investment problem can be represented in the general form (M)minE[tu]s.t.P(W<l)≤qbudgetconstraintst∈{0,1,2,…,T},where
the first constraint is a probability constraint of bankruptcy, in which W generally represents the realized wealth by
investment. Moreover,
the budget constraints are the wealth dynamics during the investment horizon.
We will continue the discussion on the determistic formulation of the model in Section 3.


## 3. The Problem Formulation

In this section, we will derive
the deterministic formulation of the problem (M). Most efforts are devoted to
present the objective function and the probability constraint. Actually, we do
this by introducing a list of indicator variables. Before we start this work,
let us first
consider the budget constraints first.


### 3.1. The Budget Constraints

Based on the previously given
notations on the scenarios tree, we first have the allocation of the initial investment
wealth
represented asB=u0′x0.
At scenario Snt,n∈Nt,t=0,1,…,T, the
wealth Wnt should be the realized payoff during the
previous period, that is, (3.1)Wnt=vnt′xa(n),t−1.Also, for a self-financing process that we are
considering here, the realized
wealth will be reinvested at this decision point, which means(3.2)Wnt=unt′xnt.Therefore, we
conclude the budget constraints at scenarioSnt,n∈Nt,t=0,1,…,T,
by the set of equations as follows: (3.3)u0′x0=B,vnt′xa(n),t−1=unt′xnt,n∈Nt,t=1,2,…,T.


### 3.2. The Objective and The Probability Constraint

We come to the formulation of the
objective function and the probability constraint. Let us consider the
investment process. There are basically three different outputs at a given scenarioSnt.
The first one is that we succeed to obtain the target wealth and stop the
investment on this scenario, and this is really the objective. The second one is
that we unfortunately fall into bankruptcy on this scenario and have to exit
the investment. In either case, we cannot restart it again. In addition to the
above two cases, the investment may be continued to next period.Now, we define two 0-1 variables to
describe the investment story. On scenarioSnt,n∈Nt,t=0,1,…,T, first
define εnt∈{0,1} such that (3.4)εnt={1,Wnt≥u,1≤Wa(n),j<u,∀j<t,0,otherwise.Parallel toεnt, we define ηnt∈{0,1} such that (3.5)ηnt={1,Wnt<l,l≤Wa(n),j<u,∀j<t,0,otherwise.Reading
the definitions,εnt=1 indicates the first case, where the investment reaches the target and stops at
scenario Snt, and ηnt=1 represents the second case that bankruptcy happens at scenario Snt. By using εnt and ηnt, we can write our
objective as (3.6)E[tu]=∑t=0T(t⋅∑n∈Ntpntεnt),   and
the deterministic form of the probability as (3.7)P(W<l)=∑t=0T∑n∈Ntpntηnt≤q.We consider again the indicator
variablesεnt and ηnt.
Their values on scenario Snt actually depend on both the current state
and also all of the ancestor states. Take εnt as an example, εnt=1 holds if and only if the following
two conditions are both satisfied. One is that the investment continues to the
current scenario, and the other is that the payoff at the current scenario is no
less than the target wealth. If either of the above conditions is not achieved,
we should get εnt=0.
Moreover, the case of ηnt is for the same logic but about the bankruptcy part.
Thus, we introduce
another two sets of variables to track the current state and the historical
states separately.For the current state, we defineδnt,ξnt∈{0,1} as follows: (3.8)δnt={1,Wnt≥u,0,Wnt<u,ξnt={1,Wnt<l,0,Wnt≥l,  and for the ancestor
states, we define ϕnt∈{0,1} such that (3.9)ϕnt={1,l≤Wa(n),j<u,∀j<t,0,otherwise,   where ϕnt=1 means that the investment has kept going on
to the current scenario and ϕnt=0 means that it has stopped on the parent scenario
or other ancestor scenarios before.Combine the above definitions and reviewεnt and ηnt, we realize the
relations (3.10)εnt=δnt⋅ϕnt,ηnt=ξnt⋅ϕnt.If we replace these nonlinear constraints by a set of linear
constraints, then the problem can be hopefully formulated
as a linear programming problem,
which will benefit for the further research on solution methods and
applications. Since the indicator variables are all defined as binary 0-1 variables,
we derive the transformation(3.11)εnt=δnt⋅ϕnt⟺{δnt+ϕnt−εnt≤1,δnt+ϕnt−2εnt≥0.It is direct to check that for given values of{δnt,ϕnt}, εnt must realize the same value either by εnt=δnt⋅ϕnt or by the constraints (3.12)δnt+ϕnt−εnt≤1,δnt+ϕnt−2εnt≥0,   and similar case for ηnt, (3.13)ηnt=ξnt⋅ϕnt⟺{ξnt+ϕnt−ηnt≤1,ξnt+ϕnt−2ηnt≥0.Therefore, we now
replace (3.10) by the following set of inequalities: (3.14)δnt+ϕnt−εnt≤1,δnt+ϕnt−2εnt≥0,ξnt+ϕnt−ηnt≤1,ξnt+ϕnt−2ηnt≥0.Up to now, we have almost derived out the
formulation of the model based on a series of indicator variables, includingε,η,δ,ξ,ϕ.
The remaining task is to construct the dynamics of ϕnt and also the constraints of δnt and ξnt, so that the definitions
here can be implemented in the model.


### 3.3. The Dynamics of Indicator Variables

Consider the constraints ofδnt and ξnt first. Given a large enough number M1>u and a small enough number M2<l, we have for δnt, (3.15)δnt={1,Wnt≥u,0,Wnt<u,⟺{Wnt−(M1−u)⋅δnt<u,Wnt+(u−M2)⋅(1−δnt)≥u   and for ξnt, we have (3.16)ξnt={1,Wnt<l,0,Wnt≥l,⟺{Wnt−(M1−l)⋅(1−ξnt)<l,Wnt+(l−M2)⋅ξnt≥l.We
combine the constraints ofδnt and ξnt as the constraint set (3.17)Wnt−(M1−u)⋅δnt<u,Wnt+(u−M2)(1−δnt)≥u,Wnt−(M1−l)(1−ξnt)<l,Wnt+(l−M2)⋅ξnt≥l.Next,
let us focus on the dynamics ofϕnt.
At the beginning point of the investment, ϕ0=1 holds. During the
investment process, we first write out the dynamics and then explain the underlying
reasons: (3.18)ϕ0=1,ϕnt=ϕa(n),t−1−(εa(n),t−1+ηa(n),t−1).The dynamic equation holds
for the following reasons.First, suppose
the investment has been continued to the scenarioSa(n),t−1 and
does not stop at that scenario, which
means we already held ϕa(n),t−1=1, and εa(n),t−1=ηa(n),t−1=0, then, the investment must keep
going on to the current scenario Snt. In this case, we should have ϕnt=1 base
on the definition of ϕ.
The recursive equation in (3.18) succeeds to realize this case and gives ϕnt=1−0=1.Second, if the investment has stopped, either on
the parent scenarioSa(n),t−1 or
on any of the ancestor scenarios before, we should hold ϕnt=0.
This case can also be realized
by the dynamic equation (3.18). In
case that the investment stopped on the parent scenario Sa(n),t−1,
that is, ϕa(n),t−1=1,
and either εa(n),t−1=1 or ηa(n),t−1=1,
then (3.18) gives ϕnt=0;
in the other case of stopping before the previous stage, we
already had ϕa(n),t−1=0,
also both εa(n),t−1=0 and ηa(n),t−1=0, the result of (3.18) is still ϕnt=0.


### 3.4. The Deterministic Formulation

Now, we have derived all the constraints of
the indicator variables by (3.3), (3.14), (3.17), (3.18). Together with the objective
function and the probability constraint represented by (3.6) and (3.7), respectively,
the problem (M) can be finally written as a mix integer linear programming
problem: (P)min∑t=1T(t⋅∑n∈Ntpntεnt)s.t.∑t=1T∑n∈Ntpntηnt≤q(3.3),(3.14),(3.17),(3.18)εnt,ηnt,δnt,ξnt,ϕnt∈{0,1},n∈Nt,t∈{1,2,…,T}.Next, we construct an example to analyze the model and illustrate
the solving process. The problem is input by an MATLAB program, and numerically solved by using Cplex software.


## 3.1. The Budget Constraints

Based on the previously given
notations on the scenarios tree, we first have the allocation of the initial investment
wealth
represented asB=u0′x0.
At scenario Snt,n∈Nt,t=0,1,…,T, the
wealth Wnt should be the realized payoff during the
previous period, that is, (3.1)Wnt=vnt′xa(n),t−1.Also, for a self-financing process that we are
considering here, the realized
wealth will be reinvested at this decision point, which means(3.2)Wnt=unt′xnt.Therefore, we
conclude the budget constraints at scenarioSnt,n∈Nt,t=0,1,…,T,
by the set of equations as follows: (3.3)u0′x0=B,vnt′xa(n),t−1=unt′xnt,n∈Nt,t=1,2,…,T.


## 3.2. The Objective and The Probability Constraint

We come to the formulation of the
objective function and the probability constraint. Let us consider the
investment process. There are basically three different outputs at a given scenarioSnt.
The first one is that we succeed to obtain the target wealth and stop the
investment on this scenario, and this is really the objective. The second one is
that we unfortunately fall into bankruptcy on this scenario and have to exit
the investment. In either case, we cannot restart it again. In addition to the
above two cases, the investment may be continued to next period.Now, we define two 0-1 variables to
describe the investment story. On scenarioSnt,n∈Nt,t=0,1,…,T, first
define εnt∈{0,1} such that (3.4)εnt={1,Wnt≥u,1≤Wa(n),j<u,∀j<t,0,otherwise.Parallel toεnt, we define ηnt∈{0,1} such that (3.5)ηnt={1,Wnt<l,l≤Wa(n),j<u,∀j<t,0,otherwise.Reading
the definitions,εnt=1 indicates the first case, where the investment reaches the target and stops at
scenario Snt, and ηnt=1 represents the second case that bankruptcy happens at scenario Snt. By using εnt and ηnt, we can write our
objective as (3.6)E[tu]=∑t=0T(t⋅∑n∈Ntpntεnt),   and
the deterministic form of the probability as (3.7)P(W<l)=∑t=0T∑n∈Ntpntηnt≤q.We consider again the indicator
variablesεnt and ηnt.
Their values on scenario Snt actually depend on both the current state
and also all of the ancestor states. Take εnt as an example, εnt=1 holds if and only if the following
two conditions are both satisfied. One is that the investment continues to the
current scenario, and the other is that the payoff at the current scenario is no
less than the target wealth. If either of the above conditions is not achieved,
we should get εnt=0.
Moreover, the case of ηnt is for the same logic but about the bankruptcy part.
Thus, we introduce
another two sets of variables to track the current state and the historical
states separately.For the current state, we defineδnt,ξnt∈{0,1} as follows: (3.8)δnt={1,Wnt≥u,0,Wnt<u,ξnt={1,Wnt<l,0,Wnt≥l,  and for the ancestor
states, we define ϕnt∈{0,1} such that (3.9)ϕnt={1,l≤Wa(n),j<u,∀j<t,0,otherwise,   where ϕnt=1 means that the investment has kept going on
to the current scenario and ϕnt=0 means that it has stopped on the parent scenario
or other ancestor scenarios before.Combine the above definitions and reviewεnt and ηnt, we realize the
relations (3.10)εnt=δnt⋅ϕnt,ηnt=ξnt⋅ϕnt.If we replace these nonlinear constraints by a set of linear
constraints, then the problem can be hopefully formulated
as a linear programming problem,
which will benefit for the further research on solution methods and
applications. Since the indicator variables are all defined as binary 0-1 variables,
we derive the transformation(3.11)εnt=δnt⋅ϕnt⟺{δnt+ϕnt−εnt≤1,δnt+ϕnt−2εnt≥0.It is direct to check that for given values of{δnt,ϕnt}, εnt must realize the same value either by εnt=δnt⋅ϕnt or by the constraints (3.12)δnt+ϕnt−εnt≤1,δnt+ϕnt−2εnt≥0,   and similar case for ηnt, (3.13)ηnt=ξnt⋅ϕnt⟺{ξnt+ϕnt−ηnt≤1,ξnt+ϕnt−2ηnt≥0.Therefore, we now
replace (3.10) by the following set of inequalities: (3.14)δnt+ϕnt−εnt≤1,δnt+ϕnt−2εnt≥0,ξnt+ϕnt−ηnt≤1,ξnt+ϕnt−2ηnt≥0.Up to now, we have almost derived out the
formulation of the model based on a series of indicator variables, includingε,η,δ,ξ,ϕ.
The remaining task is to construct the dynamics of ϕnt and also the constraints of δnt and ξnt, so that the definitions
here can be implemented in the model.


## 3.3. The Dynamics of Indicator Variables

Consider the constraints ofδnt and ξnt first. Given a large enough number M1>u and a small enough number M2<l, we have for δnt, (3.15)δnt={1,Wnt≥u,0,Wnt<u,⟺{Wnt−(M1−u)⋅δnt<u,Wnt+(u−M2)⋅(1−δnt)≥u   and for ξnt, we have (3.16)ξnt={1,Wnt<l,0,Wnt≥l,⟺{Wnt−(M1−l)⋅(1−ξnt)<l,Wnt+(l−M2)⋅ξnt≥l.We
combine the constraints ofδnt and ξnt as the constraint set (3.17)Wnt−(M1−u)⋅δnt<u,Wnt+(u−M2)(1−δnt)≥u,Wnt−(M1−l)(1−ξnt)<l,Wnt+(l−M2)⋅ξnt≥l.Next,
let us focus on the dynamics ofϕnt.
At the beginning point of the investment, ϕ0=1 holds. During the
investment process, we first write out the dynamics and then explain the underlying
reasons: (3.18)ϕ0=1,ϕnt=ϕa(n),t−1−(εa(n),t−1+ηa(n),t−1).The dynamic equation holds
for the following reasons.First, suppose
the investment has been continued to the scenarioSa(n),t−1 and
does not stop at that scenario, which
means we already held ϕa(n),t−1=1, and εa(n),t−1=ηa(n),t−1=0, then, the investment must keep
going on to the current scenario Snt. In this case, we should have ϕnt=1 base
on the definition of ϕ.
The recursive equation in (3.18) succeeds to realize this case and gives ϕnt=1−0=1.Second, if the investment has stopped, either on
the parent scenarioSa(n),t−1 or
on any of the ancestor scenarios before, we should hold ϕnt=0.
This case can also be realized
by the dynamic equation (3.18). In
case that the investment stopped on the parent scenario Sa(n),t−1,
that is, ϕa(n),t−1=1,
and either εa(n),t−1=1 or ηa(n),t−1=1,
then (3.18) gives ϕnt=0;
in the other case of stopping before the previous stage, we
already had ϕa(n),t−1=0,
also both εa(n),t−1=0 and ηa(n),t−1=0, the result of (3.18) is still ϕnt=0.


## 3.4. The Deterministic Formulation

Now, we have derived all the constraints of
the indicator variables by (3.3), (3.14), (3.17), (3.18). Together with the objective
function and the probability constraint represented by (3.6) and (3.7), respectively,
the problem (M) can be finally written as a mix integer linear programming
problem: (P)min∑t=1T(t⋅∑n∈Ntpntεnt)s.t.∑t=1T∑n∈Ntpntηnt≤q(3.3),(3.14),(3.17),(3.18)εnt,ηnt,δnt,ξnt,ϕnt∈{0,1},n∈Nt,t∈{1,2,…,T}.Next, we construct an example to analyze the model and illustrate
the solving process. The problem is input by an MATLAB program, and numerically solved by using Cplex software.


## 4. An Example

The
investment process is represented by a 3-stage triple tree, noted from time 1
to time 4, as showed in Figure1. The portfolio can be organized and
reorganized at the beginning of each stage. We simply consider a portfolio of
two assets, and the prices on each decision point are given. Also, the
conditional probabilities of the three notes in any single-stage subtree are P={.3,.36,.34} in order. For other essential constants, we assume the
initial budget B=$100,
the target payoff u=$104,
and the bancruptcy banchmark l=$95.
In addition, we take M1=10000 and M2=−10000 as those two large enough numbers for
formulating the problem. Finally, we assign the largest accetable bancruptcy
probability to be q=0.2.Figure 1
The scenario tree of example.Cplex takes 0.41 second to optimize the problem. Reading the
solution file, we find that there are chances to obtain the payoff target
before the investment horizon, as clearly as in the third stage on the scenarios of{S1,3,S8,3}, respectively. Accordingly, the bankruptcy
possibly happens on the third and the fourth stages, on the scenarios of {S4,3,S19,4,S27,4}, which makes the total probability of
bankruptcy is 0.178. Details of selected optimal solutions are shown in Table 1. Other solutions are also carefully checked, it turns out that the
construction of indicator variables does work. For example, on the children
scenarios of the stopping scenarios {S1,3,S8,3,S4,3},
the values of ϕ are all zero as the investment has been
stopped before.Table 1
The selected solutions of example.
Time 1Time 2Time 3Time 4Payoff target obtainedScenarioNoneNoneS1,3S8,3NoneSolutionε1,3=1ε8,3=1δ1,3=1δ8,3=1ϕ1,3=1ϕ8,3=1Bankruptcy happensScenarioNoneNoneS4,3S19,4S27,4Solutionη4,3=1η19,4=1η27,4=1ξ4,3=1ξ19,4=1ξ27,4=1ϕ4,3=1ϕ19,4=1ϕ27,4=1For two-stage problem, there are well-known algorithms
such as branch-and-bound, Lagrangian relaxation, or cutting plane methods for
solving it. When we extend it into the multistage case, as we are doing now,
the problem becomes much more complex.
As the size of the problem increases,
the existing solution methods become less efficient. We will further investigate on more applicable solution methodologies. In
addition to the solution methodology, another
relevant research topic is to compare the investment policies under
different objectives and risk constraints.



---

*Source: 609196-2009-04-05.xml*