Unit5

Straight Lines and Planes

• Equation of a straight line in intercept form: $\frac{x}{a} + \frac{y}{b} = 1$ (1). This form highlights where the line intersects the x-axis at point a and the y-axis at point b.

• Equation of a plane in intercept form: $\frac{x}{a} + \frac{y}{b} + \frac{z}{c} = 1$ (2). This form shows the intersections with the x, y, and z axes at points a, b, and c respectively.

• If $c \rightarrow \infty$, the plane becomes: $\frac{x}{a} + \frac{y}{b} = 1$ for all $z$ (3). This represents a plane or a straight line parallel to the z-axis because the plane never intersects the z-axis.

Family of Curves

• Consider a family of curves: $y = mx + c$, where $m$ is negative and fixed, and $c$ varies. This generates parallel lines with the same slope but different y-intercepts.

• Example 1: $y = -2x + 3$ (4)

• Example 2: $y = -2x$ (5)

• Example 3: $y = -2x - 3$ (6)

• Identify regions between lines using inequalities; for instance, the region above the line $y = -2x + 3$ can be described by y > -2x + 3.

Linear Inequalities

• Algebra focuses on equations (e.g., determinants, eigenvalues), providing exact solutions.

• Analysis often deals with inequalities, which describe ranges and bounds rather than specific values.

• Linear programming is centered on inequalities and decision-making, optimizing outcomes within given constraints.

• Three approaches:

  • Intuitive geometry: Visualizing inequalities and feasible regions.

  • Computational simplex method: An algorithmic approach to solving linear programming problems.

  • Algebraic duality: Transforming and solving related optimization problems to gain insights or find solutions.

Geometric Meaning

• An inequality divides n-dimensional space into two halfspaces: one where the inequality holds and one where it doesn't. This division is fundamental in understanding feasible regions.

• Example: $x + 2y \geq 4$ (7)

• The boundary between the halfspaces is the line $x + 2y = 4$. Points on this line satisfy the equality condition.

Strict vs. Tight Inequalities

• Strict inequalities: Exclude equality (e.g., <, >). Example: x < 5. The solution set does not include $x = 5$.

• Tight inequalities: Allow equality (e.g., $\leq, \geq$). Example: $x^2 + y^2 \geq 2xy$ (equality holds when $x = y$). This inequality is always true, and the equality condition helps identify specific cases.

Halfspaces

• Equations define lines and planes, while inequalities define halfspaces. Halfspaces represent all points on one side of a plane.

• In n-dimensional space, a plane has dimension $n-1$. For instance, in 3D space, a plane is 2-dimensional.

Non-Negativity Constraint

• Fundamental constraint in linear programming: variables are nonnegative, reflecting real-world scenarios where quantities cannot be negative.

• $x \geq 0$ (8)

• $y \geq 0$ (9)

• These inequalities produce additional halfspaces, restricting solutions to the first quadrant or higher-dimensional equivalent.

Feasible Set and Cost Function

• Imposing multiple inequalities creates a feasible set (intersection of halfspaces). The feasible set contains all points that satisfy all constraints simultaneously.

• A feasible set consists of solutions to a set of linear inequalities, such as $Ax \geq b$. Non-negativity constraints, $x \geq 0$, add more halfspaces, further refining the feasible set.

• More constraints reduce the size of the feasible set, potentially leading to a single point, an empty set, or a bounded region.

Examples of Feasible Sets

• Example 1: Feasible set defined by $x + 2y \leq 4, x \geq 0, y \geq 0$ forms a small triangle in the first quadrant.

• Example 2: $x + 2y \leq 4$ and $x + 2y \geq 4$ shrinks the set to a straight line, specifically the line $x + 2y = 4$.

• Example 3: $x + 2y \leq -2$ results in an empty set because $x$ and $y$ are non-negative, so their sum cannot be less than -2.

Aspects of Linear Inequalities

1. Feasible set: The region defined by all constraints.

2. Feasible point: A point within the feasible set. An optimal feasible point maximizes or minimizes a cost function.

Cost Function

• Cost function: e.g., $2x + 3y$, which represents a family of parallel lines. The cost function is what we aim to optimize.

• Minimum cost is achieved when the line first intersects the feasible set, indicating the lowest possible cost that satisfies all constraints.

Optimal Solution

• The intersection occurs at a corner (e.g., point B) where $x^* = 0$ and $y^* = 2$. Corners are critical in linear programming as they often represent optimal solutions.

