Unit5

Equation of a Straight Line and Plane

• Equation of a straight line in intercept form: $\frac{x}{a} + \frac{y}{b} = 1$ (1)
• Equation of a plane in intercept form: $\frac{x}{a} + \frac{y}{b} + \frac{z}{c} = 1$ (2)
• If $c \rightarrow \infty$, the plane becomes similar to a straight line.
• Equation: $\frac{x}{a} + \frac{y}{b} = 1 \quad \forall \quad z$ (3)

Family of Curves

• Equation: $y = mx + c$
• $m$ is negative and fixed.
• $c$ varies from one value to another.
• Examples:
  • $y = -2x + 3$ (4)
  • $y = -2x$ (5)
  • $y = -2x - 3$ (6)
• Identify regions between lines using inequalities.

Linear Inequalities

• Algebra focuses on equations (determinants, eigenvalues).
• Analysis focuses on inequalities.
• Linear programming deals with inequalities.
• Decision-making involves inequalities.
• Three approaches to underlying mathematics:
  • Intuitively through geometry.
  • Computationally through the simplex method.
  • Algebraically through duality.

Geometric Meaning of Linear Inequalities

• An inequality divides n-dimensional space into two halfspaces.
• One halfspace satisfies the inequality; the other does not.
• Example: $x + 2y \geq 4$ (7)
• The boundary between halfspaces is the line $x + 2y = 4$.

Strict vs. Tight Inequalities

