New answers tagged

1 vote

If there's an optimal solution for a LP, does it have to be at one of the vertices?

Not exactly. The result you found says that if there is an optimal solution then there is an optimal solution at a corner. There could also be optimal solutions that occur at non-corners. For a ...
user avatar
  • 3,705
0 votes

Optimal basic feasible solution in which reduced cost vector has a negative component

It can easily be seen that $\bar{c} \in \mathbb R$ where $\mathbb R = \{\mathbb R_-,0,\mathbb R_+\}$. For any set $S \subset \mathbb N$ let define notation $c_S$ such that vector $c_S$ contains ...
user avatar
1 vote

demonstrating convexity of set defined by quadratic inequality

Consider the epigraph of $f$ which is the set {$(x,a):a\geq\,f(x)$} The function clearly has a minimum because $\bigtriangledown f(x)=0$ gives: $Ax+a=0$ and since $A$ is positive definite, hence ...
user avatar
2 votes
Accepted

Decision variable limit condition in constrained linear and quadratic programing

The objective function is irrelevant to your question, as your interest is a box feasible region of $x$. In the case that $x$ is an univariable, you can solve the following two linear program: $$ \...
user avatar
0 votes

Model a LP problem which depends on a previously unknown value.

If $x_i$ is a binary variable that indicates whether bond $i$ is selected, the cardinality constraint is $\sum_{i=1}^n x_i \le 7$. Note that you don’t need to enforce $0\le \sum_i$ because that is ...
user avatar
  • 34.8k
0 votes

Linear constraint expressing the sum of the $k$ largest elements

Let binary decision variable $y_i$ indicate whether $x_i$ is among the largest $k$. Let continuous decision variable $z_i\in[0,1]$ represent the product $x_i y_i$. Let $w$ represent the $k$th ...
user avatar
  • 34.8k
2 votes

Find the canonical set of constraints that define the Polyhedron

You need to find equations for the five planes that contain the polyhedron's five faces. Three of the planes are obvious: $x=0$ for BDFO, $y=0$ for BCEO, and $z=0$ for EFO. Now let's find the equation ...
user avatar
1 vote

How to derive the dual of a conic programming problem, $\min_{x\in L}\{c^T x: \,\, Ax-b\in K\}$?

We can make use of Fenchel's Duality scheme, defining: $P(x)=c^{T}x$ and $Q(Ax)=0$ if $Ax\,\in\,K+b,\,\,$ $-\infty\,\,$ otherwise. So the function $Q(Ax)=-\delta_{K+b}(Ax)$ where $\delta$ is the ...
user avatar
2 votes

How to derive the dual of a conic programming problem, $\min_{x\in L}\{c^T x: \,\, Ax-b\in K\}$?

EDIT: Oops, didn't see that you had $x\in L$ in the question. I only answered for $L=\mathbb{R}^n$. Below, I give a Lagrangian approach for $L$ a closed, convex cone. I will outline an approach of ...
user avatar
  • 2,400
0 votes

Solution to System of linear inequalities 3x3

just a starting hint Linear disequalities are much more involved than equalities., and diophantine inequalities more than continuous inequalities. That premised we have better first of all to get rid ...
user avatar
  • 33.6k
2 votes

What is the meaning of this math formulation?

It looks like a standard flow conservation constraint. In network models, it is somewhat common to use either $\Delta^-(v)$ or $\delta^-(v)$ to denote the set of nodes $u$ for which there is an arc ...
user avatar
  • 4,020
1 vote

How is the dual problem for conic programs derived via Lagrangians?

The main idea is that we can use the relation $x\in K$ implicitly; we could penalize it directly in the Lagrangian, but we can also use the fact that $x\in K$ to derive a relation on other quantities. ...
user avatar
  • 2,400
0 votes
Accepted

Linearization of non-linear program

You have $x_j \le M$ for all $j$. You can enforce the logical implication $$\sum_{j=1}^{i-1} x_j > b_0 \implies x_i \le b_1$$ by introducing binary decision variable $y_i$ and imposing linear ...
user avatar
  • 34.8k

Top 50 recent answers are included