Optimization I

Notes from .

Introduction

• Tool of conceptualization and analysis rather than a orrect solution.
• Modelling optimization problem requires a lot of practical experience.
  • Must be able to distinguish tractable models from nontractable ones
• Linear vs Nonlinear programming

Types of Optimization Problems

Linear Programming

• Objective is linear and constraint are linear equalities or inequalities.
  • Populat as many problems in practice have linear constraints and objectives.
  • Objective and constrainsts which are linear are least difficult to define.
    • Linearity due to its simplicity is easy to reason about and get an initial answer.
    • Most known method: Simplex

Unconstrained Problems

• Optimization without constraints on arbitrary objectives.
  • Many constraints can be implemented in the objective (ex: availability of resources which at some cost (however great) can be supplemented/replenished).
  • Ex: $x_1 + x_2 = B$ can be substituted in the objective as $x_2 = B-x_1$.
• Usually though, it is a stepping stone to constrained problems (with some practical exceptions)

Constrained Problems

• Worst case: nonlinear constraints (equalities and inequalities) and objectives
• Quite common in real complex planning problems.
• Sometimes additional assumptions are used to make problem smooth and easier
  • Ex: continuity and continuous derivatives
  • Compact and connected sets of state space
  • Becomes “Continous Variable Programming”
  • Assumption for many algorithms which make sequences of small movements in the unknown set of statespace.

Size of Problems

• Large scale problems (1000 or more vars to solve) requires exploiting special structure and high compute.

Iterative algorithms and convergence

• Most algorithms are iterative in nature
• Start from an intial vector and the algorithm constantly refines/improves the intial gues..
• This process is repeated until “convergence”
  • Difference between the refinement is below some threshold $\epsilon$.
• “One good theory is worth a thousand computer runs.”
• Good algorithm will have fast convergence.