# Stochastic Separated Continuous Conic Programming: Strong Duality and a Solution Method

Authors: Xiaoqing Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We study a new class of optimization problems calledstochastic separated continuous conic programming (SSCCP). SSCCP is an extension to the optimization model called separated continuous conic programming (SCCP) which has applications in robust optimization and sign-constrained linear-quadratic control. Based on the relationship among SSCCP, its dual, and their discretization counterparts, we develop a strong duality theory for the SSCCP. We also suggest a polynomial-time approximation algorithm that solves the SSCCP to any predefined accuracy.


---

## Body

## 1. Introduction

Stochastic programming is one of the branches of optimization which enjoys a fast development in recent years. It tries to find optimal decisions in problems involving uncertain data, so it is also called “optimization under uncertainty” [1]. Since the problems in reality often involve uncertain data, stochastic programming has a lot of applications.Many deterministic optimization models have their stochastic counterpart; for example, the stochastic counterpart of linear programming is stochastic linear programming. In this paper, we consider the stochastic counterpart of a kind of optimization model calledseparated continuous conic programming (SCCP) which has the following form:
(1)
(
SCCP
)
max
∫
0
T
‍
[
(
γ
+
(
T
-
t
)
c
)
′
u
(
t
)
+
d
′
x
(
t
)
]
d
t
(
SCCP
)
s
.
t
.
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
∈
𝒦
1
,
(
SCCP
)
s
.
t
.
b
-
H
u
(
t
)
∈
𝒦
2
,
(
SCCP
)
s
.
t
.
u
(
t
)
∈
𝒦
3
,
x
(
t
)
∈
𝒦
4
,
t
∈
[
0
,
T
]
.
Here the control and state variables (both are decision variables), u
(
t
) and x
(
t
), are vectors of bounded measurable functions of time t
∈
[
0
,
T
]. 𝒦
i, i
=
1,2
,
3,4, are closed convex cones in the Euclidean space with appropriate dimensions, γ
,
c
,
d
,
α
,
a
,
b are vectors, G
,
F
,
H are matrices, and the superscript ′ denotes the transpose operation.SCCP was first studied by Wang et al. [2]. They developed a strong duality theory for SCCP under some mild and verifiable conditions and suggested an approximation algorithm to solve SCCP with predefined precision. SCCP has a variety of applications in robust optimization and sign-constrained linear-quadratic control. However, many applications of SCCP are stochastic in nature in the sense that the values of some parameters in the resulted SCCP models may change over time with some probability distribution. To incorporate this kind of randomness into the SCCP model, we introduce the following stochastic counterpart of SCCP which we call stochastic separated continuous conic programming (SSCCP) problem:
(2)
max
∫
0
T
1
‍
[
(
γ
+
(
T
-
t
)
c
)
′
u
(
t
)
+
d
′
x
(
t
)
]
d
t
+
E
ξ
(
∫
T
1
T
2
‍
[
(
γ
(
ξ
)

+

(
T
-
t
)
c
(
ξ
)
)
′
u
(
t
)


+


d
(
ξ
)
′
x
(
t
)
]

d
t

)
s
.
t
.
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
∈
𝒦
1
,
t
∈
[
0
,
T
1
]
,
b
-
H
u
(
t
)
∈
𝒦
2
,
t
∈
[
0
,
T
1
]
,
u
(
t
)
∈
𝒦
3
,
x
(
t
)
∈
𝒦
4
,
t
∈
[
0
,
T
1
]
,
α
+
T
1
a
+
(
t
-
T
1
)
a
(
ξ
)
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
∈
𝒦
(
ξ
)
1
,
-
∫
T
1
t
‍
G
u
(
s
)
d
s
-
F
x
t
∈
[
T
1
,
T
2
]
,
b
(
ξ
)
-
H
u
(
t
)
∈
𝒦
(
ξ
)
2
,
t
∈
[
T
1
,
T
2
]
,
u
(
t
)
∈
𝒦
(
ξ
)
3
,
x
(
t
)
∈
𝒦
(
ξ
)
4
,
t
∈
[
T
1
,
T
2
]
,
where ξ is a random variable.SSCCP is formulated with the similar idea as that of the stochastic linear programming [1, 3]. There are two stages in this problem; the values of some parameters in the second stage depend on the value of a random variable ξ.Our goal in this paper is developing the strong duality forSSCCP and suggesting a solution method to solve it approximately with predefined precision. Here is a summary of our main results. Through discretization, we connect SSCCP and its dual to two ordinary conic programs, and we show that strong duality holds for SSCCP and its dual under some mild (and verifiable) conditions on these two ordinary conic programs. Furthermore, the optimal values of those two conic programs provide an explicit bound on the duality gap between SSCCP and its dual, based on which we suggest a polynomial-time approximation algorithm that solves SSCCP to any predefined accuracy. According to our knowledge, we are the first to raise the SSCCP model and there have been no other results on SSCCP besides those in this paper.The paper is organized as follows. In Section2, we present an overview on the related literature. We also give a concrete example to show the application of SSCCP. In Section 3, we construct a dual for SSCCP. We also discretize S
SCCP and its dual into two ordinary conic programs, and bring out their relations. In Section 4, we discuss the strong feasibility for SSCCP, its dual, and their discretizations. We then establish the strong duality result for SSCCP and its dual in Section 5. This leads to a polynomial-time approximation algorithm with an explicit error bound, detailed in Section 6. In Section 7, we summarize what we get for SSCCP and point out some future research directions.For simpler presentation, in the remainder of this paper, we will concentrate on the following problem, which is the correspondingSSCCP when ξ is a discrete variable and only takes two different values with probability θ and 1
-
θ, that is, there are only two scenarios in the second stage of SSCCP:
(3)
max
∫
0
T
1
‍
[
(
γ
+
(
T
-
t
)
c
)
′
u
(
t
)
+
d
′
x
(
t
)
]
d
t
+
∫
T
1
T
‍
[
(
γ
˘
1
+
(
T
-
t
)
c
˘
1
)
′
v
(
t
)
+
d
˘
1
′
y
(
t
)
]
d
t
+
∫
T
1
T
‍
[
(
γ
˘
2
+
(
T
-
t
)
c
˘
2
)
′
w
(
t
)
+
d
˘
2
′
z
(
t
)
]
d
t
s
.
t
.
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
∈
𝒦
1
,
t
∈
[
0
,
T
1
]
,
b
-
H
u
(
t
)
∈
𝒦
2
,
t
∈
[
0
,
T
1
]
,
u
(
t
)
∈
𝒦
3
,
x
(
t
)
∈
𝒦
4
,
t
∈
[
0
,
T
1
]
,
α
1
+
t
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
v
(
s
)
d
s
-
F
y
(
t
)
∈
𝒦
11
,
t
∈
(
T
1
,
T
]
,
b
1
-
H
v
(
t
)
∈
𝒦
21
,
t
∈
(
T
1
,
T
]
,
v
(
t
)
∈
𝒦
31
,
y
(
t
)
∈
𝒦
41
,
t
∈
(
T
1
,
T
]
,
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
(
s
)
d
s
-
F
z
(
t
)
∈
𝒦
12
,
-
∫
T
1
t
‍
G
w
(
s
)
d
s
-
F
t
∈
(
T
1
,
T
]
,
b
2
-
H
w
(
t
)
∈
𝒦
22
,
t
∈
(
T
1
,
T
]
,
w
(
t
)
∈
𝒦
32
,
z
(
t
)
∈
𝒦
42
,
t
∈
(
T
1
,
T
]
,
where the first-stage control and state variables are u
(
t
) and x
(
t
), t
∈
[
0
,
T
1
], and the second-stage control and state variables are v
(
t
)
,
w
(
t
), y
(
t
), and z
(
t
), t
∈
(
T
1
,
T
]. Also  α
1
=
α
+
T
1
a
-
T
1
a
1, α
2
=
α
+
T
1
a
-
T
1
a
2, γ
˘
1
=
θ
γ
1, c
˘
1
=
θ
c
1, d
˘
1
=
θ
d
1, γ
˘
2
=
(
1
-
θ
)
γ
2, c
˘
2
=
(
1
-
θ
)
c
2, d
˘
2
=
(
1
-
θ
)
d
2.Note that although (3) is a deterministic optimization problem, it is not an SCCP. To see why this is the case, one can try to formulate (3) into the form of SCCP and it then becomes clear that (3) cannot fit into the SCCP form.In the rest of this paper, we will use some results on conic programming without explanations. Interested readers can consult the books on conic programming (e.g., [4]) for the related results.


## 2. Literature Review

Bellman [5, 6] first introduced the so-called continuous linear programming (CLP), which has the following form:
(4)
(
CLP
)
max
∫
0
T
‍
c
(
t
)
′
x
(
t
)
d
t
(
CLPL
)
s
.
t
.
B
x
(
t
)
-
∫
0
t
‍
K
x
(
s
)
d
s
≤
b
(
t
)
(
CLPL
)
s
.
t
.
x
(
t
)
≥
0
,
t
∈
[
0
,
T
]
.
Here x
(
t
) is a decision variable. The model has wide-ranging applications (e.g., the bottleneck problem [5]). But CLP is very difficult to solve in its general form. Later, Anderson [7] introduced separated continuous linear programming (SCLP) (see (5)), a special case of CLP, to model the job-shop scheduling problems:
(5)
(
SCLP
)
max
∫
0
T
‍
[
(
γ
+
(
T
-
t
)
c
)
′
u
(
t
)
+
d
′
x
(
t
)
]
d
t
(
SCLPL
)
s
.
t
.
∫
0
t
‍
G
u
(
s
)
d
s
+
F
x
(
t
)
≤
α
+
t
a
,
(
SCLPL
)
s
.
t
.
H
u
(
t
)
≤
b
,
(
SCLPL
)
s
.
t
.
u
(
t
)
≥
0
,
x
(
t
)
≥
0
,
t
∈
[
0
,
T
]
.
The word “separated” refers to the fact that there are two kinds of constraints in SCLP: the constraints involving integration and the instantaneous constraints [7].Anderson et al. [8] studied the properties of the extreme solutions of the SCLP, based on which Anderson and Philpott [9] developed a simplex type of algorithm for a network-based SCLP. Refer to Anderson and Philpott [10] and Anderson and Nash [11] for their other results on SCLP. Pullan [12–18] continues studying SCLP in a series of papers. He systematically developed a duality theory and solution algorithms for the SCLP.There are other researches focused on other forms ofSCLP, including Luo and Bertsimas [19], Shapiro [20], Fleischer and Sethuraman [21], Weiss [22], and Nasrabadi et al. [23].One of the extensions ofSCLP is SCCP introduced by Wang et al. [2] in which the constraints involve the convex cone in their right hand side. When all the convex cones are nonnegative orthants, SCCP reduces to SCLP. In [2], based on the relationship among SCCP, its dual, and their discretization counterparts, they develop a strong duality theory for the SCCP. They also suggest a polynomial-time approximation algorithm that solves the SCCP to any predefined accuracy.Wang [24, 25] extends SCCP to generalized separated continuous conic programming (GSCCP) by allowing the parameters in (1) to be piece-wise constants and extends the results of [2] for SCCP to GSCCP. In this paper, we extend SCCP to SSCCP by allowing the changes of values of some parameters in SCCP in the second stage. We also extend the results of [2] for SCCP to SSCCP.


### 2.1. A Motived Example for SSCCP

We consider a problem which appears in [2]; for completeness, we reproduce the problem description and the formulation below.A network processes a continuous flow of jobs at two machines. The jobs visit machines 1 and 2 in the order1
→
2
→
1, that is, a total of three processing steps; see Figure 1. Corresponding to each processing step, there is a buffer holding the fluid. At t
=
0, the initial levels of fluid at the three steps are 50, 20, and 120 units. The input rates of fluid from outside to the three buffers are 0.01, 0.01, and 0.01. To process each unit of job (“fluid”), the time requirements at the three steps are 0.4, 0.8, and 0.2 time units.Figure 1
The fluid network in the example in Section2.1.The problem is to find the processing rates at the three steps,u
i
(
t
),  i
=
1,2
,
3, which determine the fluid levels in the three buffers, x
i
(
t
), i
=
1,2
,
3, during a given time interval [
0
,
T
] such that the fluid levels in the three buffers are maintained as close as possible to a prespecified constant level d
=
(
30
10
80
)
′.The problem can be formulated as follows:(6)
min
∫
0
T
‍
[
(
x
(
t
)
-
d
)
′
(
x
(
t
)
-
d
)
]
d
t
s
.
t
.
∫
0
t
‍
G
u
(
s
)
d
s
+
x
(
t
)
=
α
+
t
a
,
b
-
H
u
(
t
)
≥
0
,
u
(
t
)
≥
0
,
x
(
t
)
≥
0
,
t
∈
[
0
,
T
]
,
where
(7)
G
=
(
1
0
0
-
1
1
0
0
-
1
1
)
,
H
=
(
0.4
0
0.2
0
0.8
0
)
,
α
=
(
50
20
120
)
,
a
=
(
0.01
0.01
0.01
)
,
b
=
(
1
1
)
.
We can further express the above problem in the form of SCCP. Please refer to [2] for the details.In reality, the values ofa and b could be changed during [
0
,
T
] for example, when the machine 1 experiences partial breakdown within [
T
1
,
T
]; where 0
≤
T
1
≤
T, the corresponding value of capacity vector for machine 1, b
1, will change during [
T
1
,
T
]. This makes the formulation of the problem an SSCCP. We omit the details here.


## 2.1. A Motived Example for SSCCP

We consider a problem which appears in [2]; for completeness, we reproduce the problem description and the formulation below.A network processes a continuous flow of jobs at two machines. The jobs visit machines 1 and 2 in the order1
→
2
→
1, that is, a total of three processing steps; see Figure 1. Corresponding to each processing step, there is a buffer holding the fluid. At t
=
0, the initial levels of fluid at the three steps are 50, 20, and 120 units. The input rates of fluid from outside to the three buffers are 0.01, 0.01, and 0.01. To process each unit of job (“fluid”), the time requirements at the three steps are 0.4, 0.8, and 0.2 time units.Figure 1
The fluid network in the example in Section2.1.The problem is to find the processing rates at the three steps,u
i
(
t
),  i
=
1,2
,
3, which determine the fluid levels in the three buffers, x
i
(
t
), i
=
1,2
,
3, during a given time interval [
0
,
T
] such that the fluid levels in the three buffers are maintained as close as possible to a prespecified constant level d
=
(
30
10
80
)
′.The problem can be formulated as follows:(6)
min
∫
0
T
‍
[
(
x
(
t
)
-
d
)
′
(
x
(
t
)
-
d
)
]
d
t
s
.
t
.
∫
0
t
‍
G
u
(
s
)
d
s
+
x
(
t
)
=
α
+
t
a
,
b
-
H
u
(
t
)
≥
0
,
u
(
t
)
≥
0
,
x
(
t
)
≥
0
,
t
∈
[
0
,
T
]
,
where
(7)
G
=
(
1
0
0
-
1
1
0
0
-
1
1
)
,
H
=
(
0.4
0
0.2
0
0.8
0
)
,
α
=
(
50
20
120
)
,
a
=
(
0.01
0.01
0.01
)
,
b
=
(
1
1
)
.
We can further express the above problem in the form of SCCP. Please refer to [2] for the details.In reality, the values ofa and b could be changed during [
0
,
T
] for example, when the machine 1 experiences partial breakdown within [
T
1
,
T
]; where 0
≤
T
1
≤
T, the corresponding value of capacity vector for machine 1, b
1, will change during [
T
1
,
T
]. This makes the formulation of the problem an SSCCP. We omit the details here.


## 3. The Dual and Discretizations

### 3.1. The Dual

