Decomposable norm minimization with proximal-gradient homotopy algorithm

We study the convergence rate of the proximal-gradient homotopy algorithm applied to norm-regularized linear least squares problems, for a general class of norms. The homotopy algorithm reduces the regularization parameter in a series of steps, and uses a proximal-gradient algorithm to solve the problem at each step. Proximal-gradient algorithm has a linear rate of convergence given that the objective function is strongly convex, and the gradient of the smooth component of the objective function is Lipschitz continuous. In many applications, the objective function in this type of problem is not strongly convex, especially when the problem is high-dimensional and regularizers are chosen that induce sparsity or low-dimensionality. We show that if the linear sampling matrix satisfies certain assumptions and the regularizing norm is decomposable, proximal-gradient homotopy algorithm converges with a linear rate even though the objective function is not strongly convex. Our result generalizes results on the linear convergence of homotopy algorithm for \(\ell _1\)-regularized least squares problems. Numerical experiments are presented that support the theoretical convergence rate analysis.     

Solving multi-period interdiction via generalized Bender’s decomposition

This paper considers a novel formulation of the multi-period network interdiction problem. In this model, delivery of the maximum flow as well as the act of interdiction happens over several periods, while the budget of resource for interdiction is limit. It is assumed that when an edge is interdicted in a period, the evader considers a rate of risk of detection at consequent periods. Application of the generalized Benders decomposition algorithm considers solving the resulting mixed-integer nonlinear programming problem. Computational experiences denote reasonable consistency with expectations.     

Rectangular-radial drawings of cubic plane graphs

Rectangular drawings and rectangular duals can be naturally extended to other surfaces. In this paper, we extend rectangular drawings and rectangular duals to drawings on a cylinder. The extended drawings are called rectangular-radial drawings and rectangular-radial duals. Rectangular-radial drawings correspond to periodic rectangular tilings of a 1-dimensional strip. We establish a necessary and sufficient condition for plane graphs with maximum degree 3 to have rectangular-radial drawings and a necessary and sufficient condition for triangulated plane graphs to have rectangular-radial duals. Furthermore, we present three linear time algorithms under three different conditions for finding a rectangular-radial drawing for a given cubic plane graph, if one exists.     

On the fractional derivatives of radial basis functions: Theories and applications

The paper provides the fractional integrals and derivatives of the Riemann‐Liouville and Caputo type for the five kinds of radial basis functions, including the Powers, Gaussian, Multiquadric, Matérn, and Thin‐plate splines, in one dimension. It allows to use high‐order numerical methods for solving fractional differential equations. The results are tested by solving two test problems. The first test case focuses on the discretization of the fractional differential operator while the second considers the solution of a fractional order differential equation.     

Top local cohomology modules and Gorenstein injectivity with respect to a semidualizing module

Let ${(R, \mathfrak{m})}$ be a commutative Noetherian local ring of Krull dimension d, and let C be a semidualizing R-module. In this paper, it is shown that if R is complete, then C is a dualizing module if and only if the top local cohomology module of ${R, H _{\mathfrak{m}} ^{d} (R)}$ , has finite G _C -injective dimension. This generalizes a recent result due to Yoshizawa, where the ring is assumed to be complete Cohen-Macaulay.     

On the Stability of a k-Cubic Functional Equation in Intuitionistic Fuzzy n-Normed Spaces

In this paper, we investigate some stability results concerning the k-cubic functional equation f(kx + y) + f(kx?y) = kf(x + y) + kf(x?y) + 2k(k²?1)f(x) in the intuitionistic fuzzy n-normed spaces.     

On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients

