Search

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

We consider the dividend maximization problem including a ruin penalty in a diffusion environment. The additional penalty term is motivated by a constraint on dividend strategies. Intentionally, we use different discount rates for the dividends and the penalty, which causes time-inconsistency. This allows to study different types of constraints. For the diffusion approximation of the classical surplus process we derive an explicit equilibrium dividend strategy and the associated value function. Inspired by duality arguments, we can identify a particular equilibrium strategy such that for a given initial surplus the imposed constraint is fulfilled. Furthermore, we illustrate our findings with a numerical example.

The present paper introduces a mathematical model for studying dynamic grain growth. In particular, we show how characteristic measurements, grain volumes, centroids, and central second-order moments at discrete moments in time can be turned quickly into a continuous description of the grain growth process in terms of geometric diagrams (which largely generalize the well-known Voronoi and Laguerre tessellations). We evaluate the computational behavior of our algorithm on real-world data., 21 pages, 4 tables, 6 figures

One of the major challenges associated with applying operations research (OR) models to disrupting human trafficking networks is the limited amount of reliable data sources readily available for public use, since operations are intentionally hidden to prevent detection, and data from known operations are often incomplete. To help address this data gap, we propose a network generator for domestic sex trafficking networks by integrating OR concepts and qualitative research. Multiple sources regarding sex trafficking in the upper Midwest of the United States have been triangulated to ensure that networks produced by the generator are realistic, including law enforcement case file analysis, interviews with domain experts, and a survivor-centered advisory group with first-hand knowledge of sex trafficking. The output models the relationships between traffickers, so-called "bottoms", and victims. This generator allows operations researchers to access realistic sex trafficking network structures in a responsible manner that does not disclose identifiable details of the people involved. We demonstrate the use of output networks in exploring policy recommendations from max flow network interdiction with restructuring. To do so, we propose a novel conceptualization of flow as the ability of a trafficker to control their victims. Our results show the importance of understanding how sex traffickers react to disruptions, especially in terms of recruiting new victims.

This paper deals with the integration of input move-blocking into the framework of suboptimal model predictive control. The blocked input parameterization is explicitly considered as a source of suboptimality. A straightforward integration approach is to hold back a manually generated stabilizing fallback solution in some buffer for the case that the optimizer does not find a better input move-blocked solution. An extended approach superimposes the manually generated stabilizing warm-start by the move-blocked control sequence and enables a stepwise improvement of the control performance. In addition, this contribution provides a detailed review of the literature on input move-blocked model predictive control and combines important results with the findings of suboptimal model predictive control. A numerical example supports the theoretical results and shows the effectiveness of the proposed approach., Added missing condition to Eq. (11); Added reference to difference inclusion (12) in Prop. 7 and Prop. 10; Removed typos

Order picking is the process of retrieving ordered products from storage locations in warehouses. In picker-to-parts order picking systems, two or more customer orders may be grouped and assigned to a single picker. Then routing decision regarding the visiting sequence of items during a picking tour must be made. (J.Won and S.Olafsson 2005) found that solving the integrated problem of batching and routing enables warehouse managers to organize order picking operations more efficiently compared with solving the two problems separately and sequentially. We therefore investigate the mathematical programming formulation of this integrated problem. We present several improved formulations for the problem based on the findings of (Valle, Beasley, and da Cunha 2017), that can significantly improve computational results. More specifically, we reconstruct the connectivity constraints and generate new cutting planes in our branch-and-cut framework. We also discuss some problem properties by studying the structure of the graphical representation, and we present two types of additional constraints. We also consider the no-reversal case of this problem. We present efficient formulations by building different auxiliary graphs. Finally, we present computational results for publicly available test problems for single-block and multiple-block warehouse configurations, Comment: 37 pages, 11 figures, 7 tables

Recently, Yamanaka and Yamashita proposed the so-called positively homogeneous optimization problem, which includes many important problems, such as the absolute-value and the gauge optimizations. They presented a closed form of the dual formulation for the problem, and showed weak duality and the equivalence to the Lagrangian dual under some conditions. In this work, we focus on a special positively homogeneous optimization problem, whose objective function and constraints consist of some gauge and linear functions. We prove not only weak duality but also strong duality. We also study necessary and sufficient optimality conditions associated to the problem. Moreover, we give sufficient conditions under which we can recover a primal solution from a Karush-Kuhn-Tucker point of the dual formulation. Finally, we discuss how to extend the above results to general convex optimization problems by considering the so-called perspective functions., Comment: 24 pages

