Search

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.

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.

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

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.

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

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

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.

International audience; We present a generic coordinate descent solver for the minimization of a nonsmooth convex objective with structure. The method can deal in particular with problems with linear constraints. The implementation makes use of efficient residual updates and automatically determines which dual variables should be duplicated. A list of basic functional atoms is pre-compiled for efficiency and a modelling language in Python allows the user to combine them at run time. So, the algorithm can be used to solve a large variety of problems including Lasso, sparse multinomial logistic regression, linear and quadratic programs.

This paper studies stochastic optimization problems with polynomials. We propose an optimization model with sample averages and perturbations. The Lasserre type Moment-SOS relaxations are used to solve the sample average optimization. Properties of the optimization and its relaxations are studied. Numerical experiments are presented., Comment: 17 pages

Distributed optimization algorithms are essential for training machine learning models on very large-scale datasets. However, they often suffer from communication bottlenecks. Confronting this issue, a communication-efficient primal-dual coordinate ascent framework (CoCoA) and its improved variant CoCoA+ have been proposed, achieving a convergence rate of $\mathcal{O}(1/t)$ for solving empirical risk minimization problems with Lipschitz continuous losses. In this paper, an accelerated variant of CoCoA+ is proposed and shown to possess a convergence rate of $\mathcal{O}(1/t^2)$ in terms of reducing suboptimality. The analysis of this rate is also notable in that the convergence rate bounds involve constants that, except in extreme cases, are significantly reduced compared to those previously provided for CoCoA+. The results of numerical experiments are provided to show that acceleration can lead to significant performance gains.

This paper addresses the problem of robust dynamic output stabilization of FO-LTI interval systems with the fractional order 0, Comment: arXiv admin note: substantial text overlap with arXiv:1701.05344

This paper documents a computational implementation of a {\em projection and rescaling algorithm} for finding most interior solutions to the pair of feasibility problems \[ \text{find} \; x\in L\cap\mathbb{R}^n_{+} \;\;\;\; \text{ and } \; \;\;\;\; \text{find} \; \hat x\in L^\perp\cap\mathbb{R}^n_{+}, \] where $L$ denotes a linear subspace in $\mathbb{R}^n$ and $L^\perp$ denotes its orthogonal complement. The projection and rescaling algorithm is a recently developed method that combines a {\em basic procedure} involving only low-cost operations with a periodic {\em rescaling step.} We give a full description of a MATLAB implementation of this algorithm and present multiple sets of numerical experiments on synthetic problem instances with varied levels of conditioning. Our computational experiments provide promising evidence of the effectiveness of the projection and rescaling algorithm. Our MATLAB code is publicly available. Furthermore, the simplicity of the algorithm makes a computational implementation in other environments completely straightforward., Comment: 19 pages

It is well known that finite-dimensional polyhedral convex sets can be generated by finitely many points and finitely many directions. Representation formulas in this spirit are obtained for convex polyhedra and generalized convex polyhedra in locally convex Hausdorff topological vector spaces. Our results develop those of X. Y. Zheng (Set-Valued Anal., Vol. 17, 2009, 389-408), which were established in a Banach space setting. Applications of the representation formulas to proving solution existence theorems for generalized linear programming problems and generalized linear vector optimization problems are shown.

This paper is concerned with the strong calmness of the KKT solution mapping for a class of canonically perturbed conic programming, which plays a central role in achieving fast convergence under situations when the Lagrange multiplier associated to a solution of these conic optimization problems is not unique. We show that the strong calmness of the KKT solution mapping is equivalent to a local error bound for solutions of perturbed KKT system, and is also equivalent to the pseudo-isolated calmness of the stationary point mapping along with the calmness of the multiplier set map at the corresponding reference point. Sufficient conditions are also provided for the strong calmness by establishing the pseudo-isolated calmness of the stationary point mapping in terms of the noncriticality of the associated multiplier, and the calmness of the multiplier set mapping in terms of a relative interior condition for the multiplier set. These results cover and extend the existing ones in \cite{Hager99,Izmailov12} for nonlinear programming and in \cite{Cui16,Zhang17} for semidefinite programming., 21 pages

