An Unconstrained Convex Programming Approach to Linear Semi-Infinite Programming.
In this paper, an unconstrained convex programming dual approach for solving a class of linear semi-infinite programming problems is proposed. Both primal and dual convergence results are established under some basic assumptions. Numerical examples are also included to illustrate this approach.
Introduction
. Many linear semi-infinite programming problems including
the L1 and Chebychev approximation problems [14, 15] appear in the following "dual
Program (D)
is a compact set in R n , a(t)
a are continuous functions defined on T .
A corresponding "primal form" linear semi-infinite programming problem can be
represented as follows.
Min
Z
c(t)x(t)d-(t)
s.t.
Z
a
where -(t) is the Lebesgue measure, a particular regular Borel measure, on T and
is measurable on T; x(t) - 0 a.e. with respect to -; and
R
To simplify our expressions, Eq. (1.2) will be denoted by
R
The duality theory relating Programs (P ) and (D) can be found in [17]. Under
certain conditions, a strong duality theorem holds. According to [17], there exist three
"basic" solution approaches, namely, the exchange methods, discretization methods,
and methods based on local reduction. All these methods usually replace Program (D)
by a sequence of finite linear programming problems for approximation and require a
Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor,
Michigan 48109, U.S.A.(cjlin@engin.umich.edu).
y Operations Research and Industrial Engineering, North Carolina State University, Raleigh, NC
27695-7913, U.S.A. The work of this author was supported in part by the 1994 NCSC-Cray Research
Grant (fang@eos.ncsu.edu).
z Institute of Applied Mathematics, National Cheng-Kung University, Tainan, Taiwan, R.O.C.
(soonyi@mail.ncku.edu.tw).
search procedure for global optimization on T . This could be very costly, especially
when T has higher dimensionality [13, 15, 16, 18].
In this paper, we propose a solution approach which identifies an optimal solution
of Program (D) as a limit point of the solutions of a sequence of finite dimensional
unconstrained convex programming problems. No global optimization is required
in the proposed approach but instead, a multidimensional integration is required.
The basic ideas are introduced in Section 2 and main results are given in Section 3.
Primal convergence results are derived in Section 4 and numerical examples are given
in Section 5. The last section includes some concluding remarks.
2. Basic Ideas. Following [11], given - ? 0, we perturb Program (P ) by adding
an entropic term -
R
log x(t)d-(t) to its objective to form a perturbed problem:
Min
Z
Z
log x(t)d-(t)
s.t.
Z
The conjugate dual [4, 21] of Program (P - ) is given as follows.
Program (D - )
Z
e
When its optimal solution exists, we denote x
- (t) as an optimal solution of Program
with an optimal objective value v(P - ). Similarly, w
- denotes an optimal
solution of Program (D - ) with an optimal objective value v(D - ).
Note that (D - ) is an unconstrained convex program which can be treated by
various numerical techniques [8]. This provides an alternative approach even though
the bottleneck becomes the numerical integration of a multidimensional integration
over a compact set T in R n . Compared to Program (D), solving (D - ) is like a penalty
function method [5] with an exponential penalty term -
R
penalty function methods used for semi-infinite programming problems can be referred
to [6, 20]. In this paper we focus on using the exponential penalty function for linear
semi-infinite programming as an extension of the methods developed for solving linear
programming problems [10, 12].
In order to show that the proposed approach works, we need to address three
basic issues [1]:
(i) The existence of an optimal solution w
- to Program (D -
(ii) The existence of a compact set and a positive constant \Theta such that w
lies
in the compact set, 8
(iii) If a sequence fw
g converges to w   as - i ! 0, then w   is an optimal solution
of (D).
In general, issues (i) and (ii) are much more difficult to deal with than the third
one. In this paper, we refer to Borwein and Lewis [2] for issue (i) and resolve the
other two in Section 3. Related results for the finite dimensional case can be found
in [9].
Throughout this paper, two commonly seen assumptions are made:
CONVEX PROGRAMMING APPROACH TO LSIP 3
Program (D) has an interior feasible solution, i.e., fw
(A2) The primal constraint qualification (PCQ) holds, i.e., there exists - x in L 1 (T;
is measurable on T and
R
with respect to the Lebesgue measure,
R
R
and
R
With the assumption (A2), Theorem 4.2 of [2] resolves issue (i) and assures that
both Programs (P - ) and (D - ) attain optimality with v(P -
w   - is optimal to Program (D - ), then
x
is the unique optimal solution of Program (P - ). This provides a dual-to-primal
conversion formula. Also note that since the objective function of Program (D - ) is
strictly concave, under the assumption (A2), its optimal solution w
- can be obtained
by solving the following first order condition:
Z
a(t)e
3. Main Results. The objective of this section is to address issues (ii) and (iii).
Since issue (ii) is more difficult to handle, we start with issue (iii).
Theorem 3.1. If fw
is an optimal solution of
Program (D).
Proof.
Under the assumption (A1), Program (D) has a feasible solution -
with
Z
e
Z
e
If w   is not feasible for Program (D), then there exists - t 2 T such that a( -
Since T is a compact set in R n and a j (t); c(t) are continuous on T , there exists a
neighborhood N and an ffl ? 0 such that a(t) T w   \Gamma c(t) - ffl; for t 2 N
By using L'Hopital's rule, we have
Z
e
Hence the right-hand-side of Eq. since
Z
e
Z
Consequently, the left-hand-side of Eq. (3.1) approaches b T -
causes a contradiction. Therefore, w   must be feasible for Program (D).
4 C.-J. LIN, S.-C. FANG AND S.-W. WU
(Optimality) If w   is not an optimal solution of Program (D), then we can find
a feasible solution -
w with b T -
is optimal for Program (D - i ), we
know
Z
e
Z
e
\Gammac(t)
With the same reason as we had for Eq. (3.3), as
This
again causes a contradiction and hence completes the proof.
As a direct consequence, we have the next result.
Corollary 3.2. If fw
lim
Z
e
Proof. Since
Z
e
Z
e
as
Z
e
\Gammac(t)
Therefore,
lim
Z
e
To handle issue (ii), we make an additional assumption:
(Bounded level set assumption) There exists a constant L such that fw j
is nonempty and bounded.
Note that the assumption (A3) implies that Program (D) is solvable. We shall
keep using this constant L throughout the rest of the paper.
Given that ffl ? 0; l ? 0, - is the Lebesgue measure on T , and -
the following notations:
1. -
2.
3.
4. -
Consequently, the feasible region of the original problem F 4
becomes S(0) and the assumption (A3) becomes that
nonempty and bounded.
Now we prove that, under some conditions, there exist \Theta ? 0 and - l ? 0 such that
lies in a compact set S( - l) " B, 8 In this way, we have a convergent
subsequence which goes to an optimal solution w   .
CONVEX PROGRAMMING APPROACH TO LSIP 5
The basic idea is to use -(w   - ; ffl) as a measure of those t 0 s at which the constraint
lies outside S( - l) " B, we can prove that
-(w
bounded above by zero, which causes a violation of the first order necessary
Z
a(t)e
as
Theorem 3.3. Under the assumption (A3), there exists - l ? 0 such that S( -
is compact.
Proof. It is easy to see that S(l) " B is closed, for l ? 0. Hence we only have to
prove that there exists - l ? 0 such that S( -
If our claim is not true, there must exist a sequence fl i g, with lim i!1 l
that S(l i unbounded. Hence, we can select an unbounded sequence fw l i
with
for each l i . It is obvious that f w l i
is a bounded sequence, thus we
can find a subsequence fk i g of fl i g such that f wk i
converges to a point, say -
as
nonempty, we can find at least one w
being sufficiently small.
Equivalently, for any t 2 T ,
As
Therefore, for
any fi ? 0,
This contradicts the assumption
(A3), under which
By using the constant - l ? 0 obtained in Theorem 3.3, we can derive the following
results:
Lemma 3.4. Given ffl ? 0 and - l
Proof. Since -
is a closed subset of S( - l)"B, it is compact. With -
we have
there exists a sequence f -
is compact, there exists a subsequence which converges to a point -
with -
Hence
a.e. in T:
Remembering that a j (t) and c(t) are continuous on T , we know a(t) T -
. However, since -
B, from its definition, there exists - t 2 T such
6 C.-J. LIN, S.-C. FANG AND S.-W. WU
that a( -
contradicts Eq. (3.8). Thus we have and the
proof follows.
Lemma 3.5. Given any w 0 2 the line segment w
intersects -
at exactly one point.
Proof. Noting that w
there exists at least one - t 2 T such that
Note that for t 2 T with
Together with (3.11), we know such -
ff exists and -
Note that b T (w
We claim that w
Otherwise there are two possible cases:
(Case 1) There exists -
In this
case, we can find a small number fl ? 0 such that a( -
This contradicts the definition of -
ff.
(Case 2) For all
l. In this case, we
can find a small number fi ? 0 such that
This again contradicts the definition of -
ff.
Hence
We now prove that w
is the only
point where w
we know that there exists - t 2 T such that
By Eq. (3.9), we have a( -
Combining with Eq. (3.14), we know
there exists another intersection point, say w
then by the definition of -
ff, we see ff ? -
ff and a( - t) T (w
Hence
this causes a contradiction.
Lemma 3.6. Given ffl ? 0 and - l
Proof. Take
w be the intersection point of w
We can find ff ? 1 such that
(3.
CONVEX PROGRAMMING APPROACH TO LSIP 7
Note that Therefore for each t with
By Lemma 3.4, we further have
The next lemma shows that b T w
sufficiently small.
Lemma 3.7. There exists \Theta 1 ? 0 such that b T w
- L, for
Proof. By the assumption (A3), we can find a point -
w that is feasible for Program
(D) and b T -
Z
e
Z
e
Z
e
Z
e
w is feasible for (D), lim -!0 -
R
there exists a
sufficiently small \Theta 1 such that, for
Z
e
This completes the proof.
Combining the lemmas derived before, we now ready to prove the main result.
Theorem 3.8. Under the assumptions (A1)-(A3), if there exists -
that a(t) T -
, then there exists \Theta ? 0 such that w
- lies in a compact set
Proof. Suppose that the claim is not true. Then, Lemma 3.7 implies that there
exists an infinite sequence fw
whose elements are not in S( -
for each - i . Since
Z
a j (t)e
\Gammac(t)
we have
Z
w)e
By Lemma 3.6, for each i, we have -(w   - i
8 C.-J. LIN, S.-C. FANG AND S.-W. WU
Z
w)e
Z
\Gammac(t)-fflg
Z
\Gammac(t)-fflg
R
\Gammac(t)-fflg (a(t) T -
d-(t) is bounded away from zero. Hence the right hand side of Eq. (3.19) approaches
1, as i !1. This contradicts Eq. (3.18) and completes the proof.
Consequently, the issues (ii) and (iii) have been taken care by the following corollary

Corollary 3.9. Under the assumptions (A1)-(A3), if there exists -
that a(t) T -
, then there exists \Theta ? 0 such that w
- lies in a compact set
sequence fw
with has at least
one convergent subsequence in S( - l) " B, whose limiting point is an optimal solution
of Program (D).
4. Dual Unboundedness and Primal Convergence in Optimal Value.
Note that (A3) is an assumption on bounded level sets. To detect the unboundedness
of the dual program (D), the following lemma may help.
Lemma 4.1. With the assumptions (A1) and (A2), suppose there exists -
such that a(t) T -
goes to infinity, as - i decreases to 0, then
either the program (D) is unbounded above or its optimal solution set is unbounded.
Proof. Assume our conclusion is false, then the program (D) is bounded above
and its optimal solution set is nonempty and bounded. In this case, we let L be the
optimal objective value which is sufficient for the assumption (A3) to hold.
With the assumptions (A1) and (A2) and the existence of -
Theorem 3.8 shows that the sequence fw
lies in a compact
set. This clearly causes a contradiction and the proof follows.
We now turn our attention to investigate the primal convergence of Program
in terms of the optimal objective value. It is important to point out that in our
formulation of program (P ), since the primal variable
where -(t) is the Lebesgue measure, a particular regular Borel measure, the program
may not achieve P -attainment [2, 3, 4]. In other words, program (P ) may not
have an optimal solution x   (t) such that
x
x
Z
e
and x   (t)
However, this does not affect the dual convergence results and
we shall show the convergence of program (P - i ) in terms of optimal objective value.
We start with the following two lemmas:
Lemma 4.2. If fw
such that, for each i ?
CONVEX PROGRAMMING APPROACH TO LSIP 9
Proof. If the claim is not true, then there exists a particular K such that, for any
lies in a compact set T , there is a subsequence which converges to - t
with
This contradicts the fact that
Hence the proof is complete.
Note that when w
is optimal to Program (D - i ), Eq. (2.4) holds as
Z
a j (t)e
m. Now, if there exists -
then Eq. (4.1) implies that
Z
w)e
\Gammac(t)
and
Z
e
This leads to the following result:
Lemma 4.3. If there exists -
R
Combining Lemmas 4.2 and 4.3, we have the following convergence result:
Theorem 4.4. If fw
0, and there exists -
such that a(t) T -
lim
Z
x
(t) log x
and
lim
Z
c(t)x
Proof. Given ffl ? 0, let
w . Lemma 4.2 provides an N ? 0 such that, for
Then from Eqs. (2.3), (4.2) and (4.3), for i ? N , we have
Z
x
(t) log x
Z
Z
e
\Gammac(t)
Therefore,
lim
Z
x
(t) log x
Since
Z
c(t)x
Z
x
(t) log x
Z
e
as
lim
Z
c(t)x
This clearly shows the primal convergence of program (P - i ) in terms of the optimal
objective value.
5. Numerical Examples. In this section, three numerical examples are re-
ported. Our purpose is not to claim any computational superiority of the proposed
method. Instead, we simply intend to illustrate the computational behavior the proposed
approach. Note that the proposed approach is flexible to use any commercial
or public unconstrained nonlinear optimizer, instead of developing special codes for
our own implementation. In our examples, the L-BFGS-B software [22] was applied.
5.1. L1 Problems. In this subsection, the following two commonly seen L1
problems [14, 15] were tested:
Problem 1
Problem 2
CONVEX PROGRAMMING APPROACH TO LSIP 11

Table
Problem 1
const. comp. slackness
It was reported in [14, 15] that 0.6931 and -1.78688 are approximate optimal
solutions to Problem 1 and Problem2, respectively.
We applied the L-BFGS-B subroutines [22] to solve Program (D - ) with the standard
default setting in the "driver1.f" of the L-BFGS-B solver. The stopping criteria
of L-BFGS-B was given by
where f is the function to be optimized and f k , f k+1 are the values of f in the k-th
and (k+1)-th iteration, respectively. Moreover, epsmch = 2:22 \Theta 10 \Gamma16 , which reflects
the machine accuracy for our Silicon Graphics workstation, and factr was set to be
A trivial initial solution with chosen for Problem 1.
The numerical results of the proposed approach is shown by Table 5.1.
In the table, "argmin
\Gammac(t)g, "min
\Gammac(t)g, and "comp.
Z
c(t)e
Z
c(t)x
Z
x
(t) log x
Z
x
The final w
we obtained for problem 1 is
Similarly, we chose a trivial initial solution with
2. The numerical results is shown in Table 5.2.
The final w
we obtained for problem 2 is
The first three columns of both tables clearly show that b T w
converges to the
reported solution up to the 4-th digit after the decimal point, as - i decreases. The

Table
Problem 2
const. comp. slackness

Table
Two dimensional problem
argmins argmin t min const. comp. slackness
last two columns of both tables also show that the dual feasibility and complementary
slackness conditions are satisfied up to the 4-th digit after the decimal point, when - i
is small enough.
The computational bottleneck of the proposed approach lies in the following in-
tegration
Z
e
Numerically, we need to discretize T for integration. When - i is getting smaller, a
finer discretization of T is needed. This could be very time-consuming, especially
when T has a high dimensionality. In our examples, we partition
400,000 intervals and use the Simpson's method for integration.
5.2. Two Dimensional Problem. In this subsection, the following two-dimensional
problem on page 112 of [15] was tested:
It was reported in [7] that 2.4356 is an approximate optimal objective value. We
followed all settings as described in the previous subsection with an initial solution
The numerical results are shown in Table 5.3.
CONVEX PROGRAMMING APPROACH TO LSIP 13
The final w
we obtained is
For this two dimensional problem, we partitioned [0; 1] \Theta [0; 1] into 1500 2 intervals
for integration. The computational behavior of this case is quite similar to
those reported in the previous subsection. The proposed approach indeed generates a
convergent solution which satisfies the dual feasibility and complementary slackness
conditions.
Because the numerical integration of
R
could be difficult for
a general problem, we do not claim any computational superiority of the proposed
approach. However, the proposed approach does provide a new angle to solve the
linear semi-infinite programming problems.
6. Concluding Remarks.
1. We have proposed an unconstrained convex programming approach to solving
linear semi-infinite programming problems. In this approach, solving Program
(D - ) with a sufficiently small - ? 0 provides an approximate solution
to Program (D).
2. A dual convergence result shows that, under the assumptions (A1)-(A3),
(D in terms of optimal solutions.
3. A primal convergence result shows that (P - in terms of
optimal objective values.
4. Compared to most known methods, the proposed approach does not require
any search procedures for finding a global optimizer over T . Instead, an
integration over T is required. We do not claim any computational superiority
of the proposed approach. However, it does provide an alternative. For
some problems, it might be easier to do integration than to perform a global
optimization over T .
5. The proposed approach is flexible to use any unconstrained nonlinear opti-
mizer. Three examples were included to illustrate the proposed approach.

Acknowledgment

:. The authors would like to thank Dr. A. R. Conn and referees
for their constructive comments.



--R

Analysis and Methods
Convergence of best entropy estimates


Survey of penalty
An exact penalty function for semi-infinite programming
A projected Lagrangian algorithm for semi-infinite program- ming
Numerical Methods for Unconstrained Optimization and Nonlinear Equations
An existence theorem for penalty function theory
Linear Optimization and Extensions: Theory and Algo- rithms
Linear programming with entropic perturbation

An inexact approach to solving linear semi-infinite programming problems
An interior point algorithm for semi-infinite linear pro- gramming



A dual affine scaling based algorithm for solving linear semi-infinite programming Problems
The Math Works Inc.
The potential method for conditional maxima in the locally compact metric spaces
Convex Analysis

--TR

--CTR
A. Ismael F. Vaz , Edite M. G. P. Fernandes , M. Paula S. F. Gomes, SIPAMPL: Semi-infinite programming with AMPL, ACM Transactions on Mathematical Software (TOMS), v.30 n.1, p.47-61, March 2004
convex programming;entropy optimization;linear programming;semi-infinite programming