S m , J. W.: Monotone Data Smoothing by Quadratic Splines 299

ZAMM * Z. angew. Math. Mech. 70 (1990) 8,299-307

&2?IWDT, J. w. Akademie-Verlag Berlin

Monotone Data Smoothing by Quadratic Splines via Dualization

Fiir dfe Aufgabe des monotonen GEttens von eindhensionalen Daren wird ah Zie@nktion eine gewichtete Summe verwendet. Durch den ersten SummMden wird eine Minimierung der Kriimmung angestrebt. wcihrend der gegediufige zweite Summand im Fall von Interpolation minimal ausfdlt. Die Monotonieforderung wird als Nebenbedingung beriicksichtigt. Bei Verwendung w n quadratischen Splines IaJt sich diese Gliittwtgsaufgabe zu einem quadratischen Optiwiierungsprobkm fiitisieren. und hierzu wiederum gibt es eine duale Aufgabe, welche ohne Nebenbedingungen auskommt. Aus numerischen Gribulen ist daher dieser Zugang zugkrijlig. Zus&tzlich kann der optimale Spline iiber eine Riickrechnungsformel direkt aus einer besung der dualen Aggabe errechnet werden. Die Dualisierung und interessierende Dualititsaussagen werden hier aus der Eenchel-Theorie gewonnen. SchlieJlich sei erwahnt. daj sich die Berechnung der erforderlichen Fenchel-Konjugierten h c h Vorgabe einer der Variabkn merklich erkichtern Iapt.

For monotone smoothing of univariate data sets an objective function is used which represents a trade-of/ between curvature minimization and interpolation. The monotonicity condition is taken into the constraints. Using quadratic splines this smoothing problem is discretized by a quadratic program, and this in turn can be dualized in such a way that an unconstrained program results. In addition, a return-formula holds true by means of which the optimal spline is directly computed from a solution of the dual probkm. Thus, from a numerical point of view this approach is attractive. Here the dualization is performed via Fmhel's theory. For computing the needed Fenchel conjugates it is convenient to f i x one of the variables.

