Search

This paper investigates multidimensional extended type-I BSVIEs and infinite families of BSDEs in the case of quadratic generators. We establish existence and uniqueness results in the case of fully quadratic as well as Lipschitz-quadratic quadratic generators. We also present and discuss a type of flow property satisfied by this family of BSVIEs. As a preliminary step, we establish the well-posedness of a class of infinite families of BSDEs, as introduced in Hern{\aa}ndez and Possama\"i [20], which are of interest in their own right. Our approach relies on the strategy developed by Tevsadze [49] for quadratic BSDEs and the treatment of Lipschitz extended type-I BSVIEs in [20]. We motivate their analysis of both of these objects by a series of practical applications.

We consider a nonlinear differential equation under the combined influence of small state-dependent Brownian perturbations of size $\varepsilon$, and fast periodic sampling with period $\delta$; $0, Comment: 37 pages, 4 figures

We introduce an extension to local principal component analysis for learning symmetric manifolds. In particular, we use a spectral method to approximate the Lie algebra corresponding to the symmetry group of the underlying manifold. We derive the sample complexity of our method for a variety of manifolds before applying it to various data sets for improved density estimation.

We prove that solution operators of elliptic obstacle-type variational inequalities (or, more generally, locally Lipschitz continuous functions possessing certain pointwise-a.e. convexity properties) are Newton differentiable when considered as maps between suitable Lebesgue spaces and equipped with the strong-weak Bouligand differential as a generalized set-valued derivative. It is shown that this Newton differentiability allows to solve optimal control problems with H1-cost terms and one-sided pointwise control constraints by means of a semismooth Newton method. The superlinear convergence of the resulting algorithm is proved in the infinite-dimensional setting and its mesh independence is demonstrated in numerical experiments. We expect that the findings of this paper are also helpful for the design of numerical solution procedures for quasi-variational inequalities and the optimal control of obstacle-type variational problems., Comment: Minor revisions. Published in SIAM Journal on Control and Optimization, Vol. 61, Iss. 3 (2023)

In this work we consider stochastic gradient descent (SGD) for solving linear inverse problems in Banach spaces. SGD and its variants have been established as one of the most successful optimisation methods in machine learning, imaging and signal processing, etc. At each iteration SGD uses a single datum, or a small subset of data, resulting in highly scalable methods that are very attractive for large-scale inverse problems. Nonetheless, the theoretical analysis of SGD-based approaches for inverse problems has thus far been largely limited to Euclidean and Hilbert spaces. In this work we present a novel convergence analysis of SGD for linear inverse problems in general Banach spaces: we show the almost sure convergence of the iterates to the minimum norm solution and establish the regularising property for suitable a priori stopping criteria. Numerical results are also presented to illustrate features of the approach.

In this paper, we study optimal control problems of semilinear elliptic and parabolic equations. A tracking cost functional, quadratic in the control and state variables, is considered. No control constraints are imposed. We prove that the corresponding state equations are well posed for controls in L2. However, it is well known that in the L2 framework the mappings involved in the control problem are not Frechet differentiable in general, which makes any analysis of the optimality conditions challenging. Nevertheless, we prove that every L2 optimal control belongs to L∞, and consequently standard optimality conditions are available. The first author was supported by MCIN/AEI/10.13039/501100011033 under research project PID2020-114837GB-I00. The second author was partially supported by the German Research Foundation (DFG) under project grant Wa 3626/3-2.

Convex nonsmooth optimization problems, whose solutions live in very high dimensional spaces, have become ubiquitous. To solve them, the class of first-order algorithms known as proximal splitting algorithms is particularly adequate: they consist of simple operations, handling the terms in the objective function separately. In this overview, we demystify a selection of recent proximal splitting algorithms: we present them within a unified framework, which consists in applying splitting methods for monotone inclusions in primal-dual product spaces, with well-chosen metrics. Along the way, we easily derive new variants of the algorithms and revisit existing convergence results, extending the parameter ranges in several cases. In particular, we emphasize that when the smooth term in the objective function is quadratic, e.g., for least-squares problems, convergence is guaranteed with larger values of the relaxation parameter than previously known. Such larger values are usually beneficial for the convergence speed in practice., To appear in SIAM Review

It is known that the generalized Nash equilibrium problem can be reformulated as a quasivariational inequality. Our aim in this work is to introduce a variational approach to study the existence of solutions for generalized ordinal Nash games, that is, generalized games where the player preferences are binary relations that do not necessarily admit a utility representation., Comment: 7 pages

