Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Strict Complementarity Approach to Error Bound and Sensitivity of Solution of Conic Programs
75
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we provide an elementary, geometric, and unified framework to analyze conic programs that we call the strict complementarity approach. This framework allows us to establish error bounds and quantify the sensitivity of the solution. The framework uses three classical ideas from convex geometry and linear algebra: linear regularity of convex sets, facial reduction, and orthogonal decomposition. We show how to use this framework to derive error bounds for linear programming (LP), second order cone programming (SOCP), and semidefinite programming (SDP).
rate research
Read More
In this article, we introduce a new homotopy function to trace the trajectory by applying modified homotopy continuation method for finding the solution of the Linear Complementarity Problem. Earlier several authors attempted to propose homotopy functions based on original problems. We propose the homotopy function based on the Karush-Kuhn-Tucker condition of the corresponding quadratic programming problem of the original problem. The proposed approach extends the processability of the larger class of linear complementarity problems and overcomes the limitations of other existing homotopy approaches. We show that the homotopy path approaching the solution is smooth and bounded. We find the positive tangent direction of the homotopy path. The difficulty of finding a strictly feasible initial point for the interior point algorithm can be replaced appropriately by combining the interior point with the homotopy method. Various classes of numerical examples are illustrated to show the effectiveness of the proposed algorithm.
We propose an algorithm for solving bound-constrained mathematical programs with complementarity constraints on the variables. Each iteration of the algorithm involves solving a linear program with complementarity constraints in order to obtain an estimate of the active set. The algorithm enforces descent on the objective function to promote global convergence to B-stationary points. We provide a convergence analysis and preliminary numerical results on a range of test problems. We also study the effect of fixing the active constraints in a bound-constrained quadratic program that can be solved on each iteration in order to obtain fast convergence.
We develop a novel variant of the classical Frank-Wolfe algorithm, which we call spectral Frank-Wolfe, for convex optimization over a spectrahedron. The spectral Frank-Wolfe algorithm has a novel ingredient: it computes a few eigenvectors of the gradient and solves a small-scale SDP in each iteration. Such procedure overcomes slow convergence of the classical Frank-Wolfe algorithm due to ignoring eigenvalue coalescence. We demonstrate that strict complementarity of the optimization problem is key to proving linear convergence of various algorithms, such as the spectral Frank-Wolfe algorithm as well as the projected gradient method and its accelerated version.
The error bound property for a solution set defined by a set-valued mapping refers to an inequality that bounds the distance between vectors closed to a solution of the given set by a residual function. The error bound property is a Lipschitz-like/calmness property of the perturbed solution mapping, or equivalently the metric subregularity of the underlining set-valued mapping. It has been proved to be extremely useful in analyzing the convergence of many algorithms for solving optimization problems, as well as serving as a constraint qualification for optimality conditions. In this paper, we study the error bound property for the solution set of a very general second-order cone complementarity problem (SOCCP). We derive some sufficient conditions for error bounds for SOCCP which is verifiable based on the initial problem data.
Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, when the ambiguity set constitutes a 2-Wasserstein ball centered at a discrete distribution, then the distributionally robust linear program is equivalent to a copositive program (if the problem has complete recourse) or can be approximated arbitrarily closely by a sequence of copositive programs (if the problem has sufficiently expensive recourse). These results directly extend to the classical robust setting and motivate strong tractable approximations of two-stage problems based on semidefinite approximations of the copositive cone. We also demonstrate that the two-stage distributionally robust optimization problem is equivalent to a tractable linear program when the ambiguity set constitutes a 1-Wasserstein ball centered at a discrete distribution and there are no support constraints.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
