Lagrangian method for a silmple linear programming

convex optimizationlagrange multiplierlinear programmingoptimization

I'm trying to solve a simple LP using Lagrangian method. But I don't know how to use the soloution of the dual problem to find the solution of the main LP.

I consider the following simple problem:
$$ \min_{x} \sum_{i=1}^n -f_ix_i $$
$$ \text{s.t.}\quad \sum_{i=0}^n x_i=1, x\ge 0 $$

The general form is:
$$ \min c^Tx $$
$$ \text{s.t.}\quad Ax=b, x\ge 0 $$

In my problem: $A=[1 \, 1\,1 \cdots \,1]$,
$c=-f=[-f_1\,-f_2\,\cdots\,-f_n]^T$ and $b=1$.

The dual problem will be:
$$\max \,-v$$
$$\text{s.t. }A^Tv-f\ge 0$$

The constraint means:
$$\forall i\le n, \, v\ge f_i\Rightarrow -v\le -f_i$$
$$\Rightarrow -v\le \min{-f_i} \Rightarrow \,-v= \min{-f_i}= -\max f_i\Rightarrow v=\max f_i$$

Therefore I've solved the dual problem. but what is the solution of the original problem? My question is:

In general how can I find the solution $x$ after solving the dual problem for $v$?

Best Answer

Complementary Slackness Principle tells us that either the inequality $i$ in $A^Tv_{opt}-f\ge 0$ becomes equality or $x_i=0$. Assuming all the numbers $f_i$ are distinct and $\nu_{opt}=\max f_i=f_k$. Then $\nu_{opt}>f_i$ for $i\ne k$, hence, $x_i=0$ for $i\ne k$. Clearly then $x_k=1$.

Related Solutions

Optimization – Correct Dual to Given Primal Linear Programming Problem

Maybe it's worthwhile to talk through where the dual comes from. This will take a while, but hopefully the dual won't seem so mysterious when we're done.

Suppose we want to use the primal's constraints as a way to find an upper bound on the optimal value of the primal. If we multiply the first constraint by $9$, the second constraint by $1$, and add them together, we get $9(2x_1 - x_2) + 1(x_1 +3 x_2)$ for the left-hand side and $9(1) + 1(9)$ for the right-hand side. Since the first constraint is an equality and the second is an inequality, this implies $$19x_1 - 6x_2 \leq 18.$$ But since $x_1 \geq 0$, it's also true that $5x_1 \leq 19x_1$, and so $$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$$ Therefore, $18$ is an upper-bound on the optimal value of the primal problem.

Surely we can do better than that, though. Instead of just guessing $9$ and $1$ as the multipliers, let's let them be variables. Thus we're looking for multipliers $y_1$ and $y_2$ to force $$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$

Now, in order for this pair of inequalities to hold, what has to be true about $y_1$ and $y_2$? Let's take the two inequalities one at a time.

The first inequality: $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

We have to track the coefficients of the $x_1$ and $x_2$ variables separately. First, we need the total $x_1$ coefficient on the right-hand side to be at least $5$. Getting exactly $5$ would be great, but since $x_1 \geq 0$, anything larger than $5$ would also satisfy the inequality for $x_1$. Mathematically speaking, this means that we need $2y_1 + y_2 \geq 5$.

On the other hand, to ensure the inequality for the $x_2$ variable we need the total $x_2$ coefficient on the right-hand side to be exactly $-6$. Since $x_2$ could be positive, we can't go lower than $-6$, and since $x_2$ could be negative, we can't go higher than $-6$ (as the negative value for $x_2$ would flip the direction of the inequality). So for the first inequality to work for the $x_2$ variable, we've got to have $-y_1 + 3y_2 = -6$.

The second inequality: $y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

Here we have to track the $y_1$ and $y_2$ variables separately. The $y_1$ variables come from the first constraint, which is an equality constraint. It doesn't matter if $y_1$ is positive or negative, the equality constraint still holds. Thus $y_1$ is unrestricted in sign. However, the $y_2$ variable comes from the second constraint, which is a less-than-or-equal to constraint. If we were to multiply the second constraint by a negative number that would flip its direction and change it to a greater-than-or-equal constraint. To keep with our goal of upper-bounding the primal objective, we can't let that happen. So the $y_2$ variable can't be negative. Thus we must have $y_2 \geq 0$.

