Nonlinear Optimization

Strengthening the SDP Relaxation of AC Power Flows with Convex Envelopes, Bound Tightening, and Lifted Nonlinear Cuts

Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

This paper considers state-of-the-art convex relaxations for the AC power flow equations and introduces new valid cuts based on convex envelopes and lifted nonlinear constraints. These valid linear inequalities strengthen existing semidefinite and quadratic programming relaxations and dominate existing cuts proposed in the litterature. Together with model intersections and bound tightening, the new linear cuts … Read more

Solutions of a constrained Hermitian matrix-valued function optimization problem with applications

Categories Constrained Nonlinear Optimization Tags

Let $f(X) =\left( XC + D\right)M\left(XC + D \right)^{*} – G$ be a given nonlinear Hermitian matrix-valued function with $M = M^*$ and $G = G^*$, and assume that the variable matrix $X$ satisfies the consistent linear matrix equation $XA = B$. This paper shows how to characterize the semi-definiteness of $f(X)$ subject to all … Read more

A framework for simultaneous aerodynamic design optimization in the presence of chaos

Categories Systems governed by Differential Equations Optimization Tags , , , , ,

Integrating existing solvers for unsteady partial differential equations (PDEs) into a simultaneous optimization method is challenging due to the forward- in-time information propagation of classical time-stepping methods. This paper applies the simultaneous single-step one-shot optimization method to a reformulated unsteady PDE constraint that allows for both forward- and backward-in-time information propagation. Especially in the presence … Read more

Backward Step Control for Global Newton-type Methods

Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

We present and analyze a new damping approach called backward step control for the globalization of the convergence of Newton-type methods for the numerical solution of nonlinear root-finding problems. We provide and discuss reasonable assumptions that imply convergence of backward step control on the basis of generalized Newton paths in conjunction with a backward analysis … Read more

ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks

Categories Network Optimization, Nonlinear Optimization Tags , , , ,

In this note, we extend the existing algorithms Extra and subgradient-push to a new algorithm ExtraPush for convex consensus optimization over a directed network. When the network is stationary, we propose a simplified algorithm called Normalized ExtraPush. These algorithms use a fixed step size like in Extra and accept the column-stochastic mixing matrices like in … Read more

Global Convergence of ADMM in Nonconvex Nonsmooth Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, $\phi(x_1,\ldots,x_p,y)$, subject to linear equality constraints that couple $x_1,\ldots,x_p,y$, where $p\ge 1$ is an integer. Our ADMM sequentially updates the primal variables in the order $x_1,\ldots,x_p,y$, followed by updating the dual … Read more

Generalized Conjugate Gradient Methods for $\ell_1$ Regularized Convex Quadratic Programming with Finite Convergence

Categories Convex Optimization, Nonsmooth Optimization, Quadratic Programming Tags , , , ,

The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper we propose some generalized CG (GCG) methods for solving the $\ell_1$-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite number of iterations. At each iteration, our methods first … Read more

Sparse Recovery via Partial Regularization: Models, Theory and Algorithms

Categories Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , , , , , ,

In the context of sparse recovery, it is known that most of existing regularizers such as $\ell_1$ suffer from some bias incurred by some leading entries (in magnitude) of the associated vector. To neutralize this bias, we propose a class of models with partial regularizers for recovering a sparse solution of a linear system. We … Read more

Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models

Categories Nonlinear Optimization

We present an improved evaluation complexity bound for nonlinear least squares problems using higher order regularization methods. CitationTechnical Report NA 15-17, Numerical Analysis Group, University of Oxford, 2015ArticleDownload View PDF

Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization

Categories Unconstrained Optimization Tags , , ,

In a recent paper we introduced a trust-region method with variable norms for unconstrained minimization and we proved standard asymptotic convergence results. Here we will show that, with a simple modification with respect to the sufficient descent condition and replacing the trust-region approach with a suitable cubic regularization, the complexity of this method for finding … Read more