Least Squares Orthogonal Polynomials
- PDF / 10,208,759 Bytes
- 110 Pages / 594 x 828 pts Page_size
- 32 Downloads / 243 Views
(p, q E z v ) , (pEZY),
where p V q = (max(p(v),q(v))[v E V) E Z V, p A q -- ( m i n p ( v ) , q ( v ) ) l v E V ) E Z V, and 1 is the vector in Z y with all components being equal to 1. A set D C Z y is said to be an L-convex set if its indicator function rid (defined by So(p) -- 0 if p E D, and - +c~ otherwise) is an L-convex function, i.e., if
i) D ~- 0; ii) p, q E D = ~ p V q , iii) p E D ~ p + I E D .
pAqED;and
A function f" Z y -+ Z U {+c~} with dom f ~ q) is called M-convex if it satisfies • M-EXC) For x, y E dom f and u E supp + ( x y), there exists v E s u p p - ( x - y) such that
:(z) + :(y) _>
+
÷f(yWxu-xv),
where, for any u E V, Xu is the characteristic vector of u (defined by X~(v) = 1 if v = u, and = 0 otherwise), and supp+(z)
{v E V" z(v) > 0}
(z E zY),
supp-(z)- {v e V. z(v) < 0}
(z e ZV).
-
-
A set B C Z y is said to be an M-convex set if its indicator function is an M-convex function, i.e., if B satisfies • B-EXC) For x, y E B and for u E s u p p + ( x y), there exists v E s u p p - ( x - y) such that x - Xu + Xv E B and y + Xu - Xv E B. This means that an M-convex set is the same as the set of integer points of the base polyhedron of an integral submodular system (see [8] for submodular systems). L-convexity and M-convexity are conjugate to each other under the integral Fenchel-Legendre transformation f ~ f ° defined by f" (p) - sup { (p, x) - f (x)" x E Z V }, p E Z V, where (p,x) - ~-~.v~vp(v)x(v). That is, for Lconvex function g and M-convex function f, it holds [15] that g" is M-convex, f" is L-convex, g"=g,
and f " = f .
L-convex functions and M-convex functions EXAMPLE 1 (Minimum
cost flow problem) L-
convexity and M-convexity are inherent in the integer minimum-cost flow problem, as pointed out in [12], [15]. Let G - (V, A) be a graph with vertex set V and arc set A, and let T C_ V be given. For ~" A --+ Z its boundary 0~" V --+ Z is defined by O (v)
: E
{~(a)" a C 5 + v } - E
{~(a)" a E 5-v}
(v e v ) , where 5+v and 5-v denote the sets of out-going and in-coming arcs incident to v, respectively. For ~" V -+ Z its coboundary 5~: A --+ Z is defined by
5~(a) - ~(0 +a) -~(O-a)
(a e
A),
where O+a and O-a mean the initial and terminal vertices of a, respectively: Denote the class of one-dimensional discrete convex functions by C1 - {~" Z -+ Z U {+c~}[ d o m ~ # 0, ~(t-1)+~(t+l)_>2~(t)
(tEZ)}.
For ~a E C1 (a C A), representing the arc-cost in terms of flow, the total cost function f: Z T --+ Z U { + ~ } defined by
S(x) --i~fE
~a(~(a))"
aEA
(x
O¢(v) - - z ( v ) e T), O (v) - 0 (veV\T)
z r)
is M-convex, provided that f > - c o (i.e., f does not take the value o f - c ~ ) . For ~a C C1 (a E A), representing the arc-cost in terms of tension, the total cost function g" Z T -+ Z U {+c~} defined by
dependence of the column vectors; namely, J C_ V belongs to B if and only if IJ[ - m and the column vectors with indices in J are linearly independent. Then f" z v __+ Z U { + ~ } defined by
f (x) -
- d e g sdetA[J]
( x - x j, J e B)
+c~
(otherwise)
is M-convex, wh
Data Loading...