• The minimum cost is $2x^* + 3y^* = 6$. This is the minimized value of the cost function.

• The vector $(0, 2)$ is feasible (lies in the feasible set) and optimal (minimizes the cost function). It is the solution to the linear programming problem.

• The minimum cost, 6, is the value of the program, representing the best possible outcome given the constraints.

System of Equations

• General form: $Ax = b$ (10) where A is a matrix of coefficients, x is the vector of variables, and b is the vector of constants.

• Matrix representation:

\begin{bmatrix}
a{11} & \cdots & a{1n} \
\vdots & \ddots & \vdots \
a{m1} & \cdots & a{mn}
\end{bmatrix} \times \begin{bmatrix}
x1 \ \vdots \ xn
\end{bmatrix} = \begin{bmatrix}
b1 \ \vdots \ bm
\end{bmatrix}

(11)

Cost Function in 3D

• Example: $2x + 3y + 4z$

• Vector representation:

\begin{bmatrix} 2 & 3 & 4 \end{bmatrix} \times \begin{bmatrix} x \
y \
z \end{bmatrix}

(12). This notation simplifies the representation and manipulation of cost functions in higher dimensions.

Linear Programming Components

• Constraint: Conditions that limit the feasible solutions, such as resource availability or requirements.

• Cost function: The function to be minimized or maximized, representing the objective (e.g., cost, profit).

• Feasible set: The set of all possible solutions that satisfy all constraints.

• Optimal solution: Minimize or maximize the cost function within the feasible set. This is the goal of linear programming.

• The optimal vector is found at a corner of the feasible set. This is a key property that simplifies the search for optimal solutions.

• The first contact with the feasible set must occur along its boundary. This means the optimal solution lies on the edge or corner of the feasible region.

Methods for Finding Optimal Solutions

1. Simplex method: An iterative algorithm that moves from one corner of the feasible set to another until the optimal solution is found.

2. Interior point method: Algorithms that move through the interior of the feasible region to find the optimal solution, often more efficient for large problems.

Important Considerations

• A different cost function may result in multiple optimal points, especially if the cost function is parallel to an edge of the feasible set.

• If the cost function is, e.g., $x + 2y$, the entire edge between points B and A could be optimal, indicating multiple solutions with the same cost.

• The minimum cost is $x^* + 2y^* = 4$ for all optimal vectors on this edge. All points on this edge yield the same minimum cost.

• The maximum problem may have no solution if the cost can increase indefinitely (unbounded). This occurs when the feasible region extends infinitely in the direction of increasing cost.

Categories of Linear Programming Problems

1. Infeasible: The feasible set is empty, meaning there are no solutions that satisfy all constraints.

2. Unbounded: The cost function is unbounded on the feasible set, meaning the cost can increase or decrease without limit.

3. Optimal: The cost reaches its minimum (or maximum) on the feasible set, providing a specific solution.

• Empty and unbounded cases are uncommon but important to recognize as they indicate issues with the problem formulation.

Slack Variables

• Convert an inequality to an equation, allowing easier manipulation and solution.

• Example: $x + 2y \geq 4$ (13)

• Introduce slack variable $w$: $w = x + 2y - 4$ (14)

• Constraint: $w \geq 0$ (15)

• Slack variables improve problem definition by transforming inequalities into manageable equations.

Primal Problem

• Minimize $cx$ subject to $Ax = b$ and $x \geq 0$ (16). This is a standard formulation of a linear programming problem.

The Diet Problem

• Two protein sources:

  • Steak

  • Peanut butter

• Each pound of peanut butter provides 1 unit of protein.

• Each pound of steak provides 2 units of protein.

• Requirement: At least 4 units of protein needed to meet nutritional needs.

Problem Formulation for Diet Problem

• A diet with $x$ pounds of peanut butter and $y$ pounds of steak must satisfy $x + 2y \geq 4$, along with $x \geq 0$ and $y \geq 0$. This defines the feasible set within the context of the diet.

• Objective: Minimize the cost of the diet while meeting the protein requirement.

• Cost:

  • Peanut butter: $2 per pound.

  • Steak: $3 per pound.

• Total cost: $2x + 3y$. This linear cost function needs to be minimized.

Duality

• Every linear program has a dual, which provides an alternative perspective on the problem.

• If the original problem is a minimization, its dual is a maximization, and vice versa.

• The minimum in the primal problem equals the maximum in its dual, offering a powerful tool for problem-solving and validation.