We study the convergence of stochastic fixed point iterations in the consistent case (in the sense of Butnariu and Fl{\aa}m (1995)) in several different settings, under decreasingly restrictive regularity assumptions of the fixed point mappings. The iterations are Markov chains and, for the purposes of this study, convergence is understood in very restrictive terms. We show that sufficient conditions for geometric (linear) convergence in expectation of stochastic projection algorithms presented in Nedi\'c (2011), are in fact necessary for geometric (linear) convergence in expectation more generally of iterated random functions., Comment: 29 pages, 4 figures

The Bregman divergence (Bregman distance, Bregman measure of distance) is a certain useful substitute for a distance, obtained from a well-chosen function (the "Bregman function"). Bregman functions and divergences have been extensively investigated during the last decades and have found applications in optimization, operations research, information theory, nonlinear analysis, machine learning and more. This paper re-examines various aspects related to the theory of Bregman functions and divergences. In particular, it presents many sufficient conditions which allow the construction of Bregman functions in a general setting and introduces new Bregman functions (such as a negative iterated log entropy). Moreover, it sheds new light on several known Bregman functions such as quadratic entropies, the negative Havrda-Charv\'at-Tsallis entropy, and the negative Boltzmann-Gibbs-Shannon entropy, and it shows that the negative Burg entropy, which is not a Bregman function according to the classical theory but nevertheless is known to have "Bregmanian properties", can, by our re-examination of the theory, be considered as a Bregman function. Our analysis yields several by-products of independent interest such as the introduction of the concept of relative uniform convexity (a certain generalization of uniform convexity), new properties of uniformly and strongly convex functions, and results in Banach space theory., Comment: Correction of a few very minor inaccuracies; added journal details (volume, page numbers, etc.); some references were updated

The aim of this paper is to analyze a class of consensus algorithms with finite-time or fixed-time convergence for dynamic networks formed by agents with first-order dynamics. In particular, in the analyzed class a single evaluation of a nonlinear function of the consensus error is performed per each node. The classical assumption of switching among connected graphs is dropped here, allowing to represent failures and intermittent communications between agents. Thus, conditions to guarantee finite and fixed-time convergence, even while switching among disconnected graphs, are provided. Moreover, the algorithms of the considered class are shown to be computationally simpler than previously proposed finite-time consensus algorithms for dynamic networks, which is an important feature in scenarios with computationally limited nodes and energy efficiency requirements such as in sensor networks. The performance of the considered consensus algorithms is illustrated through simulations, comparing it to existing approaches for dynamic networks with finite-time and fixed-time convergence. It is shown that the settling time of the considered algorithms grows slower when the number of nodes increases than with other consensus algorithms for dynamic networks., Please cite the publisher's version}. For the publisher's version and full citation details see: https://doi.org/10.1080/00207179.2018.1543896 The following links provide access, for a limited time, to a free copy of the publisher's version: https://www.tandfonline.com/eprint/FSW8JJRVPHMXJ3XUUXZH/full?target=10.1080/00207179.2018.1543896

In this paper, we establish results fully addressing two open problems proposed recently by I. Ivanov, see Nonlinear Analysis 69 (2008) 4012--4024, with respect to the convergence of the accelerated Riccati iteration method for solving the continuous coupled algebraic Riccati equation, or CCARE for short. These results confirm several desirable features of that method, including the monotonicity and boundedness of the sequences it produces, its capability of determining whether the CCARE has a solution, the extremal solutions it computes under certain circumstances, and its faster convergence than the regular Riccati iteration method.

We suggest simple modifications of the conditional gradient method for smooth optimization problems, which maintain the basic convergence properties, but reduce the implementation cost of each iteration essentially. Namely, we propose the step-size procedure without any line-search, and inexact solution of the direction finding subproblem. Preliminary results of computational tests confirm efficiency of the proposed modifications., 20 pages

