Search

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]

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]

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]

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]

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]

Recent papers indicate that some algorithms for constrained optimization may exhibit worst-case complexity bounds that are very similar to those of unconstrained optimization algorithms. A natural question is whether well-established practical algorithms, perhaps with small variations, may enjoy analogous complexity results. In the present paper we show that the answer is positive with respect to inexact restoration algorithms in which first-order approximations are employed for defining the subproblems. [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]

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]

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]

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]

The solution of matrices with a 2×2 block structure arises in numerous areas of computational mathematics, such as PDE discretizations based on mixed-finite element methods, constrained optimization problems, or the implicit or steady state treatment of any system of PDEs with multiple dependent variables. Often, these systems are solved iteratively using Krylov methods and some form of block preconditioner. Under the assumption that one diagonal block is inverted exactly, this paper proves a direct equivalence between convergence of 2×2 block preconditioned Krylov or fixed-point iterations to a given tolerance, with convergence of the underlying preconditioned Schur-complement problem. In particular, results indicate that an effective Schur-complement preconditioner is a necessary and sufficient condition for rapid convergence of 2×2 block-preconditioned GMRES, for arbitrary relative-residual stopping tolerances. A number of corollaries and related results give new insight into block preconditioning, such as the fact that approximate block-LDU or symmetric block-triangular preconditioners offer minimal reduction in iteration over block-triangular preconditioners, despite the additional computational cost. Theoretical results are verified numerically on a nonsymmetric steady linearized Navier--Stokes discretization, which also demonstrate that theory based on the assumption of an exact inverse of one diagonal block extends well to the more practical setting of inexact inverses. [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]

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]

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]

In this paper, we propose new linesearch-based methods for nonsmooth constrained optimization problems when first-order information on the problem functions is not available. In the first part, we describe a general framework for bound-constrained problems and analyze its convergence toward stationary points, using the Clarke-Jahn directional derivative. In the second part, we consider inequality constrained optimization problems where both objective function and constraints can possibly be nonsmooth. In this case, we first split the constraints into two subsets: difficult general nonlinear constraints and simple bound constraints on the variables. Then, we use an exact penalty function to tackle the difficult constraints and we prove that the original problem can be reformulated as the bound-constrained minimization of the proposed exact penalty function. Finally, we use the framework developed for the bound-constrained case to solve the penalized problem. Moreover, we prove that every accumulation point, under standard assumptions on the search directions, of the generated sequence of iterates is a stationary point of the original constrained problem. In the last part of the paper, we report extended numerical results on both bound-constrained and nonlinearly constrained problems, showing that our approach is promising when compared to some state-of-the-art codes from the literature. [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]

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]

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]

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]

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]

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]

In this paper, we propose two novel non-stationary first-order primal-dual algorithms to solve non-smooth composite convex optimization problems. Unlike existing primal-dual schemes where the parameters are often fixed, our methods use predefined and dynamic sequences for parameters. We prove that our first algorithm can achieve an O(1/k) convergence rate on the primal-dual gap, and primal and dual objective residuals, where k is the iteration counter. Our rate is on the non-ergodic (i.e., the last iterate) sequence of the primal problem and on the ergodic (i.e., the averaging) sequence of the dual problem, which we call the semi-ergodic rate. By modifying the step-size update rule, this rate can be boosted even faster on the primal objective residual. When the problem is strongly convex, we develop a second primal-dual algorithm that exhibits an O(1/k²) convergence rate on the same three types of guarantees. Again by modifying the step-size update rule, this rate becomes faster on the primal objective residual. Our primal-dual algorithms are the first ones to achieve such fast convergence rate guarantees under mild assumptions compared to existing works, to the best of our knowledge. As byproducts, we apply our algorithms to solve constrained convex optimization problems and prove the same convergence rates on both the objective residuals and the feasibility violation. We still obtain at least O(1/k²) rates even when the problem is "semi-strongly" convex. We verify our theoretical results via two well-known numerical examples. [ABSTRACT FROM AUTHOR]

