Iterative reweighted minimization methods for l_p regularized unconstrained nonlinear programming

In this paper we study general \(l_p\) regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of the first- and second-order stationary points and hence also of local minimizers of the \(l_p\) minimization problems. We extend some existing iterative reweighted \(l_1\) ( \(\mathrm{IRL}_1\) ) and \(l_2\) ( \(\mathrm{IRL}_2\) ) minimization methods to solve these problems and propose new variants for them in which each subproblem has a closed-form solution. Also, we provide a unified convergence analysis for these methods. In addition, we propose a novel Lipschitz continuous \({\epsilon }\) -approximation to \(\Vert x\Vert ^p_p\) . Using this result, we develop new \(\mathrm{IRL}_1\) methods for the \(l_p\) minimization problems and show that any accumulation point of the sequence generated by these methods is a first-order stationary point, provided that the approximation parameter \({\epsilon }\) is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that \({\epsilon }\) be dynamically updated and approach zero. Our computational results demonstrate that the new \(\mathrm{IRL}_1\) method and the new variants generally outperform the existing \(\mathrm{IRL}_1\) methods (Chen and Zhou in 2012; Foucart and Lai in Appl Comput Harmon Anal 26:395–407, 2009).     

Revisiting several problems and algorithms in continuous location with \ell _\tau norms

This paper addresses the general continuous single facility location problems in finite dimension spaces under possibly different \(\ell _\tau \) norms, \(\tau \ge 1\) , in the demand points. We analyze the difficulty of this family of problems and revisit convergence properties of some well-known algorithms. The ultimate goal is to provide a common approach to solve the family of continuous \(\ell _\tau \) ordered median location problems Nickel and Puerto (Facility location: a unified approach, 2005) in dimension \(d\) (including of course the \(\ell _\tau \) minisum or Fermat-Weber location problem for any \(\tau \ge 1\) ). We prove that this approach has a polynomial worst case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems.     

On the Largest Graph-Lagrangian of 3-Graphs with Fixed Number of Edges

The Graph-Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Graph-Lagrangian of a hypergraph. Frankl and Füredi conjectured that the \({r}\) -graph with \(m\) edges formed by taking the first \(\textit{m}\) sets in the colex ordering of the collection of all subsets of \({\mathbb N}\) of size \({r}\) has the largest Graph-Lagrangian of all \(r\) -graphs with \(m\) edges. In this paper, we show that the largest Graph-Lagrangian of a class of left-compressed \(3\) -graphs with \(m\) edges is at most the Graph-Lagrangian of the \(\mathrm 3 \) -graph with \(m\) edges formed by taking the first \(m\) sets in the colex ordering of the collection of all subsets of \({\mathbb N}\) of size \({3}\) .     

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.     

How large dimension guarantees a given angle?

We study the following two problems: (1) Given $n\ge 2$ and $0\le \alpha \le 180^\circ $ , how large Hausdorff dimension can a compact set $A\subset \mathbb{R }^n$ have if $A$ does not contain three points that form an angle $\alpha $ ? (2) Given $\alpha $ and $\delta $ , how large Hausdorff dimension can a subset $A$ of a Euclidean space have if $A$ does not contain three points that form an angle in the $\delta $ -neighborhood of $\alpha $ ? An interesting phenomenon is that different angles show different behaviour in the above problems. Apart from the clearly special extreme angles $0$ and $180^\circ $ , the angles $60^\circ , 90^\circ $ and $120^\circ $ also play special role in problem (2): the maximal dimension is smaller for these angles than for the other angles. In problem (1) the angle $90^\circ $ seems to behave differently from other angles.     

Complexity of unconstrained L_2-L_p minimization