In this paper we study the auxiliary problems that appear in $p$-order tensor methods for unconstrained minimization of convex functions with $\nu$-H\"{o}lder continuous $p$th derivatives. This type of auxiliary problems corresponds to the minimization of a $(p+\nu)$-order regularization of the $p$th order Taylor approximation of the objective. For the case $p=3$, we consider the use of Gradient Methods with Bregman distance. When the regularization parameter is sufficiently large, we prove that the referred methods take at most $\mathcal{O}(\log(\epsilon^{-1}))$ iterations to find either a suitable approximate stationary point of the tensor model or an $\epsilon$-approximate stationary point of the original objective function.

The aim of this paper is to investigate the existence of optimal controls for systems described by stochastic partial differential equations (SPDEs) with locally monotone coefficients controlled by different external forces which are feedback controls. To attain our objective we adapt the argument of H. Lisei, (Existence of optimal and epsilon-optimal controls for the stochastic Navier - Stokes equation, Nonlinear Analysis, 51, (2002) 95-118) where the existence of optimal control to the stochastic Navier-Stokes equation was studied. The results obtained in the present paper may be applied to demonstrate the existence of optimal control to various types of controlled SPDEs such as: a stochastic nonlocal equation and stochastic semilinear equations which are locally monotone equations; we also apply the result to a monotone equation such as the stochastic reaction diffusion equation and to a stochastic linear equation.

A class of semilinear parabolic reaction diffusion equations with multiple time delays is considered. These time delays and corresponding weights are to be optimized such that the associated solution of the delay equation is the best approximation of a desired state function. The differentiability of the mapping is proved that associates the solution of the delay equation to the vector of weights and delays. Based on an adjoint calculus, first-order necessary optimality conditions are derived. Numerical test examples show the applicability of the concept of optimizing time delays., Comment: 17 pages, 2 figures

The aim of this paper is to design a band-limited optimal input with power constraints for identifying a linear multi-input multi-output system. It is assumed that the nominal system parameters are specified. The key idea is to use the spectral decomposition theorem and write the power spectrum as $\phi_{u}(j\omega)=\frac{1}{2}H(j\omega)H^*(j\omega)$. The matrix $H(j\omega)$ is expressed in terms of a truncated basis for $\mathcal{L}^2\left(\left[-\omega_{\mbox{cut-off}},\omega_{\mbox{cut-off}}\right]\right)$. With this parameterization, the elements of the Fisher Information Matrix and the power constraints turn out to be homogeneous quadratics in the basis coefficients. The optimality criterion used are the well-known $\mathcal{D}-$optimality, $\mathcal{A}-$optimality, $\mathcal{T}-$optimality and $\mathcal{E}-$optimality. The resulting optimization problem is non-convex in general. A lower bound on the optimum is obtained through a bi-linear formulation of the problem, while an upper bound is obtained through a convex relaxation. These bounds can be computed efficiently as the associated problems are convex. The lower bound is used as a sub-optimal solution, the sub-optimality of which is determined by the difference in the bounds. Interestingly, the bounds match in many instances and thus, the global optimum is achieved. A discussion on the non-convexity of the optimization problem is also presented. Simulations are provided for corroboration.

Two optimization algorithms are proposed for solving a stochastic programming problem for which the objective function is given in the form of the expectation of convex functions and the constraint set is defined by the intersection of fixed point sets of nonexpansive mappings in a real Hilbert space. This setting of fixed point constraints enables consideration of the case in which the projection onto each of the constraint sets cannot be computed efficiently. Both algorithms use a convex function and a nonexpansive mapping determined by a certain probabilistic process at each iteration. One algorithm blends a stochastic gradient method with the Halpern fixed point algorithm. The other is based on a stochastic proximal point algorithm and the Halpern fixed point algorithm; it can be applied to nonsmooth convex optimization. Convergence analysis showed that, under certain assumptions, any weak sequential cluster point of the sequence generated by either algorithm almost surely belongs to the solution set of the problem. Convergence rate analysis illustrated their efficiency, and the numerical results of convex optimization over fixed point sets demonstrated their effectiveness.