• Strict inequalities exclude equality (e.g., "
• Tight inequalities allow equality in some cases.
  • Example: $x^2 + y^2 \geq 2xy$ (equality holds when $x = y$).

Equations, Inequalities, and Halfspaces

• Equations represent lines and planes.
• Inequalities represent halfspaces.
• In n-dimensional space, a plane has dimension $n - 1$.

Non-Negativity Constraints

• A fundamental constraint in linear programming requires variables to be nonnegative.
• Examples:
  • $x \geq 0$ (8)
  • $y \geq 0$ (9)
• These inequalities produce additional halfspaces.

Feasible Set and Cost Function

• The feasible set results from imposing all inequalities simultaneously.
• It is the intersection of halfspaces.
• The cost function (e.g., $2x + 3y$) touches the feasible set.

Properties of Feasible Sets

• A feasible set is the solution to a family of linear inequalities like $Ax \geq b$ (intersection of m halfspaces).
• Nonnegativity constraints $x \geq 0$ add n more halfspaces.
• More constraints lead to smaller feasible sets.

Examples of Feasible Sets

• Small triangle:
  x + 2y \leq 4, x \geq 0, y \geq 0
  
• Shrinking to a straight line:
  x + 2y \leq 4, x + 2y \geq 4
  
• Empty set:
  x + 2y \leq -2
  

Aspects of Linear Inequalities

• Feasible set.
• Feasible point that maximizes or minimizes a cost function.

Cost Function

• Example: $2x + 3y$ represents a family of parallel lines.
• Minimum cost occurs when the line first intersects the feasible set.

Optimal Solution

• Intersection occurs at point B, where $x^* = 0$ and $y^* = 2$.
• Minimum cost: $2x^* + 3y^* = 6$.
• The vector $(0, 2)$ is feasible and optimal.
• Minimum cost of 6 is the value of the program.

System of Equations

• Represented as $Ax = b$ (10)
• Where A is a matrix, x is a vector of variables, and b is a vector of constants:

$[\begin{bmatrix} a<em>{11} & \cdots & a</em>{1n} \ \cdots &amp; &amp; \ a<em>{m1} & \cdots & a</em>{mn} \end{bmatrix}] \times [\begin{bmatrix} x<em>1 \ \cdots \ \cdots \ x</em>n \end{bmatrix}] = [\begin{bmatrix} b<em>1 \ \cdots \ b</em>m \end{bmatrix}]$ (11)

Cost Function in Multiple Dimensions

• Example: $2x + 3y + 4z$
• Represented in vector form:
  
  [\begin{bmatrix} 2 & 3 & 4 \end{bmatrix}] \times [\begin{bmatrix} x \ y \ z \end{bmatrix}]
  (12)

Key Components

• Constraint
• Cost function
• Feasible set
• Optimal solution
• Goal: Minimize or maximize the cost function.

Optimal Vector

• Occurs at a corner of the feasible set.
• First contact occurs along the boundary.
• Methods:
  • Simplex method
  • Interior point method

Important Points

• A different cost function can result in an intersection that is not a single point.
• Example: If the cost is $x + 2y$, the whole edge between points B and A is optimal.
• Minimum cost: $x^* + 2y^* = 4$ for all optimal vectors.
• Maximum problem on the feasible set may have no solution (cost can go arbitrarily high).

Categories of Linear Programming Problems

• The feasible set is empty.
• The cost function is unbounded on the feasible set.
• The cost reaches its minimum (or maximum) on the feasible set (the good case).
• Empty and unbounded cases are uncommon.

Slack Variables

• Purpose: Change inequality to an equation.
• Example:
  • Original inequality: $x + 2y \geq 4$ (13)
  • Introducing slack variable: $w = x + 2y - 4$ (14)
  • Constraint on slack variable: $w \geq 0$ (15)
• Improves problem definition.

Primal Problem

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

Diet Problem and Its Dual

• 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 in the diet.

Problem Formulation for Diet

• A diet containing x pounds of peanut butter and y pounds of steak is constrained by:
  • $x + 2y \geq 4$
  • $x \geq 0$
  • $y \geq 0$
• This defines the feasible set.
• Goal: Minimize the cost of the diet.
• Cost per source:
  • Peanut butter: $2 per pound
  • Steak: $3 per pound
• Total cost: $2x + 3y$

Duality in Linear Programming

• Every linear program has a dual.
• If the original problem is minimization, the dual is maximization.
• The minimum in the primal problem equals the maximum in its dual.

Protein Pills Example

• Synthetic protein as a substitute.
• Druggist maximizes the pill price p, subject to linear constraints.
• Constraints:
  • Synthetic protein must not cost more than protein in peanut butter ($2 per unit).
  • Synthetic protein must not cost more than protein in steak ($3 for two units).
  • The price must be nonnegative.
• Income to the druggist: $4p$ (since 4 units of protein are required).

Dual Problem Formulation

• Maximize $4p$, subject to:
  • $p \leq 2$
  • $2p \leq 3$
  • $p \geq 0$ (17)

Linear Programming Overview

• Objective: Minimize or maximize a linear cost function.
• Constraints: Linear constraints.

Simplex Method

• Applies to linear programming problems with n unknowns and m constraints where $x \geq 0$ and $Ax \geq b$.
• Best approach: Put the problem into matrix form.
  • An m x n matrix A.
  • A column vector b with m components.
  • A row vector c (cost vector) with n components.
• Cost: $cx = c<em>1x</em>1 + \cdots + c<em>nx</em>n$

Steps in Simplex Algorithm

• Standard Form: Convert LPP to standard form.
  • Transform objective function to a maximization problem.
  • Convert all constraints to $\leq$ inequalities.
  • Ensure all variables are non-negative.
• Introduce Slack Variables: Convert inequalities into equations by adding slack variables.

Simplex Tableau and Pivot Selection

• Initial Simplex Tableau: Construct the initial tableau with coefficients from the objective function, constraints, and slack variables.
• Pivot Selection:
  • Pivot Column: Most negative entry in the Z-row for maximization, most positive for minimization.
  • Pivot Row: Smallest non-negative ratio of right-hand side values to pivot column values.

Pivot Operation and Iteration

• Pivot Operation: Transform the pivot element to 1 and other entries in the pivot column to 0 using row operations.
• Iteration: Repeat pivot selection and operation until all entries in the Z-row are non-negative (maximization) or non-positive (minimization).

Optimal Solution

• Values of decision variables in columns with 1s and 0s in the final tableau represent the optimal solution.
• Optimal value of the objective function is in the Z-row, bottom right-hand corner.

Geometry of Simplex Method

• Movement Along Edges: The method moves from corner to corner along the edges of the feasible set.

Slack Variables and Problem Types

• Standard Maximization Problem:
  • Objective function is linear and maximized.
  • Variables are non-negative.
  • Structural constraints are of the form $ax + by + \cdots \leq c$, where $c \geq 0$.
• Examples:
  • Maximization: $2x + y \leq 4$ (18) becomes $2x + y + s_1 = 4$ (19)
  • Minimization: $2x + y \geq 4$ (20) becomes $2x + y - s_1 = 4$ (21)

Problem: Feasible Set Sketch

• Sketch the feasible set with constraints
  x + 2y \geq 6, 2x + y \geq 6, x \geq 0, y \geq 0
  
• Identify the points at the three corners of this set.

Cost Function Minimization

• On the feasible set, find the minimum value of the cost function $x+y$.
• Draw the line $x+y = constant$ that first touches the feasible set.
• Find the points that minimize the cost functions $3x+y$ and $x-y$.

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)
• Graphical representation includes feasible region and corner points.