B K a u e m tfemed @ymcyuu 3adauu Monomonnozo cz~axui?anun Mnoxecma odrw.uepnux dannux unonb3yemcs eweuienan cyrwrwa. lTepoe ee c l l ( l t ~ ~ o e omeuaem 3a M W U M ~ ~ ~ ~ W K p w n u , a npomueoenunmtqee emopoe cnazaeMw MWUMWWO e cnyuae unmepnomyuu. Tpe6wanue Monomonnocmu eucmynaem K ~ K ozpanuuenue. n' noMotqu napa6oflu- ~ ~ ~ C K U X crmniw~ 3my 3adauy Moxno npti6nuxenno 3a.uemmb KoneunoMepnoii npo6ne.ud K ~ ~ ~ ) ~ ~ ~ U U H O Z O npozpuupoea- nu. EIS coonnwmmwyem & d c m e w u 3adaw 6e3 ozpauuuenuri. C mourn 3pmun uuc~~nnozo peureHwr ma~ofr nodxd nenaemcn npednoumumenwuu. Eome mozo, OnmuManbnuIS c d nonyuaemcs npn.uuM nymeM w pewenu koilcmeennd 3adauu. TeopemuvecKaR ocnwa onucannozo Memoda - 3mo m e o m 9enxem. Cnedyem 3a~emumb, wno emuucnenue conpnxennd g5-u 9enxem 06nezwemcn, ecm d n a w nepeMennux 3 a h npe&apume,tbno.

1. Jntrodllctioo

The present paper continues the studies in the preceding paper [lo] on convex smoothing of univariate data sets by means of cubic C'-splines. Now, smoothing under the requirement of monotonicity shall be treated. For the sake of simplicity, in this case quadratic splines will be used.

Let the data set (x,,, u,,), (xl, ul), .. ., (x, u,,) on the grid A: xo < x1 < ... < x,, be given. Then for determining a smoothing spline s it is proposed to minimize the functional

s"(x)~ dx + pr - l(s(xI- 1) - ui- J2 + pi(s(xJ - uJ2}

subject to the constraint that

s is monotone (increasing) on [x,,, XJ . (1.2)

Here wf > 0, i = l(1) n, and p , > 0, i = 0(1) n, are given parameters; for recommendations how to choose these quantities see e.g. (31, [lo]. The choice of an appropriate value for the coeacient 1 > 0 is the result of a trade-off between curvature minimization and interpolation. In unconstrained smoothing the functional H is well-known, e.g., from DE BOOR'S book [3] while in convex smoothing H is used in [a], [q, [lo] and in further papers.

In [3l, [a], [q the admissible functions are taken from a Sobolev space, say W,Z[xo, xJ, and then it is shown that a unique minimizer s exists and that s is a cubic spline. Here, as in [lo], the feasible functions are assumed to be splines directly. In this way it is possible to treat also quadratic splines.

Substituting quadratic splines into (l.l), (1.2) the problem of monotone smoothing is discretized. The result is a program of the type

with convex functions Fr : R4 + R, closed convex sets & c R4, and given a E R'; see (2.6), (2.7), (2.8) for details. Here, problem (1.3) is called a partially separable program with an additional condition.

In the earlier papers [l], (41, [lo] also programs of this special structure (1.3) occur, except the now appearing additional condition mo = a. In these papers, for solving partially separable programs numerically it is proposed to dualize

300 ZAMM Z. angew. Math. Mech. 70 (1990) 8

them since there are dual programs which have the advantage to be unconstrained. Therefore, e.g, Newton's method can be used for the dual program. Moreover, if a solution of the dual program is computed the solution of the primal program can be determined directly by a return-formula.

The aim of the present paper is to show that the dualization technique introduced in [l], [4] also applies to the problem of monotone data smoothing with quadratic splines. For programs (1.3) with an additional condition the theoretical questions of interest are discussed. Further, the conjugate functions (3.9) needed for stating the dual program (3.12) as well as the return-formula (4.5) are explicitly computed. Also some numerical comments are given.

In the paper [q data smoothing is treated by putting I = 0 in the objective function (1.1) and, in turn, adding s(xi) E [L i , UJ, i = 0(1) n, to the constraints, where L i, Ui are prescribed constants. It is of interest to remark that for programs of this type the present dualization method is not completely applicable since now the programs for determining the conjugate functions (3.9) may not have unique maximizers.

2. First results on monotone smoothing by quadratic splines

Let us begin with some simple properties of quadratic splines. Usually such a spline s on the grid A is given by

for x i - S x 5 xi, where hi = xi - x i - ,, i = l(1) n. As immediately seen, s E C'[x,, xJ holds if and only if

Y, - Y i - 1 mi-' + mi = 2 , i = l(1)n - 1 , hi

is valid, and then one gets

y , = s(xi), mi = s'(x3, i = 0(1) n . In what follows, the yi and mi are used as parameters which are to be adapted to the monotonicity requirement.

Let 6 and E be given linear Co-splines on A with Si = 6(xi) and = &(xi). Then monotonicity of s is a special case of the constraint

S(x) 5 s'(x) 5 E ( X ) for x , 5 x 5 x , (2.4)

occurring for S = 0 and E = + a. Of course, (2.4) leads here to

S, 2 m, 5 E ~ , i = 0(1) n . (2.5)

When the quadratic spline (2.1) is substituted into (1.1) and (2.4), as straightforwardly shown a program (1.3) arises with

and

w, = u x , g , y ) E R 4 : X + JJ = 2 8 - , S i S Y 5 E, } I hi

is fixed in order to simplify the succeeding determination of the conjugate functions (3.9). For the same reason it is omitted to eliminate mo in F, and Wl by means of the additional condition m, = a.

The objective function (1.3) is in the case (2.6) quadratic, positive semidefinite, and moreover bounded below by zero. In addition the feasible domain in (1.3) is nonempty. Indeed, i f y , - , and mi-l are already chosen according to the constraints then m, can be taken from [ S , , E ~ ] and y , such that equation (2.2) is satisfied. Thus, in view of a result on semidefinite quadratic programs, see e.g. [2], appendix 2, program (1.3) specified by (2.6), (2.7), (2.8) is solvable. Moreover, using the fact that the quadratic form of the Hessian taken at the difference of two solution vectors vanishes, it is straightforwardly shown that the minimizer is unique. Hence, one gets

Theorem 1: Theproblem (l.l), (2.4) of extendedmonotone data smoothing is uniquely solvable in the space of quadratic C'-splines.

!~HMIDT. J. W.: Monotone Data Smoothing by Quadratic Splines 301

3. Dualizotion of partidy separable programs with additional conditions

In order to transform the constrained programming problem (1.3) into an unconstrained one, Fenchel's duality theory and extensions of it due to ROCKAFELLAR [9] and STOW [12] can be used. The dualization technique for partially separable programs which is developed in the papers [l] and [4] is now, on the basis of Fenchel's theory, somewhat generalized such that programs with additional conditions are also covered.

Let F, G : R"' -+ R u { + 00) be proper convex functionals. Then, in Fenchel's theory, to theprimdconvexprogram

P: inf{F(u) + G(u):u ER"'} (3.1)

D:SUP {-F*(u*) - G*(-U*):U*ER~} (3.2)

F*(u*) = SUP {u~u* - F(u): u E R"} , (3.3)

belongs the dual concave program

where the conjugate function F* is defined by

and analogously G*. Next, following the line of paper [4] program (1.3) is shown to be a special case of P, and the corresponding program

D is stated as well as the essential return-formula (4.5). Introducing additional variables Yl, M1, ..., Ke1, Mne1 program (1.3) is equivalently reformulated as a separable one,

i Fi(Yi- 1, mi- 1, Y;, MI) -+ Min! i = 1

s.t.(yi-l,ml-l, Y;, Mi)€ W, for i = 1(1)n, yl = Y;, mi = MI for i = l(1)n - 1 , m, = a ;

here yn = Y, m,, = M n is only a convenient change of notation. Further, set

u = (yo,mo, Y1,Ml,yl,ml,..., K-1,Mn-1yyn-1ymn-1, Y m M J ~ R b and

Then problem (3.4) and therefore likewise problem (1.3) becomes a program P if F and G are chosen according to

and for L I E W

G(u) = (" +00 otherwise

(3.4)

(3.7)

with W = {u:yl = Yr,ml = Mt for i = l(1)n - 1,mo = a } .

of the separability of F it follows immediately with For deriving the corresponding dual program D the conjugate functions F* and G* are to be determined. In view

u* = (~o',mo', Cy M?,y?,m?, ..., ~ - l y ~ t - l y ~ $ - l ~ ~ $ - l , T 9 M 3 ~ R h that

n

i = 1 F*(u*) = Hf(y:'l, m:-l, Y:, M:)

holds true if the Fenchel conjugate H: to Fi and VC: is defined by

H:(e,5,aYrl)=sup{ef+ b + ag+ tly-FiU;x,g,y):Cf,x,g,y)EW,}. (3.9)

Notice that in contrast to the original program (1.3), the programs for computing the conjugates H: are only Cdimensional, and moreover in the present problems they can be solved explicitly.

Further because of

302 ZAMM ' Z. angew. Math. Mech. 70 (1990) 8

for u E W one gets

G*(u*) = SUP {u~u*:u E W} =

(3.10) am: for y,* = 0, Yf + y: = 0, Mf + mf = 0 for i = l(1) n - 1, Y t = 0, MZ = 0 + 00 otherwise.

Hence the dual program D is obtained to be

-

s.t.yg = 0,

H:(Y?-~ , mr-l, I.;*, M:) + am; -+ Max!

+ y: = 0 , M f + mf = 0 for i = l(1)n - 1, yll = O,M,* = 0. i = 1

After eliminating the constraints one gets Proposi t ion 2: A program which is dual to the programming problem (1.3) reads

n -

with y,* = 0, y,* = O,m,* = 0 ,

H ? ( Y ? - ~ , m:-l, -y?, -m?) + urn,* -+ Max! i = 1

(3.11)

(3.12)

where the conjugate functions H:, . . . , H,* are given by (3.9). Remark that for finite H? program (3.12) is unconstrained. In order to derive duality statements for the pair of programs (1.3) and (3.12) the following strong duality theorem

is cited from [12], part 5.3.

Theorem 3: Let F and G be closed proper convex functionals, and assume that vectors w, z E dom F n dom G exist such that F is w-stable and G is z-stable. Iftheprimalprogram P has afinite optimal value then the dualprogram D is solvable and

(3.13)

The assumptions of this theorem are shown to be valid in the present problem of monotone data smoothing. Now, the present, F and G are proper convex and closed, and in view of Theorem 1 the optimal value of program P is finite. Further, for a vector ( y o , m,, ..., y,, m,) satisfying (2.2), (2.5)

inf{F(u) + G ( u ) : u ~ l R ' " } = max(-F*(u*) - G * ( - u * ) : u * ~ l R * ) .

z = ( Y O , m ~ , Y I , mi, Y I , mi, ..., Y n - 1 , m,-1, y,- 1 9 m,-,, y,, m,) E dom F n dom G holds true. Using stability properties obtainable from [12] F and G are seen to be z-stable: The functions Fi are z-stable since z is an interior point of dom Fi, and the indicator functions of the sets & and Ware z-stable since these sets are described by affine linear constraints. Thus, Theorem 3 applies to the above problem of monotone smoothing.

4. The return-formula

The essential return-formula (4.5) is a consequence of

if and only if Theorem 4: Under the assumptions of Theorem 3, vectors u and u* are optimal for the programs P and D, respectively,

u E aF*(u*) n aG*(-u*) ( 4 4

holds true. Here, as usual, a denotes the subdifferential. A proof of this theorem can be found e.g. in the book [9]. Now, following the line of paper [4] the return-formula is verified for programs (1.3) having an additional condition.

To this end, the programs (3.9) for computing the Fenchel conjugates Hi*(@, 5, u, q) are assumed to have unique maximizers

VXe, t, 6, v), R i k , t, g, v), E i k t, ~9 Yi(e, t, 0, rt)) for all (@, t, u, q) E lR4, i = l(1) n. In what follows this property is abbreviated by (Fus).

program (3.9), the differentiability of H? follows, and Since a vector U;, xi, g, y i ) belongs to the subgradient a H f ( e , 5,u, q) if and only if this vector is a maximizer of

SCHMIDT, J. W.: Monotone Data Smoothing by Quadratic Splines 303

Now, let u* be optimal for the dual program (3.1 l), and let the optimal value of (3.1 1) be finite. Then, G*( -u*) = -urn: follows, and using the Lagrangian to (3.11), namely

the Kuhn-Tucker conditions yield

Next define the vector u by

-uTu* = -urn,* = G*(-u*) + G(u) .

This again implies u ~aG*( -u*) ; see e.g. [9]. Of course, also # E M * ( # * ) is valid. Therefore, Theorem 4 ensures the optimality of the introduced vector u, and it follows

Proposi t ion 5 : Let assumption (Fus) be valid, and let (yo*, m& ..., y:, m,*) be a solution of the dualprogram (3.12). Then the vector ( yo , m,, ..., y,, mn) with

5. Dualization of the problem of monotone smoothing

The dual program (3.12) as well as the return-formula (4.5) are stated when the Fenchel conjugates Hf defined by (3.9) are known. In the present case these functions can be explicitly computed. It is technically of advantage that after dropping the condition m, E [do, go] all sets @ are of the same structure, and the number of constraints describing them is as small as possible.

For Fi and 4 given by (2.6) and (2.7), respectively, the 4-dimensional program (3.9) reads

e f + 5 x + c T g + q y - - - 4wi'("if -- x)' - p i - l u - ui-$ - p i ( g - ui)' -, Max! hi

s.t.x + y = 2=f, 6i 5 y 5 E i . hi

For solving this quadratic program only some hints are given. With the abbreviations

u = 4wil/h, h = hi, p = pi-1, 4 =Pi, u = Ui-1 u = ~ i , 6 = 6i, E = ~ i , (5.2)

to (5.1) belongs the Lagrangian

@ U x , g , y , A , p , v ) = -d- 5x - ag - q y + a (" - - x y + p c f - uI2 + 4 ( g - v)2 + A(6 - y)

+ p ( y - & ) + V x + y - 2 - if), ( and the Kuhn-Tucker conditions, now necessary and sufficient, are

@x = = Qif = @* = Qi, = 0, @A g 0,A 2 O,A@Z. = 0, Qp 6 0,p O,@, = 0 (5.3)

304 ZAMM . Z. angew. Math. Mech. 70 (1990) 8

By means of the equalities in the first row of (5.3) one obtains easily

1 5 + p l + i l - p t - q - - i l + p 7 + '-' (" @) (; q) 2h2

x = - + - _ - _ + - + - 2a

2q 2qh '-' (" @) (; ,> 2h2 2a

(5.4)

e 5 + 9 + l - C L 2P 2Ph h 2 h q P d t + q + n - p

h 2 h q P

f = u + - -

g = v + - + 1 5 ' + q + n - p - 5 - q - n + / . f y = - + - - - - + - + -

9

In view of the complementarity conditions in (5.3) four cases are possible. Case 1: Let il = 0, p = 0. Then QzA 5 0, QzP 5 0 gives 6 5 y 5 8, i.e. now only the vectors (e, 5 , 6 , q) E DIi are

considered where

Thus, with regard to (4.2), using the maximizer c f ; x, g, y) it follows

e 5 + ? a,H:(e, 5, "7 ?) = f = u + - - -, 2P 2Ph

fJ 5 + r 2q 2qh

a3HT(@, 5, 0, ?) = g = 2, + - + -,

a,H:(e,tJ,a,q) =

and hence

HT(e7 5 7 6, V ) = HTi(e7 5 7 "7 V ) =

(5.5)

+- 4a

(5.7)

for (e, 5, " 9 ?) E Dli.

Case 2 : Let il = 0, Qz,, = 0. The latter equality gives y = 8 from which p is computed,

5 ( p - q ) - - + - + - =-+- - - - + - + - &

( 2 k 2 ( ; :) l) 'hu l h ( i i) (: : ) 2 i 2 2Q '

The condition p 2 0 leads to the domain

2a

and since (5.4) the components of the maximizer are

, y = E . " 5 P - ? , g = v + - + - - - , x = & + - + - 5 P - ? e 5 C L - ? f = u + - - -+ - 2p 2ph 2ph a a 2q 2qh 2qh

Thus, property (4.2) leads to

1 alH:(@,5,",q) = f =

(5.9)

azH:(@, 5, b, q) = x =

a3H:(e7e,a,rl) = g =

(5.10) v

SCHMIDT, J. W.: Monotone Data Smoothing by Quadratic Splines 305

where the coefficient of p - q in (5.8) is abbreviated by

(5.11)

Case 3: Let f i = 0, @ A = 0. This case is analogous to Case 2. The domain is obtained to be

while in formulas (5.10) and (5.12) now only the quantity E is to be replaced by 6, e.g.

HT(e, '3 6, V ) = H5i(e, 5, ~3 V )

(5.13)

(5.14)

for (e, 5,6, q) E D3+

Case 4: @ A = 0, @,, = 0 implies 6 = E. Thus this case is covered e.g. by Case 1. Hence the following result essential in the present approach to monotone smoothing is proved.

Proposi t ion 6: The Fenchel conjugates (3.9) belonging to Fi and @ given by (2.6) and (2.7), respectively, read

W ( e , 5 , 6 , V ) = Hj*i(e, 5 , 6 , q) for (e, t, b, V ) E Dji (5.15)

for j E (1,2,3} and i = l (1 ) n where the functions H$ are obtained from (5.7), (5.12) and (5.14) while the pieces D, of the domains are defined by ( 5 . 9 , (5.9) and (5.13), respectively. In addition, the abbreviations (5.2) and (5.11) are to be taken into account.

Notice that for applying the return-formula (4.5) only the derivatives of H:, ..., H: are necessary. This is also the case when the dual program (3.12) is solved e.g. by Newton's method. Then, of course, one can use directly the easier obtainable formulas (5.6), (5.10), and again (5.10) with E replaced by 6.

6. Convex smoothing by quadratic splines

Let 6 and E be piecewise constant functions on the grid A with 6 ( x ) = 6, and ei = E(X) for xi-l 5 x 5 xi, i = l (1 ) n. If quadratic splines (2.1) are used the condition

26(x) 6 ~ ' ' ( x ) 5 ~ E ( x ) for xiWl 6 x 5 x i , i = l ( l ) n , (6.1)

including convexity for 6 = 0 and E = + co is discretized by

6,h. Yi - Yi-1 - 1 1 - m i - l 5 eihi for i = l ( 1 ) n

hi

Thus, the smoothing problem (l.l), (6.1) takes the form

Fi(yt- l , mi-i, ye mi) -, Min! i = 1

s.t. mi-l,yi,mi)E @ for i = l ( l ) n ,

306

where the functions Fi are given by (2.6) while the sets 4 now are

ZAMM . Z. angew. Math. Mech. 70 (1990) 8

U ; x , g , y ) : x + y = 2 e , 6 , h i I g - - f - x 6 Eihi hi hi

(6.4)

The feasible domain is easily seen to be nonempty, and the present programming problem of extended convex smoothing is uniquely solvable.

To program (6.3) without additional conditions the dual program n

- HTCyF-,, m:-l, -y:, -m:) + Max! i = l

with y$ = 0, mt = 0, y.* = 0, m: = 0,

belongs with conjugates HT according to (3.9); see [4]. As it is said in the report [ll] the latter functions are equal to

ui - Ui-1 HTk, 5 , a, rl ) = ui- le + uia + hi

with

[ eihi(q - 5 ) - 4wi1.$hi for tj - 5 >= 8 ~ ~ 1 . 5 ~ ;

see in addition [8]. Finally, notice that the essential return-formula (4.5) is now also valid.

7. Numerical comments

The general strategy for treating the problem (1.3), (2.6), (2.7) of monotone smoothing numerically is to compute at first a solution (yo*, m$, ..., y:, m,*) of the unconstrained dual program (3.12), (5.15) and then to determine the solution (yo, mo, ..., yn, m,) of (1.3), (2.6), (2.7) by means of the return-formula (4.5).

Since program (3.12) is concave the equalities

azH:(O, m t , -y:, -m:) - a = 0, a,Ht(y:, m?, - y t , - m f ) - a3H:(0, mX, -y:, -m:) = 0, %Ht(y: , m:, -yf, - m t ) - a4H:(0, mX, -Y:, -my) = 0 , alW+l(y:,mi*, -Y:+~, -mi*,l) - 83Hit(y?-l,mi*-1, -y:, -m:) = 0, a,H:+,(y:,m:, -y:+,, -rn:+'+,) - a4H:(y:-l,mi*_2, -y:, -m:) = 0, i = 2(1)n - 2 , alHn*(~n*-l,rnn*-l,O,O) - a3H:-l(~n*-1,mn*-,, - y L , -m,*-,) = 0, ~ZHn*(yn*-l,mXl,O,O) - a4H:-l(y:-2,m:-2, - Y ; - ~ , -m&J = 0

are sufficient and necessary for a maximizer. The Jacobian of the piecewise linear system (7.1) is block-tridiagonal

* I * * I

/ * * I * * I * * /

SCHMIDT, J. W.: Monotone Data Smoothing by Quadratic Splines 307

and this special structure should be taken into account in order to solve system (7.1) effectively. Thus, e.g., the Newton method can be used. Further, since the standard Newton method may be sensitive to the choice of the starting vector, gradient or damped Newton steps should be added in cases when convergence fails to appear. As tests have shown this sensitivity occurs especially for E close to 6.

References

1 BURMEBTER, W.; HESS, W.; SCHMIDT, J. W.: Convex spline interpolants with minimal curvature. Computing 35 (1985), 219-229. 2 COLLATZ, L. ; WETTERLING, W. : Optimierungsaufgaben. Berlin - Heidelberg - New York, Springer-Verlag 1966. 3 DE BOOR, C. : A practical guide to splines. Berlin - Heidelberg- New York, Springer-Verlag 1978. 4 DLETZE, S.; SCHMIDT, J. W.: Determination of shape preserving spline interpolants with minimal curvature via dual programs. J.

5 D o n , S. L.; MCALLISIER, D. F.: Algorithms for computing shape preserving spline approximations to data. Numer. Math. 46 (1985),

6 ELFVING, T.; ANDERSSON, L.-E. : An algorithm for computing constrained smoothing spline functions. Numer. Math. 52 (1988), 583 - 595. 7 IRVINE, L. D.; MARTIN, S. P.; SMITH, P. W.: Constrained interpolation and smoothing. Constr. Approximation 2 (1986), 129- 151. 8 LEHRACK, I. : Konvex-konkaves Ausgleichen mit quadratischen und kubischen Splines. Diplomarbeit Techn. Univ. Dresden 1988. 9 ROCKAFELLAR, R. T.: Convex analysis. Princeton, N.J., Princeton Univ. Press 1970. 10 SCHMIDT, J. W.: An unconstrained dual program for computing convex C'-spline approximants. Computing 39 (1987), 133- 140. 11 SCHMIDT, J. W.: Convex smoothing by splines and dualization. Proceed. Int. Conf. Numer. Meth. Applic., Sofia 1988, Publ. House

12 STOER, J.; WITZGALL, C. : Convexity and optimization in finite dimensions. Berlin - Heidelberg - New York, Springer-Verlag 1970. 13 HERTZSCHUCH, A. : Monotone Datenglattung mit quadratischen Splines unter Verwendung eines vergroberten Spline-Gitters.

Approx. Theory 52 (1988), 43 - 57.

159- 174

Bulgar. Acad. Sci. 1989, pp. 425-436.

Diplomarbeit, Techn. Univ. Dresden 1990.

Note added in p roof The described dualization approach for constructing monotone spline approximants also applies if the spline grid is chosen to be coarser than the grid introduced by the data set. Let the given data be

(xi- 1, ui- A s (xtlt uilh - - * t (xikt9 UiliJr (xi, 4 3 i = 1(1) s

with xi-l < xil < ... < xi4 < xi, i = l(1) n, and define the spline grid only by the nodes xo < x1 < ... < x,. Further, modify the objective function (1.1) by adding the term

k1

j = 1 c Pij(S(Xij) - UijY 3

with weights pi, 2 0. Then, using quadratic splines again a partially separable program (1.3) arises, and the corresponding Fenchel conjugates (3.9) can be explicitly determined; for details see [13]. In this diploma thesis also results of numerical tests in applying the dualization procedure are given.

Received November 11, 1988

Address: Prof. Dr. JOCHEN W. SCHMIDT, Technical University Dresden, Department of Mathematics, Mommsenstr. 13, Dresden DDR-8027, German Democratic Republic