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

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

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

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).

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

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.

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

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.

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.

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.

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.

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.

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.

Our purpose of this paper is to study stochastic control problem for systems driven by mean-field stochastic differential equations with elephant memory, in the sense that the system (like the elephants) never forgets its history. We study both the finite horizon case and the infinite time horizon case. - In the finite horizon case, results about existence and uniqueness of solutions of such a system are given. Moreover, we prove sufficient as well as necessary stochastic maximum principles for the optimal control of such systems. We apply our results to solve a mean-field linear quadratic control problem. - For infinite horizon, we derive sufficient and necessary maximum principles. As an illustration, we solve an optimal consumption problem from a cash flow modelled by an elephant memory mean-field system.

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

Risk measure is a fundamental concept in finance and in the insurance industry, it is used to adjust life insurance rates. In this current paper, we will study dynamic risk measures by means of backward stochastic Volterra integral equations (BSVIEs) with jumps. We prove a comparison theorem for such a type of equations. Since the solution of a BSVIEs is not a semimartingale in general, we will discuss some particular semimartingale issues., Comment: 11 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

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 the late sixties, N. Shor and B. Polyak independently proposed optimal first-order methods for non-smooth convex optimization problems. In 1982 A. Nemirovski proposed optimal first-order methods for smooth convex optimization problems, which utilized auxiliary line search. In 1985 A. Nemirovski and Yu. Nesterov proposed a parametric family of optimal first-order methods for convex optimization problems with intermediate smoothness. In 2013 Yu. Nesterov proposed a universal gradient method which combined all the good properties of the previous methods, except the possibility of using auxiliary line search. One can typically observe that in practice auxiliary line search improves performance for many tasks. In this paper, we propose the apparently first such method of non-smooth convex optimization allowing for the use of the line search procedure. Moreover, it is based on the universal gradient method, which does not require any a priori information about the actual degree of smoothness of the problem. Numerical experiments demonstrate that the proposed method is, in some cases, considerably faster than Nesterov's universal gradient method.

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

This paper presents a non-intrusive framework for integrating existing unsteady partial differential equation (PDE) solvers into a parallel-in-time simultaneous optimization algorithm. The time-parallelization is provided by the non-intrusive software library XBraid, which applies an iterative multigrid reduction technique to the time domain of existing time-marching schemes for solving unsteady PDEs. Its general user-interface has been extended for computing adjoint sensitivities such that gradients of output quantities with respect to design changes can be computed parallel-in-time alongside with the primal PDE solution. In this paper, the primal and adjoint XBraid iterations are embedded into a simultaneous optimization framework, namely the One-shot method. In this method, design updates towards optimality are employed after each state and adjoint update such that optimality and feasibility of the design and the PDE solution are reached simultaneously. The time-parallel optimization method is validated on an advection-dominated flow control problem which shows significant speedup over a classical time-serial optimization algorithm.

The solution of inverse problems in a variational setting finds best estimates of the model parameters by minimizing a cost function that penalizes the mismatch between model outputs and observations. The gradients required by the numerical optimization process are computed using adjoint models. Exponential integrators are a promising family of time discretizations for evolutionary partial differential equations. In order to allow the use of these discretizations in the context of inverse problems adjoints of exponential integrators are required. This work derives the discrete adjoint formulae for a W-type exponential propagation iterative methods of Runge-Kutta type (EPIRK-W). These methods allow arbitrary approximations of the Jacobian while maintaining the overall accuracy of the forward integration. The use of Jacobian approximation matrices that do not depend on the model state avoids the complex calculation of Hessians in the discrete adjoint formulae, and allows efficient adjoint code generation via algorithmic differentiation. We use the discrete EPIRK-W adjoints to solve inverse problems with the Lorenz-96 model and a computational magnetics benchmark test. Numerical results validate our theoretical derivations.

In the literature, there are a few researches to design some parameters in the Proximal Point Algorithm (PPA), especially for the multi-objective convex optimizations. Introducing some parameters to PPA can make it more flexible and attractive. Mainly motivated by our recent work (Bai et al., A parameterized proximal point algorithm for separable convex optimization, Optim. Lett. (2017) doi: 10.1007/s11590-017-1195-9), in this paper we develop a general parameterized PPA with a relaxation step for solving the multi-block separable structured convex programming. By making use of the variational inequality and some mathematical identities, the global convergence and the worst-case $\mathcal{O}(1/t)$ convergence rate of the proposed algorithm are established. Preliminary numerical experiments on solving a sparse matrix minimization problem from statistical learning validate that our algorithm is more efficient than several state-of-the-art algorithms.

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.

We suggest simple implementable modifications of conditional gradient and gradient projection methods for smooth convex optimization problems in Hilbert spaces. Usually, the custom methods attain only weak convergence. We prove strong convergence of the new versions and establish their complexity estimates, which appear similar to the convergence rate of the weakly convergent versions., 17 pages

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

In this article we continue our investigation of the iterative regularization method for optimization problems based on Bregman distances. The optimization problems are subject to pointwise inequality constraints in $L^2(\Omega)$. We provide an estimate for the noise error for perturbed data, which can be used to construct an a priori stopping rule. Furthermore we show how to implement our method with a semi-smooth Newton method using finite elements and present numerical results for the stopping rule.