The gradient descent method minimizes an unconstrained nonlinear optimization problem with \({\mathcal {O}}(1/\sqrt{K})\), where K is the number of iterations performed by the gradient method. Traditionally, this analysis is obtained for smooth objective functions having Lipschitz continuous gradients. This paper aims to consider a more general class of nonlinear programming problems in which functions have Hölder continuous gradients. More precisely, for any function f in this class, denoted by \({{\mathcal {C}}}^{1,\nu }_L\), there is a \(\nu \in (0,1]\) and \(L>0\) such that for all \(\mathbf{x,y}\in {{\mathbb {R}}}^n\) the relation \(\Vert \nabla f(\mathbf{x})-\nabla f(\mathbf{y})\Vert \le L \Vert \mathbf{x}-\mathbf{y}\Vert ^{\nu }\) holds. We prove that the gradient descent method converges globally to a stationary point and exhibits a convergence rate of \({\mathcal {O}}(1/K^{\frac{\nu }{\nu +1}})\) when the step-size is chosen properly, i.e., less than \([\frac{\nu +1}{L}]^{\frac{1}{\nu }}\Vert \nabla f(\mathbf{x}_k)\Vert ^{\frac{1}{\nu }-1}\). Moreover, the algorithm employs \({\mathcal {O}}(1/\epsilon ^{\frac{1}{\nu }+1})\) number of calls to an oracle to find \({\bar{\mathbf{x}}}\) such that \(\Vert \nabla f({{\bar{\mathbf{x}}}})\Vert <\epsilon \).     

An improved heuristic for the far from most strings problem

The Far From Most Strings Problem (FFMSP) asks for a string that is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are far if their Hamming distance is greater than or equal to a given threshold. FFMSP belongs to the class of sequence consensus problems which have applications in molecular biology, amongst others. FFMSP is NP-hard. It does not admit a constant-ratio approximation either, unless P=NP. In the last few years, heuristic and metaheuristic algorithms have been proposed for the problem, which use local search and require a heuristic, also called an evaluation function, to evaluate candidate solutions during local search. The heuristic function used, for this purpose, in these algorithms is the problem’s objective function. However, since many candidate solutions can be of the same objective value, the resulting search landscape includes many points which correspond to local maxima. In this paper, we devise a new heuristic function to evaluate candidate solutions. We then incorporate the proposed heuristic function within a Greedy Randomized Adaptive Search Procedure (GRASP), a metaheuristic originally proposed for the problem by Festa. The resulting algorithm outperforms state-of-the-art with respect to solution quality, in some cases by orders of magnitude, on both random and real data in our experiments. The results indicate that the number of local optima is considerably reduced using the proposed heuristic.     

k-torsionless modules with finite Gorenstein dimension

Let R be a commutative Noetherian ring. It is shown that the finitely generated R-module M with finite Gorenstein dimension is reflexive if and only if M _p is reflexive for p ∈ Spec(R) with depth(R _p) ? 1, and $G - {\dim _{{R_p}}}$ (M _p) ? depth(R _p) ? 2 for p ∈ Spec(R) with depth(R _p) ? 2. This gives a generalization of Serre and Samuel’s results on reflexive modules over a regular local ring and a generalization of a recent result due to Belshoff. In addition, for n ? 2 we give a characterization of n-Gorenstein rings via Gorenstein dimension of the dual of modules. Finally it is shown that every R-module has a k-torsionless cover provided R is a k-Gorenstein ring.     

On dominant poles and model reduction of second order time-delay systems

The method known as the dominant pole algorithm (DPA) has previously been successfully used in combination with model order reduction techniques to approximate standard linear time-invariant dynamical systems and second order dynamical systems. In this paper, we show how this approach can be adapted to a class of second order delay systems, which are large scale nonlinear problems whose transfer functions have an infinite number of simple poles. Deflation is a very important ingredient for this type of methods. Because of the nonlinearity, many deflation approaches for linear systems are not applicable. We therefore propose an alternative technique that essentially removes computed poles from the system?s input and output vectors. In general, this technique changes the residues, and hence, modifies the order of dominance of the poles, but we prove that, under certain conditions, the residues stay near the original residues. The new algorithm is illustrated by numerical examples.