Protein Pills and the Dual Problem

• Consider an alternative: synthetic protein pills. This leads to the concept of a dual problem.

• The druggist wants to maximize the pill price $p$ subject to constraints, representing an optimization from a different angle.

• Constraints:

  • Synthetic protein must not cost more than protein from peanut butter ($2 per unit).

  • Synthetic protein must not cost more than protein from steak ($3 for two units).

  • The price must be nonnegative, ensuring a realistic scenario.

• Since 4 units of protein are required, the druggist's income will be $4p$. This is the objective function for the dual problem.

Dual Problem Formulation

• Maximize $4p$ subject to $p \leq 2$, $2p \leq 3$, and $p \geq 0$ (17). This is the mathematical formulation of the dual problem.

Linear Programming

• Minimize or maximize a linear cost function subject to linear constraints. A fundamental optimization technique with broad applications.

The Simplex Method

• Linear programming with $n$ unknowns $x \geq 0$ and $m$ constraints $Ax \geq b$.

• Best approach: Put the problem in matrix form.

  • $m \times n$ matrix A.

  • Column vector b with m components.

  • Row vector c (cost vector) with n components.

• Cost: $cx = c<em>1x</em>1 + \cdots + c<em>nx</em>n$

Simplex Algorithm Steps

1. Standard Form:

   • Transform objective function to maximization. If minimizing, negate the cost function.

   • Convert constraints to $\leq$ inequalities. Reverse inequalities by multiplying by -1.

   • Ensure all variables are non-negative. Add non-negativity constraints if necessary.

2. Introduce Slack Variables:

   • Convert inequalities to equations by adding slack variables (unused constraint portion). These variables represent the difference between the left and right sides of the inequality.

3. Initial Simplex Tableau:

   • Tabular representation with coefficients from objective function, constraints, and slack variables. Organize coefficients in a matrix to facilitate calculations.

4. Pivot Selection:

   • Pivot Column:

   • Maximization: Most negative entry in the Z-row (objective function row). This indicates the variable to increase to improve the objective function.

   • Minimization: Most positive entry. Choose the column that will decrease the objective function the most.

   • Pivot Row:

   • Calculate ratios of right-hand side values (b-values) to corresponding pivot column values. These ratios determine how much the entering variable can increase.

   • Smallest non-negative ratio determines the leaving variable. This ensures that the constraints remain satisfied.

5. Pivot Operation:

   • Use row operations to transform the pivot element to 1 and other entries in the pivot column to 0. This updates the tableau to reflect the change in the solution.

6. Iteration:

   • Repeat steps 4 and 5 until all entries in the Z-row are non-negative (maximization) or non-positive (minimization). This indicates that the optimal solution has been reached.

7. Optimal Solution:

   • Decision variable values in columns with 1s and 0s represent the optimal solution. Read the values from the right-hand side of the tableau.

   • Optimal objective function value is in the Z-row, bottom right-hand corner of the tableau. This is the maximum or minimum value of the objective function.

Geometry of the Simplex Method

• The method moves from corner to corner along edges of the feasible set, systematically improving the objective function until the optimal corner is reached.

Slack Variables and Pivoting

• Standard Maximization Problem:

  • Linear objective function to be maximized.

  • Non-negative variables.

  • Structural constraints of the form $ax + by + \cdots \leq c$, where $c \geq 0$. These constraints define the boundaries of the feasible region.

• Example:

  • Maximization: $2x + y \leq 4$ (18) becomes $2x + y + s<em>1 = 4$ (19), where $s</em>1$ is the slack variable.

  • Minimization: $2x + y \geq 4$ (20) becomes $2x + y - s<em>1 = 4$ (21), where $s</em>1$ is the surplus variable.

Problem: Feasible Set and Corners

• Sketch the feasible set with constraints: $x + 2y \geq 6, 2x + y \geq 6, x \geq 0, y \geq 0$. Graph the constraints to visualize the feasible region.

• Find the coordinates of the corners of this set. These corners are potential optimal solutions.

Minimizing a Cost Function

• On the feasible set, what is the minimum value of the cost function $x + y$? Determine the objective.

• Draw the line $x + y = constant$ that first touches the feasible set. This line represents the cost function, and its intersection with the feasible set indicates the minimum cost.

• What points minimize the cost functions $3x + y$ and $x - y$? Different cost functions will lead to different optimal points.

