Unconstrained and Constrained Optimization Flashcards
1
Q
How do you find a critical point of a single variable function using calculus?
A
Take derivative and set it equal to zero. Solve for critical point(s).
2
Q
How do you determine Max/Min of a single variate function using calculus?
A
Take second derivative, if its “+” then its a minima (inflection concave, bowl), if “-“ then maxima (inflection convex, hill)
3
Q
How do you find the critical points for multi-variate function with calculus?
A
Take gradient of function w.r.t. all variables. Set = 0, solve for critical point(s).
4
Q
How do you determine if multi-variate function is max/min?
A
Take Hessian H(x), (determinant of second gradient).
- Positive Definite Hessian - positive value of determinant, all eigenvalues ‘+’, point is minima.
- Positive Semi-Definite Hessian - Det(H(x)) >= 0, one eigenvalue = 0, point could be infinite line or unbound from below/above.
- Negative Definite - negative determinant, all eigenvalues ‘-‘, point is maxima.
- Indefinite - both positive and negative eigenvalues, saddle point.
5
Q
Define a Positive Definite Matrix, what does PD hessian mean?
A
PD matrix means all eigenvalues are positive. PD hessian means determinant is positive, point is a minima.
6
Q
Define a Positive Semi-Definite Matrix, what does PSD hessian mean?
A
A PSD matrix means at least one, or multiple eigenvalues are = 0, the rest are positive. A PSD hessian means your minimizer could be a hyperplane of infinite minima or its unbounded from below/above
7
Q
Define a Negative Definite Matrix, what does ND hessian mean?
A
a ND matrix means all eigenvalues are negative. A ND hessian means the point is a maximum.
8
Q
Define a non-singular indefinite matrix
A
Both positive and negative eigenvalues
9
Q
Define a non-singular/invertible matrix
A
matrix that can be inverted, AA^(-1) = I
10
Q
Define a singular matrix
A
matrix that does not have an inverse
11
Q
Find eigenvalues and eigenvectors of 2x2 matrix:
A
1) (A-lambdaI)
2) det(A-lambdaI) = 0
3) (A-lambda_iI)V_i = 0 *for each lambda is V
12
Q
What is optimization?
A
The process of making something fully perfect, functional, or effective as possible. *Mathematically finding the min/max within a neighborhood or constraints.
13
Q
What is the goal of unconstrained optimization?
A
To minimize some function f(x), or maximize -f(x).
14
Q
What are challenges associated with unconstrained optimization.
A
- The function f(x) may be unknown form, or have little knowledge of the shape
- f(x) may be expensive to evaluate, may need to reduce number of function calls/queries of objective function
15
Q
What is Newton’s Root Finding Method?
A
Root finding methods are used the determine the ‘x’ values at which a function ‘g’, crosses zero using successive approximations to these roots:
x_n+1 = x_n - f(x_n)/f’(x_n)
16
Q
What is the first step to Newton’s root finding method?
A
Need an initial point.
17
Q
How do we determine an initial pt for Newton’s root finding?
A
Make a plot, or guess based on intuition.
18
Q
What is a multimodal problem?
A
a multimodal problem is a problem with multiple local minima/optimum over a range of x
*unimodal - monotonically increases for some range x<=m, and decreases for some range x>=m (single optima)
19
Q
When do calculus-based method fail to find a minima
A
- Higher order functions
- Transcendental functions
- Constrained optimization
- Functions that are “black box” functions of unknown form
20
Q
When does a derivative of a function not exist?
A
- When the function is not continuous: cusp, hold, any discontinuity
- If an asymptote or vertical/horizontal line
21
Q
What is the Lagrangian Function?
A
A modification to an objective function accounting for “m” inequality constraints and l equality constraints
22
Q
What are Lagrange multipliers?
A
They tell you the sensitivity of the solution to perturbation of the constraint.
- zero = inactive / passive
- large = highly sensitive
- small = insensitive to changes in constraint
23
Q
What is an active constraint?
A
A constraint for which the constrained optimization solution lies on the boundary, preventing the solution from reaching the unconstrained global minima.
24
Q
What are 3 characteristics of “Black Box” functions?
A
1) Functions of unknown form
2) Functions may be engineering tools that are expensive to run: inadequate # samples, can’t plot, too many vbls to visualize
3) Functions often strongly non-linear and have discontinuities
25
What is engineering analysis?
Given the values for the design variables, analysis to determine how we expect the system to perform
26
What is engineering design?
Given a desired performance or measure of ranking designs based on performance, what system do we want?
27
What is the vector x in an optimization problem f(x)?
X - is a design variable vector related to the design drawn from the design space.
28
What is a weak local solution to a minimization problem?
A weak local solution is x* of which f(x*) < = f(x) for all x in Neighborhood around x*
29
What is a strong local solution to a minimization problem?
A strong local solution is x* of which f(x*) < f(x*) for all x in the Neighborhood of N around x*
30
What is a global solution? Which type of function guarantees global sol?
X* is a global minimizer of f(x*) <= f(x) for ALL x.
| A convex function guarantees a global sol.
31
Why are global solutions difficult to find?
Because we can only evaluate f(x), grad_f(x), and H(x) locally - one point at a time. Its difficult to know when to stop, there is no test that guarantees a global solution without further info unless function is convex.
32
Define the concept of convexity, write the equation
a function is convex if for all points x1,x2 in the domain of f(x) and for all lambda [0,1], the value of the function at (x1*lambda+(1-lambda)*x2) is less than then function average f(x1)*lambda + (1-lambda)*f(x2).
- if f is convex, any local optimizer x* is a global minimizer
* concept of convexity proves unimodality
33
What are the first and second order necessary conditions for unconstrained optimization?
(Optimality Conditions)
1st Order Nec:
If x* is a local minimizer, and the function is continuous and differentiable - the gradient at x* must equal zero.
2nd Order Nec:
if x* is a local minimizer, and the function is continuous and differentiable - the gradient at x* must equal zero and the hessian at x* must be positive semi-definite.
34
What are the first and second order sufficient conditions?
If the gradient f(x*) equals zero and the hessian H(x*) is positive definite at the critical point x*, then x* is a strong local solution.
**ONLY CONDITIONS that guarantee minimizer solution.
35
What is an optimization algorithm?
An optimization algorithm is one that evaluates a sequence of designs with the goal of finding the best.
36
Basic steps of an optimization algorithm (super abbreviated):
1) Starting point for design (x)
2) Information of state around x
3) Select subset of design space to search for improvement upon current point from state of x information
4) Search subset area, stop after sufficient improvement to "best" in subset
5) Move to this pt as "current state" - restart step 2
6) Iterate until improvement is "good enough"
37
What are three types of unconstrained optimization algorithms?
Direct search, line search, and trust region methods
38
Describe Direct Search Methods
1. No derivatives used in search
| 2. Search direction based on a sequence, patter, or random
39
What are the types of Direct Search Methods?
1. Grid & Random search - distribute pts, evaluate function and zoom to min(f) for finer discretiziation
2. Random walk, compass search, and coordinate pattern search - use univariate directions (or random) to check function improvements, eval min(f), and move
40
Describe Line Search Methods
1. Typically uses derivatives to define search direction, but not always
2. Search is conducted along successive lines in design space.
-only allows for semi-definite or definite hessians
"fix direction (p), compute step length (alpha)"
41
What are the orders of Line Search Methods? Explain each one
Zeroth Order:
- only uses function values f(x)
First Order:
- uses function value f(x), and gradient grad_f(x)
- may approximate hessian w/ first order methods
Second Order:
- uses f(x), grad_f(x), and Hessian H(x)
42
Describe Trust Region Methods.
1. Search is conducted locally by approximating objective function as quadratic or linear
2. "trust region" refers to how far from current point your model function is still a valid approximation
3. Trust regions allow for indefinite or semi-definite Hessians (line search does not)
"fix distance (delta), choose direction (p)"
43
What are the two types of line search methods?
Exact and Inexact
44
What is an unconstrained optimization Merit Function? What is the relation to the objective function? What is its advantage?
The merit function is a 1D slice of high-dimensional space, approximating the objective function.
phi(a) = f(x_k+a*p)
min phi(a)
phi(0) = f(x)
phi'(0) = dphi/da)a = 0 = grad_f(x_k)*p < 0
45
Why does unconstrained optimization require sufficient decrease and curvature conditions?
The line search method f(xk+a*pk) <= f(xk) is not enough to produce convergence to an inflection pt/minimizer x*.
- -Finds relative decrease each iteration, but could miss local min
- -Why we need Wolfe Conditions
46
What is the sufficient decrease condition?
Sufficient decrease, first wolfe, or armijo condition: checks that the value of the merit function at alpha is less than the starting point value
47
What is the second Wolfe Condition?
The second Wolfe Condition checks that the slope of the merit function is increasing to more negative
48
What is the Strong Wolfe Condition?
The Strong Wolfe condition checks that the absolute value of the merit function at alpha is less than the absolute at the origin.
--> It insures the function is swallowing out like approaching the bottom of the bowl.
49
Draw a representation of a merit function depicting the First Wolfe, Second Wolfe, and Strong Wolfe Conditions:
--
50
What is the generic form of the line search method? What are the steps?
xk = x0 + a*pk
1. Define an initial point in the design space to begin search x0
2. Define a descent search direction - grad(f(x))
3. Find the value alpha that minimizes the function along the descent search direction. (step length 'alpha' approximations)
4. Decide when the process has converged to an acceptable solution to stop iterating grad(f(x)) = 0
51
What 3 methods are used for approximating alpha step lengths (inexact line searches)?
1. Backtracking
2. Polynomial approximation
3. Golden Section Method (GSM)
52
What is a back-tracking line search?
1. Start at a given start length for alpha.
2. Evaluate the merit function at alpha_k
3. Check if satisfies the sufficient decrease condition.
4. Decrease length of alpha for next step by some percentage.
Repeat
53
What are polynomial approximations?
The idea is that we approximate the function f(X) along the search direction in terms of alpha. typically interested in "reasonable" but inexact approximations of the minimum along the search line.
Use quadratic or cubic
54
How do we use polynomial approximations to find a min?
- For a quadratic objective function, we would need either a 2 pt. or 3 pt. approximation to find unknown constants
- Once we have a form for polynomial approximation, we can differentiate with respect to alpha and find the value of alpha that minimizes f along the search direction.
55
How do we select the pts that define the polynomial approximation?
We bracket the minimum to ensure that we can find a good approximation along the line.
56
What assumptions for bracketing the minimum?
- Assume the problem has a single minimum
- Assume that we are traveling along a descent direction.
- Assume that we are working with a fixed interval size
57
What is the general idea of bracketing the minimum for a polynomial approximation?
Choosing points such that they reduce/interior to the min/max points between (f1,f2,f3) if f1
58
What are the issues that come with approximating minimum steps in polynomial approximation of an un bound min function?
Choice of too small an interval: f3 < min(f1,f2) - may not include local min
Choice of too large an interval: f1 < min(f2,f3) - may infinitely decrease steps
59
What is the basic process of GSM?
The golden section method is successively refines the bracketing of the minimum step length in order to converge to an estimate the step length a* that corresponds to a minimum f(x*).
60
What is beneficial of GSM? What are limitations?
It eliminates the same fraction of the interval in successive iterations.
Limitations are that GSM only good for convex functions or unimodal (second deriv > 0 everywhere)
61
What is the procedure of GSM?
Start with first bracket along search direction defined by an upper and lower bound.
- add two intermediate points
- replace one bound with new pt reducing size of search region
- re-label the remaining intermediate point and develop a new intermediate point based on effective spacing rules.
62
What are GSM spacing rules? Explain the golden ratio
The two relations guarantee that we discard the same fraction of the interval with respect to each new point and the interior remaining point.
The ratio of the intermediate points gives us the golden section ratio: 1.618
63
How do we determine convergence to estimate along minimum of GSM method?
Establish relative tolerance
64
What is the comparison between polynomial approx vs. GSM?
If you know the function is unimodal when use polynomial approximation.
If you don't, then you may want to use GSM.
65
What is the benefit of polynomial approx over GSM?
It can find the estimated minimum with fewer function calls
66
What are the properties of a descent direction?
The descent direction must form an acute angle with the negative function gradient.
The dot product of the descent direction with the negative function gradient, if it exists, means there is a component of the descent direction that decreases the objective function.
67
What is the steepest descent direction?
A direction that provides the most rapid decrease in function evaluation within the small neighborhood of current point through the domain
68
What is the benefit of the steepest direction? What problems?
Steepest descent directions are perpendicular to previous dir, which is tangent to contour line.
- Inexact searches, approximately perpendicular
69
What is the Newton Direction Method?
Newton direction is search direction based on 2nd order Taylor Series expansion of the function.
- search direction pk = - H(x)^-1* grad(f), iteration xk = x+pk
- Assuming step length of 1 gives exact solution for min.
- For positive definite hessian, the search direction of max descent toward minimum
- Finds direction for function with quadratic convergence
70
When is Newton Search Direction not applicable?
- Hessian may not exist
- Hessian may not be positive definite. So it may not define descent direction
- Saddle point or maximum
71
Why/why not use Newton Search Direction method?
Most accurate, computationally expensive. For non +def hessian, need a hessian update to maintain sufficiently positive definite hessian approximation (to satisfy Wolfe/GSM/Backtracking)
72
What is a quasi-newton search direction?
- Quasi-Newton search direction is a Newton direction except with 1st order hessian approximation
- Define this by using Taylor Series expansion of the gradient
73
What are the secant condition and curvature conditions for quasi-newton methods?
-----
74
What is conjugacy?
A-orthogonality (linear independence)
75
What is linear independent vectors?
Defined vectors such that no linear combination of the any vector can be written to make another in the set
76
Zeroth order methods:
Powells Method:
Univariate Search:
77
First order methods:
Steepest Descent, Conjugate Gradient, Quasi-Newton Methods
78
What is the conjugate direction method?
modifies a steepest descent algorithm by enforcing conjugacy. The search direction is based on the gradient at the current point plus a scalar multiple of the previous search direction.
79
What is the univariate search?
Univariate search is a zeroth-order line search algorithm in which we systematically move along a different coordinate variable direction per iteration, determining '+' or '-' direction along the coordinate line is a descent direction.
80
When does univariate search converge well?
--
81
How could we form a univariate search of 1st order?
We can choose our next coordinate variable direction based on the derivative of each to see which direction will give the greatest improvement in our function value
82
What is Powell's method?
Powell's method is a modification of the univariate search based on conjugate directions. It takes min steps in each univariate, builds a conjugate, takes min step, and removes first unit in direction vectors. Steps in univariate direction, and build a new conjugate. When slope is within a tolerance, restart univariate directions again.
83
What are the steps of Powell's method?
--
84
What is the convergence of Powell's method?
In general, for an n-D quadratic function with a minimum. Powell's method will converge to the minimum after n conjugate directions have been formed, requiring n^2 line searches.
85
What are the drawbacks of steepest descent algorithms?
Steepest descent algorithms do not use information from previous iterations to form search directions
86
What is a convex set?
A convex set is defined as a dataset for which every point can be connected to another pt by a line, and ALL pts are inside the set
87
What is a globally convergent algorithm?
A globally convergent algorithm is to describe an algorithm that will converge to a global optimum from ANY starting pt for a convex optimization problem.
*convexity is the key b.c. local optimum IS global optimum
88
What is the difference between conjugate directions and Fletcher Reeves Conjugate Gradient?
Conjugate direction method uses linear independent searches to build a set of conjugate directions over whole space, producing 1-D linear searches. Which minimizes along coordinate directions based on gradient residual minimization.
Fletcher Reeves Conjugate Gradient converts to non-linear conjugates and performs line search to approximate hessian from previous steps and search directions
89
compare FRCG vs. BFGS update
FRCG uses '+' def H(x) to converge at most n iterations for quadratic functions, linearly.
BFGS uses quasi-newton hessian approximation to converge super-linearly
90
What are eigenvalues?
Eigenvalues are a directional transformation constant (stretch/squeeze), magnitude determines rate of gradient change over axis
91
What are eigenvectors?
Eigenvectors are prinipal directions of constant span, telling you direction of gradient changes
92
What does the combo of eigenvalue/vector tell you about the function, slope, and convexity?
all L > 0, + def H(x), convex, x* is minima
L > = 0 (one L = 0), + semi-def, either saddle, unbound, or not enough information
L<0, -def, concave, x* is maxima
L1>L2>0, dir V1 has higher rate of change over unit length, contours closer.
L1<0
L1>0 & and L2<0 = saddle point
93
What are constraint qualifications?
Constraint qualifications ensure constraint linearization is a good representation of the feasible set around x*.
94
When are constraint qualifications required?
Constraint qualifications are required to use KKT conditions in constrained optimization.
95
What are the two main types of constraint qualifications? explain
LICQ - linear independence constraint qual.
*Tells you that all constraint gradients are linearly independent
MFCQ - Mangasarian Fromovitz const. qual.
*Tells you all active constrains are bound, not necessarily unique or linearly independent.
96
What are the KKT conditions?
The KKT conditions are first order necessary conditions for constrained optimization using a lagrangian approximation of your function including inequality and equality constraints.
1. ∇f(x*)=-∇gi(x*)λi (collinearity, along minimizer)
2. gi(x*) <= 0 (x* is feasible, in feasible space)
3. λi*gi(x*) = 0, where λi>=0 (complementarity, g(x) = 0 when on active constraint, h(x) = 0 always)
97
What are direct methods of constrained optimization?
Sequential Linear Programming (SLP)
Method of Feasible Directions (MoFD)
Generalization Reduced Gradients (GRG)
Sequential Quadratic Programming (SQP)
98
What information about convexity and Min/Max points can be derived from Hessian?
For Hessian [fxx fyx; fxy fyy]:
a. if fxx > 0 and fyy < 0, det(fxx*fyy-fxy^2) < 0 we know saddle (x upward convexity, y downward concavity)
b. det(H) > 0, local inflection
- fxx>0, have minima
- fxx<0, have maxima
c. det(H) = 0, not enough information
- could either be saddle, or unbound from below/above
99
What is Method of Feasible Directions?
Constrained line search method, uses the concept of feasibility (∇f(xo)*p<= 0) and usability (∇g(xo)*p<=0) to maintain search directions inside the feasible design space . It moves away from or travels along the constraints.
100
What is the MoFD Process?
1. Find usable or feasible pt xo and set convergence conditions.
2. if in feasible region g<0 set steepest descent - ∇f(xo)
3. if any active constraints, solve direction method w/ pushoff or side constraints via LP methods.
4. if pushoff convergence small, check minimization.
5. Conduct unconstrained line search, w/ step length a*, evaluate constraint minimization at gi(xo+a*p)
6. If line terminates within interior of feasible region check convergence and constraint criteria KKT
7. update iteration, pushoff factors, and convergence criteria repeat.
101
How to do check if MoFD has reached the minimum or a constraint boundary?
Using KKT conditions.
102
What is Generalized Reduced Gradient Method?
The method of reducing dimensionality through total differentials of your objective and constraints to develop gradient w.r.t. dependent variables ∇f and general gradient of independent variables combined from equality and inequality constraints. Then through new linearized constraints, conducting line search methods using these two and updating linearization of gradients.
103
What method do we use if a constraint becomes inactive during move due to non-linearity in GRG method?
Step back with Newton's method for root finding.
104
What are advantages/disadvantages of GRG?
Advantages:
- Very efficient compared to sequential unconstrained minimization (indirect methods)
Disadvantages:
- spend most time recovering, lots of memory with increased slack variables and dimensionality.
105
What is Sequential Linear Programming?
Sequentially solving linear programming problems through linearization of your objective function and constraints to solve linear programming within side constraints, slowly marching to march toward constrained non-linear optimization problem.
106
What is the SLP process?
1. Linearize problem (objective and constraints) around baseline point in design space
2. Add side constraints/move limits around baseline point to prevent unbounded searching
3. Solve LP with any appropriate technique
4. set new baseline pt, repeat 1-3
107
What is sequential quadratic programming?
A quadratic approximation of your objective function and linearized constraints with taylor series 2nd order hessian or approx B (BFGS) to build your quadratic problem. Then building full set of constraints, converting any inequality with interior point or using active set methods to determine which inequality constraints are active. From here, get Lagrangian and use KKT conditions to solve equality constrained QP in 1-D searches (Direct or iteratively), update hessian/approx B, and repeat.
108
What are indirect constrained optimization methods?
Exterior penalty function
Interior penalty function
Augmented Lagrangian
109
What is the difference between direct and indirect constrained optimization methods?
Direct methods utilize the constraints directly to solve for approximate functions or direction find for minimization. Indirect methods build pseudo functions which penalize the optimization for violating constraints through unconstrained searches.
110
What is the exterior penalty function method?
Exterior penalty function method builds pseudo-objective function which penalizes the function, f(rp →∞), as your proceed exterior to the feasible region.
111
What are the advantages and disadvantages of exterior penalty function method?
Advantages:
- Simple to implement, can start interior/exterior to feasible region, allows for application of unconstrained optimization
Disadvantages:
- As rp →∞, the function becomes increasingly non-linear and causes difficulty line searching.
- The constrained optimum is approached from infeasible region, which means if iterations stop prematurely the result could be and infeasible design
112
What is the interior penalty function method?
The interior penalty function method begins inside of the feasible region and penalizes your function, f(rp* log(g) →0), as it nears the constraint boundary.
113
What are the advantages and disadvantages of interior penalty method?
Advantages:
- Starting from interior, so any premature stops will still result in feasible design.
- Can combine interior and exterior to address equality constraints
Disadvantages:
- only applies to inequality constraints (no interior for equality constraints)
- Slightly more complicated
- Pseudo Obj. function discontinuous at constraint boundaries, issues for line search methods.
114
Why do we scale constraints for indirect constrainded optimization?
1. Ensure curvature of pseudo-objective function is not dominated by single constraint with much steep gradients than other constraints
2. Make methods less sensitive to initial choices of rp (exterior)
and rp' (interior) penalties.
115
What does scaling the constraints mean for indirect constrained optimization do?
scaling constraints to the same order of magnitude as the gradient of the objective function.
116
What is the Augmented Lagrangian method?
The Augmented Lagrangian method attempts to build similar penalty on equality and inequality constraints while still being able to achieve a constrained optimal design for finite values of rp without requiring convergence of rp, rp', instead of requiring lagrange multiplier updates.
117
What are the advantages and disadvantages of Augmented Lagrangian?
Advantages:
- Insensitive to values of rp, not necessary for rp →∞.
- get precise active inequality and equality constraints
- accelerated convergence due to updating of lagrange multipliers
- start infeasible/feasible locations
- at optimum, when λi =0, will automatically identify active constraint
