In this video, I’ll talk about nonlinear convex

programming and how to use KKT optimality conditions to solve some convex programming

problems. I will limit our discussion to maximization

problems in this general form. If you have a minimization problem, you can

convert it to a maximization problem by maximizing the opposite of the objective function. We try to find the values of x1, x2, through

xn that maximize the objective function while satisfying all these m constraints. For this problem formulation, if the objective

function is nonlinear, or at least one of the constraints is nonlinear, then this problem

is called a nonlinear programming problem. Nonlinear programming problems are more commonly

seen in real life than linear programming problems. Also, nonlinear programming problems are in

general more difficult so solve than linear programming problems. Traditional operations research techniques

can only solve some special nonlinear programming problems. For example, if the objective function is

concave and all the constraints are convex, this problem is called a convex programming

problem. For a convex programming problem, a local

optimum is also a global optimum. KKT conditions can be used to determine the

optimality of a potential solution for convex programming problems. Sometimes, we can also use the KKT conditions

to find the optimal solutions. For a convex programming problem, (x1, x2,

…, xn) is an optimal solution if there exist m non-negative numbers u1, u2, …, um such

that all the following conditions are satisfied at the optimal point. These are called the KKT conditions. The first condition is an inequality constraint. It should be applied to all the n decision

variables, x1 through xn. The second condition is an equality constraint. It says either xj is equal to 0, or this part

should be equal to 0. This part is exactly the same as the left

hand side of the first condition. It should be applied to all the n decision

variables as well. The third condition is actually the constraint. We just moved the right hand side to the left. It should be applied to all the m constraints. The fourth condition is an equality constraint. It says either ui is equal to 0, or this part

is equal to 0. This part is exactly the same as the left

hand side of the third condition. It should be applied to all the m constraints

as well. The fifth condition is just the sign restriction

for xj. It should be applied to all the decision variables. The last condition is just the sign restriction

for ui. It should be applied to all the m variables

u1 through um. We’d better illustrate the KKT conditions

with an example. This is a maximization problem with two variables,

x1 and x2. The objective function is nonlinear, so it

is a nonlinear programming problem. We can use the techniques introduced in the

previous video titled Convex and Concave Functions to determine whether the objective function

and the constraint are convex or concave. It turns out the objective function is concave,

and the constraint is both convex and concave. So the problem is a convex programming problem. Now, let’s check the KKT conditions. We have two variables, so n=2. We have only one constraint, so m=1. When j=1, condition 1, the partial derivative

of f with respect to x1 minus u1 times the partial derivative of g with respect to x1. It leads to this inequality. Condition2: x1 time the left hand side of

the first condition is equal to 0. When j=2, condition 1, the partial derivative

of f with respect to x2 minus u1 times the partial derivative of g with respect to x2. It leads to this inequality. Condition 2: x2 time the left hand side of

this condition is equal to 0. Condition 3: We re-write the constraint by

moving the right hand side to the left. Condition 4: u1 times the left hand side of

condition 3 is equal to 0. Condition 5: The sign restrictions for x1

and x2. Condition 6: The sign restriction for u1. After we get all these KKT conditions, let’s

see if we can find the optimal solution. Using conditions 5 and 6, we can split the

problem into some subproblems. For example, x1 is greater than or equal to

0. We can split it into two cases. x1=0 and x1>0. We can do the same for x2 and u1. So, we will have a total of 8 combinations

or scenarios. Now, let’s try the first combination, x1,

x2, and x3 are all equal to 0. This condition will be changed to 1 is less

than or equal to 0, which is a contradiction. So this combination is not optimal. The second combination is x1 and x2 are equal

to 0, u1 is greater than 0. This condition will be changed to u1 is greater

than or equal to 1/2. This condition will be changed to 0 is equal

to 0. This condition will changed to u1 is greater

than or equal to 2. This condition will be changed to 0 is equal

to 0. This condition will be changed to -3 is less

than or equal to 0. This condition will be changed to -3 is equal

to 0. This is a contradiction! We’ll continue to check other combinations. Finally, we find that only combination 4 doesn’t

lead to a contradiction. It is x1 is equal to 0, x2 and u1 are greater

than 0. This condition will be changed to u1 is greater

than or equal to 1/2. This condition will be changed to 0 is equal

to 0. This condition will changed to u1 is greater

than or equal to 2. This condition will be changed to u1=2. This condition will be changed to x2 is less

than or equal to 3. This condition will be changed to x2 is equal

to 3. So, the optimal solution is x1 is equal to

0, x2 is equal to 3. Plug them back into the objective function. We will get z is equal to 6. Okay, that is about nonlinear convex programming

and KKT conditions. Thanks for watching.

Ultimate Blogger Theme By Buywptemplates

<3

thanks for making this topic so easy

Thank you! And a question. At 6:58, the (4) condition should lead to u_1 = 0, instead of -3 = 0?

Thank you. I got it.

Very clear

Thank you!

Cukup jelas. Barakallah ilmunya pak.

Hi Guys, please comment and let me know what you think about this Operations Research Open Course. Your feedback is really appreciated. If you enjoy the video, please subscribe and share. All my replies here are only related to the content in my own videos. I am afraid I won't be able to answer other questions. Thanks for your understanding.