We introduce a new form of Lagrangian and propose a simple first-order algorithm for nonconvex optimization with nonlinear equality constraints. We show the algorithm generates bounded dual iterates, and establish the convergence to KKT points under standard assumptions. The key features of the method are: (i) it does not require boundedness assumptions on the iterates and the set of multipliers; (ii) it is a single-loop algorithm that does not involve any penalty subproblems., Accepted at Operations Research Letters

When an iterative method is applied to solve the linear equation system in interior point methods (IPMs), the attention is usually placed on accelerating their convergence by designing appropriate preconditioners, but the linear solver is applied as a black box with a standard termination criterion which asks for a sufficient reduction of the residual in the linear system. Such an approach often leads to an unnecessary 'oversolving' of linear equations. In this paper, an IPM that relies on an inner termination criterion not based on the residual of the linear system is introduced and analyzed. Moreover, new indicators for the early termination of the inner iterations are derived from a deep understanding of IPM needs. The new technique has been adapted to the Conjugate Gradient (CG) and to the Minimum Residual method (MINRES) applied in the IPM context. The new criterion has been tested on a set of quadratic optimization problems including compressed sensing, image processing and instances with partial differential equation constraints, and it has been compared to standard residual tests with variable tolerance. Evidence gathered from these computational experiments shows that the new technique delivers significant improvements in terms of inner (linear) iterations and those translate into significant savings of the IPM solution time.

Optimal control problem is typically solved by first finding the value function through Hamilton-Jacobi equation (HJE) and then taking the minimizer of the Hamiltonian to obtain the control. In this work, instead of focusing on the value function, we propose a new formulation for the gradient of the value function (value-gradient) as a decoupled system of partial differential equations in the context of continuous-time deterministic discounted optimal control problem. We develop an efficient iterative scheme for this system of equations in parallel by utilizing the properties that they share the same characteristic curves as the HJE for the value function. For the theoretical part, we prove that this iterative scheme converges linearly in $L_\alpha^2$ sense for some suitable exponent $\alpha$ in a weight function. For the numerical method, we combine characteristic line method with machine learning techniques. Specifically, we generate multiple characteristic curves at each policy iteration from an ensemble of initial states, and compute both the value function and its gradient simultaneously on each curve as the labelled data. Then supervised machine learning is applied to minimize the weighted squared loss for both the value function and its gradients. Experimental results demonstrate that this new method not only significantly increases the accuracy but also improves the efficiency and robustness of the numerical estimates, particularly with less amount of characteristics data or fewer training steps.

Given a parameter dependent fixed point equation $x = F(x,u)$, we derive an abstract compactness principle for the fixed point map $u \mapsto x^*(u)$ under the assumptions that (i) the fixed point equation can be solved by the contraction principle and (ii) the map $u \mapsto F(x,u)$ is compact for fixed $x$. This result is applied to infinite-dimensional, semi-linear control systems and their reachable sets. More precisely, we extend a non-controllability result of Ball, Marsden, and Slemrod [1] to semi-linear systems. First we consider $L^p$-controls, $p>1$. Subsequently we analyze the case $p=1$.

In this paper, we consider stochastic optimal control of systems driven by stochastic differential equations with irregular drift coefficient. We establish a necessary and sufficient stochastic maximum principle. To achieve this, we first derive an explicit representation of the first variation process (in the Sobolev sense) of the controlled diffusion. Since the drift coefficient is not smooth, the representation is given in terms of the local time of the state process. Then we construct a sequence of optimal control problems with smooth coefficients by an approximation argument. Finally, we use Ekeland’s variational principle to obtain an approximating adjoint process from which we derive the maximum principle by passing to the limit. The work is notably motivated by the optimal consumption problem of investors paying wealth tax.

In this article, we consider the motion planning of a rigid object on the unit sphere with a unit speed. The motion of the object is constrained by the maximum absolute value, $U_{max}$ of geodesic curvature of its path; this constrains the object to change the heading at the fastest rate only when traveling on a tight smaller circular arc of radius $r \frac{1}{2}$, while paths of the above type may cease to exist depending on the boundary conditions and the value of $r$, optimal paths may be concatenations of more than three circular arcs.

Necessary conditions for asymptotic stability and stabilizability of subsets for dynamical and control systems are obtained. The main necessary condition is homotopical and is in turn used to obtain a homological one. A certain extension is ruled out. Questions are posed., Comment: Accepted to SIAM J Control and Optimization

