The strong convergence of a three-step algorithm for the split feasibility problem

Based on the very recent work by Dang and Gao (Invers Probl 27:1–9, 2011) and Wang and Xu (J Inequal Appl, doi:10.1155/2010/102085, 2010), and inspired by Yao (Appl Math Comput 186:1551–1558, 2007), Noor (J Math Anal Appl 251:217–229, 2000), and Xu (Invers Probl 22:2021–2034, 2006), we suggest a three-step KM-CQ-like method for solving the split common fixed-point problems in Hilbert spaces. Our results improve and develop previously discussed feasibility problem and related algorithms.     

Counterexamples to a triality theorem for quadratic-exponential minimization problems

The main goal of this note is to give a counterexample to the Triality Theorem in Gao and Ruan (Math Methods Oper Res 67:479–491, 2008). This is done first by considering a more general optimization problem with the aim to encompass several examples from Gao and Ruan (Math Methods Oper Res 67:479–491, 2008) and other papers by Gao and his collaborators (see f.i. Gao Duality principles in nonconvex systems. Theory, methods and applications. Kluwer, Dordrecht, 2000; Gao and Sherali Advances in applied mathematics and global optimization. Springer, Berlin, 2009). We perform a thorough analysis of the general optimization problem in terms of local extrema while presenting several counterexamples.     

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.     

Relaxation methods for solving linear inequality systems: converging results

The problem of finding a feasible solution to a linear inequality system arises in numerous contexts. In González-Gutiérrez and Todorov (Optim. Lett. doi:10.1007/s11590-010-0244-4, 2011), an algorithm, called extended relaxation method, for solving the feasibility problem has been proposed by the authors. Convergence of the algorithm has been proven. In this paper, we consider a class of extended relaxation methods depending on a parameter and prove their convergence. Numerical experiments have been provided, as well.     

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.     

A symmetry property for q-weighted Robinson–Schensted and other branching insertion algorithms

In [19], a \(q\) -weighted version of the Robinson–Schensted algorithm was introduced. In this paper, we show that this algorithm has a symmetry property analogous to the well-known symmetry property of the usual Robinson–Schensted algorithm. The proof uses a generalisation of the growth diagram approach introduced by Fomin [5–8]. This approach, which uses ‘growth graphs’, can also be applied to a wider class of insertion algorithms which have a branching structure, including some of the other \(q\) -weighted versions of the Robinson–Schensted algorithm which have recently been introduced by Borodin–Petrov [2].     

An improved local convergence analysis for a two-step Steffensen-type method

We study a class of Steffensen-type algorithm for solving nonsmooth variational inclusions in Banach spaces. We provide a local convergence analysis under ω-conditioned divided difference, and the Aubin continuity property. This work on the one hand extends the results on local convergence of Steffensen’s method related to the resolution of nonlinear equations (see Amat and Busquier in Comput. Math. Appl. 49:13–22, 2005; J. Math. Anal. Appl. 324:1084–1092, 2006; Argyros in Southwest J. Pure Appl. Math. 1:23–29, 1997; Nonlinear Anal. 62:179–194, 2005; J. Math. Anal. Appl. 322:146–157, 2006; Rev. Colomb. Math. 40:65–73, 2006; Computational Theory of Iterative Methods, 2007). On the other hand our approach improves the ratio of convergence and enlarges the convergence ball under weaker hypotheses than one given in Hilout (Commun. Appl. Nonlinear Anal. 14:27–34, 2007).     

Estimating upper bounds on the limit points of majorizing sequences for Newton’s method

We present new sufficient conditions for the semilocal convergence of Newton’s method to a locally unique solution of an equation in a Banach space setting. Upper bounds on the limit points of majorizing sequences are also given. Numerical examples are provided, where our new results compare favorably to earlier ones such as Argyros (J Math Anal Appl 298:374–397, 2004), Argyros and Hilout (J Comput Appl Math 234:2993-3006, 2010, 2011), Ortega and Rheinboldt (1970) and Potra and Pták (1984).     

Non-Decaying Solutions to the Navier Stokes Equations in Exterior Domains

We establish a new theorem of existence (and uniqueness) of solutions to the Navier-Stokes initial boundary value problem in exterior domains. No requirement is made on the convergence at infinity of the kinetic field and of the pressure field. These solutions are called non-decaying solutions. The first results on this topic dates back about 40 years ago see the references (Galdi and Rionero in Ann. Mat. Pures Appl. 108:361–366, 1976, Arch. Ration. Mech. Anal. 62:295–301, 1976, Arch. Ration. Mech. Anal. 69:37–52, 1979, Pac. J. Math. 104:77–83, 1980; Knightly in SIAM J. Math. Anal. 3:506–511, 1972). In the articles Galdi and Rionero (Ann. Mat. Pures Appl. 108:361–366, 1976, Arch. Ration. Mech. Anal. 62:295–301, 1976, Arch. Ration. Mech. Anal. 69:37–52, 1979, Pac. J. Math. 104:77–83, 1980) it was introduced the so called weight function method to study the uniqueness of solutions. More recently, the problem has been considered again by several authors (see Galdi et al. in J. Math. Fluid Mech. 14:633–652, 2012, Quad. Mat. 4:27–68, 1999, Nonlinear Anal. 47:4151–4156, 2001; Kato in Arch. Ration. Mech. Anal. 169:159–175, 2003; Kukavica and Vicol in J. Dyn. Differ. Equ. 20:719–732, 2008; Maremonti in Mat. Ves. 61:81–91, 2009, Appl. Anal. 90:125–139, 2011).     

