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]

This paper considers strategies for selecting the barrier parameter at every iteration of an interior-point method for nonlinear programming. Numerical experiments suggest that heuristic adaptive choices, such as Mehrotra's probing procedure, outperform monotone strategies that hold the barrier parameter fixed until a barrier optimality test is satisfied. A new adaptive strategy is proposed based on the minimization of a quality function. The paper also proposes a globalization framework that ensures the convergence of adaptive interior methods, and examines convergence failures of the Mehrotra predictor-corrector algorithm. The barrier update strategies proposed in this paper are applicable to a wide class of interior methods and are tested in the two distinct algorithmic frameworks provided by the IPOPT and KNITRO software packages. [ABSTRACT FROM AUTHOR]

In this paper we consider an optimization problem with equality constraints given in operator form as F(x) = 0, where F : X → Y is an operator between Banach spaces. The paper addresses the case when the equality constraints are not regular in the sense that the Fréchet derivative F[sup1](x*) is not onto. In the first part of the paper, we pursue an approach based on the construction of p-regularity. For p-regular constrained optimization problems, we formulate necessary conditions for optimality and derive sufficient conditions for optimality. In the second part of the paper, we consider a generalization of the concept of p-regularity and derive generalized necessary conditions for optimality for an optimization problem that is neither regular nor p-regular. For this problem, we show that the tangent cone to a level surface of F can consist of rays (rather than lines). This is in contrast to the regular and the p-regular cases, for which the tangent cone is always "two-sided." We state that if the gradient of the generalized p-regular problem is nonzero, it can belong to an open set, despite the fact that all constructions are usually closed. Both p-regular and generalized conditions for optimality reduce to classical conditions for regular cases, but they give new and nontrivial conditions for nonregular cases. The presented results can be considered as a part of the p-regularity theory. [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]

In the first part of this two-paper series, we presented a conceptual algorithm for the optimal control of constrained switched systems and proved that this algorithm generates a sequence of points that converge to a necessary condition for optimality. However, since our algorithm requires the exact solution of a differential equation, the numerical implementation of this algorithm is impractical. In this paper, we address this shortcoming by constructing an implementable algorithm that discretizes the differential equation, producing a finite-dimensional nonlinear program. We prove that this implementable algorithm constructs a sequence of points that asymptotically satisfy a necessary condition for optimality for the constrained switched system optimal control problem. Four simulation experiments are included to validate the theoretical developments. [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]

This paper discusses asymptotic analysis and adaptive design of convex estimators over the Hölder class under the sup-norm risk and the pointwise risk using constrained optimization and asymptotic statistical techniques. Specifically, convex B-spline estimators are proposed to achieve uniform optimal convergence rates and adaptive procedures. The presence of the convex shape constraint complicates asymptotic performance analysis, particularly uniform convergence analysis. This in turn requires deep understanding of a family of size varying constrained optimization problems on spline coeficients. To address these issues, we establish the uniform Lipschitz property of optimal spline coeficients in the l∞-norm by exploiting the structure of underlying constrained optimization 8 problems. By using this property, polyhedral theory, and statistical techniques, we show that the convex B-spline estimator attains uniform consistency and optimal rates of convergence on the entire interval of interest over the Hölder class under the sup-norm risk and the pointwise risk. In addition, adaptive estimates are constructed under both risks when the Hölder exponent is between one and two. These estimates achieve a maximal risk within a constant factor of the minimax risk over the Hölder class. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling tasks subject to out-forest precedence constraints, where the tasks are identified with the edges. Initially only the tasks with no predecessors are available. At each step, an available task is selected and processed, resulting in either (a) termination, or (b) the replacement of the selected task in the available set by a random subset of its immediate successors. Also, an outcome-dependent reward is gained. The goal is to maximize the expected utility, which can be either linear or exponential. Denardo, Rothblum, and Van der Heyden [Math. Oper. Res., 29 (2004), pp. 162-181] (DRV) study a special version of the above problem. DRV use a leaf-to-stem induction to demonstrate the optimality of a priority rule and to compute it, the latter with work that is quadratic in the number of edges in the application that motivated their paper. Sethuraman and Tsitsiklis [Math. Oper. Res., 32 (2007), pp. 589-593] (ST) treat the general model and demonstrate optimality of a priority rule by employing an idea of Tsisiklis [Ann. Appl. Probab., 4 (1994), pp. 194-199] to successively eliminate nodes, from highest to lowest priority. ST report a work bound that is exponential in the size of the data. In the current paper, we adapt the leaf-to-stem methodology of DRV to show how to compute optimal priority rules for the general model, with work that is polynomial in the size of the data. [ABSTRACT FROM AUTHOR]

