A new iterative algorithm for mean curvature-based variational image denoising

The total variation semi-norm based model by Rudin-Osher-Fatemi (in Physica D 60, 259–268, 1992) has been widely used for image denoising due to its ability to preserve sharp edges. One drawback of this model is the so-called staircasing effect that is seen in restoration of smooth images. Recently several models have been proposed to overcome the problem. The mean curvature-based model by Zhu and Chan (in SIAM J. Imaging Sci. 5(1), 1–32, 2012) is one such model which is known to be effective for restoring both smooth and nonsmooth images. It is, however, extremely challenging to solve efficiently, and the existing methods are slow or become efficient only with strong assumptions on the formulation; the latter includes Brito-Chen (SIAM J. Imaging Sci. 3(3), 363–389, 2010) and Tai et al. (SIAM J. Imaging Sci. 4(1), 313–344, 2011). Here we propose a new and general numerical algorithm for solving the mean curvature model which is based on an augmented Lagrangian formulation with a special linearised fixed point iteration and a nonlinear multigrid method. The algorithm improves on Brito-Chen (SIAM J. Imaging Sci. 3(3), 363–389, 2010) and Tai et al. (SIAM J. Imaging Sci. 4(1), 313–344, 2011). Although the idea of an augmented Lagrange method has been used in other contexts, both the treatment of the boundary conditions and the subsequent algorithms require careful analysis as standard approaches do not work well. After constructing two fixed point methods, we analyze their smoothing properties and use them for developing a converging multigrid method. Finally numerical experiments are conducted to illustrate the advantages by comparing with other related algorithms and to test the effectiveness of the proposed algorithms.     

A predictor-corrector smoothing Newton method for symmetric cone complementarity problems

In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective.     

On the Second-order Directional Derivatives of Singular Values of Matrices and Symmetric Matrix-valued Functions

The (parabolic) second-order directional derivatives of singular values of matrices and symmetric matrix-valued functions induced by real-valued functions play important roles in studying second-order optimality conditions for different types of matrix cone optimization problems. We propose a direct way to derive the formula for the second-order directional derivative of any eigenvalue of a symmetric matrix in Torki (Nonlinear Anal 46:1133–1150 2001), from which a formula for the second-order directional derivative of any singular value of a matrix is established. We demonstrate a formula for the second-order directional derivative of the symmetric matrix-valued function. As applications, the second-order derivative for the projection operator over the SDP cone is derived and used to get the second-order tangent set of the SDP cone in Bonnans and Shapiro (2000), and the tangent cone and the second-order tangent set of the epigraph of the nuclear norm are given as well.     

An entropy-like proximal algorithm and the exponential multiplier method for convex symmetric cone programming

We introduce an entropy-like proximal algorithm for the problem of minimizing a closed proper convex function subject to symmetric cone constraints. The algorithm is based on a distance-like function that is an extension of the Kullback-Leiber relative entropy to the setting of symmetric cones. Like the proximal algorithms for convex programming with nonnegative orthant cone constraints, we show that, under some mild assumptions, the sequence generated by the proposed algorithm is bounded and every accumulation point is a solution of the considered problem. In addition, we also present a dual application of the proposed algorithm to the symmetric cone linear program, leading to a multiplier method which is shown to possess similar properties as the exponential multiplier method (Tseng and Bertsekas in Math. Program. 60:1–19, 1993) holds.     

A nonmonotone approximate sequence algorithm for unconstrained nonlinear optimization

A new nonmonotone algorithm is proposed and analyzed for unconstrained nonlinear optimization. The nonmonotone techniques applied in this algorithm are based on the estimate sequence proposed by Nesterov (Introductory Lectures on Convex Optimization: A Basic Course, 2004) for convex optimization. Under proper assumptions, global convergence of this algorithm is established for minimizing general nonlinear objective function with Lipschitz continuous derivatives. For convex objective function, this algorithm maintains the optimal convergence rate of convex optimization. In numerical experiments, this algorithm is specified by employing safe-guarded nonlinear conjugate gradient search directions. Numerical results show the nonmonotone algorithm performs significantly better than the corresponding monotone algorithm for solving the unconstrained optimization problems in the CUTEr (Bongartz et al. in ACM Trans. Math. Softw. 21:123–160, 1995) library.     

A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations

In this paper, we consider a class of mathematical programs governed by second-order cone constrained parameterized generalized equations. We reformulate the necessary optimality conditions as a system of nonsmooth equations under linear independence constraint qualification and the strict complementarity condition. A set of second order sufficient conditions is proposed, which is proved to be sufficient for the second order growth of the stationary point. The smoothing Newton method in [40] is employed to solve the system of nonsmooth equations whose strongly BD-regularity at a solution point is demonstrated under the second order sufficient conditions. Several illustrative examples are provided and discussed.     

