Convex Optimization Theory Athena Scientific, 2009
Convex Optimization TheoryAthena Scientific, 2009byDimitri P. BertsekasMassachusetts Institute of TechnologySupplementary Chapter 6 onConvex Optimization AlgorithmsThis chapter aims to supplement the book Convex Optimization Theory,Athena Scientific, 2009 with material on convex optimization algorithms.The chapter will be periodically updated. This version is datedDecember 19, 2014
6Convex OptimizationAlgorithmsContents6.1. Convex Optimization Models: An Overview . . . .6.1.1. Lagrange Dual Problems . . . . . . . . . . .6.1.2. Fenchel Duality and Conic Programming . . . .6.1.3. Additive Cost Problems . . . . . . . . . . .6.1.4. Large Number of Constraints . . . . . . . . .6.1.5. Exact Penalty Functions. . . . . . . . . .6.2. Algorithmic Descent - Steepest Descent . . . . . .6.3. Subgradient Methods . . . . . . . . . . . . . .6.3.1. Convergence Analysis . . . . . . . . . . . .6.3.2. ǫ-Subgradient Methods . . . . . . . . . . .6.3.3. Incremental Subgradient Methods . . . . . . .6.3.4. Randomized Incremental Subgradient Methods .6.4. Polyhedral Approximation Methods . . . . . . . .6.4.1. Outer Linearization - Cutting Plane Methods . .6.4.2. Inner Linearization - Simplicial Decomposition .6.4.3. Duality of Outer and Inner Linearization . . . .6.4.4. Generalized Simplicial Decomposition . . . . .6.4.5. Generalized Polyhedral Approximation . . . .6.4.6. Simplicial Decomposition for Conic Programming6.5. Proximal Methods . . . . . . . . . . . . . . .6.5.1. Proximal Algorithm . . . . . . . . . . . . .6.5.2. Proximal Cutting Plane Method . . . . . . .6.5.3. Bundle Methods . . . . . . . . . . . . . .6.6. Dual Proximal Algorithms . . . . . . . . . . . .6.6.1. Proximal Inner Linearization Methods . . . . .6.6.2. Augmented Lagrangian Methods . . . . . . 6328334347357359369371375377381249
250Convex Optimization Algorithms6.7. Incremental Proximal Methods . . . . . . . . . . .6.7.1. Incremental Subgradient-Proximal Methods . . .6.7.2. Incremental Constraint Projection-Proximal Methods6.8. Generalized Proximal Algorithms and Extensions . . .6.9. Interior Point Methods . . . . . . . . . . . . . .6.9.1. Primal-Dual Methods for Linear Programming . .6.9.2. Interior Point Methods for Conic Programming . .6.10. Gradient Projection - Optimal Complexity Algorithms6.10.1. Gradient Projection Methods . . . . . . . . .6.10.2. Gradient Projection with Extrapolation . . . . .6.10.3. Nondifferentiable Cost – Smoothing . . . . . .6.10.4. Proximal Gradient Methods . . . . . . . . . .6.11. Notes, Sources, and Exercises . . . . . . . . . . .References . . . . . . . . . . . . . . . . . . . . . .Chap. 416417423427430431451
Sec. 6.1Convex Optimization Models: An Overview251In this supplementary chapter, we discuss several algorithmic approachesfor minimizing convex functions. A major type of problem that we aim tosolve is dual problems, which by their nature involve convex nondifferentiable minimization. The fundamental reason is that the negative of thedual function in the MC/MC framework is typically a conjugate function(cf. Section 4.2.1), which is generically closed and convex, but often nondifferentiable (it is differentiable only at points where the supremum in thedefinition of conjugacy is uniquely attained; cf. Prop. 5.4.3). Accordinglymost of the algorithms that we discuss do not require differentiability fortheir application. We refer to general nonlinear programming textbooksfor methods (e.g., [Ber99]) that rely on differentiability, such as gradientand Newton-type methods.6.1 CONVEX OPTIMIZATION MODELS: AN OVERVIEWWe begin with a broad overview of some important types of convex optimization problems, and some of their principal characteristics. Convexoptimization algorithms have a broad range of applications, but they areparticularly useful for large/challenging problems with special structure,usually connected in some way to duality. We discussed in Chapter 5 twoimportant duality structures. The first is Lagrange duality for constrainedoptimization, which arises by assigning dual variables to inequality constraints. The second is Fenchel duality together with its special case, conicduality. Both of these duality structures arise often in applications, and inthis chapter we provide an overview and discuss some examples in Sections6.1.1 and 6.1.2, respectively. In Sections 6.1.3 and 6.1.4, we discuss someadditional structures involving a large number of additive terms in the cost,or a large number of constraints. These types of problems also arise oftenin the context of duality. Finally, in Section 6.1.5, we discuss an important technique, based on conjugacy and duality, whereby we can transformconvex constrained optimization problems to equivalent unconstrained (orless constrained) ones.6.1.1Lagrange Dual ProblemsWe first focus on Lagrange duality (cf. Sections 5.3.1-5.3.4). It involves theproblemminimize f (x)(6.1)subject to x X, g(x) 0, ′where X is a set, g(x) g1 (x), . . . , gr (x) , and f : X 7 ℜ and gj : X 7 ℜ, j 1, . . . , r, are given functions. We refer to this as the primal problem,and we denote its optimal value by f .
Convex Optimization Algorithms252Chap. 6The dual problem ismaximizeq(µ)subject toµ ℜr , µ 0,(6.2)where the dual function q is given byµ 0,q(µ) inf L(x, µ),x X(6.3)and L is the Lagrangian function defined byL(x, µ) f (x) µ′ g(x),x X, µ ℜr .The dual optimal value isq sup q(µ).µ ℜrThe weak duality relation q f is easily shown by writing for all µ 0,and x X with g(x) 0,q(µ) inf L(z, µ) f (x) z Xsoq sup q(µ) µ 0infrXj 1x X, g(x) 0µj gj (x) f (x),f (x) f .We state this formally as follows.Proposition 6.1.1: (Weak Duality Theorem) For any feasiblesolutions x and µ of the primal and dual problems, respectively, wehave q(µ) f (x). Moreover, q f .Generally the solution process is simplified when strong duality holds.The following strong duality result has been shown in Prop. 5.3.1.Proposition 6.1.2: (Convex Programming Duality - Existenceof Dual Optimal Solutions) Consider the problem (6.1). Assumethat f is finite, and that one of the following two conditions holds:(1) There exists x X such that gj (x) 0 for all j 1, . . . , r.(2) The functions gj , j 1, . . . , r, are affine, and there exists x ri(X) such that g(x) 0.Then q f and the set of optimal solutions of the dual problem isnonempty. Under condition (1) this set is also compact.
Sec. 6.1Convex Optimization Models: An Overview253The following proposition gives necessary and sufficient conditions foroptimality (see Prop. 5.3.2).Proposition 6.1.3: (Optimality Conditions) Consider the problem (6.1). There holds q f , and (x , µ ) are a primal and dualoptimal solution pair if and only if x is feasible, µ 0, andµ j gj (x ) 0,x arg min L(x, µ ),x Xj 1, . . . , r.(6.4)Partially Polyhedral ConstraintsThe preceding results for the inequality-constrained problem (6.1) can berefined by making more specific assumptions regarding available polyhedralstructure in the constraint functions and the abstract constraint set X. Letus first consider an extension of problem (6.1) where there are additionallinear equality constraints:minimize f (x)subject to x X, g(x) 0, Ax b,(6.5) ′where X is a convex set, g(x) g1 (x), . . . , gr (x) , f : X 7 ℜ andgj : X 7 ℜ, j 1, . . . , r, are convex functions, A is an m n matrix, andb ℜm . We can deal with this problem by simply converting the constraintAx b to the equivalent set of linear inequality constraintsAx b, Ax b,(6.6)with corresponding dual variables λ 0 and λ 0. The Lagrangianfunction isf (x) µ′ g(x) (λ λ )′ (Ax b),and by introducing a dual variableλ λ λ with no sign restriction, it can be written asL(x, µ, λ) f (x) µ′ g(x) λ′ (Ax b).The dual problem ismaximizeinf L(x, µ, λ)x Xsubject to µ 0, λ ℜm .(6.7)
Convex Optimization Algorithms254Chap. 6The following is the standard duality result; see Prop. 5.3.5.Proposition 6.1.4: (Convex Programming - Linear Equalityand Nonlinear Inequality Constraints) Consider problem (6.5).Assume that f is finite, that there exists x X such that Ax band g(x) 0, and that there exists x̃ ri(X) such that Ax̃ b. Thenq f and there exists at least one dual optimal solution.In the special case of a problem with just linear equality constraints:minimizef (x)subject to x X,Ax b,(6.8)the Lagrangian function isL(x, λ) f (x) λ′ (Ax b),and the dual problem ismaximizeinf L(x, λ)x Xsubject toλ ℜm .The corresponding duality result is given as Prop. 5.3.3, and for the casewhere there are additional linear inequality constraints, as Prop. 5.3.4.Discrete Optimization and Lower BoundsThe preceding propositions deal with situations where the most favorableform of duality (q f ) holds. However, duality can be useful even whenthere is duality gap, as often occurs in problems of the form (6.1) that havea finite constraint set X. An example is integer programming, where thecomponents of x must be integers from a bounded range (usually 0 or 1).An important special case is the linear 0-1 integer programming problemminimize c′ xsubject to Ax b,xi 0 or 1,i 1, . . . , n.A principal approach for solving such problems is the branch-andbound method , which is described in many sources. This method relies onobtaining lower bounds to the optimal cost of restricted problems of theformminimize f (x)subject to x X̃,g(x) 0,
Sec. 6.1Convex Optimization Models: An Overview255where X̃ is a subset of X; for example in the 0-1 integer case where Xspecifies that all xi should be 0 or 1, X̃ may be the set of all 0-1 vectorsx such that one or more components xi are fixed at either 0 or 1 (i.e., arerestricted to satisfy xi 0 for all x X̃ or xi 1 for all x X̃). Theselower bounds can often be obtained by finding a dual-feasible (possiblydual-optimal) solution µ of this problem and the corresponding dual value q(µ) inf f (x) µ′ g(x) ,(6.9)x X̃which by weak duality, is a lower bound to the optimal value of the restricted problem minx X̃, g(x) 0 f (x). When X̃ is finite, q is concave andpolyhedral, so that solving the dual problem amounts to minimizing thepolyhedral function q over the nonnegative orthant.Separable Problems - DecompositionLet us now discuss an important problem structure that involves Lagrangeduality, and arises frequently in applications. Consider the problemminimizesubject tonXi 1a′j xfi (xi )(6.10) bj , j 1, . . . , r,where x (x1 , . . . , xn ), each fi : ℜ 7 ℜ is a convex function of thesingle scalar component xi , and aj and bj are some vectors and scalars,respectively. Then by assigning a dual variable µj to the constraint a′j x bj , we obtain the dual problem [cf. Eq. (6.2)]maximizenXi 1qi (µ) subject to µ 0,whererXµj b jj 1 r Xµj aji ,qi (µ) inf fi (xi ) xi xi ℜ (6.11)j 1and µ (µ1 , . . . , µr ). Note that the minimization involved in the calculation of the dual function has been decomposed into n simpler minimizations. These minimizations are often conveniently done either analyticallyor computationally, in which case the dual function can be easily evaluated. This is the key advantageous structure of separable problems: itfacilitates computation of dual function values (as well as subgradients aswe will see in Section 6.3), and it is amenable to decomposition/distributedcomputation.
Convex Optimization Algorithms256Chap. 6There are also other separable problems that are more general thanthe one of Eq. (6.10). An example is when x has m components x1 , . . . , xmof dimensions n1 , . . . , nm , respectively, and the problem has the formminimizesubject tomXi 1mXi 1fi (xi )(6.12)gi (xi ) 0,xi Xi , i 1, . . . , m,where fi : ℜni 7 ℜ and gi : ℜni 7 ℜr are given functions, and Xi aregiven subsets of ℜni . The advantage of convenient computation of the dualfunction value using decomposition extends to such problems as well. Wemay also note that when the components x1 , . . . , xm are one-dimensional,and the functions fi and sets Xi are convex, there is a particularly favorable strong duality result for the separable problem (6.12), even whenthe constraint functions gi are nonlinear but consist of convex componentsgij : ℜ 7 ℜ, j 1, . . . , r; see Tseng [Tse09].PartitioningAn important point regarding large-scale optimization problems is thatthere are several different ways to introduce duality in their solution. Forexample an alternative strategy to take advantage of separability, oftencalled partitioning, is to divide the variables in two subsets, and minimizefirst with respect to one subset while taking advantage of whatever simplification may arise by fixing the variables in the other subset. In particular,the problemminimize F (x) G(y)subject to Ax By c,x X, y Y,can be written asminimize F (x) infBy c Ax, y YG(y)subject to x X,orminimize F (x) p(c Ax)subject to x X,where p is the primal function of the minimization problem involving yabove:p(u) infG(y);By u, y Y(cf. Section 4.2.3). This primal function and its subgradients can often beconveniently calculated using duality.
Sec. 6.16.1.2Convex Optimization Models: An Overview257Fenchel Duality and Conic ProgrammingWe recall the Fenchel duality framework from Section 5.3.5. It involves theproblemminimize f1 (x) f2 (Ax)(6.13)subject to x ℜn ,where A is an m n matrix, f1 : ℜn 7 ( , ] and f2 : ℜm 7 ( , ]are closed convex functions, and we assume that there exists a feasible solution. The dual problem, after a sign change to convert it to a minimizationproblem, can be written asminimizef1 (A′ λ) f2 ( λ)(6.14)subject to λ ℜm ,where f1 and f2 are the conjugate functions of f1 and f2 . We denote byf and q the optimal primal and dual values. The following is given asProp. 5.3.8.Proposition 6.1.5: (Fenchel Duality) (a) If f is finite and A · ri dom(f1 ) ri dom(f2 ) 6 Ø, thenf q and there exists at least one dual optimal solution.(b) There holds f q , and (x , λ ) is a primal and dual optimalsolution pair if and only if x arg minn f1 (x) x′ A′ λ x ℜ and Ax arg minn f2 (z) z ′ λ .z ℜ(6.15)An important problem structure, which can be analyzed as a specialcase of the Fenchel duality framework is the conic programming problemdiscussed in Section 5.3.6:minimize f (x)subject to x C,(6.16)where f : ℜn 7 ( , ] is a closed proper convex function and C is aclosed convex cone in ℜn .Indeed, let us apply Fenchel duality with A equal to the identity andthe definitionsf1 (x) f (x),f2 (x) n0 if x C, if x / C.
Convex Optimization Algorithms258Chap. 6The corresponding conjugates are f1 (λ) sup λ′ x f (x) ,x ℜnf2 (λ) sup λ′ x x C 0 if λ C , if λ / C ,whereC {λ λ′ x 0, x C}is the polar cone of C (note that f2 is the support function of C; cf.Example 1.6.1). The dual problem [cf. Eq. (6.14)] isminimizef (λ)subject to λ Ĉ,(6.17)where f is the conjugate of f and Ĉ is the negative polar cone (also calledthe dual cone of C):Ĉ C {λ λ′ x 0, x C}.Note the symmetry between the primal and dual problems (6.16) and(6.17). The strong duality relation f q can be written asinf f (x) inf f (λ).x Cλ ĈThe following proposition translates the conditions of Prop. 6.1.5 toguarantee that there is no duality gap and that the dual problem has anoptimal solution (cf. Prop. 5.3.9).Proposition 6.1.6: (Conic Duality Theorem) Assume that theoptimal valueof the primal conic problem (6.16) is finite, and that ri dom(f ) ri(C) 6 Ø. Then, there is no duality gap and the dualproblem (6.17) has an optimal solution.Using the symmetry of the primal and dual problems, we also obtainthat there is no duality gap and the primal problem (6.16) has an optimalsolution if the optimal value of the dual conic problem (6.17) is finite andri dom(f ) ri(Ĉ) 6 Ø. It is also possible to exploit polyhedral structurein f and/or C, using Prop. 5.3.6. Furthermore, we may derive primal anddual optimality conditions using Prop. 6.1.5(b).
Sec. 6.1Convex Optimization Models: An Overview259Linear-Conic ProblemsAn important special case of conic programming, called linear-conic problem, arises when dom(f ) is affine and f is linear over dom(f ), i.e.,f (x) c′ x if x b S,if x / b S,where b and c are given vectors, and S is a subspace. Then the primalproblem can be written asminimizec′ xsubject to x b S,x C.(6.18)To derive the dual problem, we note thatf (λ) sup (λ c)′ xx b S sup(λ c)′ (y b)y S (λ c)′ b if λ c S ,if λ c / S .It can be seen that the dual problem (6.17), after discarding the superfluousterm c′ b from the cost, can be written asminimizeb′ λsubject to λ c S ,λ Ĉ.(6.19)Figure 6.1.1 illustrates the primal and dual linear-conic problems.The following proposition translates the conditions of Prop. 6.1.6 tothe linear-conic duality context.Proposition 6.1.7: (Linear-Conic Duality Theorem) Assumethat the primal problem (6.18) has finite optimal value. Assume further that either (b S) ri(C) 6 Ø or C is polyhedral. Then, there isno duality gap and the dual problem has an optimal solution.Proof: Under the condition (b S) ri(C) 6 Ø, the result follows fromProp. 6.1.6. For the case where C is polyhedral, the result follows from themore refined version of the Fenchel duality theorem, discussed at the endof Section 5.3.5. Q.E.D.
Convex Optimization Algorithms260Chap. 6λ (c S ) Ĉ(Dual)C Ĉx (b S) C(Primal)λ c S cx bb SFigure 6.1.1. Illustration of primal and dual linear-conic problems for the case ofa 3-dimensional problem, 2-dimensional subspace S, and a self-dual cone (C Ĉ);cf. Eqs. (6.18) and (6.19).Special Forms of Linear-Conic ProblemsThe primal and dual linear-conic problems (6.18) and (6.19) have beenplaced in an elegant symmetric form. There are also other useful formatsthat parallel and generalize similar formats in linear programming (cf. Example 4.2.1 and Section 5.2). For example, we have the following dualproblem pairs:minAx b, x Cc′ xmin c′ xAx b C max b′ λ,(6.20)b′ λ,(6.21)c A′ λ ĈmaxA′ λ c, λ Ĉwhere x ℜn , λ ℜm , c ℜn , b ℜm , and A is an m n matrix.To verify the duality relation (6.20), let x be any vector such thatAx b, and let us write the primal problem on the left in the primal conicform (6.18) asminimize c′ x(6.22)subject to x x N(A), x C,where N(A) is the nullspace of A. The corresponding dual conic problem(6.19) is to solve for µ the problemminimizex′ µsubject to µ c N(A) ,µ Ĉ.(6.23)
Sec. 6.1Convex Optimization Models: An Overview261Since N(A) is equal to Ra(A′ ), the range of A′ , the constraints of problem(6.23) can be equivalently written as c µ Ra(A′ ) Ra(A′ ), µ Ĉ, orc µ A′ λ,µ Ĉ,for some λ ℜm . Making the change of variables µ c A′ λ, the dualproblem (6.23) can be written asminimizex′ (c A′ λ)subject to c A′ λ Ĉ.By discarding the constant x′ c from the cost function, using the fact Ax b, and changing from minimization to maximization, we see that this dualproblem is equivalent to the one in the right-hand side of the duality pair(6.20). The duality relation (6.21) is proved similarly.We next discuss two important special cases of conic programming:second order cone programming and semidefinite programming. These problems involve some special cones, and an explicit definition of the affineset constraint. They arise in a variety of practical settings, and their computational difficulty tends to lie between that of linear and quadratic programming on one hand, and general convex programming on the otherhand.Second Order Cone ProgrammingConsider the coneC (x1 , . . . , xn ) xn qx21 ··· x2n 1 ,known as the second order cone (see Fig. 6.1.2). The dual cone is()Ĉ {y 0 y ′ x, x C} y0 infk(x1 ,.,xn 1 )k xny′x ,and it can be shown that Ĉ C. This property is referred to as self-dualityof the second order cone, and is fairly evident from Fig. 6.1.2. For a proof,we write)(n 1Xyi xiinfinfy ′ x inf yn xn k(x1 ,.,xn 1 )k xnxn 0k(x1 ,.,xn 1 )k xni 1 inf yn xn k(y1 , . . . , yn 1 )k xnxn 0 0if k(y1 , . . . , yn 1 )k yn , otherwise.
Convex Optimization Algorithms262Chap. 62 xx33xx111xx22Figure 6.1.2. The second order cone in ℜ3 :C n(x1 , . . . , xn ) xn px21 · · · x2n 1o.Combining the last two relations, we havey Ĉif and only if0 yn k(y1 , . . . , yn 1 )k,so Ĉ C.Note that linear inequality constraints of the form a′i x bi 0 canbe written as 00x Ci ,a′ibiwhere Ci is the second order cone of ℜ2 . As a result, linear-conic problemsinvolving second order cones contain as special cases linear programmingproblems.The second order cone programming problem (SOCP for short) isminimizec′ xsubject to Ai x bi Ci , i 1, . . . , m,(6.24)where x ℜn , c is a vector in ℜn , and for i 1, . . . , m, Ai is an ni nmatrix, bi is a vector in ℜni , and Ci is the second order cone of ℜni . It isseen to be a special case of the primal problem in the left-hand side of theduality relation (6.21), where b1A1.C C1 · · · Cm .b . ,A . ,bmAm
Sec. 6.1Convex Optimization Models: An Overview263Thus from the right-hand side of the duality relation (6.21), and theself-duality relation C Ĉ, the corresponding dual linear-conic problemhas the formmaximizesubject tomXi 1mXb′i λi(6.25)A′i λi c,i 1λi Ci , i 1, . . . , m,where λ (λ1 , . . . , λm ). By applying the duality result of Prop. 6.1.7, wehave the following.Proposition 6.1.8: (Second Order Cone Duality Theorem)Consider the primal SOCP (6.24), and its dual problem (6.25).(a) If the optimal value of the primal problem is finite and thereexists a feasible solution x such thatAi x bi int(Ci ),i 1, . . . , m,then there is no duality gap, and the dual problem has an optimalsolution.(b) If the optimal value of the dual problem is finite and there existsa feasible solution λ (λ1 , . . . , λm ) such thatλi int(Ci ),i 1, . . . , m,then there is no duality gap, and the primal problem has anoptimal solution.Note that while Prop. 6.1.7 requires a relative interior point condition,the preceding proposition requires an interior point condition. The reasonis that the second order cone has nonempty interior, so its relative interiorcoincides with its interior.The SOCP arises in many application contexts, and significantly, itcan be solved numerically with powerful specialized algorithms that belongto the class of interior point methods, to be discussed in Chapter 3. Werefer to the literature for a more detailed description and analysis (see e.g.,Ben-Tal and Nemirovski [BeT01], and Boyd and Vanderberghe [BoV04]).Generally, SOCPs can be recognized from the presence of convexquadratic functions in the cost or the constraint functions. The followingare illustrative examples.
Convex Optimization Algorithms264Chap. 6Example 6.1.1: (Robust Linear Programming)Frequently, there is uncertainty about the data of an optimization problem,so one would like to have a solution that is adequate for a whole range ofthe uncertainty. A popular formulation of this type, is to assume that theconstraints contain parameters that take values in a given set, and require thatthe constraints are satisfied for all values in that set. This approach is alsoknown as a set membership description of the uncertainty and has also beenused in fields other than optimization, such as set membership estimation,and minimax control.As an example, consider the problemminimize c′ xsubject to a′j x bj , (aj , bj ) Tj ,j 1, . . . , r,(6.26)where c ℜn is a given vector, and Tj is a given subset of ℜn 1 to whichthe constraint parameter vectors (aj , bj ) must belong. The vector x mustbe chosen so that the constraint a′j x bj is satisfied for all (aj , bj ) Tj ,j 1, . . . , r.Generally, when Tj contains an infinite number of elements, this problem involves a correspondingly infinite number of constraints. To convert theproblem to one involving a finite number of constraints, we note thata′j x bj , (aj , bj ) Tjif and only ifwheregj (x) supgj (x) 0,{a′j x bj }.(6.27)(aj ,bj ) TjThus, the robust linear programming problem (6.26) is equivalent tominimize c′ xsubject to gj (x) 0,j 1, . . . , r.For special choices of the set Tj , the function gj can be expressed inclosed form, and in the case where Tj is an ellipsoid, it turns out that theconstraint gj (x) 0 can be expressed in terms of a second order cone. To seethis, letTj (aj Pj uj , bj qj′ uj ) kuj k 1, uj ℜnj , (6.28)where Pj is a given n nj matrix, aj ℜn and qj ℜnj are given vectors,and bj is a given scalar. Then, from Eqs. (6.27) and (6.28),gj (x) sup(aj Pj uj )′ x (bj qj′ uj ) kuj k 1 sup (Pj′ x qj )′ uj a′j x bj ,kuj k 1
Sec. 6.1Convex Optimization Models: An Overviewand finally265gj (x) kPj′ x qj k a′j x bj .Thus,gj (x) 0(Pj′ x qj , bj a′j x) Cj ,if and only ifwhere Cj is the second order cone of ℜnj 1 ; i.e., the “robust” constraintgj (x) 0 is equivalent to a second order cone constraint. It follows that inthe case of ellipsoidal uncertainty, the robust linear programming problem(6.26) is a SOCP of the form (6.24).Example 6.1.2: (Quadratically Constrained QuadraticProblems)Consider the quadratically constrained quadratic problemminimizex′ Q0 x 2q0′ x p0subject to x′ Qj x 2qj′ x pj 0,j 1, . . . , r,where Q0 , . . . , Qr are symmetric n n positive definite matrices, q0 , . . . , qrare vectors in ℜn , and p0 , . . . , pr are scalars. We show that the problem canbe converted to the second order cone format. A similar conversion is alsopossible for the quadratic programming problem where Q0 is positive definiteand Qj 0, j 1, . . . , r.Indeed, since each Qj is symmetric and positive definite, we have 1/2x′ Qj x 2qj′ x pj Qj x1/2 ′1/2 1/2Qj x 2 Qj 1/2 kQj x Qjqj ′1/2Qj x pjqj k2 pj qj′ Q 1j qj ,for j 0, 1, . . . , r. Thus, the problem can be written as1/2 1/2minimize kQ0 x Q01/2q0 k2 p0 q0′ Q 10 q0 1/2subject to kQj x Qjqj k2 pj qj′ Q 1j qj 0,or, by neglecting the constant p0 1/21/2minimize kQ0 x Q0subject to1/2kQj x j 1, . . . , r,q0′ Q 10 q0 ,q0 k 1/2Qjqj k qj′ Q 1j qj pj 1/2, 1/2,j 1, . . . , r.By introducing an auxiliary variable xn 1 , the problem can be written asminimize xn 11/2 1/2subject to kQ0 x Q01/2kQj x q0 k xn 1 1/2Qjqj k qj′ Q 1j qj pjj 1, . . . , r.It can be seen that this problem has the second order cone form (6.24).We finally note that the problem of this example is special in that ithas no duality gap, assuming its optimal value is finite, i.e., there is no needfor the interior point conditions of Prop. 6.1.8. This can be traced to the factthat linear transformations preserve the closure of sets defined by quadraticconstraints (see e.g., BNO03], Section 1.5.2).
Convex Optimization Algorithms266Chap. 6Semidefinite Programming2Consider the space of symmetric n n matrices, viewed as the space ℜnwith the inner product X, Y trace(XY ) n XnXxij yij .i 1 j 1Let C be the cone of matrices that are positive semidefinite, called thepositive semidefinite cone. The interior of C is the set of positive definitematrices.The dual cone is Ĉ Y trace(XY ) 0, X C ,and it can be shown that Ĉ C, i.e., C is self-dual. Indeed, if Y / C,there exists a vector v ℜn such that0 v ′ Y v trace(vv ′ Y ).Hence the positive semidefinite matrix X vv ′ satisfies 0 trace(XY ),so Y / Ĉ and it follows that C Ĉ. Conversely, let Y C, and let X beany positive semidefinite matrix. We can express X asX nXλi ei e′i ,i 1where λi are the nonnegative eigenvalues of X, and ei are correspondingorthonormal eigenvectors. Then,!nnXX′λi e′i Y ei 0.λi ei ei trace(XY ) trace Yi 1i 1It follows that Y Ĉ, and C Ĉ.The semidefinite programming problem (SDP for short) is to minimize a linear function of a symmetric matrix over the intersection of anaffine set with the positive semidefinite cone. It has the formminimize D, X subject to Ai , X bi , i 1, . . . , m,X C,(6.29)where D, A1 , . . . , Am , are given n n symmetric matrices, and b1 , . . . , bm ,are given scalars. It is seen to be a special case of the primal problem inthe left-hand side of the duality relation (6.20).
Sec. 6.1Convex Optimization Models: An Overview267The SDP is a fairly general problem. In particular, it can also beshown that a SOCP can be cast as a SDP (see the end-of-chapter exercises).Thus SDP involves a more general structure than SOCP. This is consistentwith the practical observation that the latter problem is generally moreamenable to computational solution.We can view the SDP as a problem with linear cost, linear constraints,and a convex set constraint (as in Section 5.3.3). Then, similar to the caseof SOCP, it can be verified that the dual problem (6.19), as given by theright-hand side of the duality relation (6.20), takes the formb′ λmaximizesubject to D (λ1 A1 · · · λm Am ) C,(6.30)where b (b1 , . . . , bm ) and the maximization is over the vector λ (λ1 , . . . , λm ). By applying the duality result of Prop. 6.1.7, we have thefollowing proposition.Proposition 6.1.9: (Semidefinite Duality Theorem) Considerthe primal problem (6.29), and its dual problem (6.30).(a) If the optimal value of the primal problem is finite and thereexists a primal-feasible solution, which is positive definite, thenthere is no duality gap, and the dual problem has an optimalsolution.(b) If the optimal value of the dual problem is finite and there existscalars λ1 , . . . , λm such that D (λ1 A1 · · · λm
Convex Optimization Theory Athena Scientific, 2009 by Dimitri P. Bertsekas Massachusetts Institute of Technology Supplementary Chapter 6 on Convex Optimization Algorithms This chapter aims to supplement the book Convex Optimization Theory, Athena Scientific, 2009 with material on convex optimization algorithms. The chapter will be .
Convex obj non-convex domain. Introduction Generic Problem: min Q(x); s:t: x 2F; Q(x) convex, especially: convex quadratic F nonconvex Examples: F is a mixed-integer set F is constrained in a nasty way, e.g. x 1 3 sin(x 2) 2cos(x 3) 4 Bienstock, Michalka Columbia Convex obj non-convex domain.
Convex optimization – Boyd & Vandenberghe Nonlinear programming – Bertsekas Convex Analysis – Rockafellar Fundamentals of convex analysis – Urruty, Lemarechal Lectures on modern convex optimization – Nemirovski Optimization for Machine Learning – Sra, Nowozin, Wright Theory of Convex Optimization for Machine Learning – Bubeck .
Convex optimization { Boyd & Vandenberghe (BV) Introductory lectures on convex optimisation { Nesterov Nonlinear programming { Bertsekas Convex Analysis { Rockafellar Numerical optimization { Nocedal & Wright Lectures on modern convex optimization { Nemirovski Optimization for Machine Learning { Sra, Nowozin, Wright
Solution. We prove the rst part. The intersection of two convex sets is convex. There-fore if Sis a convex set, the intersection of Swith a line is convex. Conversely, suppose the intersection of Swith any line is convex. Take any two distinct points x1 and x2 2 S. The intersection of Swith the line through x1 and x2 is convex.
Convex optimization is still important for many nonconvex problems: . Some Convex Optimization References D. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Athena Scientific, 1996. . R.T. ROCKAFELLAR, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. 24
What is convex projective geometry? Motivation from hyperbolic geometry Nice Properties of Hyperbolic Space Convex: Intersection with projective lines is connected. Properly Convex: Convex and closure is contained in an affine patch ()Disjoint from some projective hyperplane. Strictly Convex: Properly convex and boundary contains
Apr 15, 2003 · Convex Analysis and Optimization Chapter 7 Solutions Dimitri P. Bertsekas with Angelia Nedi c and Asuman E. Ozdaglar Massachusetts Institute of Technology Athena Scienti c, Belmont, Massachusetts . Since Mis convex, its
Click 500 series – Customizable devices built on our Click 500 platform This user guide covers the Click 500 series. For the Click 100–400 series, please see the Click 100–400 Series User Guide. Using this Manual This manual is divided into two parts: Part I: Introduction to the Click Series – This part contains information common to the Click line, beginning with basic module .
