Search

For time-dependent PDEs, the numerical schemes can be rendered bound-preserving without losing conservation and accuracy by a postprocessing procedure of solving a constrained minimization in each time step. Such a constrained optimization can be formulated as a nonsmooth convex minimization, which can be efficiently solved by first order optimization methods, if using the optimal algorithm parameters. By analyzing the asymptotic linear convergence rate of the generalized Douglas--Rachford splitting method, optimal algorithm parameters can be approximately expressed as a simple function of the number of out-of-bounds cells. We demonstrate the efficiency of this simple choice of algorithm parameters by applying such a limiter to cell averages of a discontinuous Galerkin scheme solving phase field equations for 3D demanding problems. Numerical tests on a sophisticated 3D Cahn--Hilliard--Navier--Stokes system indicate that the limiter is high order accurate, very efficient, and well suited for large-scale simulations. For each time step, it takes at most 20 iterations for the Douglas--Rachford splitting to enforce bounds and conservation up to the round-off error, for which the computational cost is at most 80N with N being the total number of cells. [ABSTRACT FROM AUTHOR]

We propose a trust-region stochastic sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with stochastic objectives and deterministic equality constraints. We consider a fully stochastic setting, where at each step a single sample is generated to estimate the objective gradient. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices (i.e., Hessians without modification) in SQP subproblems. As a trust-region method for constrained optimization, our algorithm must address an infeasibility issue---the linearized equality constraints and trust-region constraints may lead to infeasible SQP subproblems. In this regard, we propose an adaptive relaxation technique to compute the trial step, consisting of a normal step and a tangential step. To control the lengths of these two steps while ensuring a scale-invariant property, we adaptively decompose the trust-region radius into two segments, based on the proportions of the rescaled feasibility and optimality residuals to the rescaled full KKT residual. The normal step has a closed form, while the tangential step is obtained by solving a trust-region subproblem, to which a solution ensuring the Cauchy reduction is sufficient for our study. We establish a global almost sure convergence guarantee for TR-StoSQP and illustrate its empirical performance on both a subset of problems in the CUTEst test set and constrained logistic regression problems using data from the LIBSVM collection. [ABSTRACT FROM AUTHOR]

Classical primal-dual algorithms attempt to solve max∣1 miι⅛ £(æ, μ) by alternately minimizing over the primal variable x through primal descent and maximizing the dual variable μ through dual ascent. However, when Z2(x, μ) is highly nonconvex with complex constraints in x, the minimization over x may not achieve global optimality and, hence, the dual ascent step loses its valid intuition. This observation motivates us to propose a new class of primal-dual algorithms for nonconvex constrained optimization with the key feature to reverse dual ascent to a conceptually new dual descent, in a sense, elevating the dual variable to the same status as the primal variable. Surprisingly, this new dual scheme achieves some best iteration complexities for solving nonconvex optimization problems. In particular, when the dual descent step is scaled by a fractional constant, we name it scaled dual descent (SDD), otherwise, unsealed dual descent (UDD). For nonconvex multiblock optimization with nonlinear equality constraints, we propose SDD-alternating direction method of multipliers (SDD-ADMM) and show that it finds an e-stationary solution in O{e~4) iterations. The complexity is further improved to O{e~3) and O{e~2) under proper conditions. We also propose UDD-augmented Lagrangian method (UDD-ALM), combining UDD with ALM, for weakly convex minimization over affine constraints. We show that UDD-ALM finds an e-stationary solution in O{e~2) iterations. These complexity bounds for both algorithms either achieve or improve the best-known results in the ADMM and ALM literature. Moreover, SDD-ADMM addresses a longstanding limitation of existing ADMM frameworks. [ABSTRACT FROM AUTHOR]

The Fritz John (FJ) and Karush--Kuhn--Tucker (KKT) conditions are fundamental tools for characterizing minimizers and form the basis of almost all methods for constrained optimization. Since the seminal works of Fritz John, Karush, Kuhn, and Tucker, FJ/KKT conditions have been enhanced by adding extra necessary conditions. Such an extension was initially proposed by Hestenes in the 1970s and later extensively studied by Bertsekas and collaborators. In this work, we revisit enhanced KKT stationarity for standard (smooth) nonlinear programming. We argue that every KKT point satisfies the usual enhanced versions found in the literature. Therefore, enhanced KKT stationarity only concerns the Lagrange multipliers. We then analyze some properties of the corresponding multipliers under the quasi-normality constraint qualification (QNCQ), showing in particular that the set of so-called quasinormal multipliers is compact under QNCQ. Also, we report some consequences of introducing an extra abstract constraint to the problem. Given that enhanced FJ/KKT concepts are obtained by aggregating sequential conditions to FJ/KKT, we discuss the relevance of our findings with respect to the well-known sequential optimality conditions, which have been crucial in generalizing the global convergence of a well-established safeguarded augmented Lagrangian method. Finally, we apply our theory to mathematical programs with complementarity constraints and multiobjective problems, improving and elucidating previous results in the literature. [ABSTRACT FROM AUTHOR]

A popular approach to minimizing a finite sum of smooth convex functions is stochastic gradient descent (SGD) and its variants. Fundamental research questions associated with SGD include (i) how to find a lower bound on the number of times that the gradient oracle of each individual function must be assessed in order to find an e-minimizer of the overall ob jective; (ii) how to design algorithms which guarantee finding an e-minimizer of the overall ob jective in expectation no more than a certain number of times (in terms of 1/\epsilon) that the gradient oracle of each function needs to be assessed (i.e., upper bound). If these two bounds are at the same order of magnitude, then the algorithms may be called optimal. Most existing results along this line of research typically assume that the functions in the ob jective share the same condition number. In this paper, the first model we study is the problem of minimizing the sum of finitely many strongly convex functions whose condition numbers are all different. We propose an SGD-based method for this model and show that it is optimal in gradient computations, up to a logarithmic factor. We then consider a constrained separate block optimization model and present lower and upper bounds for its gradient computation complexity. Next, we propose solving the Fenchel dual of the constrained block optimization model via generalized SSNM, which we introduce earlier, and show that it yields a lower iteration complexity than solving the original model by the ADMM-type approach. Finally, we extend the analysis to the general composite convex optimization model and obtain gradient-computation complexity results under certain conditions. [ABSTRACT FROM AUTHOR]