Linearly Implicit Approximations of Diffusive Relaxation Systems

Diffusive relaxation systems provide a general framework to approximate nonlinear diffusion problems, also in the degenerate case (Aregba-Driollet et al. in Math. Comput. 73(245):63–94, 2004; Boscarino et al. in Implicit-explicit Runge-Kutta schemes for hyperbolic systems and kinetic equations in the diffusion limit, 2011; Cavalli et al. in SIAM J. Sci. Comput. 34:A137–A160, 2012; SIAM J. Numer. Anal. 45(5):2098–2119, 2007; Naldi and Pareschi in SIAM J. Numer. Anal. 37:1246–1270, 2000; Naldi et al. in Surveys Math. Indust. 10(4):315–343, 2002). Their discretization is usually obtained by explicit schemes in time coupled with a suitable method in space, which inherits the standard stability parabolic constraint. In this paper we combine the effectiveness of the relaxation systems with the computational efficiency and robustness of the implicit approximations, avoiding the need to resolve nonlinear problems and avoiding stability constraints on time step. In particular we consider an implicit scheme for the whole relaxation system except for the nonlinear source term, which is treated though a suitable linearization technique. We give some theoretical stability results in a particular case of linearization and we provide insight on the general case. Several numerical simulations confirm the theoretical results and give evidence of the stability and convergence also in the case of nonlinear degenerate diffusion.     

An augmented Lagrangian approach for sparse principal component analysis

Principal component analysis (PCA) is a widely used technique for data analysis and dimension reduction with numerous applications in science and engineering. However, the standard PCA suffers from the fact that the principal components (PCs) are usually linear combinations of all the original variables, and it is thus often difficult to interpret the PCs. To alleviate this drawback, various sparse PCA approaches were proposed in the literature (Cadima and Jolliffe in J Appl Stat 22:203–214, 1995; d’Aspremont et?al. in J Mach Learn Res 9:1269–1294, 2008; d’Aspremont et?al. SIAM Rev 49:434–448, 2007; Jolliffe in J Appl Stat 22:29–35, 1995; Journée et?al. in J Mach Learn Res 11:517–553, 2010; Jolliffe et?al. in J Comput Graph Stat 12:531–547, 2003; Moghaddam et?al. in Advances in neural information processing systems 18:915–922, MIT Press, Cambridge, 2006; Shen and Huang in J Multivar Anal 99(6):1015–1034, 2008; Zou et?al. in J Comput Graph Stat 15(2):265–286, 2006). Despite success in achieving sparsity, some important properties enjoyed by the standard PCA are lost in these methods such as uncorrelation of PCs and orthogonality of loading vectors. Also, the total explained variance that they attempt to maximize can be too optimistic. In this paper we propose a new formulation for sparse PCA, aiming at finding sparse and nearly uncorrelated PCs with orthogonal loading vectors while explaining as much of the total variance as possible. We also develop a novel augmented Lagrangian method for solving a class of nonsmooth constrained optimization problems, which is well suited for our formulation of sparse PCA. We show that it converges to a feasible point, and moreover under some regularity assumptions, it converges to a stationary point. Additionally, we propose two nonmonotone gradient methods for solving the augmented Lagrangian subproblems, and establish their global and local convergence. Finally, we compare our sparse PCA approach with several existing methods on synthetic (Zou et?al. in J Comput Graph Stat 15(2):265–286, 2006), Pitprops (Jeffers in Appl Stat 16:225–236, 1967), and gene expression data (Chin et?al in Cancer Cell 10:529C–541C, 2006), respectively. The computational results demonstrate that the sparse PCs produced by our approach substantially outperform those by other methods in terms of total explained variance, correlation of PCs, and orthogonality of loading vectors. Moreover, the experiments on random data show that our method is capable of solving large-scale problems within a reasonable amount of time.     

Speeding up branch and bound algorithms for solving the maximum clique problem

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.     

Convergence of a non-interior continuation algorithm for the monotone SCCP

It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.     

Strong convergence properties of a modified nonmonotone smoothing algorithm for the SCCP

The smoothing algorithms have been successfully applied to solve the symmetric cone complementarity problem (denoted by SCCP), which in general have the global and local superlinear/quadratic convergence if the solution set of the SCCP is nonempty and bounded. Huang, Hu and Han [Science in China Series A: Mathematics, 52: 833–848, 2009] presented a nonmonotone smoothing algorithm for solving the SCCP, whose global convergence is established by just requiring that the solution set of the SCCP is nonempty. In this paper, we propose a new nonmonotone smoothing algorithm for solving the SCCP by modifying the version of Huang-Hu-Han’s algorithm. We prove that the modified nonmonotone smoothing algorithm not only is globally convergent but also has local superlinear/quadratical convergence if the solution set of the SCCP is nonempty. This convergence result is stronger than those obtained by most smoothing-type algorithms. Finally, some numerical results are reported.     