Reduced Row Echelon Form

• Used in solving linear programming problems.

Primal and Dual Problems

• Primal Problem: Minimize $cx$ subject to $Ax \geq b$ and $x \geq 0$ (27)
• Dual Problem: Maximize $yb$ subject to $yA \leq c$ and $y \geq 0$ (28)
• In the dual problem, b and c are switched.
• The dual unknown y is a row vector with m components.
• The feasible set has $yA \leq c$ instead of $Ax \geq b$.

Example: Primal and Dual Conversion

• Minimize: $x<em>1 + 4x</em>2$ subject to
  2x1 + x2 \geq 6, 5x1 + 3x2 \geq 7, x1 \geq 0, x2 \geq 0
  
• Maximize: $6y<em>1 + 7y</em>2$ subject to
  2y1 + 5y2 \leq 1, y1 + 3y2 \leq 4, y1 \geq 0, y2 \geq 0
  

Conversion Example: Minimization to Dual

• Minimize $Z = 12x<em>1 + 16x</em>2$ subject to
  x1 + 2x2 \geq 40, x1 + x2 \geq 30, x1 \geq 0, x2 \geq 0
• Conversion:
  • Original coefficients:

• Maximize $Z = 40y<em>1 + 30y</em>2$ subject to
  y1 + y2 \leq 12, 2y1 + y2 \leq 16, y1 \geq 0, y2 \geq 0

Reminder: System of Equations

• $Ax = b$ (29)
  
  [\begin{bmatrix} a{11} & \cdots & a{1n} \ \cdots & & \ a{m1} & \cdots & a{mn} \end{bmatrix}] \times [\begin{bmatrix} x1 \ \cdots \ \cdots \ xn \end{bmatrix}] = [\begin{bmatrix} b1 \ \cdots \ bm \end{bmatrix}]
  (30)

Reminder: Cost Function

• $2x + 3y + 4z$
  
  [\begin{bmatrix} 2 & 3 & 4 \end{bmatrix}] \times [\begin{bmatrix} x \ y \ z \end{bmatrix}]
  (31)

Reminder: Linear Programming

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

Reminder: Simplex Method

• Linear programming with $n$ unknowns $x \geq 0$ and $m$ constraints $Ax \geq b$.
• Matrix form:
  • $m \times n$ matrix $A$.
  • Column vector $b$ with $m$ components.
  • Row vector $c$ (cost vector) with $n$ components.
• Cost is $cx = c<em>1x</em>1 + \cdots + c<em>nx</em>n$.

Reminder: Simplex Algorithm Steps

• Standard Form: Transform to maximization, $\leq$ inequalities, non-negative variables.
• Slack Variables: Convert inequalities to equations.

Reminder: Simplex Tableau and Pivot Selection

• Initial Tableau: Coefficients from objective function, constraints, and slack variables.
• Pivot Selection:
  • Pivot Column: Most negative entry in Z-row (maximization), most positive (minimization).
  • Pivot Row: Smallest non-negative ratio of right-hand side values to pivot column values.

