数理解析研究所講究録
第 1879 巻 2014 年 97-106

97

A simplicial algorithm with$\omega$- $k$sections and its convergence

Takahito Kuno *and Tomohiro Ishihama \dag er
Graduate School of Systems end Information Engineering
University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan

Abstract
The simplicial algorithm is a kind of branch-and-bound method for solving convex maximization problems. The subdivision rules sufficient for convergence include -subdivision,-bisection and the conventional bisection. In this paper, we develop a new convergent
subdivision rule interpolating -bisection and -subdivision.
$\omega$$\omega$$\omega$$\omega$

Key words: Global optimization, convex maximization, branch-and-bound, simplicial
algorithm, subdivision rule.

1

Introduction

Branch-and-bound is a potent tool for solving convex maximization problems, a typical classof multiextremal global optimization problems. Algorithms based on branch-and-bound canbe categorized roughly into three types: the conical algorithm [13], which subdivides thefeasible set using a set of cones in the branching step, and narrows down the cone containing an
optimal solution with the help of concavity cuts in the bounding step; the simplicial algorithm[3], which uses simplices instead of cones in the branching step, and carries out the bounding
steps using concave envelopes; and the rectangular algorithm [1], which uses rectangles inthe branching step and can be applied to only separable objective function problems. Unlike
discrete optimization problems, no matter how many times the branching step is repeated,
continuous optimization problems never yield trivial subproblems in general. Therefore, theconvergence analysis is essential in developing deterministic branch-and-bound algorithms
for convex maximization. In each type of branch-and-bound algorithms, it is observed thatthe convergence is accelerated by using the -subdivision rule, which exploits a by-productof the bounding step to subdivide cones, simplices or rectangles in the branching step. The
convergence when using this rule was proven by Jaumard-Meyer [5, 6], Locatelli [9] andKuno-Ishihama [8] for the conical algorithm, by Locatelli-Raber [10, 11] and Kuno-Buckland$\omega$*The author was partially supported by the Grant-in-Aid for Scientific Research $(C$ 25330022 from the Japan
Society for the Promotion of Sciences. -mail: takahito@cs.tsukuba.ac.jp\dagger Current affiliation: $NS$ Solutions Corporation, Tokyo 104-8280, Japan.
$)$

$E$

98
[7] for the simplicial algorithm, and by Falk-Soland [1] and Soland [12] for the rectangle

algorithm.
In [7, 8], they also proposed a new kind of subdivision rule, called -bisection, which isa hybrid of -subdivision and the conventional bisection. In this paper, we extend this idea
and develop a rule for subdividing each simplex into a prescribed number of subsimplices
in the branching step of the simplicial algorithm. In Section 2, we formulate the convex
maximization problem and illustrate how the simplicial algorithm solves it. In Section 3, we
modify the relaxed problem solved in the bounding step and review the convergence under theusual -subdivision rule. In Section 4, for a given number , we develop a convergent rule
for subdividing each simplex into subsimplices in the branching step. If $k=2$ , then thissubdivision rule coincides with -bisection; and if is equal to the problem dimension, it is
the usual -subdivision. In Section 5, we report the results of a numerical comparison among-bisection, trisection, quadsection, and the usual -subdivision.
$\omega$$\omega$$k$$\omega$$k$$k$$\omega$$\omega$$\omega$$\omega$

2 Simplicial algorithm for convex maximization
The problem considered in this paper is as follows:

maximize$f(x)$

subject to Ax(1)$\leq b,$. The objective function is a nonlinear convex function definedon an open convex set, which is assumed to be large enough to contain an -simplex
where$A\in \mathbb{R}^{m\cross n}$

and

$f$

$b\in \mathbb{R}^{m}$$n$$\Delta^{1}$

enclosing the feasible set$D=\{x\in \mathbb{R}^{n}| Ax\leq b\}.$Also the following are assumed throughout the paper:(Al) The set $D$ is bounded and contains the origin$0\in \mathbb{R}^{n}$as an interior point.