Revisiting fitting monotone polynomials to data

We revisit Hawkins’ (Comput Stat 9(3):233–247, 1994) algorithm for fitting monotonic polynomials and discuss some practical issues that we encountered using this algorithm, for example when fitting high degree polynomials or situations with a sparse design matrix but multiple observations per $x$ -value. As an alternative, we describe a new approach to fitting monotone polynomials to data, based on different characterisations of monotone polynomials and using a Levenberg–Marquardt type algorithm. We consider different parameterisations, examine effective starting values for the non-linear algorithms, and discuss some limitations. We illustrate our methodology with examples of simulated and real world data. All algorithms discussed in this paper are available in the R Development Core Team (A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, 2011) package MonoPoly.     

Strong NP-hardness of scheduling problems with learning or aging effect

Proofs of strong NP-hardness of single machine and two-machine flowshop scheduling problems with learning or aging effect given in Rudek (Computers & Industrial Engineering 61:20–31, 2011; Annals of Operations Research 196(1):491–516, 2012a; International Journal of Advanced Manufacturing Technology 59:299–309, 2012b; Applied Mathematics and Computations 218:6498–6510, 2012c; Applied Mathematical Modelling 37:1523–1536, 2013) contain a common mistake that make them incomplete. We reveal the mistake and provide necessary corrections for the problems in Rudek (Computers & Industrial Engineering 61:20–31, 2011; Annals of Operations Research 196(1):491–516, 2012a; Applied Mathematical Modelling 37:1523–1536, 2013). NP-hardness of problems in Rudek (International Journal of Advanced Manufacturing Technology 59:299–309, 2012b; Applied Mathematics and Computations 218:6498–6510, 2012c) remains unknown because of another mistake which we are unable to correct.     

Quasi-stationary stefan problem with values on the front depending on its geometry

The problem presented below is a singular-limit problem of the extension of the Cahn-Hilliard model obtained via introducing the asymmetry of the surface tension tensor under one of the truncations (approximations) of the inner energy [2, 5–8, 10, 12, 13].     

Solving proximal split feasibility problems without prior knowledge of operator norms

In this paper our interest is in investigating properties and numerical solutions of Proximal Split feasibility Problems. First, we consider the problem of finding a point which minimizes a convex function \(f\) such that its image under a bounded linear operator \(A\) minimizes another convex function \(g\) . Based on an idea introduced in Lopez (Inverse Probl 28:085004, 2012), we propose a split proximal algorithm with a way of selecting the step-sizes such that its implementation does not need any prior information about the operator norm. Because the calculation or at least an estimate of the operator norm \(\Vert A\Vert \) is not an easy task. Secondly, we investigate the case where one of the two involved functions is prox-regular, the novelty of this approach is that the associated proximal mapping is not nonexpansive any longer. Such situation is encountered, for instance, in numerical solution to phase retrieval problem in crystallography, astronomy and inverse scattering Luke (SIAM Rev 44:169–224, 2002) and is therefore of great practical interest.     

More about λ-support iterations of (<λ)-complete forcing notions

This article continues Ros?anowski and Shelah (Int J Math Math Sci 28:63–82, 2001; Quaderni di Matematica 17:195–239, 2006; Israel J Math 159:109–174, 2007; 2011; Notre Dame J Formal Logic 52:113–147, 2011) and we introduce here a new property of (<λ)-strategically complete forcing notions which implies that their λ-support iterations do not collapse λ ⁺ (for a strongly inaccessible cardinal λ).     

A note on the global convergence theorem of the scaled conjugate gradient algorithms proposed by Andrei

In (Andrei, Comput. Optim. Appl. 38:402?C416, 2007), the efficient scaled conjugate gradient algorithm SCALCG is proposed for solving unconstrained optimization problems. However, due to a wrong inequality used in (Andrei, Comput. Optim. Appl. 38:402?C416, 2007) to show the sufficient descent property for the search directions of SCALCG, the proof of Theorem?2, the global convergence theorem of SCALCG, is incorrect. Here, in order to complete the proof of Theorem?2 in (Andrei, Comput. Optim. Appl. 38:402?C416, 2007), we show that the search directions of SCALCG satisfy the sufficient descent condition. It is remarkable that the convergence analyses in (Andrei, Optim. Methods Softw. 22:561?C571, 2007; Eur. J. Oper. Res. 204:410?C420, 2010) should be revised similarly.     

