A projection subgradient method for solving optimization with variational inequality constraints

In this paper, we propose a projection subgradient method for solving some classical variational inequality problem over the set of solutions of mixed variational inequalities. Under the conditions that $T$ is a $\Theta $ -pseudomonotone mapping and $A$ is a $\rho $ -strongly pseudomonotone mapping, we prove the convergence of the algorithm constructed by projection subgradient method. Our algorithm can be applied for instance to some mathematical programs with complementarity constraints.     

Regularization and iterative methods for monotone inverse variational inequalities

We consider the monotone inverse variational inequality: find $x\in H$ such that $$\begin{aligned} f(x)\in \Omega , \quad \left\langle \tilde{f}-f(x),x\right\rangle \ge 0, \quad \forall \tilde{f}\in \Omega , \end{aligned}$$ where $\Omega $ is a nonempty closed convex subset of a real Hilbert space $H$ and $f:H\rightarrow H$ is a monotone mapping. A general regularization method for monotone inverse variational inequalities is shown, where the regularizer is a Lipschitz continuous and strongly monotone mapping. Moreover, we also introduce an iterative method as discretization of the regularization method. We prove that both regularized solution and an iterative method converge strongly to a solution of the inverse variational inequality.     

On efficiency and mixed duality for a new class of nonconvex multiobjective variational control problems

In this paper, we extend the notions of \((\Phi ,\rho )\) -invexity and generalized \((\Phi ,\rho )\) -invexity to the continuous case and we use these concepts to establish sufficient optimality conditions for the considered class of nonconvex multiobjective variational control problems. Further, multiobjective variational control mixed dual problem is given for the considered multiobjective variational control problem and several mixed duality results are established under \((\Phi ,\rho )\) -invexity.     

An iterative algorithm for common fixed points for nonexpansive semigroups and strictly pseudo-contractive mappings with optimization problems

In this paper, we introduce an iterative algorithm for finding a common element of the set of solutions of a system of mixed equilibrium problems, the set of solutions of a variational inclusion problems for inverse strongly monotone mappings, the set of common fixed points for nonexpansive semigroups and the set of common fixed points for an infinite family of strictly pseudo-contractive mappings in Hilbert spaces. Furthermore, we prove a strong convergence theorem of the iterative sequence generated by the proposed iterative algorithm under some suitable conditions which solves some optimization problems. Our results extend and improve the recent results of Chang et al. (Appl Math Comput 216:51–60, 2010), Hao (Appl Math Comput 217(7):3000–3010, 2010), Jaiboon and Kumam (Nonlinear Anal 73:1180–1202, 2010) and many others.     

The Second Variational Formula for Laguerre Minimal Hypersurfaces in {\mathbb {R}^n}

Li and Wang (Manuscr Math 122(1):73–95, 2007) presented Laguerre geometry for hypersurfaces in ${\mathbb{R}^{n}}$ and calculated the first variational formula of the Laguerre functional by using Laguerre invariants. In this paper we present the second variational formula for Laguerre minimal hypersurfaces. As an application of this variational formula we give the standard examples of Laguerre minimal hypersurfaces in ${\mathbb{R}^{n}}$ and show that they are stable Laguerre minimal hypersurfaces. Using this second variational formula we can prove that a surface with vanishing mean curvature in ${\mathbb{R}^{3}_{0}}$ is Laguerre equivalent to a stable Laguerre minimal surface in ${\mathbb{R}^{3}}$ under the Laguerre embedding. This example of stable Laguerre minimal surface in ${\mathbb{R}^{3}}$ is different from the one Palmer gave in (Rend Mat Appl 19(2):281–293, 1999).     

Singular perturbation method for inhomogeneous nonlinear free boundary problems

In this paper, we study solutions of one phase inhomogeneous singular perturbation problems of the type: $ F(D^2u,x)=\beta _{\varepsilon }(u) + f_{\varepsilon }(x) $ and $ \Delta _{p}u=\beta _{\varepsilon }(u) + f_{\varepsilon }(x)$ , where $\beta _{\varepsilon }$ approaches Dirac $\delta _{0}$ as $\varepsilon \rightarrow 0$ and $f_{\varepsilon }$ has a uniform control in $L^{q}, q>N.$ Uniform local Lipschitz regularity is obtained for these solutions. The existence theory for variational (minimizers) and non variational (least supersolutions) solutions for these problems is developed. Uniform linear growth rate with respect to the distance from the $\varepsilon -$ level surfaces are established for these variational and nonvaritional solutions. Finally, letting $\varepsilon \rightarrow 0$ basic properties such as local Lipschitz regularity and non-degeneracy property are proven for the limit and a Hausdorff measure estimate for its free boundary is obtained.     

