اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Strict Complementarity Approach to Error Bound and Sensitivity of Solution of Conic Programs
75
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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).
قيم البحث
اقرأ أيضاً
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 func
tions 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 es
timate 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 grad
ient 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/ca
lmness 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
