A regularized Newton method without line search for unconstrained optimization

In this paper, we propose a regularized Newton method without line search. The proposed method controls a regularization parameter instead of a step size in order to guarantee the global convergence. We show that the proposed algorithm has the following convergence properties. (a) The proposed algorithm has global convergence under appropriate conditions. (b) It has superlinear rate of convergence under the local error bound condition. (c) An upper bound of the number of iterations required to obtain an approximate solution \(x\) satisfying \(\Vert \nabla f(x) \Vert \le \varepsilon \) is \(O(\varepsilon ^{-2})\) , where \(f\) is the objective function and \(\varepsilon \) is a given positive constant.     

The Arboreal Jump Number of an Order

Let ${\mathcal P}$ be a partial order and ${\mathcal A}$ an arboreal extension of it (i.e. the Hasse diagram of ${\mathcal A}$ is a rooted tree with a unique minimal element). A jump of ${\mathcal A}$ is a relation contained in the Hasse diagram of ${\mathcal A}$ , but not in the order ${\mathcal P}$ . The arboreal jump number of ${\mathcal A}$ is the number of jumps contained in it. We study the problem of finding the arboreal extension of ${\mathcal P}$ having minimum arboreal jump number—a problem related to the well-known (linear) jump number problem. We describe several results for this problem, including NP-completeness, polynomial time solvable cases and bounds. We also discuss the concept of a minimal arboreal extension, namely an arboreal extension whose removal of one jump makes it no longer arboreal.     

Guaranteed clustering and biclustering via semidefinite programming

Identifying clusters of similar objects in data plays a significant role in a wide range of applications. As a model problem for clustering, we consider the densest \(k\) -disjoint-clique problem, whose goal is to identify the collection of \(k\) disjoint cliques of a given weighted complete graph maximizing the sum of the densities of the complete subgraphs induced by these cliques. In this paper, we establish conditions ensuring exact recovery of the densest \(k\) cliques of a given graph from the optimal solution of a particular semidefinite program. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of \(k\) large, distinct clusters and a smaller number of outliers. This approach also yields a semidefinite relaxation with similar recovery guarantees for the biclustering problem. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. This problem may be posed as that of partitioning the nodes of a weighted bipartite complete graph such that the sum of the densities of the resulting bipartite complete subgraphs is maximized. As in our analysis of the densest \(k\) -disjoint-clique problem, we show that the correct partition of the objects and features can be recovered from the optimal solution of a semidefinite program in the case that the given data consists of several disjoint sets of objects exhibiting similar features. Empirical evidence from numerical experiments supporting these theoretical guarantees is also provided.     

Application of the multipole method to direct and inverse problems for the Grad-Shafranov equation with a nonlocal condition

Two homogeneous Dirichlet problems for the Grad-Shafranov equation with an affine right-hand side are considered in plane simply connected domains with a piecewise smooth boundary. The problems are denoted by and $(\mathfrak{D})$ , and $(\mathfrak{A})$ the second involves a nonlocal condition. The corresponding inverse problems $(\mathfrak{D}^{ - 1} )$ and $(\mathfrak{A}^{ - 1} )$ of finding unknown parameters on the right-hand side of the equation from a given normal derivative of the solution to the respective direct problem are also considered. These problems arise in the computation of plasma flow characteristics in a tokamak. It is shown that the sought parameters can be found from two given quantities: (i) the normal derivative in the corresponding direct problem, which is physically interpreted as the magnetic field at an arbitrary single point $\tilde x$ of a special subset $\tilde \Gamma $ of the boundary Γ, and (ii) the integral of the normal derivative over Γ, which is physically interpreted as the total current through the tokamak cross section. Both problems are shown to be uniquely solvable, and necessary and sufficient conditions for unique solvability are given. A method for finding the desired parameters is proposed, which includes a technique for finding the subset $\tilde \Gamma $ . The results are based, first, on the multipole method, which ensures the high-order accurate computation of the normal derivatives of the solution to direct problems $(\mathfrak{D})$ and $(\mathfrak{A})$ , and, second, on the asymptotics of these derivatives as one of the parameters on the right-hand side of the equation tends to infinity.     

Convex optimization for the planted k-disjoint-clique problem

