nonlinear optimization – Page 8 – Optimization Online

On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

Published: 2017/04/26

Unconstrained Optimization adaptive regularized framework using cubics, conjugate gradient method, energy norm, krylov subspace methods, line search algorithm, nonlinear optimization, trust-region methods, unconstrained optimization

We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem” in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model”. The … Read more

Partially separable convexly-constrained optimization with non-Lipschitz singularities and its complexity

Published: 2017/04/20

Xiaojun Chen

Philippe L. Toint

Hong Wang

Nonsmooth Optimization complexity, non-lipschitz, nonlinear optimization

An adaptive regularization algorithm using high-order models is proposed for partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian $\ell_q$-norm regularization terms for $q\in (0,1)$. It is shown that the algorithm using an $p$-th order Taylor model for $p$ odd needs in general at most $O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and … Read more

Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization

Published: 2017/01/02, Updated: 2019/08/26

Frank E. Curtis

Daniel P. Robinson

Mohammadreza Samadi

Constrained Nonlinear Optimization, Nonlinear Optimization equality constrained optimization, nonconvex optimization, nonlinear optimization, trust funnel methods, worst-case iteration-complexity

A method is proposed for solving equality constrained nonlinear optimization problems involving twice continuously differentiable functions. The method employs a trust funnel approach consisting of two phases: a first phase to locate an $\epsilon$-feasible point and a second phase to seek optimality while maintaining at least $\epsilon$-feasibility. A two-phase approach of this kind based on … Read more

A Sequential Algorithm for Solving Nonlinear Optimization Problems with Chance Constraints

Published: 2016/08/17, Updated: 2019/08/26

Frank E. Curtis

Victor M. Zavala

Constrained Nonlinear Optimization, Nonlinear Optimization cardinality constraints, chance constraints, exact penalization, nonlinear optimization, sample average approximation, sequential quadratic programming, trust-region methods

An algorithm is presented for solving nonlinear optimization problems with chance constraints, i.e., those in which a constraint involving an uncertain parameter must be satisfied with at least a minimum probability. In particular, the algorithm is designed to solve cardinality-constrained nonlinear optimization problems that arise in sample average approximations of chance-constrained problems, as well as … Read more

Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization

Published: 2016/08/16

Coralia Cartis

Nicholas I. M. Gould

Philippe L. Toint

Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization complexity, high-order optimality conditions, machine learning, nonlinear optimization

High-order optimality conditions for convexly-constrained nonlinear optimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of the objective function up to order $q \geq 1$ … Read more

On a conjecture in second-order optimality conditions

Published: 2016/06/16, Updated: 2017/06/23

Constrained Nonlinear Optimization constraint qualifications, nonlinear optimization, second order optimality conditions, singular value decomposition

In this paper we deal with optimality conditions that can be verified by a nonlinear optimization algorithm, where only a single Lagrange multiplier is avaliable. In particular, we deal with a conjecture formulated in [R. Andreani, J.M. Martinez, M.L. Schuverdt, “On second-order optimality conditions for nonlinear programming”, Optimization, 56:529–542, 2007], which states that whenever a … Read more

A fresh CP look at mixed-binary QPs: New formulations and relaxations

Published: 2016/05/21

Constrained Nonlinear Optimization, Quadratic Programming completely positive, conic optimization, copositivity, nonconvex optimization, nonlinear optimization, quadratic programming, reformulations

Triggered by Burer’s seminal characterization from 2009, many copositive (CP) reformulations of mixed-binary QPs have been discussed by now. Most of them can be used as proper relaxations, if the intractable co(mpletely )positive cones are replaced by tractable approximations. While the widely used approximation hierarchies have the disadvantage to use positive-semidefinite (psd) matrices of orders … Read more

A Reduced-Space Algorithm for Minimizing $\ell_1hBcRegularized Convex Functions

Published: 2016/02/19, Updated: 2019/08/26

Tianyi Chen

Frank E. Curtis

Daniel P. Robinson

Convex Optimization active-set methods, convex optimization, model prediction, nonlinear optimization, reduced-space methods, sparse optimization, subspace minimization

We present a new method for minimizing the sum of a differentiable convex function and an $\ell_1$-norm regularizer. The main features of the new method include: $(i)$ an evolving set of indices corresponding to variables that are predicted to be nonzero at a solution (i.e., the support); $(ii)$ a reduced-space subproblem defined in terms of … Read more

Constrained Optimization with Low-Rank Tensors and Applications to Parametric Problems with PDEs

Published: 2016/01/25

Sebastian Garreis

Michael Ulbrich

Optimization of Systems modeled by PDEs, Stochastic Programming, Systems governed by Differential Equations Optimization interior point methods, low-rank tensors, nonlinear optimization, optimal control under uncertainty, parametric variational inequalities, pdes with uncertainties, semismooth newton methods, uncertainty quantification

Low-rank tensor methods provide efficient representations and computations for high-dimensional problems and are able to break the curse of dimensionality when dealing with systems involving multiple parameters. We present algorithms for constrained nonlinear optimization problems that use low-rank tensors and apply them to optimal control of PDEs with uncertain parameters and to parametrized variational inequalities. … Read more

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Published: 2015/10/19, Updated: 2015/11/19

Coralia Cartis

Nicholas I. M. Gould

Philippe L. Toint

Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization complexity, high-order models, nonlinear optimization, worst-case analysis

Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of $O(\epsilon^{-3/2})$ proved by Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) for computing an $\epsilon$-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are … Read more