Recognizing the strength of parametric optimization to model uncertainty, we extend the classical linear programming duality theory to a parametric setting. For linear programs with parameters in general locations, we prove parametric weak and strong duality theorems and parametric complementary slackness theorems. ArticleDownload
We discuss easily verifiable cone membership certificates, that is, certificates proving relations of the form \( b\in K \) for convex cones \(K\) that consist of vectors in the dual cone \(K^*\). Vectors in the dual cone are usually associated with separating hyperplanes, and so they are interpreted as certificates of non-membership in the standard … Read more
Thirty years ago, in a seminal paper Ramana derived an exact dual for Semidefinite Programming (SDP). Ramana’s dual has the following remarkable features: i) it assumes feasibility of the primal, but it does not make any regularity assumptions, such as strict feasibility ii) its optimal value is the same as the optimal value of the … Read more
Covering and elimination inequalities are central to combinatorial optimization, yet their role has largely been studied in problem-specific settings or via no-good cuts. This paper introduces a unified perspective that treats these inequalities as primitives for set system approximation in binary integer programs (BIPs). We show that arbitrary set systems admit tight inner and outer … Read more
Risk-averse multi-stage problems and their applications are gaining interest in various fields of applications. Under convexity assumptions, the resolution of these problems can be done with trajectory following dynamic programming algorithms like Stochastic Dual Dynamic Programming (SDDP) to access a deterministic lower bound, and dual SDDP for deterministic upper bounds. In this paper, we leverage … Read more
Quadratic optimization (QO) has been studied extensively in the literature due to its applicability in many practical problems. While practical, it is known that QO problems are generally NP-hard. So, researchers developed many approximation methods to find good solutions. In this paper, we analyze QO problems using robust optimization techniques. To this end, we first … Read more
The structured saddle-point problem involving the infimal convolution in real Hilbert spaces finds applicability in many applied mathematics disciplines. For this purpose, we develop a stochastic primal-dual splitting algorithm with loopless variance-reduction for solving this generic problem. We first prove the weak almost sure convergence of the iterates. We then demonstrate that our algorithm achieves … Read more
This paper focuses on solving mathematical programs with complementarity constraints (MPCCs) by assuming neither MPCC linear independence constraint qualification (MPCC-LICQ) nor lower/upper level strict complementarity at the solution. First, necessary conditions for MPCC local optimality and sufficient conditions for convergence to B-stationarity are investigated. Under MPCC-Abadie constraint qualification (MPCC-ACQ), we show that a local minimizer … Read more
This paper studies duality and optimality conditions for general convex stochastic optimization problems. The main result gives sufficient conditions for the absence of a duality gap and the existence of dual solutions in a locally convex space of random variables. It implies, in particular, the necessity of scenario-wise optimality conditions that are behind many fundamental … Read more
The aim of this paper is to formulate several questions related to distributionally robust Stochastic Optimal Control modeling. As an example, the distributionally robust counterpart of the classical inventory model is discussed in details. Finite and infinite horizon stationary settings are considered. ArticleDownload View PDF