Page - 66 - in Proceedings - OAGM & ARW Joint Workshop 2016 on "Computer Vision and Robotics“

A B C D Bold lines: edges of the triangles Dashed lines: minimal heights Large circles: limitation induced by ABC Small circles: limitation induced by BCD T1 T2 hT1 hT2 Figure 1: Triangle T1 = (A,B,C) with minimal height hT1 onC and triangle T2 = (C,D,B) with minimal heighthT2 onD. Limiting the movement of all nodes in a triangle byα times the minimum of the heights induces circles foreachnode, ofwhich thesmallestone is chosenasconstraints. In order to apply the primal-dual algorithm, Problem (2) is reformulated as a saddle-point problem according to min u∈Ω F(∆u) ⇐⇒ min u∈U F(∆u)+IΩ(u) ⇐⇒ min u∈U sup w∈U 〈w,∆u〉−F∗(w)+IΩ(u), (5) whereF(u) = 1 2 ‖u‖22, the indicator function of Ω, i.e., IΩ(u) = 0 foru∈Ω and∞otherwise, and F∗ is theconvex conjugateofF, definedasF∗(w) := supu∈U〈w,u〉−F(u). Explicitly,weget F∗(w) = sup u∈U 〈w,u〉− 1 2 ‖u‖22 = 〈w,w〉− 1 2 ‖w‖22 = 1 2 ‖w‖22, (6) where the second equality is due tou=w being the unique critical point ofu 7→ 〈w,u〉− 1 2 ‖u‖22, which can be confirmed by differentiation, and hence, u= w being the unique global maximiser. Thus, (2) is reformulatedas the followingsaddlepointproblem min u∈U max w∈U L(u,w), whereL(u,w) = 〈w,∆u〉− 1 2 ‖w‖22 +IΩ(u). (7) The following proposition shows that by solving (7), we indeed obtain a solution of the original problem(2). Proposition. The saddle point problem (7) with feasible set Ω defined as in (4) admits at least one solution and for any saddle point (u+,w+) of (7), u+ is a solution of the original minimisation problem (2). Proof. Due to [7, VI Prop 2.4, p. 176], it is sufficient to show that forL:U×U→Rdefined as in (7), foru∈U fixed,w 7→L(u,w) is concaveandupper semi-continuousonU, and forw∈U fixed, u 7→L(u,w) is convexand lowersemi-continuousonU. Further,weneed toshowthatu 7→L(u,w) is coercive for fixedw and that lim ‖w‖→∞ w∈U inf u∈U L(u,w) =−∞. (8) Theconvexity/concavityandl.s.c./u.s.c. assumptionsaresatisfied, inparticularduetoΩbeingconvex andclosed, andu 7→L(u,w) is coercivedue toΩbeingbounded. Further, forfixedu∈Ω, lim ‖w‖→∞ 〈w,∆u〉−‖w‖22≤ lim‖w‖→∞‖w‖‖∆u‖− 1 2 ‖w‖22 = lim‖w‖→∞‖w‖ ( ‖∆u‖− 1 2 ‖w‖ ) =−∞ andhence, (8)holds,yielding theexistenceofasaddlepoint(u+,w+). Due to[7, IIIProp3.1,p. 57], the optimalityofu+ for (2) is adirect consequenceof (5). 4 66