In this paper we consider inequality constrained nonlinear optimization problems where the first order derivatives of the objective function and the constraints cannot be used. Our starting point is the possibility to transform the original constrained problem into an unconstrained or linearly constrained minimization of a nonsmooth exact penalty function. This approach shows two main difficulties: the first one is the nonsmoothness of this class of exact penalty functions which may cause derivative-free codes to converge to nonstationary points of the problem; the second one is the fact that the equivalence between stationary points of the constrained problem and those of the exact penalty function can only be stated when the penalty parameter is smaller than a threshold value which is not known a priori. In this paper we propose a derivative-free algorithm which overcomes the preceding difficulties and produces a sequence of points that admits a subsequence converging to a Karush--Kuhn--Tucker point of the constrained problem. In particular the proposed algorithm is based on a smoothing of the nondifferentiable exact penalty function and includes an updating rule which, after at most a finite number of updates, is able to determine a "right value" for the penalty parameter. Furthermore we present the results obtained on a real world problem concerning the estimation of parameters in an insulin-glucose model of the human body. [ABSTRACT FROM AUTHOR]

In this paper, we study methods for generating approximate primal solutions as a byproduct of subgradient methods applied to the Lagrangian dual of a primal convex (possibly nondifferentiable) constrained optimization problem. Our work is motivated by constrained primal problems with a favorable dual problem structure that leads to efficient implementation of dual subgradient methods, such as the recent resource allocation problems in large-scale networks. For such problems, we propose and analyze dual subgradient methods that use averaging schemes to generate approximate primal optimal solutions. These algorithms use a constant stepsize in view of its simplicity and practical significance. We provide estimates on the primal infeasibility and primal suboptimality of the generated approximate primal solutions. These estimates are given per iteration, thus providing a basis for analyzing the trade-offs between the desired level of error and the selection of the stepsize value. Our analysis relies on the Slater condition and the inherited boundedness properties of the dual problem under this condition. It also relies on the boundedness of subgradients, which is ensured by assuming the compactness of the constraint set. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of minimizing a nonconvex quadratic function, subject to two quadratic inequality constraints. As an application, such a quadratic program plays an important role in the trust region method for nonlinear optimization; such a problem is known as the Celis, Dennis, and Tapia (CDT) subproblem in the literature. The Lagrangian dual of the CDT subproblem is a semidefinite program (SDP), hence convex and solvable. However, a positive duality gap may exist between the CDT subproblem and its Lagrangian dual because the CDT subproblem itself is nonconvex. In this paper, we present a necessary and sufficient condition to characterize when the CDT subproblem and its Lagrangian dual admits no duality gap (i.e., the strong duality holds). This necessary and sufficient condition is easy verifiable and involves only one (any) optimal solution of the SDP relaxation for the CDT subproblem. Moreover, the condition reveals that it is actually rare to render a positive duality gap for the CDT subproblems in general. Moreover, if the strong duality holds, then an optimal solution for the CDT problem can be retrieved from an optimal solution of the SDP relaxation, by means of a matrix rank-one decomposition procedure. The same analysis is extended to the framework where the necessary and sufficient condition is presented in terms of the Lagrangian multipliers at a KKT point. Furthermore, we show that the condition is numerically easy to work with approximatively. [ABSTRACT FROM AUTHOR]