Standard Maximization Problem Example

• Maximize $6x + 4y$ (22)

• Subject to:

  • $x + 2y \leq 8$ (23)

  • $2x + y \leq 10$ (24)

  • $x \geq 0$ (25)

  • $y \geq 0$ (26)

Reduced Row Echelon Form

Duality (Primal and Dual Problems)

• Primal Problem:

  • Minimize $cx$ subject to $Ax \geq b$ and $x \geq 0$ (27)

• In the dual problem, b and c are switched, and the inequality direction is reversed.

• The dual unknown y is a row vector with m components.

• Feasible set: $yA \leq c$ instead of $Ax \geq b$. The constraints are transformed accordingly.

• Dual Problem:

  • Maximize $yb$ subject to $yA \leq c$ and $y \geq 0$ (28). This is the dual formulation of the linear programming problem.

Example: Primal and Dual Problems

• Minimize:

  • $x<em>1 + 4x</em>2$

• Subject to:

  • $2x<em>1 + x</em>2 \geq 6$

  • $5x<em>1 + 3x</em>2 \geq 7$

  • $x_1 \geq 0$

  • $x_2 \geq 0$

• Maximize:

  • $6y<em>1 + 7y</em>2$

• Subject to:

  • $2y<em>1 + 5y</em>2 \leq 1$

  • $y<em>1 + 3y</em>2 \leq 4$

  • $y_1 \geq 0$

  • $y_2 \geq 0$

Converting a Minimization Problem to its Dual

• Minimize:

  • $Z = 12x<em>1 + 16x</em>2$

• Subject to:

  • $x<em>1 + 2x</em>2 \geq 40$

  • $x<em>1 + x</em>2 \geq 30$

  • $x_1 \geq 0$

  • $x_2 \geq 0$

• Maximize:

  • $Z = 40y<em>1 + 30y</em>2$

• Subject to:

  • $y<em>1 + y</em>2 \leq 12$

  • $2y<em>1 + y</em>2 \leq 16$

  • $y_1 \geq 0$

  • $y_2 \geq 0$

System of Equations (Repeated)

• $Ax = b$ (29)

• Matrix representation:

\begin{bmatrix}
a{11} & \cdots & a{1n} \
\vdots & \ddots & \vdots \
a{m1} & \cdots & a{mn}
\end{bmatrix} \times \begin{bmatrix}
x1 \ \vdots \ xn
\end{bmatrix} = \begin{bmatrix}
b1 \ \vdots \ bm
\end{bmatrix}

(30)

Cost Function in 3D (Repeated)

• Example: $2x + 3y + 4z$

• Vector representation:

\begin{bmatrix} 2 & 3 & 4 \end{bmatrix} \times \begin{bmatrix} x \
y \
z \end{bmatrix}

(31)

Linear Programming (Repeated)

• Minimize or maximize a linear cost function subject to linear constraints.

The Simplex Method (Repeated)

• Linear programming with $n$ unknowns $x \geq 0$ and $m$ constraints $Ax \geq b$.

• Best approach: Put the problem in matrix form.

  • $m \times n$ matrix A.

  • Column vector b with m components.

  • Row vector c (cost vector) with n components.

• Cost: $cx = c<em>1x</em>1 + \cdots + c<em>nx</em>n$

Simplex Algorithm Steps (Repeated)

1. Standard Form:

   • Transform objective function to maximization.

   • Convert constraints to $\leq$ inequalities.

   • Ensure all variables are non-negative.

2. Introduce Slack Variables:

   • Convert inequalities to equations by adding slack variables (unused constraint portion).

3. Initial Simplex Tableau:

   • Tabular representation with coefficients from objective function, constraints, and slack variables.

4. Pivot Selection:

   • Pivot Column:

   • Maximization: Most negative entry in the Z-row (objective function row).

   • Minimization: Most positive entry.

   • Pivot Row:

   • Calculate ratios of right-hand side values (b-values) to corresponding pivot column values.

   • Smallest non-negative ratio determines the leaving variable.

5. Pivot Operation:

   • Use row operations to transform the pivot element to 1 and other entries in the pivot column to 0.

6. Iteration:

   • Repeat steps 4 and 5 until all entries in the Z-row are non-negative (maximization) or non-positive (minimization).

7. Optimal Solution:

   • Decision variable values in columns with 1s and 0s represent the optimal solution.

   • Optimal objective function value is in the Z-row, bottom right-hand corner of the tableau.