(A2) The objective function value $f(x)$ is nonnegative and bounded for any$x\in\Delta^{1}.$The simplicial algorithm is a kind of branch-and-bound algorithm for solving the multiextremal problem (1) to optimality. In the preprocessing, the feasible set is enclosed in the-simplex , which is given as conv $\{v_{j}^{1}|j=1, \ldots,n+1\}$ , the convex hull of $n+1$ affinely
is subdivided into a set of subsimplices
independent vectors. In the branching step,, satisfying$D$$\Delta^{1}$$n$$\Delta^{1}$$\Delta^{i},$$i\in \mathscr{I}$$\Delta^{1}=\bigcup_{i\in \mathscr{I}}\Delta^{i}$;$int\Delta^{r}\cap int\Delta^{s}=\emptyset$,

if$r,s\in \mathscr{I}$and $r\neq s,$

where
is an (infinite) index set, and int represents the set of interior points. Associatedwith each is a subproblem:$\mathscr{I}$$\cdot$$\Delta^{i}$maximize$f(x)$

subject to$x\in D\cap\Delta^{i}.$

(2)

99
Since (2) is essentially the same problem as the original (1), it cannot be solved directly.
In the bounding step, replacing $f$ by its concave envelope , a minimal concave function
overestimating $f$ on , the following relaxed problem is solved:$g^{i}$$\Delta^{i}$maximizesubject to$g^{i}(x)$(3)$x\in D\cap\Delta^{i}.$In our case, where $f$ is convex, is an affine function which agrees with $f$ at the vertices of. This implies that (3) isjust alinear program and can be solved easily. Let be an optimal
solution of (3). Then we have$g^{i}$$\Delta^{j}$$\omega^{i}$$g^{i}(\omega^{i})\geq f(x) , \forall x\in D\cap\Delta^{i}.$Therefore, if
for the incumbent solutionof (1) obtained during the algorithm, we can conclude that
contains no solution better than and discard it from further$g^{i}(\omega^{i})\leq f(x^{*})$$x^{*}$$\Delta^{i}$$x^{*}$

consideration. Otherwise, is again subdivided into smaller subsimplices in the branching
step. Unlike discrete optimization problems, no matter how many times the branching andbounding steps are repeated, (2) can have infinitely many feasible solutions. In that case, atleast one infinite sequence of simplices is generated in a nested fashion:$\Delta^{i}$(4)$\Delta^{1}\supset\Delta^{2}\supset\cdots\supset\Delta^{i}\supset\Delta^{i+1}\supset\cdots.$

The convergence of the simplicial algorithm depends largely on how to subdivide the simplex
conv $\{v_{j}^{i}|j=1, \ldots,n+1\}$ . The simplest subdivision rule is bisection, where thelongest edge of is cut at the midpoint. Thenis divided into two subsimplices, eitherof which is the successor
in the sequence (4). Under this rule, the sequence graduallyshrinks to a single point. Since
for $i=1,2,$ , we have, as
. This exhaustiveness guarantees that the incumbent converges to a globally optimal
solution of (1).
Although not exhaustive, an often-used altemative is -subdivision. The simplex
issubdivided into up to $n+1$ subsimplices, radially at . Let be an index set such thatif
is affinely independent of ’s for $j\neq r$ . Then the children of are given as$\Delta^{i}=$$\Delta^{i}$$\Delta^{i}$$\Delta^{i+1}$$\omega^{i}\in\Delta^{i}$$|g^{i}(\omega^{i})-f(\omega^{i})|arrow 0$$\ldots$$iarrow\infty$$x^{*}$$\Delta^{i}$$\omega$$\omega^{i}$$J^{i}$$r\in J^{i}$$\omega^{i}$$v_{j}$$\Delta^{i}$$\Delta^{i_{r}}=conv\{v_{1}^{i}, \ldots,v_{r-1}, \omega^{i},v_{r+1}^{i}, \ldots,v_{n+1}^{i}\}, r\in J^{i}.$The subdivision rule has been said to be empirically more efficient than bisection. The
theoretical convergence was, however, an open question for some decades until LocatelliRaber proved it in 2000 [10, 11]. In the succeeding section, we will outline an easier altemative
proof given in [7], which provides a clue leading to another kind of convergent subdivision$\omega-$

rule.