In this paper, we propose a variance-reduced primal-dual algorithm with Bregman distance for solving convex-concave saddle-point problems with finite-sum structure and nonbilinear coupling function. This type of problems typically arises in machine learning and game theory. Based on some standard assumptions, the algorithm is proved to converge with oracle complexity of $O\left(\frac{\sqrt n}{\epsilon}\right)$ and $O\left(\frac{n}{\sqrt \epsilon}+\frac{1}{\epsilon^{1.5}}\right)$ using constant and non-constant parameters, respectively where $n$ is the number of function components. Compared with existing methods, our framework yields a significant improvement over the number of required primal-dual gradient samples to achieve $\epsilon$-accuracy of the primal-dual gap. We tested our method for solving a distributionally robust optimization problem to show the effectiveness of the algorithm.

In this paper we prove Morse index theorems for a big class of constrained variational problems on graphs. Such theorems are useful in various physical and geometric applications. Our formulas compute the difference of Morse indices of two Hessians related to two different graphs or two different sets of boundary conditions. Several applications such as the iteration formulas or lower bounds for the index are proved., 30 pages, 4 figures

A hyperbolicity cone is said to be rank-one generated (ROG) if all its extreme rays have rank one, where the rank is computed with respect to the underlying hyperbolic polynomial. This is a natural class of hyperbolicity cones which are strictly more general than the ROG spectrahedral cones. In this work, we present a study of the automorphisms of ROG hyperbolicity cones and their derivative relaxations. One of our main results states that the automorphisms of the derivative relaxations are exactly the automorphisms of the original cone fixing a certain direction. As an application, we completely determine the automorphisms of the derivative relaxations of the nonnegative orthant and of the cone of positive semidefinite matrices. More generally, we also prove relations between the automorphisms of a spectral cone and the underlying permutation-invariant set, which might be of independent interest., Comment: 25 pages. Some minor fixes and changes. To appear at the SIAM Journal on Applied Algebra and Geometry

We consider the problem of computing the \emph{distance-based representative skyline} in the plane, a problem introduced by Tao, Ding, Lin and Pei [Proc. 25th IEEE International Conference on Data Engineering (ICDE), 2009] and independently considered by Dupin, Nielsen and Talbi [Optimization and Learning - Third International Conference, OLA 2020] in the context of multi-objective optimization. Given a set $P$ of $n$ points in the plane and a parameter $k$, the task is to select $k$ points of the skyline defined by $P$ (also known as Pareto front for $P$) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in $O(n\log h)$ time, where $h$ is the number of points in the skyline of $P$. We also show that the decision problem can be solved in $O(n\log k)$ time and the optimization problem can be solved in $O(n \log k + n \operatorname{loglog} n)$ time. This improves previous algorithms and is optimal for a large range of values of $k$., 25 pages

Based on a degenerate proximal point analysis, we show that the Douglas-Rachford splitting can be reduced to a well-defined resolvent, but generally fails to be a proximal mapping. This extends the recent result of [Bauschke, Schaad and Wang. Math. Program., 168 (2018), pp. 55-61] to more general setting. The related concepts and consequences are also discussed. In particular, the results regarding the maximal and cyclic monotonicity are instrumental for analyzing many operator splitting algorithms., 9 pages

In this paper, we consider an optimal reinsurance problem to minimize the probability of drawdown for the scaled Cram\'er-Lundberg risk model when the reinsurance premium is computed according to the mean-variance premium principle. We extend the work of Liang et al. [16] to the case of minimizing the probability of drawdown. By using the comparison method and the tool of adjustment coefficients, we show that the minimum probability of drawdown for the scaled classical risk model converges to the minimum probability for its diffusion approximation, and the rate of convergence is of order $O(n^{-1/2})$. We further show that using the optimal strategy from the diffusion approximation in the scaled classical risk model is $O(n^{-1/2})$-optimal.

In increasingly different contexts, it happens that a human player has to interact with artificial players who make decisions following decision-making algorithms. How should the human player play against these algorithms to maximize his utility? Does anything change if he faces one or more artificial players? The main goal of the paper is to answer these two questions. Consider n-player games in normal form repeated over time, where we call the human player optimizer, and the (n -- 1) artificial players, learners. We assume that learners play no-regret algorithms, a class of algorithms widely used in online learning and decision-making. In these games, we consider the concept of Stackelberg equilibrium. In a recent paper, Deng, Schneider, and Sivan have shown that in a 2-player game the optimizer can always guarantee an expected cumulative utility of at least the Stackelberg value per round. In our first result, we show, with counterexamples, that this result is no longer true if the optimizer has to face more than one player. Therefore, we generalize the definition of Stackelberg equilibrium introducing the concept of correlated Stackelberg equilibrium. Finally, in the main result, we prove that the optimizer can guarantee at least the correlated Stackelberg value per round. Moreover, using a version of the strong law of large numbers, we show that our result is also true almost surely for the optimizer utility instead of the optimizer's expected utility.