On the Gauss–Newton method

We provide a new semilocal convergence analysis of the Gauss–Newton method (GNM) for solving nonlinear equation in the Euclidean space. Using a combination of center-Lipschitz, Lipschitz conditions, and our new idea of recurrent functions, we provide under the same or weaker hypotheses than before (Ben-Israel, J. Math. Anal. Appl. 15:243–252, 1966; Chen and Nashed, Numer. Math. 66:235–257, 1993; Deuflhard and Heindl, SIAM J. Numer. Anal. 16:1–10, 1979; Guo, J. Comput. Math. 25:231–242, 2007; Häußler, Numer. Math. 48:119–125, 1986; Hu et al., J. Comput. Appl. Math. 219:110–122, 2008; Kantorovich and Akilov, Functional Analysis in Normed Spaces, Pergamon, Oxford, 1982), a finer convergence analysis. The results can be extended in case outer or generalized inverses are used. Numerical examples are also provided to show that our results apply, where others fail (Ben-Israel, J. Math. Anal. Appl. 15:243–252, 1966; Chen and Nashed, Numer. Math. 66:235–257, 1993; Deuflhard and Heindl, SIAM J. Numer. Anal. 16:1–10, 1979; Guo, J. Comput. Math. 25:231–242, 2007; Häußler, Numer. Math. 48:119–125, 1986; Hu et al., J. Comput. Appl. Math. 219:110–122, 2008; Kantorovich and Akilov, Functional Analysis in Normed Spaces, Pergamon, Oxford, 1982).     

Harmonic mappings in Bergman spaces

In this paper, we investigate the properties of mappings in harmonic Bergman spaces. First, we discuss the coefficient estimate, the Schwarz-Pick Lemma and the Landau-Bloch theorem for mappings in harmonic Bergman spaces in the unit disk $\mathbb D $ of $\mathbb C $ . Our results are generalizations of the corresponding ones in Chen et al. (Proc Am Math Soc 128:3231–3240, 2000), Chen et al. (J Math Anal Appl 373:102–110, 2011), Chen et al. (Ann Acad Sci Fenn Math 36:567–576, 2011). Then, we study the Schwarz-Pick Lemma and the Landau-Bloch theorem for mappings in harmonic Bergman spaces in the unit ball $\mathbb B ^{n}$ of $\mathbb C ^{n}$ . The obtained results are generalizations of the corresponding ones in Chen and Gauthier (Proc Am Math Soc 139:583–595 2011). At last, we get a characterization for mappings in harmonic Bergman spaces on $\mathbb B ^{n}$ in terms of their complex gradients.     

Fine tuning Nesterov’s steepest descent algorithm for differentiable convex programming

We modify the first order algorithm for convex programming described by Nesterov in his book (in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004). In his algorithms, Nesterov makes explicit use of a Lipschitz constant L for the function gradient, which is either assumed known (Nesterov in Introductory lectures on convex optimization. A basic course. Kluwer, Boston, 2004), or is estimated by an adaptive procedure (Nesterov 2007). We eliminate the use of L at the cost of an extra imprecise line search, and obtain an algorithm which keeps the optimal complexity properties and also inherit the global convergence properties of the steepest descent method for general continuously differentiable optimization. Besides this, we develop an adaptive procedure for estimating a strong convexity constant for the function. Numerical tests for a limited set of toy problems show an improvement in performance when compared with the original Nesterov’s algorithms.     

One-dimensional center-based l 1-clustering method

Motivated by the method for solving center-based Least Squares—clustering problem (Kogan in Introduction to clustering large and high-dimensional data, Cambridge University Press, 2007; Teboulle in J Mach Learn Res 8:65–102, 2007) we construct a very efficient iterative process for solving a one-dimensional center-based l ₁—clustering problem, on the basis of which it is possible to determine the optimal partition. We analyze the basic properties and convergence of our iterative process, which converges to a stationary point of the corresponding objective function for each choice of the initial approximation. Given is also a corresponding algorithm, which in only few steps gives a stationary point and the corresponding partition. The method is illustrated and visualized on the example of looking for an optimal partition with two clusters, where we check all stationary points of the corresponding minimizing functional. Also, the method is tested on the basis of large numbers of data points and clusters and compared with the method for solving the center-based Least Squares—clustering problem described in Kogan (2007) and Teboulle (2007).     

Mutually-adjoint boundary-value problems with deviation from the characteristic for a multidimensional Gellerstedt equation

In this paper, we study mutually-adjoint boundary-value problems with a deviation from the characteristic for multidimensional Gellerstedt equation. In [3, 4], for the equation of the vibration of a string, the boundary-value problem with a deviation from the characteristic was studied, where the main attention was paid to the study of such problems for hyperbolic equations. For hyperbolic equations on the plane, this problem was studied in [5, 9].