Markov decision process models and algorithms can be used to identify optimal policies for dispatching ambulances to spatially distributed customers, where the optimal policies indicate the ambulance to dispatch to each customer type in each state. Since the optimal solutions are dependent on Markov state variables, they may not always correspond to a simple set of rules when implementing the policies in practice. Restricted policies that conform to a priority list for each type of customer may be desirable for use in practice, since such policies are transparent, explainable, and easy to implement. A priority list policy is an ordered list of ambulances that indicates the preferred order to dispatch the ambulances to a customer type subject to ambulance availability. This paper proposes a constrained Markov decision process model for identifying optimal priority list policies that is formulated as a mixed integer programming model, does not extend the Markov state space, and can be solved using standard algorithms. A series of computational examples illustrate the benefit of intuitive policies. The optimal mixed integer programming solutions to the computational examples have objective function values that are close to those of the unrestricted model and are superior to those of heuristics.

In this paper we consider a company whose assets and liabilities evolve according to a correlated bivariate geometric Brownian motion, such as in Gerber and Shiu (2003). We determine what dividend strategy maximises the expected present value of dividends until ruin in two cases: (i) when shareholders won't cover surplus shortfalls and a solvency constraint (as in Paulsen, 2003) is consequently imposed, and (ii) when shareholders are always to fund any capital deficiency with capital (asset) injections. In the latter case, ruin will never occur and the objective is to maximise the difference between dividends and capital injections. Developing and using appropriate verification lemmas, we show that the optimal dividend strategy is, in both cases, of barrier type. Both value functions are derived in closed form. Furthermore, the barrier is defined on the ratio of assets to liabilities, which mimics some of the dividend strategies that can be observed in practice by insurance companies. Existence and uniqueness of the optimal strategies are shown. Results are illustrated.

We consider a model of adversarial dynamics consisting of three populations, labelled Blue, Green and Red, which evolve under a system of first order nonlinear differential equations. Red and Blue populations are adversaries and interact via a set of Lanchester combat laws. Green is divided into three sub-populations: Red supporters, Blue supporters and Neutral. Green support for Red and Blue leads to more combat effectiveness for either side. From Green's perspective, if either Red or Blue exceed a size according to the capacity of the local population to facilitate or tolerate, then support for that side diminishes; the corresponding Green population reverts to the neutral sub-population, who do not contribute to combat effectiveness of either side. The mechanism for supporters deciding if either Blue or Red are too big is given by a logistic-type interaction term. The intent of the model is to examine the role of influence in complex adversarial situations typical in counter-insurgency, where victory requires a genuine balance between maintaining combat effectiveness and support from a third party whose backing is not always assured., Pre-review version. The manuscript accepted for publication in JORS

A continuous selection of polynomial functions is a continuous function whose domain can be partitioned into finitely many pieces on which the function coincides with a polynomial. Given a set of finitely many polynomials, we show that there are only finitely many continuous selections of it and each one is semi-algebraic. Then, we establish some generic properties regarding the critical points, defined by the Clarke subdifferential, of these continuous selections. In particular, given a set of finitely many polynomials with generic coefficients, we show that the critical points of all continuous selections of it are finite and the critical values are all different, and we also derive the coercivity of those continuous selections which are bounded from below. We point out that some existing results about {\L}ojasiewicz's inequality and error bounds for the maximum function of some finitely many polynomials are also valid for all the continuous selections of them., Comment: 28 pages

In this work, we propose integral global optimality conditions for multiobjective problems not necessarily differentiable. The integral characterization, already known for single objective problems, are extended to multiobjective problems by weighted sum and Chebyshev weighted scalarizations. Using this last scalarization, we propose an algorithm for obtaining an approximation of the weak Pareto front whose effectiveness is illustrated by solving a collection of multiobjective test problems.

We generalize the Maximum Principle for free end point optimal control problems involving sweeping systems derived in [de Pinho MdR, Ferreira MMA, Smirnov GV. Optimal control involving sweeping processes. Set-Valued Var Anal. 2019;27(2):523–548] to cover the case where the constraints are time dependent and the end point is constrained to a set. As in [de Pinho MdR, Ferreira MMA, Smirnov GV. Optimal control involving sweeping processes. Set-Valued Var Anal. 2019;27(2):523–548], an ingenious smooth approximating family of standard differential equations plays a crucial role., This work was supported by the Portuguese Foundation for Science and Technology (FCT) in the framework of the Strategic Funding UIDB/04650/2020. This work was also supported by the ERDF - European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COM PETE 2020, INCO.2030, under the Portugal 2020 Partnership Agreement and by National Funds, Norte 2020, through CCDRN and FCT, within projects To Chair (POCI-01-0145-FEDER-028247), Upwind (PTDC/EEI-AUT/31447/2017 - POCI-01-0145-FEDER-031447) and Systec R&D unit (UIDB/00147/2020).

