Questions tagged [constraints]
In mathematics, a constraint is a condition of an optimization problem that the solution must satisfy.
67
questions
13
votes
1
answer
18k
views
How to set up Lagrangian for matrix constraints?
Suppose we have a function $f: \mathbb{R} \to \mathbb{R} $ which we want to optimize subject to some constraint $g(x) \le c$, where $g:\mathbb{R} \to \mathbb{R}$. What we do is that we can set up a ...
- 6,045
0
votes
1
answer
72
views
Write logical operator all(x<a) in terms of Heavyside functions
I am currently solving a complex optimisation problem, with constraints that take the form: $1 - all(g(x)<a) <= 0$, meaning I require all values $g(x)$ (for some function $g$) to be below some ...
-1
votes
1
answer
291
views
How can I linearize the IFF-THEN constraint with binary and continuous variable?
I have an optimization problem where
$a_{m,n}\in\{0,1\}$ is a binary variable and $0\le f_{m,n}\le 1$ is a continuous vaiable
I have an Iff-THEN constraint like this
IFF $a_{m,n}=1$, THEN $f_{m,n}&...
- 155
10
votes
1
answer
3k
views
Conic by three points and two tangent lines
With the exception of degenerate situations, a conic is uniquely determined by five points lying on it. Likewise, five lines tangent to a conic uniquely define that conic. With four points and one ...
- 43.1k
10
votes
5
answers
1k
views
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$
An "Olympiad type" inequality:
Let $x_1,x_2,\dots,x_n$ real numbers in $[0;+\infty)$ with $x_1+\dots+x_n=1$ and
$$f(x_1,\dots,x_n)=\frac{x_1+x_2}{1+x_1x_2}+\frac{x_2+x_3}{1+x_2x_3}+\dots+\...
- 302
8
votes
2
answers
3k
views
Calculus of variation with inequality constraints
Find the function $y$ which maximizes the functional $$J[y] = \int_0^1 g(x) y(x) dx$$ subject to $0 \leq y(x) \leq 1$ for all $x\in [0,1]$ and $$\int_0^1 y(x) dx = k$$ where $g$ is a strictly ...
- 135
7
votes
1
answer
8k
views
Involving indicator function as a constraint in a LP problem
I am trying to solve following LP problem
\begin{align}
&\min_x –c^\top x \\
\text{s.t.} & \sum_{i=1}^M I(-a_i x\leq b) \geq m \\
& \sum_{i=1}^N x_i =1 \\
& x_i\geq 0
\end{align}
where ...
- 153
6
votes
2
answers
412
views
Different Approaches for Proving Kantorovich Inequality
Here is a statement of the famous Kantorovich inequality.
Thoerem (Kantorovich). Let $A$ be a $n\times n$ symmetric and positive matrix. Furthermore, assume that its eigenvalues are $0 < \lambda_1 ...
- 15.2k
6
votes
1
answer
2k
views
Connection Between Orthogonal Projection onto the Unit Simplex and the Softmax Function
Referring to papers Softmax to Sparsemax and Efficient Projections onto the L1-Ball, what is the relationship between a euclidean projection onto the probability simplex and applying the Softmax ...
- 91
5
votes
2
answers
161
views
$f(x, y, z)$ with both $\leq$ and $=$ constraints. General questions.
I need to ask you for this question, which is a rather general one, in order to understand how to behave when studying maxima and minima with constraints, in many variables. The specific question is ...
- 3,501
4
votes
2
answers
3k
views
How to model a consecutive binary constraint?
Let us say we have $n$ binary variables $x_i$ for all $i=1,2,\ldots,n$, i.e., $x_i\in\{0,1\}$ for all $i=1,2,\ldots,n$.
I need to write the following constraint:
If $x_i=1$ and $x_{i+2}=1$, then $...
- 527
3
votes
2
answers
4k
views
Model Predictive Control
I have a few confusions about Model Predictive Control (MPC). Since they are all minor questions related to the same category, I ask them under one topic.
In an article, the cost function is defined ...
- 75
2
votes
1
answer
198
views
How to handle equality constraints in this problem?
Here is the problem setup
\begin{equation}
\begin{array}{c}
\text{min} \hspace{4mm} \mathbf{b}^{T}_{}\mathbf{A}^{}_{}\mathbf{b}^{}_{} \\
s.t \hspace{5mm} \mathbf{b} \in \mathbb{R}^{N} \\
\hspace{9mm}...
- 1,007
1
vote
3
answers
471
views
Circle and Locus _ ONLY PEN AND PAPER ALLOWED.
Q) Let T be the line passing through the points P(–2, 7) and Q(2, –5). Let $F_{1}$ be the set of all pairs of circles $(S_{1}$, $S_{2}$) such that T is tangent to $S_{1}$ at P and tangent to $S_{2}$ ...
- 1,274
9
votes
1
answer
5k
views
the relation between cardinality, L1-norm and L2-norm of a vector
For every $u\in \mathbb{R}^n$, $\textbf{Card}(u)=q$ implies ${\lVert u \rVert}_1 \leq \sqrt{q} {\lVert u \rVert}_2$
where $\textbf{Card}(u)$ is the number of non-zero element (so the L0-norm).
Why ...
- 299
7
votes
2
answers
2k
views
Integer linear programming constraint for maximum number of consecutive ones in a binary sequence
Consider an integer programming problem with binary decision variables $x_1,\ldots,x_n \in \{0,1\}$. Im trying to model the constraint that enforces the maximum number of consecutive ones in ...
- 1,113
7
votes
1
answer
900
views
Least-squares over the unit simplex
I am interested in the non-negative least squares problem subject to one equality constraint
$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} &...
- 215
5
votes
1
answer
3k
views
How to use Karush-Kuhn-Tucker (KKT) conditions in inequality constrained optimization
I am trying to understand how to use the Karush-Kuhn-Tucker conditions, similar as asked but not answered in this thread.
Assume the target function is given by $f(x)$, where $x$ a vector. Let $g(x) ...
- 948
4
votes
2
answers
620
views
Find the unit vector within a subspace with the minimum norm projection onto another subspace
Let $W$ and $V$ be subspaces of $\mathbb{R}^n$ with dimensions $m$ and $p$ respectively. I want to find the unit vector in $W$ whose projection onto $V$ has the minimum Euclidean norm. From geometric ...
4
votes
1
answer
928
views
Optimize monotonic function in calculus of variations
I'm interested in the variational problem
$$\min_{y} \int_a^b F(x,y(x),y'(x))dx \qquad \text{subject to} \quad -y'(x)\leq 0 \quad \forall x \tag{1}$$
i.e. $y(x)$ has to be monotonic.
I ...
- 362
4
votes
1
answer
582
views
Asymptotics of Gaussian integral over the unit sphere
I would like to evaluate the integral asymptotically over the unit sphere surface
$$
Z =\int e^{a \cos^2 \theta + b \sin^2\theta\cos2\phi + c\cos\theta} d\Omega = \int\limits_{0}^{\pi}\int\limits_{0}...
- 1,288
4
votes
1
answer
3k
views
Why use Bordered Hessian than "simple" Hessian as second derivative test?
Why use Bordered Hessian than "simple" Hessian as second derivative test in a multi constrained optimization problem?
The critical points are found from the Lagrangian so they follow the constraints.
...
- 43
4
votes
1
answer
4k
views
Can a convex QCQP with an additional linear constraint be converted into a SOCP?
I have a quadratically constrained quadratic program (QCQP) that I massaged into the form
$$\begin{aligned} & \underset{x}{\text{minimize}}
& & x^T Q x \\
& \text{subject to}
& &...
- 177
3
votes
1
answer
272
views
Importance of the Klee-Minty Cube in Optimization
Has anyone ever heard of the Klee-Minty Cube in Optimization?
Supposedly, the Klee-Minty Cube shows the "flaws" of the Dantzig's Simplex Algorithm. Supposedly, Dantzig's Simplex Algorithm ...
- 3,242
3
votes
0
answers
962
views
From constrained to unconstrained maximization problem
I have the following constrained maximization problem
$$
\max_{X_1,X_2,...,X_i,...,X_N} \sum_{i=1}^{N}X_i f_i(X_1,...,X_N)
\hspace{0.2 cm} \text{subject to} \sum_{i=1}^{N}X_i-B\leq 0 \text{ and } X_i\...
- 278
3
votes
0
answers
94
views
Subset sum problem with $F_m^2 F_n^2$ (Fibonacci square) weights
Suppose $$N = \sum_{i=1}^{k} \sum_{j=1}^{k} x_i \cdot y_j\cdot F_{c_i}^2 \cdot F_{c_j}^2 ; (x_i, y_j, c_i, c_j \in \mathbb{Z}, c_i, c_j \ge 1) \tag{1}$$ and $F_k$ is the $k$-th Fibonacci number. The ...
- 3,376
3
votes
2
answers
3k
views
How to maximize area of two circles inside a rectangle without overlapping?
Two circles have to be drawn inside a rectangle of dimensions $W\times H$ such that the area of both circles is to be as large as possible without overlapping.
Let the radii of the circles be $r_1$ ...
- 33
2
votes
1
answer
356
views
How to Solve this Boolean Equations?
I have a Boolean Equations, described as below,
$$\neg \mathbf{x} = \mathbf{M}\cdot \neg(\mathbf{M} \cdot \mathbf{x})$$
in which $\mathbf{M}$ is an $n\times n$ Boolean matrix, and $\mathbf{x}$ is an $...
- 63
2
votes
1
answer
2k
views
Derivative of the solution of a linear program
Let $x^\star$ be a solution of the linear program
\begin{align}
\text{maximize} &\quad c \cdot x \\
\text{subject to} &\quad A \cdot x \leq b
\end{align}
How can one compute the derivatives of ...
- 6,057
2
votes
1
answer
169
views
Why not define the Lagrangian like this?
Say I have a constrained optimisation problem where I need to minimize $f(x,y)$ subject to the constraint that $g(x,y) = c$.
The lagrangian is defined as
$$\mathcal{L}(x,y,\lambda)=f(x,y)+\lambda (g(...
- 703
2
votes
3
answers
1k
views
Why does the Lagrange multiplier $\lambda$ change when the equality constraint is scaled?
Consider the problem
$$\begin{array}{ll} \text{maximize} & x^2+y^2 \\ \text{subject to} & \dfrac{x^2}{25} + \dfrac{y^2}{9} = 1\end{array}$$
Solving this using the Lagrange multiplier method,...
- 609
2
votes
2
answers
8k
views
How do you find redundant constraints for a feasible region?
I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm only trying to find the non-redundant constraints that define a feasible region (i.e. I ...
- 131
2
votes
1
answer
3k
views
Converting nonlinear constraints (product of binary and continuous variables) for linear programming
I have the following constraint in my model:
$$(\sum_i^I \epsilon_i^m x_{ij} - c_j^m) \sum_k^K w_{jkm} z_{jk} \le \tau_j^m - c_j^m \qquad \forall j, m$$
where $0 \leq x_{ij} \leq 1$ and $z_{jk} = \{...
- 25
2
votes
2
answers
41
views
Can the implication $(x_1 = 0) \rightarrow (p(x_1,...,x_n) = 0)$ be encoded in a system of polynomial constraints in $\mathbb{C}[x_1,...,x_n]$?
Consider a set $S$ of polynomials in $\mathbb{C}[x_1,x_2,...,x_n]$, the polynomial ring of $n$ variables over the complex numbers.
The set $S$ can then be interpreted as a system of constraints on the ...
- 890
2
votes
2
answers
5k
views
Max and Min using Lagrange Multipliers
Suppose A is a symmetric matrix. Show that the maximum and minimum of $\mathbf x ^T A \mathbf x$ subject to the constraint $\mathbf x ^T \mathbf x=1$ are the maximum and minimum eigenvalues of A.
I ...
- 1,245
2
votes
1
answer
146
views
I have a problem solving an Isoperimetric Question using Euler-Lagrange
I have been asked to find the extremums for the functional$$\int \limits _0^1(x')^2+t^2\,dt$$subjected to$$\int \limits _0^1x^2\,dt=2,\quad x(0)=0,\quad x(1)=0,$$with $x=x(t)$ and $x'=x'(t)$.
Here,$$L(...
- 143
2
votes
1
answer
455
views
Operations Research - Optimal Transport Routes
I have a problem in which there are 4 vessels available to transport people from 3 different bases back to a main base.
Vessel 1 has a capacity of 50, can make 6 round trips, and is allowed
to visit ...
- 23
2
votes
4
answers
1k
views
Binary variables in time series: integer linear programming
I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.
I have a binary variable $\alpha_t$ for $t \in [0, 24[$. I ...
- 1,093
2
votes
1
answer
83
views
How does one use the 'input/hr' column in the table below in setting up the problem?
I have to set up a linear programming problem corresponding to the following scenario:
If my understanding of the problem is correct, I use $mod$:
Let $i$ be $A$ or $B$.
Let $x$ be amount of raw ...
- 13.8k
2
votes
1
answer
319
views
Optimal transport with relaxed constraint on marginals
Let $X$ be some appropriate space (metric measure, Polish, whatever...) and $X\times X$ the product space with $\pi^1$ and $\pi^2$ as projections onto the first and second factor, respectively. Let $\...
- 1,213
1
vote
1
answer
186
views
Identify boolean function that satisfies some constrains
The problem
I want to find a boolean function $f(x,y):\{0,1\}^n \rightarrow \{0,1\}$, where $x=\{x_i\}_{i=1}^{m}$ and $y=\{y_i\}_{i=1}^{k}$ are $m$ and $k$ boolean variables, such that:
$m,k \ge 1$ (...
- 327
1
vote
1
answer
253
views
matrix least square optimization with constraint
I want to Minimize the following equation (the error matrix) by
formulating a cost function and calculating the point where
its gradient equals zero.
\begin{equation}
\hat{X} = \arg \min_{X} \...
- 63
1
vote
1
answer
139
views
Apply the Lagrange multiplier rule to find the minimizer of an integral functional over a convex set
I want to minimize $$F(w):=\sum_{i\in I}\sum_{j\in I}\int\lambda({\rm d}x)w_i(x)p(x)\int_{\left\{\:pq_j\:>\:0\:\right\}}\lambda({\rm d}y)\frac{\left|w_j(y)p(y)\right|^2}{q_j(y)\sigma_{ij}(x,y)}\...
- 13.8k
1
vote
2
answers
63
views
Linear program geometry
I’ve tried to solve a question in my homework, and I don’t really know what to do.
In the problem a polyhedron is given and I need to build the set of constraints that defines this polyhedron.
The ...
- 111
1
vote
2
answers
134
views
Looking for asymp exp as $N \rightarrow \infty$ for $\sum_{r=1}^{N}\sum_{t=1}^{N}\left[\sqrt{rt}\in Z\right]$ w/wo the constraint $GCD(r,t)=1$
Where $[...]$ are Iverson brackets. These two problems arise from summing over the number of reducible quadratics using their coefficients where $r\, {x}^{2} + s\, x + t$ where in both cases we have $...
- 975
1
vote
2
answers
1k
views
$ {L}_{1} $ (L1) Norm Regularized Minimization with of Convex Function with Linear Equality Constraint Using ADMM Framework
In section 6.3 of Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers there is a method for minimizing a loss function with l1 regularization. i.e.
...
- 151
1
vote
0
answers
69
views
Help needed to define a constraint in an optimization problem?
Given objective function is
\begin{align}
\underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t \hspace{4mm}\mathbf{p^Te_p}-1=0\\\...
- 1,007
1
vote
1
answer
164
views
Linear constraint considering binary bit position
Right now, I have some binary variables for a linear programming problem:
$x_1\;x_2\;x_3\;x_4\;x_5\;x_6\;x_7\;x_8$
Say these are groups of 4 bits each in this example. So:
Group 1 ={$x_1\;x_2\;x_3\;...
- 75
1
vote
1
answer
211
views
Least squares minimization subject to the constraint $\sum_j|u_j| \leq 1$
I would like to learn about methods for minimizing the cost $L(u) = (f - Au)^{tr}M(f-Au)$, where $f \in R^m$ is a known vector, $u \in R^n$ is the argument of the minimization and $A \in R^{n\times m}$...
- 4,815
1
vote
2
answers
1k
views
Least Squares with Quadratic (Positive Definite) Constraint
I wonder how to solve the following constrained problem
${\rm Minimize}_{\vec{A}}$ $\parallel Z\vec{A}-Y\parallel^2_2$ , $\quad\vec{A}\in\mathbb{R}^{n^2}$
such that: $A\in\mathbb{R}^{5\times 5}$ is ...
- 476