Improved smoothing Newton methods for symmetric cone complementarity problems

There recently has been much interest in smoothing Newton method for solving nonlinear complementarity problems. We extend such method to symmetric cone complementarity problems (SCCP). In this paper, we first investigate a one-parametric class of smoothing functions in the context of symmetric cones, which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Then we propose a smoothing Newton method for the SCCP based on the one-parametric class of smoothing functions. For the proposed method, besides the classical step length, we provide a new step length and the global convergence is obtained. Finally, preliminary numerical results are reported, which show the effectiveness of the two step lengthes in the algorithm and provide efficient domains of the parameter for the complementarity problems.     

A note on quadratic convergence of a smoothing Newton algorithm for the LCP

The linear complementarity problem (LCP) is to find ${(x,s)\in\mathfrak{R}^n\times\mathfrak{R}^n}$ such that (x, s) ≥ 0, s = Mx + q, x ^T s = 0 with ${M\in\mathfrak{R}^{n\times n}}$ and ${q\in\mathfrak{R}^n}$ . The smoothing Newton algorithm is one of the most efficient methods for solving the LCP. To the best of our knowledge, the best local convergence results of the smoothing Newton algorithm for the LCP up to now were obtained by Huang et al. (Math Program 99:423–441, 2004). In this note, by using a revised Chen–Harker–Kanzow–Smale smoothing function, we propose a variation of Huang–Qi–Sun’s algorithm and show that the algorithm possesses better local convergence properties than those given in Huang et al. (Math Program 99:423–441, 2004).     

New error bounds for the linear complementarity problem with an SB-matrix

Error bounds for SB-matrices linear complementarity problems are given in the paper (Dai et al., Numer Algorithms 61:121–139, 2012). In this paper, new error bounds for the linear complementarity problem when the matrix involved is an SB-matrix are presented and some sufficient conditions that new bounds are sharper than those of the previous paper under certain assumptions are provided. New perturbation bounds of SB-matrices linear complementarity problems are also considered.     

Further variations on the theme of FC-groups

Groups that are FC, or more generally satisfy any of the weakenings of the FC-condition considered in de Giovanni (Serdica Math. J. 28:241?C254, 2002) and Robinson et?al. (J. Algebra 326:218?C226, 2011), have local systems consisting of normal finite-by-nilpotent subgroups. Apart from generalizing results from de Giovanni (Serdica Math. J. 28:241?C254, 2002) and Robinson et al. (J. Algebra 326:218?C226, 2011) to the more general context of locally (normal and finite-by-nilpotent) groups, we partially settle an open problem raised in Robinson et?al. (J. Algebra 326:218?C226, 2011) concerning the isomorphism of maximal p-subgroups, but in this more general setting of locally (normal and finite-by-nilpotent) groups.     

A filter trust-region algorithm for unconstrained optimization with strong global convergence properties

We present a new filter trust-region approach for solving unconstrained nonlinear optimization problems making use of the filter technique introduced by Fletcher and Leyffer to generate non-monotone iterations. We also use the concept of a multidimensional filter used by Gould et?al. (SIAM J. Optim. 15(1):17?C38, 2004) and introduce a new filter criterion showing good properties. Moreover, we introduce a new technique for reducing the size of the filter. For the algorithm, we present two different convergence analyses. First, we show that at least one of the limit points of the sequence of the iterates is first-order critical. Second, we prove the stronger property that all the limit points are first-order critical for a modified version of our algorithm. We also show that, under suitable conditions, all the limit points are second-order critical. Finally, we compare our algorithm with a natural trust-region algorithm and the filter trust-region algorithm of Gould et al. on the CUTEr unconstrained test problems Gould et?al. in ACM Trans. Math. Softw. 29(4):373?C394, 2003. Numerical results demonstrate the efficiency and robustness of our proposed algorithms.     

Homogeneous Self-dual Algorithms for Stochastic Second-Order Cone Programming

Jin et al. (in J. Optim. Theory Appl. 155:1073–1083, 2012) proposed homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. In this paper, we utilize their work to derive homogeneous self-dual algorithms for stochastic second-order cone programs with finite event space. We also show how the structure in the stochastic second-order cone programming problems may be exploited so that the algorithms developed for these problems have less complexity than the algorithms developed for stochastic semidefinite programs mentioned above.     

Optimal Transport, Convection, Magnetic Relaxation and Generalized Boussinesq Equations

