Test Instances for Multiobjective Mixed-Integer Nonlinear Optimization

A suitable set of test instances, also known as benchmark problems, is a key ingredient to systematically evaluate numerical solution algorithms for a given class of optimization problems. While in recent years several solution algorithms for the class of multiobjective mixed-integer nonlinear optimization problems have been proposed, there is a lack of a well-established set … Read more

On the Optimization Landscape of Burer-Monteiro Factorization: When do Global Solutions Correspond to Ground Truth?

In low-rank matrix recovery, the goal is to recover a low-rank matrix, given a limited number of linear and possibly noisy measurements. Low-rank matrix recovery is typically solved via a nonconvex method called Burer-Monteiro factorization (BM). If the rank of the ground truth is known, BM is free of sub-optimal local solutions, and its true solutions … Read more

Yet another fast variant of Newton’s method for nonconvex optimization

\(\) A second-order algorithm is proposed for minimizing smooth nonconvex functions that alternates between regularized Newton and negative curvature steps. In most cases, the Hessian matrix is regularized with the square root of the current gradient and an additional term taking moderate negative curvature into account, a negative curvature step being taken only exceptionnally. As … Read more

A Test Instance Generator for Multiobjective Mixed-integer Optimization

Application problems can often not be solved adequately by numerical algorithms as several difficulties might arise at the same time. When developing and improving algorithms which hopefully allow to handle those difficulties in the future, good test instances are required. These can then be used to detect the strengths and weaknesses of different algorithmic approaches. … Read more

A Levenberg-Marquardt Method for Nonsmooth Regularized Least Squares

\(\) We develop a Levenberg-Marquardt method for minimizing the sum of a smooth nonlinear least-squares term \(f(x) = \frac{1}{2} \|F(x)\|_2^2\) and a nonsmooth term \(h\). Both \(f\) and \(h\) may be nonconvex. Steps are computed by minimizing the sum of a regularized linear least-squares model and a model of \(h\) using a first-order method such … Read more

Computing the Completely Positive Factorization via Alternating Minimization

In this article, we propose a novel alternating minimization scheme for finding completely positive factorizations. In each iteration, our method splits the original factorization problem into two optimization subproblems, the first one being a orthogonal procrustes problem, which is taken over the orthogoal group, and the second one over the set of entrywise positive matrices. … Read more

A momentum-based linearized augmented Lagrangian method for nonconvex constrained stochastic optimization

Nonconvex constrained stochastic optimization has emerged in many important application areas. Subject to general functional constraints it minimizes the sum of an expectation function and a nonsmooth regularizer. Main challenges arise due to the stochasticity in the random integrand and the possibly nonconvex functional constraints. To address these issues we propose a momentum-based linearized augmented … Read more

Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution

This work characterizes the effect of depth on the optimization landscape of linear regression, showing that, despite their nonconvexity, deeper models have more desirable optimization landscape. We consider a robust and over-parameterized setting, where a subset of measurements are grossly corrupted with noise and the true linear model is captured via an $N$-layer linear neural … Read more

Hidden convexity in a class of optimization problems with bilinear terms

In this paper we identify a new class of nonconvex optimization problems that can be equivalently reformulated to convex ones. These nonconvex problems can be characterized by convex functions with bilinear arguments. We describe several examples of important applications that have this structure. A reformulation technique is presented which converts the problems in this class … Read more

Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization

Nonconvex minimization algorithms often benefit from the use of second-order information as represented by the Hessian matrix. When the Hessian at a critical point possesses negative eigenvalues, the corresponding eigenvectors can be used to search for further improvement in the objective function value. Computing such eigenpairs can be computationally challenging, particularly if the Hessian matrix … Read more