We consider transferable utility cooperative games with infinitely many players and the core understood in the space of bounded additive set functions. We show that, if a game is bounded below, then its core is non-empty if and only if the game is balanced. This finding is a generalization of Schmeidler's (1967) original result ``On Balanced Games with Infinitely Many Players'', where the game is assumed to be non-negative. We furthermore demonstrate that, if a game is not bounded below, then its core might be empty even though the game is balanced; that is, our result is tight. We also generalize Schmeidler's (1967) result to the case of restricted cooperation too.

For decision making under uncertainty, min-max regret has been established as a popular methodology to find robust solutions. In this approach, we compare the performance of our solution against the best possible performance had we known the true scenario in advance. We introduce a generalization of this setting which allows us to compare against solutions that are also affected by uncertainty, which we call balanced regret. Using budgeted uncertainty sets, this allows for a wider range of possible alternatives the decision maker may choose from. We analyze this approach for general combinatorial problems, providing an iterative solution method and insights into solution properties. We then consider a type of selection problem in more detail and show that, while the classic regret setting with budgeted uncertainty sets can be solved in polynomial time, the balanced regret problem becomes NP-hard. In computational experiments using random and real-world data, we show that balanced regret solutions provide a useful trade-off for the performance in classic performance measures.

We study the problem of maximizing the probability that (i) an electric component or financial institution $X$ does not default before another component or institution $Y$ and (ii) that $X$ and $Y$ default jointly within the class of all random variables $X,Y$ with given univariate continuous distribution functions $F$ and $G$, respectively, and show that the maximization problems correspond to finding copulas maximizing the mass of the endograph $\Gamma^\leq(T)$ and the graph $\Gamma(T)$ of $T=G \circ F^-$, respectively. After providing simple, copula-based proofs for the existence of copulas attaining the two maxima $\overline{m}_T$ and $\overline{w}_T$ we generalize the obtained results to the case of general (not necessarily monotonic) transformations $T:[0,1] \rightarrow [0,1]$ and derive simple and easily calculable formulas for $\overline{m}_T$ and $\overline{w}_T$ involving the distribution function $F_T$ of $T$ (interpreted as random variable on $[0,1]$). The latter are then used to charac\-terize all non-decreasing transformations $T:[0,1] \rightarrow [0,1]$ for which $\overline{m}_T$ and $\overline{w}_T$ coincide. A strongly consistent estimator for the maximum probability that $X$ does not default before $Y$ is derived and proven to be asymptotically normal under very mild regularity conditions. Several examples and graphics illustrate the main results and falsify some seemingly natural conjectures., Comment: 27 pages, 4 figures

This paper proposes and analyzes an accelerated inexact dampened augmented Lagrangian (AIDAL) method for solving linearly-constrained nonconvex composite optimization problems. Each iteration of the AIDAL method consists of: (i) inexactly solving a dampened proximal augmented Lagrangian (AL) subproblem by calling an accelerated composite gradient (ACG) subroutine; (ii) applying a dampened and under-relaxed Lagrange multiplier update; and (iii) using a novel test to check whether the penalty parameter of the AL function should be increased. Under several mild assumptions involving the dampening factor and the under-relaxation constant, it is shown that the AIDAL method generates an approximate stationary point of the constrained problem in ${\cal O}(\varepsilon^{-5/2}\log\varepsilon^{-1})$ iterations of the ACG subroutine, for a given tolerance $\varepsilon>0$. Numerical experiments are also given to show the computational efficiency of the proposed method.

The decision making and management of many engineering networks involves multiple parties with conflicting interests, while each party is constituted with multiple agents. Such problems can be casted as a multi-cluster game. Each cluster is treated as a self-interested player in a non-cooperative game where agents in the same cluster cooperate together to optimize the payoff function of the cluster. In a large-scale network, the information of agents in a cluster can not be available immediately for agents beyond this cluster, which raise challenges to the existing Nash equilibrium seeking algorithms. Hence, we consider a partial-decision information scenario in generalized Nash equilibrium seeking for multi-cluster games in a distributed manner. We reformulate the problem as finding zeros of the sum of preconditioned monotone operators by the primal-dual analysis and graph Laplacian matrix. Then a distributed generalized Nash equilibrium seeking algorithm is proposed without requiring fully awareness of its opponent clusters' decisions based on a forward-backward-forward method. With the algorithm, each agent estimates the strategies of all the other clusters by communicating with neighbors via an undirected network. We show that the derived operators can be monotone when the communication strength parameter is sufficiently large. We prove the algorithm convergence resorting to the fixed point theory by providing a sufficient condition. We discuss its potential application in Energy Internet with numerical studies.

