11
votes
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
11
votes
Accepted
Non-negative non-decreasing polynomial lower than $x^N$ somewhere in $0 \le x \le 1$
For $N\geq 3$, there is such a polynomial. Take $f(x)=x^{N-3}(x-3x^2+3x^3)$. To show that this satisfies the desired property, it suffices to check the $N=3$ case.
We compute $f(x)=x-3x^2+3x^3=x(1-3x+...
- 34k
9
votes
Accepted
Minimizing $\frac{x_1+x_2}{1+x_1x_2}+\frac{x_2+x_3}{1+x_2x_3}+\dots+\frac{x_n+x_1}{1+x_nx_1}$ for non-negative $x_i$ satisfying $x_1+x_2+\dots+x_n=1$
Here is a complete solution proposal for the case $n\geq 4$.
Sorry for the bad english.
The set of $(x_1,...,x_n)$ with non negative coefficients and sum $1$ is compact and the function $f$ considered ...
- 164
7
votes
Minimum value of $(x^2+y^2)^2$
I think a fun way to do the problem similar to what you've done is by using polar co-ordinates. Sub $x=r \cos \theta$ and $y=r \sin \theta$. Then you want to minimise $(x^2+y^2)^2=r^4$. Note that the ...
- 1,766
7
votes
Accepted
What is "box-constrained mathematical optimization problem"?
It is a problem where the only constraints are upper and lower bounds on the variables (which can be $\pm \infty$). Examples are:
$$\min_{x \geq 0} f(x)$$
$$\min_x \{ f(x) : 0 \leq x_i \leq 1 \; \...
- 19.9k
6
votes
Accepted
How to use Karush-Kuhn-Tucker (KKT) conditions in inequality constrained optimization
Think about what an inequality constraint means for optimality:
either the optimum is away from the boundary of the optimization domain, and so the constraint plays no role;
or the optimum is on the ...
- 49.8k
6
votes
Why does the Lagrange multiplier $\lambda$ change when the equality constraint is scaled?
If $x^\star$ minimizes $f(x)$ subject to the constraint that $g(x)=0$, then under mild assumptions there exists a Lagrange multiplier $\lambda$ that satisfies
$$
\tag{1} \nabla f(x^\star) = \lambda \...
- 52.7k
6
votes
Accepted
Derivative of the solution of a linear program
This is known as sensitivity analysis. If you have a non-degenerate optimal basic feasible solution, it is relatively simple to find derivatives of the optimal BFS or the optimal objective value ...
- 11.1k
6
votes
Accepted
Lagrange Multipliers. What do I do if the Lagrange multiplier is 0 or the gradient of the constraint is 0?
Great question! Consider the constraint $g(x,y) = y^3-x^2$. Note that $\nabla g(0,0)=(0,0)$. Now consider the function $f(x,y) = y$. Your task is to minimize $f(x,y)$ subject to the constraint $g(x,y)=...
- 118k
5
votes
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
5
votes
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
5
votes
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
5
votes
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
5
votes
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
5
votes
Accepted
Binary variables in time series: integer linear programming
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 + ...
- 4,307
5
votes
Accepted
How to linearize the product of a non-binary discrete variable and a continuous variable?
If you can bound $y_j$ by some (not too large) positive integer $Y$, so that $y_j\in \{0,1,\dots,Y\}$, you can introduce binary variables $z_0, z_1,\dots,z_Y$ and add the following constraints:$$\sum_{...
- 5,253
5
votes
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
5
votes
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
5
votes
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
4
votes
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$
- 276k
4
votes
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
4
votes
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
4
votes
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
4
votes
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
4
votes
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$
- 276k
4
votes
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
4
votes
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
4
votes
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
4
votes
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
4
votes
Minimizing a functional subject to boundary conditions
TL;DR: It is potentially problematic to assume a 6th-order Euler-Poisson (EP) equation in a higher-order variational problem without adequate boundary conditions (BCs).
OP's functional can be ...
- 12.7k
Only top scored, non community-wiki answers of a minimum length are eligible