We propose two approaches, based on Riemannian optimization for computing a stochastic approximation of the pth root of a stochastic matrix A. In the first approach, the approximation is found in the Riemannian manifold of positive stochastic matrices. In the second approach, we introduce the Riemannian manifold of positive stochastic matrices sharing with A the Perron eigenvector and we compute the approximation of the pth root of A in such a manifold. This way, differently from the available methods based on constrained optimization, A and its pth root approximation share the Perron eigenvector. Such a property is relevant, from a modeling point of view, in the embedding problem for Markov chains. The extended numerical experimentation shows that, in the first approach, the Riemannian optimization methods are generally faster and more accurate than the available methods based on constrained optimization. In the second approach, even though the stochastic approximation of the pth root is found in a smaller set, the approximation is generally more accurate than the one obtained by standard constrained optimization. [ABSTRACT FROM AUTHOR]

In this paper, we consider a Markov decision process (MDP) with a Borel state space X⊔ {Δ}, where Δ is an absorbing state (cemetery), and a Borel action space A. We consider the space of finite occupation measures restricted on X\times A and the extreme points in it. It is possible that some strategies have infinite occupation measures. Nevertheless, we prove that every finite extreme occupation measure is generated by a deterministic stationary strategy. Then, for this MDP, we consider a constrained problem with total undiscounted criteria and J constraints, where the cost functions are nonnegative. By assumption, the strategies inducing infinite occupation measures are not optimal. Then our second main result is that, under mild conditions, the solution to this constrained MDP is given by a mixture of no more than J +1 occupation measures generated by deterministic stationary strategies. [ABSTRACT FROM AUTHOR]

The presence of second-order smoothness for objective functions of optimization problems can provide valuable information about their stability properties and help us design efficient numerical algorithms for solving these problems. Such second-order information, however, cannot be expected in various constrained and composite optimization problems since we often have to express their objective functions in terms of extended-real-valued functions for which the classical second derivative may not exist. One powerful geometrical tool to use for dealing with such functions is the concept of twice epi-differentiability. In this paper, we study a stronger version of this concept, called strict twice epi-differentiability. We characterize this concept for certain composite functions and use it to establish the equivalence of metric regularity and strong metric regularity for a class of generalized equations at their nondegenerate solutions. Finally, we present a characterization of continuous differentiability of the proximal mapping of our composite functions. [ABSTRACT FROM AUTHOR]

This paper proposes a path-based approach for the minimization of a continuously differentiable function over sparse symmetric sets, which is a hard problem that exhibits a restrictiveness-hierarchy of necessary optimality conditions. To achieve the more restrictive conditions in the hierarchy, state-of-the-art algorithms require a support optimization oracle that must exactly solve the problem in smaller dimensions. The path-based approach developed in this study produces a path-based optimality condition, which is placed well in the restrictiveness-hierarchy, and a method to achieve it that does not require a support optimization oracle and, moreover, is projection-free. In the development process, new results are derived for the regularized linear minimization problem over sparse symmetric sets, which give additional means to identify optimal solutions for convex and concave objective functions. We complement our results with numerical examples. [ABSTRACT FROM AUTHOR]

An optimization algorithm for nonsmooth nonconvex constrained optimization problems with upper-C² objective functions is proposed and analyzed. Upper-C² is a weakly concave property that exists in difference of convex (DC) functions and arises naturally in many applications, particularly certain classes of solutions to parametric optimization problems e.g., recourse of stochastic programming and projection onto closed sets. The algorithm can be viewed as an extension of sequential quadratic programming (SQP) to nonsmooth problems with upper-² objectives or a simplified bundle method. It is globally convergent with bounded algorithm parameters that are updated with a trust-region criterion. The algorithm handles general smooth constraints through linearization and uses a line search to ensure progress. The potential inconsistencies from the linearization of the constraints are addressed through a penalty method. The capabilities of the algorithm are demonstrated by solving both simple upper-² problems and a real-world optimal power flow problem used in current power grid industry practices. [ABSTRACT FROM AUTHOR]

In this paper we develop accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient (LLCG), which is beyond the well-studied class of convex optimization with Lipschitz continuous gradient. In particular, we first consider unconstrained convex optimization with LLCG and propose accelerated proximal gradient (APG) methods for solving it. The proposed APG methods are equipped with a verifiable termination criterion and enjoy an operation complexity of O(ε1/2 log ε¹) and\scrO (log ε1) for finding an ε-residual solution of an unconstrained convex and strongly convex optimization problem, respectively. We then consider constrained convex optimization with LLCG and propose a first-order proximal augmented Lagrangian method for solving it by applying one of our proposed APG methods to approximately solve a sequence of proximal augmented Lagrangian subproblems. The resulting method is equipped with a verifiable termination criterion and enjoys an operation complexity of O(ε¹ log ε¹) and O(ε1/2 log ε¹) for finding an ε-KKT solution of a constrained convex and strongly convex optimization problem, respectively. All the proposed methods in this paper are parameter-free or almost parameter-free except that knowledge of the convexity parameter is required. In addition, preliminary numerical results are presented to demonstrate the performance of our proposed methods. To the best of our knowledge, no prior studies have been conducted to investigate accelerated first-order methods with complexity guarantees for convex optimization with LLCG. All the complexity results obtained in this paper are new. [ABSTRACT FROM AUTHOR]

The problem of interest is the minimization of a nonlinear function subject to nonlinear equality constraints using a sequential quadratic programming (SQP) method. The minimization must be performed while observing only noisy evaluations of the objective and constraint functions. In order to obtain stability, the classical SQP method is modified by relaxing the standard Armijo line search based on the noise level in the functions, which is assumed to be known. Convergence theory is presented giving conditions under which the iterates converge to a neighborhood of the solution characterized by the noise level and the problem conditioning. The analysis assumes that the SQP algorithm does not require regularization or trust regions. Numerical experiments indicate that the relaxed line search improves the practical performance of the method on problems involving uniformly distributed noise, compared to a standard line search. [ABSTRACT FROM AUTHOR]