We establish a connection between optimal transport theory (see Villani in Topics in optimal transportation. Graduate studies in mathematics, vol. 58, AMS, Providence, 2003, for instance) and classical convection theory for geophysical flows (Pedlosky, in Geophysical fluid dynamics, Springer, New York, 1979). Our starting point is the model designed few years ago by Angenent, Haker, and Tannenbaum (SIAM J. Math. Anal. 35:61–97, 2003) to solve some optimal transport problems. This model can be seen as a generalization of the Darcy–Boussinesq equations, which is a degenerate version of the Navier–Stokes–Boussinesq (NSB) equations. In a unified framework, we relate different variants of the NSB equations (in particular what we call the generalized hydrostatic-Boussinesq equations) to various models involving optimal transport (and the related Monge–Ampère equation, Brenier in Commun. Pure Appl. Math. 64:375–417, 1991; Caffarelli in Commun. Pure Appl. Math. 45:1141–1151, 1992). This includes the 2D semi-geostrophic equations (Hoskins in Annual review of fluid mechanics, vol. 14, pp. 131–151, Palo Alto, 1982; Cullen et al. in SIAM J. Appl. Math. 51:20–31, 1991, Arch. Ration. Mech. Anal. 185:341–363, 2007; Benamou and Brenier in SIAM J. Appl. Math. 58:1450–1461, 1998; Loeper in SIAM J. Math. Anal. 38:795–823, 2006) and some fully nonlinear versions of the so-called high-field limit of the Vlasov–Poisson system (Nieto et al. in Arch. Ration. Mech. Anal. 158:29–59, 2001) and of the Keller–Segel for Chemotaxis (Keller and Segel in J. Theor. Biol. 30:225–234, 1971; Jäger and Luckhaus in Trans. Am. Math. Soc. 329:819–824, 1992; Chalub et al. in Mon. Math. 142:123–141, 2004). Mathematically speaking, we establish some existence theorems for local smooth, global smooth or global weak solutions of the different models. We also justify that the inertia terms can be rigorously neglected under appropriate scaling assumptions in the generalized Navier–Stokes–Boussinesq equations. Finally, we show how a “stringy” generalization of the AHT model can be related to the magnetic relaxation model studied by Arnold and Moffatt to obtain stationary solutions of the Euler equations with prescribed topology (see Arnold and Khesin in Topological methods in hydrodynamics. Applied mathematical sciences, vol. 125, Springer, Berlin, 1998; Moffatt in J. Fluid Mech. 159:359–378, 1985, Topological aspects of the dynamics of fluids and plasmas. NATO adv. sci. inst. ser. E, appl. sci., vol. 218, Kluwer, Dordrecht, 1992; Schonbek in Theory of the Navier–Stokes equations, Ser. adv. math. appl. sci., vol. 47, pp. 179–184, World Sci., Singapore, 1998; Vladimirov et al. in J. Fluid Mech. 390:127–150, 1999; Nishiyama in Bull. Inst. Math. Acad. Sin. (N.S.) 2:139–154, 2007).     

Additive Results of the Drazin Inverse for Bounded Linear Operators

Given two bounded linear operators $P$ and $Q$ on a Banach space the formula for the Drazin inverse of $P+Q$ is given, under the assumptions $P^2 Q+PQ^2=0$ and $P^3 Q=PQ^3=0$ . In particular, some recent results arising in Drazin (Am Math Mon 65:506–514, 1958), Hartwig et al. (Linear Algebra Appl 322:207–217, 2001) and Castro-González et al. (J Math Anal Appl 350:207–215, 2009) are extended.     

Characterization of the Fermat curve as the most symmetric nonsingular algebraic plane curve

A projective nonsingular plane algebraic curve of degree \(d\ge 4\) is called maximally symmetric if it attains the maximum order of the automorphism groups for complex nonsingular plane algebraic curves of degree \(d\) . For \(d\le 7\) , all such curves are known. Up to projectivities, they are the Fermat curve for \(d=5,7\) ; see Kaneta et al. (RIMS Kokyuroku 1109:182–191, 1999) and Kaneta et al. (Geom. Dedic. 85:317–334, 2001), the Klein quartic for \(d=4\) , see Hartshorne (Algebraic Geometry. Springer, New York, 1977), and the Wiman sextic for \(d=6\) ; see Doi et al. (Osaka J. Math. 37:667–687, 2000). In this paper we work on projective plane curves defined over an algebraically closed field of characteristic zero, and we extend this result to every \(d\ge 8\) showing that the Fermat curve is the unique maximally symmetric nonsingular curve of degree \(d\) with \(d\ge 8\) , up to projectivity. For \(d=11,13,17,19\) , this characterization of the Fermat curve has already been obtained; see Kaneta et al. (Geom. Dedic. 85:317–334, 2001).