Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [constraints]

In mathematics, a constraint is a condition of an optimization problem that the solution must satisfy.

0
votes
0answers
11 views

Formulation of SVM optimization problem

I need help in verifying/understanding a step in formulating an optimization problem used for support vector machines (though this question doesn't need any background in SVM). Consider a bunch of $m$ ...
1
vote
2answers
28 views

Formulation of a constrained optimization problem with probabilities

we are given four probabilities for an event. We shall adapt these probabilities in order to maximize the entropy given a constraint $4 = \sum_{i = 1}^4 2p_ii \Leftrightarrow 2 = \sum_{i = 1}^4 p_ii$. ...
0
votes
1answer
31 views

Periodic B-spline least squares fitting

I have a set of $M$ data points $(x_j,y_j), 1 \le j \le M$ defined on an interval $[a,b]$ and I want to fit a periodic B-spline of order $k$ to these data. So my model will be: $$ f(x) = \sum_{i=1}^N ...
2
votes
2answers
71 views

Lagrange multipliers example with sympy - all minima but one maxima.

Consider the following optimization problem: Minimize $x^3+y^3$ Subject to: $x^2+y^2 \leq 1$ On the boundary of the constraint, we can consider $x=\cos\theta$ and $y=\sin\theta$. Then, the ...
0
votes
2answers
36 views

Given a circle $A$ of area 1 centered at $\{0,0\}$, give conditions that another circle $B$ of known area <1, lies totally within $A$

Given a circle $A$ of area 1 centered at $\{0,0\}$--so, of radius $\frac{1}{\sqrt{\pi}}$--give conditions on the possible location of the center $\{x,y\}$ of another circle $B$ of known area $\pi r^2 &...
1
vote
0answers
27 views

Convex Conjugate of sum-of-max terms

Let $f: \mathbb{R}^n \mapsto \mathbb{R}$ be a sum-of-max linear terms function: $$f(x) = \sum_{k=1}^K \max_i\{a_{k,i}^\top x\}$$ where $a$ are the linear coefficients. I am interested in the convex ...
0
votes
0answers
40 views

Optimizing a function under strictly positive constraint

Find x and y that optimise \begin{align} f(x,y) &= (-a-y)(\Psi(y)-\Psi(x+y)) + (b-x)(\Psi(x)-\Psi(x+y)) \\ &-\log \Gamma(x+y) + \log\Gamma(x) + \log\Gamma(y) \end{align} where a, b are ...
0
votes
1answer
21 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 ...
0
votes
0answers
23 views

Optimize for a parameter in a function with constraints on other 2 more parameters

I am an applied statistics student trying to solve a problem where constrained optimization is required. I have a function $f(x, p_1, p_2)$ in which $p_1 \epsilon [0,1]$, $p_2 \epsilon [0,1]$ are ...
1
vote
2answers
52 views

Least Squares with equality and inequality constraints

Could someone kindly suggest a method of solving the following constrained (equality and inequality) system of equations in the least squares fashion? $$\min_x\frac 12\|Ax-b\|_2^2$$ such that $$\...
0
votes
0answers
8 views

Degrees of freedom in hypothesis testing with multiple constrained parameters in one constraint

Suppose you are estimating a (multivariate) model with a parameter vector $\theta=(\theta_1,\dots,\theta_p)'$. You have two constraints in the model, and would like to test them with either the ...
2
votes
0answers
169 views

Similarity of the solutions

I am trying to solve the following rank-k decomposition $$\Sigma \approx W\Lambda W^T$$ where $\Sigma \in R^{n \times n}$ is a positive definite symmetric matrix having diagonal elements 1, $\Lambda \...
1
vote
3answers
45 views

Maximum and minimum of $\frac13x^3 - \frac32y^2 + 2x $ such that $x-y=0$

The function to maximize and minimize is; $$f(x,y) = \frac13x^3 - \frac32y^2 + 2x $$ The constraint is; $$g(x,y) = x-y $$ such that $$g(x,y) = 0$$ I found the first order condition and found ...
0
votes
1answer
30 views

Adding $\lambda\cdot d$ to a constraint. How does the optimal solution change?

We are give a linear programm in standard form. Given $A\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ with Rank$(A)=m$ and $B$ a basis whos basis solution is optimal. Now the right side of the constraint $Ax=...
0
votes
0answers
19 views

Optimization, Are all points feasible if there is only one constraint?

The definition of a regular point is as follows : If instead of having multiple constraints there is only one, we would have $$ D\;h(x) = \nabla h_1(x)^T $$ Would all points then be regular ...
0
votes
0answers
5 views

Counting the number of variables and constraints

An optimization problem is defined a graph of V nodes and E edges. First, I defined variables on each nodes (two independent variables for each node), and each edge imposes one constraint (on the 2 ...
0
votes
0answers
11 views

Linearization of constraints including product of binary variables.

I have three constraints including product of binary variables as following: enter image description here So basically, I have a complicated multiplication of binary variables. I am wondering if I ...
0
votes
0answers
16 views

Is there any online nonlinear constrained optimizor available?

I am trying to a nonlinear constrained optimization that has around 100 variables and countless constraints, is there any online nonlinear constrained optimizer available?
2
votes
1answer
17 views

Optimisation - first order necessary conditions, directions, Chong & Zak Q. 6.16

For this question from Introduction to optimisation by Chong & Zak : The answer is : I'm unsure about what's been done for part (b) here. From part (a) it seems that for $d$ we have $d=...
2
votes
1answer
81 views

Constants of motion for a system of two points moving on spherical surface with a force depending only on their relative distance

Consider two points that moves only on a spherical surface of radius $R$. There is only a force between them that has a potential $U(d)$ where $d$ is the distance between the two points. What is the ...
3
votes
1answer
33 views

Labeling nodes in a bipartite graph to satisfy edge constraints

I'm trying to find an algorithm for the following problem. Let $G$ be a bipartite graph. The edges in $G$ have labels $R$; each label $R(u, v)$ is an integer range $[a, b]$ with $a$ and $b$ being ...
0
votes
0answers
42 views

Is there an easy way to tell if a set of quadratic constraints are solvable

I am trying to find a matrix whose null space $N\in\mathbb{R}^{9 \times n}$ does not intersect with the column space of the matrix $$ M(R) = \begin{bmatrix} 0 & -r_3 & r_2 \\ r_3 & 0 &...
1
vote
2answers
44 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 ...
2
votes
2answers
35 views

Strict inequality logical implication in optimization problems

I have $ x \in \{0,1\}$ and $y \geq 0$ and I want to model that $x=1$ iff $y>0$, is this possible while keeping the constraint linear? Thanks. One part of the implication is easy $ y \leq Mx$. The ...
0
votes
1answer
53 views

Lagrange multipliers don't seem to work

Consider the following constrained optimization problem: $$ \min x^3+y^3 \\ \text{s.t.} x^2+y^2\leq 1 $$ From plotting this, the minima seems to be at $(-1,0)$ and $(0,-1)$. Now, the KKT conditions ...
0
votes
0answers
25 views

Is there efficient Surface Walking method for optimization problems with equality constraint?

To my best knowledge, if we want to find the minimum of a function $f$ defined on a $d$-dimension manifold $M$ in $\mathbb{R}^n$, a.k.a an optimization problem with equality constraint, the most ...
0
votes
0answers
26 views

Optimization with a symmetric matrix constraint

I have a problem where I need to find the optimal $X\in S_{++}^n$ (i.e. $X$ is positive definite) for a strictly convex function $f(X)$. For what I understand, I need to assign a positive ...
0
votes
1answer
45 views

Linear programming constraints

How do I formulate a linear constraint using LP for the following? $$x_1 + x_2 + \cdots + x_n \geq 5$$ then $z$ takes a value of $1$, where $x_1, x_2, \dots, x_n, z \in \{0,1\}$.
2
votes
3answers
131 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,...
1
vote
0answers
17 views

Minimizing polynomial function over the standard simplex

I have the following optimization problem $$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{i=1}^k x_i \prod_{j=1}^{i-1} (1-x_j)\\ \text{subject to} & \displaystyle\sum_{i=1}^k x_i = 1\...
0
votes
0answers
8 views

Univalent Mapping - Uniqueness of Fixed Point on the Positive Orthant

I am facing a n-dimensional fixed-point problem descending from a game theoretic problem given by the set of equations $$ \forall j \in n: R_{j} (\vec{x}_{-j}) - x_{j} = W \left( A_{j} \exp \left(-\...
0
votes
1answer
40 views

Describing Constraints Using Linear Algebra (Convex Optimization)

I've been learning Convex Optimization but one thing that really confused me in class was how exactly to recast a given set of constraints in matrix form, so that it can be solved using CVX. For ...
0
votes
0answers
33 views

Optimization problem with the dependent decision variables

In the optimization problem with $2$ dependent decision variables, is it possible to reduce the objective function to a problem with one variable and enforce the relation between variables as an ...
1
vote
0answers
31 views

Constrained Optimization: Abstract Problem

I could use some help with these problems. Suppose we have an objective function $f(x, y)$ and a constraint $y = h(x)$. Suppose the Lagrangian has a critical point at $(0, 0, \lambda^*)$. 1) Explain ...
0
votes
1answer
24 views

How many constraints are there in $g(x) \leq 2x \geq 0$?

How many constraints are there in $g(x) \leq 2x \geq 0$? I thought $g(x) \leq 2x$ and $g(x) \geq 0$, but something suggested that there could be three rather than two constraints here? Perhaps the ...
1
vote
0answers
25 views

A scheduling problem on an oriented graph with multiple constraints

The problem is the following : Data An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks A map $d: V \rightarrow \mathbb{N}$ : to be understood a function mapping tasks ...
0
votes
0answers
22 views

Solution of Linear Diophantine Equation

How to find all solutions of Linear Diophantine Equation $a \cdot x + b \cdot y = c $ given $a,b,c$ where $c$ is divisible by $\gcd(a,b)$ and constraints are $x_0 \leq x \leq x_1$ and $y_0 \leq y \leq ...
0
votes
0answers
29 views

Logical operators in constrained optimization

Trying to find the minimum of a function $f(x,y,z)$ is it possible to write (and solve) such constraints: $min f(x,y,z)$ subject to $(x=1 \land y=4 \land z=2) \lor (x=4 \land y=1 \land z=3) \lor (x=9 \...
0
votes
1answer
99 views

How to linearize the product of a non-binary discrete variable and a continuous variable?

Given a set $J$, I have the following constraint: $w_j = y_j u \quad \forall j \in J$ where $y_j \in \mathbb{N}$ and $u \in \mathbb{R}⁺_0$. I would like to make this constraint linear. Note: I am ...
0
votes
1answer
51 views

Multiple constraints on quadratic programming? - How to solve?

Assume that you are using quadprog command in MATLAB/Octave and you want to minimize this objective function: $$\Phi_{min} = \frac{1}{2}X^TQX + c^TX$$ With ...
4
votes
1answer
109 views

Proving $\frac12 < \int_0^1 \frac1{\sqrt{4-x+x^3}} dx < \frac{ \pi }6$

I have a question where I have to show $$\frac12 < \int_0^1 \frac1{\sqrt{4-x+x^3}} dx < \frac{ \pi }6 \approx 0.52359$$ using the result $$\frac12 < \int_0^{1/2} \frac{1}{\sqrt{1-x^{2n}}} ...
0
votes
0answers
26 views

N dimension random distribution with constraints

I am trying to draw $M$ random/semi-random numbers in $N$ dimensions applying some constraints. For instants I have a method that "selects" only the right points, but I am sure that it can be done ...
1
vote
0answers
34 views

“Convert” quadratic constraint to quadratic objective

I have a large sparse quadratic optimization problem with a single quadratic constraint: $$\begin{array}{ll} \text{maximize} & c'x\\ \text{subject to} & l \leq Ax \leq u\\ & x'Qx + b'x \...
1
vote
1answer
37 views

Finding a constraint on one variable of a multivariable function to constrain the entire function

I have a function. Now I want to let my variables only take values between 0, and 1. The problem is as follows. For what values of Y, is L(x,y) < 0. That is, without putting a further constraint ...
0
votes
1answer
26 views

Can the simplex method be used for general monotonically increasing objective functions?

The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's ...
0
votes
1answer
25 views

A convex objective function will be convex regardless of constraints?

Let's say I have a convex objective function. The boilerplate example is $z=x^2+y^2$. Now, I also have some constraint, $f(x,y)=0$. Is it true that the constrained optimization problem must be convex ...
2
votes
2answers
71 views

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

if $x,y$ are real number such that $x^2+2xy-y^2=6$ Then find minimum value of $(x^2+y^2)^2$ what i try : $x^2+2xy+y^2-2y^2=6$ or $(x+y)^2-\bigg(\sqrt{2} y\bigg)^2=6$ put $\displaystyle (x+y)=\sqrt{6}...
0
votes
0answers
28 views

Proving the learnability of XOR function by a particular neural network

Let's say I have the following neural network and the constraints: The architecture is fixed (see the network in this image, I'm not allowed to post images due to low rep) (note that there are no ...
3
votes
0answers
77 views

Riemannian Manifold for the Partial Doubly Stochastic Matrices

Excuses if my formulation is non-rigorous. I am not a mathematician by training. I have a constrained optimization problem where each of my matrix valued parameters lives inside the Birkhoff Polytope....
3
votes
0answers
26 views

Computing hyper area of a contrained simplex

Let $D_n [r , (a_1, b_1 ) , \ldots , (a_n, b_n) ] = \{ (x_1 , \ldots , x_n ) \in \mathbb R^n \mid \sum_i x_i = r \mbox{ and } b_i \geq x_i \geq a_i \, \forall i \}$, where $r \geq b_i \geq a_i \geq 0$...