The space mapping technique is used to efficiently solve complex optimization problems. It combines the accuracy of fine model simulations with the speed of coarse model optimizations to approximate the solution of the fine model optimization problem. In this paper, we propose novel space mapping methods for solving shape optimization problems constrained by PDEs. We present the methods in a Riemannian setting based on Steklov--Poincaré-type metrics and discuss their numerical discretization and implementation. We investigate the numerical performance of the space mapping methods on several model problems. Our numerical results highlight the methods' great efficiency for solving complex shape optimization problems. [ABSTRACT FROM AUTHOR]

This paper considers data-driven chance-constrained stochastic optimization problems in a Bayesian framework. Bayesian posteriors afford a principled mechanism to incorporate data and prior knowledge into stochastic optimization problems. However, the computation of Bayesian posteriors is typically an intractable problem and has spawned a large literature on approximate Bayesian computation. Here, in the context of chance-constrained optimization, we focus on the question of statistical consistency (in an appropriate sense) of the optimal value, computed using an approximate posterior distribution. To this end, we rigorously prove a frequentist consistency result demonstrating the convergence of the optimal value to the optimal value of a fixed, parameterized constrained optimization problem. We augment this by also establishing a probabilistic rate of convergence of the optimal value. We also prove the convex feasibility of the approximate Bayesian stochastic optimization problem. Finally, we demonstrate the utility of our approach on an optimal staffing problem for an M/M/c queueing model. [ABSTRACT FROM AUTHOR]

We propose efficient numerical schemes for implementing the natural gradient descent (NGD) for a broad range of metric spaces with applications to PDE-based optimization problems. Our technique represents the natural gradient direction as a solution to a standard least-squares problem. Hence, instead of calculating, storing, or inverting the information matrix directly, we apply efficient methods from numerical linear algebra. We treat both scenarios where the Jacobian, i.e., the derivative of the state variable with respect to the parameter, is either explicitly known or implicitly given through constraints. We can thus reliably compute several natural NGDs for a large-scale parameter space. In particular, we are able to compute Wasserstein NGD in thousands of dimensions, which was believed to be out of reach. Finally, our numerical results shed light on the qualitative differences between the standard gradient descent and various NGD methods based on different metric spaces in nonconvex optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the linear programming (LP) formulation for deep reinforcement learning. The number of the constraints depends on the size of state and action spaces, which makes the problem intractable in large or continuous environments. The general augmented Lagrangian method suffers the double-sampling obstacle in solving the linear program. Motivated from the updates of the multipliers, we overcome the obstacles in minimizing the augmented Lagrangian function by replacing the intractable conditional expectations with the multipliers. Therefore, a deep parameterized augmented Lagrangian method is proposed. The replacement provides a promising breakthrough to integrate the two steps in the augmented Lagrangian method into a single quadratic penalty problem. A general theoretical analysis shows that the solutions generated from a sequence of the constrained optimization converge to the optimal solution of the linear program if the error is controlled properly. A theoretical analysis on the quadratic penalty algorithm without using target networks under a neural tangent kernel setting shows the residual can be arbitrarily small if the parameter in the network and the optimization algorithm is chosen suitably. Preliminary experiments illustrate that our method is competitive with other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

We propose a double-loop inexact accelerated proximal gradient (APG) method for a strongly convex composite optimization problem with two smooth components of different smoothness constants and computational costs. Compared to APG, the inexact APG can reduce the time complexity for finding a near-stationary point when one smooth component has higher computational cost but a smaller smoothness constant than the other. The strongly convex composite optimization problem with this property arises from subproblems of a regularized augmented Lagrangian method for affine-constrained composite convex optimization and also from the smooth approximation for bilinear saddle-point structured nonsmooth convex optimization. We show that the inexact APG method can be applied to these two problems and reduce the time complexity for finding a near-stationary solution. Numerical experiments demonstrate significantly higher efficiency of our methods over an optimal primal-dual first-order method by Hamedani and Aybat [SIAM J. Optim., 31 (2021), pp. 1299--1329] and the gradient sliding method by Lan, Ouyang, and Zhou [arXiv2101.00143, 2021]. [ABSTRACT FROM AUTHOR]

We present a framework for analyzing convergence and local rates of convergence of a class of descent algorithms, assuming the objective function is weakly convex. The framework is general, in the sense that it combines the possibility of explicit iterations (based on the gradient or a subgradient at the current iterate), implicit iterations (using a subgradient at the next iteration, like in the proximal schemes), as well as iterations when the associated subgradient is specially constructed and does not correspond either to the current or the next point (this is the case of descent steps in bundle methods). Under the subdifferential-based error bound on the distance to critical points, linear rates of convergence are established. Our analysis applies, among other techniques, to prox-descent for decomposable functions, the proximal-gradient method for a sum of functions, redistributed bundle methods, and a class of algorithms that can be cast in the feasible descent framework for constrained optimization. [ABSTRACT FROM AUTHOR]

Given a closed convex set A in a Banach space X, motivated by the continuity and Fréchet differentiability of A introduced, respectively, in [D. Gale and V. Klee, Math. Scand., 7 (1959), pp. 379-391] and [X. Y. Zheng, SIAM J. Optim., 30 (2020), pp. 490-512], this paper considers the Cp-differentiability, subdifferentiability, and G\^ateaux differentiability of A. Using the technique of variational analysis, it is proved that A is Cp-differentiable (resp., subdifferentiable or G\^ateaux differentiable) if and only if for every continuous convex function f : X → R with infx∈A f(x) > infx∈X f(x) the corresponding constrained optimization problem PA(f) is 2/p-order-well-posed solvable (resp., generalized well-posed solvable or weak well-posed solvable). It is also proved that if the conjugate function f* of a continuous convex function f on X is Cp-differentiable on dom(f*), then for every closed convex set A in X with infx∈A f(x) > -∞ the corresponding optimization problem PA(f) is 2/p-order-well-posed solvable. As a byproduct, every constrained convex optimization problem with a strongly convex quadratic objective function is proved to be globally second-order-well-posed solvable. Our main results are new even in the case of finite dimensional spaces. [ABSTRACT FROM AUTHOR]

