Pietro Belotti » IE426 F.A.Q. - Dept. of Industrial & Systems Engineering, Lehigh University

IE426 F.A.Q.

These are questions asked by students during or at the end of a class. I will record them here if I think they are useful for everyone. If you have a question, feel free to email it to me.

Lecture 2: convexity, relaxation, lower/upper bound;
Lecture 4: Linear Programming, AMPL;
Lecture 10: Pre-quiz;
Lecture 14: Integer Programming;
Lecture 15: Branch and Bound;

Lecture 2 – September 1, 2009

Q.: Why is the function $f(r,h)=r\cdot h$ nonconvex?
A.: We can prove it by applying the definition: a function $f(x)$ on a vector $x\in \mathbb R^n$ is convex if, for any two points $x'\in \mathbb R^n, x'' \in \mathbb R^n$ and for any $\alpha \in [0,1]$ , we have

$f(\alpha x' + (1-\alpha)x'')\le \alpha f(x') + (1-\alpha)f(x'')$ .

Now take the two points $x'=\left(\begin{array}{c}0\\1\end{array}\right)$ and $x''=\left(\begin{array}{c}1\\0\end{array}\right)$ , and $\alpha=0.5$ . We have

$f(\alpha x' + (1-\alpha)x'') = f\left(\frac{1}{2} \left(\begin{array}{c}0\\1\end{array}\right) + (1-\frac{1}{2})\left(\begin{array}{c}1\\0\end{array}\right)\right) = f\left(\begin{array}{c}\frac{1}{2}\\ \frac{1}{2}\end{array}\right) =\frac{1}{4}$ , and this is strictly greater ( $>$ ) than $\frac{1}{2} \cdot 0 + (1-\frac{1}{2})\cdot 0 = \alpha f(x') + (1-\alpha)f(x'') = 0$ .

Q.: How does the function $f(x_1,x_2)=x_1\cdot x_2$ look like?
A.: It looks like a saddle:

$Graph of the function <img src='http://s.wordpress.com/latex.php?latex=f%28x_1%2Cx_2%29%3Dx_1%5Ccdot%20x_2&bg=ffffff&fg=000000&s=0' alt='f(x_1,x_2)=x_1\cdot x_2' title='f(x_1,x_2)=x_1\cdot x_2' class='latex' />$

Q.: What is a relaxation good for? When solving a relaxation to optimality, the solution might not be feasible for the original problem.
A.: That is true. The feasible set $F$ of the original problem $P$ is contained or equal to the feasible set $F'$ of a relaxation $P'$ , therefore the global optimum of the relaxation $P'$ might be in $F'\setminus F$ and hence infeasible for $P$ . However, it is very useful in that it provides a lower bound on the global optimum of $P$ .

Q.: Why is the constraint $\pi r^2h = V$ non-convex, and why is $\pi r^2h \ge V$ , or equivalently, $h \ge \frac{V}{\pi r^2}$ convex instead?
A.: One clarification first: we are considering non-negative values of $r$ and $h$ only. Assuming that, the set $S= \{(r,h)\in \mathbb R_+^2: r^2h = V\}$ is a curve on the Cartesian plane:

Here we have a segment between two points $x'$ and $x''$ , all of whose points are not in the set, that is, for none of the points in between do we have $\pi r^2h = V$ .

The inequality constraint is something else. Here we have that a portion of the Cartesian plane $S'= \{(r,h)\in \mathbb R_+^2: r^2h \ge V\}$ that includes not only the line $S= \{(r,h)\in \mathbb R_+^2: r^2h = V\}$ , but all points above this line (the shaded area):

Therefore, for any two points in $S'$ , all points in between also belong to $S'$ . The convexity of $S'$ can be shown by convexity of the function $f(r,h) = \frac{V}{\pi r^2} - h$ , obtained by its Hessian, $H(f) = \left(\begin{array}{cc}\frac{6V}{\pi r^4} & 0\\ 0 & 0\end{array}\right)$ , which is positive semidefinite for any $r\ge 0$ .

