# Tag Info

6

No, the solutions are not the same. On p. 499, the book is merely presenting an example of a self-concordant function. When you ask about algorithm complexity for problem (1), which algorithm do you have in mind? At this point in the book's development, it is not clear how to solve problem (1) efficiently. The book will present a strategy that utilizes log-...

5

This can be done by iterating the simplex method. (Or your favorite method for solving linear programs.) We want to know if the polytope $P = \{\mathbf x : A\mathbf x \ge \mathbf 0\}$ has an interior point. To do this, we will try to find $n+1$ affinely independent points in $P$, then average them. Let $\mathbf x^0 = \mathbf 0$. This will be the first of ...

5

You can add a constraint $$x_4^+ - x_4^- = -13 - 12 x_1 + 5 x_2 - 7 x_3$$ ($x_4^+, x_4^- \geq 0$) and change objective to $$\min \quad 2 x_1 - x_2 + x_3 + x_4^+ + x_4^-$$

5

No. Why would developers work on all these MIP solvers if there is an easy LP formulation? We can write $x (1-x)=0$. But that does not really help. This is non-linear (quadratic) and non-convex, and you would need a global NLP solver (which often use Branch-and-bound). Of course, using some Lagrange multiplier technique as suggested elsewhere, is ...

4

An $L_{1}$ maximization problem can have multiple isolated local maximum solutions but that can never happen in an LP. Thus, in general, you can't construct an equivalent (having the same set of local maximum points) LP. Yes, it's possible in some trivial cases, but not in general. For example, consider $\max | x |$ $-1 \leq x \leq 2$ Here, the ...

4

Yes, it is a typo. You have written down the constraint correctly, they can be read off as the coefficient of $x_3$ in the maximization problem.

4

$$\max c^Tx$$ subject to $$Ax\le b$$ $$x \ge 0$$ Using the simplex algorithm, we can determine if there is a solution, $x^*$. Now consider $$\max e^Tx$$ subject to $$Ax\le b$$ $$c^Tx=c^Tx^*$$ $$x \ge 0$$ where $e$ is the all-one vector. We check if the solution is unbounded, if it is unbounded, then $M$ is unbounded.

4

Let's write down our simplex table, remembering our upper bounds for each variables. \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}\hline & x_1 & x_2 & x_3 & x_4 & x_5 & s & -z & RHS & \text{ratio} &UB \\ \hline -z & -2 & -4 & \color{blue}{-7} & -1 & -5 & 0 &...

4

One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as: $$-x_t + x_{t+1} - x_{t+2} \le 0$$ and $$-x_t + x_{t+1} + x_{t+2} - x_{t+3} \le 1$$ A little bit of thought is needed to decide what to do at the borders, especially the first time period. A different approach is detailed here.

4

The ineqaulity $a\ge b$ is tight iff $a=b$. In optimization context it is often called an active constraint. $x_2$ has to stop at $x_2=3$ because looking at the third constraint we get for $x_1=0$ (at the origin, unchanged) and $x_2=3$ (as increased from zero) $$-x_1+x_2=0+3=3\le3.$$ Hence, equality again (=tight), and the interesting things can happen. ...

4

Each of the horses has a certain return when they win, A is a $6\times$ return, B is $5\times$, C $4\times$, and D $3\times$. In general say you have a set of horses $H_i$ that each have a return $r_i$, and you bet some total amount $B$ with $B_i$ on each horse $H_i$. As long as $B_i \ge \frac{B}{r_i}$ for all $i$, you will not lose money. That is because ...

4