We study nonconvex homogeneous quadratically constrained quadratic optimization with m(∈ {1, 2}) constraints, denoted by (QQm). (QQ2) contains (QQ1), the trust region subproblem (TRS) and its generalization (GTRS), and the ellipsoid regularized total least squares problem as special cases. It is known that there is a necessary and sufficient optimality condition for the global minimizer of (QQ2). In this paper, we first show that any local minimizer of (QQ1) is globally optimal. Unlike its special case (TRS) with at most one local nonglobal minimizer, (QQ2) may have infinitely many local nonglobal minimizers. At any local nonglobal minimizer of (QQ2), both the linear independence constraint qualification and the strict complementary slackness condition hold, and the Hessian of the Lagrangian has exactly one negative eigenvalue. As the main contribution, we prove that the standard second-order sufficient optimality condition for any strict local nonglobal minimizer of (QQ2) remains necessary. It turns out that finding all local nonglobal minimizers of (GTRS) or proving the nonexistence can be done in polynomial time. More applications and the impossibility of extending our main result are discussed. [ABSTRACT FROM AUTHOR]

We present a new algorithm for infinite-dimensional optimization with general constraints, called ALESQP. In short, ALESQP is an augmented Lagrangian method that penalizes inequality constraints and solves equality-constrained nonlinear optimization subproblems at every iteration. The subproblems are solved using a matrix-free trust-region sequential quadratic programming (SQP) method that takes advantage of iterative, i.e., inexact linear solvers, and is suitable for large-scale applications. A key feature of ALESQP is a constraint decomposition strategy that allows it to exploit problem-specific variable scalings and inner products. We analyze convergence of ALESQP under different assumptions. We show that strong accumulation points are stationary. Consequently, in finite dimensions ALESQP converges to a stationary point. In infinite dimensions we establish that weak accumulation points are feasible in many practical situations. Under additional assumptions we show that weak accumulation points are stationary. We present several infinite-dimensional examples where ALESQP shows remarkable discretization-independent performance in all of its iterative components, requiring a modest number of iterations to meet constraint tolerances at the level of machine precision. Also, we demonstrate a fully matrix-free solution of an infinite-dimensional problem with nonlinear inequality constraints. [ABSTRACT FROM AUTHOR]

We propose a novel preconditioned inexact primal-dual interior point method for constrained convex quadratic programming problems. The algorithm we describe invokes the preconditioned conjugate gradient method on a new reduced Schur complement Karush-Kuhn-Tucker (KKT) system in implicit form. In contrast to standard approaches, the Schur complement formulation we consider enables reuse of the factorization of the KKT matrix with rows and columns corresponding to inequality constraints excluded across all interior point iterations. Further, two new preconditioners are presented for the resulting reduced system that alleviate the ill-conditioning associated with slack variables in primal-dual interior point methods. Each of the preconditioners we propose also provably reduces the number of unique eigenvalues for the coefficient matrix and thus the conjugate gradient method iteration count. One preconditioner is efficient when the number of equality constraints is small, while the other is efficient when the number of remaining degrees of freedom is small. Numerical experiments with synthetic problems and problems from the Maros-Mészáros quadratic programming collection show that our preconditioned inexact interior point solvers are effective at improving conditioning and reducing cost. Across all test problems for which the direct method is not fastest, our preconditioned methods achieve a reduction in cost by a geometric mean of 1.432 relative to the best alternative preconditioned method for each problem. [ABSTRACT FROM AUTHOR]

This paper focuses on a time-varying constrained nonconvex optimization problem, and considers the synthesis and analysis of online regularized primal-dual gradient methods to track a Karush-Kuhn-Tucker (KKT) trajectory. The proposed regularized primal-dual gradient method is implemented in a running fashion, in the sense that the underlying optimization problem changes during the execution of the algorithms. In order to study its performance, we first derive its continuous-time limit as a system of differential inclusions. We then study sufficient conditions for tracking a KKT trajectory, and also derive asymptotic bounds for the tracking error (as a function of the time-variability of a KKT trajectory). Further, we provide a set of sufficient conditions for the KKT trajectories not to bifurcate or merge, and also investigate the optimal choice of the parameters of the algorithm. Illustrative numerical results for a time-varying nonconvex problem are provided. [ABSTRACT FROM AUTHOR]

The design of key nonlinear systems often requires the use of expensive blackbox simulations presenting inherent discontinuities whose positions in the variable space cannot be analytically predicted. Without further precautions, the solution of related optimization problems leads to design configurations which may be close to discontinuities of the blackbox output functions. These discontinuities may betray unsafe regions of the design space, such as nonlinear resonance regions. To account for possible changes of operating conditions, an acceptable solution must be away from unsafe regions of the space of variables. The objective of this work is to solve a constrained blackbox optimization problem with the additional constraint that the solution should be outside unknown zones of discontinuities or strong variations of the objective function or the constraints. The proposed approach is an extension of the mesh adaptive direct search (Mads) algorithm and aims at building a series of inner approximations of these zones. The algorithm, called DiscoMADS, relies on two main mechanisms: revealing discontinuities and progressively escaping the surrounding zones. A convergence analysis supports the algorithm and preserves the optimality conditions of Mads. Numerical tests are conducted on analytical problems and on three engineering problems illustrating the following possible applications of the algorithm: the design of a simplified truss, the synthesis of a chemical component, and the design of a turbomachine blade. The DiscoMADS algorithm successfully solves these problems by providing a feasible solution away from discontinuous regions. [ABSTRACT FROM AUTHOR]

