Math 273a: Optimization
Instructor: Wotao Yin
Department of Mathematics, UCLA
Fall 2015
online discussions on [Link]
What is mathematical optimization?
Optimization models the goal of solving a problem in the optimal way.
Examples:
Running a business: to maximize profit, minimize loss, maximize
efficiency, or minimize risk.
Design: minimize the weight of a bridge/truss, and maximize the
strength, within the design constraints
Planning: select a flight route to minimize time or fuel consumption
of an airplane
Formal definition: to minimize (or maximize) a real function by deciding
the values of free variables from within an allowed set.
Optimization is an essential tool in life, business, and engineer.
Examples:
Walmart pricing and logistics
Airplane engineering such as shape design and material selection
Packing millions of transistors in a computer chip in a functional way
achieving these requires analyzing many related variables and possibilities,
taking advantages of tiny opportunities.
We will
cover some of the sophisticated mathematics for optimization
be closer to the reality than most other math courses
Status of optimization
Last few decades: astonishing improvements in computer hardware and
software, which motivated great leap in optimization modeling, algorithm
designs, and implementations.
Solving certain optimization problems has become standard techniques
and everyday practice in business, science, and engineering. It is now
possible to solve certain optimization problems with thousands, millions,
and even thousands of millions of variables.
Optimization has become part of undergrad curriculum. Optimization
(along with statistics) has been the foundation of machine learning and
big-data analytics. Matlab has two optimization toolboxes......
Ingredients of successful optimization
modeling: turn a problem into one of the typical optimization formulations
algorithms: an (iterative) procedure that leads you toward a solution
(most optimization problems do not have a closed-form solution)
software and, for some problems, hardware implementation: realize the
algorithms and return numerical solutions
First examples
Find two nonnegative numbers whose sum is up to 6 so that their product
is a maximum.
Find the largest area of a rectangular region provided that its perimeter is
no greater than 100.
Given a sequence of n numbers that are not all negative, find two indices
so that the sum of those numbers between the two (including them) is a
maximum.
Optimization formulation
minimize f (x)
x
subject to x C
minimize is often abbreviated as min
decision variable is typically stated under minimize, unless obvious
subject to is often shortened to s.t.
in linear and nonlinear optimization, feasible set C is represented by
hi (x) = bi , i E (equality constraints)
gj (x) bj0 , jI (inequality constraints)
A quadratic program (QP)
minimize f (x) = (x1 1)2 + (x2 1)2
Elements: decision variables, parameters, constraint, feasible set, objective.
A linearly constrained quadratic program (QP)
minimize f (x) = (x1 1)2 + (x2 1)2
subject to x1 + x2 = 3.
Elements: decision variables, parameters, constraint, feasible set, objective.
Linear program (LP)
From Griva-Nash-Sofer 1.2:
minimize f (x) = (2x1 + x2 )
subject to x1 + x2 1
x1 0, x2 0.
Elements: decision variables, constraints, feasible set, objective.
Nonlinear linear program (NLP)
minimize f (x) = (x1 + x2 )2
subject to x1 x2 0
2 x1 1
2 x2 1.
Elements: decision variables, feasible set, objective, (box) constraints, global
minimizer vs local minimizer.
Global vs local solution
Solution means optimal solution
Global solution x : f (x ) f (x) for all x C
Local solution x : > 0 such that f (x ) f (x) for all x C and
kx x k
a (global or local) solution x is unique if holds strictly as <
In general, it is difficult to tell if a local solution is global because
algorithms can only check nearby points and have not clue of behaviors
farther away. Hence, a solution may refer to a local solution.
A local solution to a convex program is globally optimal. A LP is convex.
A stationary point (where the derivative is zero) is also known as a
solution, but it can be a maximization, minimization, or saddle point.
This course
Most of this course focuses on finding local solutions and, for convex
programs, global solutions. This is seemingly odd but there are good
reasons:
Asking for global solutions is computationally intractable, in general.
Most global optimization algorithms (often takes long time to run) seeks
the global solution by finding local solutions
Many useful problems are convex, that is, a local solution is global
In some applications, a local solution is an improvement from an existing
point. Local solutions are OK.
We do not cover discrete optimization
Most of this course focuses on problems with continuous variables, such as
length, volume, strength, weight, time, etc.
Many useful variables are discrete such as yes/no decision, the number of
flights to dispatch, etc.
Discrete variables often take binary or integer values, or values from a
discrete set. Those problems are called discrete optimization.
In discrete problems, we cannot just check nearby points or simply round
non-integers to integers (exceptions exist though).
Continuous optimization is solved as subproblem in some discrete
optimization, though not always.
Quiz
Question: There are n numbers a1 , . . . , an with at least one ai 0. Find
Pt
1 s t n, so that i=s
ai is a maximum.
Idea: create x {0, 1}n of the form [0, . . . , 0, 1 . . . , 1, 0 . . . , 0] such that
Pt Pn
i=s
ai = i=1
ai xi
Quiz
Question: There are n numbers a1 , . . . , an with at least one ai 0. Find
Pt
1 s t n, so that i=s
ai is a maximum.
Idea: create x {0, 1}n of the form [0, . . . , 0, 1 . . . , 1, 0 . . . , 0] such that
Pt Pn
i=s
ai = i=1
ai xi
Solution:
n
X
maximizen ai xi
x,y,z{0,1}
i=1
subject to x0 = xn+1 = 0
n
X
xi 1 select at least one
i=1
n
X
xi xi1 yi , yi = 1 0-to-1 change
i=1
Xn
xi xi+1 yi , zi = 1 1-to-0 change.
i=1
Quiz
Question: There are n numbers a1 , . . . , an with at least one ai 0. Find
Pt
1 s t n, so that i=s
ai is a maximum.
Idea: create x {0, 1}n of the form [0, . . . , 0, 1 . . . , 1, 0 . . . , 0] such that
Pt Pn
i=s
ai = i=1
ai xi
Combinatorial algorithm: there is an O(n) algorithm to solve the
problem with just one pass of data.