In general, standard necessary optimality conditions cannot be formulated in a straightforward manner for semismooth shape optimization problems. In this paper, we consider shape optimization problems constrained by variational inequalities of the first kind, so-called obstacle-type problems. Under appropriate assumptions, we prove existence of adjoints for regularized problems and convergence to adjoints of the unregularized problem. Moreover, we derive shape derivatives for the regularized problem and prove convergence to a limit object. Based on this analysis, an efficient optimization algorithm is devised and tested numerically. [ABSTRACT FROM AUTHOR]

In many inverse problems, a nonnegativity constraint is natural. Moreover, in some cases, we expect the vector of unknown parameters to have zero components. When a Bayesian approach is taken, this motivates a desire for prior probability density (and hence posterior probability density) functions that have positive mass at the boundary of the set {x∊RN|x&#88040}. Unfortunately, it is difficult to define a prior with this property that yields computationally tractable inference for large-scale inverse problems. In this paper, we use nonnegativity constrained optimization to define such prior and posterior density functions when the measurement error is either Gaussian or Poisson distributed. The numerical optimization methods we use are highly efficient, and hence our approach is computationally tractable even in large-scale cases. We embed our nonnegativity constrained optimization approach within a hierarchical framework, obtaining Gibbs samplers for both Gaussian and Poisson distributed measurement cases. Finally, we test the resulting Markov chain Monte Carlo methods on examples from both image deblurring and positron emission tomography. [ABSTRACT FROM AUTHOR]

In this paper, we analyze optimal control problems governed by semilinear parabolic equations. Box constraints for the controls are imposed, and the cost functional involves the state and possibly a sparsity-promoting term, but not a Tikhonov regularization term. Unlike finite dimensional optimization or control problems involving Tikhonov regularization, second order sufficient optimality conditions for the control problems we deal with must be imposed in a cone larger than the one used to obtain necessary conditions. Different extensions of this cone have been proposed in the literature for different kinds of minima: strong or weak minimizers for optimal control problems. After a discussion on these extensions, we propose a new extended cone smaller than those considered until now. We prove that a second order condition based on this new cone is sufficient for a strong local minimum. [ABSTRACT FROM AUTHOR]

The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial time, existing algorithms do not use SDP. In this paper, we investigate the use of SDP for TTRS. Starting from the basic SDP relaxation of TTRS, which admits a gap, recent research has tightened the basic relaxation using valid secondorder- cone inequalities. Even still, closing the gap requires more. For the special case of TTRS in dimension n = 2, we fully characterize the remaining valid inequalities, which can be viewed as strengthened versions of the second-order-cone inequalities just mentioned. We also demonstrate that these valid inequalities can be used computationally even when n > 2 to solve TTRS instances that were previously unsolved using SDP-based techniques. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a Markov decision process with constraints on a Borel state space with the expected total reward criterion. Assuming that the transition probability has a density function, which is continuous in an action variable, we prove the existence of an optimal randomized stationary policy. Moreover, we show that there exists a deterministic stationary policy if the Borel algebra on the state space has no conditional atoms in the subalgebra generated by the density functions and the action correspondence. [ABSTRACT FROM AUTHOR]

Currently, nearly all positivity preserving discontinuous Galerkin (DG) discretizations of partial differential equations are coupled with explicit time integration methods. Unfortunately, for many problems this can result in severe time-step restrictions. The techniques used to develop explicit positivity preserving DG discretizations cannot, however, easily be combined with implicit time integration methods. In this paper, we therefore present a new approach. Using Lagrange multipliers, the conditions imposed by the positivity preserving limiters are directly coupled to a DG discretization combined with a diagonally implicit Runge--Kutta time integration method. The positivity preserving DG discretization is then reformulated as a Karush--Kuhn--Tucker (KKT) problem, which is frequently encountered in constrained optimization. Since the limiter is only active in areas where positivity must be enforced, it does not affect the higher order DG discretization elsewhere. The resulting nonsmooth nonlinear algebraic equations have, however, a different structure compared to most constrained optimization problems. We therefore develop an efficient active set semismooth Newton method that is suitable for the KKT formulation of time-implicit positivity preserving DG discretizations. Convergence of this semismooth Newton method is proven using a specially designed quasi-directional derivative of the time-implicit positivity preserving DG discretization. The time-implicit positivity preserving DG discretization is demonstrated for several nonlinear scalar conservation laws, which include the advection, Burgers, Allen--Cahn, Barenblatt, and Buckley--Leverett equations. [ABSTRACT FROM AUTHOR]

Principal component regression (PCR) is a useful method for regularizing least squares approximations. Although conceptually simple, straightforward implementations of PCR have high computational costs and so are inappropriate for large scale problems. In this paper, we propose efficient algorithms for computing approximate PCR solutions that, on one hand, are high quality approximations to the true PCR solutions (when viewed as minimizer of a constrained optimization problem) and, on the other hand, entertain rigorous risk bounds (when viewed as statistical estimators). In particular, we propose an input sparsity time algorithms for approximate PCR. We also consider computing an approximate PCR in the streaming model and kernel PCR. Empirical results demonstrate the excellent performance of our proposed methods. [ABSTRACT FROM AUTHOR]

In the present paper, we prove that the augmented Lagrangian method converges to KKT points under the quasi-normality constraint qualification, which is associated with the external penalty theory. An interesting consequence is that the Lagrange multiplier estimates computed by the method remain bounded in the presence of the quasi-normality condition. In order to establish a more general convergence result, a new sequential optimality condition for smooth constrained optimization, called PAKKT, is defined. The new condition takes into account the sign of the dual sequence, constituting an adequate sequential counterpart to the (enhanced) Fritz John necessary optimality conditions proposed by Hestenes, and later extensively treated by Bertsekas. PAKKT points are substantially better than points obtained by the classical approximate KKT (AKKT) condition, which has been used to establish theoretical convergence results for several methods. In particular, we present a simple problem with complementarity constraints such that all its feasible points are AKKT, while only the solutions and a pathological point are PAKKT. This shows the efficiency of the methods that reach PAKKT points, particularly the augmented Lagrangian algorithm, in such problems. We also provide the appropriate strict constraint qualification associated with the PAKKT sequential optimality condition, called PAKKT-regular, and we prove that it is strictly weaker than both quasi-normality and the cone continuity property. PAKKT-regular connects both branches of these independent constraint qualifications, generalizing all previous theoretical convergence results for the augmented Lagrangian method in the literature. [ABSTRACT FROM AUTHOR]

Optimization problems with rank constraints appear in many diverse fields such as control, machine learning, and image analysis. Since the rank constraint is nonconvex, these problems are often approximately solved via convex relaxations. Nuclear norm regularization is the prevailing convexifying technique for dealing with these types of problem. This paper introduces a family of low-rank inducing norms and regularizers which include the nuclear norm as a special case. A posteriori guarantees on solving an underlying rank constrained optimization problem with these convex relaxations are provided. We evaluate the performance of the low-rank inducing norms on three matrix completion problems. In all examples, the nuclear norm heuristic is outperformed by convex relaxations based on other low-rank inducing norms. For two of the problems there exist low-rank inducing norms that succeed in recovering the partially unknown matrix, while the nuclear norm fails. These low-rank inducing norms are shown to be representable as semidefinite programs. Moreover, these norms have cheaply computable proximal mappings, which make it possible to also solve problems of large size using first-order methods. [ABSTRACT FROM AUTHOR]

This paper improves the trust-region algorithm with adaptive sparse grids introduced in [SIAM J. Sci. Comput., 35 (2013), pp. A1847-A1879] for the solution of optimization problems governed by partial differential equations (PDEs) with uncertain coefficients. The previous algorithm used adaptive sparse-grid discretizations to generate models that are applied in a trust-region framework to generate a trial step. The decision whether to accept this trial step as the new iterate, however, required relatively high-fidelity adaptive discretizations of the objective function. In this paper, we extend the algorithm and convergence theory to allow the use of low-fidelity adaptive sparse-grid models in objective function evaluations. This is accomplished by extending conditions on inexact function evaluations used in previous trust-region frameworks. Our algorithm adaptively builds two separate sparse grids: one to generate optimization models for the step computation and one to approximate the objective function. These adapted sparse grids often contain significantly fewer points than the high-fidelity grids, which leads to a dramatic reduction in the computational cost. This is demonstrated numerically using two examples. Moreover, the numerical results indicate that the new algorithm rapidly identifies the stochastic variables that are relevant to obtaining an accurate optimal solution. When the number of such variables is independent of the dimension of the stochastic space, the algorithm exhibits near dimension-independent behavior. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of tilt stability in finite dimensional optimization via the approach of using the subgradient graphical derivative. We establish a new characterization of tilt-stable local minimizers for a broad class of unconstrained optimization problems in terms of a uniform positive-definiteness of the subgradient graphical derivative of the objective function around the point in question. By applying this result to nonlinear programming under the metric subregularity constraint qualification, we derive second-order characterizations and several new sufficient conditions for tilt stability. In particular, we show that each stationary point of a nonlinear programming problem satisfying the metric subregularity constraint qualification is a tilt-stable local minimizer if the classical strong second-order sufficient condition holds. [ABSTRACT FROM AUTHOR]

This paper is concerned with necessary and sufficient second-order conditions for finite-dimensional and infinite-dimensional constrained optimization problems. Using a suitably defined directional curvature functional for the admissible set, we derive no-gap second-order optimality conditions in an abstract functional analytic setting. Our theory not only covers those cases where the classical assumptions of polyhedricity or second-order regularity are satisfied but also allows to study problems in the absence of these requirements. As a tangible example, we consider no-gap second-order conditions for bang-bang optimal control problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of optimization problems with orthogonality constraints, the feasible region of which is called the Stiefel manifold. Our new framework combines a function value reduction step with a correction step. Different from the existing approaches, the function value reduction step of our algorithmic framework searches along the standard Euclidean descent directions instead of the vectors in the tangent space of the Stiefel manifold, and the correction step further reduces the function value and guarantees a symmetric dual variable at the same time. We construct two types of algorithms based on this new framework. The first type is based on gradient reduction including the gradient re ection (GR) and the gradient projection (GP) algorithms. The other one adopts a columnwise block coordinate descent (CBCD) scheme with a novel idea for solving the corresponding CBCD subproblem inexactly. We prove that both GR/GP with a fixed step size and CBCD belong to our algorithmic framework, and any clustering point of the iterates generated by the proposed framework is a first-order stationary point. Preliminary experiments illustrate that our new framework is of great potential. [ABSTRACT FROM AUTHOR]

In numerous applications, scientists and engineers acquire varied forms of data that partially characterize the inputs to an underlying physical system. This data is then used to inform decisions such as controls and designs. Consequently, it is critical that the resulting control or design is robust to the inherent uncertainties associated with the unknown probabilistic characterization of the model inputs. In this paper, we consider optimal control and design problems constrained by partial differential equations with uncertain inputs. We do not assume a known probabilistic model for the inputs, but rather we formulate the problem as a distributionally robust optimization problem where the outer minimization problem determines the control or design, while the inner maximization problem determines the worst-case probability measure that matches desired characteristics of the data. We analyze the inner maximization problem in the space of measures and introduce a novel measure approximation technique, based on the approximation of continuous functions, to discretize the unknown probability measure. We prove consistency of our approximated min-max problem and conclude with numerical results. [ABSTRACT FROM AUTHOR]

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 consider the problem of minimizing a given n-variate polynomial f over the hypercube [-1, 1]n. An idea introduced by Lasserre, is to find a probability distribution on [-1, 1]n with polynomial density function h (of given degree r) that minimizes the expectation ∩[-1 1]n∩(x)h(x)dμ(x), where dμ(x) is a fixed, finite Borel measure supported on [- 1, 1]n. It is known that, for the Lebesgue measure dμ(x) = dx, one may show an error bound O(1/√r) if h is a sum-of-squares density, and an O(1/r) error bound if h is the density of a beta distribution. In this paper, we show an error bound of O(1/r²), if dμ(x) = (∏in=1 √1-xi²) (the well-known measure in the study of orthogonal polynomials), and h has a Schmiidgen-type representation with respect to [-1,1]n, which is a more general condition than a sum of squares. The convergence rate analysis relies on the theory of polynomial kernels and, in particular, on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eig envalue problems, as is also the case for sum-of-squares densities. [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]

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]

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]