We consider the unconstrained $L_q$ - $L_p$ minimization: find a minimizer of $\Vert Ax-b\Vert ^q_q+\lambda \Vert x\Vert ^p_p$ for given $A \in R^{m\times n}$ , $b\in R^m$ and parameters $\lambda >0$ , $p\in [0, 1)$ and $q\ge 1$ . This problem has been studied extensively in many areas. Especially, for the case when $q=2$ , this problem is known as the $L_2-L_p$ minimization problem and has found its applications in variable selection problems and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the $L_q$ - $L_p$ problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function $\Vert \cdot \Vert ^p_p$ . In this paper, we show that the $L_q$ - $L_p$ minimization problem is strongly NP-hard for any $p\in [0,1)$ and $q\ge 1$ , including its smoothed version. On the other hand, we show that, by choosing parameters $(p,\lambda )$ carefully, a minimizer, global or local, will have certain desired sparsity. We believe that these results provide new theoretical insights to the studies and applications of the concave regularized optimization problems.     

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.     

The {\mathcal {A}}-Truncated K-Moment Problem

Let \({\mathcal {A}}\subseteq {\mathbb {N}}^n\) be a finite set, and \(K\subseteq {\mathbb {R}}^n\) be a compact semialgebraic set. An \({\mathcal {A}}\) -truncated multisequence ( \({\mathcal {A}}\) -tms) is a vector \(y=(y_{\alpha })\) indexed by elements in \({\mathcal {A}}\) . The \({\mathcal {A}}\) -truncated \(K\) -moment problem ( \({\mathcal {A}}\) -TKMP) concerns whether or not a given \({\mathcal {A}}\) -tms \(y\) admits a \(K\) -measure \(\mu \) , i.e., \(\mu \) is a nonnegative Borel measure supported in \(K\) such that \(y_\alpha = \int _K x^\alpha \mathtt {d}\mu \) for all \(\alpha \in {\mathcal {A}}\) . This paper proposes a numerical algorithm for solving \({\mathcal {A}}\) -TKMPs. It aims at finding a flat extension of \(y\) by solving a hierarchy of semidefinite relaxations \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \) for a moment optimization problem, whose objective \(R\) is generated in a certain randomized way. If \(y\) admits no \(K\) -measures and \({\mathbb {R}}[x]_{{\mathcal {A}}}\) is \(K\) -full (there exists \(p \in {\mathbb {R}}[x]_{{\mathcal {A}}}\) that is positive on \(K\) ), then \((\mathtt {SDR})_k\) is infeasible for all \(k\) big enough, which gives a certificate for the nonexistence of representing measures. If \(y\) admits a \(K\) -measure, then for almost all generated \(R\) , this algorithm has the following properties: i) we can asymptotically get a flat extension of \(y\) by solving the hierarchy \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \) ; ii) under a general condition that is almost sufficient and necessary, we can get a flat extension of \(y\) by solving \((\mathtt {SDR})_k\) for some \(k\) ; iii) the obtained flat extensions admit a \(r\) -atomic \(K\) -measure with \(r\le |{\mathcal {A}}|\) . The decomposition problems for completely positive matrices and sums of even powers of real linear forms, and the standard truncated \(K\) -moment problems, are special cases of \({\mathcal {A}}\) -TKMPs. They can be solved numerically by this algorithm.     

Optimal mass transport and symmetric representations of their cost functions

We consider Monge–Kantorovich problems corresponding to general cost functions \(c(x,y)\) but with symmetry constraints on a Polish space \(X\times X\) . Such couplings naturally generate anti-symmetric Hamiltonians on \(X\times X\) that are \(c\) -convex with respect to one of the variables. In particular, if \(c\) is differentiable with respect to the first variable on an open subset \(X\) in \( \mathbb {R}^d\) , we show that for every probability measure \(\mu \) on \(X\) , there exists a symmetric probability measure \(\pi _0\) on \(X\times X\) with marginals \(\mu \) , and an anti-symmetric Hamiltonian \(H\) such that \(\nabla _2H(y, x)=\nabla _1c(x,y)\) for \( \pi _0\) -almost all \((x,y) \in X \times X.\) If \(\pi _0\) is supported on a graph \((x, Sx)\) , then \(S\) is necessarily a \(\mu \) -measure preserving involution (i.e., \(S^2=I\) ) and \(\nabla _2H(x, Sx)=\nabla _1c(Sx,x)\) for \(\mu \) -almost all \(x \in X.\) For monotone cost functions such as those given by \(c(x,y)=\langle x, u(y)\rangle \) or \(c(x,y)=-|x-u(y)|^2\) where \(u\) is a monotone operator, \(S\) is necessarily the identity yielding a classical result by Krause, namely that \(u(x)=\nabla _2H(x, x)\) where \(H\) is anti-symmetric and concave-convex.     