In this paper, we study a fully composite formulation of convex optimization problems, which includes, as a particular case, the problems with functional constraints, max-type minimization problems, and problems with simple nondifferentiable components. We treat all these formulations in a unified way, highlighting the existence of very natural optimization schemes of different order p ≥ 1. As the result, we obtain new high-order (p ≥ 2) optimization methods for composite formulation. We prove the global convergence rates for them under the most general conditions. Assuming that the upper-level component of our objective function is subhomogeneous, we develop efficient modification of the basic fully composite first-order and second-order methods and propose their accelerated variants. [ABSTRACT FROM AUTHOR]

A regularized minimization model with l1-norm penalty (RP) is introduced for training the autoencoders that belong to a class of two-layer neural networks. We show that the RP can act as an exact penalty model which shares the same global minimizers, local minimizers, and d(irectional)-stationary points with the original regularized model under mild conditions. We construct a bounded box region that contains at least one global minimizer of the RP, and propose a linearly constrained regularized minimization model with l1-norm penalty (LRP) for training autoencoders. A smoothing proximal gradient algorithm is designed to solve the LRP. Convergence of the algorithm to a generalized d-stationary point of the RP and LRP is delivered. Comprehensive numerical experiments convincingly illustrate the efficiency as well as the robustness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Error bound analysis, which estimates the distance of a point to the solution set of an optimization problem4 using the optimality residual, is a powerful tool for the analysis of first-order optimization algorithms. In this paper, we use global error bound analysis to study the iteration complexity of a first-order algorithm for a linearly constrained nonconvex minimization problem. We develop a global dual error bound analysis for a regularized version of this nonconvex problem by using a novel "decomposition" technique. Equipped with this global dual error bound, we prove that a suitably designed primal-dual first-order method can generate an e-stationary solution of the linearly constrained nonconvex minimization problem within O(1/ε178;) iterations, which is the best known iteration complexity for this class of nonconvex problems. The iteration complexity of our algorithm for finding an e-stationary solution is O(1/ε178;), which improves the best known complexity of O(1/ε179;) for the problem under consideration. Furthermore, when the objective function is quadratic, we establish the linear convergence of the algorithm. Our proof is based on a new potential function and a novel use of error bounds. [ABSTRACT FROM AUTHOR]

We propose a rapid and robust iterative algorithm to solve inverse acoustic scattering problems formulated as a PDE constrained shape optimization problem. We use a level-set method to represent the obstacle geometry and propose a new scheme for updating the geometry based on an adaptation of accelerated gradient descent methods. The resulting algorithm aims at reducing the number of iterations and improving the accuracy of reconstructions. To cope with regularization issues, we propose a smoothing to the shape gradient using a single layer potential associated with ik where k is the wave number. Numerical experiments are given for several data types (full aperture, backscattering, phaseless, multiple frequencies) and show that our method outperforms a nonaccelerated approach in terms of convergence speed, accuracy, and sensitivity to initial guesses. [ABSTRACT FROM AUTHOR]

Many problems in engineering can be understood as controlling the bifurcation structure of a given device. For example, one may wish to delay the onset of instability or bring forward a bifurcation to enable rapid switching between states. We propose a numerical technique for controlling the bifurcation diagram of a nonlinear partial differential equation by varying the shape of the domain. Specifically, we are able to delay or advance a given branch point to a target parameter value. The algorithm consists of solving a shape optimization problem constrained by an augmented system of equations, the Moore--Spence system, that characterize the location of the branch points. Numerical experiments on the Allen--Cahn, Navier--Stokes, and hyperelasticity equations demonstrate the effectiveness of this technique in a wide range of settings. [ABSTRACT FROM AUTHOR]

We formulate a mixed-integer partial differential equation constrained optimization problem for designing an electromagnetic cloak governed by the 2D Helmholtz equation with absorbing boundary conditions. Our formulation is an alternative to the topology optimization formulation of electromagnetic cloaking design. We extend the formulation to include uncertainty with respect to the angle of the incidence wave, and we develop a mixed-integer trust-region approach for solving both the deterministic and the uncertain formulation. We present detailed numerical results that show that our trust-region approach obtains effective cloaks. [ABSTRACT FROM AUTHOR]

We propose an algorithm for solving bound-constrained mathematical programs with complementarity constraints on the variables. Each iteration of the algorithm involves solving a linear program with complementarity constraints in order to obtain an estimate of the active set. The algorithm enforces descent on the objective function to promote global convergence to B-stationary points. We provide a convergence analysis and preliminary numerical results on a range of test problems. We also study the effect of fixing the active constraints in a bound-constrained quadratic program that can be solved on each iteration in order to obtain fast convergence. [ABSTRACT FROM AUTHOR]

A novel gradient stepsize is derived at the motivation of equipping the Barzilai--Borwein (BB) method with the two dimensional quadratic termination property. A remarkable feature of the novel stepsize is that its computation only depends on the BB stepsizes in previous iterations and does not require any exact line search or the Hessian, and hence it can easily be extended for nonlinear optimization. By adaptively taking long BB steps and some short steps associated with the new stepsize, we develop an efficient gradient method for quadratic optimization and general unconstrained optimization and extend it to solve extreme eigenvalue problems. The proposed method is further extended for box-constrained optimization and singly linearly box-constrained optimization by incorporating gradient projection techniques. Numerical experiments demonstrate that the proposed method outperforms the most successful gradient methods in the literature. [ABSTRACT FROM AUTHOR]

