Constrained Optimization

Question 1

What are two types of constraints ?

Answer 1

inequality 
gi(x) ≤ 0 for i ∈ {1,2,...,l} 

equality
hj(x) = 0 for j ∈ {1,2,...,m}

Question 2

what is the feasible region of the constraint problem ?

Answer 2

Ω = {x ∈ Rn | gi (x) ≤ 0 for i = 1, 2, . . . , l and hj(x) = 0 for j = 1,2,…,m}

Question 3

What is the active set of constraint problems ?

Answer 3

A(x) = {i ∈ {1,2,…,l}|gi(x) = 0}

Question 4

what are the consequences of adding constraints to optimization problem ?

Answer 4

• constraints may render local minima of the objective infeasible
• introduce new local minima
• boundary of the feasible region may be non-smooth even if all constraint functions are smooth

Question 5

What are the methods that will help nonlinear constraint problems?

Answer 5

• penalty
• augmented Lagrangian methods
• sequential quadratic programming
• interior point algorithms

Question 6

What is the active-set methods based on ?

Answer 6

based on the premise that equality-constrained problems are easier to solve than those that (also) contain inequality constraints

Question 7

Reduced search space in active-set ?

Answer 7

active-set methods maintain a working set

-all constraints in the working set are enforced as equalities as the reduced search space in the subspace of the feasible region

Question 8

what are the taxonomy of constraints ?

Answer 8

• quantifiable vs. non-quantifiable
• relaxable vs. un-relaxable
• a-priori vs. simulation-based -known vs. hidden

Question 9

Explain what is quantifiable(Q) vs. non-quantifiable(N) ?

Answer 9

• quantifiable constraint is a constraint that the degree of feasibility and/or violation can be quantified.
• A non-quantifiable constraint is one for which the degrees of satisfying or violating the constraint are both unavailable.

Question 10

Explain what is Relaxable(R) vs un-relaxable(U) ?

Answer 10

• A relaxable constraint does not need to be satisfied in order to obtain meaningful outputs
• An un-relaxable constraint must be satisfied for meaningful outputs to be obtained.

Question 11

Explain A Priori (A) versus simulation-based(S)

Answer 11

• An a priori constraint is that the feasibility can be confirmed without running a simulation.
• A simulation-based constraint (or simulation constraint) requires running a simulation to verify feasibility.

Question 12

Explain Known (K) versus hidden (H) ?

Answer 12

-A known constraint is that the constraints are given.

-A hidden constraint is not explicitly known to
the solver.

Question 13

What we focus on the case of taxonomy of constraints ?

Answer 13

QUPK

Question 14

Explain Active-Set (1 + 1)-ES ?

Answer 14

• inequality constraint turns active when it is active at a successful candidate solution
• allow constraints to turn inactive, suspend the use of the active set with a probability of 0.2
• step size is adapted only in those iterations where the use of the active set is not suspended

Question 15

What is Lagrange Functions ?

Answer 15

to minimize a function f subject to an equality constraint h(x) = 0

L(x; λ) = f (x) + λh(x)
L(x; λ) = f (x) + λg (x)

λ is the Lagrange multiplier

Question 16

KKT conditions

Answer 16

• Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints.
• KKT conditions are first derivative tests (sometimes called first-order) necessary conditions provided that some regularity conditions are satisfied.

Question 17

Explain Quadratic Penalty Method ?

Answer 17

• it use a quadratic penalty function and μ > 0 is referred to as the penalty parameter
• get at an optimizer of the constrained problem
• by iteratively optimizing the quadratic penalty function with an increasing sequence of penalty parameter values

Question 18

Advantage of l_1 penalty method vs quadratic penalty method ?

Answer 18

-the l1 penalty method avoids the ill-conditioning issue of the
quadratic penalty method
- quadratic penalty is inexact suffer ill-conditioning
-l1 penalty is exact.

Question 19

What is Augmented Lagrangian Methods ?

Answer 19

-augmented Lagrangian approaches incorporate Lagrange multiplier estimates to avoid the ill-conditioning issues of quadratic penalty methods while preserving smoothness of the objective