We introduce a class of specially structured linear programming (LP) problems, which has favorable modeling capability for important application problems in different areas such as optimal transport, discrete tomography and economics. To solve these generally large-scale LP problems efficiently, we design an implementable inexact entropic proximal point algorithm (iEPPA) combined with an easy-to-implement dual block coordinate descent method as a subsolver. Unlike existing entropy-type proximal point algorithms, our iEPPA employs a more practically checkable stopping condition for solving the associated subproblems while achieving provable convergence. Moreover, when solving the capacity constrained multi-marginal optimal transport (CMOT) problem (a special case of our LP problem), our iEPPA is able to bypass the underlying numerical instability issues that often appear in the popular entropic regularization approach, since our algorithm does not require the proximal parameter to be very small in order to obtain an accurate approximate solution. Numerous numerical experiments show that our iEPPA is efficient and robust for solving large-scale CMOT problems. The experiments on the discrete tomography problem also highlight the potential modeling power of our model., 28 pages, 6 figures

The paper is concerned with a zero-sum Stackelberg stochastic linear-quadratic (LQ, for short) differential game over finite horizons. Under a fairly weak condition, the Stackelberg equilibrium is explicitly obtained by first solving a forward stochastic LQ optimal control problem (SLQ problem, for short) and then a backward SLQ problem. Two Riccati equations are derived in constructing the Stackelberg equilibrium. An interesting finding is that the difference of these two Riccati equations coincides with the Riccati equation associated with the zero-sum Nash stochastic LQ differential game, which implies that the Stackelberg equilibrium and the Nash equilibrium are actually identical. Consequently, the Stackelberg equilibrium admits a linear state feedback representation, and the Nash game can be solved in a leader-follower manner.

We study non-autonomous observation systems \begin{align*} \dot{x}(t) = A(t) x(t),\quad y(t) = C(t) x(t),\quad x(0) = x_0\in X, \end{align*} where $(A(t))$ is a strongly measurable family of closed operators on a Banach space $X$ and $(C(t))$ is a family of bounded observation operators from $X$ to a Banach space $Y$. Based on an abstract uncertainty principle and a dissipation estimate, we prove that the observation system satisfies a final-state observability estimate in $\mathrm{L}^r(E; Y)$ for measurable subsets $E \subseteq [0,T], T > 0$. We present applications of the above result to families $(A(t))$ of uniformly strongly elliptic differential operators as well as non-autonomous Ornstein-Uhlenbeck operators $P(t)$ on $\mathrm{L}^p(\mathbb{R}^d)$ with observation operators $C(t)u = u|_{\Omega(t)}$. In the setting of non-autonomous strongly elliptic operators, we derive necessary and sufficient geometric conditions on the family of sets $(\Omega(t))$ such that the corresponding observation system satisfies a final-state observability estimate., Comment: minor corrections

According to the structural balance theory, a signed graph is considered structurally balanced when it can be partitioned into a number of modules such that positive and negative edges are respectively located inside and between the modules. In practice, real-world networks are rarely structurally balanced, though. In this case, one may want to measure the magnitude of their imbalance, and to identify the set of edges causing this imbalance. The correlation clustering (CC) problem precisely consists in looking for the signed graph partition having the least imbalance. Recently, it has been shown that the space of the optimal solutions of the CC problem can be constituted of numerous and diverse optimal solutions. Yet, this space is difficult to explore, as the CC problem is NP-hard, and exact approaches do not scale well even when looking for a single optimal solution. To alleviate this issue, in this work we propose an efficient enumeration method allowing to retrieve the complete space of optimal solutions of the CC problem. It combines an exhaustive enumeration strategy with neighborhoods of varying sizes, to achieve computational effectiveness. Results obtained for middle-sized networks confirm the usefulness of our method.

The objective of this paper is to analyze the existence of equilibria for a class of deterministic mean field games of controls. The interaction between players is due to both a congestion term and a price function which depends on the distributions of the optimal strategies. Moreover, final state and mixed state-control constraints are considered, the dynamics being nonlinear and affine with respect to the control. The existence of equilibria is obtained by Kakutani's theorem, applied to a fixed point formulation of the problem. Finally, uniqueness results are shown under monotonicity assumptions.

