| # Convex Optimization Problems Convex Optimization > Convex sets | Convex functions | Convex optimization problems | Algorithms | DCP Definition Optimality Maximizing a convex function ## Definition The optimization problem in standard form: is called a convex optimization problem if: the objective function is convex; the functions defining the inequality constraints, , are convex; the functions defining the equality constraints, , are affine. Note that, in the convex optimization model, we do not tolerate equality constraints, unless they are affine. ## Optimality ### Local and global optima Recall the definition of global and local optima given here. Theorem: Global vs. local optima in convex optimization For convex problems, any locally optimal point is globally optimal. In addition, the optimal set is convex. (Proof) ### Optimality condition Consider the optimization problem above, which we write as where is the feasible set. When is differentiable, then we know that for every , Then is optimal if and only if If , then it defines a supporting hyperplane to the feasible set at . When the problem is unconstrained, we obtain the optimality condition: Note that these conditions are not always feasible, since the problem may not have any minimizer. This can happen for example when the optimal value is only attained in the limit; or, in constrained problems, when the feasible set is empty. Examples: Minimization of a convex quadratic function. Optimality condition for a convex, unconstrained problem. Optimality condition for a convex, linearly constrained problem. The optimality conditions given above might be hard to solve. We will return to this issue later. ## Maximization of convex functions Sometimes we would like to maximize a convex function over a set . Such problems are usually hard to solve. For example, the problem of maximizing the distance from a given point (say, ) to a point in a polyhedron described as is an example of such hard problems. One important property of convex functions is that their maximum over any set is the same as the maximum over the convex hull of that set. That is, for any set and any convex function , we have In the example mentioned above, where we seek to maximize the Euclidean norm of a point in a polyhedron, if we know the vertices of the polyhedron, that is, we can express the polyhedron as then the optimal distance is simply . Unfortunately, in practice, finding the vertices (given the original representation of as an intersection of hyperplanes) is hard, as the polytope might have an exponential number of vertices.