Reminder: Pivot Operation and Iteration

• Pivot Operation: Make pivot element 1, other entries in pivot column 0 (row operations).
• Iteration: Repeat until all entries in Z-row are non-negative (maximization) or non-positive (minimization).

Reminder: Optimal Solution

• Decision variables corresponding to columns with 1s and 0s in the final tableau represent the optimal solution.
• Optimal value of the objective function is in the Z-row, bottom right-hand corner of the tableau.

Standard Maximization Problem

• Maximize $6x + 4y$ (32)
• Subject to:
  • $x + 2y \leq 8$ (33)
  • $2x + y \leq 10$ (34)
  • $x \geq 0$ (35)
  • $y \geq 0$ (36)
• The feasible region is graphically represented.

Geometric Solution

• Calculate the value of the objective function at the corners of the feasible region.
• Corners: (0,0), (5,0), (4,2), (0,4)
• $f = 6x + 4y$
  • f(0,0) = 0
  • f(5,0) = 30
  • f(4,2) = 32
  • f(0,4) = 16

Simplex Tableau Setup

• Initial tableau:

| | | | | | | |
| :-- | :- | :- | :--- | :--- | :- | :- |
| | x | y | s1 | s2 | f | |
| | 1 | 2 | 1 | 0 | 0 | 8 |
| | 2 | 1 | 0 | 1 | 0 | 10 |
| | -6 | -4 | 0 | 0 | 1 | 0 |

• Choose the pivot column (most negative entry in the objective function row).

Pivot Row Selection

• Smallest ratio determines pivot row.

| | | | | | | | Ratio |
| :-- | :- | :- | :--- | :--- | :- | :- | :----- |
| | x | y | s1 | s2 | f | | |
| | 1 | 2 | 1 | 0 | 0 | 8 | 8/1 = 8 |
| | 2 | 1 | 0 | 1 | 0 | 10 | 10/2 = 5 |
| | -6 | -4 | 0 | 0 | 1 | 0 | |

Row Operations

• $R<em>2 = R</em>2 / 2$, $R<em>1 = R</em>1 - R<em>2$, $R</em>3 = R<em>3 + 6R</em>2$

First Iteration Result

• Choose pivot column and pivot row for the next iteration.

Second Pivot Selection

Final Tableau and Optimal Solution

| | | | | | | |
| :-- | :- | :-- | :--- | :--- | :- | :- |
| | x | y | s1 | s2 | f | |
| | 0 | 1 | 2/3 | -1/3 | 0 | 2 |
| | 1 | 0 | -1/3 | 2/3 | 0 | 4 |
| | 0 | 0 | 2/3 | 8/3 | 1 | 32 |

• Stop iteration when all entries are non-negative in the optimal function row.
• Optimal solution: $x = 4$, $y = 2$, $f = 32$. Columns with 1s and 0s give the solution.

Infeasible Points

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

Example with Multiple Variables

• 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)

Tableau and Initial Operations

• $f = 4x + 2y + 3z \quad or \quad −4x −2y −3z + f$

• Perform $R<em>1 = R</em>1/0.1 , R<em>2 = R</em>2 −0.22R<em>1$ and $R</em>3 = R<em>3 +4R</em>1$

Further Operations and Results

• Perform $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, 4x − 3y \leq 9, x \geq 0, y \geq 0

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)
• Corners:
  • (0,0) f = 0
  • (0,4) f = 12
  • (4,2) f = 30
  • (5,0) f = 30

Simplex Tableau Setup

| | | | | | | |
| :-- | :- | :- | :--- | :--- | :- | :- |
| | x | y | s1 | s2 | f | |
| | 1 | 2 | 1 | 0 | 0 | 8 |
| | 2 | 1 | 0 | 1 | 0 | 10 |
| | -6 | -3 | 0 | 0 | 1 | 0 |

• 1st column is the pivot column and 1st row is the pivot row.
• Perform $R<em>2 = R</em>2/2, R<em>1 = R</em>1 −R<em>2$ and $R</em>3 = R<em>3 +6R</em>2$