In this paper, we consider an infinite horizon, continuous-review, stochastic inventory system in which cumulative customers' demand is price-dependent and is modeled as a Brownian motion. Excess demand is backlogged. The revenue is earned by selling products and the costs are incurred by holding/shortage and ordering, the latter consists of a fixed cost and a proportional cost. Our objective is to simultaneously determine a pricing strategy and an inventory control strategy to maximize the expected long-run average profit. Specifically, the pricing strategy provides the price $p_t$ for any time $t\geq0$ and the inventory control strategy characterizes when and how much we need to order. We show that an $(s^*,S^*,p^*)$ policy is optimal and obtain the equations of optimal policy parameters, where $p^*=\{p_t^*:t\geq 0\}$. Furthermore, we find that at each time $t$, the optimal price $p_t^*$ depends on the current inventory level $z$, and it is increasing in $[s^*,z^*]$ and is decreasing in $[z^*,\infty)$, where $z^*$ is a negative level., Comment: 29 pages, 2 figures

In this paper, we consider variations of the utility system considered by Vetta, in which users are grouped together. Our aim is to establish how grouping and cooperation among users affect performance bounds. We consider two types of grouping. The first type is from \cite{Zhang2014}, where each user belongs to a group of users having social ties with it. For this type of utility system, each user's strategy maximizes its social group utility function, giving rise to the notion of \emph{social-aware Nash equilibrium}. We prove that this social utility system yields to the bounding results of Vetta for non-cooperative system, thus establishing provable performance guarantees for the social-aware Nash equilibrium. For the second type of grouping, the set of users is partitioned into $l$ disjoint groups, where the users within a group cooperate to maximize their group utility function, giving rise to the notion of \emph{group Nash equilibrium}. In this case, each group can be viewed as a new user with vector-valued actions, and a 1/2 bound for the performance of group Nash equilibrium follows from the result of Vetta. But as we show tighter bounds involving curvature can be established. By defining the group curvature $c_{k_i}$ associated with group $i$ with $k_i$ users, we show that if the social utility function is nondecreasing and submodular, then any group Nash equilibrium achieves at least $1/(1+\max_{1\leq i\leq l}c_{k_i})$ of the optimal social utility, which is tighter than that for the case without grouping. As a special case, if each user has the same action space, then we have that any group Nash equilibrium achieves at least $1/(1+c_{k^*})$ of the optimal social utility, where $k^*$ is the least number of users among the $l$ groups. Finally, we present an example of a utility system for database assisted spectrum access to illustrate our results., Comment: This paper was accepted by Journal of Control and Decision

International audience; This note is an addendum to [1, 2], pointing out the differences between these papers and raising open questions.

One often encounters numerical difficulties in solving linear matrix inequality (LMI) problems obtained from $H_\infty$ control problems. We discuss the reason from the viewpoint of optimization, and provide necessary and sufficient conditions for LMI problem and its dual not to be strongly feasible. Moreover, we interpret them in terms of control system. In this analysis, facial reduction, which was proposed by Borwein and Wolkowicz, plays an important role. We show that a necessary and sufficient condition closely related to the existence of invariant zeros in the closed left-half plane in the system, and present a way to remove the numerical difficulty with the null vectors associated with invariant zeros in the closed left-half plane. Numerical results show that the numerical stability is improved by applying it.