Sporadic Reinhardt Polygons

Let $n$ be a positive integer, not a power of two. A Reinhardt polygon is a convex $n$ -gon that is optimal in three different geometric optimization problems: it has maximal perimeter relative to its diameter, maximal width relative to its diameter, and maximal width relative to its perimeter. For almost all $n$ , there are many Reinhardt polygons with $n$ sides, and many of them exhibit a particular periodic structure. While these periodic polygons are well understood, for certain values of $n$ , additional Reinhardt polygons exist, which do not possess this structured form. We call these polygons sporadic. We completely characterize the integers $n$ for which sporadic Reinhardt polygons exist, showing that these polygons occur precisely when $n=pqr$ with $p$ and $q$ distinct odd primes and $r\ge 2$ . We also prove that a positive proportion of the Reinhardt polygons with $n$ sides is sporadic for almost all integers $n$ , and we investigate the precise number of sporadic Reinhardt polygons that are produced for several values of $n$ by a construction that we introduce.     

Coupon collector’s problems with statistical applications to rankings

Some new exact distributions on coupon collector’s waiting time problems are given based on a generalized Pólya urn sampling. In particular, usual Pólya urn sampling generates an exchangeable random sequence. In this case, an alternative derivation of the distribution is also obtained from de Finetti’s theorem. In coupon collector’s waiting time problems with $m$ kinds of coupons, the observed order of $m$ kinds of coupons corresponds to a permutation of $m$ letters uniquely. Using the property of coupon collector’s problems, a statistical model on the permutation group of $m$ letters is proposed for analyzing ranked data. In the model, as the parameters mean the proportion of the $m$ kinds of coupons, the observed ranking can be intuitively understood. Some examples of statistical inference are also given.     

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.     

SIP: critical value functions have finite modulus of non-convexity

We consider semi-infinite programming problems ${{\rm SIP}(z)}$ depending on a finite dimensional parameter ${z \in \mathbb{R}^p}$ . Provided that ${\bar{x}}$ is a strongly stable stationary point of ${{\rm SIP}(\bar{z})}$ , there exists a locally unique and continuous stationary point mapping ${z \mapsto x(z)}$ . This defines the local critical value function ${\varphi(z) := f(x(z); z)}$ , where ${x \mapsto f(x; z)}$ denotes the objective function of ${{\rm SIP}(z)}$ for a given parameter vector ${z\in \mathbb{R}^p}$ . We show that ${\varphi}$ is the sum of a convex function and a smooth function. In particular, this excludes the appearance of negative kinks in the graph of ${\varphi}$ .     

L’espace symétrique de Drinfeld et correspondance de Langlands locale I

We give an upper bound of a Hamiltonian displacement energy of a unit disk cotangent bundle $D^*M$ in a cotangent bundle $T^*M$ , when the base manifold $M$ is an open Riemannian manifold. Our main result is that the displacement energy is not greater than $C r(M)$ , where $r(M)$ is the inner radius of $M$ , and $C$ is a dimensional constant. As an immediate application, we study symplectic embedding problems of unit disk cotangent bundles. Moreover, combined with results in symplectic geometry, our main result shows the existence of short periodic billiard trajectories and short geodesic loops.     

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.     

T-coercivity and continuous Galerkin methods: application to transmission problems with sign changing coefficients

To solve variational indefinite problems, one uses classically the Banach–Ne?as–Babu?ka theory. Here, we study an alternate theory to solve those problems: T-coercivity. Moreover, we prove that one can use this theory to solve the approximate problems, which provides an alternative to the celebrated Fortin lemma. We apply this theory to solve the indefinite problem $\text{ div}\sigma \nabla u=f$ set in $H^1_0$ , with $\sigma $ exhibiting a sign change.     