Two-stage stochastic mixed-integer programming (SMIP) problems with general integer variables in the second-stage are generally difficult to solve. This paper develops the theory of integer set reduction for characterizing the subset of the convex hull of feasible integer points of the second-stage subproblem which can be used for solving the SMIP. The basic idea is to consider a small enough subset of feasible integer points that is necessary for generating a valid inequality for the integer subproblem. An algorithm for obtaining such a subset based on the solution of the subproblem LP-relaxation is then devised and incorporated into the Fenchel decomposition method for SMIP. To demonstrate the performance of the new integer set reduction methodology, a computational study based on randomly generated test instances was performed. The results of the study show that integer set reduction provides significant gains in terms of generating cuts faster leading to better bounds in solving SMIPs than using a direct solver., Comment: 28 pages, 5 figures

We present the concept of a Generalized Feedback Nash Equilibrium (GFNE) in dynamic games, extending the Feedback Nash Equilibrium concept to games in which players are subject to state and input constraints. We formalize necessary and sufficient conditions for (local) GFNE solutions at the trajectory level, which enable the development of efficient numerical methods for their computation. Specifically, we propose a Newton-style method for finding game trajectories which satisfy necessary conditions for an equilibrium, which can then be checked against sufficiency conditions. We show that the evaluation of the necessary conditions in general requires computing a series of nested, implicitly-defined derivatives, which quickly becomes intractable. To this end, we introduce an approximation to the necessary conditions which is amenable to efficient evaluation, and in turn, computation of solutions. We term the solutions to the approximate necessary conditions Generalized Feedback Quasi-Nash Equilibria (GFQNE), and we introduce numerical methods for their computation. In particular, we develop a Sequential Linear-Quadratic Game approach, in which a LQ local approximation of the game is solved at each iteration. The development of this method relies on the ability to compute a GFNE to inequality- and equality-constrained LQ games, and therefore specific methods for the solution of these special cases are developed in detail. We demonstrate the effectiveness of the proposed solution approach on a dynamic game arising in an autonomous driving application.

This paper presents a computational approach for finding the optimal shapes of peristaltic pumps transporting rigid particles in Stokes flow. In particular, we consider shapes that minimize the rate of energy dissipation while pumping a prescribed volume of fluid, number of particles and/or distance traversed by the particles over a set time period. Our approach relies on a recently developed fast and accurate boundary integral solver for simulating multiphase flows through periodic geometries of arbitrary shapes. In order to fully capitalize on the dimensionality reduction feature of the boundary integral methods, shape sensitivities must ideally involve evaluating the physical variables on the particle or pump boundaries only. We show that this can indeed be accomplished owing to the linearity of Stokes flow. The forward problem solves for the particle motion in a slip-driven pipe flow while the adjoint problems in our construction solve quasi-static Dirichlet boundary value problems backwards in time, retracing the particle evolution. The shape sensitivities simply depend on the solution of one forward and one adjoint (for each shape functional) problems. We validate these analytic shape derivative formulas by comparing against finite-difference based gradients and present several examples showcasing optimal pump shapes under various constraints., Comment: 24 pages, 8 figures

The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension K, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures.

In this paper, a necessary and sufficient condition for the controllability of networked systems with heterogeneous dynamics is established where the nodes are higher dimensional linear time invariant systems and the network topology is directed and weighted. The controllability of networked system over some specific topologies are also examined and some non-controllability results are obtained. The theoretical results are demonstrated with examples.

Random feature methods have been successful in various machine learning tasks, are easy to compute, and come with theoretical accuracy bounds. They serve as an alternative approach to standard neural networks since they can represent similar function spaces without a costly training phase. However, for accuracy, random feature methods require more measurements than trainable parameters, limiting their use for data-scarce applications or problems in scientific machine learning. This paper introduces the sparse random feature expansion to obtain parsimonious random feature models. Specifically, we leverage ideas from compressive sensing to generate random feature expansions with theoretical guarantees even in the data-scarce setting. In particular, we provide generalization bounds for functions in a certain class (that is dense in a reproducing kernel Hilbert space) depending on the number of samples and the distribution of features. The generalization bounds improve with additional structural conditions, such as coordinate sparsity, compact clusters of the spectrum, or rapid spectral decay. In particular, by introducing sparse features, i.e. features with random sparse weights, we provide improved bounds for low order functions. We show that the sparse random feature expansions outperforms shallow networks in several scientific machine learning tasks.