In this article we explore a symplectic packing problem where the targets and domains are $2n$-dimensional symplectic manifolds. We work in the context where the manifolds have first homology group equal to $\mathbb{Z}^n$, and we require the embeddings to induce isomorphisms between first homology groups. In this case, Maley, Mastrangeli and Traynor showed that the problem can be reduced to a combinatorial optimization problem, namely packing certain allowable simplices into a given standard simplex. They designed a computer program and presented computational results. In particular, they determined the simplex packing widths in dimension four for up to $k=12$ simplices, along with lower bounds for higher values of $k$. We present a modified algorithmic approach that allows us to determine the $k$-simplex packing widths for up to $k = 13$ simplices in dimension four and up to $k = 8$ simplices in dimension six. Moreover, our approach determines all simplex-multisets that allow for optimal packings., Comment: 28 pages, improved general presentation, added an explanation to some numbers appearing in tables

In this paper, we leverage over-parameterization to design regularization-free algorithms for the high-dimensional single index model and provide theoretical guarantees for the induced implicit regularization phenomenon. Specifically, we study both vector and matrix single index models where the link function is nonlinear and unknown, the signal parameter is either a sparse vector or a low-rank symmetric matrix, and the response variable can be heavy-tailed. To gain a better understanding of the role played by implicit regularization without excess technicality, we assume that the distribution of the covariates is known a priori. For both the vector and matrix settings, we construct an over-parameterized least-squares loss function by employing the score function transform and a robust truncation step designed specifically for heavy-tailed data. We propose to estimate the true parameter by applying regularization-free gradient descent to the loss function. When the initialization is close to the origin and the stepsize is sufficiently small, we prove that the obtained solution achieves minimax optimal statistical rates of convergence in both the vector and matrix cases. In addition, our experimental results support our theoretical findings and also demonstrate that our methods empirically outperform classical methods with explicit regularization in terms of both $\ell_2$-statistical rate and variable selection consistency., major revision

Like most multiobjective combinatorial optimization problems, biobjective optimization problems on matroids are in general intractable and their corresponding decision problems are in general NP-hard. In this paper, we consider biobjective optimization problems on matroids where one of the objective functions is restricted to binary cost coefficients. We show that in this case the problem has a connected efficient set with respect to a natural definition of a neighborhood structure and hence, can be solved efficiently using a neighborhood search approach. This is, to the best of our knowledge, the first non-trivial problem on matroids where connectedness of the efficient set can be established. The theoretical results are validated by numerical experiments with biobjective minimum spanning tree problems (graphic matroids) and with biobjective knapsack problems with a cardinality constraint (uniform matroids). In the context of the minimum spanning tree problem, coloring all edges with cost 0 green and all edges with cost 1 red leads to an equivalent problem where we want to simultaneously minimize one general objective and the number of red edges (which defines the second objective) in a Pareto sense.

We associate with each convex optimization problem, posed on some locally convex space, with infinitely many constraints indexed by the set T, and a given non-empty family H of finite subsets of T, a suitable Lagrangian-Haar dual problem. We obtain necessary and sufficient conditions for H-reducibility, that is, equivalence to some subproblem obtained by replacing the whole index set T by some element of H. Special attention is addressed to linear optimization, infinite and semi-infinite, and to convex problems with a countable family of constraints. Results on zero H-duality gap and on H-(stable) strong duality are provided. Examples are given along the paper to illustrate the meaning of the results., 23 pages and 1 figure

The Vehicle Routing Problem (VRP) is one of the most intensively studied combinatorial optimisation problems for which numerous models and algorithms have been proposed. To tackle the complexities, uncertainties and dynamics involved in real-world VRP applications, Machine Learning (ML) methods have been used in combination with analytical approaches to enhance problem formulations and algorithmic performance across different problem solving scenarios. However, the relevant papers are scattered in several traditional research fields with very different, sometimes confusing, terminologies. This paper presents a first, comprehensive review of hybrid methods that combine analytical techniques with ML tools in addressing VRP problems. Specifically, we review the emerging research streams on ML-assisted VRP modelling and ML-assisted VRP optimisation. We conclude that ML can be beneficial in enhancing VRP modelling, and improving the performance of algorithms for both online and offline VRP optimisations. Finally, challenges and future opportunities of VRP research are discussed., Submitted to International Journal of Production Research

We propose easily verifiable necessary and sufficient conditions for the linearizability of two-input systems by an endogenous dynamic feedback with a dimension of at most two.

