# Tag Info

Accepted

### Involving indicator function as a constraint in a LP problem

It's possible to do with a mixed-integer linear program: just add the constraint $$-a_i x \le b + A(1-y_i)$$ where $y_1, y_2, \dots, y_M$ all take values in $\{0,1\}$, and $A$ is a large constant ...
• 146k
Accepted

• 118k
Accepted

### Expressing Boolean constraint in binary integer linear programming

This can be described as a set of linear inequalities: \begin{align} &y_3\ge 1-y_1-y_2\\ &y_3\le 1-y_1+y_2\\ &y_3\le 1-y_2+y_1\\ &y_3\ge y_1+y_2-1 \end{align} These inequalities ...
• 4,307
Accepted

### How to model a consecutive binary constraint?

To model the implication as described in the question $$x_i=1 \text{ and } x_{i+2}=1 \Rightarrow x_{i+1} = 1$$ add the constraints: $$x_i -x_{i+1} + x_{i+2} \le 1$$ (no extra variables needed ...
• 4,307
Accepted

### A positive function which even derivatives are positive and odd derivatives negative

This is not a mathematics question at heart, but it has a certain overlap with mathematics. Such functions are called completely monotone, and are characterized by being the Laplace transforms of non-...
• 24.6k
Accepted

### Convert NL equality constraint involving minimum to linear inequality constraint?

The constraint $$z = \min(x,y)$$ can be interpreted as: \begin{align} &z \le x \text{ and } z \le y\\ &z \ge x \text{ or } z \ge y \end{align} This can be implemented in a MIP model ...
• 4,307
Accepted

### Given that $|3x|+|2y| \leq 1$ then the maximum value of $9x+4y$ is ?.

$9x+4y \le |9x+4y| \le 2|3x|+2|2y|+|3x| \le 2+|3x| \le 2+1=3$ and for $x=1/3$ and $y=0$ we have $9x+4y=3$.
• 77.6k
Accepted

• 5,253

### How is the inequality constraint $\mbox{Tr}(W) \geq c$ convex?

$\text{Tr}(W)$ is a linear function, so the constraint is convex.
• 52.7k
Accepted

### How is the inequality constraint $\mbox{Tr}(W) \geq c$ convex?

Suppose $$Tr(X) \ge c$$ and $$Tr(Y) \ge c$$ For $\alpha \in (0,1)$, we have $$Tr(\alpha X + (1-\alpha) Y)=\alpha Tr(X)+(1-\alpha)Tr(Y) \ge c$$ Hence it is convex. Note that trace is a linear ...
• 151k

### Constructible problems for which the solution is non-constructible?

First observe that there are constructive real numbers $a$ such that we (working in ZF) do not (currently) know whether $a$ is zero or positive. For example, let $a$ be given by the Cauchy sequence ...
• 73.4k
Accepted

### If $x^2+y^2+z^2=1$ and $x+y+z=0$, is it true that $x^4+y^4+z^4=\frac{1}{2}$?

$$x^4+y^4+z^4=(x^2+y^2+z^2)^2-2(x^2y^2+y^2z^2+z^2x^2)=1-2(x^2y^2+y^2z^2+z^2x^2)$$ Now $x^2y^2+y^2z^2+z^2x^2=(xy+yz+zx)^2-2xyz(x+y+z)=(xy+yz+zx)^2-0$ Again, $2(xy+yz+zx)=(x+y+z)^2-(x^2+y^2+z^2)=0-1$
Accepted

### L-BFGS convergence on constrained, nonconvex problems

I figured out what the issue was with my algorithm. It turns out that skipping an L-BFGS update when $\mathbf{s}_t^\mathrm{T}\mathbf{y}_k \leq 0$ was not the cause of the problem but rather how I was ...
• 161
Accepted

### Is there a closed form solution to the following optimization problem?

First note that the objective can be simplified to $\sum_{n=1}^N j_n -\lambda N i$. Now sort the $m_j$ into ascending order ($m_1\le m_2 \le \dots \le m_N$). Observe that, for fixed $i$ (and subject ...
• 5,253
Accepted

### Finding cones of directions

For me, it is easier to understand the definitions if you look at the geometry of the sets $S$. I'll look at parts a. and c. here. Before we start, I think you're missing something small from the ...
• 2,643

### Given that $|3x|+|2y| \leq 1$ then the maximum value of $9x+4y$ is ?.

The gradient of $9x+4y$ is $(9,4)$. Move along that from $-\infty$ to reach the constraint, pass through it and exit from the other side. The last point visited by this process is the maximal point ...
• 32.6k
Accepted

### Minimum value of $(x^2+y^2)^2$

$$(x^2+y^2)^2=(x^2-y^2)^2+4x^2y^2=(6-2xy)^2+4x^2y^2=2(2xy-3)^2+18\ge18$$ The equality occurs if $2xy=3$
Accepted

### Multiple constraints on quadratic programming? - How to solve?

You can rephrase $$y_{\min} \leq Ax \leq y_{\max},$$ as $$\begin{pmatrix}A \\ -A\end{pmatrix}x \leq \begin{pmatrix}y_{\max} \\ -y_{\min}\end{pmatrix},$$ which is in the format of what quadprog accepts....
• 19.9k
Accepted

### Linear program with quadratic (L2 norm) constraint

Your problem is a second order cone programming (SOCP) problem. There are specialized interior point solvers for these kinds of problems that can be very efficient.
• 11.1k
Accepted

### Either-or condition for equality constraints

You can do this by reformulating each equality constraint as two inequality constraints: \begin{align} & \quad \sum_{j\in J} a_{1j}x_j \leq b_1 +M_1y \\ & \quad \sum_{j\in J} a_{1j}x_j \geq ...
• 19.9k
Accepted

### How to prove that $C = cc^T$ is not convex?

Suppose $c \neq 0$ and $C=cc^T$. Then $C = (-c)(-c)^T$ and so $(C,c), (C,-c)$ are feasible. However the average $(C , 0)$ is not feasible, hence the feasible set is not convex.
• 175k