Minimal subgroups and the structure of finite groups

A subgroup $H$ of a finite group $G$ is weakly-supplemented in $G$ if there exists a proper subgroup $K$ of $G$ such that $G=HK$ . In this paper we prove that a finite group $G$ is $p$ -nilpotent if every minimal subgroup of $P\bigcap G^{N}$ is weakly-supplemented in $G$ , and when $p=2$ either every cyclic subgroup of $P\bigcap G^{N}$ with order 4 is weakly-supplemented in $G$ or $P$ is quaternion-free, where $p$ is the smallest prime number dividing the order of $G$ , $P$ a sylow $p$ -subgroup of $G$ .     

On Topological Changes in the Delaunay Triangulation of Moving Points

Let $P$ P be a collection of $n$ n points moving along pseudo-algebraic trajectories in the plane. (So, in particular, there are constants $s,c>0$ s , c > 0 such that any four points are co-circular at most $s$ s times, and any three points are collinear at most $c$ c times.) One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a sub-cubic bound, on the maximum number of discrete changes that the Delaunay triangulation ${\mathrm{DT}}(P)$ DT ( P ) of $P$ P experiences during the motion of the points of $P$ P . In this paper, we obtain an upper bound of $O(n^{2+{\varepsilon }})$ O ( n 2 + ε ) , for any ${\varepsilon }>0$ ε > 0 , under the assumptions that (i) any four points can be co-circular at most twice and (ii) either no triple of points can be collinear more than twice or no ordered triple of points can be collinear more than once.     

Approximate Hermitian–Einstein connections on principal bundles over a compact Riemann surface

Let $X$ be a compact connected Riemann surface and $G$ a connected reductive complex affine algebraic group. Given a holomorphic principal $G$ -bundle $E_G$ over $X$ , we construct a $C^\infty $ Hermitian structure on $E_G$ together with a $1$ -parameter family of $C^\infty $ automorphisms $\{F_t\}_{t\in \mathbb R }$ of the principal $G$ -bundle $E_G$ with the following property: Let $\nabla ^t$ be the connection on $E_G$ corresponding to the Hermitian structure and the new holomorphic structure on $E_G$ constructed using $F_t$ from the original holomorphic structure. As $t\rightarrow -\infty $ , the connection $\nabla ^t$ converges in $C^\infty $ Fréchet topology to the connection on $E_G$ given by the Hermitian–Einstein connection on the polystable principal bundle associated to $E_G$ . In particular, as $t\rightarrow -\infty $ , the curvature of $\nabla ^t$ converges in $C^\infty $ Fréchet topology to the curvature of the connection on $E_G$ given by the Hermitian–Einstein connection on the polystable principal bundle associated to $E_G$ . The family $\{F_t\}_{t\in \mathbb R }$ is constructed by generalizing the method of [6]. Given a holomorphic vector bundle $E$ on $X$ , in [6] a $1$ -parameter family of $C^\infty $ automorphisms of $E$ is constructed such that as $t\rightarrow -\infty $ , the curvature converges, in $C^0$ topology, to the curvature of the Hermitian–Einstein connection of the associated graded bundle.     

Weak Fenchel and weak Fenchel-Lagrange conjugate duality for nonconvex scalar optimization problems

In this work, by using weak conjugate maps given in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), weak Fenchel conjugate dual problem, ${(D_F^w)}$ , and weak Fenchel Lagrange conjugate dual problem ${(D_{FL}^w)}$ are constructed. Necessary and sufficient conditions for strong duality for the ${(D_F^w)}$ , ${(D_{FL}^w)}$ and primal problem are given. Furthermore, relations among the optimal objective values of dual problem constructed by using Augmented Lagrangian in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), ${(D_F^w)}$ , ${(D_{FL}^w)}$ dual problems and primal problem are examined. Lastly, necessary and sufficient optimality conditions for the primal and the dual problems ${(D_F^w)}$ and ${(D_{FL}^w)}$ are established.