Constrained least squares problems arise in many applications. Their memory and computation costs are expensive in practice involving high-dimensional input data. We employ the so-called "sketching" strategy to project the least squares problem onto a space of a much lower "sketching dimension" via a random sketching matrix. The key idea of sketching is to reduce the dimension of the problem as much as possible while maintaining the approximation accuracy. Tensor structure is often present in the data matrices of least squares, including linearized inverse problems and tensor decompositions. In this work, we utilize a general class of row-wise tensorized sub-Gaussian matrices as sketching matrices in constrained optimizations for the sketching design's compatibility with tensor structures. We provide theoretical guarantees on the sketching dimension in terms of error criterion and probability failure rate. In the context of unconstrained linear regressions, we obtain an optimal estimate for the sketching dimension. For optimization problems with general constraint sets, we show that the sketching dimension depends on a statistical complexity that characterizes the geometry of the underlying problems. Our theories are demonstrated in a few concrete examples, including unconstrained linear regression and sparse recovery problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the sequential convex programming method with monotone line search (SCPls) in [Z. Lu, Sequential Convex Programming Methods for a Class of Structured Nonlinear Programming, https://arxiv.org/abs/1210.3039, 2012] for a class of difference-of-convex optimization problems with multiple smooth inequality constraints. The SCPls is a representative variant of moving-ball-approximation-type algorithms [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259; J. Bolte, Z. Chen, and E. Pauwels, Math. Program., 182 (2020) pp. 1-36; J. Bolte and E. Pauwels, Math. Oper. Res., 41 (2016), pp. 442-465; R. Shefi and M. Teboulle, Math. Program., 159 (2016), pp. 137-164] for constrained optimization problems. We analyze the convergence rate of the sequence generated by SCPls in both nonconvex and convex settings by imposing suitable Kurdyka--Löjasiewicz (KL) assumptions. Specifically, in the nonconvex settings, we assume that a special potential function related to the ob jective and the constraints is a KL function, while in the convex settings we impose KL assumptions directly on the extended ob jective function (i.e., sum of the ob jective and the indicator function of the constraint set). A relationship between these two different KL assumptions is established in the convex settings under additional differentiability assumptions. We also discuss how to deduce the KL exponent of the extended ob jective function from its Lagrangian in the convex settings, under additional assumptions on the constraint functions. Thanks to this result, the extended ob jectives of some constrained optimization models such as minimizing\ell1 sub ject to logistic/Poisson loss are found to be KL functions with exponent 1 under mild assumptions. To illustrate how our results can be applied, we consider SCPs for minimizing 1-2 [P-Yin, Y. Lou, Q. He, and J. Xin, SIAM J. Sci. Comput., 37 (2015), pp. A536--A563] subject to residual error measured by norm/Lorentzian norm [R. E. Carrillo, A. B. Ramirez, G. R. Arce, K. E. Barner, and B. M. Sadler, EURASIP J. Adv. Signal Process. (2016), 108]. We first discuss how the various conditions required in our analysis can be verified, and then perform numerical experiments to illustrate the convergence behaviors of SCPls. [ABSTRACT FROM AUTHOR]

We propose a unified framework to address a family of classical mixed-integer optimization problems with logically constrained decision variables, including network design, facility location, unit commitment, sparse portfolio selection, binary quadratic optimization, sparse principal component analysis, and sparse learning problems. These problems exhibit logical relationships between continuous and discrete variables, which are usually reformulated linearly using a big-M formulation. In this work, we challenge this long-standing modeling practice and express the logical constraints in a nonlinear way. By imposing a regularization condition, we reformulate these problems as convex binary optimization problems, which are solvable using an outer-approximation procedure. In numerical experiments, we establish that a general-purpose numerical strategy, which combines cutting-plane, first-order, and local search methods, solves these problems faster and at a larger scale than state-of-the-art mixed-integer linear or second-order cone methods. Our approach successfully solves network design problems with 100s of nodes and provides solutions up to 40% better than the state of the art, sparse portfolio selection problems with up to 3,200 securities compared with 400 securities for previous attempts, and sparse regression problems with up to 100,000 covariates. [ABSTRACT FROM AUTHOR]

An algorithm is proposed to solve robust control problems constrained by partial differential equations with uncertain coefficients, based on the so-called MG/OPT framework. The levels in the MG/OPT hierarchy correspond to discretization levels of the PDE, as usual. For stochastic problems, the relevant quantities (such as the gradient) contain expected value operators on each of these levels. They are estimated using a multilevel Monte Carlo method, the specifics of which depend on the MG/OPT level. Each of the optimization levels then contains multiple underlying multilevel Monte Carlo levels. The MG/OPT hierarchy allows the algorithm to exploit the structure inherent in the PDE, speeding up the convergence to the optimum. In contrast, the multilevel Monte Carlo hierarchy exists to exploit structure present in the stochastic dimensions of the problem. A statement about the asymptotic cost of the algorithm is proven, and some additional properties are discussed. The performance of the algorithm is numerically investigated for three test cases. A reduction in the number of samples required on expensive levels and therefore in computation time can be observed. [ABSTRACT FROM AUTHOR]

Shape optimization based on shape calculus has received a lot of attention in recent years, particularly regarding the development, analysis, and modification of efficient optimization algorithms. In this paper we propose and investigate nonlinear conjugate gradient methods based on Steklov--Poincar\'e-type metrics for the solution of shape optimization problems constrained by partial differential equations. We embed these methods into a general algorithmic framework for gradientbased shape optimization methods and discuss the numerical discretization of the algorithms. We numerically compare the proposed nonlinear conjugate gradient methods to the already established gradient descent and limited memory BFGS methods for shape optimization on several benchmark problems. The results show that the proposed nonlinear conjugate gradient methods perform well in practice and that they are an efficient and attractive addition to already established gradient-based shape optimization algorithms. [ABSTRACT FROM AUTHOR]

In this paper we combine the stochastic variance reduced gradient (SVRG) method [R. Johnson and T. Zhang, in Advances in Neural Information Processing Systems 26, 2013, pp. 315-323] with the primal dual fixed point method (PDFP) proposed in [P. Chen, J. Huang, and X. Zhang, Inverse Problems, 29 (2013)] to minimize a sum of two convex functions, one of which is linearly composite. This type of problems typically arise in sparse signal and image reconstruction. The proposed SVRGPDFP can be seen as a generalization of Prox-SVRG [L. Xiao and T. Zhang, SIAM J. Optim., 24 (2014), pp. 2057-2075] originally designed for the minimization of a sum of two convex functions. Based on some standard assumptions, we propose two variants, one for strongly convex objective functions and the other for the general convex case. Convergence analysis shows that the convergence rate of SVRG-PDFP is Ϭ(1/k) (here k is the iteration number) for the general convex objective function and linear for the strongly convex case. Numerical examples on machine learning and computerized tomography image reconstruction are provided to show the effectiveness of the algorithms. [ABSTRACT FROM AUTHOR]

