![]() Then the problem can be equivalently written in the dual form, as an LP: Assume that the above problem is feasible, so that strong duality holds. Indeed, it is feasible, since, and its objective value equals to the optimal value. ![]() The point is optimal for the primal problem. Let us set, where denotes the optimal dual variable. We can also find a corresponding optimal point: for every, the point achieves the minimum in the definition of the dual function. This allows us to compute the optimal value of the problem analytically. The problem is convex, and satisfies Slater’s condition (in fact, strong duality always holds for this convex quadratic problem). The minimum distance to an affine set mentioned in XXX is In this problem, Slater’s condition is not satisfied, since for any feasible pair. The Lagrangian is, and the dual function is 5.6 in BV,p.236.) Examples A convex counterexampleĬonvexity alone is not enough to guarantee strong duality. If Slater’s condition holds, then the interior of intersects the left-half plane, and strong duality holds. If the problem is convex, then is also convex. If the minimum is finite, then the inequality defines a supporting hyperplane, with slope, of at. The problem is feasible if and only if intersects the left-half plane. ![]() Geometric interpretationĪssume that there is only one inequality constraint in the primal problem ( ), and let In particular, strong duality holds for any feasible linear optimization problem. If is quadratic convex, and the functions are all affine, then the duality gap is always zero, provided one of the primal or dual problems is feasible. We can replace the above by a weak form of Slater’s condition, where strict feasibility is not required whenever the function is affine. We say that the problem satisfies Slater’s condition if it is strictly feasible, that is: We say that strong duality holds for the above problem if the duality gap is zero. The duality gap is the non-negative number. We have seen how weak duality allows to form a convex optimization problem that provides a lower bound on the original (primal) problem, even when the latter is non-convex. Strong duality via Slater’s condition Duality gap and strong duality Note that the dual variables associated with the affine equality constraints (in vector ) are not constrained in sign. To the problem we associate the Lagrangian, with values We denote by the domain of the problem (which is the intersection of the domains of all the functions involved), and by its feasible set. Where the functions are convex, and are affine. In this section, we consider a convex optimization problem
0 Comments
Leave a Reply. |