In this article we develop a general theory of exact parametric penalty functions for constrained optimization problems. The main advantage of the method of parametric penalty functions is the fact that a parametric penalty function can be both smooth and exact unlike the standard (i.e. non-parametric) exact penalty functions that are always nonsmooth. We obtain several necessary and/or sufficient conditions for the exactness of parametric penalty functions, and for the zero duality gap property to hold true for these functions. We also prove some convergence results for the method of parametric penalty functions, and derive necessary and sufficient conditions for a parametric penalty function to not have any stationary points outside the set of feasible points of the constrained optimization problem under consideration. In the second part of the paper, we apply the general theory of exact parametric penalty functions to a class of parametric penalty functions introduced by Huyer and Neumaier, and to smoothing approximations of nonsmooth exact penalty functions. The general approach adopted in this article allowed us to unify and significantly sharpen many existing results on parametric penalty functions., This is a slightly edited version of Accepted Manuscript of an article published by Taylor & Francis in Optimization on 06/07/2017

In this work, we study the pseudomonotonicity of multivalued operators from the point of view of polarity, in an analogous way as the well-known monotone polar due to Mart\'inez-Legaz and Svaiter, and the quasimonotone polar recently introduced by Bueno and Cotrina. We show that this new polar, adapted for pseudomonotonicity, possesses analogous properties to the monotone and quasimonotone polar, among which are a characterization of pseudomonotonicity, maximality and pre-maximality. Furthermore, we characterize the notion of $D$-maximal pseudomonotonicity introduced by Hadjisavvas. We conclude this work studying the connections between pseudomonotonicity and variational inequality problems., Comment: 14 pages

The vertical alignment optimization problem for road design aims to generate a vertical alignment of a new road with a minimum cost, while satisfying safety and design constraints. We present a new model called multi-haul quasi network flow (MH-QNF) for vertical alignment optimization that improves the accuracy and reliability of previous mixed integer linear programming models. We evaluate the performance of the new model compared to two state-of-the-art models in the field: the complete transportation graph (CTG) and the quasi network flow (QNF) models. The numerical results show that, within a 1% relative error, the proposed model is robust and solves more than 93% of test problems compared to 82% for the CTG and none for the QNF. Moreover, the MH-QNF model solves the problems approximately 8 times faster than the CTG model., Comment: 23 pages, 4 figures The Version of Record of this manuscript has been published and is available in Engineering Optimization (GENO); Estimated publication date: Jan 12, 2017 (online); http://dx.doi.org/10.1080/0305215X.2016.1271880

In this paper we study variational inequalities in a real Hilbert space, which are governed by a strongly monotone and Lipschitz continuous operator $F$ over a closed and convex set $C$. We assume that the set $C$ can be outerly approximated by the fixed point sets of a sequence of certain quasi-nonexpansive operators called cutters. We propose an iterative method the main idea of which is to project at each step onto a particular half-space constructed by using the input data. Our approach is based on a method presented by Fukushima in 1986, which has recently been extended by several authors. In the present paper we establish strong convergence in Hilbert space. We emphasize that to the best of our knowledge, Fukushima's method has so far been considered only in the Euclidean setting with different conditions on $F$. We provide several examples for the case where $C$ is the common fixed point set of a finite number of cutters with numerical illustrations of our theoretical results.

Several optimization schemes have been known for convex optimization problems. However, numerical algorithms for solving nonconvex optimization problems are still underdeveloped. A significant progress to go beyond convexity was made by considering the class of functions representable as differences of convex functions. In this paper, we introduce a generalized proximal point algorithm to minimize the difference of a nonconvex function and a convex function. We also study convergence results of this algorithm under the main assumption that the objective function satisfies the Kurdyka–ᴌojasiewicz property.

In the literature, necessary and sufficient conditions in terms of variational inequalities are introduced to characterize minimizers of convex set valued functions with values in a conlinear space. Similar results are proved for a weaker concept of minimizers and weaker variational inequalities. The implications are proved using scalarization techniques that eventually provide original problems, not fully equivalent to the set-valued counterparts. Therefore, we try, in the course of this note, to close the network among the various notions proposed. More specifically, we prove that a minimizer is always a weak minimizer, and a solution to the stronger variational inequality always also a solution to the weak variational inequality of the same type. As a special case we obtain a complete characterization of efficiency and weak efficiency in vector optimization by set-valued variational inequalities and their scalarizations. Indeed this might eventually prove the usefulness of the set-optimization approach to renew the study of vector optimization.