Multistage stochastic programming provides a modeling framework for sequential decision-making problems that involve uncertainty. One typically overlooked aspect of this methodology is how uncertainty is incorporated into modeling. Traditionally, statistical forecasting techniques with simple forms, e.g., (first-order) autoregressive time-series models, are used to extract scenarios to be added to optimization models to represent the uncertain future. However, often times, the performance of these forecasting models are not thoroughly assessed. Motivated by the advances in probabilistic forecasting, we incorporate a deep learning-based time-series forecasting method into multistage stochastic programming framework, and compare it with the cases where a traditional forecasting method is employed to model the uncertainty. We assess the impact of more accurate forecasts on the quality of two commonly used look-ahead policies, a deterministic one and a two-stage one, in a rolling\red{-}horizon framework on a practical problem. Our results illustrate that more accurate forecasts contribute substantially to the model performance, and enable obtaining high-quality solutions even from computationally cheap heuristics. They also show that the probabilistic forecasting capabilities of deep learning-based methods can be especially beneficial when used as a (conditional) sampling tool for scenario-based models, and to predict the worst-case scenario for risk-averse models.

The outcomes of warfare have rarely only been characterised by the quantity and quality of individual combatant force elements. The ability to manoeuvre and adapt across force elements through effective Command and Control (C2) can allow smaller or weaker forces to overcome an adversary with greater resource and fire-power. In this paper, we combine the classic Lanchester combat model with the Kuramoto-Sakaguchi model for phase oscillators on a network to create a flexible Networked-Lanchester-C2 representation of force-on-force military engagement. The mathematical model thus unifies three of the military warfighting `functions': fires, manoeuvre and C2. We consider three illustrative use-cases, and show that an analytical treatment of a reduced model characterises global effects in the full system. For inhomogeneous forces we observe that with appropriate balance between internal organisational coupling, resource manoeuvrability and even weaker lethality the force can be adaptive to overcome an initially stronger adversary., Comment: 30 pages, 16 figures, preprint accepted by the Journal of the Operational Research Society

Flexible sparsity regularization means stably approximating sparse solutions of operator equations by using coefficient-dependent penalizations. We propose and analyse a general nonconvex approach in this respect, from both theoretical and numerical perspectives. Namely, we show convergence of the regularization method and establish convergence properties of a couple of majorization approaches for the associated nonconvex problems. We also test a monotone algorithm for an academic example where the operator is an $M$ matrix, and on a time-dependent optimal control problem, pointing out the advantages of employing variable penalties over a fixed penalty.

International audience; In this article, we give an in-depth analysis of the problem of optimising the total population size for a standard logistic-diffusive model. This optimisation problem stems from the study of spatial ecology and amounts to the following question: assuming a species evolves in a domain, what is the best way to spread resources in order to ensure a maximal population size at equilibrium? {In recent years, many authors contributed to this topic.} We settle here the proof of two fundamental properties of optimisers: the bang-bang one which had so far only been proved under several strong assumptions, and the other one is the fragmentation of maximisers. Here, we prove the bang-bang property in all generality using a new spectral method. The technique introduced to demonstrate the bang-bang character of optimizers can be adapted and generalized to many optimization problems with other classes of bilinear optimal control problems where the state equation is semilinear and elliptic. We comment on it in a conclusion section.Regarding the geometry of maximisers, we exhibit a blow-up rate for the $BV$-norm of maximisers as the diffusivity gets smaller: if $\Omega$ is an orthotope and if $m_\mu$ is an optimal control, then $\Vert m_\mu\Vert_{BV}\gtrsim \sqrt{\mu}$. The proof of this results relies on a very fine energy argument.

This work introduces a second-order differential inclusion for unconstrained convex optimization. In continuous level, solution existence in proper sense is obtained and exponential decay of a novel Lyapunov function along with the solution trajectory is derived as well. Then in discrete level, based on numerical discretizations of the continuous differential inclusion, both an inexact accelerated proximal point algorithm and an inexact accelerated proximal gradient method are proposed, and some new convergence rates are established via a discrete Lyapunov function.

We consider an optimal control problem governed by an elliptic variational inequality of the second kind. The problem is discretized by linear finite elements for the state and a variational discrete approach for the control. Based on a quadratic growth condition we derive nearly optimal a priori error estimates. Moreover, we establish second order sufficient optimality conditions that ensure a quadratic growth condition. These conditions are rather restrictive, but allow us to construct a one-dimensional locally optimal solution with reduced regularity, which serves as an exact solution for numerical experiments.

This paper investigates the robust stability and stabilization analysis of interval fractional-order systems with time-varying delay. The stability problem of such systems is solved first, and then using the proposed results a stabilization theorem is also included, where sufficient conditions are obtained for designing a stabilizing controller with a predetermined order, which can be chosen to be as low as possible. Utilizing efficient lemmas, the stability and stabilization theorems are proposed in the form of LMIs, which is more suitable to check due to various existing efficient convex optimization parsers and solvers. Finally, two numerical examples have shown the effectiveness of our results., arXiv admin note: text overlap with arXiv:1807.10827

We present two sampled quasi-Newton methods (sampled LBFGS and sampled LSR1) for solving empirical risk minimization problems that arise in machine learning. Contrary to the classical variants of these methods that sequentially build Hessian or inverse Hessian approximations as the optimization progresses, our proposed methods sample points randomly around the current iterate at every iteration to produce these approximations. As a result, the approximations constructed make use of more reliable (recent and local) information, and do not depend on past iterate information that could be significantly stale. Our proposed algorithms are efficient in terms of accessed data points (epochs) and have enough concurrency to take advantage of parallel/distributed computing environments. We provide convergence guarantees for our proposed methods. Numerical tests on a toy classification problem as well as on popular benchmarking binary classification and neural network training tasks reveal that the methods outperform their classical variants., Comment: 50 pages, 33 figures

In this paper we study the problem of decomposing a given tensor into a tensor train such that the tensors at the vertices are orthogonally decomposable. When the tensor train has length two, and the orthogonally decomposable tensors at the two vertices are symmetric, we recover the decomposition by considering random linear combinations of slices. Furthermore, if the tensors at the vertices are symmetric and low-rank but not orthogonally decomposable, we show that a whitening procedure can transform the problem into the orthogonal case. When the tensor network has length three or more and the tensors at the vertices are symmetric and orthogonally decomposable, we provide an algorithm for recovering them subject to some rank conditions. Finally, in the case of tensor trains of length two in which the tensors at the vertices are orthogonally decomposable but not necessarily symmetric, we show that the decomposition problem reduces to the novel problem of decomposing a matrix into an orthogonal matrix multiplied by diagonal matrices on either side. We provide and compare two solutions, one based on Sinkhorn's theorem and one on Procrustes' algorithm. We conclude with a multitude of open problems in linear and multilinear algebra that arose in our study.

International audience; The goal of this paper is to provide a selection principle for potential mean field games on a finite state space and, in this respect, to show that equilibria that do not minimize the corresponding mean field control problem should be ruled out. Our strategy is a tailor-made version of the vanishing viscosity method for partial differential equations. Here, the viscosity has to be understood as the square intensity of a common noise that is inserted in the mean field game or, equivalently, as the diffusivity parameter in the related parabolic version of the master equation. As established in the recent contribution (Bayraktar et al., 2021, J. Math. Pures Appl. 147:98-162), the randomly forced mean field game becomes indeed uniquely solvable for a relevant choice of a Wright-Fisher common noise, the counterpart of which in the master equation is a Kimura operator on the simplex. We here elaborate on (Bayraktar et al., 2021, J. Math. Pures Appl. 147:98-162) to make the mean field game with common noise both uniquely solvable and potential, meaning that its unique solution is in fact equal to the unique minimizer of a suitable stochastic mean field control problem. Taking the limit as the intensity of the common noise vanishes, we obtain a rigorous proof of the aforementioned selection principle. As a byproduct, we get that the classical solution to the viscous master equation associated with the mean field game with common noise converges to the gradient of the value function of the mean field control problem without common noise. We hence select a particular weak solution of the master equation of the original mean field game. Lastly, we establish an intrinsic uniqueness criterion for this solution within a suitable class of weak solutions to the master equation satisfying a weak one-sided Lipschitz inequality.

Recently, the author, together with L. Leustean and A. Nicolae, introduced the notion of jointly firmly nonexpansive families of mappings in order to investigate in an abstract manner the convergence of proximal methods. Here, we further the study of this concept, by giving a characterization in terms of the classical resolvent identity, by improving on the rate of convergence previously obtained for the uniform case, and by giving a treatment of the asymptotic behaviour at infinity of such families., arXiv admin note: text overlap with arXiv:2108.13994

This paper continues studies of non-intersection properties of finite collections of sets initiated 40 years ago by the extremal principle. We study elementary non-intersection properties of collections of sets, making the core of the conventional definitions of extremality and stationarity. In the setting of general Banach/Asplund spaces, we establish new primal (slope) and dual (generalized separation) necessary conditions for these non-intersection properties. The results are applied to convergence analysis of alternating projections., Comment: 26 pages

We study model predictive control for singular differential-algebraic equations with higher index. This is a novelty when compared to the literature where only regular differential-algebraic equations with additional assumptions on the index and/or controllability are considered. By regularization techniques, we are able to derive an equivalent optimal control problem for an ordinary differential equation to which well-known model predictive control techniques can be applied. This allows the construction of terminal constraints and costs such that the origin is asymptotically stable w.r.t. the resulting closed-loop system.

Mixed effects (ME) models inform a vast array of problems in the physical and social sciences, and are pervasive in meta-analysis. We consider ME models where the random effects component is linear. We then develop an efficient approach for a broad problem class that allows nonlinear measurements, priors, and constraints, and finds robust estimates in all of these cases using trimming in the associated marginal likelihood. The software accompanying this paper is disseminated as an open-source Python package called LimeTr. LimeTr is able to recover results more accurately in the presence of outliers compared to available packages for both standard longitudinal analysis and meta-analysis, and is also more computationally efficient than competing robust alternatives. Supplementary materials that reproduce the simulations, as well as run LimeTr and third party code are available online. We also present analyses of global health data, where we use advanced functionality of LimeTr, including constraints to impose monotonicity and concavity for dose-response relationships. Nonlinear observation models allow new analyses in place of classic approximations, such as log-linear models. Robust extensions in all analyses ensure that spurious data points do not drive our understanding of either mean relationships or between-study heterogeneity., 33 pages, 7 figures

A square matrix $A$ is completely positive if $A=BB^T$, where $B$ is a (not necessarily square) nonnegative matrix. In general, a completely positive matrix may have many, even infinitely many, such CP factorizations. But in some cases a unique CP factorization exists. We prove a simple necessary and sufficient condition for a completely positive matrix whose graph is triangle free to have a unique CP factorization. This implies uniqueness of the CP factorization for some other matrices on the boundary of the cone $\mathcal{CP}_n$ of $n\times n$ completely positive matrices. We also describe the minimal face of $\mathcal{CP}_n$ containing a completely positive $A$. If $A$ has a unique CP factorization, this face is polyhedral., Comment: 16 pages, typos corrected, submitted

Qualitative and quantitative aspects for variational inequalities governed by strongly pseudomonotone operators on Hilbert space are investigated in this paper. First, we establish a global error bound for the solution set of the given problem with the residual function being the normal map. Second, we will prove that the iterative sequences generated by gradient projection method (GPM) with stepsizes forming a non-summable diminishing sequence of positive real numbers converge to the unique solution of the problem when the operator is bounded over the constraint set. Two counter-examples are given to show the necessity of the boundedness assumption and the variation of stepsizes. We also analyze the convergence rate of the iterative sequences generated by this method. Finally, we give an in-depth comparison between our algorithm and a recent related algorithm through several numerical experiments., 22 pages

In this paper, we consider gradient methods for minimizing smooth convex functions, which employ the information obtained at the previous iterations in order to accelerate the convergence towards the optimal solution. This information is used in the form of a piece-wise linear model of the objective function, which provides us with much better prediction abilities as compared with the standard linear model. To the best of our knowledge, this approach was never really applied in Convex Minimization to differentiable functions in view of the high complexity of the corresponding auxiliary problems. However, we show that all necessary computations can be done very efficiently. Consequently, we get new optimization methods, which are better than the usual Gradient Methods both in the number of oracle calls and in the computational time. Our theoretical conclusions are confirmed by preliminary computational experiments., Comment: This is an Accepted Manuscript of an article published by Taylor \& Francis in Optimization Methods and Software on 13 Jan 2021, available at https://www.tandfonline.com/doi/10.1080/10556788.2020.1858831

In this paper we first extend the diminishing stepsize method for nonconvex constrained problems presented in [4] to deal with equality constraints and a nonsmooth objective function of composite type. We then consider the particular case in which the constraints are convex and satisfy a standard constraint qualification and show that in this setting the algorithm can be considerably simplified, reducing the computational burden of each iteration., arXiv admin note: text overlap with arXiv:1709.03384

A stochastic second-order trust region method is proposed, which can be viewed as a second-order extension of the trust-region-ish (TRish) algorithm proposed by Curtis et al. (INFORMS J. Optim. 1(3) 200-220, 2019). In each iteration, a search direction is computed by (approximately) solving a trust region subproblem defined by stochastic gradient and Hessian estimates. The algorithm has convergence guarantees for stochastic minimization in the fully stochastic regime, meaning that guarantees hold when each stochastic gradient is required merely to be an unbiased estimate of the true gradient with bounded variance and when the stochastic Hessian estimates are bounded uniformly in norm. The algorithm is also equipped with a worst-case complexity guarantee in the nearly deterministic regime, i.e., when the stochastic gradient and Hessian estimates are very close in expectation to the true gradients and Hessians. The results of numerical experiments for training convolutional neural networks for image classification and training a recurrent neural network for time series forecasting are presented. These results show that the algorithm can outperform a stochastic gradient approach and the first-order TRish algorithm in practice.

We consider the problem of minimizing a finite sum of convex functions subject to the set of minimizers of a convex differentiable function. In order to solve the problem, an algorithm combining the incremental proximal gradient method with smooth penalization technique is proposed. We show the convergence of the generated sequence of iterates to an optimal solution of the optimization problems, provided that a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. Finally, the functionality of the method is illustrated by some numerical experiments addressing image inpainting problems and generalized Heron problems with least squares constraints.

In this paper, we present a structurally flat triangular form which is based on the extended chained form. We provide a complete geometric characterization of the proposed triangular form in terms of necessary and sufficient conditions for an affine input system with two inputs to be static feedback equivalent to this triangular form. This yields a sufficient condition for an affine input system to be flat., Comment: arXiv admin note: substantial text overlap with arXiv:2002.01203

Industry 4.0 is a concept that assists companies in developing a modern supply chain (MSC) system when they are faced with a dynamic process. Because Industry 4.0 focuses on mobility and real-time integration, it is a good framework for a dynamic vehicle routing problem (DVRP). This research works on DVRP. The aim of this research is to minimize transportation cost without exceeding the capacity constraint of each vehicle while serving customer demands from a common depot. Meanwhile, new orders arrive at a specific time into the system while the vehicles are executing the delivery of existing orders. This paper presents a two-stage hybrid algorithm for solving the DVRP. In the first stage, construction algorithms are applied to develop the initial route. In the second stage, improvement algorithms are applied. Experimental results were designed for different sizes of problems. Analysis results show the effectiveness of the proposed algorithm., 22 pages, 4 figures, 1 table. Journal of Management Analytics (2020)

Discrete convex functions are used in many areas, including operations research, discrete-event systems, game theory, and economics. The objective of this paper is to investigate basic operations such as direct sum, splitting, and aggregation that are related to network induction of discrete convex functions as well as discrete convex sets. Various kinds of discrete convex functions in discrete convex analysis are considered such as integrally convex functions, L-convex functions, M-convex functions, multimodular functions, and discrete midpoint convex functions., Comment: 42 pages. arXiv admin note: text overlap with arXiv:1907.09161

This work presents a partitioned solution procedure to compute shape gradients in fluid-structure interaction (FSI) using black-box adjoint solvers. Special attention is paid to project the gradients onto the undeformed configuration. This is due to the mixed Lagrangian-Eulerian formulation of large-displacement FSI in this work. Adjoint FSI problem is partitioned as an assembly of well-known adjoint fluid and structural problems, without requiring expensive cross-derivatives. The sub-adjoint problems are coupled with each other by augmenting the target functions with auxiliary functions, independent of the concrete choice of the underlying adjoint formulations. The auxiliary functions are linear force-based or displacement-based functionals which are readily available in well-established single-disciplinary adjoint solvers. Adjoint structural displacements, adjoint fluid displacements, and domain-based adjoint sensitivities of the fluid are the coupling fields to be exchanged between the adjoint solvers. A reduced formulation is also derived for the case of boundary-based adjoint shape sensitivity analysis for fluids. Numerical studies show that the complete formulation computes accurate shape gradients whereas inaccuracies appear in the reduced gradients, specially in regions of strong flow gradients and near singularities. Nevertheless, reduced gradient formulations are found to be a compromise between computational costs and accuracy. Mapping techniques including nearest element interpolation and the mortar method are studied in computational adjoint FSI. It is numerically shown that the mortar method does not introduce spurious oscillations in primal and sensitivity fields along non-matching interfaces, unlike the nearest element interpolation.

We consider the distributionally robust optimization and show that computing the distributional worst-case is equivalent to computing the projection onto the canonical simplex with additional linear inequality. We consider several distance functions to measure the distance of distributions. We write the projections as optimization problems and show that they are equivalent to finding a zero of real-valued functions. We prove that these functions possess nice properties such as monotonicity or convexity. We design optimization methods with guaranteed convergence and derive their theoretical complexity. We demonstrate that our methods have (almost) linear observed complexity.

We present a fast algorithm for generating Laguerre diagrams with cells of given volumes, which can be used for creating RVEs of polycrystalline materials for computational homogenisation, or for fitting Laguerre diagrams to EBSD or XRD measurements of metals. Given a list of desired cell volumes, we solve a convex optimisation problem to find a Laguerre diagram with cells of these volumes, up to any prescribed tolerance. The algorithm is built on tools from computational geometry and optimal transport theory which, as far as we are aware, have not been applied to microstructure modelling before. We illustrate the speed and accuracy of the algorithm by generating RVEs with user-defined volume distributions with up to 20,000 grains in 3D. We can achieve volume percentage errors of less than 1% in the order of minutes on a standard desktop PC. We also give examples of polydisperse microstructures with bands, clusters and size gradients, and of fitting a Laguerre diagram to 3D EBSD measurements of an IF steel.

Incomplete pairwise comparison matrices offer a natural way of expressing preferences in decision making processes. Although ordinal information is crucial, there is a bias in the literature: cardinal models dominate. Ordinal models usually yield non-unique solutions; therefore, an approach blending ordinal and cardinal information is needed. In this work, we consider two cascading problems: first, we compute ordinal preferences, maximizing an index that combines ordinal and cardinal information; then, we obtain a cardinal ranking by enforcing ordinal constraints. Notably, we provide a sufficient condition (that is likely to be satisfied in practical cases) for the first problem to admit a unique solution and we develop a provably polynomial-time algorithm to compute it. The effectiveness of the proposed method is analyzed and compared with respect to other approaches and criteria at the state of the art., preprint submitted to the International Journal of General Systems

A series of basic qualitative properties of the minimum sum-of-squares clustering problem are established in this paper. Among other things, we clarify the solution existence, properties of the global solutions, characteristic properties of the local solutions, locally Lipschitz property of the optimal value function, locally upper Lipschitz property of the global solution map, and the Aubin property of the local solution map. We prove that the problem in question always has a global solution and, under a mild condition, the global solution set is finite and the components of each global solution can be computed by an explicit formula. Based on a newly introduced concept of nontrivial local solution, we get necessary conditions for a system of centroids to be a nontrivial local solution. Interestingly, we are able to show that these necessary conditions are also sufficient ones. Finally, it is proved that the optimal value function is locally Lipschitz, the global solution map is locally upper Lipschitz, and the local solution map has the Aubin property, provided that the original data points are pairwise distinct. Thanks to the obtained complete characterizations of the nontrivial local solutions, one can understand better the performance of not only the $k$-means algorithm, but also of other solution methods for the minimum sum-of-squares clustering problem.

For certain industrial control applications an explicit function capturing the nontrivial trade-off between competing objectives in closed loop performance is not available. In such scenarios it is common practice to use the human innate ability to implicitly learn such a relationship and manually tune the corresponding controller to achieve the desirable closed loop performance. This approach has its deficiencies because of individual variations due to experience levels and preferences in the absence of an explicit calibration metric. Moreover, as the complexity of the underlying system and/or the controller increase, in the effort to achieve better performance, so does the tuning time and the associated tuning cost. To reduce the overall tuning cost, a tuning framework is proposed herein, whereby a supervised machine learning is used to extract the human-learned cost function and an optimization algorithm that can efficiently deal with a large number of variables, is used for optimizing the extracted cost function. Given the interest in the implementation across many industrial domains and the associated high degree of freedom present in the corresponding tuning process, a Model Predictive Controller applied to air path control in a diesel engine is tuned for the purpose of demonstrating the potential of the framework.

Minimization of a smooth function on a sphere or, more generally, on a smooth manifold, is the simplest non-convex optimization problem. It has a lot of applications. Our goal is to propose a version of the gradient projection algorithm for its solution and to obtain results that guarantee convergence of the algorithm under some minimal natural assumptions. We use the Lezanski-Polyak-Lojasiewicz condition on a manifold to prove the global linear convergence of the algorithm. Another method well fitted for the problem is the conditional gradient (Frank-Wolfe) algorithm. We examine some conditions which guarantee global convergence of full-step version of the method with linear rate.

In classical Markov Decision Processes (MDPs), action costs and transition probabilities are assumed to be known, although an accurate estimation of these parameters is often not possible in practice. This study addresses MDPs under cost and transition probability uncertainty and aims to provide a mathematical framework to obtain policies minimizing the risk of high long-term losses due to not knowing the true system parameters. To this end, we utilize the risk measure value-at-risk associated with the expected performance of an MDP model with respect to parameter uncertainty. We provide mixed-integer linear and nonlinear programming formulations and heuristic algorithms for such risk-averse models of MDPs under a finite distribution of the uncertain parameters. Our proposed models and solution methods are illustrated on an inventory management problem for humanitarian relief operations during a slow-onset disaster. The results demonstrate the potential of our risk-averse modeling approach for reducing the risk of highly undesirable outcomes in uncertain/risky environments.