9 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 ...
user avatar
7 votes
Accepted

Proving that a sphere has a minimal surface to volume ratio using Calculus of Variations

I spent a few more hours on the problem, and eventually found the solution. No major breakthroughs, but a lot of algebra. First, I reversed the problem, instead maximizing the volume subject to a ...
user avatar
  • 672
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 ...
user avatar
  • 1,474
6 votes
Accepted

Conic by three points and two tangent lines

The comment by Narasimham made me aware of a very elegant way of tackling this problem. The figure above can be interpreted as the orthogonal projection of a right cone whose axis lies in the plane. ...
user avatar
  • 38.6k
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 ...
user avatar
  • 46.2k
6 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 \; \...
user avatar
  • 19.2k
5 votes

Model Predictive Control

In addition to the answer of @Johan at point 5), note I use a different cost function, with which you are probably more familiar with Define the cost function $\mathbf{V}(\mathbf{x},\mathbf{U})$ as $...
user avatar
  • 872
5 votes
Accepted

Can a convex QCQP with an additional linear constraint be converted into a SOCP?

It is always possible to convert a convex QCQP into an SOCP. It is not always possible to go the other direction, however. Just express this problem as follows: \begin{array}{ll} \text{minimize} & ...
user avatar
5 votes
Accepted

Calculus of variation with inequality constraints

Suppose that on two infinitesimal intervals $A = [a, a+dx]$ and $B = [b, b+dx]$, we have $a < b$, $y > \epsilon$ on $A$ and $y< 1 - \epsilon$ on $B$. Let $C = [0,1] - A - B$. Since $g$ is ...
user avatar
5 votes

Proving that a sphere has a minimal surface to volume ratio using Calculus of Variations

There are a few problems with the formulation: The volume constraint: right now you are constraining the total volume to be zero (check by differentiating $S$ with respect to $\lambda$). If you want ...
user avatar
  • 46.2k
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 ...
user avatar
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-...
user avatar
  • 22.4k
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 ...
user avatar
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$.
user avatar
  • 75.4k
5 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 \...
user avatar
  • 48.6k
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.
user avatar
  • 48.6k
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 ...
user avatar
5 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 ...
user avatar
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 ...
user avatar
4 votes

Notation: is a factor of

Well $|$ is used to describe divisibility so I think it meets our requirements. For example, $3|6$. $x$ is a factor of $y$ $\Leftrightarrow$ $x|y$.
user avatar
  • 2,820
4 votes
Accepted

Trace minimization subject to constraints

First, let $L=(\sqrt{\Sigma})^{-1}H$ the minimization problem becomes $$ \min_{K:K\sqrt{\Sigma}\cdot L=I}{\rm tr}((K\sqrt{\Sigma})(K\sqrt{\Sigma})^T) =\min_{S:SL=I}\,{\rm tr}(SS^T) =\min_{S:SL=I}\,\...
user avatar
4 votes
Accepted

Linear optimization with "max" function (convex) constraint

We may assume that $k_1+k_2 < L$, otherwise we simply could drop the constraint $\max(x_1,k_1)+\max(x_2,k_2)\geq L$ and solve the remaining system. Now let $P=\{x\mid Ax\leq b, x\geq 0\}$. Further ...
user avatar
4 votes
Accepted

Find the points on the sphere $x^2 + y^2 + z^2 = 4$ that are closest to, and farthest from the point (3, 1, -1).

Do you have to use Lagrange multipliers? The sphere is centered at the origin, and the point lies outside it. If you find the line through $(3,1,-1)$ and the origin, the closest and farthest points ...
user avatar
  • 25.6k
4 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 ...
user avatar
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 ...
user avatar
  • 4,030
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 ...
user avatar
4 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 + ...
user avatar
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$
user avatar
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....
user avatar
  • 19.2k

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