Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition

Categories Global Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

This work proposes a rapid algorithm, BM-Global, for nuclear-norm-regularized convex and low-rank matrix optimization problems. BM-Global efficiently decreases the objective value via low-cost steps leveraging the nonconvex but smooth Burer-Monteiro (BM) decomposition, while effectively escapes saddle points and spurious local minima ubiquitous in the BM form to obtain guarantees of fast convergence rates to the … Read more

A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth

Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

Classical results show that gradient descent converges linearly to minimizers of smooth strongly convex functions. A natural question is whether there exists a locally nearly linearly convergent method for nonsmooth functions with quadratic growth. This work designs such a method for a wide class of nonsmooth and nonconvex locally Lipschitz functions, including max-of-smooth, Shapiro’s decomposable … Read more

Error Bound and Isocost Imply Linear Convergence of DCA-based Algorithms to D-stationarity

Categories Nonsmooth Optimization Tags , , ,

We consider a class of structured nonsmooth difference-of-convex minimization, which can be written as the difference of two convex functions possibly nonsmooth with the second one in the format of the maximum of a finite convex smooth functions. We propose two extrapolation proximal difference-of-convex based algorithms for potential acceleration to converge to a weak/standard d-stationary … Read more

An implicit function formulation for optimization of discretized index-1 differential algebraic systems

Categories Systems governed by Differential Equations Optimization Tags , , ,

A formulation for the optimization of index-1 differential algebraic equation systems (DAEs) that uses implicit functions to remove algebraic variables and equations from the optimization problem is described. The formulation uses the implicit function theorem to calculate derivatives of functions that remain in the optimization problem in terms of a reduced space of variables, allowing … Read more

An Exact Approach for Solving Pickup-and-Delivery Traveling Salesman Problems with Neighborhoods

Categories Nonlinear Optimization, Production and Logistics, Transportation Tags , , , ,

This paper studies a variant of the traveling salesman problem called the pickup-and-delivery traveling salesman problem with neighborhoods that combines traditional pickup and delivery requirements with the flexibility of visiting the customers at locations within compact neighborhoods of arbitrary shape. We derive two optimality conditions for the problem, a local condition that verifies whether a … Read more

Duality assertions in vector optimization w.r.t. relatively solid convex cones in real linear spaces

Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization Tags , , , , , , ,

We derive duality assertions for vector optimization problems in real linear spaces based on a scalarization using recent results concerning the concept of relative solidness for convex cones (i.e., convex cones with nonempty intrinsic cores). In our paper, we consider an abstract vector optimization problem with generalized inequality constraints and investigate Lagrangian type duality assertions … Read more

A Gauss-Newton-based Decomposition Algorithm for Nonlinear Mixed-Integer Optimal Control Problems

Categories (Mixed) Integer Nonlinear Programming, Control Applications, Systems governed by Differential Equations Optimization Tags , ,

For the fast approximate solution of Mixed-Integer Non-Linear Programs (MINLPs) arising in the context of Mixed-Integer Optimal Control Problems (MIOCPs) a decomposition algorithm exists that solves a sequence of three comparatively less hard subproblems to determine an approximate MINLP solution. In this work, we propose a problem formulation for the second algorithm stage that is … Read more

Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability

Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , ,

Tight reformulations of combinatorial optimization problems like Convex Mixed-Integer Nonlinear Programs (MINLPs) enable one to solve these problems faster by obtaining tight bounds on the optimal value. We consider two techniques for reformulation: perspective reformulation and separability detection. We develop routines for the automatic detection of problem structures suitable for these reformulations and implement new … Read more

Distributed Projections onto a Simplex

Categories Linear, Cone and Semidefinite Programming, Parallel Algorithms Tags , , ,

Projecting a vector onto a simplex is a well-studied problem that arises in a wide range of optimization problems. Numerous algorithms have been proposed for determining the projection; however, all but one of these algorithms are serial. We address this gap by developing a method that preprocesses the input vector by decomposing and distributing it … Read more

Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization

Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

An algorithm for solving nonconvex smooth optimization problems is proposed, analyzed, and tested. The algorithm is an extension of the Trust Region Algorithm with Contractions and Expansions (TRACE) [Math. Prog. 162(1):132, 2017]. In particular, the extension allows the algorithm to use inexact solutions of the arising subproblems, which is an important feature for solving large-scale … Read more