RENS

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution $\bar{x}$ of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables $x_j$ with $\bar{x} _{j} \in \mathbb {Z}$ and bounding the remaining integer variables to $x_{j} \in \{ \lfloor \bar{x} _{j} \rfloor , \lceil \bar{x} _{j} \rceil \}$ . We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLP s, using solely software which is available in source code. It turns out that for these problem classes 60 to 70 % of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.     

Solving inverse cone-constrained eigenvalue problems

We compare various algorithms for constructing a matrix of order $n$ whose Pareto spectrum contains a prescribed set $\Lambda =\{\lambda _1,\ldots , \lambda _p\}$ of reals. In order to avoid overdetermination one assumes that $p$ does not exceed $n^2.$ The inverse Pareto eigenvalue problem under consideration is formulated as an underdetermined system of nonlinear equations. We also address the issue of computing Lorentz spectra and solving inverse Lorentz eigenvalue problems.     

Identification of a convolution kernel in a control problem for the heat equation with a boundary memory term

We consider the evolution of the temperature \(u\) in a material with thermal memory characterized by a time-dependent convolution kernel \(h\) . The material occupies a bounded region \(\Omega \) with a feedback device controlling the external temperature located on the boundary \(\Gamma \) . Assuming both \(u\) and \(h\) unknown, we formulate an inverse control problem for an integrodifferential equation with a nonlinear and nonlocal boundary condition. Existence and uniqueness results of a solution to the inverse problem are proved.     

A perturbation method for spinorial Yamabe type equations on S^m and its application

For $m\ge 2$ , we prove the existence of non-trivial solutions for a certain kind of nonlinear Dirac equations with critical Sobolev nonlinearities on $S^m$ via a perturbative variational method. For the special case $m=2$ , this establishes the existence of a conformal immersion $S^2\rightarrow \mathbb R ^3$ with prescribed mean curvature $H$ which is close to a positive constant under an index counting condition on $H$ .     

A mean field model for a class of garbage collection algorithms in flash-based solid state drives

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class $\mathcal {C}$ of GC algorithms. Apart from the Random GC algorithm, class $\mathcal {C}$ includes two novel GC algorithms: the $d$ -Choices GC algorithm, that selects $d$ blocks uniformly at random and erases the block containing the least number of valid pages among the $d$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments, we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $N=50{,}000$ blocks). We further show that the $d$ -Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small $d$ values, e.g., $d = 10$ , and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $b$ per block is large (e.g., for $b \ge 64$ ).     

Optimal Reconstruction Might be Hard

Given as input a point set $\mathcal S $ that samples a shape $\mathcal A $ , the condition required for inferring Betti numbers of $\mathcal A $ from $\mathcal S $ in polynomial time is much weaker than the conditions required by any known polynomial time algorithm for producing a topologically correct approximation of $\mathcal A $ from $\mathcal S $ . Under the former condition which we call the weak precondition, we investigate the question whether a polynomial time algorithm for reconstruction exists. As a first step, we provide an algorithm which outputs an approximation of the shape with the correct Betti numbers under a slightly stronger condition than the weak precondition. Unfortunately, even though our algorithm terminates, its time complexity is unbounded. We then identify at the heart of our algorithm a test which requires answering the following question: given 2 two-dimensional simplicial complexes $L \subset K$ , does there exist a simplicial complex containing $L$ and contained in $K$ which realizes the persistent homology of $L$ into $K$ ? We call this problem the homological simplification of the pair $(K,L)$ and prove that this problem is NP-complete, using a reduction from 3SAT.     

Existence and extremal solutions of parabolic variational–hemivariational inequalities