We propose a new inexact column-and-constraint generation (i-C&CG) method to solve two-stage robust optimization problems. The method allows solutions to the master problems to be inexact, which is desirable when solving large-scale and/or challenging problems. It is equipped with a backtracking routine that controls the trade-off between bound improvement and inexactness. Importantly, this routine allows us to derive theoretical finite convergence guarantees for our i-C&CG method. Numerical experiments demonstrate computational advantages of our i-C&CG method over state-of-the-art column-and-constraint generation methods.

Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization is NP-hard. In this paper, we study the cardinality constrained multilinear set in the special case when the number of monomials is exactly two. We give an extended formulation, with two more auxiliary variables and exponentially many inequalities, of the convex hull of solutions of the standard linearization of this problem. We also show that the separation problem can be solved efficiently.

The main purpose of this article is to prove a logarithmic convexity estimate for the solution of a linear heat equation subject to dynamic boundary conditions in a bounded convex domain. As an application, we prove the impulsive null approximate controllability for an impulsive heat equation with dynamic boundary conditions.

In the paper, we study a class of useful minimax problems on Riemanian manifolds and propose a class of effective Riemanian gradient-based methods to solve these minimax problems. Specifically, we propose an effective Riemannian gradient descent ascent (RGDA) algorithm for the deterministic minimax optimization. Moreover, we prove that our RGDA has a sample complexity of $O(\kappa^2\epsilon^{-2})$ for finding an $\epsilon$-stationary solution of the Geodesically-Nonconvex Strongly-Concave (GNSC) minimax problems, where $\kappa$ denotes the condition number. At the same time, we present an effective Riemannian stochastic gradient descent ascent (RSGDA) algorithm for the stochastic minimax optimization, which has a sample complexity of $O(\kappa^4\epsilon^{-4})$ for finding an $\epsilon$-stationary solution. To further reduce the sample complexity, we propose an accelerated Riemannian stochastic gradient descent ascent (Acc-RSGDA) algorithm based on the momentum-based variance-reduced technique. We prove that our Acc-RSGDA algorithm achieves a lower sample complexity of $\tilde{O}(\kappa^{4}\epsilon^{-3})$ in searching for an $\epsilon$-stationary solution of the GNSC minimax problems. Extensive experimental results on the robust distributional optimization and robust Deep Neural Networks (DNNs) training over Stiefel manifold demonstrate efficiency of our algorithms., Comment: This paper was accepted to IEEE Transactions on Pattern Analysis and Machine Intelligence

This paper studies a variational obstacle avoidance problem on complete Riemannian manifolds. That is, we minimize an action functional, among a set of admissible curves, which depends on an artificial potential function used to avoid obstacles. In particular, we generalize the theory of bi-Jacobi fields and biconjugate points and present necessary and sufficient conditions for optimality. Local minimizers of the action functional are divided into two categories and subsequently classified, with local uniqueness results obtained in both cases., 11 pages

In recent years, a variety of gradient-based methods have been developed to solve Bi-Level Optimization (BLO) problems in machine learning and computer vision areas. However, the theoretical correctness and practical effectiveness of these existing approaches always rely on some restrictive conditions (e.g., Lower-Level Singleton, LLS), which could hardly be satisfied in real-world applications. Moreover, previous literature only proves theoretical results based on their specific iteration strategies, thus lack a general recipe to uniformly analyze the convergence behaviors of different gradient-based BLOs. In this work, we formulate BLOs from an optimistic bi-level viewpoint and establish a new gradient-based algorithmic framework, named Bi-level Descent Aggregation (BDA), to partially address the above issues. Specifically, BDA provides a modularized structure to hierarchically aggregate both the upper- and lower-level subproblems to generate our bi-level iterative dynamics. Theoretically, we establish a general convergence analysis template and derive a new proof recipe to investigate the essential theoretical properties of gradient-based BLO methods. Furthermore, this work systematically explores the convergence behavior of BDA in different optimization scenarios, i.e., considering various solution qualities (i.e., global/local/stationary solution) returned from solving approximation subproblems. Extensive experiments justify our theoretical results and demonstrate the superiority of the proposed algorithm for hyper-parameter optimization and meta-learning tasks. Source code is available at https://github.com/vis-opt-group/BDA., 18 pages, accepted for publication in IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)

This contribution features an accelerated computation of the Sinkhorn's algorithm, which approximates the Wasserstein transportation distance, by employing nonequispaced fast Fourier transforms (NFFT). The algorithm proposed allows approximations of the Wasserstein distance by involving not more than $\mathcal O(n\log n)$ operations for probability measures supported by~$n$ points. Furthermore, the proposed method avoids expensive allocations of the characterizing matrices. With this numerical acceleration, the transportation distance is accessible to probability measures out of reach so far. Numerical experiments using synthetic and real data affirm the computational advantage and superiority., Comment: 32 pages, 6 figures