Q.: Why don’t we prove that the set $S=\{x\in \mathbb R^n: a^\top x = b\}$ convex by using the definition?
A.: Sure. We want to prove that, for any two points $x'\in S$ and $x''\in S$ and for any $\alpha\in [0,1]$ , we have $\alpha x' + (1-\alpha)x'' \in S$ . For this particular case, if $a^\top x' = b$ and $a^\top x''=b$ then $a^\top (\alpha x' + (1-\alpha)x'') = \alpha a^\top x' + (1-\alpha) a^\top x'' = \alpha b + (1-\alpha)b = b$ , which proves our assertion.

Q.: If $g(x)$ is a convex function, is the constraint $g(x)=b$ nonconvex?
A.: If $g(x)$ is linear, then $g(x)=b$ is convex. If $g(x)$ is just convex, the set of points such that $g(x)=b$ might be nonconvex because of the definition of a convex function:

$g(\alpha x' + (1-\alpha)x'')\le \alpha g(x') + (1-\alpha)g(x'')$

means that there might be a point between $x'$ and $x''$ such that the above inequality holds strictly, that is, such that

$g(\alpha x' + (1-\alpha)x'') < \alpha g(x') + (1-\alpha)g(x'') = b$

and therefore the set of points satisfying $g(x)=b$ is nonconvex.

Lecture 4 – September 9, 2009

Q.: There are five variables in the two-year
project selection problem, one for each opportunity. Why aren’t there ten of them (five for each year)?