100
3 Relaxation of the relaxed subproblem
Introducing an auxiliary variable$\tau\geq 0$, let us relax the feasible set $D$ a little bit into$D(\tau)=\{x\in \mathbb{R}^{n}| Ax\leq(1+\tau)b\}.$Since $b>0$ under the assumption (Al), it holds that
$D=D(0)\subset D(\tau’)\subset D(\tau") , if0\leq\tau’\leq\tau".$

Definition 3.1. For a positive constant(1) if $x\in D(\sigma)$ .

$\sigma$, a point$x$is referred to as a$\sigma$-feasible solution of

Let $\sigma>0$ be a prescribed tolerance, and let$F^{i}= \max\{f(v_{j}^{i})|j=1, \ldots,n+1\}, i=1,2, \ldots.$

Note that is nonnegative under the assumption (A2), and besides nonincreasing in . Let us
select a number $M$ to satisfy$F^{i}$$i$$M>F^{1}/\sigma,$and define a problem in and :$x$$\tau$$(P^{i})$

It is easy to see that$(P^{i})$$e\in \mathbb{R}^{n+1}$$g^{i}(x)-M\tau$$x\in D(\tau)\cap\Delta^{i},$$\tau\geq 0.$

is equivalent to a linear programmaximizesubject towheremaximizesubject to$d\lambda-M\tau$$AV\lambda-b\tau\leq$b, e $\lambda=1,$(5)$\lambda\geq 0,$$\tau\geq 0,$

is the all-ones vector, and$d=[g^{i}(v_{1}^{i}), \ldots,g^{i}(v_{n+1}^{i})]=[f(v_{1}^{i}), \ldots,f(v_{n+1}^{i})], V=[v_{1}^{i}, \ldots,v_{n+1}^{i}].$

The dual problem of (6) is written as

minimizesubject to$\mu b+v$$\mu AV+ve\geq d,$(6)$vb\leq M,$$\mu\geq 0.$

Since (5) is always feasible and the objective function is bounded from above by , both, respectively. Obviously, an
and(5) and (6) have optimal solutions, denotedwithis then given by
optimal solution of$F^{i}$$(\lambda^{i}, \tau^{i})$$(P^{i})$

Proposition 3.1. If
problem (2), i. e.,$(\omega^{i}, \tau^{i})$$D\cap\Delta^{j}\neq\emptyset$$(\mu^{i}, v^{i})$$\omega^{j}=V\lambda^{i}.$, then the optimal $\nu alue$ of$(P^{i})$is an upper bound on the sub-$g^{i}(\omega^{i})-M\tau^{i}\geq f(x) , \forall x\in D\cap\Delta^{i}.$101
Proposition3.2. If $g^{i}(\omega^{i})-M\tau^{i}<0$, then

. Otherwise,$D\cap\Delta^{i}=\emptyset$$\omega^{i}$is aof (1).

$\sigma$-feasible solution‘
Iftums out to be empty, then is discarded from further consideration. We may
therefore assume thatfor every . Letand$D\cap\Delta$$\Delta^{i}$$g^{i}(\omega^{i})-M\tau^{i}\geq 0$

conv$\Delta$

Then$\Delta_{+}^{i}$is a$|J^{i}|$-face of$\Delta^{i}$$\omega^{i}\in D(\sigma)$$J^{i}=\{j|\lambda_{j}^{i}>0\}.$$\{v_{j}^{i}|j\in J^{i}\},$, on which$\omega^{i}$$i$lies. Even more remarkable is the following:

Lemma 3.3. It holds that$g^{i}(x)\leq\mu^{i}Ax+v^{i}, \forall x\in A.$

In particular,$g^{i}(x)=\mu^{i}Ax+v^{i}$

Lemma 3.3 suggests that we can adopt
as follows:$\mu^{i}A$

,

if

and

$v^{i}$$x\in A_{+}^{i}.$as the coefficients and write$g^{i}$

explicitly$g^{i}(x)=\mu^{i}Ax+v^{i}, i=1,2, \ldots.$

Then we can show the following:

Lemma 3.4. The gradient of$g^{i}$

is bounded, i. e., there exists a constant such that
$L$$\Vert\mu^{i}A\Vert\leq L, i=1,2, \ldots.$

Lemma 3.5. It holds that$g^{k}(x)\leq g^{i}(x) , x\in\Delta_{+}^{k}, i=1, \ldots,k.$Lemma 3.6. If
is generated by subdividing radially at an arbitrary point
each , then there exists a subsequence $\{i_{r}|r=1,2, \ldots\}$ such that$\Delta^{i+1}$$\Delta^{i}$$u^{i}\in\Delta_{+}^{i}for$$i$$u^{i_{2s-1}}\in\Delta_{+}^{i_{2s-1}}\cap\Delta_{+}^{i_{2s}}, s=1,2, \ldots.$

Using these lemmas, together with the bounded convergence principle (see e.g., Lemma
III.2 in [4] , we can derive a convergence result:$)$

Theorem 3.7. If
each , then$\Delta^{i+1}$

is generated by subdividing$\Delta^{i}$

mdially at an arbitrary point$u^{i}\in\Delta_{+}^{i}$

for

$i$

$\lim_{iarrow}\inf_{\infty}|g^{i}(u^{i})-f(u^{i})|=0.$, the convergence of the algorithm with the usual
Since,
for each is just a corollary of Theorem 3.7:$\omega^{i}\in\Delta_{+}^{i}$$u^{i}=\omega^{i}$$\omega$-subdivision, where$i$

Corollary 3.8. If$\Delta^{i+1}$

is generated by subdividing$\Delta^{i}$radially at$\lim_{iarrow}\inf_{\infty}|g^{i}(\omega^{i})-f(\omega^{i})|=0.$$\omega^{i}$for each , then
$i$

102
Theorem 3.7 is, however, not sufficient to ensure the convergence to an optimal solution
or an approximately optimal solution of (1). For this purpose, we need to further restrict thefor each , as in Corollary 3.8, and update
selection of for each . If we selectthe incumbent withappropriately, then converges to an optimal -feasible solution
which satisfies
and $f(x^{*})\geq f(x)$ ,$u^{i}$$u^{i}=\omega^{i}\in\Delta_{+}^{i}$$i$$\omega^{i}$$x^{*}$$i$$x^{*}$$\sigma$$\forall x\in D$$x^{*}\in D(\sigma)$

Although it is a rather satisfactory result from a theoretical viewpoint, -subdivision rule hasa serious weakness, i.e., is subdivided into up to $n+1$ subsimplices for each . This meansthat we need to solve $n+1$ linear programs, in the worst case, to update the upper bound on$f$ over. To overcome this, we develop a new subdivision rule called -ksection, whichholds the number of subsimplices generated at a time below a prescribed number $k\leq n+1.$$\omega$$\Delta^{i}$$i$$D\cap\Delta^{i}$$\omega$

4 Simplicial algorithm based on
In establishing the$\omega$$\omega\cdot ksection$-ksection rule, we need to make an additional assumption:(A3) The objective function $f$ of (1) is strictly convex.

Therefore, if$x^{1}\neq x^{2}$, we assume$f((1-\lambda)x^{1}+\lambda x^{2})<(1-\lambda)f(x^{1})+\lambda f(x^{2}) , \forall\lambda\in(0,1)$.

Let$k^{i}= \min\{k, |J^{i}|\}, i=1,2, \ldots.$-ksection rule, is subdivided radially at a point in a -face of . Before giving thedetail, let us see how the sequence (4) behaves under the assumption (A3) if such a subdivision
rule is applied.
In the$k^{i}$$\Delta^{i}$$\omega$$\Delta_{+}^{i}$

Lemma 4.1. If
is generated by subdividing radially at a point in a face ofeach , then $\{v_{j}^{i}|i=1,2, \ldots\}$ has an accumulation point for $j=1,$ $\ldots,n+1$ . Among
there exists an accumulation point of $\{u^{i}|i=1,2, \ldots\}.$$\Delta^{i+1}$$u^{i}$$\Delta^{i}$$i$$k^{i}$$v_{j}^{0}$$\Delta_{+}^{i}for$$v_{j}^{0\prime}s,$$u^{0}$On the basis of this observation, let us develop the procedure for

Figure 1). For each subset$K\subset J^{i}$with $|K|=k^{i}$ , let$u_{K}=\sum_{j\in K}\frac{\lambda_{j}^{i}}{\Lambda_{K}}v_{j}^{i}, \Lambda_{K}=\sum_{j\in K}\lambda_{j}^{i}.$Also let$p_{K}= \min\{\Vert v_{j}^{k}-u_{K}\Vert|j\in K\}.$