\begin{align}\|cx-y\|_1&= |y_0|+\sum_{i=1}^n|ci-y_i|\\ &=|y_0|+ \sum_{i=1}^n i|c-\frac{y_i}i|\end{align} Note that $|y_0|$ doesn't have an influence on the choice of $c$. Let $v$ be the sorted vector that consist of $i$ copies of $\frac{y_i}{i}$ (possibly with duplicity), where $1 \le i \le n$. Then $c$ can be chosen to be the median of the vector ... 4 The best possible (I believe) is by Cohen, Lee, and Song: https://arxiv.org/abs/1810.07896 Hope this helps. 4 In general, it is not true that the relaxed version gives the convex hull: $$ch(\{x \in \{0,1\}^n \mid Ax \leq b\}) \neq \{x \in [0,1]^n \mid Ax \leq b\}.$$ But if we did know the convex hull, then the integer program would reduce to a linear program. A simple example is given by the set $$X = \{ (x_1,x_2) \in \{0,1\}^2 \mid x_1 + x_2 \leq \frac{1}{2}\} = \... 4 Unfortunately, no. There is really nothing else you can say other than that the optimal solution is between the two bounds. Presumably you could estimate these probabilities experimentally, but I assume that is not what you’re asking. 4 Since \Vert x\Vert_1\leq1, this means \sum_j\vert x_j\vert\leq 1. Now let x_0=-\mathrm{sign}(c_{i})e_i as in your question. For an arbitrary x we then have:$$ |c^Tx|=\left\vert\sum_{j} c_j x_j\right\vert\leq\sum_j|c_j||x_j|\leq|c_i|\sum_j|x_j|=|c_i|\Vert x\Vert_1\leq|c_i| $$Because c^Tx_0=-|c_i|, we have that this is indeed the best possible. 3 If f(x)=30,000 + 575x - 5x^2 was your output function, then it is correctly maximized at x=57.5. Since a quadratic is symmetric about its maximum, f(57)=f(58), and either 57 or 58 papaya trees will maximize production. However, as Paul notes in the comments, your output function has an error. It ought to be$$f(x)=(50+x)(600-5x) = 30,000 + \color{... 3 To make an example, take any linear programming problem with nontrivial feasible region and make an extra copy of each of the constraints. 3 \begin{align}\frac{\partial f}{\partial x}=-2x+3x^2+2xy\qquad (1)\end{align} \begin{align}\frac{\partial f}{\partial y}=2y+x^2+y^2\qquad (2)\end{align} At \begin{align}\frac{\partial f}{\partial x}=\frac{\partial f}{\partial y}=0\end{align} we have (1) implies \begin{align}x(3x+2y-2)=0\end{align} So there are two casesx=0$or ... continue from there. 3 I see that you have specified that$A x_0 \geq 0$and$x_0 \in \{0,1\}^n$. Then the "simplest" cut is the so-called "no-good" cut, which just forces one of the components to change: $$\sum_{j : (x_0)_j = 0} x_j + \sum_{j : (x_0)_j = 1} (1-x_j) \geq 1.$$ This will definitely cut off the corner of the hypercube$x_0$. (And only that corner of the hypercube).... 3 Linear Programming as such is in P because there are other algorithms which can solve Linear Programs (LPs) in polynomial time, for example interior points methods. The simplex, however, has an exponential running time for worst-case examples (such as the Klee-Minty-cube). Since other algorithms exist which can always solve an LP in polynomial time, LPs are ... 3 My interpretation is that the question is: How can I assure that the linear inequality$q_{ij}-q_{il}-q_{kj}+q_{kl} \geq 0$holds when$q_{ij} \geq q_{kl}$. This is an implication betweeen linear inequalities $$q_{ij} \geq q_{kl} \Rightarrow q_{ij}-q_{il}-q_{kj}+q_{kl} \geq 0$$ Unfortunately not LP-representable. However, it can be modelled using ... 3 The second constraint is linear. Let's look closer to the first constraint.$(0,1,1)$is in$C$,$(0,-1, 1)$is in$C$. Consider$\frac12(0,1,1)+\frac12(0,-1,1)=(0,0,1)$and it is not in$C$. Hence it can't be convex. 3 The dual is $$\max_y \sum_{i=1}^n i y_i$$ subject to $$y_i \ge 0$$ $$\sum_{i=j}^n y_i = j, \forall j \in \{1,\ldots, n\}$$ In particular, for$n>1$, we have $$y_1 +\ldots + y_n =1$$ and $$y_2 +\ldots + y_n =2$$ which implies that$y_1=-1<0$which shows that the dual is infeasible. We can check that the primal is feasible and hence it is ... 3 Suppose on the contrary that such$u \ne 0$exists for point$B$, then $$5(1.4+ \epsilon u_1)-2(0 +\epsilon u_2) \le 7\tag{1}$$ $$5(1.4- \epsilon u_1)-2(0 -\epsilon u_2) \le 7\tag{2}$$ $$\epsilon u_2 \ge 0\tag{3}$$ $$-\epsilon u_2 \ge 0\tag{4}$$ From$(3)$and$(4)$, we conclude that$u_2=0.\$ Hence now, we have $$7+5\epsilon u_1 \le 7 \iff \epsilon u_1 \... 3 Now I am not sure how to add the condition 5\% and 8\% lost during the refining process. prubin has already provided a nice answer, but it seems that you don't get what he says. See the table. For light crude oil, add the numbers and you'll get 0.4+0.2+0.35=0.95 which equals 1-0.05. For heavy crude oil, the sum of the numbers is 0.32+0.4+0.2=... 3 Given a maximization problem of the form in definition 1. Let us try to convert it into a maximization problem in the second form, and check the duality form definition 2 is the same as duality in definition 1. We let A_1=A, b_1=b, A_2=0, b_2 be any nonnegative vector, then the dual accoding to Definition 2 is$$\min\left\{\left \langle \...

3

You're almost there, but there's a minus sign missing on the RHS of the dual constraints. As David M. points out, the dual of a max LPP should be a min LPP. It can be observed that you've replaced the dual variables in \begin{align} \max 10 y_1 + 21 y_2 & \\ \begin{bmatrix} 1 & 2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} y_1 \\y_2 \end{bmatrix} &...

3

"The 1250 is not just the value of z. The value of 1250 is the sum of all of those parameters. Yet we assign 1250 to z by the simple expedient of declaring the other variables to be zero. What is the justification for that?" You are correct. But for a linear program, you know that the optimal solution is at an extreme point. Extreme points are defined by ...

3

The dual of the dual is the primal. Therefore, if the dual has a finite optimal solution, strong duality tells us that the dual of the dual (hence the primal) also has a finite optimal solution, and the two are equal.

Only top voted, non community-wiki answers of a minimum length are eligible