In this paper, we study the null controllability of a nonlinear age, space and two-sex structured population dynamics model. This model is such that the nonlinearity and the couplage are at birth level. We consider a population with males and females and we are dealing with two cases of null controllability problems. The first problem is related to the total extinction, which means that, we estimate a time \begin{document}$ T $\end{document} to bring the male and female subpopulation density to zero. The second case concerns null controllability of male or female subpopulation. Since the absence of males or females in the population stops births; so, if we have the total extinction of the females at time \begin{document}$ T, $\end{document} and if \begin{document}$ A $\end{document} is the life span of the individuals, at time \begin{document}$ T+A $\end{document} one will get certainly the total extinction of the population. Our method uses first an observability inequality related to the adjoint of an auxiliary system, a null controllability of the linear auxiliary system, and after the Schauder's fixed point theorem.

In the context of structured nonconvex optimization, we estimate the increase in minimum value for a decision that is robust to parameter perturbations as compared to the value of a nominal problem. The estimates rely on detailed expressions for subgradients and local Lipschitz moduli of min-value functions in nonconvex robust optimization and require only the solution of the nominal problem. The theoretical results are illustrated by examples from military operations research involving mixed-integer optimization models. Across 54 cases examined, the median error in estimating the increase in minimum value is 12%. Therefore, the derived expressions for subgradients and local Lipschitz moduli may accurately inform analysts about the possibility of obtaining cost-effective, parameter-robust decisions in nonconvex optimization.

We investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is formulated as the rank minimization of a nonlinear feature map applied to the original matrix, which is then further approximated by a constrained non-convex optimization problem involving the Grassmann manifold. We propose two sets of algorithms, one arising from Riemannian optimization and the other as an alternating minimization scheme, both of which include first- and second-order variants. Both sets of algorithms have theoretical guarantees. In particular, for the alternating minimization, we establish global convergence and worst-case complexity bounds. Additionally, using the Kurdyka-Lojasiewicz property, we show that the alternating minimization converges to a unique limit point. We provide extensive numerical results for the recovery of union of subspaces and clustering under entry sampling and dense Gaussian sampling. Our methods are competitive with existing approaches and, in particular, high accuracy is achieved in the recovery using Riemannian second-order methods., Comment: Fixed some typos in version 2

We aim to compute lifted stationary points of a sparse optimization problem (P0) with complementarity constraints. We define a continuous relaxation problem (Rv) that has the same global minimizers and optimal value with problem (P0). Problem (Rv) is a mathematical program with complementarity constraints (MPCC) and a difference-of-convex (DC) objective function. We define MPCC lifted-stationarity of (Rv) and show that it is weaker than directional stationarity, but stronger than Clarke stationarity for local optimality. Moreover, we propose an approximation method to solve (Rv) and an augmented Lagrangian method to solve its subproblem, which relaxes the equality constraint in (Rv) with a tolerance. We prove the convergence of our algorithm to an MPCC lifted-stationary point of problem (Rv) and use a sparse optimization problem with vertical linear complementarity constraints to demonstrate the efficiency of our algorithm on finding sparse solutions in practice., Comment: 29 pages, 3 figures

We introduce a twice differentiable augmented Lagrangian for nonlinear optimization with general inequality constraints and show that a strict local minimizer of the original problem is an approximate strict local solution of the augmented Lagrangian. A novel augmented Lagrangian method of multipliers (ALM) is then presented. Our method is originated from a generalization of the Hetenes-Powell augmented Lagrangian, and is a combination of the augmented Lagrangian and the interior-point technique. It shares a similar algorithmic framework with existing ALMs for optimization with inequality constraints, but it can use the second derivatives and does not depend on projections on the set of inequality constraints. In each iteration, our method solves a twice continuously differentiable unconstrained optimization subproblem on primal variables. The dual iterates, penalty and smoothing parameters are updated adaptively. The global and local convergence are analyzed. Without assuming any constraint qualification, it is proved that the proposed method has strong global convergence. The method may converge to either a Kurash-Kuhn-Tucker (KKT) point or a singular stationary point when the converging point is a minimizer. It may also converge to an infeasible stationary point of nonlinear program when the problem is infeasible. Furthermore, our method is capable of rapidly detecting the possible infeasibility of the solved problem. Under suitable conditions, it is locally linearly convergent to the KKT point, which is consistent with ALMs for optimization with equality constraints. The preliminary numerical experiments on some small benchmark test problems demonstrate our theoretical results., Comment: 31 pages