Among$u_{K}$’s we select as$u^{i}$

the one with the largest$p_{K}$, say$p_{K^{i}}= \max\{p_{K}|K\subset J^{i}, |K|=k^{i}\}.$$\omega$-ksection (also see

103

Figure 1:For$u^{i}=u_{K^{i}}$, the children of$\Delta^{i}$$\omega$-Bisection when $J^{i}=\{1,2,4\}.$are given as$\Delta^{i_{r}}=conv\{v_{1}^{i}, \ldots,v_{r-1}^{i},u^{i},v_{r+1}^{i}, \ldots,v_{n+1}^{i}\}, r\in K^{i},$some one of which is adopted as$\Delta^{i+1}$

in (4).

Lemma 4.2. There exist a number $k^{0}\in\{2, \ldots,k\}$ and a set $J^{0}\subset\{1, \ldots,n+1\}$ such that
andfor infinitely many . Moreover,$k^{i}=k^{0}$$J^{i}=J^{0}$(i) for each$i$$K\subset J^{0}$with $|K|=k^{0}$ , the sequence $\{v_{K}^{i}|i=1,2, \ldots\}$ has an accumulation point, and$v_{K}^{0}\in\{v_{j}^{0}|j\in K\}$(ii) for each $j\in J^{0}$ , the sequence $\{\lambda_{j}^{i}|i=1,2, \ldots\}$ has an accumulation pointthat$\lambda_{j}^{0}\geq 0$such$\sum_{j\in J^{0}}\lambda_{j}^{0}=1.$

Theorem 4.3. If, then$\Delta^{i+1}$

is generated by subdividing$\Delta^{i}$

according to the$\omega$-ksection rule for each$i$$\lim_{karrow}\inf_{\infty}|g^{i}(\omega^{i})-f(\omega^{i})|=0$.

(7)

Let us incolporate the -ksection rule into the simplicial algorithm. For two prescribed$\sigma>0$
tolerances
and a number $k\in\{2, \ldots,n\}$ , the algorithm can be described as follows:$\omega$$\epsilon\geq 0,$

algorithm $simplicia1_{-}\omega_{-}ksection$find an -simplex
conv
enclosing ;$M>F^{1}/\sigma$
select a number
for $F^{1}= \max\{f(v_{j}^{1})|j=1, \ldots,n+1\}$ ;define the convex envelope of $f$ on ;solve
of maximizing $g^{1}(x)-M\tau$ subject to
and
let
;
for an optimal solutionof$n$$\Delta^{1}=$$\{v_{1}^{1}, \ldots,v_{n+1}^{1}\}$$g^{1}$$(P^{1})$$\alpha(\Delta^{1})arrow g^{1}(\omega^{1})-M\tau^{1}$$D$$\Delta^{1}$$x\in D(\sigma)\cap\Delta^{1}$$(\omega^{1}, \tau^{1})$$\tau\geq 0$$(P^{1})$

;

104
;

$(x^{1},\beta^{1})arrow(\omega^{1},f(\omega^{1}));\mathscr{L}arrow\{\Delta^{1}\};iarrow 1$

while

do
select a simplex
if$\mathscr{L}\neq\emptyset$

conv$\Delta^{i}=$$\alpha(\Delta^{i})\leq \mathscr{L}arrow\emptyset(1+\epsilon)\beta^{i}$$\{v_{1}^{i}, \ldots,v_{n+1}^{i}\}$with the largest value of$\alpha$from$\mathscr{L}$

;

then

else
;
denote the -feasible solution providing
letaccording to -ksection;
identify the set $K^{i}\subset\{1, \ldots,n+1\}$ and the point
;
for
conv
subdivide into
doforof $f$ on ;define the concave envelope
;
and
solve
of maximizing $g^{i_{r}}(x)-M\tau$ subject tooffor an optimal solution
letend for;arg max $\{f(x)|x=x^{i}, \omega^{i_{r}},r\in K^{i}\}$ and let$\omega^{i}$$\alpha(\Delta^{i})$$\sigma$$u^{i}\in\Delta^{i}$$\Delta^{i_{r}}=$$\Delta^{i}$$\omega$$\{v_{1}^{i}, \ldots,v_{r-1}^{i},u^{i},v_{r+1}^{i}, \ldots,v_{n+1}^{i}\}$$r\in K^{i}$$r\in K^{i}$$\Delta^{i_{r}}$$g^{i_{r}}$$x\in D(\sigma)\cap\Delta^{i_{r}}$$(P^{i_{r}})$$(\omega^{i_{r}}, \tau^{i_{r}})$$\alpha(\Delta^{i_{r}})arrow g^{i_{r}}(\Phi^{i_{r}})-M\tau^{i_{r}}$$x^{i+1}arrow$$\tau\geq 0$$(P^{i_{r}})$$\beta^{i+1}arrow f(x^{i+1})$$\mathscr{L}arrow \mathscr{L}\cup\{\Delta^{i_{r}}|r\in K^{i_{r}}\}\backslash \{\Delta^{i}\};iarrow i+1$

end ifend whileend.

. If the algorithm $simplicial_{-}\omega$ -ksection terminates afler iteraTheorem 4.4. Suppose
tions, then is an optimal -feasible solution of $(l)$ . Even if not, every accumulation point of
the sequence $\{x^{i}|i=1,2, \ldots\}$ is an optimal -feasible solution.
$\epsilon=0$$x^{i}$$i$$\sigma$$\sigma$

Let us introduce the following notion of solution to the convex maximization problem (1):Definition 4.1. For two positive constants
optimal solution of (1) if$x^{*}\in D(\sigma)$

and

and

$\epsilon$$\sigma$, a point$f( x^{*})\geq\frac{1}{1+\epsilon}f(x)$,$x^{*}$

is referred to as an$(\epsilon, \sigma)-$$\forall x\in D.$, then the algorithm $simplicial_{-}\omega$ -ksection terminates after finitely
Corollary 4.5. If-optimal solution of (1).
many iterations and yields an$\epsilon>0$$x^{k}$$(\epsilon, \sigma)$

5 Numerical results
Lastly, let us report numerical results of comparing the algorithm when using -bisection,-trisection, -quadsection, and the usual -subdivision. The test problem was a convex
quadratic maximization problem of of the form$\omega$$\omega$$\omega$$\omega$maximize $f(x)+5.0dy$
subject to Ax

$+$

By

$\leq b$, (x,y)(8)$\geq 0,$

105$\frac{Tab1e1:Averagenumber.ofbranchingsand.CPUtime(inseconds)}{m\cross nk\frac{q=02n}{\# time}\frac{q=03n}{\# time}\frac{q=0.4n}{\# time}}$

3.2
3.0
3.0
3.0
3.6
3.6
3.9

2
3
4

$60\cross 100$

$q+1$

2
3
4

$60\cross 150$

0.08190.07740.07970.07940.13730.12800.137811.2 0.2304
6.7 0.1526

6.8
6.8
10.4
10.0
11.1

204.4 4.044
272.2 4.459
326.7 5.218
296.2 4.528
19.6 0.8458
24.5 0.8985
25.0 0.8913

0.15930.15940.38610.33190.3556$\frac{q+13.90.135411.30.340121.20.7353}{80\cross 15025.40.333342.42.486}$

1.8
1.8
1.8
1.8

3
4
$q+1$

0.14580.14590.14920.1463

5.3 0.3161
5.5 0.3179
5.5 0.3117

112.2
206.4
134.6

5.556
9.914
6.118

where
$f(x)=0.5x^{T}Qx+cx.$

To make the feasible set bounded, the vector
was fixed to 1, , 1,
and all components of the last law of
andwere set to ones. Other entries of $A,$
together with components of, were generated randomly in the intervaland$[-0.5,1.0]$ , so that the percentages of zeros and negative numbers were about 20% and 10%,respectively. The matrix
was symmetric, tridiagonal, and the tridiagonal entries
were random numbers in [0.0, 1.0]. Note that the objective function of (8) can be linearized
simply by replacing the nonlinear part $f$ with its concave envelope. Therefore, we may perform the branching procedure in the -space of dimension $q\leq n$ , not in the whole space ofdimension . In accordance with this decomposition principle [4], we coded all computer programs in GNU Octave [2], and tested those on a single core of Intel Core i7 $(3.20GHz)$ . The
values of the two tolerances and were fixed atand $10^{-10}$ , respectively.
Table 1 shows the computational results. Three different sizes $(60, 100)$ , $(60, 150)$ and$(80, 150)$ were selected as $(m,n)$ , andwas set to 20%, 30% and 40% of the whole set ofvariables for each $(m,n)$ , i.e., the triple $(m,n,q)$ was up to $(80, 150,60)$ . Ten instances weresolved for each $(m,n,q)$ . The column labeledlists the average number of iterations, and‘time’ lists the average computational time in seconds; and the rows $k=2,3,4$ , and $q+1$
represent the results of -bisection, -trisection, -quadsection, and the usual -subdivision,respectively.
We immediately see from Table 1 that both the number of iterations and the CPU time increase rather rapidly, as the percentage of nonlinear variables increases, for every subdivision
rule. It is, however, a well-known characteristic common to deterministic global optimization
algorithms. Instead, we should notice that there is a little difference in performance among
the four subdivision rules. It is presumed that the numberofspanning is in general$b\in \mathbb{R}^{m}$$[$$\ldots$$n]^{T}$$B\in \mathbb{R}^{m\cross(n-q)}$$A\in \mathbb{R}^{m\cross q}$$d\in \mathbb{R}^{n-q}$$c\in \mathbb{R}^{q}$$Q\in \mathbb{R}^{q\cross q}$

$x$

$n$

$\epsilon$$10^{-5}$$\sigma$

$q$

$\#$

$\omega$$\omega$’$\omega$$\omega$$|J^{i}|$$\omega^{i}$$v_{j}^{i\prime}s$

106rather small compared with. As a result, the number of children of would be often de$\Delta^{i}$$k^{i}$$q$. This finding needs to be confirmed in further studies. Anyway, we may conclude
fined bythat the -ksection rule performs at least as well as the usual -subdivision when $k=2,3,4.$$|J^{i}|$$\omega$$\omega$

References[1] Falk, J.E., and R.M. Soland, “An algorithm for separable nonconvex programming problems”, Management Science 15 (1969), 550-569.
[2] GNU Octave, http: $//www.gnu.org/$ software/octave/.

[3] Horst, R., ‘An algorithm for nonconvex programming problems”, Mathematical Programming 10 (1976), 312-321.
[4] Horst, R. and H. Tuy, Global optimization:
Springer-Verlag (Berlin, 1993).

Deterministic Approaches, 2nd ed.,[5] Jaumard, B., and C. Meyer, “A simplified convergence proof for the cone partitioning
algorithm”, Joumal of Global optimization 13 (1998), 407Al6.

[6] Jaumard, B., and C. Meyer, “On the convergence of cone splitting algorithms withsubdivisions”, Journal of optimization Theory and Applications 110 (2001), 119-144.

$\omega-$[7] Kuno, T., and PE.K. Buckland, “A convergent simplicial algorithm with -subdivisionand -bisection strategies”, Joumal of Global optimization 52 (2012), 371-390.
$\omega$$\omega$-bisection for concave-13-20, University of Tsukuba (Ibaraki, 2013).

[8] Kuno, T., and T. Ishihama, “A convergent conical algorithm withminimization”, Technical Report$CS$ - $TR$

[9] Locatelli, M., “Finiteness of conical algorithm withgramming 85 (1999), 593-616.

$\omega$$\omega$-subdivisions”, Mathematical Pro-[10] Locatelli, M., and U. Raber, “On convergence of the simplicial branch-and-bound algorithm based on -subdivisions”, Journal of optimization Theory and Applications 107(2000), 69-79.
$\omega$[11] Locatelli, M., and U. Raber, “Finiteness result for the simplicial branch-and-bound algorithm based on -subdivisions”, Joumal of optimization Theory and Applications 107(2000), 81-88.
$\omega$[12] Soland, R.M., “Optimal facility location with concave costs”, Operations Research 22(1971), 373-382.
[13] Tuy, H., ”Concave programming under linear constraints”, Soviet Mathematics 5 (1964),

1437-1440.