We consider quasilinear parabolic variational–hemivariational inequalities in a cylindrical domain $Q=\Omega \times (0,\tau )$ of the form $$\begin{aligned} u\in K:\ \langle u_t+Au, v-u\rangle +\int _Q j^o(x,t, u;v-u)\,dxdt\ge 0,\ \ \forall \ v\in K, \end{aligned}$$ where $K\subset X_0=L^p(0,\tau ;W_0^{1,p}(\Omega ))$ is some closed and convex subset, $A$ is a time-dependent quasilinear elliptic operator, and $s\mapsto j(\cdot ,\cdot ,s)$ is assumed to be locally Lipschitz with $(s,r)\mapsto j^o(x,t, s;r)$ denoting its generalized directional derivative at $s$ in the direction $r$ . The main goal of this paper is threefold: first, an existence and comparison principle is proved; second, the existence of extremal solutions within some sector of appropriately defined sub-supersolutions is shown; third, the equivalence of the above parabolic variational–hemivariational inequality with an associated multi-valued parabolic variational inequality of the form $$\begin{aligned} u\in K:\ \langle u_t+Au, v-u\rangle +\int _Q \eta \, (v-u)\,dxdt\ge 0,\ \ \forall \ v\in K \end{aligned}$$ with $\eta (x,t)\in \partial j(x,t, u(x,t))$ is established, where $s\mapsto \partial j(x,t, s)$ denotes Clarke’s generalized gradient of the locally Lipschitz function $s\mapsto j(\cdot ,\cdot ,s)$ .     

Mixed discriminants

The mixed discriminant of $n$ Laurent polynomials in $n$ variables is the irreducible polynomial in the coefficients which vanishes whenever two of the roots coincide. The Cayley trick expresses the mixed discriminant as an $A$ -discriminant. We show that the degree of the mixed discriminant is a piecewise linear function in the Plücker coordinates of a mixed Grassmannian. An explicit degree formula is given for the case of plane curves.     

On matching cover of graphs

A k-matching cover of a graph \(G\) is a union of \(k\) matchings of \(G\) which covers \(V(G)\) . The matching cover number of \(G\) , denoted by \(mc(G)\) , is the minimum number \(k\) such that \(G\) has a \(k\) -matching cover. A matching cover of \(G\) is optimal if it consists of \(mc(G)\) matchings of \(G\) . In this paper, we present an algorithm for finding an optimal matching cover of a graph on \(n\) vertices in \(O(n^3)\) time (if use a faster maximum matching algorithm, the time complexity can be reduced to \(O(nm)\) , where \(m=|E(G)|\) ), and give an upper bound on matching cover number of graphs. In particular, for trees, a linear-time algorithm is given, and as a by-product, the matching cover number of trees is determined.     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.     

Counting and Sampling Minimum Cuts in Genus g Graphs

Let \(G\) be a directed graph with \(n\) vertices embedded on an orientable surface of genus \(g\) with two designated vertices \(s\) and \(t\) . We show that computing the number of minimum \((s,t)\) -cuts in \(G\) is fixed-parameter tractable in \(g\) . Specifically, we give a \(2^{O(g)} n^2\) time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are no prior results that are fixed-parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample an \((s,t)\) -minimum cut uniformly at random in \(O(n \log n)\) time per sample.     

On maximum likelihood estimation of the concentration parameter of von Mises–Fisher distributions

Maximum likelihood estimation of the concentration parameter of von Mises–Fisher distributions involves inverting the ratio \(R_\nu = I_{\nu +1} / I_\nu \) of modified Bessel functions and computational methods are required to invert these functions using approximative or iterative algorithms. In this paper we use Amos-type bounds for \(R_\nu \) to deduce sharper bounds for the inverse function, determine the approximation error of these bounds, and use these to propose a new approximation for which the error tends to zero when the inverse of \(R_\nu \) is evaluated at values tending to \(1\) (from the left). We show that previously introduced rational bounds for \(R_\nu \) which are invertible using quadratic equations cannot be used to improve these bounds.     

On the Density of the Winding Number of Planar Brownian Motion

We obtain a formula for the density \(f(\theta , t)\) of the winding number of a planar Brownian motion \(Z_t\) around the origin. From this formula, we deduce an expansion for \(f(\log (\sqrt{t})\,\theta ,\,t)\) in inverse powers of \(\log \sqrt{t}\) and \((1+\theta ^2)^{1/2}\) which in particular yields the corrections of any order to Spitzer’s asymptotic law (in Spitzer, Trans. Am. Math. Soc. 87:187–197, 1958). We also obtain an expansion for \(f(\theta ,t)\) in inverse powers of \(\log \sqrt{t}\) , which yields precise asymptotics as \(t \rightarrow \infty \) for a local limit theorem for the windings.     

Affine Types of L -Polyhedra for 5 -lattices

We construct an algorithm for deducing all affinely nonequivalent types of $L$ -polyhedra on n-lattices, where $n \leqslant 5$ . The computational part of the algorithm designed for calculations on a personal computer is based on the relationship between the geometry of lattices and the theory of hypermetric spaces. For the first time, a complete list of affine types ( $139$ types) of $L$ -polyhedra on $5 $ -lattices is obtained.