We consider the $k$ -disjoint-clique problem. The input is an undirected graph $G$ in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph $k$ disjoint cliques that cover the maximum number of nodes of $G$ . This problem may be understood as a general way to pose the classical ‘clustering’ problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters of data items, such that the items in each cluster are close to each other. Our formulation additionally allows ‘noise’ nodes to be present in the input data that are not part of any of the cliques. The $k$ -disjoint-clique problem is NP-hard, but we show that a convex relaxation can solve it in polynomial time for input instances constructed in a certain way. The input instances for which our algorithm finds the optimal solution consist of $k$ disjoint large cliques (called ‘planted cliques’) that are then obscured by noise edges inserted either at random or by an adversary, as well as additional nodes not belonging to any of the $k$ planted cliques.     

Coset intersection of irreducible plane cubics

In a projective plane $PG(2,\mathbb K )$ over an algebraically closed field $\mathbb K $ of characteristic $p\ge 0$ , let $\Omega $ be a pointset of size $n$ with $5\le n \le 9$ . The coset intersection problem relative to $\Omega $ is to determine the family $\mathbf F$ of irreducible cubics in $PG(2,\mathbb K )$ for which $\Omega $ is a common coset of a subgroup of the additive group $(\mathcal F ,+)$ for every $\mathcal F \in \mathbf F$ . In this paper, a complete solution of this problem is given.     

The generalization of Minkowski problems for polytopes

The generalization of Minkowski problems, such as the $L_p$ and Orlicz Minkowski problems, have caused wide concern recently. In this paper, we will establish the existence of the Orlicz Minkowski problem for polytopes. In particular, a solution to the $L_p$ Minkowski problem for polytopes with $p>1$ is given. By the uniqueness of this solution, we present a new proof of the $L_p$ Minkowski inequality that demonstrates the relationship between these two fundamental theorems of the $L_p$ Brunn–Minkowski theory.     

Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain

In this paper, we study the problem of moving $n$ n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an $O(n^2\log n)$ O ( n 2 log n ) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $O(n^2)$ O ( n 2 ) time. We present an $O(n\log n)$ O ( n log n ) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $O(n)$ O ( n ) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in $O(n)$ O ( n ) time, improving the previously best $O(n^2)$ O ( n 2 ) time solution.     

A hyperbolic smoothing approach to the Multisource Weber problem

The Multisource Weber problem, also known as the continuous location-allocation problem, or as the Fermat-Weber problem, is considered here. A particular case of the Multisource Weber problem is the minimum sum-of-distances clustering problem, also known as the continuous \(p\) -median problem. The mathematical modelling of this problem leads to a \(min-sum-min\) formulation which, in addition to its intrinsic bi-level nature, is strongly nondifferentiable. Moreover, it has a large number of local minimizers, so it is a typical global optimization problem. In order to overcome the intrinsic difficulties of the problem, the so called Hyperbolic Smoothing methodology, which follows a smoothing strategy using a special \( \, C^{\infty } \, \) differentiable class function, is adopted. The final solution is obtained by solving a sequence of low dimension \( \, C^{\infty } \, \) differentiable unconstrained optimization sub-problems which gradually approaches the original problem. For the purpose of illustrating both the reliability and the efficiency of the method, a set of computational experiments making use of traditional test problems described in the literature was performed. Apart from consistently presenting better results when compared to related approaches, the novel technique introduced here was able to deal with instances never tackled before in the context of the Multisource Weber problem.     

Thresholded covering algorithms for robust and max–min optimization

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems.     

Semidefinite relaxations of ordering problems

Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element $u$ is before $v$ in the ordering. In the second case, the profit depends on whether $u$ is before $v$ and $r$ is before $s$ . The linear ordering problem is well studied, with exact solution methods based on polyhedral relaxations. The quadratic ordering problem does not seem to have attracted similar attention. We present a systematic investigation of semidefinite optimization based relaxations for the quadratic ordering problem, extending and improving existing approaches. We show the efficiency of our relaxations by providing computational experience on a variety of problem classes.     

Parameterization of the Extrapolations in the Kreĭn–Schwartz Theorem and the Entropy Maximizer: the Scalar Case

