Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints

Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

This paper proposes and analyzes a proximal augmented Lagrangian (NL-IAPIAL) method for solving smooth nonconvex composite optimization problems with nonlinear K-convex constraints, i.e., the constraints are convex with respect to the order given by a closed convex cone K. Each NL-IAPIAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite … Read more

Complexity Aspects of Local Minima and Related Notions

Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if … Read more

A Modified Proximal Symmetric ADMM for Multi-Block Separable Convex Optimization with Linear Constraints

Categories Convex Optimization Tags , , ,

We consider the linearly constrained separable convex optimization problem whose objective function is separable w.r.t. $m$ blocks of variables. A bunch of methods have been proposed and well studied. Specifically, a modified strictly contractive Peaceman-Rachford splitting method (SC-PRCM) has been well studied in the literature for the special case of $m=3$. Based on the modified … Read more

Affinely Adjustable Robust Linear Complementarity Problems

Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Robust Optimization Tags , , , ,

Linear complementarity problems are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many sub-areas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties – especially in the sense of robust optimization – is still in … Read more

Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters

Categories Convex Optimization, Stochastic Programming Tags , , , , ,

Many key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to … Read more

A geodesic interior-point method for linear optimization over symmetric cones

Categories Complementarity and Variational Inequalities, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

We develop a new interior-point method (IPM) for symmetric-cone optimization, a common generalization of linear, second-order-cone, and semidefinite programming. In contrast to classical IPMs, we update iterates with a geodesic of the cone instead of the kernel of the linear constraints. This approach yields a primal-dual-symmetric, scale-invariant, and line-search-free algorithm that uses just half the … Read more

Approximate Submodularity and Its Implications in Discrete Optimization

Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , ,

Submodularity, a discrete analog of convexity, is a key property in discrete optimization that features in the construction of valid inequalities and analysis of the greedy algorithm. In this paper, we broaden the approximate submodularity literature, which so far has largely focused on variants of greedy algorithms and iterative approaches. We define metrics that quantify … Read more

A branch-and-price method for the vehicle allocation problem

Categories Applications - OR and Management Sciences, Integer Programming, Transportation Tags , , , ,

The Vehicle Allocation Problem (VAP) consists of allocating a fleet of vehicles to attend to the expected demand for freight transportation between terminals along a finite multiperiod planning horizon. The objective is to maximize the profits generated for the completed services. The previous deterministic and stochastic approaches used heuristic procedures and approximations for solving large-scale … Read more

A Shared Mobility Based Framework for Evacuation Planning and Operations under Forecast Uncertainty

Categories Network Optimization, Stochastic Programming, Transportation

To meet evacuation needs from carless populations who may require personalized assistance to evacuate safely, we propose a ridesharing-based evacuation program that recruits volunteer drivers before a disaster strikes, and then matches volunteers with evacuees who need assistance once demand is realized. We optimize resource planning and evacuation operations under uncertain spatiotemporal demand, and construct … Read more

A new binary programming formulation and social choice property for Kemeny rank aggregation

Categories Combinatorial Optimization, Integer Programming, Other Topics

Rank aggregation is widely used in group decision-making and many other applications where it is of interest to consolidate heterogeneous ordered lists. Oftentimes, these rankings may involve a large number of alternatives, contain ties, and/or be incomplete, all of which complicate the use of robust aggregation methods. In particular, these characteristics have limited the applicability … Read more