We propose a single time-scale stochastic subgradient method for constrained optimization of a composition of several nonsmooth and nonconvex functions. The functions are assumed to be locally Lipschitz and differentiable in a generalized sense. Only stochastic estimates of the values and generalized derivatives of the functions are used. The method is parameter-free. We prove convergence with probability one of the method, by associating with it a system of differential inclusions and devising a nondifferentiable Lyapunov function for this system. For problems with functions having Lipschitz continuous derivatives, the method finds a point satisfying an optimality measure with error of order 1/N, after executing N iterations with constant stepsize. [ABSTRACT FROM AUTHOR]

This paper aims at developing two versions of the generalized Newton method to compute local minimizers for nonsmooth problems of unconstrained and constrained optimization that satisfy an important stability property known as tilt stability. We start with unconstrained minimization of continuously differentiable cost functions having Lipschitzian gradients and suggest two second-order algorithms of Newton type: one involving coderivatives of Lipschitzian gradient mappings, and the other based on graphical derivatives of the latter. Then we proceed with the propagation of these algorithms to minimization of extended-real-valued prox-regular functions, while covering in this way problems of constrained optimization, by using Moreau envelopes. Employing advanced techniques of second-order variational analysis and characterizations of tilt stability allows us to establish the solvability of subproblems in both algorithms and to prove the Q-superlinear convergence of their iterations. [ABSTRACT FROM AUTHOR]

Sequential quadratic optimization algorithms are proposed for solving smooth nonlinear optimization problems with equality constraints. The main focus is an algorithm proposed for the case when the constraint functions are deterministic, and constraint function and derivative values can be computed explicitly, but the objective function is stochastic. It is assumed in this setting that it is intractable to compute objective function and derivative values explicitly, although one can compute stochastic function and gradient estimates. As a starting point for this stochastic setting, an algorithm is proposed for the deterministic setting that is modeled after a state-of-theart line-search SQP algorithm but uses a stepsize selection scheme based on Lipschitz constants (or adaptively estimated Lipschitz constants) in place of the line search. This sets the stage for the proposed algorithm for the stochastic setting, for which it is assumed that line searches would be intractable. Under reasonable assumptions, convergence (resp., convergence in expectation) from remote starting points is proved for the proposed deterministic (resp., stochastic) algorithm. The results of numerical experiments demonstrate the practical performance of our proposed techniques. [ABSTRACT FROM AUTHOR]

In this paper, we propose a primal-dual algorithm with a novel momentum term using the partial gradients of the coupling function that can be viewed as a generalization of the method proposed by Chambolle and Pock in 2016 to solve saddle point problems defined by a convex-concave function L(x,y)=f(x)+Φ(x,y)--h(y) with a general coupling term Φ(x,y) that is not assumed to be bilinear. Assuming ∇xΦ(*, y) is Lipschitz for any fixed y, and ∇yΦ(*, *) is Lipschitz, we show that the iterate sequence converges to a saddle point; and for any (x,y), we derive error bounds in terms of ... for the ergodic sequence ... In particular, we show O(1/k) rate when the problem is merely convex in x. Furthermore, assuming Φ(x,*) is linear for each fixed x and f is strongly convex, we obtain the ergodic convergence rate of O(1/k²) -- we are not aware of another single-loop method in the related literature achieving the same rate when Φ is not bilinear. Finally, we propose a backtracking technique which does not require the knowledge of Lipschitz constants while ensuring the same convergence results. We also consider convex optimization problems with nonlinear functional constraints and we show that using the backtracking scheme, the optimal convergence rate can be achieved even when the dual domain is unbounded. We tested our method against other state-of-the-art first-order algorithms and interior-point methods for solving quadratically constrained quadratic problems with synthetic data, the kernel matrix learning, and regression with fairness constraints arising in machine learning. [ABSTRACT FROM AUTHOR]

We introduce a numerical method, multilevel designed quadrature for computing the statistical solution of partial differential equations with random input data. Similar to multilevel Monte Carlo methods, our method relies on hierarchical spatial approximations in addition to a parametric/stochastic sampling strategy. A key ingredient in multilevel methods is the relationship between the spatial accuracy at each level and the number of stochastic samples required to achieve that accuracy. Our sampling is based on flexible quadrature points that are designed for a prescribed accuracy, which can yield less overall computational cost compared to alternative multilevel methods. We propose a constrained optimization problem that determines the number of samples to balance the approximation error with the computational budget. We further show that the optimization problem is convex and derive analytic formulas for the optimal number of points at each level. We validate the theoretical estimates and the performance of our multilevel method via numerical examples on a linear elasticity and a steady state heat diffusion problem. [ABSTRACT FROM AUTHOR]

Solutions to the linear complementarity problem (LCP) are naturally sparse in many applications such as bimatrix games and portfolio section problems. Despite that it gives rise to the hardness, sparsity makes optimization faster and enables relatively large scale computation. Motivated by this, we take the sparse LCP into consideration, investigating the existence and boundedness of its solution set as well as introducing a new merit function, which allows us to convert the problem into a sparsity constrained optimization. The function turns out to be continuously differentiable and twice continuously differentiable for some chosen parameters. Interestingly, it is also convex if the involved matrix is positive semidefinite. We then explore the relationship between the solution set to the sparse LCP and stationary points of the sparsity constrained optimization. Finally, Newton hard thresholding pursuit is adopted to solve the sparsity constrained model. Numerical experiments demonstrate that the problem can be efficiently solved through the new merit function. [ABSTRACT FROM AUTHOR]

