2.3 Convex Constrained Optimization Problems


 Gabriel Benson
 5 years ago
 Views:
Transcription
1 42 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION Theorem 15 Let f : R n R and h : R R. Consider g(x) = h(f(x)) for all x R n. The function g is convex if either of the following two conditions is satisfied: (1) f is convex, h is nondecreasing and convex. (2) f is concave, h is nonincreasing and convex. By applying Theorem 15, we can see that: 1 f(x) e f(x) is convex if f is convex, is convex if f is concave and f(x) > 0 for all x. 2.3 Convex Constrained Optimization Problems In this section, we consider a generic convex constrained optimization problem. We introduce the basic terminology, and study the existence of solutions and the optimality conditions. We conclude this section with the projection problem and projection theorem. which is important for the subsequent algorithmic development Constrained Problem Consider the following constrained optimization problem minimize f(x) subject to g 1 (x) 0,..., g m (x) 0 Bx = d x X, (2.5) where f : R n R is an objective function, X R n is a given set, g i : R n R, i = 1,..., m are constraint functions, B is a p n matrix, and d R p. Let g(x) 0 compactly denote the inequalities g 1 (x) 0,..., g m (x) 0. Define C = {x R n g(x) 0, Bx = d, x X}. (2.6) We refer to the set C as constraint set or feasible set. The problem is feasible when C is nonempty. We refer to the value inf x C f(x) as the optimal value and denote it by f, i.e., f = inf x C f(x), where C is given by Eq. (2.6). A vector x is optimal (solution) when x is feasible and attains the optimal value f, i.e., g(x ) 0, Bx = d, x X, f(x ) = f. Before attempting to solve problem (2.5), there are some important questions to be answered, such as:
2 2.3. CONVEX CONSTRAINED OPTIMIZATION PROBLEMS 43 Is the problem infeasible, i.e., is C empty? Is f = +? 1. Is f =? If the answer is yes to any of the preceding questions, then it does not make sense to consider the problem in (2.5) any further. The problem is of interest only when f is finite. In this case, the particular instances when the problem has a solution are of interest in many applications. A feasibility problem is the problem of determining whether the constraint set C in Eq. (2.6) is empty or not. It can be posed as an optimization problem with the objective function f(x) = 0 for all x R n. In particular, a feasibility problem can be reduced to the following minimization problem: minimize 0 (2.7) subject to g(x) 0, Bx = d, x X. (2.8) In many applications, the feasibility problem can be a hard problem on its own. For example, the stability in linear time invariant systems often reduces to the feasibility problem where we want to determine whether there exist positive definite matrices P and Q such that A T P + P A = Q. Equivalently, the question is whether the set {(P, Q) S n ++ S n ++ A T P + P A = Q} is nonempty, where S n ++ denotes the set of n n positive definite matrices. From now on, we assume that the problem in Eq. (2.5) is feasible, and we focus on the issues of finiteness of the optimal value f and the existence of optimal solutions x. In particular, for problem (2.5), we use the following assumption. Assumption 1 The functions f and g i, i = 1,..., m are convex over R n. The set X is closed and convex. The set C = {x R n g(x) 0, Bx = d, x X} is nonempty. Under Assumption 1, the functions f and g i, i = 1,..., m are continuous over R n (see Theorem 10). In what follows,we denote the set of optimal solutions of problem (2.5) by X Existence of Solutions Here, we provide some results on the existence of solutions. Under Assumption 1, these results are consequences of Theorems 3 and 4 of Section This happens in general only when domf C =.
3 44 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION Theorem 16 Let Assumption 1 hold. In addition, let X R n be bounded. Then, the optimal set X of problem (2.5) is nonempty, compact, and convex. Proof. At first, we show that the constraint set C is compact. The set C is the intersection of the level sets of continuous functions g i and hyperplanes (for j = 1,..., p, each set {x R n b T j x = d j } is a hyperplane), which are all closed sets. Therefore, C is closed. Since C X and X is bounded (because it is compact), the set C is also bounded. Hence, by Lemma 8 of Section 1.2.2, the set C is compact. The function f is continuous (by convexity over R n ). Hence, by Weierstrass Theorem (Theorem 3), the optimal value f of problem (2.5) is finite and its optimal set X is nonempty. The set X is closed since it can be represented as the intersection of closed sets: X = C {x R n f(x) f }. Furthermore, X is bounded since X C and C is bounded. Hence, X is compact. We now show that X is convex. Note that C is convex as it is given as the intersection of convex sets. Furthermore, the level set {x R n f(x) f } is convex by convexity of f. Hence, X is the intersection of two convex sets and, thus, X is convex. As seen in the proof of Theorem 16, the set C is closed and convex under Assumption 1. Also, under this assumption, the set X is closed and convex but possibly empty. The boundedness of X is the key assumption ensuring nonemptiness and boundedness of X. The following theorem is based on Theorem 4. We provide it without a proof. (The proof can be constructed similar to that of Theorem 16. The only new detail is in part (i), where using the coercivity of f, we show that the level sets of f are bounded.) Theorem 17 Let Assumption 1 hold. Furthermore, let any of the following conditions be satisfied: (i) The function f is coercive over C. (ii) For some γ R, the set {x C f(x) γ} is nonempty and compact. (iii) The set C is compact. Then, the optimal set X of problem (2.5) is nonempty, compact, and convex. For a quadratic convex objective and a linear constraint set, the existence of solutions is equivalent to finiteness of the optimal value. Furthermore, the issue of existence of solutions can be resolved by checking a linear condition, as seen in the following theorem. Theorem 18 Consider the problem minimize f(x) = x T P x + c T x subject to Ax b, where P is an n n positive semidefinite matrix, c R n, A is an m n matrix, and b R m. The following statements are equivalent:
4 2.3. CONVEX CONSTRAINED OPTIMIZATION PROBLEMS 45 (1) The optimal value f is finite. (2) The optimal set X is nonempty. (3) If Ay 0 and P y = 0 for some y R n, then c T y 0. The proof of Theorem 18 requires the notion of recession directions of convex closed sets, which is beyond the scope of these notes. The interested reader can find more discussion on this in Bertsekas, Nedić and Ozdaglar [9] (see there Proposition 2.3.5), or in Auslender and Teboulle [2]. As an immediate consequence of Theorem 18, we can derive the conditions for existence of solutions of linear programming problems. Corollary 1 Consider a linear programming problem minimize f(x) = c T x subject to Ax b. The following conditions are equivalent for the LP problem: (1) The optimal value f is finite. (2) The optimal set X is nonempty. (3) If Ay 0 for some y R n, then c T y 0. A linear programming (LP) problem that has a solution, it always has a solution of a specific structure. This specific solution is due to the geometry of the polyhedral constraint set. We describe this specific solution for an LP problem in a standard form: minimize subject to c T x Ax = b x 0, (2.9) where A is an m n matrix and b R m. The feasible set for the preceding LP problem is the polyhedral set {x R n Ax = b, x 0}. Definition 5 We say that x is a basic feasible solution for the LP in Eq. (2.9), when x is feasible and there are n linearly independent constraints among the constraints that x satisfies as equalities. The preceding definition actually applies to an LP problem in any form and not necessarily in the standard form. Furthermore, a basic solution of an LP is a vertex (or extreme point) of the (polyhedral) constraint set of the given LP, which are out of the scope of these lecture notes. The interested readers may find more on this, for example, in the textbook on linear optimization by Bertsimas and Tsitsiklis [11].
5 46 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION Note that for a given polyhedral set, there can be only finitely many basic solutions. However, the number of such solutions may be very large. For example, the cube {x R n 0 x i 1, i = 1,..., n} is given by 2n inequalities, and it has 2 n basic solutions. We say that a vector x is a basic solution if it satisfies Definition 5 apart from being feasible. Specifically, x is a basic solution for (2.9) if there are n linearly independent constraints among the constraints that x satisfies as equalities. A basic solution x is degenerate if more than n constraints are satisfied as equalities at x (active at x). Otherwise, it is nondegenerate. Example 8 Consider the polyhedral set given by minimize x 1 + x 2 + x 3 2 subject to x 2 + 2x 3 2 x 1 1 x 3 1 x 1 0, x 2 0, x 3 0. The vector x = (1, 1, 0) is a nondegenerate basic feasible solution since there are exactly three linearly independent constraints that are active at x, specifically, x 1 + x 2 + x 3 2, x 1 1, x 3 0. The vector ˆx = (1, 0, 1) is a degenerate feasible solution since there are five constraints active at ˆx, namely x 1 + x 2 + x 3 2, x 2 + 2x 3 2, x 1 1, x 3 1, x 2 0. Out of these, for example, the last three are linearly independent. We are now ready to state a fundamental result for linear programming solutions. Theorem 19 Consider an LP problem. Assume that its constraint set has at least one basic feasible solution and that the LP has an optimal solution. Then, there exists an optimal solution which is also a basic feasible solution Optimality Conditions In this section, we deal with a differentiable convex function. We have the following. Theorem 20 Let f : R n R be a differentiable convex function, and let C R n be a nonempty closed convex set. Consider the problem minimize f(x) subject to x C. A vector x is optimal for this problem if and only if x C and f(x ) T (z x ) 0 for all z C.
6 2.3. CONVEX CONSTRAINED OPTIMIZATION PROBLEMS 47 Proof. For the sake of simplicity, we prove the result assuming that f is continuously differentiable. Let x be optimal. Suppose that for some ẑ C we have f(x ) T (ẑ x ) < 0. Since f is continuously differentiable, by the firstorder Taylor expansion [Theorem 6(a)], we have for all sufficiently small α > 0, f(x + α(ẑ x )) = f(x ) + α f(x ) T (ẑ x ) + o(α) < f(x ), with x C and ẑ C. By the convexity of C, we have x + α(ẑ x ) C. Thus, this vector is feasible and has a smaller objective value than the optimal point x, which is a contradiction. Hence, we must have f(x ) T (z x ) 0 for all z C. Suppose now that x C and By convexity of f [see Theorem 12], we have implying that This and Eq. (2.10) further imply that f(x ) T (z x ) 0 for all z C. (2.10) f(x ) + f(x ) T (z x ) f(z) for all z C, Since x C, it follows that x is optimal. f(x ) T (z x ) f(z) f(x ). 0 f(z) f(x ) for all z C. We next discuss several implications of Theorem 20, by considering some special choices for the set C. Let C be the entire space, i.e., C = R n. The condition f(x ) T (z x ) 0 for all z C reduces to In turn, this is equivalent to f(x ) T d 0 for all d R n. (2.11) f(x ) = 0. Thus, by Theorem 20, a vector x is a minimum of f over R n if and only if f(x ) = 0. Let the set C be affine, i.e., the problem of interest is minimize f(x) subject to Ax = b, (2.12) where A is an m n matrix and b R m. In this case, the condition of Theorem 20 reduces to f(x ) T y 0 for all y N A,
7 48 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION where N A is the null space of the matrix A. Thus, the gradient f(x ) is orthogonal to the null space N A. Since the range of A T is orthogonal to N A [see Eq. (1.2)], it follows that f(x ) belongs to the range of A T, implying that f(x ) + A T λ = 0 for some λ R m. Hence, by Theorem 20, a vector x solves problem (2.12) if and only if Ax = b and there exists λ R m such that f(x ) + A T λ = 0. The relation f(x ) + A T λ = 0 is known as primal optimality condition. It is related to Lagrangian duality, which is the focus of Section 2.5. Let C be the nonnegative orthant in R n, i.e., the problem of interest is For this problem, the condition of Theorem 20 is equivalent to minimize f(x) subject to x 0. (2.13) f(x ) T x = 0. Therefore, a vector x solves problem (2.13) if and only if x 0 and f(x ) T x = 0. The relation f(x ) T x = 0 is known as complementarity condition, and the terminology comes again from the Lagrangian duality theory. Let C be a simplex in R n, i.e., the problem of interest is minimize f(x) subject to x 0, n x i = a, (2.14) i=1 where a > 0 is a scalar. By Theorem 20, x is optimal if and only if n i=1 f(x ) x i (x i x i ) 0 for all x i 0 with n i=1 x i = a. Consider an index i with x i > 0. Let j i and consider a feasible vector x with x i = 0, x j = x j + x i and all the other coordinates the same as those of x. By using this vector in the preceding relation, we obtain ( ) f(x ) f(x ) x i 0 for all i such that x i > 0, x j x i or equivalently f(x ) x i f(x ) x j for all i such that x i > 0. (2.15) Hence, x is an optimal solution to problem (2.14) if and only if x satisfies relation (2.15). Let us illustrate the optimality conditions for a simplical constraint set on the problem of optimal routing in a communication network (see [5] and [17]).
8 2.3. CONVEX CONSTRAINED OPTIMIZATION PROBLEMS 49 Example 9 (Optimal Routing) Consider a directed graph modeling a data communication network. Let S be a set of origindestination pairs, i.e., each s S is an ordered pair (i s, j s ) of nodes i s and j s in the network, with i s being the origin and j s being the destination of s. Let y s be the traffic flow of s (data units/second) i.e., the arrival rate of traffic entering the network at the origin of s and exiting the network at the destination of s. The traffic flow of s is routed through different paths in the network. There is a cost associated with using the links L of the network, namely, the cost of sending a flow z ij on the link (i, j) L is f ij (z ij ), where f ij is convex and continuously differentiable. The problem is to decide on paths along which the flow y s should be routed, so as to minimize the total cost. To formalize the problem, we introduce the following notation:  P s is the set of all directed paths from the origin of s to the destination of s.  x s is the part of the flow y s routed through the path p with p P s. Let x denote a vector of pathflow variables, i.e., x = {x p p P s, s S}. Then, the routing problem can be casted as the following convex minimization: minimize f(x) = subject to (i,j) L f ij {p (i,j) p} x p p P s x p = y s for all s S x p 0 for all p P s and all s S. The cost on link (i, j) depends on the total flow through that link, i.e., the sum of all flows x p along paths p that contain the link (i, j). The problem is convex in variable x, with differentiable objective function and a constraint set given by a Cartesian product of simplices (one simplex per s). We now consider the optimality conditions for the routing problem. Note that f(x) x p = (i,j) p f ij(z ij ), with z ij being the total flow on the link (i, j). When f ij(z ij ) is viewed as the length of the link (i, j) evaluated at z ij, the partial derivative f(x) x p is the length of the path p. By the necessary and sufficient conditions for a simplex [cf. Eq. 2.14], for all s S, we have x p > 0 when f(x ) f(x ) for all p P s. x p x p This relation means that a set of pathflows is optimal if and only if the flow is positive only on the shortest paths (where link length is measured by the first derivative). It also means that at an optimum x, for an s S, all the paths p P s carrying a positive flow x p > 0 have the same length (i.e., the traffic y s is routed through the paths of equal length).
9 50 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION In the absence of convexity, the point x C satisfying the condition f(x ) T (z x ) 0 for all z C is referred to as a stationary point. Such a point may be a local or global minimum of f over C. A global minimum of f over C is any solution to the problem of minimizing f over C. A local minimum of f over C is a point x C for which there exists a ball B( x, r) such that there is no better point among the points that belong to the ball B( x, r) and the set C, i.e., a ball B( x, r) such that f(x) f( x) for all x C B( x, r). For convex problems (i.e., convex f and C), there is no distinction between local and global minima: every local minimum is also global in convex problems. This makes solving convex minimization problems easier than solving a more general nonconvex problems. Let us note that for a strictly convex function, the optimal solution to the problem of minimizing f over C is unique (of course, when a solution exists). We state this result in the following theorem, whose proof follows from the definition of strict convexity. Theorem 21 Let C R n be a nonempty closed convex set and let f be a strictly convex function over C. If the problem of minimizing f over C has a solution, then the solution is unique. Proof. To arrive at a contradiction, assume that the optimal set X has more than one point. Let x 1 and x 2 be two distinct solutions, i.e., f(x 1) = f(x 2) = f and x 1 x 2. Also, let α (0, 1). Since f is convex, the set X is also convex implying that αx 1 + (1 α)x 2 X. Hence, f(αx 1 + (1 α)x 2) = f. (2.16) At the same time, by strict convexity of f over C and the relation X C, we have that f is strictly convex over X, so that f(αx 1 + (1 α)x 2) < αf(x 1) + (1 α)f(x 2) = f, which contradicts relation (2.16). Therefore, the solution must be unique Projection Theorem One special consequence of Theorems 4 and 20 is the Projection Theorem. The theorem guarantees the existence and uniqueness of the projection of a vector on a closed convex set. This result has a wide range of applications. For a given nonempty set C R n and a vector ˆx, the projection problem is the problem of determining the point x C that is the closest to ˆx among all x C (with respect to the Euclidean distance). Formally, the problem is given by minimize x ˆx 2 subject to x C. (2.17) In general, such a problem may not have an optimal solution and the solution need not be unique (when it exists). However, when the set C is closed and convex set, the solution exists and it is unique, as seen in the following theorem.
10 2.3. CONVEX CONSTRAINED OPTIMIZATION PROBLEMS 51 Figure 2.9: The projection of a vector ˆx on the closed convex set C is the vector P C [ˆx] C that is the closest to ˆx among all x C, with respect to the Euclidean distance. Theorem 22 (Projection Theorem) Let C R n be a nonempty closed convex set and ˆx R n be a given arbitrary vector. (a) The projection problem in Eq. (2.17) has a unique solution. (b) A vector x C is the solution to the projection problem if and only if (x ˆx) T (x x ) 0 for all x C. Proof. (a) The function f(x) = x ˆx is coercive over R n, and therefore coercive over C (i.e., lim x, x C f(x) = ). The set C is closed, and therefore by Theorem 4, the optimal set X for projection problem (2.17) is nonempty. Furthermore, the Hessian of f is given by 2 f(x) = 2I, which is positively definite everywhere. Therefore, by Theorem 11(b), the function f is strictly convex and the optimal solution is unique [cf. Theorem 21]. (b) By the firstorder optimality condition of Theorem 20), we have x C is a solution to the projection problem if and only if Since f(x) = 2(x ˆx), the result follows. f(x ) T (x x ) 0 for all x C. The projection of a vector ˆx to a closed convex set C is illustrated in Figure 2.9. The unique solution x to the projection problem is referred to as the projection of ˆx on C, and it is denoted by P C [ˆx]. The projection P C [ˆx] has some special properties, as given in the following theorem. Theorem 23 Let C R n be a nonempty closed convex set. (a) The projection mapping P C : R n C is nonexpansive, i.e., P C [x] P C [y] x y for all x, y R n.
11 52 CHAPTER 2. FUNDAMENTAL CONCEPTS IN CONVEX OPTIMIZATION Figure 2.10: The projection mapping x P C [x] is nonexpansive, P C [x] P C [y] x y for all x, y. (b) The set distance function d : R n R given by is convex. dist(x, C) = P C [x] x Proof. (a) The relation evidently holds for any x and y with P C [x] = P C [y]. Consider now arbitrary x, y R n with P C [x] P C [y]. By Projection Theorem (b), we have (P C [x] x) T (z P C [x]) 0 for all z C, (2.18) (P C [y] y) T (z P C [y]) 0 for all z C. (2.19) Using z = P C [y] in Eq. (2.18) and z = P C [x] in Eq. (2.19), and by summing the resulting inequalities, we obtain, Consequently, (P C [y] y + x P C [x]) T (P C [x] P C [y]) 0. (x y) T (P C [x] P C [y]) P C [x] P C [y] 2. Since P C [x] P C [y], it follows that y x P C [x] P C [y]. (b) The distance function is equivalently given by dist(x, C) = min z C x z for all x Rn. The function h(x, z) = x z is convex in (x, z) over R n R n, and the set C is convex. Hence, by Theorem 13(d), the function dist(x, C) is convex.
Duality of linear conic problems
Duality of linear conic problems Alexander Shapiro and Arkadi Nemirovski Abstract It is well known that the optimal values of a linear programming problem and its dual are equal to each other if at least
More informationA NEW LOOK AT CONVEX ANALYSIS AND OPTIMIZATION
1 A NEW LOOK AT CONVEX ANALYSIS AND OPTIMIZATION Dimitri Bertsekas M.I.T. FEBRUARY 2003 2 OUTLINE Convexity issues in optimization Historical remarks Our treatment of the subject Three unifying lines of
More informationDate: April 12, 2001. Contents
2 Lagrange Multipliers Date: April 12, 2001 Contents 2.1. Introduction to Lagrange Multipliers......... p. 2 2.2. Enhanced Fritz John Optimality Conditions...... p. 12 2.3. Informative Lagrange Multipliers...........
More informationNumerisches Rechnen. (für Informatiker) M. Grepl J. Berger & J.T. Frings. Institut für Geometrie und Praktische Mathematik RWTH Aachen
(für Informatiker) M. Grepl J. Berger & J.T. Frings Institut für Geometrie und Praktische Mathematik RWTH Aachen Wintersemester 2010/11 Problem Statement Unconstrained Optimality Conditions Constrained
More information10. Proximal point method
L. Vandenberghe EE236C Spring 201314) 10. Proximal point method proximal point method augmented Lagrangian method MoreauYosida smoothing 101 Proximal point method a conceptual algorithm for minimizing
More informationFurther Study on Strong Lagrangian Duality Property for Invex Programs via Penalty Functions 1
Further Study on Strong Lagrangian Duality Property for Invex Programs via Penalty Functions 1 J. Zhang Institute of Applied Mathematics, Chongqing University of Posts and Telecommunications, Chongqing
More informationCost Minimization and the Cost Function
Cost Minimization and the Cost Function Juan Manuel Puerta October 5, 2009 So far we focused on profit maximization, we could look at a different problem, that is the cost minimization problem. This is
More informationLecture 3. Linear Programming. 3B1B Optimization Michaelmas 2015 A. Zisserman. Extreme solutions. Simplex method. Interior point method
Lecture 3 3B1B Optimization Michaelmas 2015 A. Zisserman Linear Programming Extreme solutions Simplex method Interior point method Integer programming and relaxation The Optimization Tree Linear Programming
More information3. Linear Programming and Polyhedral Combinatorics
Massachusetts Institute of Technology Handout 6 18.433: Combinatorial Optimization February 20th, 2009 Michel X. Goemans 3. Linear Programming and Polyhedral Combinatorics Summary of what was seen in the
More informationProximal mapping via network optimization
L. Vandenberghe EE236C (Spring 234) Proximal mapping via network optimization minimum cut and maximum flow problems parametric minimum cut problem application to proximal mapping Introduction this lecture:
More information24. The Branch and Bound Method
24. The Branch and Bound Method It has serious practical consequences if it is known that a combinatorial problem is NPcomplete. Then one can conclude according to the present state of science that no
More informationApplied Algorithm Design Lecture 5
Applied Algorithm Design Lecture 5 Pietro Michiardi Eurecom Pietro Michiardi (Eurecom) Applied Algorithm Design Lecture 5 1 / 86 Approximation Algorithms Pietro Michiardi (Eurecom) Applied Algorithm Design
More informationAdaptive Online Gradient Descent
Adaptive Online Gradient Descent Peter L Bartlett Division of Computer Science Department of Statistics UC Berkeley Berkeley, CA 94709 bartlett@csberkeleyedu Elad Hazan IBM Almaden Research Center 650
More information(Basic definitions and properties; Separation theorems; Characterizations) 1.1 Definition, examples, inner description, algebraic properties
Lecture 1 Convex Sets (Basic definitions and properties; Separation theorems; Characterizations) 1.1 Definition, examples, inner description, algebraic properties 1.1.1 A convex set In the school geometry
More informationWalrasian Demand. u(x) where B(p, w) = {x R n + : p x w}.
Walrasian Demand Econ 2100 Fall 2015 Lecture 5, September 16 Outline 1 Walrasian Demand 2 Properties of Walrasian Demand 3 An Optimization Recipe 4 First and Second Order Conditions Definition Walrasian
More informationLecture 5 Principal Minors and the Hessian
Lecture 5 Principal Minors and the Hessian Eivind Eriksen BI Norwegian School of Management Department of Economics October 01, 2010 Eivind Eriksen (BI Dept of Economics) Lecture 5 Principal Minors and
More informationNo: 10 04. Bilkent University. Monotonic Extension. Farhad Husseinov. Discussion Papers. Department of Economics
No: 10 04 Bilkent University Monotonic Extension Farhad Husseinov Discussion Papers Department of Economics The Discussion Papers of the Department of Economics are intended to make the initial results
More informationConvex analysis and profit/cost/support functions
CALIFORNIA INSTITUTE OF TECHNOLOGY Division of the Humanities and Social Sciences Convex analysis and profit/cost/support functions KC Border October 2004 Revised January 2009 Let A be a subset of R m
More information4.6 Linear Programming duality
4.6 Linear Programming duality To any minimization (maximization) LP we can associate a closely related maximization (minimization) LP. Different spaces and objective functions but in general same optimal
More information1 Introduction. Linear Programming. Questions. A general optimization problem is of the form: choose x to. max f(x) subject to x S. where.
Introduction Linear Programming Neil Laws TT 00 A general optimization problem is of the form: choose x to maximise f(x) subject to x S where x = (x,..., x n ) T, f : R n R is the objective function, S
More informationt := maxγ ν subject to ν {0,1,2,...} and f(x c +γ ν d) f(x c )+cγ ν f (x c ;d).
1. Line Search Methods Let f : R n R be given and suppose that x c is our current best estimate of a solution to P min x R nf(x). A standard method for improving the estimate x c is to choose a direction
More informationInner Product Spaces
Math 571 Inner Product Spaces 1. Preliminaries An inner product space is a vector space V along with a function, called an inner product which associates each pair of vectors u, v with a scalar u, v, and
More informationOptimization in R n Introduction
Optimization in R n Introduction Rudi Pendavingh Eindhoven Technical University Optimization in R n, lecture Rudi Pendavingh (TUE) Optimization in R n Introduction ORN / 4 Some optimization problems designing
More informationIncreasing for all. Convex for all. ( ) Increasing for all (remember that the log function is only defined for ). ( ) Concave for all.
1. Differentiation The first derivative of a function measures by how much changes in reaction to an infinitesimal shift in its argument. The largest the derivative (in absolute value), the faster is evolving.
More informationDuality in General Programs. Ryan Tibshirani Convex Optimization 10725/36725
Duality in General Programs Ryan Tibshirani Convex Optimization 10725/36725 1 Last time: duality in linear programs Given c R n, A R m n, b R m, G R r n, h R r : min x R n c T x max u R m, v R r b T
More information1 Norms and Vector Spaces
008.10.07.01 1 Norms and Vector Spaces Suppose we have a complex vector space V. A norm is a function f : V R which satisfies (i) f(x) 0 for all x V (ii) f(x + y) f(x) + f(y) for all x,y V (iii) f(λx)
More informationOn Minimal Valid Inequalities for Mixed Integer Conic Programs
On Minimal Valid Inequalities for Mixed Integer Conic Programs Fatma Kılınç Karzan June 27, 2013 Abstract We study mixed integer conic sets involving a general regular (closed, convex, full dimensional,
More informationMetric Spaces. Chapter 1
Chapter 1 Metric Spaces Many of the arguments you have seen in several variable calculus are almost identical to the corresponding arguments in one variable calculus, especially arguments concerning convergence
More informationNonlinear Programming Methods.S2 Quadratic Programming
Nonlinear Programming Methods.S2 Quadratic Programming Operations Research Models and Methods Paul A. Jensen and Jonathan F. Bard A linearly constrained optimization problem with a quadratic objective
More informationSome representability and duality results for convex mixedinteger programs.
Some representability and duality results for convex mixedinteger programs. Santanu S. Dey Joint work with Diego Morán and Juan Pablo Vielma December 17, 2012. Introduction About Motivation Mixed integer
More informationTOPIC 4: DERIVATIVES
TOPIC 4: DERIVATIVES 1. The derivative of a function. Differentiation rules 1.1. The slope of a curve. The slope of a curve at a point P is a measure of the steepness of the curve. If Q is a point on the
More informationNonlinear Optimization: Algorithms 3: Interiorpoint methods
Nonlinear Optimization: Algorithms 3: Interiorpoint methods INSEAD, Spring 2006 JeanPhilippe Vert Ecole des Mines de Paris JeanPhilippe.Vert@mines.org Nonlinear optimization c 2006 JeanPhilippe Vert,
More informationPractical Guide to the Simplex Method of Linear Programming
Practical Guide to the Simplex Method of Linear Programming Marcel Oliver Revised: April, 0 The basic steps of the simplex algorithm Step : Write the linear programming problem in standard form Linear
More informationMathematical Methods of Engineering Analysis
Mathematical Methods of Engineering Analysis Erhan Çinlar Robert J. Vanderbei February 2, 2000 Contents Sets and Functions 1 1 Sets................................... 1 Subsets.............................
More information17.3.1 Follow the Perturbed Leader
CS787: Advanced Algorithms Topic: Online Learning Presenters: David He, Chris Hopman 17.3.1 Follow the Perturbed Leader 17.3.1.1 Prediction Problem Recall the prediction problem that we discussed in class.
More informationVector and Matrix Norms
Chapter 1 Vector and Matrix Norms 11 Vector Spaces Let F be a field (such as the real numbers, R, or complex numbers, C) with elements called scalars A Vector Space, V, over the field F is a nonempty
More informationError Bound for Classes of Polynomial Systems and its Applications: A Variational Analysis Approach
Outline Error Bound for Classes of Polynomial Systems and its Applications: A Variational Analysis Approach The University of New South Wales SPOM 2013 Joint work with V. Jeyakumar, B.S. Mordukhovich and
More informationMetric Spaces. Chapter 7. 7.1. Metrics
Chapter 7 Metric Spaces A metric space is a set X that has a notion of the distance d(x, y) between every pair of points x, y X. The purpose of this chapter is to introduce metric spaces and give some
More informationα = u v. In other words, Orthogonal Projection
Orthogonal Projection Given any nonzero vector v, it is possible to decompose an arbitrary vector u into a component that points in the direction of v and one that points in a direction orthogonal to v
More informationRecovery of primal solutions from dual subgradient methods for mixed binary linear programming; a branchandbound approach
MASTER S THESIS Recovery of primal solutions from dual subgradient methods for mixed binary linear programming; a branchandbound approach PAULINE ALDENVIK MIRJAM SCHIERSCHER Department of Mathematical
More informationMA651 Topology. Lecture 6. Separation Axioms.
MA651 Topology. Lecture 6. Separation Axioms. This text is based on the following books: Fundamental concepts of topology by Peter O Neil Elements of Mathematics: General Topology by Nicolas Bourbaki Counterexamples
More informationChapter 11. 11.1 Load Balancing. Approximation Algorithms. Load Balancing. Load Balancing on 2 Machines. Load Balancing: Greedy Scheduling
Approximation Algorithms Chapter Approximation Algorithms Q. Suppose I need to solve an NPhard problem. What should I do? A. Theory says you're unlikely to find a polytime algorithm. Must sacrifice one
More informationSeparation Properties for Locally Convex Cones
Journal of Convex Analysis Volume 9 (2002), No. 1, 301 307 Separation Properties for Locally Convex Cones Walter Roth Department of Mathematics, Universiti Brunei Darussalam, Gadong BE1410, Brunei Darussalam
More informationInternational Doctoral School Algorithmic Decision Theory: MCDA and MOO
International Doctoral School Algorithmic Decision Theory: MCDA and MOO Lecture 2: Multiobjective Linear Programming Department of Engineering Science, The University of Auckland, New Zealand Laboratoire
More informationModern Optimization Methods for Big Data Problems MATH11146 The University of Edinburgh
Modern Optimization Methods for Big Data Problems MATH11146 The University of Edinburgh Peter Richtárik Week 3 Randomized Coordinate Descent With Arbitrary Sampling January 27, 2016 1 / 30 The Problem
More informationSolutions Of Some NonLinear Programming Problems BIJAN KUMAR PATEL. Master of Science in Mathematics. Prof. ANIL KUMAR
Solutions Of Some NonLinear Programming Problems A PROJECT REPORT submitted by BIJAN KUMAR PATEL for the partial fulfilment for the award of the degree of Master of Science in Mathematics under the supervision
More informationInner products on R n, and more
Inner products on R n, and more Peyam Ryan Tabrizian Friday, April 12th, 2013 1 Introduction You might be wondering: Are there inner products on R n that are not the usual dot product x y = x 1 y 1 + +
More information! Solve problem to optimality. ! Solve problem in polytime. ! Solve arbitrary instances of the problem. !approximation algorithm.
Approximation Algorithms Chapter Approximation Algorithms Q Suppose I need to solve an NPhard problem What should I do? A Theory says you're unlikely to find a polytime algorithm Must sacrifice one of
More information! Solve problem to optimality. ! Solve problem in polytime. ! Solve arbitrary instances of the problem. #approximation algorithm.
Approximation Algorithms 11 Approximation Algorithms Q Suppose I need to solve an NPhard problem What should I do? A Theory says you're unlikely to find a polytime algorithm Must sacrifice one of three
More informationNPhardness of Deciding Convexity of Quartic Polynomials and Related Problems
NPhardness of Deciding Convexity of Quartic Polynomials and Related Problems Amir Ali Ahmadi, Alex Olshevsky, Pablo A. Parrilo, and John N. Tsitsiklis Abstract We show that unless P=NP, there exists no
More information3. INNER PRODUCT SPACES
. INNER PRODUCT SPACES.. Definition So far we have studied abstract vector spaces. These are a generalisation of the geometric spaces R and R. But these have more structure than just that of a vector space.
More information4. Expanding dynamical systems
4.1. Metric definition. 4. Expanding dynamical systems Definition 4.1. Let X be a compact metric space. A map f : X X is said to be expanding if there exist ɛ > 0 and L > 1 such that d(f(x), f(y)) Ld(x,
More informationNetwork Traffic Modelling
University of York Dissertation submitted for the MSc in Mathematics with Modern Applications, Department of Mathematics, University of York, UK. August 009 Network Traffic Modelling Author: David Slade
More informationSummer course on Convex Optimization. Fifth Lecture InteriorPoint Methods (1) Michel Baes, K.U.Leuven Bharath Rangarajan, U.
Summer course on Convex Optimization Fifth Lecture InteriorPoint Methods (1) Michel Baes, K.U.Leuven Bharath Rangarajan, U.Minnesota InteriorPoint Methods: the rebirth of an old idea Suppose that f is
More informationGenOpt (R) Generic Optimization Program User Manual Version 3.0.0β1
(R) User Manual Environmental Energy Technologies Division Berkeley, CA 94720 http://simulationresearch.lbl.gov Michael Wetter MWetter@lbl.gov February 20, 2009 Notice: This work was supported by the U.S.
More informationLECTURE 5: DUALITY AND SENSITIVITY ANALYSIS. 1. Dual linear program 2. Duality theory 3. Sensitivity analysis 4. Dual simplex method
LECTURE 5: DUALITY AND SENSITIVITY ANALYSIS 1. Dual linear program 2. Duality theory 3. Sensitivity analysis 4. Dual simplex method Introduction to dual linear program Given a constraint matrix A, right
More informationSystems of Linear Equations
Systems of Linear Equations Beifang Chen Systems of linear equations Linear systems A linear equation in variables x, x,, x n is an equation of the form a x + a x + + a n x n = b, where a, a,, a n and
More informationLeastSquares Intersection of Lines
LeastSquares Intersection of Lines Johannes Traa  UIUC 2013 This writeup derives the leastsquares solution for the intersection of lines. In the general case, a set of lines will not intersect at a
More informationSECOND DERIVATIVE TEST FOR CONSTRAINED EXTREMA
SECOND DERIVATIVE TEST FOR CONSTRAINED EXTREMA This handout presents the second derivative test for a local extrema of a Lagrange multiplier problem. The Section 1 presents a geometric motivation for the
More informationChapter 4. Duality. 4.1 A Graphical Example
Chapter 4 Duality Given any linear program, there is another related linear program called the dual. In this chapter, we will develop an understanding of the dual linear program. This understanding translates
More informationDATA ANALYSIS II. Matrix Algorithms
DATA ANALYSIS II Matrix Algorithms Similarity Matrix Given a dataset D = {x i }, i=1,..,n consisting of n points in R d, let A denote the n n symmetric similarity matrix between the points, given as where
More informationCHAPTER 9. Integer Programming
CHAPTER 9 Integer Programming An integer linear program (ILP) is, by definition, a linear program with the additional constraint that all variables take integer values: (9.1) max c T x s t Ax b and x integral
More information1 if 1 x 0 1 if 0 x 1
Chapter 3 Continuity In this chapter we begin by defining the fundamental notion of continuity for real valued functions of a single real variable. When trying to decide whether a given function is or
More informationBANACH AND HILBERT SPACE REVIEW
BANACH AND HILBET SPACE EVIEW CHISTOPHE HEIL These notes will briefly review some basic concepts related to the theory of Banach and Hilbert spaces. We are not trying to give a complete development, but
More informationConvex Rationing Solutions (Incomplete Version, Do not distribute)
Convex Rationing Solutions (Incomplete Version, Do not distribute) Ruben Juarez rubenj@hawaii.edu January 2013 Abstract This paper introduces a notion of convexity on the rationing problem and characterizes
More informationApproximation Algorithms
Approximation Algorithms or: How I Learned to Stop Worrying and Deal with NPCompleteness Ong Jit Sheng, Jonathan (A0073924B) March, 2012 Overview Key Results (I) General techniques: Greedy algorithms
More informationTHE FUNDAMENTAL THEOREM OF ALGEBRA VIA PROPER MAPS
THE FUNDAMENTAL THEOREM OF ALGEBRA VIA PROPER MAPS KEITH CONRAD 1. Introduction The Fundamental Theorem of Algebra says every nonconstant polynomial with complex coefficients can be factored into linear
More informationLinear Programming I
Linear Programming I November 30, 2003 1 Introduction In the VCR/guns/nuclear bombs/napkins/star wars/professors/butter/mice problem, the benevolent dictator, Bigus Piguinus, of south Antarctica penguins
More informationStationary random graphs on Z with prescribed iid degrees and finite mean connections
Stationary random graphs on Z with prescribed iid degrees and finite mean connections Maria Deijfen Johan Jonasson February 2006 Abstract Let F be a probability distribution with support on the nonnegative
More informationSeveral Views of Support Vector Machines
Several Views of Support Vector Machines Ryan M. Rifkin Honda Research Institute USA, Inc. Human Intention Understanding Group 2007 Tikhonov Regularization We are considering algorithms of the form min
More informationLoad Balancing and Switch Scheduling
EE384Y Project Final Report Load Balancing and Switch Scheduling Xiangheng Liu Department of Electrical Engineering Stanford University, Stanford CA 94305 Email: liuxh@systems.stanford.edu Abstract Load
More informationconstraint. Let us penalize ourselves for making the constraint too big. We end up with a
Chapter 4 Constrained Optimization 4.1 Equality Constraints (Lagrangians) Suppose we have a problem: Maximize 5, (x 1, 2) 2, 2(x 2, 1) 2 subject to x 1 +4x 2 =3 If we ignore the constraint, we get the
More informationINDISTINGUISHABILITY OF ABSOLUTELY CONTINUOUS AND SINGULAR DISTRIBUTIONS
INDISTINGUISHABILITY OF ABSOLUTELY CONTINUOUS AND SINGULAR DISTRIBUTIONS STEVEN P. LALLEY AND ANDREW NOBEL Abstract. It is shown that there are no consistent decision rules for the hypothesis testing problem
More informationLinear Programming Notes V Problem Transformations
Linear Programming Notes V Problem Transformations 1 Introduction Any linear programming problem can be rewritten in either of two standard forms. In the first form, the objective is to maximize, the material
More informationWhat is Linear Programming?
Chapter 1 What is Linear Programming? An optimization problem usually has three essential ingredients: a variable vector x consisting of a set of unknowns to be determined, an objective function of x to
More informationThe Equivalence of Linear Programs and ZeroSum Games
The Equivalence of Linear Programs and ZeroSum Games Ilan Adler, IEOR Dep, UC Berkeley adler@ieor.berkeley.edu Abstract In 1951, Dantzig showed the equivalence of linear programming problems and twoperson
More informationORIENTATIONS. Contents
ORIENTATIONS Contents 1. Generators for H n R n, R n p 1 1. Generators for H n R n, R n p We ended last time by constructing explicit generators for H n D n, S n 1 by using an explicit nsimplex which
More informationThe Goldberg Rao Algorithm for the Maximum Flow Problem
The Goldberg Rao Algorithm for the Maximum Flow Problem COS 528 class notes October 18, 2006 Scribe: Dávid Papp Main idea: use of the blocking flow paradigm to achieve essentially O(min{m 2/3, n 1/2 }
More informationMathematical finance and linear programming (optimization)
Mathematical finance and linear programming (optimization) Geir Dahl September 15, 2009 1 Introduction The purpose of this short note is to explain how linear programming (LP) (=linear optimization) may
More informationFairness in Routing and Load Balancing
Fairness in Routing and Load Balancing Jon Kleinberg Yuval Rabani Éva Tardos Abstract We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteria
More informationLecture 7: Finding Lyapunov Functions 1
Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.243j (Fall 2003): DYNAMICS OF NONLINEAR SYSTEMS by A. Megretski Lecture 7: Finding Lyapunov Functions 1
More informationSome Problems of SecondOrder Rational Difference Equations with Quadratic Terms
International Journal of Difference Equations ISSN 09736069, Volume 9, Number 1, pp. 11 21 (2014) http://campus.mst.edu/ijde Some Problems of SecondOrder Rational Difference Equations with Quadratic
More information. P. 4.3 Basic feasible solutions and vertices of polyhedra. x 1. x 2
4. Basic feasible solutions and vertices of polyhedra Due to the fundamental theorem of Linear Programming, to solve any LP it suffices to consider the vertices (finitely many) of the polyhedron P of the
More informationminimal polyonomial Example
Minimal Polynomials Definition Let α be an element in GF(p e ). We call the monic polynomial of smallest degree which has coefficients in GF(p) and α as a root, the minimal polyonomial of α. Example: We
More informationThe Heat Equation. Lectures INF2320 p. 1/88
The Heat Equation Lectures INF232 p. 1/88 Lectures INF232 p. 2/88 The Heat Equation We study the heat equation: u t = u xx for x (,1), t >, (1) u(,t) = u(1,t) = for t >, (2) u(x,) = f(x) for x (,1), (3)
More informationNotes on metric spaces
Notes on metric spaces 1 Introduction The purpose of these notes is to quickly review some of the basic concepts from Real Analysis, Metric Spaces and some related results that will be used in this course.
More informationLinear Algebra I. Ronald van Luijk, 2012
Linear Algebra I Ronald van Luijk, 2012 With many parts from Linear Algebra I by Michael Stoll, 2007 Contents 1. Vector spaces 3 1.1. Examples 3 1.2. Fields 4 1.3. The field of complex numbers. 6 1.4.
More informationLecture 4: BK inequality 27th August and 6th September, 2007
CSL866: Percolation and Random Graphs IIT Delhi Amitabha Bagchi Scribe: Arindam Pal Lecture 4: BK inequality 27th August and 6th September, 2007 4. Preliminaries The FKG inequality allows us to lower bound
More information(Quasi)Newton methods
(Quasi)Newton methods 1 Introduction 1.1 Newton method Newton method is a method to find the zeros of a differentiable nonlinear function g, x such that g(x) = 0, where g : R n R n. Given a starting
More information9 More on differentiation
Tel Aviv University, 2013 Measure and category 75 9 More on differentiation 9a Finite Taylor expansion............... 75 9b Continuous and nowhere differentiable..... 78 9c Differentiable and nowhere monotone......
More information17. Inner product spaces Definition 17.1. Let V be a real vector space. An inner product on V is a function
17. Inner product spaces Definition 17.1. Let V be a real vector space. An inner product on V is a function, : V V R, which is symmetric, that is u, v = v, u. bilinear, that is linear (in both factors):
More information26 Linear Programming
The greatest flood has the soonest ebb; the sorest tempest the most sudden calm; the hottest love the coldest end; and from the deepest desire oftentimes ensues the deadliest hate. Th extremes of glory
More informationLecture 2: August 29. Linear Programming (part I)
10725: Convex Optimization Fall 2013 Lecture 2: August 29 Lecturer: Barnabás Póczos Scribes: Samrachana Adhikari, Mattia Ciollaro, Fabrizio Lecci Note: LaTeX template courtesy of UC Berkeley EECS dept.
More informationPractice with Proofs
Practice with Proofs October 6, 2014 Recall the following Definition 0.1. A function f is increasing if for every x, y in the domain of f, x < y = f(x) < f(y) 1. Prove that h(x) = x 3 is increasing, using
More informationNotes V General Equilibrium: Positive Theory. 1 Walrasian Equilibrium and Excess Demand
Notes V General Equilibrium: Positive Theory In this lecture we go on considering a general equilibrium model of a private ownership economy. In contrast to the Notes IV, we focus on positive issues such
More informationGROUPS ACTING ON A SET
GROUPS ACTING ON A SET MATH 435 SPRING 2012 NOTES FROM FEBRUARY 27TH, 2012 1. Left group actions Definition 1.1. Suppose that G is a group and S is a set. A left (group) action of G on S is a rule for
More informationContinued Fractions and the Euclidean Algorithm
Continued Fractions and the Euclidean Algorithm Lecture notes prepared for MATH 326, Spring 997 Department of Mathematics and Statistics University at Albany William F Hammond Table of Contents Introduction
More informationLinear Programming. Widget Factory Example. Linear Programming: Standard Form. Widget Factory Example: Continued.
Linear Programming Widget Factory Example Learning Goals. Introduce Linear Programming Problems. Widget Example, Graphical Solution. Basic Theory:, Vertices, Existence of Solutions. Equivalent formulations.
More informationThe Steepest Descent Algorithm for Unconstrained Optimization and a Bisection Linesearch Method
The Steepest Descent Algorithm for Unconstrained Optimization and a Bisection Linesearch Method Robert M. Freund February, 004 004 Massachusetts Institute of Technology. 1 1 The Algorithm The problem
More informationSection 1.1. Introduction to R n
The Calculus of Functions of Several Variables Section. Introduction to R n Calculus is the study of functional relationships and how related quantities change with each other. In your first exposure to
More information