This assignment consists of eight problems that require you to submit a written response and a coding component.
(1) When a problem asks you to formulate you need to provide your mathematical formulation of the LP with a clear justification of variables, constraints and objective function. You should submit your written response as a PDF to GradeScope and match the page number with the questions that you answered. You can find detailed instructions on how to scan and submit your assignments on Canvas. If you fail to match the page to the corresponding question, the marker will not be able to view your response, and thus you will be awarded a 0 mark for the question.
(2) When a problem involves computation you must give the Python source code that produces the result, the final numerical results and an interpretation of your numerical results. The Python code and numerical results go into a Jupyter Notebook file QBUS2310-2022S2-Assignment1-code.ipynb. You should download the file from Canvas and enter your code in the space provided. You should submit your code as a Jupyter notebook file via Canvas. In addition, the final numerical results and your interpretation of the results should appear in the PDF of your written response, described in (1).
Note: only problems 1 and 2 do not involve computation.
The assignment is due by Monday, the 5th of September, 5pm. Late assignments will not be accepted unless a special consideration was granted.
The problems have unequal weight. Some are easy. Others, not so much.
1. (10 points) Formulate the following problem as LP: Given A ∈ Rm×n, b ∈ Rm,mminimize Σ max{0, aT x + bi}. The variable is x ∈ Rn. i=1
2. (10 points) In linear classification problems we are given two sets of points in Rn, x1, . . . , xN and y1, . . . , yM , and wish to find an affine function f : Rn R that is positive on the first set and negative on the second. When the two sets of points cannot be linearly separated, we might
seek an affine function that approximately classifies the points, for example, one that minimizes the number of points misclassified. Unfortunately, this is in general a difficult combinatorial optimization problem. One heuristic for approximate linear separation is based on support vector classifiers, which we discussed in class (see Topic 4: Piecewise-linear optimization).
We start with the basic feasibility problem:
aT xi + b ≥ 1, i = 1, . . . , N, aT yi + b ≤ −1, i = 1, . . . , M.
We then relax the constraints by introducing nonnegative variables u1, . . . , uN and v1, . . . , vM , and forming the inequalities
aT xi + b ≥ 1 − ui, i = 1, . . . , N, aT yi + b ≤ −(1 − vi), i = 1, . . . , M. (1)
When u = v = 0, we recover the original constraints. By making u and v large enough, these inequalities can always be made feasible. We can think of ui as a measure of how much the constraint aT xi b 1 is violated, and similarly for vi. Our goal is to find a, b, and sparse nonnegative u and v that satisfy the inequalities (1). Formulate this problem as an LP.
3. We consider an illumination system of m lamps, at positions l1, . . . , lm R2, illuminating n flat patches.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