| | | | | | | |
| :-- | :- | :- | :--- | :--- | :- | :- |
| | x | y | s1 | s2 | f | |
| | 0 | 1.5 | 1 | -0.5 | 0 | 3 |
| | 1 | 0.5 | 0 | 0.5 | 0 | 5 |
| | 0 | 0 | 0 | 3 | 1 | 30 |

Newton’s Method and Definitions

• Introduction to Newton's method and related concepts.

Convex Sets and Functions

• Convex Set: A set where for any two points, the line segment connecting them is entirely within the set.
• Convex Function: A function where the line segment connecting any two points on its graph lies on or above the graph itself.

Examples of Convex Functions

• Quadratic functions (e.g., $x^2$) and exponential functions (e.g., $e^x$) are convex.
• Convex Function Definition: $f(\frac{x<em>1+x</em>2}{2}) \leq \frac{f(x<em>1)+f(x</em>2)}{2}$

Concave Functions

• A function $f$ is concave if $-f$ is convex.
• A function $f$ is strictly concave if $-f$ is strictly convex.

Convex Hull

• The smallest convex polygon or polytope that contains all the points.

Hyper-Prefix

• Indicates a generalization to higher dimensions (e.g., hypercube).
• Hyperplane
  Hypercube

Constrained and Unconstrained Problems

• Differentiating between optimization problems with and without constraints.

Newton’s Method Example

• Finding solution for a polynomial with Newton’s method.
  Let $f (x) = x<em>1^2 −x</em>1x<em>3 +x</em>2^2 +3x<em>2 +2x</em>3^2$ (53); $x = [x<em>1 x</em>2 x_3]$ (54)

Single Variable Optimization

• Find minimum value of function $f(x) = x^2$, -2 < x < 3 (55)
  If $\frac{df}{dx} = 0$ and $\frac{d^2f}{dx^2} \geq 0$
  is local minimum

Multivariate Optimization

• Function: $f (x) = x<em>1^2 −x</em>1x<em>3 +x</em>2^2 +3x<em>2 +2x</em>3^2$ (57)
• Gradient:
  \nabla f(x) = [\begin{bmatrix} 2x1 - x3 \ 2x2 + 3 \ -x1 + 4x_3 \end{bmatrix}]
  (58)

Hessian Matrix

• Hessian:
  \nabla^2 f(x) = H(x) = [\begin{bmatrix} 2 & 0 & -1 \ 0 & 2 & 0 \ -1 & 0 & 4 \end{bmatrix}]
  (59)
• For quadratic functions, the Hessian matrix is constant.

Constrained Optimization Example

• Find the greatest and smallest values of $f(x,y) = xy$ on the ellipse $\frac{x^2}{8} + \frac{y^2}{2} = 1$

Distance to Origin

• Minimize distance from origin to a point on a plane.
• Problem: Find point $P(x, y, z)$ on plane $2x + y - z - 5 = 0$ closest to the origin.
• Formulation:
  • $|OP| = \sqrt{(x - 0)^2 + (y - 0)^2 + (z - 0)^2} = \sqrt{x^2 + y^2 + z^2}$ (60)
  • Subject to constraint: $2x + y - z - 5 = 0$ (61)

Solution

• Substitute $z = 2x + y - 5$ (62)
• $h(x,y) = x^2 + y^2 + (2x + y - 5)^2$ (63)
• $\frac{\partial h}{\partial x} = 2x + 2(2x + y - 5) = 0$
• $\frac{\partial h}{\partial y} = 2y + 2(2x + y - 5) = 0$ (64)
• $10x + 4y = 20$
• $4x + 4y = 10$ (65)
• Solving:
  • $x = \frac{5}{3}$
  • $y = \frac{5}{6}$ (66)

Lagrange Multipliers

• Maximize and minimize $f(x,y) = x^2 + 2y^2 - 4y$ subject to $x^2 + y^2 = 9$
• $\nabla f(x,y) = \lambda \nabla g(x,y)$ (67)
  • $2x = \lambda 2x$
    *