A Kre?n-de Branges-Kotani space $\mathbb{H }$ is associated to a given positive-definite distribution $Q$ on the finite interval $(-a,a)$ of the real line. The Kre?n-de Branges Theorem is applied to get a spectral measure of $\mathbb{H }$ . In this way a simple proof of the solubility of the Kre?n’s extension problem related to $Q$ (Kre?n–Schwartz Theorem) is obtained. A condition that guarantees the uniqueness of the extrapolation as well as a parameterization of the extrapolations by means of Schur functions are given. The choice of the Schur function $\eta \equiv 0$ in the parameterization is shown to produce an absolutely continuous measure which maximizes Burg’s entropy. The results are based on the coupling of the Arov–Grossman functional model with a Hilbert space operator built up from the multiplication operator on $\mathbb{H }$ .     

Elliptic equations with jumping nonlinearities involving high eigenvalues

We present some multiplicity results concerning semilinear elliptic Dirichlet problems with jumping nonlinearities where the jumping condition involves a set of high eigenvalues not including the first one. Using a variational method we show that the number of solutions may be arbitrarily large provided the number of jumped eigenvalues is large enough. Indeed, we prove that for every positive integer $k$ there exists a positive integer $n(k)$ such that, if the number of jumped eigenvalues is greater than $n(k),$ then the problem has at least a solution which presents $k$ peaks. Moreover, we describe the asymptotic behaviour of the solutions as the number of jumped eigenvalues tends to infinity; in particular, we analyse some concentration phenomena of the peaks (near points or suitable manifolds), we describe the asymptotic profile of the rescaled peaks, etc $\ldots $      

Derivative-free optimization: a review of algorithms and comparison of software implementations

This paper addresses the solution of bound-constrained optimization problems using algorithms that require only the availability of objective function values but no derivative information. We refer to these algorithms as derivative-free algorithms. Fueled by a growing number of applications in science and engineering, the development of derivative-free optimization algorithms has long been studied, and it has found renewed interest in recent time. Along with many derivative-free algorithms, many software implementations have also appeared. The paper presents a review of derivative-free algorithms, followed by a systematic comparison of 22 related implementations using a test set of 502 problems. The test bed includes convex and nonconvex problems, smooth as well as nonsmooth problems. The algorithms were tested under the same conditions and ranked under several criteria, including their ability to find near-global solutions for nonconvex problems, improve a given starting point, and refine a near-optimal solution. A total of 112,448 problem instances were solved. We find that the ability of all these solvers to obtain good solutions diminishes with increasing problem size. For the problems used in this study, TOMLAB/MULTIMIN, TOMLAB/GLCCLUSTER, MCS and TOMLAB/LGO are better, on average, than other derivative-free solvers in terms of solution quality within 2,500 function evaluations. These global solvers outperform local solvers even for convex problems. Finally, TOMLAB/OQNLP, NEWUOA, and TOMLAB/MULTIMIN show superior performance in terms of refining a near-optimal solution.     

Optimal L^2, H^1 and L^\infty analysis of finite volume methods for the stationary Navier–Stokes equations with large data

Previous work on the stability and convergence analysis of numerical methods for the stationary Navier–Stokes equations was carried out under the uniqueness condition of the solution, which required that the data be small enough in certain norms. In this paper an optimal analysis for the finite volume methods is performed for the stationary Navier–Stokes equations, which relaxes the solution uniqueness condition and thus the data requirement. In particular, optimal order error estimates in the $H^1$ -norm for velocity and the $L^2$ -norm for pressure are obtained with large data, and a new residual technique for the stationary Navier–Stokes equations is introduced for the first time to obtain a convergence rate of optimal order in the $L^2$ -norm for the velocity. In addition, after proving a number of additional technical lemmas including weighted $L^2$ -norm estimates for regularized Green’s functions associated with the Stokes problem, optimal error estimates in the $L^\infty $ -norm are derived for the first time for the velocity gradient and pressure without a logarithmic factor $O(|\log h|)$ for the stationary Naiver–Stokes equations.     

From pointwise to local regularity for solutions of Hamilton–Jacobi equations

It is well-known that solutions to the Hamilton–Jacobi equation $$\begin{aligned} u_{t}(t,x)+H(x,u_{x}(t,x))=0 \end{aligned}$$ fail to be everywhere differentiable. Nevertheless, suppose a solution $u$ turns out to be differentiable at a given point $(t,x)$ in the interior of its domain. May then one deduce that $u$ must be continuously differentiable in a neighborhood of $(t,x)$ ? Although this question has a negative answer in general, our main result shows that it is indeed the case when the proximal subdifferential of $u(t,\cdot )$ at $x$ is nonempty. Our approach uses the representation of $u$ as the value function of a Bolza problem in the calculus of variations, as well as necessary conditions for such a problem.     