The dual ofSSCCP that we will focus on is the following problem:
(8)
(
SSCC
P
*
)
min
∫
0
T
-
T
1
‍
[
(
α
1
+
(
T
-
t
)
a
1
)
′
h
(
t
)
+
b
1
′
l
(
t
)
]
d
t
+
∫
0
T
-
T
1
‍
[
(
α
2
+
(
T
-
t
)
a
2
)
′
p
(
t
)
+
b
2
′
q
(
t
)
]
d
t
+
∫
T
-
T
1
T
‍
[
(
α
+
(
T
-
t
)
a
)
′
f
(
t
)
+
b
′
g
(
t
)
]
d
t
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
(
γ
˘
1
+
t
c
˘
1
)
∈
𝒦
31
*
,
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
t
∈
[
0
,
T
-
T
1
]
,
F
′
h
(
t
)
-
d
˘
1
∈
𝒦
41
*
,
t
∈
[
0
,
T
-
T
1
]
,
h
(
t
)
∈
𝒦
11
*
,
l
(
t
)
∈
𝒦
21
*
,
t
∈
[
0
,
T
-
T
1
]
,
∫
0
t
‍
G
′
p
(
s
)
d
s
+
H
′
q
(
t
)
-
(
γ
˘
2
+
t
c
˘
2
)
∈
𝒦
32
*
,
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
t
∈
[
0
,
T
-
T
1
]
,
F
′
p
(
t
)
-
d
˘
2
∈
𝒦
42
*
,
t
∈
[
0
,
T
-
T
1
]
,
p
(
t
)
∈
𝒦
12
*
,
q
(
t
)
∈
𝒦
22
*
,
t
∈
[
0
,
T
-
T
1
]
,
∫
0
T
-
T
1
‍
G
′
(
h
(
s
)
+
p
(
s
)
)
d
s
+
∫
T
-
T
1
t
‍
G
′
f
(
s
)
d
s
+
H
′
g
(
t
)
-
(
γ
+
t
c
)
∈
𝒦
3
*
,
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
t
∈
(
T
-
T
1
,
T
]
,
F
′
f
(
t
)
-
d
∈
𝒦
4
*
,
t
∈
(
T
-
T
1
,
T
]
,
f
(
t
)
∈
𝒦
1
*
,
g
(
t
)
∈
𝒦
2
*
,
t
∈
(
T
-
T
1
,
T
]
,
where the decision variables h
(
t
), l
(
t
), p
(
t
), q
(
t
), f
(
t
), and g
(
t
) are bounded measurable functions. 𝒦
i
*, 𝒦
i
j
* are the dual cones of 𝒦
i and 𝒦
i
j, i
=
1,2
,
3,4, j
=
1,2, respectively.The derivation of the above dual problem is similar to the derivation of the dual problem for LP (see, e.g., [26]) and we omit the details here. Because SSCCP involves time, to achieve some degree of symmetry in the dual (to facilitate the later analysis), we choose to write the dual in the reversed time; that is, t in the dual is T
-
t in the primal.The following weak duality is readily shown from the derivation of(
SSCC
P
*
).Proposition 1.
The weak duality holds betweenS
S
C
C
P and S
S
C
C
P
*; that is, if u
(
t
)
,
x
(
t
), t
∈
[
0
,
T
1
], v
(
t
), y
(
t
), w
(
t
), z
(
t
), t
∈
(
T
1
,
T
] is a feasible solution for S
S
C
C
P and h
(
t
), l
(
t
), p
(
t
), q
(
t
), t
∈
[
0
,
T
-
T
1
), f
(
t
), g
(
t
), t
∈
[
T
-
T
1
] is a feasible solution for S
S
C
C
P
*, then
(9)
∫
0
T
1
‍
[
(
γ
+
(
T
-
t
)
c
)
′
u
(
t
)
+
d
′
x
(
t
)
]
d
t
+
∫
T
1
T
‍
[
(
γ
˘
1
+
(
T
-
t
)
c
˘
1
)
′
v
(
t
)
+
d
˘
1
′
y
(
t
)
]
d
t
+
∫
T
1
T
‍
[
(
γ
˘
2
+
(
T
-
t
)
c
˘
2
)
′
w
(
t
)
+
d
˘
2
′
z
(
t
)
]
d
t
≤
∫
0
T
-
T
1
‍
[
(
α
1
+
(
T
-
t
)
a
1
)
′
h
(
t
)
+
b
1
′
l
(
t
)
]
d
t
+
∫
0
T
-
T
1
‍
[
(
α
2
+
(
T
-
t
)
a
2
)
′
p
(
t
)
+
b
2
′
q
(
t
)
]
d
t
+
∫
T
-
T
1
T
‍
[
(
α
+
(
T
-
t
)
a
)
′
f
(
t
)
+
b
′
g
(
t
)
]
d
t
.Next we will introduce the discretizations forSSCCP and SSCC
P
*, respectively, and discuss the relationships among SSCCP, SSCC
P
*, and their discretizations. But first, we need the following notation and conventions which mostly follow what is used in [2].Notation and Conventions
(i)
When we say(
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is a feasible solution to SSCCP, we mean (
u
(
t
)
,
x
(
t
)
,
t
∈
[
0
,
T
1
]
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
,
t
∈
(
T
1
,
T
]
) is a feasible solution to SSCCP.
(ii)
By default, all vectors are column vectors. One exception is when we denote the solutions toSSCCP and its dual (or their variations) as (
u
,
x
,
v
,
y
,
w
,
z
) and (
h
,
l
,
p
,
q
,
f
,
g
), we mean (
u
′
,
x
′
,
v
′
,
y
′
,
w
′
,
z
′
)
′ and (
h
′
,
l
′
,
p
′
,
q
′
,
f
′
,
g
′
)
′.
(iii)
π
=
{
t
0
,
…
,
t
m
1
,
…
,
t
m
1
+
m
2
} denotes a partition of [
0
,
T
1
,
T
] into m
1
+
m
2 segments:
(10)
0
=
t
0
<
t
1
<
⋯
<
t
m
1
=
T
1
<
t
m
1
+
1
<
⋯
<
t
m
1
+
m
2
=
T
,
where m
1 and m
2 are positive integer numbers.
(iv)
Given a partitionπ
=
{
t
0
,
…
,
t
m
} and a vector r
^
:
=
(
r
^
(
t
0
)
,
r
^
(
t
1
)
,
…
,
r
^
(
t
m
)
), where r
^
(
·
) is a right continuous function, the following (continuous) function
(11)
r
(
t
)
=
(
t
i
-
t
t
i
-
t
i
-
1
)
r
^
(
t
i
-
1
)
+
(
t
-
t
i
-
1
t
i
-
t
i
-
1
)
r
^
(
t
i
)
,
for
t
∈
[
t
i
-
1
,
t
i
]
,
i
=
1
,
…
,
m
,
is called a piecewise linear extension of r
^, whereas the following (right-continuous) function
(12)
r
(
t
)
=
{
r
^
(
t
i
-
1
)
,
t
∈
[
t
i
-
1
,
t
i
)
,
for
i
=
1
,
…
,
m
,
r
^
(
t
m
-
1
)
,
t
=
T
,
is called a piecewise constant extension of r
^.
(v)
When(
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is a feasible solution to SSCCP, with u
(
t
), v
(
t
), w
(
t
) being piecewise constant and x
(
t
), y
(
t
), z
(
t
) piecewise linear, we assume u
(
t
), v
(
t
), w
(
t
) is right continuous, and x
(
t
), y
(
t
), z
(
t
) is continuous, with y
(
T
1
+
)
=
x
(
T
1
), z
(
T
1
+
)
=
x
(
T
1
), and the pieces of both u and x correspond to a common partition for [
0
,
T
1
], and the pieces of both v
,
w and y
,
z correspond to a common partition for (
T
1
,
T
].
When(
h
(
t
)
,
l
(
t
)
,
p
(
t
)
,
q
(
t
)
,
f
(
t
)
,
g
(
t
)
) is a feasible solution to SSCCP
*, with h
(
t
), p
(
t
), f
(
t
) being piecewise constant and l
(
t
), q
(
t
), g
(
t
) piecewise linear, we assume h
(
t
), p
(
t
), and f
(
t
) are right continuous and l
(
t
), q
(
t
) and g
(
t
) are continuous, with g
(
T
-
T
1
+
)
=
l
(
T
-
T
1
)
+
q
(
T
-
T
1
), and the pieces of h, l, p, and q correspond to a common partition for [
0
,
T
-
T
1
], and the pieces of both f and g correspond to a common partition for (
T
-
T
1
,
T
].
(vi)
Fori
=
1,2
,
3,4, denote 𝒦
i
,
m
:
=
𝒦
i
×
⋯
×
𝒦
i
︸
m, and similarly denote 𝒦
i
,
m
*
:
=
𝒦
i
*
×
⋯
×
𝒦
i
*
︸
m.


### 3.2. The Discretizations

We start with introducing the following discretization ofSSCCP based on the partition π of [
0
,
T
1
,
T
], where 0
=
t
0
<
t
1
<
⋯
<
t
m
1
=
T
1
<
t
m
1
+
1
<
⋯
<
t
m
1
+
m
2
=
T:
(13)
(
SC
P
1
(
π
)
)
max
∑
i
=
1
m
1
‍
(
(
γ
+
(
T
-
t
i
+
t
i
-
1
2
)
c
)
′
u
^
i
+
d
′
[
x
^
i
+
x
^
i
-
1
]
t
i
-
t
i
-
1
2
(
γ
+
(
T
-
t
i
+
t
i
-
1
2
)
c
)
′
u
^
i
)
+
∑
i
=
1
m
2
‍
(
(
γ
˘
1
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
1
)
′
v
^
i
+
d
˘
1
′
[
y
^
i
+
y
^
i
-
1
]
t
m
1
+
i
-
t
m
1
+
i
-
1
2
(
γ
˘
1
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
1
)
′
v
^
i
)
+
∑
i
=
1
m
2
‍
(
(
γ
˘
2
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
2
)
′
w
^
i
+
d
˘
2
′
[
z
^
i
+
z
^
i
-
1
]
t
m
1
+
i
-
t
m
1
+
i
-
1
2
(
γ
˘
1
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
1
)
′
v
^
i
)
s
.
t
.
α
+
t
i
a
-
[
G
u
^
1
+
⋯
+
G
u
^
i
+
F
x
^
i
]
∈
𝒦
1
,
s
.
t
.
α
+
t
i
a
-
s
.
t
.
i
=
1,2
,
…
,
m
1
;
(
t
i
-
t
i
-
1
)
b
-
H
u
^
i
∈
𝒦
2
,
i
=
1
,
…
,
m
1
;
u
^
i
∈
𝒦
3
,
x
^
i
∈
𝒦
4
,
i
=
1
,
…
,
m
1
;
α
1
+
t
m
1
+
i
a
1
-
[
G
u
^
1
+
⋯
+
G
u
^
m
1
]
-
[
G
v
^
1
+
⋯
+
G
v
^
i
]
-
F
y
^
i
∈
𝒦
11
,
-
[
G
v
^
1
+
⋯
+
G
]
i
=
1,2
,
…
,
m
2
;
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
1
-
H
v
^
i
∈
𝒦
21
,
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
1
i
=
1
,
…
,
m
2
;
v
^
i
∈
𝒦
31
,
y
^
i
∈
𝒦
41
,
i
=
1
,
…
,
m
2
;
α
2
+
t
m
1
+
i
a
2
-
[
G
u
^
1
+
⋯
+
G
u
^
m
1
]
-
[
G
w
^
1
+
⋯
+
G
w
^
i
]
-
F
z
^
i
∈
𝒦
12
,
i
=
1,2
,
…
,
m
2
;
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
2
-
H
w
^
i
∈
𝒦
22
,
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
2
i
=
1
,
…
,
m
2
;
w
^
i
∈
𝒦
32
,
z
^
i
∈
𝒦
42
,
i
=
1
,
…
,
m
2
.
Note that here we require that y
^
0
=
z
^
0
=
x
^
m
1 and
(14)
α
-
F
x
^
0
∈
𝒦
1
,
x
^
0
∈
𝒦
4
.
Clearly, (
SC
P
1
(
π
)
) is a conic program.Lemma 2.
From a feasible solution forS
C
P
1
(
π
), one can get a feasible solution for S
S
C
C
P with the same objective values, if 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42.Proof.
Suppose(
u
^
,
x
^
,
v
^
,
y
^
,
w
^
,
z
^
) is a feasible solution for SC
P
1
(
π
). Let
(15)
u
(
t
)
=
{
u
^
i
t
i
-
t
i
-
1
,
t
∈
[
t
i
-
1
,
t
i
)
,
i
=
1
,
…
,
m
1
,
u
^
m
1
t
m
1
-
t
m
1
-
1
,
t
=
t
m
1
,
x
(
0
)
=
x
^
0
,
x
(
t
)
=
t
i
-
t
t
i
-
t
i
-
1
x
^
i
-
1
+
t
-
t
i
-
1
t
i
-
t
i
-
1
x
^
i
,
i
=
1
,
…
,
m
1
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
]
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
i
=
1
,
…
,
m
2
,
y
(
T
1
+
)
=
x
^
m
1
,
y
(
t
)
=
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
-
1
+
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
i
=
1
,
…
,
m
2
,
w
(
t
)
=
w
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
]
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
i
=
1
,
…
,
m
2
,
z
(
T
1
+
)
=
x
^
m
1
,
z
(
t
)
=
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
z
^
(
t
i
-
1
)
+
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
z
^
i
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
LL
i
=
1
,
…
,
m
2
;
then we have u
(
t
)
∈
𝒦
3, x
(
t
)
∈
𝒦
4, t
∈
[
0
,
T
1
], v
(
t
)
∈
𝒦
31, t
∈
(
T
1
,
T
], w
(
t
)
∈
𝒦
32, and t
∈
(
T
1
,
T
].
Becausex
^
m
1
∈
𝒦
4 and y
^
0
=
z
^
0
=
x
^
m
1, y
^
0
∈
𝒦
4 and z
^
0
∈
𝒦
4. When 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, we have y
(
t
)
∈
𝒦
41, and z
(
t
)
∈
𝒦
42, and t
∈
(
T
1
,
T
].
Fort
=
0,
(16)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
-
F
x
^
0
∈
𝒦
1
.
Fort
∈
(
t
0
,
t
1
),
(17)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
+
t
a
-
G
u
^
1
t
1
t
-
F
(
t
1
-
t
t
1
x
^
0
+
t
t
1
x
^
1
)
=
t
t
1
(
α
+
t
1
a
-
G
u
^
1
-
F
x
^
1
)
+
t
1
-
t
t
1
(
α
-
F
x
^
0
)
∈
𝒦
1
.
Fort
∈
[
t
i
-
1
,
t
i
), i
=
2
,
…
,
m
1,
(18)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
+
t
a
-
(
∫
0
t
1
‍
G
u
(
s
)
d
s

+

⋯

+

∫
t
i
-
1
t
‍
G
u
(
s
)
d
s
)
-
F
x
(
t
)
=
α

+

t
a
-
(
G
u
^
1
t
1
-
t
0
(
t
1
-
t
0
)

+

⋯

+

G
u
^
i
t
i
-
t
i
-
1
(
t
-
t
i
-
1
)
)
-
F
(
t
i
-
t
t
i
-
t
i
-
1
x
^
i
-
1

+

t
-
t
i
-
1
t
i
-
t
i
-
1
x
^
i
)
=
t
-
t
i
-
1
t
i
-
t
i
-
1
(
α
+
t
i
a
-
(
G
u
^
1
+
⋯
+
G
u
^
i
-
1

+

G
u
^
i
)
-
F
x
^
i
)
+
t
i
-
t
t
i
-
t
i
-
1
(
α

+

t
i
-
1
a
-
(
G
u
^
1

+

⋯

+

G
u
^
i
-
1
)
-
F
x
^
i
-
1
)
∈
𝒦
1
.
Fort
=
t
m
1,
(19)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
+
t
m
1
a
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
F
x
^
m
1
∈
𝒦
1
.
Fort
∈
[
t
i
-
1
,
t
i
), i
=
1
,
…
,
m
1,
(20)
b
-
H
u
(
t
)
=
b
-
H
u
^
i
t
i
-
t
i
-
1
=
1
t
i
-
t
i
-
1
(
(
t
i
-
t
i
-
1
)
b
-
H
u
^
i
)
∈
𝒦
2
.
Fort
=
t
m
1,
(21)
b
-
H
u
(
t
)
=
b
-
H
u
^
m
1
t
m
1
-
t
m
1
-
1
=
1
t
m
1
-
t
m
1
-
1
(
(
t
m
1
-
t
m
1
-
1
)
b
-
H
u
^
m
1
)
∈
𝒦
2
.
Fort
∈
(
t
m
1
,
t
m
1
+
1
],
(22)
α
1
+
t
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
v
(
s
)
d
s
-
F
y
(
t
)
=
α
1
+
t
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
G
v
^
1
t
m
1
+
1
-
t
m
1
(
t
-
t
m
1
)
-
F
(
t
m
1
+
1
-
t
t
m
1
+
1
-
t
m
1
y
^
0
+
t
-
t
m
1
t
m
1
+
1
-
t
m
1
y
^
1
)
=
t
-
t
m
1
t
m
1
+
1
-
t
m
1
(
α
1

+

t
m
1
+
1
a
1
-
(
G
u
^
1

+

⋯

+

G
u
^
m
1
-
1
=
t
-
t
m
1
t
m
1
+
1
-
t
m
1
α
1

+

t
m
1
+
1
a
1
-
+
G
u
^
m
1
)
-
G
v
^
1
-
F
y
^
1
(
G
u
^
1

+

⋯

+

G
u
^
m
1
-
1
)
+
t
m
1
+
1
-
t
t
m
1
+
1
-
t
m
1
(
α
+
T
1
a
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
=
t
-
t
m
1
t
m
1
+
1
-
t
m
1
α
1

+

t
m
1
+
1
a
1
+
G
u
^
m
1
)
-
F
x
^
m
1
(
G
u
^
1

+

⋯

+

G
u
^
m
1
-
1
)
∈
𝒦
11
,
when
𝒦
1
⊆
𝒦
11
.
Fort
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
], i
=
2
,
…
,
m
2,
(23)
α
1
+
t
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
v
(
s
)
d
s
-
F
y
(
t
)
=
α
1
+
t
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
t
m
1
+
1
-
t
m
1
(
t
m
1
+
1
-
t
m
1
)
+
⋯
+
G
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
(
t
-
t
m
1
+
i
-
1
)
)
-
F
y
(
t
)
=
α
1
+
t
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
+
⋯
+
G
v
^
i
-
1
+
G
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
(
t
-
t
m
1
+
i
-
1
)
)
-
F
(
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
-
1
+
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
)
=
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
×
(
α
1
+
t
m
1
+
i
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
+
⋯
+
G
v
^
i
-
1
+
G
v
^
i
)
-
F
y
^
i
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
)
+
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
×
(
α
1
+
t
m
1
+
i
-
1
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
+
⋯
+
G
v
^
i
-
1
)
-
F
y
^
i
-
1
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
)
∈
𝒦
11
.
For t
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
], i
=
1
,
…
,
m
2
(24)
b
1
-
H
v
(
t
)
=
b
1
-
H
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
=
1
t
m
1
+
i
-
t
m
1
+
i
-
1
(
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
1
-
H
v
^
i
)
∈
𝒦
21
.
Similarly, if 𝒦
1
⊆
𝒦
12, then
(25)
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
(
s
)
d
s
-
F
z
(
t
)
∈
𝒦
12
,
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
w
(
s
)
d
s
-
t
∈
(
T
1
,
T
]
,
b
2
-
H
w
(
t
)
∈
𝒦
22
,
t
∈
(
T
1
,
T
]
.
So (
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is a feasible solution for SSCCP when 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41,  and 𝒦
4
⊆
𝒦
42.
It is easy to see that the objective value of(
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is the same as that of (
u
^
,
x
^
,
v
^
,
y
^
,
w
^
,
z
^
). We omit the details here.We now introduce the following discretization ofSSCC
P
* based on the partition π
′ of [
0
,
T
-
T
1
,
T
], π
′
=
{
t
0
,
t
1
,
…
,
t
m
2
,
…
,
t
m
2
+
m
1
}, where t
0
=
0, t
m
2
=
T
-
T
1, t
m
2
+
m
1
=
T.                              (26)
(
SC
P
2
(
π
′
)
)
min
∑
i
=
1
m
2
‍
(
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
h
^
i
+
b
1
′
[
l
^
i
+
l
^
i
-
1
]
t
i
-
t
i
-
1
2
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
)
+
∑
i
=
1
m
2
‍
(
(
α
2
+
(
T
-
t
i
+
t
i
-
1
2
)
a
2
)
′
p
^
i
+
b
2
′
[
q
^
i
+
q
^
i
-
1
]
t
i
-
t
i
-
1
2
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
)
+
∑
i
=
1
m
1
‍
(
(
α
+
(
T
-
t
m
2
+
i
+
t
m
2
+
i
-
1
2
)
a
)
′
f
^
i
+
b
′
[
g
^
i
+
g
^
i
-
1
]
t
m
2
+
i
-
t
m
2
+
i
-
1
2
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
)
s
.
t
.
G
′
(
h
^
1
+
h
^
2
+
⋯
+
h
^
i
)
+
H
′
l
^
i
-
(
γ
˘
1
+
t
i
c
˘
1
)
∈
𝒦
31
*
,
i
=
1
,
…
,
m
2
;
F
′
h
^
i
-
(
t
i
-
t
i
-
1
)
d
˘
1
∈
𝒦
41
*
,
i
=
1
,
…
,
m
2
;
h
^
i
∈
𝒦
11
*
,
l
^
i
∈
𝒦
21
*
,
i
=
1
,
…
,
m
2
;
G
′
(
p
^
1
+
p
^
2
+
⋯
+
p
^
i
)
+
H
′
q
^
i
-
(
γ
˘
2
+
t
i
c
˘
2
)
∈
𝒦
32
*
,
i
=
1
,
…
,
m
2
;
F
′
p
^
i
-
(
t
i
-
t
i
-
1
)
d
˘
2
∈
𝒦
42
*
,
i
=
1
,
…
,
m
2
;
p
^
i
∈
𝒦
12
*
,
q
^
i
∈
𝒦
22
*
,
i
=
1
,
…
,
m
2
;
G
′
(
∑
j
=
1
m
2
‍
h
^
j
+
∑
j
=
1
m
2
‍
p
^
j
)
+
G
′
(
f
^
1
+
f
^
2
+
⋯
+
f
^
i
)
+
H
′
g
^
i
-
(
γ
+
t
m
2
+
i
c
)
∈
𝒦
3
*
,
LLLLLL
+
H
′
g
^
i
-
i
=
1
,
…
,
m
1
;
F
′
f
^
i
-
(
t
m
2
+
i
-
t
m
2
+
i
-
1
)
d
∈
𝒦
4
*
,
LLLLLL
+
H
′
g
^
i
-
i
=
1
,
…
,
m
1
;
f
^
i
∈
𝒦
1
*
,
g
^
i
∈
𝒦
2
*
,
i
=
1
,
…
,
m
1
.
Note here we require that g
^
0
=
l
^
m
2
+
q
^
m
2 and
(27)
H
′
l
^
0
-
γ
˘
1
∈
𝒦
31
*
,
l
^
0
∈
𝒦
21
*
,
H
′
q
^
0
-
γ
˘
2
∈
𝒦
32
*
,
q
^
0
∈
𝒦
22
*
.
Clearly SC
P
2
(
π
′
) is also a conic program.We now show the following.Lemma 3.
For any two convex cones𝒦
1
,
𝒦
2,
(28)
𝒦
1
⊆
𝒦
2
⟺
𝒦
2
*
⊆
𝒦
1
*
.Proof.
⇒: Because 𝒦
1
⊆
𝒦
2, for any x
1
∈
𝒦
1, x
1
∈
𝒦
2, So for any y
2
∈
𝒦
2
*, x
1
′
y
2
≥
0. So y
2
∈
𝒦
1
*. So 𝒦
2
*
⊆
𝒦
1
*.
⇐: Because 𝒦
2
*
⊆
𝒦
1
*, for any y
2
∈
𝒦
2
*, y
2
∈
𝒦
1
*, So for any x
1
∈
𝒦
1,  x
1
′
y
2
≥
0. So x
1
∈
𝒦
2. so 𝒦
1
⊆
𝒦
2.Lemma 4.
From a feasible solution forS
C
P
2
(
π
′
), one can get a feasible solution for S
S
C
C
P
* with the same objective values, if 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, γ
˘
1
+
γ
˘
2
=
γ, c
˘
1
+
c
˘
2
=
c.Proof.
Suppose(
h
^
,
l
^
,
p
^
,
q
^
,
f
^
,
g
^
) is a feasible solution for SC
P
2
(
π
′
). Let
(29)
h
(
t
)
=
{
h
^
i
t
i
-
t
i
-
1
,
t
∈
[
t
i
-
1
,
t
i
)
,
i
=
1
,
…
,
m
2
,
h
^
m
2
t
m
2
-
t
m
2
-
1
,
t
=
t
m
2
,
l
(
0
)
=
l
^
0
,
l
(
t
)
=
t
i
-
t
t
i
-
t
i
-
1
l
^
i
-
1
+
t
-
t
i
-
1
t
i
-
t
i
-
1
l
^
i
,
t
∈
[
t
i
-
1
,
t
i
]
,
i
=
1
,
…
,
m
2
,
p
(
t
)
=
{
p
^
i
t
i
-
t
i
-
1
,
t
∈
[
t
i
-
1
,
t
i
)
,
i
=
1
,
…
,
m
2
,
p
^
m
2
t
m
2
-
t
m
2
-
1
,
t
=
t
m
2
,
q
(
0
)
=
q
^
0
,
q
(
t
)
=
t
i
-
t
t
i
-
t
i
-
1
q
^
i
-
1
+
t
-
t
i
-
1
t
i
-
t
i
-
1
q
^
i
,
t
∈
[
t
i
-
1
,
t
i
]
,
i
=
1
,
…
,
m
2
,
f
(
t
)
=
f
^
i
t
m
2
+
i
-
t
m
2
+
i
-
1
,
t
∈
(
t
m
2
+
i
-
1
,
t
m
2
+
i
]
,
f
(
t
)
=
f
^
i
t
m
2
+
i
-
t
m
2
+
i
-
1
,
L
t
∈
i
=
1
,
…
,
m
1
,
g
(
T
-
T
1
+
)
=
g
^
0
,
g
(
t
)
=
t
m
2
+
i
-
t
t
m
2
+
i
-
t
m
2
+
i
-
1
g
^
i
-
1
+
t
-
t
m
2
+
i
-
1
t
m
2
+
i
-
t
m
2
+
i
-
1
g
^
i
,
t
∈
(
t
m
2
+
i
-
1
,
t
m
2
+
i
]
,
i
=
1
,
…
,
m
1
;
then h
(
t
)
∈
𝒦
11
*, l
(
t
)
∈
𝒦
21
*, p
(
t
)
∈
𝒦
12
*, q
(
t
)
∈
𝒦
22
*, t
∈
[
0
,
T
-
T
1
], f
(
t
)
∈
𝒦
1
*, and t
∈
(
T
-
T
1
,
T
]. When 𝒦
2
⊆
𝒦
21, and 𝒦
2
⊆
𝒦
22, from Lemma 3, we have 𝒦
21
*
⊆
𝒦
2
*, and 𝒦
22
*
⊆
𝒦
2
*, then; because g
^
0
=
l
^
m
2
+
q
^
m
2, l
^
m
2
∈
𝒦
21
* and q
^
m
2
∈
𝒦
22
*, we have g
^
0
∈
𝒦
2
*, so g
(
t
)
∈
𝒦
2
* and t
∈
(
T
-
T
1
,
T
].
The remaining proof is similar to that in proving Lemma2 and we omit the details here.


## 3.1. The Dual

The dual ofSSCCP that we will focus on is the following problem:
(8)
(
SSCC
P
*
)
min
∫
0
T
-
T
1
‍
[
(
α
1
+
(
T
-
t
)
a
1
)
′
h
(
t
)
+
b
1
′
l
(
t
)
]
d
t
+
∫
0
T
-
T
1
‍
[
(
α
2
+
(
T
-
t
)
a
2
)
′
p
(
t
)
+
b
2
′
q
(
t
)
]
d
t
+
∫
T
-
T
1
T
‍
[
(
α
+
(
T
-
t
)
a
)
′
f
(
t
)
+
b
′
g
(
t
)
]
d
t
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
(
γ
˘
1
+
t
c
˘
1
)
∈
𝒦
31
*
,
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
t
∈
[
0
,
T
-
T
1
]
,
F
′
h
(
t
)
-
d
˘
1
∈
𝒦
41
*
,
t
∈
[
0
,
T
-
T
1
]
,
h
(
t
)
∈
𝒦
11
*
,
l
(
t
)
∈
𝒦
21
*
,
t
∈
[
0
,
T
-
T
1
]
,
∫
0
t
‍
G
′
p
(
s
)
d
s
+
H
′
q
(
t
)
-
(
γ
˘
2
+
t
c
˘
2
)
∈
𝒦
32
*
,
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
t
∈
[
0
,
T
-
T
1
]
,
F
′
p
(
t
)
-
d
˘
2
∈
𝒦
42
*
,
t
∈
[
0
,
T
-
T
1
]
,
p
(
t
)
∈
𝒦
12
*
,
q
(
t
)
∈
𝒦
22
*
,
t
∈
[
0
,
T
-
T
1
]
,
∫
0
T
-
T
1
‍
G
′
(
h
(
s
)
+
p
(
s
)
)
d
s
+
∫
T
-
T
1
t
‍
G
′
f
(
s
)
d
s
+
H
′
g
(
t
)
-
(
γ
+
t
c
)
∈
𝒦
3
*
,
s
.
t
.
∫
0
t
‍
G
′
h
(
s
)
d
s
+
H
′
l
(
t
)
-
t
∈
(
T
-
T
1
,
T
]
,
F
′
f
(
t
)
-
d
∈
𝒦
4
*
,
t
∈
(
T
-
T
1
,
T
]
,
f
(
t
)
∈
𝒦
1
*
,
g
(
t
)
∈
𝒦
2
*
,
t
∈
(
T
-
T
1
,
T
]
,
where the decision variables h
(
t
), l
(
t
), p
(
t
), q
(
t
), f
(
t
), and g
(
t
) are bounded measurable functions. 𝒦
i
*, 𝒦
i
j
* are the dual cones of 𝒦
i and 𝒦
i
j, i
=
1,2
,
3,4, j
=
1,2, respectively.The derivation of the above dual problem is similar to the derivation of the dual problem for LP (see, e.g., [26]) and we omit the details here. Because SSCCP involves time, to achieve some degree of symmetry in the dual (to facilitate the later analysis), we choose to write the dual in the reversed time; that is, t in the dual is T
-
t in the primal.The following weak duality is readily shown from the derivation of(
SSCC
P
*
).Proposition 1.
The weak duality holds betweenS
S
C
C
P and S
S
C
C
P
*; that is, if u
(
t
)
,
x
(
t
), t
∈
[
0
,
T
1
], v
(
t
), y
(
t
), w
(
t
), z
(
t
), t
∈
(
T
1
,
T
] is a feasible solution for S
S
C
C
P and h
(
t
), l
(
t
), p
(
t
), q
(
t
), t
∈
[
0
,
T
-
T
1
), f
(
t
), g
(
t
), t
∈
[
T
-
T
1
] is a feasible solution for S
S
C
C
P
*, then
(9)
∫
0
T
1
‍
[
(
γ
+
(
T
-
t
)
c
)
′
u
(
t
)
+
d
′
x
(
t
)
]
d
t
+
∫
T
1
T
‍
[
(
γ
˘
1
+
(
T
-
t
)
c
˘
1
)
′
v
(
t
)
+
d
˘
1
′
y
(
t
)
]
d
t
+
∫
T
1
T
‍
[
(
γ
˘
2
+
(
T
-
t
)
c
˘
2
)
′
w
(
t
)
+
d
˘
2
′
z
(
t
)
]
d
t
≤
∫
0
T
-
T
1
‍
[
(
α
1
+
(
T
-
t
)
a
1
)
′
h
(
t
)
+
b
1
′
l
(
t
)
]
d
t
+
∫
0
T
-
T
1
‍
[
(
α
2
+
(
T
-
t
)
a
2
)
′
p
(
t
)
+
b
2
′
q
(
t
)
]
d
t
+
∫
T
-
T
1
T
‍
[
(
α
+
(
T
-
t
)
a
)
′
f
(
t
)
+
b
′
g
(
t
)
]
d
t
.Next we will introduce the discretizations forSSCCP and SSCC
P
*, respectively, and discuss the relationships among SSCCP, SSCC
P
*, and their discretizations. But first, we need the following notation and conventions which mostly follow what is used in [2].Notation and Conventions
(i)
When we say(
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is a feasible solution to SSCCP, we mean (
u
(
t
)
,
x
(
t
)
,
t
∈
[
0
,
T
1
]
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
,
t
∈
(
T
1
,
T
]
) is a feasible solution to SSCCP.
(ii)
By default, all vectors are column vectors. One exception is when we denote the solutions toSSCCP and its dual (or their variations) as (
u
,
x
,
v
,
y
,
w
,
z
) and (
h
,
l
,
p
,
q
,
f
,
g
), we mean (
u
′
,
x
′
,
v
′
,
y
′
,
w
′
,
z
′
)
′ and (
h
′
,
l
′
,
p
′
,
q
′
,
f
′
,
g
′
)
′.
(iii)
π
=
{
t
0
,
…
,
t
m
1
,
…
,
t
m
1
+
m
2
} denotes a partition of [
0
,
T
1
,
T
] into m
1
+
m
2 segments:
(10)
0
=
t
0
<
t
1
<
⋯
<
t
m
1
=
T
1
<
t
m
1
+
1
<
⋯
<
t
m
1
+
m
2
=
T
,
where m
1 and m
2 are positive integer numbers.
(iv)
Given a partitionπ
=
{
t
0
,
…
,
t
m
} and a vector r
^
:
=
(
r
^
(
t
0
)
,
r
^
(
t
1
)
,
…
,
r
^
(
t
m
)
), where r
^
(
·
) is a right continuous function, the following (continuous) function
(11)
r
(
t
)
=
(
t
i
-
t
t
i
-
t
i
-
1
)
r
^
(
t
i
-
1
)
+
(
t
-
t
i
-
1
t
i
-
t
i
-
1
)
r
^
(
t
i
)
,
for
t
∈
[
t
i
-
1
,
t
i
]
,
i
=
1
,
…
,
m
,
is called a piecewise linear extension of r
^, whereas the following (right-continuous) function
(12)
r
(
t
)
=
{
r
^
(
t
i
-
1
)
,
t
∈
[
t
i
-
1
,
t
i
)
,
for
i
=
1
,
…
,
m
,
r
^
(
t
m
-
1
)
,
t
=
T
,
is called a piecewise constant extension of r
^.
(v)
When(
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is a feasible solution to SSCCP, with u
(
t
), v
(
t
), w
(
t
) being piecewise constant and x
(
t
), y
(
t
), z
(
t
) piecewise linear, we assume u
(
t
), v
(
t
), w
(
t
) is right continuous, and x
(
t
), y
(
t
), z
(
t
) is continuous, with y
(
T
1
+
)
=
x
(
T
1
), z
(
T
1
+
)
=
x
(
T
1
), and the pieces of both u and x correspond to a common partition for [
0
,
T
1
], and the pieces of both v
,
w and y
,
z correspond to a common partition for (
T
1
,
T
].
When(
h
(
t
)
,
l
(
t
)
,
p
(
t
)
,
q
(
t
)
,
f
(
t
)
,
g
(
t
)
) is a feasible solution to SSCCP
*, with h
(
t
), p
(
t
), f
(
t
) being piecewise constant and l
(
t
), q
(
t
), g
(
t
) piecewise linear, we assume h
(
t
), p
(
t
), and f
(
t
) are right continuous and l
(
t
), q
(
t
) and g
(
t
) are continuous, with g
(
T
-
T
1
+
)
=
l
(
T
-
T
1
)
+
q
(
T
-
T
1
), and the pieces of h, l, p, and q correspond to a common partition for [
0
,
T
-
T
1
], and the pieces of both f and g correspond to a common partition for (
T
-
T
1
,
T
].
(vi)
Fori
=
1,2
,
3,4, denote 𝒦
i
,
m
:
=
𝒦
i
×
⋯
×
𝒦
i
︸
m, and similarly denote 𝒦
i
,
m
*
:
=
𝒦
i
*
×
⋯
×
𝒦
i
*
︸
m.


## 3.2. The Discretizations

We start with introducing the following discretization ofSSCCP based on the partition π of [
0
,
T
1
,
T
], where 0
=
t
0
<
t
1
<
⋯
<
t
m
1
=
T
1
<
t
m
1
+
1
<
⋯
<
t
m
1
+
m
2
=
T:
(13)
(
SC
P
1
(
π
)
)
max
∑
i
=
1
m
1
‍
(
(
γ
+
(
T
-
t
i
+
t
i
-
1
2
)
c
)
′
u
^
i
+
d
′
[
x
^
i
+
x
^
i
-
1
]
t
i
-
t
i
-
1
2
(
γ
+
(
T
-
t
i
+
t
i
-
1
2
)
c
)
′
u
^
i
)
+
∑
i
=
1
m
2
‍
(
(
γ
˘
1
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
1
)
′
v
^
i
+
d
˘
1
′
[
y
^
i
+
y
^
i
-
1
]
t
m
1
+
i
-
t
m
1
+
i
-
1
2
(
γ
˘
1
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
1
)
′
v
^
i
)
+
∑
i
=
1
m
2
‍
(
(
γ
˘
2
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
2
)
′
w
^
i
+
d
˘
2
′
[
z
^
i
+
z
^
i
-
1
]
t
m
1
+
i
-
t
m
1
+
i
-
1
2
(
γ
˘
1
+
(
T
-
t
m
1
+
i
+
t
m
1
+
i
-
1
2
)
c
˘
1
)
′
v
^
i
)
s
.
t
.
α
+
t
i
a
-
[
G
u
^
1
+
⋯
+
G
u
^
i
+
F
x
^
i
]
∈
𝒦
1
,
s
.
t
.
α
+
t
i
a
-
s
.
t
.
i
=
1,2
,
…
,
m
1
;
(
t
i
-
t
i
-
1
)
b
-
H
u
^
i
∈
𝒦
2
,
i
=
1
,
…
,
m
1
;
u
^
i
∈
𝒦
3
,
x
^
i
∈
𝒦
4
,
i
=
1
,
…
,
m
1
;
α
1
+
t
m
1
+
i
a
1
-
[
G
u
^
1
+
⋯
+
G
u
^
m
1
]
-
[
G
v
^
1
+
⋯
+
G
v
^
i
]
-
F
y
^
i
∈
𝒦
11
,
-
[
G
v
^
1
+
⋯
+
G
]
i
=
1,2
,
…
,
m
2
;
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
1
-
H
v
^
i
∈
𝒦
21
,
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
1
i
=
1
,
…
,
m
2
;
v
^
i
∈
𝒦
31
,
y
^
i
∈
𝒦
41
,
i
=
1
,
…
,
m
2
;
α
2
+
t
m
1
+
i
a
2
-
[
G
u
^
1
+
⋯
+
G
u
^
m
1
]
-
[
G
w
^
1
+
⋯
+
G
w
^
i
]
-
F
z
^
i
∈
𝒦
12
,
i
=
1,2
,
…
,
m
2
;
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
2
-
H
w
^
i
∈
𝒦
22
,
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
2
i
=
1
,
…
,
m
2
;
w
^
i
∈
𝒦
32
,
z
^
i
∈
𝒦
42
,
i
=
1
,
…
,
m
2
.
Note that here we require that y
^
0
=
z
^
0
=
x
^
m
1 and
(14)
α
-
F
x
^
0
∈
𝒦
1
,
x
^
0
∈
𝒦
4
.
Clearly, (
SC
P
1
(
π
)
) is a conic program.Lemma 2.
From a feasible solution forS
C
P
1
(
π
), one can get a feasible solution for S
S
C
C
P with the same objective values, if 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42.Proof.
Suppose(
u
^
,
x
^
,
v
^
,
y
^
,
w
^
,
z
^
) is a feasible solution for SC
P
1
(
π
). Let
(15)
u
(
t
)
=
{
u
^
i
t
i
-
t
i
-
1
,
t
∈
[
t
i
-
1
,
t
i
)
,
i
=
1
,
…
,
m
1
,
u
^
m
1
t
m
1
-
t
m
1
-
1
,
t
=
t
m
1
,
x
(
0
)
=
x
^
0
,
x
(
t
)
=
t
i
-
t
t
i
-
t
i
-
1
x
^
i
-
1
+
t
-
t
i
-
1
t
i
-
t
i
-
1
x
^
i
,
i
=
1
,
…
,
m
1
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
]
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
i
=
1
,
…
,
m
2
,
y
(
T
1
+
)
=
x
^
m
1
,
y
(
t
)
=
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
-
1
+
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
i
=
1
,
…
,
m
2
,
w
(
t
)
=
w
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
]
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
i
=
1
,
…
,
m
2
,
z
(
T
1
+
)
=
x
^
m
1
,
z
(
t
)
=
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
z
^
(
t
i
-
1
)
+
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
z
^
i
,
v
(
t
)
=
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
,
t
∈
(
L
LL
i
=
1
,
…
,
m
2
;
then we have u
(
t
)
∈
𝒦
3, x
(
t
)
∈
𝒦
4, t
∈
[
0
,
T
1
], v
(
t
)
∈
𝒦
31, t
∈
(
T
1
,
T
], w
(
t
)
∈
𝒦
32, and t
∈
(
T
1
,
T
].
Becausex
^
m
1
∈
𝒦
4 and y
^
0
=
z
^
0
=
x
^
m
1, y
^
0
∈
𝒦
4 and z
^
0
∈
𝒦
4. When 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, we have y
(
t
)
∈
𝒦
41, and z
(
t
)
∈
𝒦
42, and t
∈
(
T
1
,
T
].
Fort
=
0,
(16)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
-
F
x
^
0
∈
𝒦
1
.
Fort
∈
(
t
0
,
t
1
),
(17)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
+
t
a
-
G
u
^
1
t
1
t
-
F
(
t
1
-
t
t
1
x
^
0
+
t
t
1
x
^
1
)
=
t
t
1
(
α
+
t
1
a
-
G
u
^
1
-
F
x
^
1
)
+
t
1
-
t
t
1
(
α
-
F
x
^
0
)
∈
𝒦
1
.
Fort
∈
[
t
i
-
1
,
t
i
), i
=
2
,
…
,
m
1,
(18)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
+
t
a
-
(
∫
0
t
1
‍
G
u
(
s
)
d
s

+

⋯

+

∫
t
i
-
1
t
‍
G
u
(
s
)
d
s
)
-
F
x
(
t
)
=
α

+

t
a
-
(
G
u
^
1
t
1
-
t
0
(
t
1
-
t
0
)

+

⋯

+

G
u
^
i
t
i
-
t
i
-
1
(
t
-
t
i
-
1
)
)
-
F
(
t
i
-
t
t
i
-
t
i
-
1
x
^
i
-
1

+

t
-
t
i
-
1
t
i
-
t
i
-
1
x
^
i
)
=
t
-
t
i
-
1
t
i
-
t
i
-
1
(
α
+
t
i
a
-
(
G
u
^
1
+
⋯
+
G
u
^
i
-
1

+

G
u
^
i
)
-
F
x
^
i
)
+
t
i
-
t
t
i
-
t
i
-
1
(
α

+

t
i
-
1
a
-
(
G
u
^
1

+

⋯

+

G
u
^
i
-
1
)
-
F
x
^
i
-
1
)
∈
𝒦
1
.
Fort
=
t
m
1,
(19)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
+
t
m
1
a
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
F
x
^
m
1
∈
𝒦
1
.
Fort
∈
[
t
i
-
1
,
t
i
), i
=
1
,
…
,
m
1,
(20)
b
-
H
u
(
t
)
=
b
-
H
u
^
i
t
i
-
t
i
-
1
=
1
t
i
-
t
i
-
1
(
(
t
i
-
t
i
-
1
)
b
-
H
u
^
i
)
∈
𝒦
2
.
Fort
=
t
m
1,
(21)
b
-
H
u
(
t
)
=
b
-
H
u
^
m
1
t
m
1
-
t
m
1
-
1
=
1
t
m
1
-
t
m
1
-
1
(
(
t
m
1
-
t
m
1
-
1
)
b
-
H
u
^
m
1
)
∈
𝒦
2
.
Fort
∈
(
t
m
1
,
t
m
1
+
1
],
(22)
α
1
+
t
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
v
(
s
)
d
s
-
F
y
(
t
)
=
α
1
+
t
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
G
v
^
1
t
m
1
+
1
-
t
m
1
(
t
-
t
m
1
)
-
F
(
t
m
1
+
1
-
t
t
m
1
+
1
-
t
m
1
y
^
0
+
t
-
t
m
1
t
m
1
+
1
-
t
m
1
y
^
1
)
=
t
-
t
m
1
t
m
1
+
1
-
t
m
1
(
α
1

+

t
m
1
+
1
a
1
-
(
G
u
^
1

+

⋯

+

G
u
^
m
1
-
1
=
t
-
t
m
1
t
m
1
+
1
-
t
m
1
α
1

+

t
m
1
+
1
a
1
-
+
G
u
^
m
1
)
-
G
v
^
1
-
F
y
^
1
(
G
u
^
1

+

⋯

+

G
u
^
m
1
-
1
)
+
t
m
1
+
1
-
t
t
m
1
+
1
-
t
m
1
(
α
+
T
1
a
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
=
t
-
t
m
1
t
m
1
+
1
-
t
m
1
α
1

+

t
m
1
+
1
a
1
+
G
u
^
m
1
)
-
F
x
^
m
1
(
G
u
^
1

+

⋯

+

G
u
^
m
1
-
1
)
∈
𝒦
11
,
when
𝒦
1
⊆
𝒦
11
.
Fort
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
], i
=
2
,
…
,
m
2,
(23)
α
1
+
t
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
v
(
s
)
d
s
-
F
y
(
t
)
=
α
1
+
t
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
t
m
1
+
1
-
t
m
1
(
t
m
1
+
1
-
t
m
1
)
+
⋯
+
G
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
(
t
-
t
m
1
+
i
-
1
)
)
-
F
y
(
t
)
=
α
1
+
t
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
+
⋯
+
G
v
^
i
-
1
+
G
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
(
t
-
t
m
1
+
i
-
1
)
)
-
F
(
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
-
1
+
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
y
^
i
)
=
t
-
t
m
1
+
i
-
1
t
m
1
+
i
-
t
m
1
+
i
-
1
×
(
α
1
+
t
m
1
+
i
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
+
⋯
+
G
v
^
i
-
1
+
G
v
^
i
)
-
F
y
^
i
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
)
+
t
m
1
+
i
-
t
t
m
1
+
i
-
t
m
1
+
i
-
1
×
(
α
1
+
t
m
1
+
i
-
1
a
1
-
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
-
(
G
v
^
1
+
⋯
+
G
v
^
i
-
1
)
-
F
y
^
i
-
1
(
G
u
^
1
+
⋯
+
G
u
^
m
1
-
1
+
G
u
^
m
1
)
)
∈
𝒦
11
.
For t
∈
(
t
m
1
+
i
-
1
,
t
m
1
+
i
], i
=
1
,
…
,
m
2
(24)
b
1
-
H
v
(
t
)
=
b
1
-
H
v
^
i
t
m
1
+
i
-
t
m
1
+
i
-
1
=
1
t
m
1
+
i
-
t
m
1
+
i
-
1
(
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
1
-
H
v
^
i
)
∈
𝒦
21
.
Similarly, if 𝒦
1
⊆
𝒦
12, then
(25)
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
(
s
)
d
s
-
F
z
(
t
)
∈
𝒦
12
,
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
w
(
s
)
d
s
-
t
∈
(
T
1
,
T
]
,
b
2
-
H
w
(
t
)
∈
𝒦
22
,
t
∈
(
T
1
,
T
]
.
So (
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is a feasible solution for SSCCP when 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41,  and 𝒦
4
⊆
𝒦
42.
It is easy to see that the objective value of(
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is the same as that of (
u
^
,
x
^
,
v
^
,
y
^
,
w
^
,
z
^
). We omit the details here.We now introduce the following discretization ofSSCC
P
* based on the partition π
′ of [
0
,
T
-
T
1
,
T
], π
′
=
{
t
0
,
t
1
,
…
,
t
m
2
,
…
,
t
m
2
+
m
1
}, where t
0
=
0, t
m
2
=
T
-
T
1, t
m
2
+
m
1
=
T.                              (26)
(
SC
P
2
(
π
′
)
)
min
∑
i
=
1
m
2
‍
(
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
h
^
i
+
b
1
′
[
l
^
i
+
l
^
i
-
1
]
t
i
-
t
i
-
1
2
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
)
+
∑
i
=
1
m
2
‍
(
(
α
2
+
(
T
-
t
i
+
t
i
-
1
2
)
a
2
)
′
p
^
i
+
b
2
′
[
q
^
i
+
q
^
i
-
1
]
t
i
-
t
i
-
1
2
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
)
+
∑
i
=
1
m
1
‍
(
(
α
+
(
T
-
t
m
2
+
i
+
t
m
2
+
i
-
1
2
)
a
)
′
f
^
i
+
b
′
[
g
^
i
+
g
^
i
-
1
]
t
m
2
+
i
-
t
m
2
+
i
-
1
2
(
α
1
+
(
T
-
t
i
+
t
i
-
1
2
)
a
1
)
′
)
s
.
t
.
G
′
(
h
^
1
+
h
^
2
+
⋯
+
h
^
i
)
+
H
′
l
^
i
-
(
γ
˘
1
+
t
i
c
˘
1
)
∈
𝒦
31
*
,
i
=
1
,
…
,
m
2
;
F
′
h
^
i
-
(
t
i
-
t
i
-
1
)
d
˘
1
∈
𝒦
41
*
,
i
=
1
,
…
,
m
2
;
h
^
i
∈
𝒦
11
*
,
l
^
i
∈
𝒦
21
*
,
i
=
1
,
…
,
m
2
;
G
′
(
p
^
1
+
p
^
2
+
⋯
+
p
^
i
)
+
H
′
q
^
i
-
(
γ
˘
2
+
t
i
c
˘
2
)
∈
𝒦
32
*
,
i
=
1
,
…
,
m
2
;
F
′
p
^
i
-
(
t
i
-
t
i
-
1
)
d
˘
2
∈
𝒦
42
*
,
i
=
1
,
…
,
m
2
;
p
^
i
∈
𝒦
12
*
,
q
^
i
∈
𝒦
22
*
,
i
=
1
,
…
,
m
2
;
G
′
(
∑
j
=
1
m
2
‍
h
^
j
+
∑
j
=
1
m
2
‍
p
^
j
)
+
G
′
(
f
^
1
+
f
^
2
+
⋯
+
f
^
i
)
+
H
′
g
^
i
-
(
γ
+
t
m
2
+
i
c
)
∈
𝒦
3
*
,
LLLLLL
+
H
′
g
^
i
-
i
=
1
,
…
,
m
1
;
F
′
f
^
i
-
(
t
m
2
+
i
-
t
m
2
+
i
-
1
)
d
∈
𝒦
4
*
,
LLLLLL
+
H
′
g
^
i
-
i
=
1
,
…
,
m
1
;
f
^
i
∈
𝒦
1
*
,
g
^
i
∈
𝒦
2
*
,
i
=
1
,
…
,
m
1
.
Note here we require that g
^
0
=
l
^
m
2
+
q
^
m
2 and
(27)
H
′
l
^
0
-
γ
˘
1
∈
𝒦
31
*
,
l
^
0
∈
𝒦
21
*
,
H
′
q
^
0
-
γ
˘
2
∈
𝒦
32
*
,
q
^
0
∈
𝒦
22
*
.
Clearly SC
P
2
(
π
′
) is also a conic program.We now show the following.Lemma 3.
For any two convex cones𝒦
1
,
𝒦
2,
(28)
𝒦
1
⊆
𝒦
2
⟺
𝒦
2
*
⊆
𝒦
1
*
.Proof.
⇒: Because 𝒦
1
⊆
𝒦
2, for any x
1
∈
𝒦
1, x
1
∈
𝒦
2, So for any y
2
∈
𝒦
2
*, x
1
′
y
2
≥
0. So y
2
∈
𝒦
1
*. So 𝒦
2
*
⊆
𝒦
1
*.
⇐: Because 𝒦
2
*
⊆
𝒦
1
*, for any y
2
∈
𝒦
2
*, y
2
∈
𝒦
1
*, So for any x
1
∈
𝒦
1,  x
1
′
y
2
≥
0. So x
1
∈
𝒦
2. so 𝒦
1
⊆
𝒦
2.Lemma 4.
From a feasible solution forS
C
P
2
(
π
′
), one can get a feasible solution for S
S
C
C
P
* with the same objective values, if 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, γ
˘
1
+
γ
˘
2
=
γ, c
˘
1
+
c
˘
2
=
c.Proof.
Suppose(
h
^
,
l
^
,
p
^
,
q
^
,
f
^
,
g
^
) is a feasible solution for SC
P
2
(
π
′
). Let
(29)
h
(
t
)
=
{
h
^
i
t
i
-
t
i
-
1
,
t
∈
[
t
i
-
1
,
t
i
)
,
i
=
1
,
…
,
m
2
,
h
^
m
2
t
m
2
-
t
m
2
-
1
,
t
=
t
m
2
,
l
(
0
)
=
l
^
0
,
l
(
t
)
=
t
i
-
t
t
i
-
t
i
-
1
l
^
i
-
1
+
t
-
t
i
-
1
t
i
-
t
i
-
1
l
^
i
,
t
∈
[
t
i
-
1
,
t
i
]
,
i
=
1
,
…
,
m
2
,
p
(
t
)
=
{
p
^
i
t
i
-
t
i
-
1
,
t
∈
[
t
i
-
1
,
t
i
)
,
i
=
1
,
…
,
m
2
,
p
^
m
2
t
m
2
-
t
m
2
-
1
,
t
=
t
m
2
,
q
(
0
)
=
q
^
0
,
q
(
t
)
=
t
i
-
t
t
i
-
t
i
-
1
q
^
i
-
1
+
t
-
t
i
-
1
t
i
-
t
i
-
1
q
^
i
,
t
∈
[
t
i
-
1
,
t
i
]
,
i
=
1
,
…
,
m
2
,
f
(
t
)
=
f
^
i
t
m
2
+
i
-
t
m
2
+
i
-
1
,
t
∈
(
t
m
2
+
i
-
1
,
t
m
2
+
i
]
,
f
(
t
)
=
f
^
i
t
m
2
+
i
-
t
m
2
+
i
-
1
,
L
t
∈
i
=
1
,
…
,
m
1
,
g
(
T
-
T
1
+
)
=
g
^
0
,
g
(
t
)
=
t
m
2
+
i
-
t
t
m
2
+
i
-
t
m
2
+
i
-
1
g
^
i
-
1
+
t
-
t
m
2
+
i
-
1
t
m
2
+
i
-
t
m
2
+
i
-
1
g
^
i
,
t
∈
(
t
m
2
+
i
-
1
,
t
m
2
+
i
]
,
i
=
1
,
…
,
m
1
;
then h
(
t
)
∈
𝒦
11
*, l
(
t
)
∈
𝒦
21
*, p
(
t
)
∈
𝒦
12
*, q
(
t
)
∈
𝒦
22
*, t
∈
[
0
,
T
-
T
1
], f
(
t
)
∈
𝒦
1
*, and t
∈
(
T
-
T
1
,
T
]. When 𝒦
2
⊆
𝒦
21, and 𝒦
2
⊆
𝒦
22, from Lemma 3, we have 𝒦
21
*
⊆
𝒦
2
*, and 𝒦
22
*
⊆
𝒦
2
*, then; because g
^
0
=
l
^
m
2
+
q
^
m
2, l
^
m
2
∈
𝒦
21
* and q
^
m
2
∈
𝒦
22
*, we have g
^
0
∈
𝒦
2
*, so g
(
t
)
∈
𝒦
2
* and t
∈
(
T
-
T
1
,
T
].
The remaining proof is similar to that in proving Lemma2 and we omit the details here.


## 4. Strong Feasibility

We say that(
u
,
x
,
v
,
y
,
w
,
z
) is a strongly feasible solution to SSCCP, if for the closed and convex cones 𝒦
i, 𝒦
i
j, i
=
1,2
,
3,4, j
=
1,2, with nonempty interiors, the following holds:
(30)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
∈
int
𝒦
1
,
t
∈
(
0
,
T
1
]
,
α
-
F
x
(
0
)
∈
𝒦
1
,
b
-
H
u
(
t
)
∈
int
𝒦
2
,
t
∈
[
0
,
T
1
]
,
u
(
t
)
∈
int
𝒦
3
,
x
(
t
)
∈
int
𝒦
4
,
t
∈
(
0
,
T
1
]
,
x
(
0
)
∈
𝒦
4
,
α
1
+
t
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
v
(
s
)
d
s
-
F
y
(
t
)
∈
int
𝒦
11
,
t
∈
(
T
1
,
T
]
,
b
1
-
H
v
(
t
)
∈
int
𝒦
21
,
t
∈
(
T
1
,
T
]
,
v
(
t
)
∈
int
𝒦
31
,
y
(
t
)
∈
int
𝒦
41
,
t
∈
(
T
1
,
T
]
,
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
(
s
)
d
s
-
F
z
(
t
)
∈
int
𝒦
12
,
t
∈
(
T
1
,
T
]
,
b
2
-
H
w
(
t
)
∈
int
𝒦
22
,
t
∈
(
T
1
,
T
]
,
w
(
t
)
∈
int
𝒦
32
,
z
(
t
)
∈
int
𝒦
42
,
t
∈
(
T
1
,
T
]
.
We say that  SSCCP is strongly feasible if there exists a strongly feasible solution. The similar notions apply to the dual problem SSCC
P
*.Next we will show that the strong feasibility ofSSCCP and SSCC
P
* can be determined by the strong feasibility of the following two conic programs:
(31)
(
C
P
1
)
max
T
1
c
′
u
^
-
(
T
1
d
-
(
T
-
T
1
)
(
d
˘
1
+
d
˘
2
)
)
′
x
^
(
C
P
1
)
max
+
(
T
-
T
1
)
c
˘
1
′
v
^
+
(
T
-
T
1
)
d
˘
1
′
y
^
(
C
P
1
)
max
+
(
T
-
T
1
)
c
˘
2
′
w
^
+
(
T
-
T
1
)
d
˘
2
′
z
^
(
C
P
1
)
s
.
t
.
α
+
T
1
a
-
G
u
^
-
F
x
^
∈
𝒦
1
,
(
C
P
1
)
s
.
t
.
T
1
b
-
H
u
^
∈
𝒦
2
,
(
C
P
1
)
s
.
t
.
u
^
∈
𝒦
3
,
x
^
∈
𝒦
4
,
(
C
P
1
)
s
.
t
.
α
1
+
T
a
1
-
G
u
^
-
G
v
^
-
F
y
^
∈
𝒦
11
,
(
C
P
1
)
s
.
t
.
(
T
-
T
1
)
b
1
-
H
v
^
∈
𝒦
21
,
(
C
P
1
)
s
.
t
.
v
^
∈
𝒦
31
,
y
^
∈
𝒦
41
,
(
C
P
1
)
s
.
t
.
α
2
+
T
a
2
-
G
u
^
-
G
w
^
-
F
z
^
∈
𝒦
12
,
(
C
P
1
)
s
.
t
.
(
T
-
T
1
)
b
2
-
H
w
^
∈
𝒦
22
,
(
C
P
1
)
s
.
t
.
w
^
∈
𝒦
32
,
z
^
∈
𝒦
42
,
(32)
(
CP
2
)
min
(
T
-
T
1
)
a
1
′
h
^
+
(
(
T
-
T
1
)
b
1
-
T
1
b
)
′
l
^
(
CP
2
)
min
+
(
T
-
T
1
)
a
2
′
p
^
+
(
(
T
-
T
1
)
b
2
-
T
1
b
)
′
q
^
(
CP
2
)
min
+
T
1
a
′
f
^
+
T
1
b
′
g
^
(
CP
2
)
s
.
t
.
G
′
h
^
+
H
′
l
^
-
(
γ
˘
1
+
(
T
-
T
1
)
c
˘
1
)
∈
𝒦
31
*
,
(
CP
2
)
s
.
t
.
F
′
h
^
-
(
T
-
T
1
)
d
˘
1
∈
𝒦
41
*
,
(
CP
2
)
s
.
t
.
h
^
∈
𝒦
11
*
,
l
^
∈
𝒦
21
*
,
(
CP
2
)
s
.
t
.
G
′
p
^
+
H
′
q
^
-
(
γ
˘
2
+
(
T
-
T
1
)
c
˘
2
)
∈
𝒦
32
*
,
(
CP
2
)
s
.
t
.
F
′
p
^
-
(
T
-
T
1
)
d
˘
2
∈
𝒦
42
*
,
(
CP
2
)
s
.
t
.
p
^
∈
𝒦
12
*
,
q
^
∈
𝒦
22
*
,
(
CP
2
)
s
.
t
.
G
′
(
h
^
+
p
^
)

+

G
′
f
^

+

H
′
g
^
-
(
γ
+
T
c
)

∈
𝒦
3
*
,
(
CP
2
)
s
.
t
.
F
′
f
^
-
T
1
d
∈
𝒦
4
*
,
(
CP
2
)
s
.
t
.
f
^
∈
𝒦
1
*
,
g
^
∈
𝒦
2
*
.Note that the constraints ofC
P
1 and C
P
2 above are the same as the constraints of SC
P
1
(
π
) and SC
P
2
(
π
′
), respectively, when m
1
=
m
2
=
1. The objectives of C
P
1 and C
P
2, however, are different from those of SC
P
1
(
π
) and SC
P
2
(
π
′
). The choice of these objectives is to facilitate the explicit derivation of a bound on the duality gap; see the proof of Theorem 11.Lemma 5.
If the conic programsC
P
1 are strongly feasible  and 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41, and 𝒦
4
⊆
𝒦
42, then S
S
C
C
P is strongly feasible, and so is S
C
P
1
(
π
).Proof.
(
1
) We first show that when C
P
1 is strongly feasible, SSCCP is strongly feasible.
Suppose(
u
^
,
x
^
,
v
^
,
y
^
,
w
^
,
z
^
) is a strongly feasible solution to C
P
1. We have
(33)
α
+
T
1
a
-
G
u
^
-
F
x
^
∈
int
𝒦
1
,
T
1
b
-
H
u
^
∈
int
𝒦
2
,
u
^
∈
int
𝒦
3
,
x
^
∈
int
𝒦
4
,
α
1
+
T
a
1
-
G
u
^
-
G
v
^
-
F
y
^
∈
int
𝒦
11
,
(
T
-
T
1
)
b
1
-
H
v
^
∈
int
𝒦
21
,
v
^
∈
int
𝒦
31
,
y
^
∈
int
𝒦
41
,
α
2
+
T
a
2
-
G
u
^
-
G
w
^
-
F
z
^
∈
int
𝒦
12
,
(
T
-
T
1
)
b
2
-
H
w
^
∈
int
𝒦
22
,
w
^
∈
int
𝒦
32
,
z
^
∈
int
𝒦
42
,
and x
^
0 is such a constant that
(34)
α
-
F
x
^
0
∈
𝒦
1
,
x
^
0
∈
𝒦
4
.
Let
(35)
u
(
t
)
=
u
^
T
1
,
t
∈
[
0
,
T
1
]
,
x
(
0
)
=
x
^
0
,
x
(
T
1
)
=
x
^
,
x
(
t
)
=
T
1
-
t
T
1
x
^
0
+
t
T
1
x
^
,
t
∈
(
0
,
T
1
)
,
v
(
t
)
=
v
^
T
-
T
1
,
t
∈
(
T
1
,
T
]
,
y
(
T
)

=

y
^
,
y
(
t
)
=
T
-
t
T
-
T
1
x
^

+

t
-
T
1
T
-
T
1
y
^
,
t
∈
(
T
1
,
T
)
,
w
(
t
)
=
w
^
T
-
T
1
,
t
∈
(
T
1
,
T
]
,
z
(
T
)
=
z
^
,
z
(
t
)
=
T
-
t
T
-
T
1
x
^
+
t
-
T
1
T
-
T
1
z
^
,
z
(
T
)
=
z
^
,
z
(
t
)
=
T
-
t
T
-
T
1
x
^
t
∈
(
T
1
,
T
)
.
We have u
(
t
)
∈
int
𝒦
3, t
∈
[
0
,
T
1
], x
(
t
)
∈
int
𝒦
4, t
∈
(
0
,
T
1
], x
(
0
)
∈
𝒦
4, v
(
t
)
∈
int
𝒦
31, w
(
t
)
∈
int
𝒦
32,   and t
∈
(
T
1
,
T
].
Because𝒦
4
⊆
𝒦
41 and 𝒦
4
⊆
𝒦
42, then y
(
t
)
∈
int
𝒦
41, t
∈
(
T
1
,
T
], z
(
t
)
∈
int
𝒦
42 and t
∈
(
T
1
,
T
].
Fort
=
0,
(36)
α
-
F
x
(
0
)
=
α
-
F
x
^
0
∈
𝒦
1
.
Fort
∈
(
0
,
T
1
],
(37)
α
+
t
a
-
∫
0
t
‍
G
u
(
s
)
d
s
-
F
x
(
t
)
=
α
+
t
a
-
G
u
^
T
1
t
-
F
(
T
1
-
t
T
1
x
^
0
+
t
T
1
x
^
)
=
t
T
1
(
α
+
T
1
a
-
G
u
^
-
F
x
^
)
+
T
1
-
t
T
1
(
α
-
F
x
^
0
)
∈
int
𝒦
1
.
Fort
∈
[
0
,
T
1
],
(38)
b
-
H
u
(
t
)
=
b
-
H
u
^
T
1
=
1
T
1
(
T
1
b
-
H
u
^
)
∈
int
𝒦
2
.
Fort
∈
(
T
1
,
T
],
(39)
α
1
+
t
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
v
(
s
)
d
s
-
F
y
(
t
)
=
α
1
+
t
a
1
-
G
u
^
T
1
T
1
-
G
v
^
T
-
T
1
(
t
-
T
1
)
-
F
(
T
-
t
T
-
T
1
x
^
+
t
-
T
1
T
-
T
1
y
^
)
=
t
-
T
1
T
-
T
1
(
α
1
+
T
a
1
-
G
u
^
-
G
v
^
-
F
y
^
)
+
T
-
t
T
-
T
1
(
α
+
T
1
a
-
G
u
^
-
F
x
^
)
∈
int
𝒦
11
.
Note that when 𝒦
1
⊆
𝒦
11, α
+
T
1
a
-
G
u
^
-
F
x
^
∈
int
𝒦
11.
Fort
∈
(
T
1
,
T
],
(40)
b
1
-
H
v
(
t
)
=
b
1
-
H
v
^
T
-
T
1
=
1
T
-
T
1
(
(
T
-
T
1
)
b
1
-
H
v
^
)
∈
int
𝒦
21
.
Similarly, we can get (by noting that𝒦
1
⊆
𝒦
12)
(41)
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
(
s
)
d
s
-
F
z
(
t
)
∈
int
𝒦
12
,
α
2
+
t
a
2
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
‍
G
w
(
s
)
d
s
-
F
z
t
∈
(
T
1
,
T
]
,
b
2
-
H
w
(
t
)
∈
int
𝒦
22
,
t
∈
(
T
1
,
T
]
.
We can see that (
u
(
t
)
,
x
(
t
)
,
v
(
t
)
,
y
(
t
)
,
w
(
t
)
,
z
(
t
)
) is a (two-piece) strongly feasible solution for SSCCP. So SSCCP is strongly feasible.
(
2
) Now we will show that from this strongly feasible solution for SSCCP, we can get a strongly feasible solution for SC
P
1
(
π
).
Let(42)
u
^
i

=

u
(
t
)
(
t
i
-
t
i
-
1
)
,
x
^
i

=

x
(
t
i
)
,
i

=

1
,
…
,
m
1
;
v
^
i

=

v
(
t
)
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
,
y
^
i

=

y
(
t
m
1
+
i
)
,
i

=

1
,
…
,
m
2
;
w
^
i

=

w
(
t
)
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
,
z
^
i

=

z
(
t
m
1
+
i
)
,
i

=

1
,
…
,
m
2
Then u
^
i
∈
int
𝒦
3, x
^
i
∈
int
𝒦
4, i
=
1
,
…
,
m
1, v
^
i
∈
int
𝒦
31, y
^
i
∈
int
𝒦
41, w
^
i
∈
int
𝒦
32, z
^
i
∈
int
𝒦
42, i
=
1
,
…
,
m
2.
Fori
=
1
,
…
,
m
1,
(43)
α
+
t
i
a
-
[
G
u
^
1
+
⋯
+
G
u
^
i
+
F
x
^
i
]
=
α
+
t
i
a
-
[
G
u
(
t
)
(
t
1
-
t
0
)
+
⋯
+
G
u
(
t
)
(
t
i
-
t
i
-
1
)
+
F
x
(
t
i
)
]
=
α
+
t
i
a
-
[
∫
0
t
1
‍
G
u
(
s
)
d
s
+
⋯
+
∫
t
i
-
1
t
i
‍
G
u
(
s
)
d
s
+
F
x
(
t
i
)
]
=
α
+
t
i
a
-
∫
0
t
i
‍
G
u
(
s
)
d
s
-
F
x
(
t
i
)
∈
int
𝒦
1
,
(
t
i
-
t
i
-
1
)
b
-
H
u
^
i
=
(
t
i
-
t
i
-
1
)
b
-
H
u
(
t
)
(
t
i
-
t
i
-
1
)
=
(
t
i
-
t
i
-
1
)
(
b
-
H
u
(
t
)
)
∈
int
𝒦
2
.
Fori
=
1
,
…
,
m
2,
(44)
α
1
+
t
m
1
+
i
a
1
-
[
G
u
^
1
+
⋯
+
G
u
^
m
1
]
-
[
G
v
^
1
+
⋯
+
G
v
^
i
]
-
F
y
^
i
=
α
1
+
t
m
1
+
i
a
1
-
∫
0
T
1
‍
G
u
(
s
)
d
s
-
∫
T
1
t
m
1
+
i
‍
G
v
(
s
)
d
s
-
F
y
(
t
m
1
+
i
)
∈
int
𝒦
11
,
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
1
-
H
v
^
i
=
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
(
b
1
-
H
v
(
t
)
)
∈
int
𝒦
21
.
Similarly, we can get.
Fori
=
1
,
…
,
m
2,
(45)
α
2
+
t
m
1
+
i
a
2
-
[
G
u
^
1
+
⋯
+
G
u
^
m
1
]
-
[
G
w
^
1
+
⋯
+
G
w
^
i
]
-
F
z
^
i
∈
int
𝒦
12
,
(
t
m
1
+
i
-
t
m
1
+
i
-
1
)
b
2
-
H
w
^
i
∈
int
𝒦
22
.
So(
u
^
,
x
^
,
v
^
,
y
^
,
w
^
,
z
^
) is a strongly feasible solution for SC
P
1
(
π
), and SC
P
1
(
π
) is strongly feasible.Lemma 6.
If the conic programsC
P
2 are strongly feasible, 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, γ
˘
1
+
γ
˘
2
=
γ, c
˘
1
+
c
˘
2
=
c, then S
S
C
C
P
* is strongly feasible and so is S
C
P
2
(
π
′
).Proof.
The proof is similar to that of Lemma5; the details are omitted here.We shall focus on one partition for[
0
,
T
1
,
T
], denoted by π
(
ϵ
1
,
ϵ
2
) and one partition for [
0
,
T
-
T
1
,
T
], denoted by π
′
(
ϵ
1
,
ϵ
2
). π
(
ϵ
1
,
ϵ
2
) divides the interval [
0
,
T
1
] into m
1 equal segments, each of length ϵ
1, and divides the interval [
T
1
,
T
] into m
2 equal segments, each of length ϵ
2. π
′
(
ϵ
1
,
ϵ
2
) divides the interval [
0
,
T
-
T
1
] into m
2 equal segments, each of length ϵ
2, and divides the interval [
T
-
T
1
,
T
] into m
1 equal segments, each of length ϵ
1.If we reverse the inner order ofu
^
,
x
^
,
v
^
,
y
^
,
w
^ and z
^ in SC
P
1
(
π
(
ϵ
1
,
ϵ
2
), that is, for example, change u
^
=
(
u
^
1
,
…
,
u
^
m
1
) to (
u
^
m
1
,
…
,
u
^
1
), we get the following problem:
(46)
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
max
h
l
1
′
u
^
+
d
l
1
′
x
^
+
h
l
2
′
v
^
+
d
l
2
′
y
^
max
+
h
l
3
′
w
^
+
d
l
3
′
z
^
+
ϵ
1
2
d
′
x
^
0
s
.
t
.
g
l
1
-
G
^
m
1
u
^
-
F
^
m
1
x
^
∈
𝒦
1
,
m
1
,
s
.
t
.
f
l
1
-
H
^
m
1
u
^
∈
𝒦
2
,
m
1
,
s
.
t
.
g
l
2
-
G
^
m
2
,
m
1
u
^
-
G
^
m
2
v
^
-
F
^
m
2
y
^
∈
𝒦
11
,
m
2
,
s
.
t
.
f
l
2
-
H
^
m
2
v
^
∈
𝒦
21
,
m
2
,
s
.
t
.
g
l
3
-
G
^
m
2
,
m
1
u
^
-
G
^
m
2
w
^
-
F
^
m
2
z
^
∈
𝒦
12
,
m
2
,
s
.
t
.
f
l
3
-
H
^
m
2
w
^
∈
𝒦
22
,
m
2
,
s
.
t
.
u
^
∈
𝒦
3
,
m
1
,
x
^
∈
𝒦
4
,
m
1
,
s
.
t
.
v
^
∈
𝒦
31
,
m
2
,
y
^
∈
𝒦
41
,
m
2
,
s
.
t
.
w
^
∈
𝒦
32
,
m
2
,
z
^
∈
𝒦
42
,
m
2
,
where
(47)
G
^
m
1
=
m
1
{
(
G
G
⋯
G
G
⋯
G
⋱
⋮
G
)
,
G
^
m
2
=
m
2
{
(
G
G
⋯
G
G
⋯
G
⋱
⋮
G
)
,
G
^
m
2
,
m
1
=
m
2
{
(
G
G
⋯
G
G
G
⋯
G
⋮
⋮
⋮
G
G
⋯
G
)
,
︸
m
1
F
^
m
1
=
m
1
{
(
F
F
⋱
F
)
,
F
^
m
2
=
m
2
{
(
F
F
⋱
F
)
,
H
^
m
1
=
m
1
{
(
H
H
⋱
H
)
,
H
^
m
2
=
m
2
{
(
H
H
⋱
H
)
,
f
l
1
=
m
1
{
(
ϵ
1
b
ϵ
1
b
⋮
ϵ
1
b
)
,
f
l
2
=
m
2
{
(
ϵ
2
b
1
ϵ
2
b
1
⋮
ϵ
2
b
1
)
,
f
l
3
=
m
2
{
(
ϵ
2
b
2
ϵ
2
b
2
⋮
ϵ
2
b
2
)
,
g
l
1
=
m
1
{
(
α
+
T
1
a
⋮
α
+
2
ϵ
1
a
α
+
ϵ
1
a
)
,
g
l
2
=
m
2
{
(
α
1
+
T
a
1
⋮
α
1
+
(
T
1
+
2
ϵ
2
)
a
1
α
1
+
(
T
1
+
ϵ
2
)
a
1
)
,
g
l
3
=
m
2
{
(
α
2
+
T
a
2
⋮
α
2
+
(
T
1
+
2
ϵ
2
)
a
2
α
2
+
(
T
1
+
ϵ
2
)
a
2
)
,
h
l
1
=
m
1
{
(
γ
+
(
T
-
T
1
+
ϵ
1
2
)
c
⋮
γ
+
(
T
-
3
ϵ
1
2
)
c
γ
+
(
T
-
ϵ
1
2
)
c
)
,
h
l
2
=
m
2
{
(
γ
˘
1
+
ϵ
2
2
c
˘
1
⋮
γ
˘
1
+
(
T
-
T
1
-
3
ϵ
2
2
)
c
˘
1
γ
˘
1
+
(
T
-
T
1
-
ϵ
2
2
)
c
˘
1
)
,
h
l
3
=
m
2
{
(
γ
˘
2
+
ϵ
2
2
c
˘
2
⋮
γ
˘
2
+
(
T
-
T
1
-
3
ϵ
2
2
)
c
˘
2
γ
˘
2
+
(
T
-
T
1
-
ϵ
2
2
)
c
˘
2
)
,
d
l
1
=
m
1
{
(
ϵ
1
2
d
+
ϵ
2
2
d
˘
1
+
ϵ
2
2
d
˘
2
same
{
(
ϵ
1
d
⋮
ϵ
1
d
)
)
,
d
l
2
=
m
2
{
(
ϵ
2
2
d
˘
1
same
{
(
ϵ
2
d
˘
1
⋮
ϵ
2
d
˘
1
)
)
,
d
l
3
=
m
2
{
(
ϵ
2
2
d
˘
2
same
{
(
ϵ
2
d
˘
2
⋮
ϵ
2
d
˘
2
)
)
.
Note that in g
l
1, the difference between two adjacent items is ϵ
1
a; in g
l
2, the difference between two adjacent items is ϵ
2
a
1; in g
l
3, the difference between two adjacent items is ϵ
2
a
2. In h
l
1, the difference between two adjacent items is ϵ
1
c; in h
l
2, the difference between two adjacent items is ϵ
2
c
˘
1; in h
l
3, the difference between two adjacent items is ϵ
2
c
˘
2. All the items in f
l
1 are the same, and this is also true for f
l
2 and f
l
3.The dual ofSC
P
1
(
π
,
ϵ
1
,
ϵ
2
)
without
(
ϵ
1
/
2
)
d
′
x
^
0 in the objective of SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) is the following problem:
(48)
(
SC
P
1
*
(
π
(
ϵ
1
,
ϵ
2
)
)
)

:
min
g
l
1
′
f
^
+
f
l
1
′
g
^
+
g
l
2
′
h
^
min
+
f
l
2
′
l
^
+
g
l
3
′
p
^
+
f
l
3
′
q
^
s
.
t
.
G
^
m
1
′
f
^
+
H
^
m
1
′
g
^
+
G
^
m
1
,
m
2
′
(
h
^
+
p
^
)
s
.
t
.
-
h
l
1
∈
𝒦
3
,
m
1
*
,
s
.
t
.
F
^
m
1
′
f
^
-
d
l
1
∈
𝒦
4
,
m
1
*
,
s
.
t
.
f
^
∈
𝒦
1
,
m
1
*
,
g
^
∈
𝒦
2
,
m
1
*
,
s
.
t
.
G
^
m
2
′
h
^
+
H
^
m
2
′
l
^
-
h
l
2
∈
𝒦
31
,
m
2
*
,
s
.
t
.
F
^
m
2
′
h
^
-
d
l
2
∈
𝒦
41
,
m
2
*
,
s
.
t
.
h
^
∈
𝒦
11
,
m
2
*
,
l
^
∈
𝒦
21
,
m
2
*
,
s
.
t
.
G
^
m
2
′
p
^
+
H
^
m
2
′
q
^
-
h
l
3
∈
𝒦
32
,
m
2
*
,
s
.
t
.
F
^
m
2
′
p
^
-
d
l
3
∈
𝒦
42
,
m
2
*
,
s
.
t
.
p
^
∈
𝒦
12
,
m
2
*
,
q
^
∈
𝒦
22
,
m
2
*
.
Similarly, we have
(49)
(
SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
min
g
u
2
′
h
^
+
f
u
2
′
l
^
+
ϵ
2
2
b
1
′
l
^
0
+
g
u
3
′
p
^
min
+
f
u
3
′
q
^
+
ϵ
2
2
b
2
′
q
^
0
+
g
u
1
′
f
^
+
f
u
1
′
g
^
s
.
t
.
G
^
m
2
′
h
^
+
H
^
m
2
′
l
^
-
h
u
2
∈
𝒦
31
,
m
2
*
,
s
.
t
.
F
^
m
2
′
h
^
-
d
u
2
∈
𝒦
41
,
m
2
*
,
s
.
t
.
f
^
∈
𝒦
1
,
m
1
*
,
g
^
∈
𝒦
2
,
m
1
*
,
s
.
t
.
G
^
m
2
′
p
^
+
H
^
m
2
′
q
^
-
h
u
3
∈
𝒦
32
,
m
2
*
,
s
.
t
.
F
^
m
2
′
p
^
-
d
u
3
∈
𝒦
42
,
m
2
*
,
s
.
t
.
h
^
∈
𝒦
11
,
m
2
*
,
l
^
∈
𝒦
21
,
m
2
*
,
s
.
t
.
G
^
m
1
,
m
2
′
(
h
^
+
p
^
)
+
G
^
m
1
′
f
^
s
.
t
.
+
H
^
m
1
′
g
^
-
h
u
1
∈
𝒦
3
,
m
1
*
,
s
.
t
.
F
^
m
1
′
f
^
-
d
u
1
∈
𝒦
4
,
m
1
*
,
s
.
t
.
p
^
∈
𝒦
12
,
m
2
*
,
q
^
∈
𝒦
22
,
m
2
*
,
where
(50)
G
^
m
1
′
=
m
1
{
(
G
′
G
′
G
′
⋱
G
′
G
′
⋯
G
′
)
,
G
^
m
2
′
=
m
2
{
(
G
′
G
′
G
′
⋱
G
′
G
′
⋯
G
′
)
,
G
^
m
1
,
m
2
′
=
m
1
{
(
G
′
G
′
⋯
G
′
G
′
G
′
⋯
G
′
⋮
⋮
⋮
G
′
G
′
⋯
G
′
)
,
︸
m
2
f
u
1
=
m
1
{
(
same
{
(
ϵ
1
b
⋮
ϵ
1
b
)
ϵ
1
2
b
)
,
f
u
2
=
m
2
{
(
s
ame
{
(
ϵ
2
b
1
⋮
ϵ
2
b
1
)
ϵ
2
2
b
1
+
ϵ
1
2
b
)
,
f
u
3
=
m
2
{
(
same
{
(
ϵ
2
b
2
⋮
ϵ
2
b
2
)
ϵ
2
2
b
2
+
ϵ
1
2
b
)
,
g
u
1
=
m
1
{
(
α
+
(
T
1
-
ϵ
1
2
)
a
α
+
(
T
1
-
3
ϵ
1
2
)
a
⋮
α
+
ϵ
1
2
a
)
,
g
u
2
=
m
2
{
(
α
1
+
(
T
-
ϵ
2
2
)
a
1
α
1
+
(
T
-
3
ϵ
2
2
)
a
1
⋮
α
1
+
(
T
1
+
ϵ
2
2
)
a
1
)
,
g
u
3
=
m
2
{
(
α
2
+
(
T
-
ϵ
2
2
)
a
2
α
2
+
(
T
-
3
ϵ
2
2
)
a
2
⋮
α
2
+
(
T
1
+
ϵ
2
2
)
a
2
)
,
h
u
1
=
m
1
{
(
γ
+
(
T
-
T
1
+
ϵ
1
)
c
γ
+
(
T
-
T
1
+
2
ϵ
1
)
c
⋮
γ
+
T
c
)
,
h
u
2
=
m
2
{
(
γ
˘
1
+
ϵ
2
c
˘
1
γ
˘
1
+
2
ϵ
2
c
˘
1
⋮
γ
˘
1
+
(
T
-
T
1
)
c
˘
1
)
,
h
u
3
=
m
2
{
(
γ
˘
2
+
ϵ
2
c
˘
2
γ
˘
2
+
2
ϵ
2
c
˘
2
⋮
γ
˘
2
+
(
T
-
T
1
)
c
˘
2
)
,
d
u
1
=
m
1
{
(
ϵ
1
d
ϵ
1
d
⋮
ϵ
1
d
)
,
d
u
2
=
m
2
{
(
ϵ
2
d
˘
1
ϵ
2
d
˘
1
⋮
ϵ
2
d
˘
1
)
,
d
u
3
=
m
2
{
(
ϵ
2
d
˘
2
ϵ
2
d
˘
2
⋮
ϵ
2
d
˘
2
)
.
Note that in g
u
1, the difference between two adjacent items is ϵ
1
a; in g
u
2, the difference between two adjacent items is ϵ
2
a
1; in g
u
3, the difference between two adjacent items is ϵ
2
a
2. In h
u
1, the difference between two adjacent items is ϵ
1
c; in h
u
2, the difference between two adjacent items is ϵ
2
c
˘
1; in h
u
3, the difference between two adjacent items is ϵ
2
c
˘
2. All the items in d
u
1 are the same, and this is also true for d
u
2 and d
u
3.Now we write down the relationships between the input parameters inSC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
), and these following relationships will be used in proving Theorem 11 in Section 5:
(51)
g
u
1
-
g
l
1
=
m
1
,
same
{
(
-
ϵ
1
2
a
⋮
-
ϵ
1
2
a
)
,
g
u
2
-
g
l
2
=
m
2
,
same
{
(
-
ϵ
2
2
a
1
⋮
-
ϵ
2
2
a
1
)
,
g
u
3
-
g
l
3
=
m
2
,
same
{
(
-
ϵ
2
2
a
2
⋮
-
ϵ
2
2
a
2
)
,
f
u
1
-
f
l
1
=
m
1
,
{
(
same
{
(
0
⋮
0
)
-
ϵ
1
2
b
)
,
f
u
2
-
f
l
2
=
m
2
,
{
(
same
{
(
0
⋮
0
)
-
ϵ
2
2
b
1
+
ϵ
1
2
b
)
,
f
u
3
-
f
l
3
=
m
2
,
{
(
same
{
(
0
⋮
0
)
-
ϵ
2
2
b
2
+
ϵ
1
2
b
)
,
h
u
1
-
h
l
1
=
m
1
,
same
{
(
ϵ
1
2
c
⋮
ϵ
1
2
c
)
,
h
u
2
-
h
l
2
=
m
2
,
same
{
(
ϵ
2
2
c
˘
1
⋮
ϵ
2
2
c
˘
1
)
,
h
u
3
-
h
l
3
=
m
2
,
same
{
(
ϵ
2
2
c
˘
2
⋮
ϵ
2
2
c
˘
2
)
,
d
u
1
-
d
l
1
=
m
1
{
(
ϵ
1
2
d
-
ϵ
2
2
d
˘
1
-
ϵ
2
2
d
˘
2
same
{
(
0
⋮
0
)
)
,
d
u
2
-
d
l
2
=
m
2
{
(
ϵ
2
2
d
˘
1
same
{
(
0
⋮
0
)
)
,
d
u
3
-
d
l
3
=
m
2
{
(
ϵ
2
2
d
˘
2
same
{
(
0
⋮
0
)
)
.


## 5. Strong Duality

In this section, we will prove that under some mild and verifiable conditions, strong duality holds betweenSSCCP and its dual.Letπ
1 denote a partition of [
0
,
T
-
T
1
,
T
], π
1
=
{
t
0
,
t
1
,
…
,
t
m
2
,
t
m
2
+
1
,
…
,
t
m
2
+
m
1
+
2
}, with t
0
=
0, t
m
2
+
1
=
T
-
T
1, t
m
2
+
m
1
+
2
=
T, and t
1
-
t
0
=
t
m
2
+
1
-
t
m
2
=
(
ϵ
2
/
2
), t
m
2
+
2
-
t
m
2
+
1
=
t
m
2
+
m
1
+
2
-
t
m
2
+
m
1
+
1 = (
ϵ
1
/
2
), while t
i
-
t
i
-
1
=
ϵ
2, i
=
2
,
…
,
m
2
;
t
j
-
t
j
-
1
=
ϵ
1, j
=
m
2
+
3
,
…
,
m
2
+
m
1
+
1.Lemma 7.
If the conic programsS
C
P
2
(
π
1
) are strongly feasible and 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, then S
C
P
1
*
(
π
(
ϵ
1
,
ϵ
2
)
) is strongly feasible.Proof.
The constraints of(
SC
P
2
(
π
1
)
) are:
(52)
(
G
^
m
2
′
G
′
…
G
′
G
′
)
h
^
+
(
H
^
m
2
′
H
′
)
l
^
-
(
h
l
2
γ
˘
1
+
(
T
-
T
1
)
c
˘
1
)
∈
𝒦
31
,
m
2
+
1
*
,
(
F
^
m
2
′
F
′
)
h
^
-
(
d
l
2
ϵ
2
2
d
˘
1
)
∈
𝒦
41
,
m
2
+
1
*
,
h
^
∈
𝒦
11
,
m
2
+
1
*
,
l
^
∈
𝒦
21
,
m
2
+
1
*
,
(
G
^
m
2
′
G
′
…
G
′
G
′
)
p
^
+
(
H
^
m
2
′
H
′
)
q
^
-
(
h
l
3
γ
˘
2
+
(
T
-
T
1
)
c
˘
2
)
∈
𝒦
32
,
m
2
+
1
*
,
(
F
^
m
2
′
F
′
)
p
^
-
(
d
l
3
ϵ
2
2
d
˘
2
)
∈
𝒦
42
,
m
2
+
1
*
,
p
^
∈
𝒦
12
,
m
2
+
1
*
,
q
^
∈
𝒦
22
,
m
2
+
1
*
,
(
G
^
m
1
,
m
2
′
G
′
⋮
G
′
G
′
⋯
G
′
G
′
)
(
h
^
+
p
^
)
+
(
G
^
m
1
′
G
′
⋯
G
′
G
′
)
f
^
+
(
H
^
m
1
′
H
′
)
g
^
-
(
h
l
1
γ
+
T
c
)
∈
𝒦
3
,
m
1
+
1
*
,
(
F
^
m
1
′
F
′
)
f
^
-
(
(
d
^
l
1
-
(
ϵ
2
2
d
˘
1
+
ϵ
2
2
d
˘
2
0
⋮
0
)
ϵ
1
2
d
)
∈
𝒦
4
,
m
1
+
1
*
,
f
^
∈
𝒦
1
,
m
1
+
1
*
,
g
^
∈
𝒦
2
,
m
1
+
1
*
.
When𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12 and 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, we have 𝒦
11
*
⊆
𝒦
1
*, 𝒦
12
*
⊆
𝒦
1
*, 𝒦
41
*
⊆
𝒦
4
*, 𝒦
42
*
⊆
𝒦
4
*. Comparing the above with the constraints of SC
P
1
*
(
π
(
ϵ
1
,
ϵ
2
)
), we observe that if
(53)
(
(
h
^
1
,
…
,
h
^
m
2
+
1
)
,
(
l
^
1
,
…
,
l
^
m
2
+
1
)
,
(
p
^
1
,
…
,
p
^
m
2
+
1
)
,
(
q
^
1
,
…
,
q
^
m
2
+
1
)
,
(
f
^
1
,
…
,
f
^
m
1
+
1
)
,
(
g
^
1
,
…
,
g
^
m
1
+
1
)
)
is a strongly feasible solution of SC
P
2
(
π
1
), then
(54)
(
(
h
^
1
,
…
,
h
^
m
2
)
,
(
l
^
1
,
…
,
l
^
m
2
)
,
(
p
^
1
,
…
,
p
^
m
2
)
,
(
q
^
1
,
…
,
q
^
m
2
)
,
(
f
^
1
+
h
^
m
2
+
1
+
p
^
m
2
+
1
,
f
^
2
,
…
,
f
^
m
1
)
,
(
g
^
1
,
…
,
g
^
m
1
)
)
is a strongly feasible solution to SC
P
1
*
(
π
(
ϵ
1
,
ϵ
2
)
).From Lemma5, we know if the conic programs C
P
1 are strongly feasible and 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41 and 𝒦
4
⊆
𝒦
42, then SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) is strongly feasible.From Lemma6, we know if the conic programs C
P
2 are strongly feasible and  𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, γ
˘
1
+
γ
˘
2
=
γ and c
˘
1
+
c
˘
2
=
c, SC
P
2
(
π
′
) is strongly feasible. Now, from Lemma 7, if additionally  𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12 and 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, then SC
P
1
*
(
π
(
ϵ
1
,
ϵ
2
)
) is strongly feasible.So under the condition that the conic programs(
C
P
1
) and (
C
P
2
) are strongly feasible, 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, γ
˘
1
+
γ
˘
2
=
γ, c
˘
1
+
c
˘
2
=
c, (
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
) is solvable.The dual ofSC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
without the constant terms (
ϵ
2
/
2
)
b
1
′
l
^
0
+
(
ϵ
2
/
2
)
b
2
′
q
^
0 in the objective is the following:
(55)
(
SC
P
2
*
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
max
h
u
1
′
u
^
+
d
u
1
′
x
^
+
h
u
2
′
v
^
max
+
d
u
2
′
y
^
+
h
u
3
′
w
^
+
d
u
3
′
z
^
s
.
t
.
g
u
1
-
G
^
m
1
u
^
-
F
^
m
1
x
^
∈
𝒦
1
,
m
1
,
s
.
t
.
f
u
1
-
H
^
m
1
u
^
∈
𝒦
2
,
m
1
,
s
.
t
.
g
u
2
-
G
^
m
2
,
m
1
u
^
-
G
^
m
2
v
^
-
F
^
m
2
y
^
∈
𝒦
11
,
m
2
,
s
.
t
.
f
u
2
-
H
^
m
2
v
^
∈
𝒦
21
,
m
2
,
s
.
t
.
g
u
3
-
G
^
m
2
,
m
1
u
^
-
G
^
m
2
w
^
-
F
^
m
2
z
^
∈
𝒦
12
,
m
2
,
s
.
t
.
f
u
3
-
H
^
m
2
w
^
∈
𝒦
22
,
m
2
,
s
.
t
.
u
^
∈
𝒦
3
,
m
1
,
x
^
∈
𝒦
4
,
m
1
,
s
.
t
.
v
^
∈
𝒦
31
,
m
2
,
y
^
∈
𝒦
41
,
m
2
,
s
.
t
.
w
^
∈
𝒦
32
,
m
2
,
z
^
∈
𝒦
42
,
m
2
.We useπ
2 to denote the partition {
t
0
,
t
1
,
t
2
,
…
,
t
m
1
+
1
,
…
,
t
m
1
+
m
2
+
2
}, with t
0
=
0, t
m
1
+
1
=
T
1, t
m
1
+
m
2
+
2
=
T, and t
1
-
t
0
=
t
m
1
+
1
-
t
m
1
=
ϵ
1
/
2, t
m
1
+
2
-
t
m
1
+
1
=
t
m
1
+
m
2
+
2
-
t
m
1
+
m
2
+
1
=
ϵ
2
/
2, while t
i
-
t
i
-
1
=
ϵ
1, i
=
2
,
…
,
m
1
;
t
j
-
t
j
-
1
=
ϵ
2, j
=
m
1
+
3
,
…
,
m
1
+
m
2
+
1.Lemma 8.
If the conic programsS
C
P
1
(
π
2
) are strongly feasible and 𝒦
2
⊆
𝒦
21
,
𝒦
2
⊆
𝒦
22
,
𝒦
3
⊆
𝒦
31 and 𝒦
3
⊆
𝒦
32, then S
C
P
2
*
(
π
′
(
ϵ
1
,
ϵ
2
)
) is strongly feasible.Proof.
If we reverse the inner order ofu
^
,
x
^
,
v
^
,
y
^
,
w
^
,
z
^, the constraints of SC
P
1
(
π
2
) are:
(56)
(
α
+
T
1
a
g
u
1
)
-
(
G
G
⋯
G
G
^
m
1
)
u
^
-
(
F
F
^
m
1
)
x
^
∈
𝒦
1
,
m
1
+
1
,
(
ϵ
1
2
b
f
u
1
)
-
(
H
H
^
m
1
)
u
^
∈
𝒦
2
,
m
1
+
1
,
(
α
1
+
T
a
1
g
u
2
)
-
(
G
G
⋯
G
G
⋮
G
G
^
m
2
,
m
1
)
u
^
-
(
G
G
⋯
G
G
^
m
2
)
v
^
-
(
F
F
^
m
2
)
y
^
∈
𝒦
11
,
m
2
+
1
,
(
ϵ
2
2
b
1
f
u
2
-
(
0
⋮
ϵ
1
2
b
)
)
-
(
H
H
^
m
2
)
v
^
∈
𝒦
21
,
m
2
+
1
,
(
α
2
+
T
a
2
g
u
3
)
-
(
G
G
⋯
G
G
⋮
G
G
^
m
2
,
m
1
)
u
^
-
(
G
G
⋯
G
G
^
m
2
)
w
^
-
(
F
F
^
m
2
)
z
^
∈
𝒦
12
,
m
2
+
1
,
(
ϵ
2
2
b
2
f
u
3
-
(
0
⋮
ϵ
1
2
b
)
)
-
(
H
H
^
m
2
)
w
^
∈
𝒦
22
,
m
2
+
1
,
u
^
∈
𝒦
3
,
m
1
+
1
,
x
^
∈
𝒦
4
,
m
1
+
1
,
v
^
∈
𝒦
31
,
m
2
+
1
,
y
^
∈
𝒦
41
,
m
2
+
1
,
w
^
∈
𝒦
32
,
m
2
+
1
,
z
^
∈
𝒦
42
,
m
2
+
1
.
When𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, comparing the above with the constraints of SC
P
2
*
(
π
′
(
ϵ
1
,
ϵ
2
)
), we observe that if
(57)
(
(
u
^
1
,
…
,
u
^
m
1
+
1
)
,
(
x
^
1
,
…
,
x
^
m
1
+
1
)
,
(
v
^
1
,
…
,
v
^
m
2
+
1
)
,
(
y
^
1
,
…
,
y
^
m
2
+
1
)
,
(
w
^
1
,
…
,
w
^
m
2
+
1
)
,
(
z
^
1
,
…
,
z
^
m
2
+
1
)
)
is a strongly feasible solution of SC
P
1
(
π
2
), then
(58)
(
(
u
^
1
,
…
,
u
^
m
1
)
,
(
x
^
1
,
…
,
x
^
m
1
)
,
(
v
^
1
+
u
^
m
1
+
1
,
v
^
2
,
…
,
v
^
m
2
)
,
(
y
^
2
,
…
,
y
^
m
2
+
1
)
,
(
w
^
1
+
u
^
m
1
+
1
,
w
^
2
,
…
,
w
^
m
2
)
,
(
z
^
2
,
…
,
z
^
m
2
+
1
)
)
is a strongly feasible solution to SC
P
2
*
(
π
′
(
ϵ
1
,
ϵ
2
)
).From Lemma5, we know that if the  conic program (
C
P
1
) is strongly feasible, and 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, then SC
P
1
(
π
2
) is strongly feasible. From Lemma 8, if additionally, 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, we have SC
P
2
*
(
π
′
(
ϵ
1
,
ϵ
2
)
) is strongly feasible.From Lemma6, we know that if the conic program (
C
P
2
) is strongly feasible and 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, γ
˘
1
+
γ
˘
2
=
γ and c
˘
1
+
c
˘
2
=
c, then SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
) is strongly feasible.So under the condition that the conic programsC
P
1 and C
P
2 are strongly feasible and 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, γ
˘
1
+
γ
˘
2
=
γ, c
˘
1
+
c
˘
2
=
c, SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
) is solvable.Now we have the following.Lemma 9.
If the conic programsC
P
1 and C
P
2 are strongly feasible  and 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22,𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, γ
˘
1
+
γ
˘
2
=
γ, c
˘
1
+
c
˘
2
=
c, both S
C
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and S
C
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
) are solvable, that is, they have optimal solutions and their optimal objective values are finite.Proposition 10.
Suppose thatS
C
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and S
C
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
) are solvable. Then, one has
(59)
v
(
S
C
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
≤
v
(
S
S
C
C
P
)
≤
v
(
S
S
C
C
P
*
)
≤
v
(
S
C
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
.Proof.
BecauseSC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
) are solvable, they have finite optimal objective values v
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
) and v
(
SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
).
From Lemma2, we know the optimal solution of SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) can be extended to a feasible solution of SSCCP, hence, the first inequality (since SSCCP is a maximization problem). A similar argument justifies the third inequality. The second inequality follows from the weak duality in Proposition 1.Theorem 11.
SupposeC
P
1 and C
P
2 are strongly feasible, with finite optimal values. 𝒦
1
⊆
𝒦
11, 𝒦
1
⊆
𝒦
12, 𝒦
2
⊆
𝒦
21, 𝒦
2
⊆
𝒦
22, 𝒦
3
⊆
𝒦
31, 𝒦
3
⊆
𝒦
32, 𝒦
4
⊆
𝒦
41, 𝒦
4
⊆
𝒦
42, γ
˘
1
+
γ
˘
2
=
γ and c
˘
1
+
c
˘
2
=
c. If one lets the number of intervals in π
,
π
′, m
1 and m
2 be the same and both of them equal to m, then there exists a constant Γ
>
0, which is independent of m, such that
(60)
v
(
S
C
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
-
v
(
S
C
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
≤
Γ
m
.
Consequently, one must have v
(
S
S
C
C
P
)
=
v
(
S
S
C
C
P
*
); that is, strong duality holds.Proof.
First note that strong duality follows immediately from the inequality in (60) by letting m
→
∞, taking into account the inequalities in Proposition 10.
To establish the error bound in (60), consider the following primal-dual pair of conic programs:
(61)
(
SCP
)
max
h
u
1
′
u
^
+
d
u
1
′
x
^
+
h
u
2
′
v
^
+
d
u
2
′
y
^
(
SCP
)
max
+
h
u
3
′
w
^
+
d
u
3
′
z
^
(
SCP
)
s
.
t
.
g
l
1
-
G
^
m
1
u
^
-
F
^
m
1
x
^
∈
𝒦
1
,
m
1
,
(
SCP
)
s
.
t
.
f
l
1
-
H
^
m
1
u
^
∈
𝒦
2
,
m
1
,
(
SCP
)
s
.
t
.
g
l
2
-
G
^
m
2
,
m
1
u
^
-
G
^
m
2
v
^
-
F
^
m
2
y
^
∈
𝒦
11
,
m
2
,
(
SCP
)
s
.
t
.
f
l
2
-
H
^
m
2
v
^
∈
𝒦
21
,
m
2
,
(
SCP
)
s
.
t
.
g
l
3
-
G
^
m
2
,
m
1
u
^
-
G
^
m
2
w
^
-
F
^
m
2
z
^
∈
𝒦
12
,
m
2
,
(
SCP
)
s
.
t
.
f
l
3
-
H
^
m
2
w
^
∈
𝒦
22
,
m
2
,
(
SCP
)
s
.
t
.
u
^
∈
𝒦
3
,
m
1
,
x
^
∈
𝒦
4
,
m
1
,
v
^
∈
𝒦
31
,
m
2
,
(
SCP
)
s
.
t
.
y
^
∈
𝒦
41
,
m
2
,
w
^
∈
𝒦
32
,
m
2
,
z
^
∈
𝒦
42
,
m
2
,
(62)
(
SC
P
*
)
min
g
l
2
′
h
^
+
f
l
2
′
l
^
+
g
l
3
′
p
^
+
f
l
3
′
q
^
(
SC
P
*
)
min
+
g
l
1
′
f
^
+
f
l
1
′
g
^
(
SC
P
*
)
s
.
t
.
G
^
m
2
′
h
^
+
H
^
m
2
′
l
^
-
h
u
2
∈
𝒦
31
,
m
2
*
,
(
SCP
*
)
s
.
t
.
F
^
m
2
′
h
^
-
d
u
2
∈
𝒦
41
,
m
2
*
,
(
SCP
*
)
s
.
t
.
G
^
m
2
′
p
^
+
H
^
m
2
′
q
^
-
h
u
3
∈
𝒦
32
,
m
2
*
,
(
SCP
*
)
s
.
t
.
F
^
m
2
′
p
^
-
d
u
3
∈
𝒦
42
,
m
2
*
,
(
SCP
*
)
s
.
t
.
G
^
m
1
,
m
2
′
(
h
^
+
p
^
)
+
G
^
m
1
′
f
^
+
H
^
m
1
′
g
^
(
SCP
*
)
s
.
t
.
-
h
u
1
∈
𝒦
3
,
m
1
*
,
(
SCP
*
)
s
.
t
.
F
^
m
1
′
f
^
-
d
u
1
∈
𝒦
4
,
m
1
*
,
(
SCP
*
)
s
.
t
.
f
^
∈
𝒦
1
,
m
1
*
,
g
^
∈
𝒦
2
,
m
1
*
,
h
^
∈
𝒦
11
,
m
2
*
,
(
SCP
*
)
s
.
t
.
l
^
∈
𝒦
21
,
m
2
*
,
p
^
∈
𝒦
12
,
m
2
*
,
q
^
∈
𝒦
22
,
m
2
*
.
Note that the problem in (62) has the same constraints as SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
) but the objective function of SC
P
1
*
(
π
(
ϵ
1
,
ϵ
2
)
), whereas the problem in (8) has the constraints of SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) but the objective function of SC
P
2
*
(
π
′
(
ϵ
1
,
ϵ
2
)
). Hence, both primal and dual are strongly feasible, since SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
) are. Consequently they both have optimal solutions and their respective optimal objective values coincide.
We denote the optimal solutions forSCP as (
u
^
*
,
x
^
*
,
v
^
*
,
y
^
*
,
w
^
*
,
z
^
*
) and the optimal solution for SC
P
* as (
h
^
*
,
l
^
*
,
p
^
*
,
q
^
*
,
f
^
*
,
g
^
*
). Note that these are feasible solutions to SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
), respectively. Hence, we have
(63)
v
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
≥
h
l
1
′
u
^
*
+
d
l
1
′
x
^
*
+
h
l
2
′
v
^
*
+
d
l
2
′
y
^
*
+
h
l
3
′
w
^
*
+
d
l
3
′
z
^
*
+
ϵ
1
2
d
′
x
^
0
,
v
(
SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
≤
g
u
2
′
h
^
*
+
f
u
2
′
l
^
*
+
ϵ
2
2
b
1
′
l
^
0
+
g
u
3
′
p
^
*
+
f
u
3
′
q
^
*
+
ϵ
2
2
b
2
′
q
^
0
+
g
u
1
′
f
^
*
+
f
u
1
′
g
^
*
.
Hence,
(64)
v
(
SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
-
v
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
≤
g
u
2
′
h
^
*
+
f
u
2
′
l
^
*
+
ϵ
2
2
b
1
′
l
^
0
+
g
u
3
′
p
^
*
+
f
u
3
′
q
^
*
+
ϵ
2
2
b
2
′
q
^
0
+
g
u
1
′
f
^
*
+
f
u
1
′
g
^
*
-
(
ϵ
1
2
h
l
1
′
u
^
*
+
d
l
1
′
x
^
*
+
h
l
2
′
v
^
*
+
d
l
2
′
y
^
*
+
h
l
3
′
w
^
*
+
d
l
3
′
z
^
*
+
ϵ
1
2
d
′
x
^
0
)
=
[
g
^
l
2
-
(
ϵ
2
2
a
1
ϵ
2
2
a
1
⋮
ϵ
2
2
a
1
)
]
′
h
^
*
+
[
f
^
l
2
+
(
0
⋮
0
ϵ
1
2
b
-
ϵ
2
2
b
1
)
]
′
l
^
*
+
[
g
^
l
3
-
(
ϵ
2
2
a
2
ϵ
2
2
a
2
⋮
ϵ
2
2
a
2
)
]
′
p
^
*
+
[
f
^
l
3
+
(
0
⋮
0
ϵ
1
2
b
-
ϵ
2
2
b
2
)
]
′
q
^
*
+
[
g
^
l
1
-
(
ϵ
1
2
a
ϵ
1
2
a
⋮
ϵ
1
2
a
)
]
′
f
^
*
+
[
f
^
l
1
-
(
0
⋮
0
ϵ
1
2
b
)
]
′
g
^
*
+
ϵ
2
2
(
b
1
′
l
^
0
+
b
2
′
q
^
0
)
-
{
[
h
^
u
1
-
(
ϵ
1
2
c
ϵ
1
2
c
⋮
ϵ
1
2
c
)
]
′
u
^
*
+
[
d
^
u
1
-
(
-
ϵ
2
2
(
d
˘
1
+
d
˘
2
)
+
ϵ
1
2
d
0
⋮
0
)
]
′
x
^
*
+
[
h
^
u
2
-
(
ϵ
2
2
c
˘
1
ϵ
2
2
c
˘
1
⋮
ϵ
2
2
c
˘
1
)
]
′
v
^
*
+
[

d
^
u
2
-

(

ϵ
2
2
d
˘
1
0
⋮
0
)

]
′
y
^
*

+

[
h
^
u
3
-
(
ϵ
2
2
c
˘
2
ϵ
2
2
c
˘
2
⋮
ϵ
2
2
c
˘
2
)
]
′
w
^
*
+
[
d
^
u
3
-
(
ϵ
2
2
d
˘
2
0
⋮
0
)
]
′
z
^
*
+
ϵ
1
2
d
′
x
0
}
=
-
ϵ
2
2
a
1
′
(
∑
j
=
1
m
2
‍
h
^
j
*
)
+
(
ϵ
1
2
b
-
ϵ
2
2
b
1
)
′
l
^
m
2
*
-
ϵ
2
2
a
2
′
(
∑
j
=
1
m
2
‍
p
^
j
*
)
+
(
ϵ
1
2
b
-
ϵ
2
2
b
2
)
′
q
^
m
2
*
-
ϵ
1
2
a
′
(
∑
j
=
1
m
1
‍
f
^
j
*
)
-
ϵ
1
2
b
′
g
^
m
1
*
+
ϵ
2
2
(
b
1
′
b
^
+
b
2
′
q
^
0
)
-
[
-
ϵ
1
2
c
′
(
∑
j
=
1
m
1
‍
u
^
j
*
)
+
(
-
ϵ
2
2
(
d
˘
1
+
d
˘
2
)
+
ϵ
1
2
d
)
′
x
^
m
1
*
-
ϵ
2
2
c
˘
1
′
(
∑
j
=
1
m
2
‍
v
^
j
*
)
-
ϵ
2
2
d
˘
1
′
y
^
m
2
*
-
ϵ
2
2
c
˘
2
′
(
∑
j
=
1
m
2
‍
w
^
j
*
)
-
ϵ
2
2
d
˘
2
′
z
^
m
2
*
+
ϵ
1
2
d
′
x
^
0
]
.
If m
1
=
m
2
=
m, then ϵ
1
=
T
1
/
m, ϵ
2
=
(
T
-
T
1
)
/
m. Hence, we have
(65)
v
(
SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
-
v
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
≤
1
2
m
[
-
(
T
-
T
1
)
a
1
′
(
∑
j
=
1
m
‍
h
^
j
*
)

+

(

T
1
b
-

(
T

-

T
1
)
b
1

)
′
l
^
m
*
-
(
T

-
T
1
)
a
2
′
(
∑
j
=
1
m
‍
p
^
j
*
)

+

(
T
1
b
-
(
T
-
T
1
)
b
2
)
′
q
^
m
*
-
T
1
a
′
(
∑
j
=
1
m
‍
f
^
j
*
)

-
T
1
b
′
g
^
m
*

+


(
T
-
T
1

)
(
b
1
′
l
^
0
+
b
2
′
q
^
0
)
+
T
1
c
′
(
∑
j
=
1
m
‍
u
^
j
*
)
-

(
-
(
T
-
T
1
)
(
d
˘
1


+


d
˘
2
)

+

T
1
d
)
′
x
^
m
*
+
(
T
-
T
1
)
c
˘
1
′
(
∑
j
=
1
m
‍
v
^
j
*
)

+

(
T
-
T
1
)
d
˘
1
′
y
^
m
*
+
(
T
-
T
1
)
c
˘
2
′

(
∑
j
=
1
m
‍
w
^
j
*


)
+
(
T
-
T
1
)
d
˘
2
′
z
^
m
*

-

T
1
d
′
x
^
0
]
.
From the primal feasibility of(
u
^
*
,
x
^
*
,
,
v
^
*
,
y
^
*
,
w
^
*
,
z
^
*
), we have
(66)
α
+
T
1
a
-
G
(
∑
i
=
1
m
‍
u
^
i
*
)
-
F
x
^
m
*
∈
𝒦
1
,
T
1
b
-
H
(
∑
i
=
1
m
‍
u
^
i
*
)
∈
𝒦
2
,
α
1
+
T
a
1
-
G
(
∑
i
=
1
m
‍
u
^
i
*
)
-
G
(
∑
i
=
1
m
‍
v
^
i
*
)
-
F
y
^
m
*
∈
𝒦
11
,
(
T
-
T
1
)
b
1
-
H
(
∑
i
=
1
m
‍
v
^
i
*
)
∈
𝒦
21
,
α
2
+
T
a
2
-
G
(
∑
i
=
1
m
‍
u
^
i
*
)
-
G
(
∑
i
=
1
m
‍
w
^
i
*
)
-
F
z
^
m
*
∈
𝒦
12
,
(
T
-
T
1
)
b
2
-
H
(
∑
i
=
1
m
‍
w
^
i
*
)
∈
𝒦
22
,
∑
i
=
1
m
‍
u
^
i
*
∈
𝒦
3
,
x
^
m
*
∈
𝒦
4
,
∑
i
=
1
m
‍
v
^
i
*
∈
𝒦
31
,
y
^
m
*
∈
𝒦
41
,
∑
i
=
1
m
‍
w
^
i
*
∈
𝒦
32
,
z
^
m
*
∈
𝒦
42
.
So we know that (
∑
i
=
1
m
‍
u
^
i
*
,
x
^
m
*
,
∑
i
=
1
m
‍
v
^
i
*
,
y
^
m
*
,
∑
i
=
1
m
‍
w
^
i
*
,
z
^
m
*
) is a feasible solution to C
P
1. Thus,
(67)
T
1
c
′
∑
i
=
1
m
‍
u
^
i
*
-
(
-
(
T
-
T
1
)
(
d
˘
1
+
d
˘
2
)
+
T
1
d
)
′
x
^
m
*
+
(
T
-
T
1
)
c
˘
1
′
∑
i
=
1
m
‍
v
^
i
*
+
(
T
-
T
1
)
d
˘
1
′
y
^
m
*
+
(
T
-
T
1
)
c
˘
2
′
∑
i
=
1
m
‍
w
^
i
*
+
(
T
-
T
1
)
d
˘
2
′
z
^
m
*
≤
v
(
C
P
1
)
.
Similarly, from the dual feasibility of (
h
^
*
,
l
^
*
,
p
^
*
,
q
^
*
,
f
^
*
,
g
^
*
), we have
(68)
G
′
(
∑
i
=
1
m
‍
h
^
i
*
)
+
H
′
l
^
m
*
-
(
γ
˘
1
+
(
T
-
T
1
)
c
˘
1
)
∈
𝒦
31
*
,
F
′
(
∑
i
=
1
m
‍
h
^
i
*
)
-
(
T
-
T
1
)
d
˘
1
∈
𝒦
41
*
,
G
′
(
∑
i
=
1
m
‍
p
^
i
*
)
+
H
′
q
^
m
*
-
(
γ
˘
2
+
(
T
-
T
1
)
c
˘
2
)
∈
𝒦
32
*
,
F
′
(
∑
i
=
1
m
‍
p
^
i
*
)
-
(
T
-
T
1
)
d
˘
2
∈
𝒦
42
*
,
G
′
(
∑
i
=
1
m
‍
h
^
i
*
+
∑
i
=
1
m
‍
p
^
i
*
)
+
G
′
(
∑
i
=
1
m
‍
f
^
i
*
)
+
H
′
g
^
m
*
-
(
γ
+
T
c
)
∈
𝒦
3
*
,
F
′
(
∑
i
=
1
m
‍
f
^
i
*
)
-
T
1
d
∈
𝒦
4
*
,
∑
i
=
1
m
‍
h
^
i
*
∈
𝒦
11
*
,
l
^
m
*
∈
𝒦
21
*
,
∑
i
=
1
m
‍
p
^
i
*
∈
𝒦
12
*
,
q
^
m
*
∈
𝒦
22
*
,
∑
i
=
1
m
‍
f
^
i
*
∈
𝒦
1
*
,
g
^
m
*
∈
𝒦
2
*
.
Hence, (
∑
i
=
1
m
‍
h
^
i
*
,
l
^
m
*
,
∑
i
=
1
m
‍
p
^
i
*
,
q
^
m
*
,
∑
i
=
1
m
‍
f
^
i
*
,
g
^
m
*
) is a feasible solution to C
P
2, and
(69)
(
T
-
T
1
)
a
1
′
(
∑
j
=
1
m
‍
h
^
j
*
)
-
(
T
1
b
-
(
T
-
T
1
)
b
1
)
′
l
^
m
*
+
(
T
-
T
1
)
a
2
′
(
∑
j
=
1
m
‍
p
^
j
*
)
-
(
T
1
b
-
(
T
-
T
1
)
b
2
)
′
q
^
m
*
+
T
1
a
′
(
∑
j
=
1
m
‍
f
^
j
*
)
+
T
1
b
′
g
^
m
*
≥
v
(
C
P
2
)
.
Putting the above together, we have(70)
v
(
SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
-
v
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
≤
1
2
m
[
T
1
d
′
x
^
0
-
v
(
C
P
2
)
+
v
(
C
P
1
)
+
(
T
-
T
1
)
×
(
b
1
′
l
^
0
+
b
2
′
q
^
0
)
-
T
1
d
′
x
^
0
]
.
Hence, we can let
(71)
Γ
≔
1
2
[
T
1
d
′
x
^
0
-
v
(
C
P
2
)
+
v
(
C
P
1
)
+
(
T
-
T
1
)
×
(
b
1
′
l
^
0
+
b
2
′
q
^
0
)
-
T
1
d
′
x
^
0
]
,
and Γ
<
∞, since v
(
C
P
1
)
<
∞ and v
(
C
P
2
)
<
∞ as assumed.


## 6. The Approximation Algorithm

Proposition10 and Theorem 11 suggest that we can solve SSCCP and their dual approximately through solving their discretized versions, the ordinary conic program SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
). The latter is readily solvable by standard algorithms, for example, SeDuMi [27], and the (discrete) solution can then be extended into the piecewise-constant control and piecewise-linear state variables as a feasible solution to SSCCP. Furthermore, the explicit error bound in (60) means that we can achieve any required accuracy by partitions π
(
ϵ
1
,
ϵ
2
) and π
′
(
ϵ
1
,
ϵ
2
) with a sufficiently large number m to construct the discretized conic programs SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) and SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
). Specifically, if δ is the required accuracy, then we can choose
(72)
m
=
⌈
Γ
δ
⌉
,
where (refer to the end of the proof of Theorem 11)
(73)
Γ
:
=
1
2
[
T
1
d
′
x
^
0
-
v
(
C
P
2
)
+
v
(
C
P
1
)
+
(
T
-
T
1
)
×
(
b
1
′
l
^
0
+
b
2
′
q
^
0
)
-
T
1
d
′
x
^
0
]
.
Then, from (59) and (60), we have
(74)
v
(
SSCC
P
*
)
-
v
(
SSCCP
)
≤
v
(
SC
P
2
(
π
′
(
ϵ
1
,
ϵ
2
)
)
)
-
v
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
)
≤
T
Γ
m
≤
δ
.
That is, the duality gap is guaranteed to be no greater than δ.To selectm following (72), we need to first derive Γ. This involves solving the two conic programs C
P
1 and C
P
2. In addition, we also need to determine x
^
0, l
^
0, and q
^
0. This can be accomplished by solving the following three conic programs:
(75)
max
d
′
x
^
0
s
.
t
.
α
-
F
x
^
0
∈
𝒦
1
,
x
^
0
∈
𝒦
4
,
min
b
′
l
^
0
s
.
t
.
H
′
l
^
0
-
γ
˘
1
∈
𝒦
31
*
,
l
^
0
∈
𝒦
21
*
,
min
b
′
q
^
0
s
.
t
.
H
′
q
^
0
-
γ
˘
2
∈
𝒦
32
*
,
q
^
0
∈
𝒦
22
*
.
Note that the constraints of the above three problems originate from (14) and (27). Clearly, maximizing d
′
x
^
0 and minimizing both b
′
l
^
0 and b
′
q
^
0 improve our estimation of the error bound.In summary, our algorithm amounts to solving six conic programming problems:C
P
1, C
P
2, (75), and SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
). Conic programs are known to be polynomially solvable. Hence, ours is a polynomial-time algorithm.Of course, withm increases, the computational burden in terms of solving the discretized problems increases. However, the discretized problems are all ordinary conic programming problem and they are polynomially solvable. There exist softwares (e.g., SeCuMi [27], CVXOPT [28], etc.) which can solve conic programming problems efficiently. So the increased computational burden does not really pose a problem in this algorithm.


## 7. Conclusion and Future Work

In this paper, we have developed a duality theory forSSCCP, which is an important extension on SCCP. Specifically, we have shown that the strong duality between SSCCP and its dual is implied by two related ordinary conic programs C
P
1 and C
P
2 being strongly feasible with finite optimal values. We have also developed a polynomial-time approximation algorithm that solves SSCCP to any desired accuracy  with an easily computable error bound, based on the strong duality result.All these results can be readily generalized forSSCCP with three or more stages and with finite number of scenarios in each stage, without essential difficulty.From Theorem11, we know that as m
→
∞, the duality gap tends to 0, and the optimal objective value of the discretized conic program v
(
SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
)
) approaches the optimal objective value of the original SSCCP. In the future, we plan to investigate whether the optimal  solution to SC
P
1
(
π
(
ϵ
1
,
ϵ
2
)
) will also approach the optimal solution to SSCCP.



---

*Source: 896591-2014-01-09.xml*