We introduce a penalty term-based splitting algorithm with inertial effects designed for solving monotone inclusion problems involving the sum of maximally monotone operators and the convex normal cone to the (nonempty) set of zeros of a monotone and Lipschitz continuous operator. We show weak ergodic convergence of the generated sequence of iterates to a solution of the monotone inclusion problem, provided a condition expressed via the Fitzpatrick function of the operator describing the underlying set of the normal cone is verified. Under strong monotonicity assumptions we can even show strong nonergodic convergence of the iterates. This approach constitutes the starting point for investigating from a similar perspective monotone inclusion problems involving linear compositions of parallel-sum operators and, further, for the minimization of a complexly structured convex objective function subject to the set of minima of another convex and differentiable function., arXiv admin note: text overlap with arXiv:1306.0352

The hierarchical structure of production planning has the advantage of assigning different decision variables to their respective time horizons and therefore ensures their manageability. However, the restrictive structure of this top-down approach implying that upper level decisions are the constraints for lower level decisions also has its shortcomings. One problem that occurs is that deterministic mixed integer decision problems are often used for long-term planning, but the real production system faces a set of stochastic influences. Therefore, a planned utilisation factor has to be included into this deterministic aggregate planning problem. In practice, this decision is often based on past data and not consciously taken. In this paper, the effect of long-term forecast error on the optimal planned utilisation factor is evaluated for a production system facing stochastic demand and the benefit of exploiting this decision's potential is discussed. Overall costs including capacity, backorder and inventory costs, are determined with simulation for different multi-stage and multi-item production system structures. The results show that the planned utilisation factor used in the aggregate planning problem has a high influence on optimal costs. Additionally, the negative effect of forecast errors is evaluated and discussed in detail for different production system environments., production planning, MRP II, simulation, aggregate production planning, demand and forecast uncertainty

In this paper, a leader-following coordination problem of heterogeneous multi-agent systems is considered under switching topologies where each agent is subject to some local (unbounded) disturbances. While these unknown disturbances may disrupt the performance of agents, a disturbance observer based approach is employed to estimate and reject them. Varying communication topologies are also taken into consideration, and their byproduct difficulties are overcome by using common Lyapunov function techniques. According to the available information in difference cases, two disturbance observer based protocols are proposed to solve this problem. Their effectiveness is verified by simulations., Comment: 12 pages, 4 figures, 2 tables

We present a delayed feedback control (DFC) mechanism for stabilizing cycles of one-dimensional discrete time systems. In particular, we consider a DFC for stabilizing -cycles of a differentiable function of the formwhere with . Following an approach of Morgul, we construct a map whose fixed points correspond to -cycles of . We then analyse the local stability of the above DFC mechanism by evaluating the stability of the corresponding equilibrium points of . We associate to each periodic orbit of an explicit polynomial whose Schur stability corresponds to the stability of the DFC on that orbit. This polynomial is the characteristic polynomial of a Jacobian matrix that lies in a large class of matrices that encompasses the usual ‘companion matrices’ found in linear algebra; the primary purpose of this paper is to show that this polynomial may be expressed in a surprisingly simple form. An example indicating the efficacy of this method is provided.

In this paper, we revisit the augmented Lagrangian method for a class of nonsmooth convex optimization. We present the Lagrange optimality system of the augmented Lagrangian associated with the problems, and establish its connections with the standard optimality condition and the saddle point condition of the augmented Lagrangian, which provides a powerful tool for developing numerical algorithms. We apply a linear Newton method to the Lagrange optimality system to obtain a novel algorithm applicable to a variety of nonsmooth convex optimization problems arising in practical applications. Under suitable conditions, we prove the nonsingularity of the Newton system and the local convergence of the algorithm., 19 pages