Standard Maximization Problem Example (Repeated)

• Maximize $6x + 4y$ (32)

• Subject to:

  • $x + 2y \leq 8$ (33)

  • $2x + y \leq 10$ (34)

  • $x \geq 0$ (35)

  • $y \geq 0$ (36)

Geometric Solution

• Calculate the value of the objective function at the four corners of the feasible region.

• $f = 6x + 4y$ or $-6x - 4y + f$

• Corner

  • (0,0) $f = 6 \times 0 + 4 \times 0 = 0$

  • (5,0) $f = 6 \times 5 + 4 \times 0 = 30$

  • (4,2) $f = 6 \times 4 + 4 \times 2 = 32$

  • (0,4) $f = 6 \times 0 + 4 \times 4 = 16$

Simplex Tableau

• Initial tableau:

• Choose the pivot column: The most negative entry in the objective function row.

• Choose the pivot row: The smallest ratio.

• Perform row operations:

  • $R<em>2 = R</em>2 / 2$

  • $R<em>1 = R</em>1 - R_2$

  • $R<em>3 = R</em>3 + 6R_2$

• Choose the pivot column and row again.

• 1.5 is the pivot element.

• Perform row operations:

  • $R<em>1 = R</em>1 / 1.5$

  • $R<em>2 = R</em>2 - 0.5R_1$

  • $R<em>3 = R</em>3 + R_1$

• All entries are non-negative in the optimal function row; stop iteration.

• The columns with 1s and 0s give the optimal solution.

Pivot Selection

• If another quotient is taken in pivot selection, it results in an infeasible point.

Maximization Problem Example

• Maximize $4x + 2y + 3z$ (37)

• Subject to:

  • $0.1x + 0.25y \leq 40$ (38)

  • $0.22x + 0.3y + 0.4z \leq 100$ (39)

  • $x \geq 0$ (40)

  • $y \geq 0$ (41)

  • $z \geq 0$ (42)

Initial Tableau

• $f = 4x + 2y + 3z$ or $-4x - 2y - 3z + f$

Row Operations

• $R<em>1 = R</em>1 / 0.1$

• $R<em>2 = R</em>2 - 0.22R_1$

• $R<em>3 = R</em>3 + 4R_1$

More Row Operations

• $R<em>2 = R</em>2 / 0.4$

• $R<em>3 = R</em>3 + 3R_2$

LP Problem with No Solution

• Pivot element does not exist.

• Negative number and negative column

• Maximize $x + 2y$ (43)

• Subject to:

  • $-3x + 2y \leq 5$ (44)

  • $4x - 3y \leq 9$ (45)

  • $x \geq 0$ (46)

  • $y \geq 0$ (47)

LP Problem with Edge Solution

• Maximize $6x + 3y$ (48)

• Subject to:

  • $x + 2y \leq 8$ (49)

  • $2x + y \leq 10$ (50)

  • $x \geq 0$ (51)

  • $y \geq 0$ (52)

Corner Solutions

• corner

  • (0,0) $f = 6 \times 0 + 3 \times 0 = 0$

  • (0,4) $f = 6 \times 0 + 3 \times 4 = 12$

  • (4,2) $f = 6 \times 4 + 3 \times 2 = 30$

  • (5,0) $f = 6 \times 5 + 3 \times 0 = 30$

Simplex Tableau and calculations

• 1st column is pivot column and 1st row is pivot row.

• Perform row operations:

  • $R<em>2 = R</em>2 / 2$

  • $R<em>1 = R</em>1 - R_2$

  • $R<em>3 = R</em>3 + 6R_2$

Newton’s Method and Definitions

Convex Sets and Functions

• Convex Set: A set where the line segment between any two points in the set is entirely within the set. Mathematically, for any two points $x, y$ in the set and any $\lambda \in [0, 1]$, the point $\lambda x + (1 - \lambda)y$ must also be in the set.

• Convex Function: A function where the line segment connecting any two points on its graph lies on or above the graph itself. For any $x, y$ in the domain and any $\lambda \in [0, 1]$, $f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda)f(y)$.

• Quadratic functions (like $x^2$) and exponential functions (like $e^x$) are convex. The second derivative of a convex function is non-negative.

• A convex function is continuous and its value at the midpoint of every interval does not exceed the arithmetic mean of its values at the ends of the interval. This property is a key characteristic of convex functions.

Concave Functions

• A function f is concave if -f is convex. The graph