In large random graphs with fixed edge density and triangle density, it has been observed numerically [C. Radin, K. Ren, and L. Sadun, J. Phys. A, 47 (2014)] that a typical graph is finite-podal, meaning that it has only finitely many distinct "types" of vertices. In particular, it seems to be a fundamental property of such graphs to have large groups of vertices that are all of the same type. In this paper we describe a mechanism that produces such behavior. By known results on graph limits, the problem reduces to the study of a constrained maximization problem for symmetric measurable functions (graphons) on the unit square. As a first step we prove that, under an assumption that holds for a wide range of parameter values, the constrained maximizers are in some sense monotone. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the stochastic inverse eigenvalue problem of reconstructing a stochastic matrix from the prescribed spectrum. We directly reformulate the stochastic inverse eigenvalue problem as a constrained optimization problem over several matrix manifolds to minimize the distance between isospectral matrices and stochastic matrices. Then we propose a geometric Polak--Ribiere--Polyak-based nonlinear conjugate gradient method for solving the constrained optimization problem. The global convergence of the proposed method is established. Our method can also be extended to the stochastic inverse eigenvalue problem with prescribed entries. An extra advantage is that our models yield new isospectral flow methods. Finally, we report some numerical tests to illustrate the efficiency of the proposed method for solving the stochastic inverse eigenvalue problem and the case of prescribed entries. [ABSTRACT FROM AUTHOR]