Finally, we want to make the right-hand side of the second inequality as small as possible, as we want the tightest upper-bound possible on the primal objective. So we want to minimize $y_1 + 9y_2$.

Putting all of these restrictions on $y_1$ and $y_2$ together we find that the problem of using the primal's constraints to find the best upper-bound on the optimal primal objective entails solving the following linear program:

$$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$$

And that's the dual.

It's probably worth summarizing the implications of this argument for all possible forms of the primal and dual. The following table is taken from p. 214 of Introduction to Operations Research, 8th edition, by Hillier and Lieberman. They refer to this as the SOB method, where SOB stands for Sensible, Odd, or Bizarre, depending on how likely one would find that particular constraint or variable restriction in a maximization or minimization problem.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint

Minimize or Maximize Lagrangian

First, setting the stage: typically $f$ is assumed to be convex, $l_i$ is assumed to be convex, and $h_j$ is assumed to be affine. If you do not assume this, then (P2) will be hard to solve but will still exist nevertheless. Now to the specific points,

Yes, it does. $L(x, \alpha, \lambda)$ is convex in $x$ and concave in $(\alpha, \lambda)$. That $L(\cdot, \alpha, \lambda)$ is convex follows directly by the convexity of $f$, $h_i$, and $l_i$ for all $i$. Let's make this clear: fix $a \in \mathbb{R}^m$ and $b \in \mathbb{R}^p$ and define $r(x) = L(x, a, b)$, let $x \in \mathbb{R}^d$ and $t \in [0,1]$, then \begin{align} r(tx + (1-t)y) &= f(tx + (1-t)y) + \sum_{i=1}^{m} \alpha_i l_i (tx + (1-t)y) + \sum_{j=1}^{p} \lambda_j h_j (tx + (1-t)y) \end{align} By the convexity of $f$, we have $$f(tx + (1-t)y) \leq t f(x) + (1-t) f(y)$$ Similarly, by the convexity of $l_i$ we have $$ l_i (tx + (1-t)y) \leq t l_i (x) + (1-t) l_i (y)$$ and since $\alpha_i$ is assumed positive multiplying by it does not change this inequality. Finally, since $h_j$ is affine, then we have equality $$\lambda_j h_j (tx + (1-t)y) = t \lambda_j h_j (x) + (1-t) \lambda_j h_j (y)$$ Combining the last three equations we can easily see that $$ r(tx + (1-t)y) \leq t r(x) + (1-t) r(y). $$ Hence, $L(\cdot, a, b)$ is convex. Similarly, if you fix $x$, then $L(x, \xi)$ is affine in $\xi$, and is therefore both convex and concave (as all affine functions are).
The definition of the dual function $g(\alpha, \lambda)$ minimizes $L(x, \alpha, \lambda)$ over $x$, and this is convex minimization since as shown, $L$ is convex in $x$. Therefore, this minimization is well-defined.
Optimizing (P1) is a different problem from the problems (P2) and (P3). These problems are generally not equivalent, but under certain conditions (such as Slater's condition) they are. In which case you can either try to solve the primal problem directly (optimize (P1) by using some form of projected gradient descent, for example) or solve the dual problem by trying to solve (P3) and in the process solve (P2), possibly multiple times. The dual optimization problem is this $$ \max_{\alpha, \lambda} \min_{x} L(x, \alpha, \lambda). $$ If you assume access to $g(\alpha, \lambda) = \min_{x} L(x, \alpha, \lambda)$ then this is a concave maximization problem, since $g(\alpha, \lambda)$ is concave as it is a minimum of affine functions regardless of the convexity of $L(\cdot, \alpha, \lambda)$. Of course, if $L(\cdot, \alpha, \lambda)$ is not convex then it will be hard to obtain the value of $g(\alpha, \beta)$ for any $\alpha, \beta$, and the dual problem may be hard.
No.
I assume you meant $h_i$ linear and $l_j$ nonlinear but convex, because $h_i$ must be linear in this formulation. In which case, you will try to solve (P3) which will require solving (P2) possibly many times for different values of $(\alpha, \beta)$. Since $f$ is non-convex, Solving (P2) cannot generally be done and you must exploit the problem structure in some way. If you can find a closed form solution for P2 in terms of $(\alpha, \beta)$ then you would use it to solve P3.

I hope this answers your questions.

Best Answer

Related Solutions

Optimization – Correct Dual to Given Primal Linear Programming Problem

Minimize or Maximize Lagrangian

Related Question