Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Exercises

Standard forms

  1. Consider the two problems

min_x : c^Tx ~:~ x ge 0, ;; Ax = b

and

min_x : (c^Tx)^2 ~:~ x ge 0, ;; Ax = b.

    1. Show by a counterexample that these problems do not necessarily share the same set of optimal points.

    2. Formulate the second problem as a linear program in standard form.

    3. Show that if cge 0 (that is, every component of c is non-negative), then the problems are equivalent.

  2. Consider a least-squares problem with linear inequality constraints

min_x : |Ax-b|_2^2 ~:~ Cx le d,

where A,C are given matrices (of row size equal to n, the number of variables) and b,d are given vectors.

    1. Write the problem as a QP in standard form.

    2. Is the converse true? In other words, can we always transform a QP in standard form, into a problem with the form above? Discuss.

  2. For given n-vectors a_1,ldots,a_m, consider the problem

min_x : sum_{i=1}^m left( |a_i^Tx| - 1right)^2

Proof or counter-example: the above problem is (a) an LP; (b) a QP; (c) An ordinary least-squares problem.

Applications

  1. Computing the convex hull. In this exercise, you will devise an algorithm that, given a set of distinct n points x_i in mathbf{R}^2, i=1,ldots,n, plots the convex hull {cal C} of the points. This well-studied problem arises a lot in computational geometry, see here.

    1. Find a point x_0 in the interior of the convex hull. Hint: think about the average of the points.

    2. Show how to formulate the following problem as a linear optimization problem: given a direction v, find the largest t such that x_0+tv in {cal C}.

    3. Using CVX, plot the convex hull of the points in the matrix

X = left[ begin {array}{cccccc} 15&6&8&5&6&3noalign{medskip}8&8&5&6&2&4end {array} right] .

Hint: use the previous part with many directions v.

    1. Comment on the accuracy needed when you scan the possible angular directions.

    2. Can you come up with a more efficient method to solve this problem? Discuss.

  2. A control problem. We consider a dynamical system with one input and one output, and described by a linear, time-invariant relationship:

y(t) = h_0 u(t) + h_1 u(t-1) + ldots + h_m u(t-m), ;; t=0,1,2,ldots,

where m >0 is the order of the system, and h=(h_0,ldots,h_m) is called the impulse response. We consider an input design problem, where we seek to find a sequence of inputs which tracks a given desired output signal y_{rm des}(t) over a given time horizon {0,ldots,N},with N given. Specifically, we seek inputs u(0),ldots,u(N) should be such that the following three conditions hold. (i) The peak deviation between y(t) and y_{rm des}(t)

max_{0 le t le N} | y(t) - y_{rm des}(t) |

is minimized; (ii) the inputs should be zero for t>M, where M <N is given; (iii) the inputs should satisfy amplitude and slew rate constraints:

|u(t)| le U, ;; |u(t+1)-u(t)| le S,

where U>0, S>0 are given. Show that the problem can be formulated as a linear program. Write a CVX code that plots the results given problem data.

  1. Advertising problem. A company wants to promote its newly developed product by launching an advertising campaign. There are four advertising options to choose from: TV Spot, Newspaper, Radio (prime time), and Radio (afternoon); these options are labelled T, N, P, A, respectively. The table below provides, for each type of advertising, the audience reached, the cost and maximum number of ads per week. The company has a budget of $8000 per week and seeks to maximize audience reached. However, the company also wants 5 or more radio spots per week and cannot spend more than $1800 on radio per week. Let T, N, P, A be the decision variables corresponding to the numbers of ads chosen weekly by the company. (You can ignore the fact that these variables should be integers.) Formulate this as a linear programming problem, making sure to incorporate all the constraints in the formulation.

Advertising options TV Spot (T) Newspaper (N) Radio (P) (prime time) Radio (A) (afternoon)
Audience Reached (per ad) 5000 8500 2400 2800
Cost (per ad) $ 800 $ 925 $ 290 $ 380
Max Ads (per week) 12 5 25 20