In this paper we discuss the polynomiality of a feasible version of Mehrotra's predictor-corrector algorithm whose variants have been widely used in several interior point method (IPM)-based optimization packages. A numerical example is given that shows that the adaptive choice of centering parameter and correction terms in this algorithm may lead to small steps being taken in order to keep the iterates in a large neighborhood of the central path, which is important for proving polynomial complexity properties of this method. Motivated by this example, we introduce a safeguard in Mehrotra's algorithm that keeps the iterates in the prescribed neighborhood and allows us to obtain a positive lower bound on the step size. This safeguard strategy is also used when the affine scaling direction performs poorly. We prove that the safeguarded algorithm will terminate after at most O(n2log(x°}T s° /e) iterations. By modestly modifying the corrector direction, we reduce the iteration complexity to O(nlog(x°}T s° /e). To ensure fast asymptotic convergence of the algorithm, we changed Mehrotra's updating scheme of the centering parameter slightly while keeping the safeguard. The new algorithms have the same order of iteration complexity as the safeguarded algorithms but enjoy superlinear convergence as well. Numerical results using the McIPM and LIPSOL software packages are reported. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of minimization of a nonsmooth function under general nonsmooth constraints when no derivatives of the objective or constraint functions are available. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends the generalized pattern search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained. The main GPS convergence result is to identify limit points x0302;, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the general MADS framework is flexible enough to allow the generation of an asymptotically dense set of refining directions along which the Clarke derivatives are nonnegative. We propose an instance of MADS for which the refining directions are dense in the hypertangent cone at x0302; with probability 1 whenever the iterates associated with the refining directions converge to a single x0302;. The instance of MADS is compared to versions of GPS on some test problems. We also illustrate the limitation of our results with examples. [ABSTRACT FROM AUTHOR]

We study block-diagonal preconditioners and an efficient variant of constraint preconditioners for general two-by-two block linear systems with zero (2,2)-block. We derive block-diagonal preconditioners from a splitting of the (1,1)-block of the matrix. From the resulting preconditioned system we derive a smaller, so-called related system that yields the solution of the original problem. Solving the related system corresponds to an efficient implementation of constraint preconditioning. We analyze the properties of both classes of preconditioned matrices, in particular their spectra. Using analytical results, we show that the related system matrix has the more favorable spectrum, which in many applications translates into faster convergence for Krylov subspace methods. We show that fast convergence depends mainly on the quality of the splitting, a topic for which a substantial body of theory exists. Our analysis also provides a number of new relations between block-diagonal preconditioners and constraint preconditioners. For constrained problems, solving the related system produces iterates that satisfy the constraints exactly, just as for systems with a constraint preconditioner. Finally, for the Lagrange multiplier formulation of a constrained optimization problem we show how scaling nonlinear constraints can dramatically improve the convergence for linear systems in a Newton iteration. Our theoretical results are confirmed by numerical experiments on a constrained optimization problem. We consider the general, nonsymmetric, nonsingular case. Our only additional requirement is the nonsingularity of the Schur-complement--type matrix derived from the splitting that defines the preconditioners. In particular, the (1,2)-block need not equal the transposed (2,1)-block, and the (1,1)-block might be indefinite or even singular. This is the first paper in a two-part sequence. In the second paper we will study the use of our preconditioners in a variety of applications. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with a primal-dual interior point method for solving nonlinearly constrained optimization problems, in which Newton-like methods are applied to the shifted barrier KKT conditions. We propose a new primal-dual merit function, called the primal- dual quadratic barrier penalty function, framework of line search methods, and show the global convergence properties of our method. Asymptotic superlinear convergence of the method is achieved by carefully controlling the parameters .Some numerical experiments are presented to show the performance of our method. [ABSTRACT FROM AUTHOR]