It is well-known that, given a linear program: minimize $c^T x$ such that $A x\leq b$, it is possible to reduce the program to deciding feasibility of the following set of constraints: $Ax \leq b, A^T y = c, y\leq 0, c^T x = b^T y$. This follows from the duality theorem of linear programming.

QUESTION: what other classes of optimization problems have this "reduction" property? For example: given a general convex program, can we reduce any optimality problem to a problem of deciding feasbility?


1 Answer 1


You displayed the KKT conditions of the LP.

For any convex optimization problem in which the objective and constraint functions $f_i(x)$ for constraints $f_i(x) \le 0$ are continuously differentiable and satisfy a constraint qualification, KKT conditions are necessary and sufficient; and therefore a point $x$ is optimal for the original optimization problem if and only if it satisfies the KKT conditions. I.e., feasibility of KKT.

This can be extended, under appropriate continuous differentiability, to convex conic optimization problems (such as a Linear Semidefinite Program (SDP)), for which conic "KKT" conditions apply given a constraint qualification, such as the Slater condition. This extension is presented in Section 5.9.2 Optimality conditions of "Convex Optimization", by Boyd and Vandenberghe


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.