A Penalized Quadratic Convex Reformulation Method for Random Quadratic Unconstrained Binary Optimization

Categories 0-1 Programming, Stochastic Approaches Tags , ,

The Quadratic Convex Reformulation (QCR) method is used to solve quadratic unconstrained binary optimization problems. In this method, the semidefinite relaxation is used to reformulate it to a convex binary quadratic program which is solved using mixed integer quadratic programming solvers. We extend this method to random quadratic unconstrained binary optimization problems. We develop a … Read more

On smoothness properties of optimal value functions at the boundary of their domain under complete convexity

Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

This article studies continuity and directional differentiability properties of optimal value functions, in particular at boundary points of their domain. We extend and complement standard continuity results from W.W. Hogan, Point-to-set maps in mathematical programming, SIAM Review, Vol. 15 (1973), 591-603, for abstract feasible set mappings under complete convexity as well as standard differentiability results … Read more

Exploring the Modeling Capacity of Two-stage Robust Optimization — Two Variants of Robust Unit Commitment Model

Categories Applications - Science and Engineering, Robust Optimization Tags , ,

To handle significant variability in loads, renewable energy generation, as well as various contingencies, two-stage robust optimization method has been adopted to construct unit commitment models and to ensure reliable solutions. In this paper, we further explore and extend the modeling capacity of two-stage robust optimization and present two new robust unit commitment variants, the … Read more

Monte Carlo Sampling-Based Methods for Stochastic Optimization

Categories Optimization of Simulated Systems, Stochastic Programming

This paper surveys the use of Monte Carlo sampling-based methods for stochastic optimization problems. Such methods are required when—as it often happens in practice—the model involves quantities such as expectations and probabilities that cannot be evaluated exactly. While estimation procedures via sampling are well studied in statistics, the use of such methods in an optimization … Read more

Regularizing Bilevel Nonlinear Programs by Lifting

Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

This paper considers a bilevel nonlinear program (NLP) whose lower-level problem satisfies a linear independence constraint qualification (LICQ) and a strong second-order condition (SSOC). One would expect the resulting mathematical program with complementarity constraints (MPCC), whose constraints are the first-order optimality conditions of the lower-level NLP, to satisfy an MPEC-LICQ. We provide an example which … Read more

Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems

Categories Convex Optimization, Quadratic Programming Tags , ,

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

Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs

Categories Approximation Algorithms, Dynamic Programming

We present a framework for obtaining Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely the Calculus of K-approximation Functions and the Calculus of K-approximation Sets. Using our framework, we provide … Read more

A Mixed Integer Nonlinear Programming Framework for Fixed Path Coordination of Multiple Underwater Vehicles under Acoustic Communication Constraints

Categories (Mixed) Integer Nonlinear Programming, Control Applications, Telecommunications Tags , , ,

Mixed Integer Nonlinear Programming (MINLP) techniques are increasingly used to address challenging problems in robotics, especially Multi-Vehicle Motion Planning (MVMP). The main contribution of this paper is a discrete time-distributed Receding Horizon Mixed Integer Nonlinear Programming (RH-MINLP) formulation of the underwater multi-vehicle path coordination problem with constraints on kinematics, dynamics, collision avoidance, and acoustic communication … Read more

One condition for all: solution uniqueness and robustness of l1-synthesis and l1-analysis minimizations

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

The l1-synthesis and l1-analysis models recover structured signals from their undersampled measurements. The solution of the former model is often a sparse sum of dictionary atoms, and that of the latter model often makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We … Read more

A branch and bound approach for convex semi-infinite programming

Categories Convex Optimization, Semi-infinite Programming

In this paper we propose an efficient approach for globally solving a class of convex semi-infinite programming (SIP) problems. Under the objective function and constraints (w.r.t. the variables to be optimized) convexity assumption, and appropriate differentiability, we propose a branch and bound exchange type method for SIP. To compute a feasible point for a SIP … Read more