In this paper, we first provide counterexamples showing that sublevels of prox-regular functions and levels of differentiable mappings with Lipschitz derivatives may fail to be prox-regular. Then, we prove the uniform prox-regularity of such sets under usual verifiable qualification conditions. The preservation of uniform prox-regularity of intersection and inverse image under usual qualification conditions is also established. Applications to constrained optimization problems are given. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) is widely used to solve large-scale linearly constrained optimization problems, convex or nonconvex, in many engineering fields. However there is a general lack of theoretical understanding of the algorithm when the objective function is nonconvex. In this paper we analyze the convergence of the ADMM for solving certain nonconvex consensus and sharing problems. We show that the classical ADMM converges to the set of stationary solutions, provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. For the sharing problems, we show that the ADMM is convergent regardless of the number of variable blocks. Our analysis does not impose any assumptions on the iterates generated by the algorithm and is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules. [ABSTRACT FROM AUTHOR]

The problem of finding sparse solutions to underdetermined systems of linear equations arises in several applications (e.g., signal and image processing, compressive sensing, statistical inference). A standard tool for dealing with sparse recovery is the ℓ1-regularized least squares approach that has been recently attracting the attention of many researchers. In this paper, we describe an active set estimate (i.e., an estimate of the indices of the zero variables in the optimal solution) for the considered problem that tries to quickly identify as many active variables as possible at a given point, while guaranteeing that some approximate optimality conditions are satisfied. A relevant feature of the estimate is that it gives a significant reduction of the objective function when setting to zero all those variables estimated to be active. This enables us to easily embed it into a given globally converging algorithmic framework. In particular, we include our estimate into a block coordinate descent algorithm for ℓ1-regularized least squares, analyze the convergence properties of this new active set method, and prove that its basic version converges with a linear rate. Finally, we report some numerical results showing the effectiveness of the approach. [ABSTRACT FROM AUTHOR]

In this paper we discuss special bilevel optimal control problems where the upper level problem is an optimal control problem of ODEs with control and terminal constraints and the lower level problem is a finite-dimensional parametric optimization problem where the parameter is the final state of the state variable of the upper level. We tackle this problem using tools from nonsmooth analysis, optimization in Banach spaces, and bilevel programming to derive necessary optimality conditions of linearized Pontryagin-type. [ABSTRACT FROM AUTHOR]