We consider the iterative solution of regularized saddle-point systems. When the leading block is symmetric and positive semidefinite on an appropriate subspace, Dollar et al. [SIAM J. Matrix Anal. Appl., 28 (2006), pp. 170-189] describe how to apply the conjugate gradient (CG) method coupled with a constraint preconditioner, a choice that has proved to be effective in optimization applications. We investigate the design of constraint-preconditioned variants of other Krylov methods for regularized systems by focusing on the underlying basis-generation process. We build upon principles laid out by Gould, Orban, and Rees [SIAM J. Matrix Anal. Appl., 35 (2014), pp. 13291343] to provide general guidelines that allow us to specialize any Krylov method to regularized saddle-point systems. In particular, we obtain constraint-preconditioned variants of Lanczos and Arnoldi-based methods, including the Lanczos version of CG, MINRES, SYMMLQ, GMRES(l), and DQGMRES. We also provide MATLAB implementations in hopes that they are useful as a basis for the development of more sophisticated software. Finally, we illustrate the numerical behavior of constraint-preconditioned Krylov solvers using symmetric and nonsymmetric systems arising from constrained optimization. [ABSTRACT FROM AUTHOR]

This paper is devoted to developing and applications of a generalized differential theory of variational analysis that allows us to work in incomplete normed spaces, without employing conventional variational techniques based on completeness and limiting procedures. The main attention is paid to generalized derivatives and subdifferentials of the Dini--Hadamard type with the usage of mild qualification conditions revolving around metric subregularity. In this way we develop calculus rules of generalized differentiation in normed spaces without imposing restrictive normal compactness assumptions and the like and then apply them to general problems of constrained opti-mization. Most of the obtained results are new even in finite dimensions. Finally, we derive refined necessary optimality conditions for nonconvex problems of semi-infinite and semidefinite program-ming. [ABSTRACT FROM AUTHOR]

This paper deals with particular families of DC optimization problems involving suprema of convex functions. We show that the specific structure of this type of function allows us to cover a variety of problems in nonconvex programming. Necessary and sufficient optimality conditions for these families of DC optimization problems are established, where some of these structural features are conveniently exploited. More precisely, we derive necessary and sufficient conditions for (global and local) optimality in DC semi-infinite programming and DC cone-constrained optimization, under natural constraint qualifications. Finally, a penalty approach to DC abstract programming problems is developed in the last section. [ABSTRACT FROM AUTHOR]

In this article, the concept of the single-objective sequential quadratically constrained quadratic programming method is extended to the multiobjective case and a new line search technique is developed for nonlinear multiobjective optimization problems. The proposed method ensures global convergence as well as spreading of the Pareto front. A descent direction is obtained by solving a quadratically constrained quadratic programming subproblem. A nondifferentiable penalty function is used to restrict the constraint violations. Convergence of the descent sequence is established under the Mangasarian--Promovitz constraint qualification and some mild assumptions. In addition to this, a new technique is designed for selecting initial points to ensure the spreading of the Pareto front. The method is compared with existing methods using a set of test problems. [ABSTRACT FROM AUTHOR]

The prevalence of uncertainty in models of engineering and the natural sciences necessitates the inclusion of random parameters in the underlying partial differential equations (PDEs). The resulting decision problems governed by the solution of such random PDEs are infinite dimen-sional stochastic optimization problems. In order to obtain risk-averse optimal decisions in the face of such uncertainty, it is common to employ risk measures in the objective function. This leads to risk-averse PDE-constrained optimization problems. We propose a method for solving such problems in which the risk measures are convex combinations of the mean and conditional value-at-risk (CVaR). Since these risk measures can be evaluated by solving a related inequality-constrained optimization problem, we suggest a log-barrier technique to approximate the risk measure. This leads to a new continuously differentiable convex risk measure: the log-barrier risk measure. We show that the log-barrier risk measure fits into the setting of optimized certainty equivalents of Ben-Tal and Teboulle and the expectation quadrangle of Rockafellar and Uryasev. Using the differentiability of the log-barrier risk measure, we derive first-order optimality conditions reminiscent of classical primal and primal-dual interior-point approaches in nonlinear programming. We derive the associated Newton system, propose a reduced symmetric system to calculate the steps, and provide a sufficient condition for local superlinear convergence in the continuous setting. Furthermore, we provide a Γ-convergence result for the log-barrier risk measures to prove convergence of the minimizers to the original nonsmooth problem. The results are illustrated by a numerical study. [ABSTRACT FROM AUTHOR]

Full-waveform inversion (FWI) is a nonlinear PDE constrained optimization problem which seeks to estimate the constitutive parameters of a medium by fitting waveforms. Among these parameters, attenuation needs to be taken into account in viscous media to exploit the full potential of FWI. Attenuation is easily implemented in the frequency domain by using complex-valued velocities in the time-harmonic wave equation. These complex velocities are frequency-dependent to guarantee causality and account for dispersion. Since estimating a complex frequency-dependent velocity at each grid point in space is not realistic, the optimization is generally performed in the real domain by processing the phase velocity (or slowness) at a reference frequency and attenuation (or quality factor) as separate real parameters. This real parametrization requires an a priori empirical relation (such as the nonlinear Kolsky--Futterman (KF) or standard linear solid (SLS) attenuation models) between the complex velocity and the two real quantities, which is prone to generate modeling errors if it does not represent accurately the attenuation behavior of the medium. Moreover, it leads to a multivariate inverse problem, which is ill-posed due to the cross-talk between the two classes of real parameters. To alleviate these issues, we solve directly the optimization problem in the complex domain by processing narrow bands of frequencies in sequence under the assumption of bandwise frequency dependence of the complex velocities. Moreover, we use a relaxation method to extend the FWI search space by processing the wave equation as a weak constraint with the alternating direction method of multipliers (ADMM) to mitigate the risk of spurious local minima. To mitigate the ill-posedness of the inversion, three total variation (TV) regularization schemes based upon ADMM and proximity algorithms are presented. In the first, regularization is applied directly on the complex velocities. In the other two, separate TV regularizations are tailored to different attributes of the complex velocities (real and imaginary parts, magnitude and phase). The real phase velocity and attenuation factor are then reconstructed a posteriori at each spatial position from the estimated complex velocity using arbitrary empirical relation. The numerical results first show that the regularization of the amplitude and phase provides the most reliable results. Moreover, they show that the band-by-band design of the inversion limits the sensitivity of the recovered phase velocity and attenuation factor to the attenuation model used for their a posteriori extraction. [ABSTRACT FROM AUTHOR]