Level Bundle Methods for Constrained Convex Optimization with Various Oracles

We propose restricted memory level bundle methods for minimizing constrained convex nonsmooth optimization problems whose objective and constraint functions are known through oracles (black-boxes) that might provide inexact information. Our approach is general and covers many instances of inexact oracles, such as upper, lower and on-demand oracles. We show that the proposed level bundle methods … Read more

Second-order sufficient conditions for strong solutions to optimal control problems

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

Second-order necessary conditions in Pontryagin form for optimal control problems

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

Robust convex relaxation for the planted clique and densest k-subgraph problems

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

Adaptive Observations And Multilevel Optimization In Data Assimilation

We propose to use a decomposition of large-scale incremental four dimensional (4D-Var) data assimilation problems in order to make their numerical solution more efficient. This decomposition is based on exploiting an adaptive hierarchy of the observations. Starting with a low-cardinality set and the solution of its corresponding optimization problem, observations are adaptively added based on … Read more

On the Complexity Analysis of Randomized Block-Coordinate Descent Methods

In this paper we analyze the randomized block-coordinate descent (RBCD) methods for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov’s technique (SIOPT 2012) for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general … Read more

A proximal technique for computing the Karcher mean of symmetric positive definite matrices

This paper presents a proximal point approach for computing the Riemannian or intrinsic Karcher mean of symmetric positive definite matrices. Our method derives from proximal point algorithm with Schur decomposition developed to compute minimum points of convex functions on symmetric positive definite matrices set when it is seen as a Hadamard manifold. The main idea … Read more

Worst-Case Results For Positive Semidefinite Rank

This paper presents various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of a generic n-dimensional polytope with v vertices is at least (nv)^(1/4) improving on previous lower bounds. For polygons with v vertices, we show that psd rank … Read more

A Trust-Region Method for Unconstrained Multiobjective Problems with Applications in Satisficing Processes

Multiobjective optimization has a significant number of real life applications. For this reason, in this paper, we consider the problem of finding Pareto critical points for unconstrained multiobjective problems and present a trust-region method to solve it. Under certain assumptions, which are derived in a very natural way from assumptions used by \citet{conn} to establish … Read more

Computing in Operations Research using Julia

The state of numerical computing is currently characterized by a divide between highly efficient yet typically cumbersome low-level languages such as C, C++, and Fortran and highly expressive yet typically slow high-level languages such as Python and MATLAB. This paper explores how Julia, a modern programming language for numerical computing which claims to bridge this … Read more