Problems with resource allocation constraints and optimization over the efficient set

The paper studies a nonlinear optimization problem under resource allocation constraints. Using quasi-gradient duality it is shown that the feasible set of the problem is a singleton (in the case of a single resource) or the set of Pareto efficient solutions of an associated vector maximization problem (in the case of $k>1$ resources). As a result, a nonlinear optimization problem under resource allocation constraints reduces to an optimization over the efficient set. The latter problem can further be converted into a quasiconvex maximization over a compact convex subset of $\mathbb{R }^k_+.$ Alternatively, it can be approached as a bilevel program and converted into a monotonic optimization problem in $\mathbb{R }^k_+.$ In either approach the converted problem falls into a common class of global optimization problems for which several practical solution methods exist when the number $k$ of resources is relatively small, as it often occurs.     

Truncated Quillen complexes of p-groups

Let \(p\) be an odd prime and let \(P\) be a \(p\) -group. We examine the order complex of the poset of elementary abelian subgroups of \(P\) having order at least \(p^2\) . Bouc and Thévenaz showed that this complex has the homotopy type of a wedge of spheres. We show that, for each nonnegative integer \(l\) , the number of spheres of dimension \(l\) in this wedge is controlled by the number of extraspecial subgroups \(X\) of \(P\) having order \(p^{2l+3}\) and satisfying \(\Omega _1(C_P(X))=Z(X)\) . We go on to provide a negative answer to a question raised by Bouc and Thévenaz concerning restrictions on the homology groups of the given complex.     

How Far Can Chemotactic Cross-diffusion Enforce Exceeding Carrying Capacities?

We consider nonnegative solutions of the Neumann initial-boundary value problem for the chemotaxis-growth system $$\begin{aligned} \left\{ \begin{array}{l} u_t=\varepsilon u_{xx} -(uv_x)_x +ru -\mu u^2, \qquad x\in \Omega , \ t>0, \\ 0=v_{xx}-v+u, \qquad x\in \Omega , \ t>0, \end{array} \right. \quad (\star ) \end{aligned}$$ in \(\Omega :=(0,L)\subset \mathbb {R}\) with \(L>0, \varepsilon >0, r\ge 0\) and \(\mu >0\) , along with the corresponding limit problem formally obtained upon taking \(\varepsilon \searrow 0\) . For the latter hyperbolic–elliptic problem, we establish results on local existence and uniqueness within an appropriate generalized solution concept. In this context we shall moreover derive an extensibility criterion involving the norm of \(u(\cdot ,t)\) in \(L^\infty (\Omega )\) . This will enable us to conclude that in this case \(\varepsilon =0\) ,

• if \(\mu \ge 1\) , then all solutions emanating from sufficiently regular initial data are global in time, whereas
• if \(\mu <1\) , then some solutions blow-up in finite time.

The latter will reveal that the original parabolic–elliptic problem ( \(\star \) ), though known to possess no such exploding solutions, exhibits the following property of dynamical structure generation: given any \(\mu \in (0,1)\) , one can find smooth bounded initial data with the property that for each prescribed number \(M>0\) the solution of ( \(\star \) ) will attain values above \(M\) at some time, provided that \(\varepsilon \) is sufficiently small. In particular, this means that the associated carrying capacity given by \(\frac{r}{\mu }\) can be exceeded during evolution to an arbitrary extent. We finally present some numerical simulations that illustrate this type of solution behavior and that, moreover, inter alia, indicate that achieving large population densities is a transient dynamical phenomenon occurring on intermediate time scales only.     

Preemptive and non-preemptive generalized min sum set cover

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given $n$ ground elements and a collection of sets $\mathcal{S }= \{S_1, S_2, \ldots , S_m\}$ where each set $S_i \in 2^{[n]}$ has a positive requirement $\kappa (S_i)$ that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set $S_i$ is defined as the first index $j$ in the ordering such that the first $j$ elements in the ordering contain $\kappa (S_i)$ elements in $S_i$ . This problem was introduced by Azar et al. (2009) with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known by Bansal et al. (2010) and Skutella and Williamson (Oper Res Lett 39(6):433–436, 2011). We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set $S$ is covered in the moment when $\kappa (S)$ amount of elements in $S$ are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming relaxation and analysis are completely different from the aforementioned previous works. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved $12.4$ -approximation for the non-preemptive problem.