A.: Because that’s what the input said: “We have 5 investment opportunities over a 2-year term,” i.e., we’ll invest in the same funds this and next year. If we could change our mind in the second year, we’d have different variables, say $y_i\in [0,1]$ , for the second year. The model would then change: from
$\min \{\sum_{i=1}^5 v_i x_i: \sum_{i=1}^5 a_i x_i \le 40; \sum_{i=1}^5 b_i x_i \le 20; x_i\in [0,1]\}$
to
$\min \{\sum_{i=1}^5 (v'_i x_i + v''_i y_i): \sum_{i=1}^5 a_i x_i \le 40; \sum_{i=1}^5 b_i y_i \le 20; x_i\in [0,1], y_i\in [0,1]\}$
where we changed the NPV given that $v_i$ is the NPV over the two years, while $v'_i$ and $v''_i$ are computed each on a one-year period (question for the Analytical Finance people: is $v'_i=v''_i=\frac{v_i}{2}$ ?)

Q.: What is meaning of the default keyword in AMPL?

A.: It is the initial value of a variable we, the modelers, are suggesting. It is totally irrelevant in the modeling part, but it can make a difference in the actual solving part. The solver, which we will use to look for a solution, may or may not take that value into account, as there are solvers whose result depends on the initial value of the variables. If we take a solver for convex optimization, such as Minos, included in the AMPL student edition, and apply it to a non-convex nonlinear problem, we may find a local optimum. This local optimum, in general, depends on the initial value we give the solver.

Q.: How do we check for convexity of a general function $f(x)$ in $n$ variables?
A.: By looking at its Hessian, i.e., the $n\times n$ matrix $H_f(x) = \left(\begin{array}{cccc}\frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \ldots & \frac{\partial^2 f}{\partial x_1\partial x_n} \\ \frac{\partial^2 f}{\partial x_2 x_1} & \frac{\partial^2 f}{\partial x_2^2} & \ldots & \frac{\partial^2 f}{\partial x_2\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n\partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \ldots & \frac{\partial^2 f}{\partial x_n^2} \end{array}\right)$

If the Hessian is Positive Semidefinite (PSD) over a certain set of points $S\subseteq \mathbb R^n$ , then $f$ is convex over $S$ .

For instance, the Hessian of a quadratic function $f(x,y) = a x^2 + b xy + c y^2$ is $\left(\begin{array}{cc}2a & b \\ b & 2c\end{array}\right)$ , which is constant. Therefore, a quadratic function is either convex for all $x\in \mathbb R^n$ or nowhere. For this two-variable example, $H_f$ is PSD if and only if $a\ge 0$ and $4ac - b^2\ge 0$ .

Lecture 10 – October 1, 2009

Q.: Is a problem $P$ a relaxation of itself?

A.: Yes. Remember the two conditions for $R$ to be a relaxation of $P$ . There is a $\le$ on the objective function and a non-strict containment ( $\subseteq$ ) for the feasible set, therefore a problem $R$ with the same objective function as $P$ and the same feasible set as $P$ is a relaxation of $P$ .

Q.: Is the global optimum of $P$ both its upper and lower bound?

A: Yes. It is a feasible solution of $P$ , so it is an upper bound. It is a global optimum of a relaxation of $P$ , so it is a lower bound too.

Q.: In order to qualify for a convex problem, must each of the constraint be convex? Or must all constraints combine to define a convex feasible set?

A.: The second rule (convexity of the feasible set) is necessary for convexity of a problem, the other condition being convexity of the objective function. Convexity of the feasible set is implied by the first rule (all constraints are convex), which however is only a *sufficient* condition for convexity of the feasible region.

Q.: Must the objective function be convex in just the feasible set of variables? (Need not to be convex outside of the feasible set?)

A.: Yes.

Q.: What do you mean by the bounded and unbounded problem? Is it related to the feasible set?

A.: A bounded optimization problem is one that admits a global optimum whose value is finite. In an unbounded problem, there is no global optimum with finite value (although there might be many feasible solutions with finite value). It is related to both the feasible set and the objective function.

For example, a problem of the form $\min \{2x: x\ge 1\}$ has an unbounded feasible set, but is bounded: its global optimum is $x=1$ and has value of 2.

A problem of the form $\min \{2x: x \le 1\}$ has an unbounded feasible set, and is unbounded: there is no global optimum with finite value, as any $k \ge 1$ , therefore any large negative number $K \ll 0$ , is feasible and has a value of $2K \ll 0$ .

Q.: I don’t understand the notations you used to define the neighborhood of x (the local optima). Does it mean the square of the absolute value? (lecture 2)

$||x-y||_2$ is the Euclidean distance between $x$ and $y$ , two $n$ -vectors: it is defined as

$\sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + \ldots + (x_n - y_n)^2}$ .

Q.: As your lectures don’t cover all the details in the reading materials, will those uncovered details be in the quiz?

A.: Some references in the lectures are to simple examples in the books. What I extracted from the textbook was sufficient for the lecture.

Q.: I thought by looking at the given objective function and the form of the constraints, I could determine if the problem is convex. Then I came across more examples which required that the feasible solution(s) be found and then, based on these, and “re-examining” the objective function and constraints with the feasible solutions, the problem was described as convex or not. So, the question is, do you have to do the second step of considering the feasible solution set, or not?

A.: No. These were just very special cases. With real-world problem, most of the times if there is one nonconvex constraint (or the objective is nonconvex) then the problem is nonconvex.

Q.: When the objective function and all other constraints are linear, but one constraint is restricting a variable to be integer, does the restriction of a variable to be integer still make the overall problem linear?

A.: It makes the problem Integer Linear, or better, Mixed Integer Linear as some variables are continuous and other are integer. Integer Linear Programming (or Integer Programming, IP for short) or Mixed Integer Linear Programming (MILP) problems are not Linear Programming (LP) problems. They are far more difficult than LP.

Q.: This integer restriction generally makes the problem non-convex, correct? (although there is an example where, because there was only one feasible solution (0,0), the problem was still called convex).

A.: Correct. Apart from special cases (which don’t occur very often in practice), ILPs and MILPs are nonconvex..

Lecture 15 – October 22, 2009

Q.: If the solution to the linear relaxation of an IP problem might be far from the actual optimal solution of the IP, why is it used in Branch-and-bound?

A.: For several reasons. First, it gives a lower bound on the original problem, which is necessary in branch-and-bound. Second, when partitioning the problem into two new subproblems (the branching step) one should make sure that the solution to the current relaxation is eliminated by branching, so that none of the two new subproblems admit it as a solution to the relaxation.

Lecture 15 – October 22, 2009

Q.: In the branch-and-bound algorithm, when the solution $x^{LP}$ of the LP relaxation is fractional, we choose for branching a variable $x_i$ whose value is fractional, $x_i^{LP}\notin \mathbb Z$ . What variable should be chosen?

A.: This question does not admit a simple answer. Given that the number of branch-and-bound (B&B) nodes generated affects the CPU time taken to solve an IP, it is usually desirable to have a strategy that minimizes the number of BB nodes, including choosing the proper variable at each node.

There are is a large body of scientific work on the subject, but to the interested reader I’d suggest to look at methods such as Strong Branching and Pseudocost Branching (for a quick introduction, see Prof. Linderoth’s slides for course IE418), and a “combination” of the two, called Reliability Branching (this is a journal article published on Operations Research Letters).