The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm … Read more
For a long time, the bilevel programming problem has essentially been considered as a special case of mathematical programs with equilibrium constraints (MPECs), in particular when the so-called KKT reformulation is in question. Recently though, this widespread believe was shown to be false in general. In this paper, other aspects of the difference between both … Read more
The problem of finding sparse solutions to underdetermined systems of linear equations is very common in many fields as e.g. in signal/image processing and statistics. A standard tool for dealing with sparse recovery is the ℓ1-regularized least-squares approach that has recently attracted the attention of many researchers. In this paper, we describe a new version … Read more
We present improvements to branch and bound techniques for globally optimizing functions with Lipschitz continuity properties by developing novel bounding procedures and parallelisation strategies. The bounding procedures involve nonconvex quadratic or cubic lower bounds on the objective and use estimates of the spectrum of the Hessian or derivative tensor, respectively. As the nonconvex lower bounds … Read more
The well-known symmetric rank-one trust-region method—where the Hessian approximation is generated by the symmetric rank-one update—is generalized to the problem of minimizing a real-valued function over a $d$-dimensional Riemannian manifold. The generalization relies on basic differential-geometric concepts, such as tangent spaces, Riemannian metrics, and the Riemannian gradient, as well as on the more recent notions … Read more
In this report, we study an efficient tridiagonal preconditioner, based on numerical differentiation, applied to the matrix-free truncated Newton method for unconstrained optimization. It is proved that this preconditioner is positive definite for many practical problems. The efficiency of the resulting matrix-free truncated Newton method is demonstrated by results of extensive numerical experiments. CitationTechnical Report … Read more
An implementable proximal point algorithm is established for the smooth nonconvex unconstrained minimization problem. At each iteration, the algorithm minimizes approximately a general quadratic by a truncated strategy with step length control. The main contributions are: (i) a framework for updating the proximal parameter; (ii) inexact criteria for approximately solving the subproblems; (iii) a nonmonotone … Read more
In this report, we state and prove first- and second-order necessary conditions in Pontryagin form for optimal control problems with pure state and mixed control-state constraints. We say that a Lagrange multiplier of an optimal control problem is a Pontryagin multiplier if it is such that Pontryagin’s minimum principle holds, and we call optimality conditions … Read more
In this report, given a reference feasible trajectory of an optimal control problem, we say that the quadratic growth property for bounded strong solutions holds if the cost function of the problem has a quadratic growth over the set of feasible trajectories with a bounded control and with a state variable sufficiently close to the … Read more
We consider the problem of identifying the densest k-node subgraph in a given graph. We write this problem as an instance of rank-constrained cardinality minimization and then relax using the nuclear and l1 norms. Although the original combinatorial problem is NP-hard, we show that the densest k-subgraph can be recovered from the solution of our … Read more