### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Nonlin Prog IOE 611

UM

GPA 3.76

### View Full Document

## 41

## 0

## Popular in Course

## Popular in Industrial Engineering

This 58 page Class Notes was uploaded by Loy King on Thursday October 29, 2015. The Class Notes belongs to IOE 611 at University of Michigan taught by Marina Epelman in Fall. Since its upload, it has received 41 views. For similar materials see /class/231590/ioe-611-university-of-michigan in Industrial Engineering at University of Michigan.

## Reviews for Nonlin Prog

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Convex sets affine and convex sets some important examples operations that preserve convexity separating and supporting hyperplanes generalized inequalities VVVVVV dual cones and generalized inequalities IOE 611 Nonlinear Programmlng Winter 2008 2 Convex gel Page 2e1 Affine set line through X1 X2 all points X6X11 6X2 06R affine set contains the line through any two distinct points in the set example solution set of linear equations X AX b conversely every affine set can be expressed as solution set of system of linear equations IOE 611 Nonlinear Programmlng Wlnler 2008 2 Convex gel Page 24 Convex set line segment between X1 and X2 all points X 2 6X1 1 6X2 with 0 g 0 g 1 convex set contains line segment between any two points in the set X17X2 C7 6X11 6X2 C examples one convex two nonconvex sets 77 L4 IOE 611 Nonlinear Programmlng Winter 2008 2 Convex see Page 24 Convex combination and convex hull convex combination of X1 in any point X of the form X01X1 02X2 0ka With 61 396k1620 convex hull convS set of all convex combinations of points in 5 IOE 611 Nonlinear Programmlng Wlnler 2008 2 Convex see Page 24 Convex cone cone a set C such that for any X 6 C7 6 gt 0 6X 6 C conic nonnegative combination of X1 and X22 any point of the form X 61X1 62x2 With 61 Z O 62 Z O convex cone a cone that is convex ie set that contains all conic combinations 01X1 02X2 QkaIQ Z 0 of points in the set IOE 611 Nonllnear Programmlng Winter 2008 2 Convex sec Page 2e5 Hyperplanes and halfspaces hyperplane set of the form X aTX b a 75 O gt a is the normal vector gt hyperplanes are affine and convex halfspaces are convex IOE 611 Nonllnear Programmlng Wlnler 2008 2 Convex sec Page 276 Euclidean balls and ellipsoids Euclidean ball with center XC and radius r 3ch r X X Xcll2 S r Xc ru U2 S 1 ellipsoid set of the form XI x xCgtTP4ltx Xe 1 with P 6 51 ie P symmetric positive definite 39 other representation XC Au u2 g 1 with A square and nonsingular IOE 611 Nonlinear Programmlng Winter 2008 2 Convex gel Page 24 Norm balls and norm cones norm a function that satisfies gt Z O 0 if and only ifX O gt tx t for t E R gt XYI S X IIYII notation is general unspecified norm symb is particular norm norm ball with center XC and radius r X X XCH g r norm cone X7 t g t Euclidean norm cone is called second order cone 1 norm balls and cones are convex IOE 611 Nonlinear Programmlng Wlnler 2008 2 Convex gel Page 2es Polyhedra solution set of finitely many linear inequalities and equalities AX j b7 CX d A E RmX C E RpX j is componentwise inequality a1 a2 03 a4 polyhedron is intersection of finite number of halfspaces and hype rpl a nes IOE 611 Nonllnear Programmlng Winter 2008 2 Convex sec Page 279 Positive semidefinite cone notation gt Squot is set of symmetric n X n matrices gt 1 X E Squot X t 0 positive semidefinite n X n matrices X651 ltgt zTXzZOforallz Si is a convex cone gt 51 2 X E Squot X gt 0 positive definite n X n matrices example j Z J 6 Si Page 2710 IOE 611 Nonlinear Programming Winter 2008 2 Convex sec Operations that preserve convexity practical methods for establishing convexity of a set C 1 apply definition X17X2 C7 OSQS 6X11 6X2 C 2 show that C is obtained from simple convex sets hyperplanes halfspaces norm balls by operations that preserve conveXIty intersection affine functions perspective function linear fractional functions V VVV IOE 611 Nonlinear Programmmg Winter 2008 2 Convex sec Page 2e11 Intersection the intersection of any number of convex sets is convex example 5 X E Rm pt g 1 for t g 7r3 where pt X1COStlX2 cos2t chos mt St X E Rm 1 3 cos tcosmtTX g 1 5 t SW35t I for m2 l Affine function suppose f R gt Rm is affine fx Ax b with A e RmX b e R gt the image of a convex set under f is convex 5 g R convex f5 fx X E 5 convex gt the inverse image f 1C of a convex set under f is convex C Q Rm convex f lC X E R fx 6 C convex examples gt scaling translation projection gt solution set of linear matrix inequality x X1A1 xmAm j B with A B 6 SP gt hyperbolic cone x XTPX g CTX27 ch Z O with P 6 Si IOE 611 Nonlinear Programmlng Winter 2008 2 Convex set Page 2e13 Perspective and linear fractional function perspective function P Rquot1 gt Rquot Pxtxt7 domPx7 t tgt0 images and inverse images of convex sets under perspective are convex linearfractional function f R gt Rm Axb Z T CTXd domf xc xdgt0 fX images and inverse images of convex sets under linear fractional functions are convex IOE 611 Nonlinear Programmlng Wlnler 2008 2 Convex set Page 2e14 example of a linear fractional function 1 f X X X1 X2 1 1 1 5 0 5 0 71 71 1 1 m1 m1 IOE 611 Nonllnear Programmlng Winter 2008 2 Convex sec Page 2715 Separating hyperplane theorem if C and D are disjoint convex sets then there exists a 75 O b such that aTxgbforXEC7 aszbforXED O Supporting hyperplane theorem supporting hyperplane to set C at boundary point X0 X aTX aTXo where a 75 O and aTX g aTXO for all X E C Generalized inequalities generalized inequality defined by a proper cone K XjKy ltgt y XEK7 XltKy ltgt y XeintK examples gt componentwise inequality K R1 XjRiy ltgt Xigyi7 i1n gt matrix inequality K 1 X jg Y ltgt Y X positive semidefinite these two types are so common that we drop the subscript in jK properties many properties of jK are similar to g on R eg ija quv 2 xquyv IOE 611 Nonlinear Programmmg Winter 2008 2 Convex set Page 249 Minimum and minimal elements jK is not in general a linear ordering we can have X K y and y K X X E 5 is the minimum element of 5 with respect to jK if yes XjKy equivalently5 xK X E 5 is a minimal element of 5 with respect to jK if y e 57 y jK X 2 y X equivalently X K 5 example K R1 X1 is the minimum element of 51 X2 is a minimal element of 52 Dual cones and generalized inequalities dual cone ofa cone K KyyTX20forallX K examples gt K R1 K R gt K 1 K 1 gt K x t X2 t K x t X2 t gt K xtgtIIIxII1 t K x t I llxlloo t first three examples are selfdual cones dual cones of proper cones are proper hence define generalized inequalities ytmo ltgt yTX20forallX KO IOE 611 Nonlinear Programmmg Winter 2008 2 Convex gel Page 241 Minimum and minimal elements via dual inequalities minimum element wrt jK X is minimum element of 5 iff for all A gtK O X is the unique minimizer of ATZ over 5 Convex optimization problems gt optimization problem in standard form gt convex optimization problems gt linear optimization gt quadratic optimization gt geometric programming gt quasiconvex optimization gt generalized inequality constraints gt semidefinite programming gt vector optimization IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problem Page 4e1 Optimization problem in standard form minimize f0X subject to x g 07 i 17 hXO7 i1p gt X E R is the optimization variable gt f0 R gt R is the objective or cost function gt f R gt R i 17 7 m are the inequality constraint functions gt h R gt R are the equality constraint functions optimal value pinffoxfX O7 i1m7 hXO7 i1p gt p 00 if problem is infeasible no X satisfies the constraints gt p 2 oo if problem is unbounded below IOE e11 Nonlinear Programmmg Wlnler 2008 4 Convex opllmlzallon problem Page 1L2 Optimal and locally optimal points gt x is feasible if X E dom f0 and it satisfies the constraints gt a feasible X is optimal if foX p Opt is the set of optimal pomts gt X is locally optimal if there is an R gt 0 such that X is optimal for minimize over 2 162 subject to fz g 07 i 17m7 hz07 i1p IV anR examples with n 1 m p O gt foX 1X dom f0 R p 0 no optimal point gt f0X logX dom f0 R p 2 oo gt foX XlogX dom f0 R p 1e X 16 is optimal gt f0X X3 3X p 2 oo local optimum at X 1 IOE 611 NonllnearProgrammlngWinler2008 4 Convexoplimlzalion problem Page 44 Implicit constraints The standard form optimization problem has an implicit constraint m p Xe Dz domf domhi7 iO il gt we call D the domain of the problem gt the constraints fX g 0 hX O are the explicit constraints gt a problem is unconstrained if it has no explicit constraints m p 0 example minimize f0X 21 logb aITX is an unconstrained problem with implicit constraints aITXlt b7 i 17k IOE e11 Nonlinear Programmmg Wlnter 2008 4 Convex optlmlzatlon problem Page H Feasibility problem find X subject to x g 07 i 17m hXO7 i1p can be considered a special case of the general problem with f0X O minimize 0 subject to x g 07 i 17m hXO7 i1p gt p 0 if constraints are feasible any feasible X is optimal gt p 2 00 if constraints are infeasible IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problem Page 4e5 Standard form convex optimization problem minimize f0x subject to x g 07 i 17m aIszb7 i 7p gt 1 f1 fm are convex equality constraints are affine gt problem is quasiconvex if f0 is quasiconvex and f1 fm convex often written as minimize f0x subject to x g 07 i 17 7 m Ax b important property feasible set of a convex optimization problem is convex IOE e11 Nonlinear Programmmg Wlnler 2008 4 Convex opllmlzallon problem Page 44 Standard form convex optimization problem Example minimize foX X X22 subject to f1X 2 X11 X22 S O h1xx1x22 o gt f0 is convex feasible set X17X2 X1 2 X2 3 O is convex gt not a convex problem according to our definition fl is not convex hl is not affine gt equivalent but not identical to the convex problem minimize Xf X22 subject to X1 3 0 X1 X2 O IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problems Page 4e7 Local and global optima Any locally optimal point of a convex problem is globally optimal proof suppose X is locally optimal and y is feasible with 160 lt foX X locally optimal means there is an R gt 0 such that z feasible7 z XII2 S R 2 152 2 f0X Consider z 2 6y 1 6X with 6 R2lly Xll2 gt lly X2 gt R so Olt0lt 12 gt z is a convex combination of two feasible points hence also feasible gt z X2 R2 and 152 S 9foX 1 9fo lt foX7 which contradicts our assumption that X is locally optimal IOE e11 Nonlinear Programmmg Wlnler 2008 4 Convex opllmlzallon problem Page Ls Optimality criterion for differentiable 1 6 X is optimal if and only if it is feasible and VfoXTy X Z O for all feasible y if nonzero Vf0X defines a supporting hyperplane to feasible set X at X IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problems Page 4e9 Optimality criterion special cases gt unconstrained problem X is optimal if and only if X E dom f07 Vf0X O gt equality constrained problem minimize f0X subject to AX b X is optimal if and only if there exists a 1 such that Xedomfo szb Vf0XATzO gt minimization over nonnegative orthant minimize f0X subject to X t O X is optimal if and only if VfoX gt O X O gt X d mf07 X O VfoxO XgtO IOE 611 Nonlinear Programmlng Wlnler 2008 4 Convex opllmlzallon problems Page 4e10 Equivalent convex problems two problems are informally equivalent if the solution of one is readily obtained from the solution of the other and vice versa Some common transformations that preserve convexity gt eliminating equality constraints minimize f0X subject to fx g 0 i 1m AX b is equivalent to minimize over 2 foFzXo subject to fFz X0 g 0 i 1 m where F and X0 are such that AXb ltgt XFzxo forsomez IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problem Page 4e11 Equivalent convex problems gt introducing equality constraints minimize 16on be subject to Aix b g 0 i 1 m is equivalent to minimize over X y foo0 subject to fy g 0 i 1 m yizAiX l39bh 20717 gt introducing slack variables for linear inequalities minimize f0x subjectto afxgbi i1m is equivalent to minimize over X 5 f0x subjectto aiTxsb i1m 520 i1m IOE 611 Nonlinear Programmlng Wlnler 2008 4 Convex optlmlzallon problem Page 442 Equivalent convex problems gt epigraph form standard form convex problem is equivalent to minimize over X t t subject to f0X t g 0 fX O7 i1m AXb gt minimizing over some variables minimize foX1X2 subject to fx1 g 07 i 17 7 m is equivalent to minimize foxl subject to fx1 g 07 i 17 7 m where foX1 ian2 foX1X2 IOE 611 Nonlinear Programmmg Winter 2008 4 Convex optimlzalion problem Page 4e13 Linear program LP minimize cTX l d subject to GX j h AX b gt convex problem with affine objective and constraint functions gt feasible set is a polyhedron Examples diet problem choose quantities X17 Xn of n foods gt one unit of food j costs cj contains amount 31 of nutrient i gt healthy diet requires nutrient i in quantity at least b to find cheapest healthy diet minimize CTX subject to AX t b7 X t O piecewiselinear minimization minimize max17m7maITX b equivalent to an LP minimize t subject to ail x b S t7 i 1 77 IOE 611 Nonlinear Programming Winter 2008 4 Convex optimlzalion problem Page 4e15 Chebyshev center of a polyhedron Chebyshev center of PXaTX b7 i1m is center of largest inscribed ball BXculllull2r Quadratic program QP minimize 12XTpxqTxr subject to GX j h AX b gt P E S so objective is convex quadratic gt minimize a convex quadratic function over a polyhedron Quadratically constrained quadratic program QCQP minimize 12XTP0X qg X r0 subject to 12XTPX qITX r g O7 AX b i1m gt P 6 Si objective and constraints are convex quadratic gt if P1 Pm 6 51 feasible region is intersection of m ellipsoids and an affine set IOE 611 Nonllnear Programmlng Winter 2008 4 Convex optimlzalion problem Page 4e19 Second order cone programming minimize f TX subject to AX b2 g CiTX d7 i 17 7 m FX 2 g A E Rquotquot F 6 RP gt inequalities are called second order cone SOC constraints AX b7 CiTX 61 E second order cone in Rnquot1 gt for n 0 reduces to an LP if c 0 reduces to a QCQP gt more general than QCQP and LP IOE 611 Nonlinear Programmmg Wlnler 2008 4 Convex opllmlzallon problem Page 440 Robust linear programming the parameters in optimization problems are often uncertain eg in an LP minimize CTX subject to an b i 1m there can be uncertainty in c a b two common approaches to handling uncertainty in a for simplicity gt deterministic model constraints must hold for all a E 639 minimize CTX subjectto ail ngforalla 8 i1m gt stochastic model a is random variable constraints must hold with probability 77 minimize CTX subject to probaTX g b 2 77 i 1 m IOE 611 Nonllnear Programmlng Winter 2008 4 Convex optimization problem Page 441 Deterministic approach via SOCP gt choose an ellipsoid as 8 639 32 Pu u2 g 1 5 e R P 6 RM center is 5 semi axes determined by singular valuesvectors Of P gt robust LP minimize CTX subject to aiTX g b Va 6 8 i 1 m is equivalent to the SOCP minimize CTX subject to 5Tx PlTle g b i 1 m follows from supHuH2 1 PuTX EITX PiTX2 IOE 611 Nonllnear Programmlng Wlnler 2008 4 Convex optimization problem Page 22 Stochastic approach via SOCP gt assume a is Gaussian with mean 5 covariance X a N N gt aiTX is Gaussian rv with mean 5 X variance XTXX hence T probaTxgbCD IIX X2 where qgtx Mm foo e t22 dt is CDF of No 1 gt robust LP minimize CTX subject to probaTX g b 2 77 i 1 m with 77 2 12 is equivalent to the SOCP minimize CTX afx 1nIIZ2XII2 be i 1 4 Convex optimization problem subject to IOE 611 Nonllnear Programmlng Winter 2008 Page 4e23 Geometric programming monomial function fX CXalva 2 l Xnn n dom f R with c gt O exponent oz can be any real number posynomial function sum of monomials K a a a n fX E ckxllkx22kxnquotk domf R k l geometric program GP minimize f0X subject to x g 1 i 1 m hX 1 i 1p with f posynomial h monomial IOE e11 Nonlinear Programmlng Wlnter 2008 4 Convex optlmlzatlon problem Page 444 Geometric program in convex form change variables to y log Xi and take logarithm of cost constraints gt monomial fX cxf1x quot transforms to logfey1eyquotaTyb blogc gt posynomial fX 2551 ckxflkxgzquot Xquot transforms to K T log fey1eyquot log Zea le bk log ck kl gt geometric program transforms to convex problem K T minimize log Zk expaOky bOk subject to log 2551 expai7y bik g 07 i 17 7 m Gy d O IOE 611 Nonlinear Programming Winter 2008 4 Convex optimization problems Page 25 Design of cantilever beam segment 4 segment 3 segment 2 segment 1 gt N segments with unit lengths rectangular cross sections of size W X h gt given vertical force F applied at the right end design problem minimize total weight subject to upper amp lower bounds on W h upper bound amp lower bounds on aspect ratios hw upper bound on stress in each segment upper bound on vertical deflection at the end of the beam variables W h for i 17 7 N IOE 611 Nonlinear Programming winter 2008 4 Convex optimization problems Page 26 Objective and constraint functions gt total weight Wlhl WNhN is posynomial gt aspect ratio hiw and inverse aspect ratio wih are monomials V maximum stress in segment i is given by 6iFwihf a monomial V the vertical deflection y and slope V of central axis at the right end of segment i are defined recursively as F V Vi1 F Y 6I 13m Vi1 YI1 I i for i N N 1 1 with VN1 yNH O E is Young s modulus v and y are posynomial functions of W h IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problem Page 27 Formulation as a GP minimize Wlhl WNhN subject to Wrg xwi g 1 Wminwf1 g 1 i 1 hggxh g 1 hminhi l g 1 i 1N Srg xwflh g 1 sminmhfl g 1 i 1 71 71 e2 6Famaxwi h g 1 I 1 yni xyl 1 note gt we write Wmin lt W lt Wmax and hmin lt h g hmax WminWi S 17 WiWmax S 17 hminhi S 17 hihmax S 1 gt we write 5min g hiW g Smax as 5minWihi S 17 S 1 gt The number of monomials appearing in yl grows approximately as N2 08 IOE e11 Nonlinear Programmlng Wlnler 20 4 Convex opllmlzallon problem Page 28 Minimizing spectral radius of nonnegative matrix PerronFrobenius eigenvalue ApfA gt Consider elementwise nonnegative A 6 RM that is irreducible I A 1 gt O gt P F Theorem there is a real positive eigenvalue of A Apf equal to spectral radius max A gt determines asymptotic growth decay rate of Ak Ak All as k gt 00 gt alternative characterization ApfA inf Av j Av for some V gt O minimizing spectral radius of matrix of posynomials gt minimize ApfAx where the elements Axj are posynomials of X gt equivalent geometric program minimize A subject to 2171 AxjvjV g 17 i 17 7 n variables A v X IOE 611 Nonlinear Programming Winter 2008 4 Convex optimlzalion problem Page 29 Quasiconvex functions f R gt R is quasiconvex if dom f is convex and the sublevel sets 5axedomffx ga are convex for all a Examples gt X is quasiconvex on R gt ce11x infz E Z z 2 X is quasilinear gt logX is quasilinear on R gt fX1X2 X1X2 is quasiconcave on Ri D linear fractional function a X b 16X C7Xd7 domfXCTX l dgt0 is quasilinear gt distance ratio X a x M dom f XI le a2 le bllz X b2 is quasiconvex IOE 611 Nonllnear ProgrammmgWimer2008 4 Convex optimlzalion problem Page 441 Internal rate of return V cash flow X X07 7Xquot X is payment in period i to us if X gt 0 we assumeXo lt O and X0X1Xn gt 0 VV present value of cash flow X for interest rate r n PVX7 r 1 r x 0 internal rate of return is smallest interest rate for which PVX7 r O V IRRX infr Z O PVX7 r O IRR is quasiconcave superlevel set is intersection of halfspaces n IRRX Z R ltgt Z1 r X Z O for 0 g r g R 0 IOE 611 Nonlinear Programming Winter 2008 4 Convex opllmlzallon problem Page 442 Properties modified Jensen inequality for quasiconvex f 0 g 6 g 1 f0x 1 0y g maxfx7 fy firstorder condition differentiable f with cvx domain is quasiconvex iff fyfx VfxTy xgo Convex representation of sublevel sets of f6 if f0 is quasiconvex there exists a family of functions pt such that gt tX is convex in X for fixed t gt t sublevel set of f0 is O sublevel set of pt ie moste mwso gt tX is non increasing in t for fixed X example p X foX m with p convex q concave and pX Z O qX gt O on dom f0 can take tX pX tqX gt for t Z 0 pt convex in X gt pXqX g t if and only if tX g 0 gt If 5 Z t pX tqX Z pX 5qX IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problem Page 4e35 Quasiconvex optimization via convex feasibility problems emsq MSQiL my Mb0 gt for fixed t a convex feasibility problem in X gt if feasible we can conclude that t 2 p if infeasible t g p Bisection method for quasiconveX optimization given lg p u 2 p tolerance e gt 0 repeat 1 t I u2 2 Solve the convex feasibility problem 3 if 1 is feasible u t else I t until u 7 g e requires exactly flog2u 06 iterations where u are initial values IOE 611 Nonlinear Programmlng Wlnler 2008 4 Convex opllmlzallon problem Page 446 Generalized linear fractional program minimize f0x subject to Gx j h Ax b linearfractional program CTX d T f0xm domfoxxe xfgt0 gt a quasiconvex optimization problem can be solved by bisection gt also if feasible equivalent to the LP variables y z minimize CTy dz subject to Gy j hz Ay bz eT y fz 1 z 2 O IOE 611 Nonllnear Programmlng Winter 2008 4 Convex optimlzalion problem Page 4e37 Generalized linear fractional program T d f0x max Ll dom f0x x eiTxfi gt O i 1 r i1r eiTx l a quasiconvex optimization problem can be solved by bisection example Von Neumann model of a growing economy maximize over X xl min17m7XIx subject to x t O Bx j Ax gt xx E Rquot activity levels of n sectors in current and next period gt Ax Bxl produced resp consumed amounts of good i gt xilxi growth rate of sector i allocate activity to maximize growth rate of slowest growing sector IOE 611 Nonlinear Programming Winter 2008 4 Convex opllmlzallon problems Page 448 Convexity of vector valued functions f R gt R is K convex if dom f is convex and OX 1 9W jK 0fX 1 9WD forxy domf 0363 1 example f S gt 5 fX X2 is ST convex proof for fixed Z 6 Rm ZTX2Z is convex in X ie zT6X 1 6 Y2z g 62TX2Z 1 6ZTY2Z forX7Y SmO 6 1 therefore 6X 1 6 Y2 j 6X2 1 6 Y2 IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problem Page 449 Generalized inequality constraints convex problem with generalized inequality constraints minimize fox subject to x jKl 07 i 17 7 m Ax b gt f0 R gt R convex f R gt Rk Ki convex wrt proper cone K gt same properties as standard convex problem convex feasible set local optimum is global etc conic form problem special case with affine objective and constraints minimize ch subject to Fx g jK O Ax b extends linear programming K 2 RT to nonpolyhedral cones IOE 611 Nonlinear Programmlng Wlnler 2008 4 Convex opllmlzallon problem Page 440 Semidefinite program SDP minimize CTX SUbjeCt t0 X1F1 X2F2 ann G j 0 AX b with F G e 5quot gt inequality constraint is called linear matrix inequality LMI gt includes problems with multiple LMI constraints for example x1 1xn n jq x1F1xFCjO is equivalent to single LMI X 31 o H 32 o X n o 6 o 1 o 51 2 o 52 0 ff 0 C IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problems Page 441 LP and SOCP as SDP LP and equivalent SDP LP minimize CTX SDP minimize CTX subject to AX j b subject to diagAX b j 0 note different interpretation of generalized inequality j SOCP and equivalent SDP SOCP minimize fTX subject to AX b2 g CiTX d7 i 1 77 SDP minimize fTX T Cixdl AXb gt0 1 subject to Aixbi7 CITXdi 7 7 IOE 611 Nonlinear Programmlng Wlnler 2008 4 Convex opllmlzallon problems Page 442 Eigenvalue minimization minimize AmaXAX where AX A0 XlAl XnAn with given A E 5quot equivalent SDP minimize t subject to AX j tl gt variables X e R t e R gt follows from S t ltgt A j t IOE 611 Nonlinear Programmlng Winter 2008 4 Convex optimlzalion problems Page 443 Matrix norm minimization minimize AX2 AmaxAXTAXl2 where AX A0 XlAl XnAn with given A e Rpxq equivalent SDP minimize t tl AX subject to AXT t gtO gt variables X E Rquot t E R gt constraint follows from A2gt ltgt ATAjt2I 1 20 1 AJEO lt N t IOE e11 Nonlinear Programming Winter 2008 4 Convex optimization problem Page H4 Vector optimization general vector optimization problem minimize wrt K f0X subject to fX g 07 i 1 hiXS07 vector objective f0 R gt Rq minimized wrt proper cone K E Rq convex vector optimization problem minimize wrt K f0X subject to fX g 07 i 17 7 m AX b with f0 K convex f1 fm convex IOE 611 Nonllnear Programmlng Winter 2008 4 Convex optimlzalion problem Page 445 Optimal and Pareto optimal points set of achievable objective values 9 f0X X feasible gt feasible X is optimal if f0X is a minimum value of O gt feasible X is Pareto optimal if f0X is a minimal value of O Multicriterion optimization vector optimization problem with K R1 1XF1X77Fqx gt q different objectives F roughly speaking we want all Fi s to be small gt feasible X is optimal if y feasible f0X j f0y if there exists an optimal point the objectives are noncompeting gt feasible Xp0 is Pareto optimal if y feasible7 f0y j f0XpO f0XpO f0y if there are multiple Pareto optimal values there is a trade off between the objectives IOE 611 Nonlinear Programming Winter 2008 4 Convex optimlzalion problems Page 1H7 Regularized least squares multicriterion problem with two objectives F1X IIAX blliy F2X X gt example with A e RlOOgtltlO gt shaded region is O gt heavy line is formed by Pareto optimal points Risk return trade off in portfolio optimization minimize w rt R1 pTXXTXX subject to 1TX 17 X t O gt X E R is investment portfolio X is fraction invested in asset i gt p E R is vector of relative asset price changes modeled as a random variable with mean f covariance X gt pTX E r is expected return XTXX 2 var r is return variance example Convex functions basic properties and examples operations that preserve convexity the conjugate function quasiconvex functions log concave and log convex functions VVVVVV convexity with respect to generalized inequalities IOE 611 Nonlinear Programmmg Winter 2008 3 Convex function Page 1 Definition f R gt R is convex if dom f is a convex set and f6x 1 6y g 6fX 1 6fy forallX7y domfO 6 1 Examples on R convex gt affine ax b on R for any a b e R gt exponential e for any a E R gt powers xo on R11 for a Z 1 or a g 0 gt powers of absolute value xp on R for p Z 1 gt negative entropy Xlogx on R11 concave gt affine ax b on R for any a b e R gt powers xo on R11 for 0 g a g 1 gt logarithm logx on R11 IOE 611 Nonlinear Programmlng Winter 2008 3 Convex function Page 33 Examples on R and RmX affine functions are convex and concave all norms are convex examples on R gt affine function fx aTx b gt norms xp 2 271 xp1p for p Z 1 xoo maxk lel examples on RmXquot m x n matrices gt affine function m n fX trATX b Z ZAny b i1 jl gt spectral maximum singular value norm 1 0 X2 UmaxX AmaxXTXl2 IOE 611 Nonlinear Programmlng Wlnler 2008 3 Convex function Page 34 Restriction of a convex function to a line f R gt R is convex if and only if the function g R gt R gtlfx1 V7 domgtxtvedomf is convex in t for any X E dom f V E R So can check convexity of f by checking convexity of functions of one variable example f Squot gt R with fX logdetX domX 2 51 log detX tV log detX log detl tX 12 VX 12 gt n log detX Z log1 t i1 where A are the eigenvalues of X l2 VX l2 g is concave in t for any choice ofX gt O V hence f is concave IOE 611 Nonlinear Programmmg Winter 2008 3 Convex function Page 5 First order condition f is differentiable if dom f is open and the gradient 8fx 8fx 8fx Vfxlt8X178X27 78Xngt exists at each X E dom f lstorder condition differentiable f with convex domain is convex iff fy 2 fx VfxTy x for all xy e dom f gradient inequality Second order conditions f is twice differentiable if dom f is open and the Hessian V2fX E Squot 82fx 8X8Xj 7 7 v2fxj exists at each X E dom f 2ndorder conditions for twice differentiable f with convex domain gt f is convex if and only if V2fX t O for all X E dom f gt if V2 fX gt O for all X E dom f then f is strictly convex IOE 611 Nonlinear Programmmg Winter 2008 3 Convex function Page 3H Examples quadratic function fX 12XTPX qTX r with P e S VfXPxq7 V2fXP convex if P t O leastsquares objective fX AX Woo 2ATAx b V2fx 2ATA convex for any A quadraticoverlinear fX7 y X2y y H y ilo X convex for y gt O Examples logsumexp fX log 221 exp Xk is convex V2fx i dia z LZZT z ex X 1T2 g lTZ2 k P k to show V2fx t O we must verify that VTV2fXv Z O for all v VTV2fXV 2k 2k Vka2 Z 0 since 2k vkzk2 3 2k zkvExzk 2k from Cauchy Schwarz inequality geometric mean fX 1121 Xk1 on R1 is concave similar proof as for log sum exp IOE 611 Nonlinear Programming Winter 2008 3 Convex function Page 9 Sublevel set and Epigraph asublevel set of f R gt R CaX domf fX ga sublevel sets of convex functions are convex converse is false epigraph of f R gt R epif 2 X7 t E Rquot1 X E dom if7 fX g t Jensen39s inequality basic inequality if f is convex then for 0 g 6 g 1 f6x 1 6y g 6fX 1 6fy extension if f is convex then fE 2 g E fz for any random variable 2 st PZ E dom f 1 basic inequality is special case with discrete distribution probz X 6 probz y 1 6 IOE 611 Nonlinear Programmlng Winter 2008 3 Convex functions Page 11 Operations that preserve convexity practical methods for establishing convexity of a function 1 1 verify definition often simplified by restricting to a line 2 for twice differentiable functions show V2fx t O show that f is obtained from simple convex functions by operations that preserve convexity U nonnegative weighted sum composition with affine function pointwise maximum and supremum composition minimization perspective VVVVVV IOE 611 Nonlinear Programmlng Wlnler 2008 3 Convex functions Page 12 Positive weighted sum amp composition with affine function nonnegative multiple af is convex if f is convex a Z 0 sum f1 f2 convex if f1 f2 convex extends to infinite sums integrals composition with affine function fAx b is convex if f is convex examples gt log barrier for linear inequalities fx Zlogb aITx domf x aiTXlt bi 1m i1 gt any norm of affine function fx Ax b IOE 611 Nonlinear Programmlng Winter 2008 3 Convex function Page 13 Pointwise maximum if f1 fm are convex then fx maxf1x fmx is convex examples gt piecewise linear function fx max17m7maITx b is convex gt sum of r largest components ofx E Rquot RX X1 X2 X is convex x is ith largest component of x proof fxmaxx1x2x1 i1lti2ltlti n IOE 611 Nonlinear Programmlng Wlnler 2008 3 Convex function Page 14 Pointwise supremum if fxy is convex in X for each y E A then gX SUP fX7y yEA is convex examples gt support function of a set C 5CX supyecyTx is convex gt distance to farthest point in a set C W sup IIX yll yEC gt maximum eigenvalue of symmetric matrix for X E S AmaXX sup yTXy H iFl IOE 611 Nonlinear Programmlng Winter 2008 3 Convex function Page 15 Extended value extension extended value extension f of f is fxfx7 XEdomf7 fxoo7 X domf often simplifies notation for example the condition 0 g 0 g 1 f6x 1 0y g 6fx 1 0fy as an inequality in R U means the same as the two conditions gt dom f is convex gt forxy domf 03631 f0x1 6ygofx1 0fy IOE 611 Nonlinear Programmlng Wlnler 2008 3 Convex function Page 16 Composition with scalar functions composition ofg R gt R and h R gt R fX hgX f f g convex h convex h nondecreasing IS convex I g concave h convex h nonlncreasmg gt proof for n 1 twice differentiable g h defined everywhere VX h ggtltgX2 hgXg X gt note monotonicity must hold for extended value extension h examples gt exp gx is convex if g is convex gt 1gx is convex if g is concave and positive IOE 611 Nonlinear Programmlng Winter 2008 3 Convex function Page 17 Vector composition composition ofg R gt Rquot and h Rquot gt R 1 00 hgX hg1X7g2X7 7gkX f is convex if gi s convex h convex h nondecreasing in each argument gi s concave h convex h nonincreasing in each argument proof for n 1 twice differentiable g h defined everywhere VX gXTV2hgXgX VhgXTgX examples gt log gx is concave if g are concave and positive gt log expgx is convex if g are convex IOE 611 Nonlinear Programmlng Wlnler 2008 3 Convex function Page 18 Minimization if fxy is convex in x7y and C is a convex set then gX inf fX7y yEC is convex examples gt fxy XTAX 2XTBy yTCy with BAT EO Cgt0 minimizing over y gives gx infy fxy XTA BC lBTx g is convex hence Schur complement A BC lBT t O gt distance to a set distx7 5 infyes x y is convex if 5 is convex IOE 611 Nonlinear Programmmg Winter 2008 3 Convex function Page 19 Perspective the perspective of a function f R gt R is the function g R x R gt R gx7 t tfxt7 domg x7 t Xt E dom if7 t gt 0 g is convex if f is convex examples gt fx xTx is convex hence gx7 t xTxt is convex for t gt O gt negative logarithm fx logx is convex hence relative entropy gx7 t t log t t logx is convex on Ri V if f is convex then gx ch df Ax bch d is convex on x CTXld gt 07 AxbCTxd e dom f IOE 611 Nonlinear Programmmg Wlnler 2008 3 Convex function Page 20 The conjugate function the conjugate of a function f is W X68313quot yTX fX Quasiconvex functions f R gt R is quasiconvex if dom f is convex and the sublevel sets 5axedomffx ga are convex for all a Internal rate of return gt cash flow X X07 7Xquot X is payment in period i to us if X gt 0 gt we assumeXo ltOand X0X1Xngt0 V present value of cash flow X for interest rate r n PVX7 r 1 r x 0 internal rate of return is smallest interest rate for which PVX7 r O V IRRX infr Z O PVX7 r O IRR is quasiconcave superlevel set is intersection of halfspaces n IRRX Z R ltgt Z1 r X Z O for 0 g r g R 0 IOE 611 Nonlinear Programming Winter 2008 3 Convex function Page 25 Properties modified Jensen inequality for quasiconvex f 0 g 6 g 1 f0x 1 0y g maxfx7 fy firstorder condition differentiable f with cvx domain is quasiconvex iff fyfx VfxTy xgo Examples of SDP problems gt Convex Optimization gt Eigenvalue problems gt logdetX problems gt Combinatorial optimization MAX CUT 0 611 Inter 2008 Convex problem extra SDP age 1 Forms of SDP problems gt Data C A i 17 m symmetric matrices gt Standard dual form m SDD maximizey Z yb 1 m St C Z yiA t O i1 gt An LMl constraint Mz t 0 where z E Rquot and M Rquot gt 5quot is a linear matrix valued function gt Standard primal form SDP minimizeX trCX st trAX b7 i1m7 X t O 0 611 Inter 2008 Convex problem extra SDP age 2 Example 1 0 2 8 11 1 2 3 7A2260blt gtandC290 5 8 0 4 3 0 7 SDD maximize 11y119y2 1 0 1 which we can rewrite in the following form SDD maximize 11y119y2 st lib1 0 2OY1ZY2 31J1 8 2 011 212 93J1 6Y2 07J1 0 i0 31Y1i8 077y170y2 75J1 4J2 Convex problem extra SDP Example 1 0 1 0 2 8 11 2 3 A1 0 3 7 A2 2 6 o blt19gtandC 2 9 o 1 7 5 8 0 4 0 7 I minimize X11 4X12 6X13 9X22 0X23 7X33 st X11 0x12 2X13 3X22 14X23 5X33 11 OX11 4X12 16X13 6X22 0X23 4X33 19 X11 X12 X13 X X21 X22 X23 i Q X31 X32 X33 0 611 Int2r 2008 Convex problem extra SDP age 4 SDP in Convex Optimization Eigenvalue Optimization Typical Eigenvalue Problems gt We are given symmetric matrices B and A i 17 k gt We choose weights W1 wk to create a new matrix 5 k s B Z wA i1 gt There might be restrictions on the weights w GW 3 d gt The typical goal is for 5 to have some nice property such as gt Amin5 is maximized gt XMAS is minimized gt XMAS 7 Amin5 is minimized 0 611 Int2r 2008 Convex problem extra SDP age 5 SDP in Convex Optimization Eigenvalue Optimization Useful Relationships Property M t t if and only if AminM Z t Proof M QDQT Consider R defined as R M t QDQT tQIQT QD tIQT Then Mttl ltgt R50 ltgt D tltO ltgt AminM2t Property M j t if and only if AmaXM g t Proof v 2 271 aiqi where qi s are orthonormal e vectors of M n M j t ltgt VTtI MV 2 ovv ltgt Z at A 2 mm ltgt AmaXM g t Convewib39ems SDP SDP in Convex Optimization Eigenvalue Optimization Consider the problem EOP minimize W75 St This is equivalent to EOP minimize W7 57 M7 A St This is an SDP Convex problem extra SDP maxs mins k SB ZWA i1 ngd u A k SB ZWA i1 ngd AIKSij Matrix norm minimization minimize Ax2 AmaXAXTAxl2 where AX A0 X1A1 XnAn with given A 6 RPM equivalent SDP minimize t tl subject to gt variables X e Rquot t e R gt constraint follows from A2 g t ltgt ATA j RI e l AX T t0 tl Ax 1 20 ieo tl AT A tl using Schur complement 5 t Ale4 0 611 Int2r 2008 Convex problems extra SDP SDP in Convex Optimization The Logarithmic Barrier Function gt Let X 6 Si gt X will have n eigenvalues x1X7 X gt We have show that the following function of X is convex BX Z nX nH AX ndetX 1 1 1 gt This function is called the logdeterminant function or the logarithmic barrier function for the semidefinite cone gt The name barrier function stems from the fact that BX gt 00 as X approaches boundary of 51 85 X6 5quot AjX Z 0j1n and AjX 0for somej 0 611 Int2r 2008 Convex problem extra SDP age 9 SDP in Convex Optimization The Analytic Center Problem for SDP gt An LMI m j C7 i1 gt The analytic center is the solution 9 of st 2 yA s c s 5 o ACP maximizeyys PIX5 i l gt This is the same as ACP minimizeyys ln det5 st yiA 5 C S gt O gt f is centrally located in the set of solutions of the LMI Convewib39ems SDP SDP in Convex Optimization Minimum Volume Circumscription Problem gt Given R gt O z E Rquot can be used to define an ellipsoid in R ERz y y ZTRy Z S 1 gt Volume of ER is proportional to xdetR 1 gt Given a convex set X convc17 Ck C R find an ellipsoid circumscribing X that has minimum volume SDP SDP in Convex Optimization Minimum Volume Circumscription Problem gt Problem formulation MCP minimizeRyz vol ERyz St CIEERJ7 i1k gt Equivalent to MCP minimizeRyz lndetR st C zTRC z 17 i1k R gt O gt Factor R M2 where M gt O MCP minimize 47Z lndetM2 st C zT T C zg17 i1k M gt O SDP SDP in Convex Optimization Minimum Volume Circumscription Problem MCP minimizeMZ ilndetM2 st cizTMTMciz 17 177k M gt 0 gt Next notice the equivalence I MC 7 M2 I T T I Mciisz 1 t0 ltgt Q72 M Mciz 1 gt In this way we can write MCP as MCP minimizeMZ 72lndetM I MC 7 M2 7 st MaiWAT 1 07 I 177k7 M gt 0 gt Substitute y M2 to obtain MCP minimizeWy 72lndetM l Mc 7y i st Mciiyf 07 1717 717 gt 0 CW Pmb39m We SDP SDP in Convex Optimization Minimum Volume Circumscription Problem MCP minimizemy 72lndetM I St MC 7yT 1 M x 0 gt Semidefinite constraints gt All of the matrix coefficients are linear functions of the variables M and y gt Objective is the logarithmic barrier function lndetM gt Easy to solve gt After solving recover the matrix R and the center 2 of the optimal ellipsoid by computing RM2 andzM71y SDP SDP in Combinatorial Optimization MAX CUT Problem gt G is an undirected graph with nodes N 17 n and edge set E gt Let WU Wj be the weight on edge ij for ij E E gt We assume that WU Z O for all ij E E gt The MAX CUT problem is to determine a subset 5 of the nodes N for which the sum of the weights of the edges that cross from 5 to its complement 5 is maximized gt 3NS SDP SDP in Combinatorial Optimization MAX CUT Problem Formulations gt Leth1forjeSandy2 1forjeg MAXCUT maximizeX wij1 XXj st XJIZlJEflJ j1n gt Let YXXT Then YJXXj7 i1n7 j1n gt Let WERMquot with WU WU for ij1n gt Reformulation MAXCUT maximizeyyx Z Z WU trWY iljl st Xj 11j1n YXX SDP SDP in Combinatorial Optimization MAX CUT Problem Formulations n MAXCUT maximizeyyx l2 j 171j1n T WU trWY 396 Y st ox i gt The first set of constraints are equivalent to YJj1 j1n MAXCUT maximizeyyx 2 W0 trWY iljl st Yl17 j1n Y XXT SDP SDP in Combinatorial Optimization MAX CUT Problem Relaxation MAXCUT maximizeyyx Z st jzlvquot 7n gt Constraint Y XXT is equivalent to Y a symmetric positive semidefinite matrix of rank 1 gt We relax this condition by removing the rank 1 restriction and obtain the relaxation of MAX CUT which is an SDP RELAX maximizey Z WU trWY iljl st 31721 j1n Y t O gt MAXCUT g RELAX Convewib39em SDP

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.