Questions tagged [constraints]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 views

Calculating a maximum size of subset of permutations and finding an example of such subset. [closed]

I've been trying to solve a problem of finding a subset of permutations under a certain constraint. So far I wasn't able to solve this, hope someone can help. Thank you in advance. The problem: We ...
user avatar
  • 11
0 votes
0 answers
15 views

Non negative least square problem with added constraints [closed]

Let $\eta,\theta \in (\mathbb{R_+})^n$ and $\varepsilon \in \left\{ -1,1\right\}^n$. Define then the matrix $A$ and the vector $y$ by $$A_{i,j}=\sqrt{\eta_i}\varepsilon_j\mathbb{1}_{\left\{ i \geq j\...
user avatar
  • 69
0 votes
0 answers
19 views

Homogeneous Least-Squares Problem with Nonlinear Constraint

I would like to find a non-trivial solution to a homogeneous least-squares problem, i.e., $$\mathrm{min}\,\|\bf{A}\bf{x}\|$$ where $\bf{A}\in\mathbb{C}^{m\times n}$ and $\bf{x}\in\mathbb{C}^{n}$. In ...
user avatar
0 votes
0 answers
9 views

How does constraining all columns of a transformation to have unit norm imply a unique solution? [closed]

I'm not adept at mathematics and just wanted to get an intuitive reason for this in order to understand
user avatar
0 votes
0 answers
15 views

Convex optimization with linear constraints. Can I solve it through KKT?

I have a constrained convex optimization problem with linear equality and inequality constraints. Minimize \begin{equation} \label{eq:costf} f(x_1,\dots,x_m) = \sum_{i=1}^m \frac{1}{x_i} \end{...
user avatar
0 votes
1 answer
52 views

Question on designing a binary (integer) programming problem

Given a vector $c\in\Re^n$ and a vector $b\in\Re^n$, I would like to design a binary programming problem, \begin{equation} \max_{x\in\{1,0\}} c^\top x \end{equation} and for constraints, I need all ...
user avatar
0 votes
0 answers
31 views

A lipschitz function $f(x)$ valued in the unit ball has almost everywhere Frechet derivative orthogonal to $f(x)$ if $\|x\|=1$.

Consider a function $f:R^n\to R^m$ valued in the unit ball $B=\{u\in R^m: \|u\|=1\}$. Assume $f$ is Lipschitz. By Rademacher's theorem, $f$ is differentiable almost everywhere, i.e., for almost every $...
user avatar
  • 1,070
0 votes
0 answers
29 views

Optimize Constrained L1 Objective

I am looking to see if it possible to optimize the following objective: Minimize $(\| Ax - b \|_1) + (\| Ax - c \|_1)$ wrt to $x$ such that $\| x \|_1 = 1$ and all elements of $x$ are nonnegative. $A$ ...
user avatar
1 vote
1 answer
62 views

Reexpress $\frac{\partial^2 z}{\partial X_i \partial X_j}$, where $z(X, Y(X))$ subject to $\frac{\partial z}{\partial Y} = 0$ as a function of $X,Y$?

Consider $C_{ij}$, the second derivative of $z(X, Y(X))$ with respect to $X$: $$C_{ij} = \frac{\partial^2z}{\partial X_i \partial X_j}$$ where $Y$ satisfies the set of equations $$\left. \frac{\...
user avatar
  • 15
0 votes
0 answers
27 views

How to maximize the geometric mean? - SLSQP would be correct?

I am trying to find a set of weights for each asset in the portfolio, that would give me the highest geometric mean, with only the constraint that all weights must sum up to 1. I'm currently using the ...
user avatar
0 votes
1 answer
40 views

Number of Combinations for Patients and Hospitals

I thought of the following problem. Suppose medical patients can have the following characteristics: Smoking Status: Often, Never, Sometimes Weight: Overweight, Underweight, Healthy Age: Child, ...
user avatar
0 votes
1 answer
17 views

Model Predictive Control with integral (end-of-horizon) constraints

Let $\mathscr T = \{0,1, \ldots, T\}$ denote the entire time horizon, $x : \mathscr T \to [0,1]$ the state and $u : \mathscr T \to \mathbb [0,1]$ the control. Consider the following problem: \begin{...
user avatar
  • 732
0 votes
0 answers
14 views

Optimization Algorithm for Continuous Objective but Binary Nonlinear Constraints

Is there an derivative-free local optimization algorithm for a continuous function with nonlinear constraints, where the constraints are binary? In other words: $$ \max_{x \in \mathbb R^n} f(x) $$ ...
user avatar
  • 1
0 votes
1 answer
23 views

How to understand this Local Minimizer solution?

I have the following problem : Let $f: \mathbb{R}^{2} \rightarrow \mathbb{R} ; f\left(x_{1}, x_{2}\right)=5 x_{2}$, let $\Omega=\left\{x \in \mathbb{R}^{2}: x_{1}^{2}+x_{2} \geq 1\right\}$, and ...
user avatar
  • 119
0 votes
1 answer
27 views

Interchange differentiability and argmin of a convex restricted problem

I would like to know if it is possible to give conditions under which $g(\theta)$ is twice-differentiable, where: $$ g(\theta) = argmin_{\eta \in \mathcal{B}} \sum^n_{i=1}\left(y_i - \sum^R f(\theta,...
user avatar
  • 11
1 vote
1 answer
33 views

How to solve a max CSP with a set of linear constraints?

Suppose there is a set of $n$ linear constraints $\{a_i^Tx+b_i\le 0\}_{i=1}^n$ with $a_i\in\mathbb{R}^d$, $b_i\in\mathbb{R}$, $x\in\mathbb{R}^d$. How can I find $x^*$ that maximizes $\vert \{i\in [n]\...
user avatar
  • 49
0 votes
1 answer
41 views

Feasible descent

Consider a NLP $\min\{f(x): g(x) \le 0\}$. There are no equality constraints. The problem is feasible for small steps $t > 0$. I have to prove that $g(x + td) \le 0$ if $g(x) < 0$, where $t$ is ...
user avatar
  • 3
0 votes
0 answers
29 views

Laplace's equation with the inner unclosed edge

Hello I'm Owen and I'm new here. Recently I was working on a boundary element problem about the Laplace equation. The basic Laplace equation is as follows: $$ \left\{\begin{array}{ll} \Delta \varphi=0 ...
user avatar
  • 1
0 votes
0 answers
21 views

converting If conditions to linear constraints

I have an optimization problem and I want to convert the following if conditions to linear constraints: If $(y_1 > U_1)$ and $(m_1)$ and $(E_1)$ then $x_1=1$ If $y_2 > U_2$ and $(m_2)$ and $(E_2)...
user avatar
  • 1
1 vote
1 answer
34 views

How can I convert a non-linear constraint to a linear constraint for the mixed integer programming?

I have a nonlinear constraint: $\sum\limits_{i\in N}\sum\limits_{j\in J} A_{ijt}\times Z_{ijt}\geq \sum\limits_{i\in N}\sum\limits_{j\in J} D_{ij} \hspace{0.5cm} \forall{t}$ Here, $Z_{ijt}$={0,1}; $...
user avatar
  • 15
1 vote
0 answers
26 views

How to bundle pairs of trips?

I have a database of real-time trip demands: ...
user avatar
  • 47
0 votes
0 answers
9 views

Speed adjustment on a given path for cost minimization with fixed departure and arrival time

I have an optimization problem which consists in going from a departure point to an arrival point given a set of predefined intermediate points between the departure and the arrival. The departure and ...
user avatar
  • 1
1 vote
0 answers
47 views

Solve the minimization problem using subdifferentials on a non-differentiable continuous function subject to two constraints

This is a desmos plot of the problem I am exploring: https://www.desmos.com/calculator/0rxekqcj26 My first question is how to find the subdifferential of $f(x,y) = \max\{|x|, y + 4\}$. From my ...
user avatar
0 votes
0 answers
15 views

Range of z for convex constraint?

What would the range of z be if this were to be a convex constraint? $2x_1^2 + (2+z)x_2^2 - x_3^2 \leq 5$ I thought it could be approached by applying the two conditions of a convex hull (i.e, the ...
user avatar
  • 1
0 votes
0 answers
10 views

Linear Programming- Three products, four workshops, and a limited supply of unique components.

Say I have three products, 1, 2, and 3. There are four workshops (A,B,C,D) that build these 3 products. Product 1 must be processed in workshops A and B Product 2 must be processed in workshops A and ...
user avatar
0 votes
0 answers
23 views

Linear Programming- A shipment of three products in a cargo plane.

Suppose we want to maximize revenue in the following situation. We have 3 shipments of products. Shipment one: ...
user avatar
0 votes
1 answer
40 views

Minimize function with respect to constraint

Consider the function $ f(a) =\sum_{k=1}^N \|a- x_k\|^2$, where $a, x_k \in \mathbb{R}^d$, which we want to minimize w.r.t. $\|a- c\|^2=1$ Building the lagrangian yields: $\sum_{k=1}^N \|a- x_k\|^2 + \...
user avatar
  • 451
1 vote
1 answer
31 views

Maximum Entropy Distribution with Asymptotic

Set $P(x)$ as probability distribution function, which satisfies(constraints) $x\in[0,1]$ $P(x)\ge 0$, $\int^1_0P(x)dx=1$ $P(x)\rightarrow x^2$ while $x\rightarrow 0$ $P(x)=P(1-x)$ Then, how to find ...
user avatar
  • 48
0 votes
0 answers
23 views

For optimization problems, is the complementary slackness constraint really necessary?

I am dealing with a bilevel optimization problem, and to solve it I am applying the Karush–Kuhn–Tucker conditions to the inner optimization problem. As a result, I can reformulate my bilevel ...
user avatar
0 votes
0 answers
39 views

Multinomial distribution expectation with constraints

I'm trying to calculate (code-wise) the expectation of a multinomial distribution under specific constraints and I haven't been able to find a close formula for this. To be more precise, I have a r.v $...
user avatar
  • 1
3 votes
0 answers
104 views

Closed form solution for a quadratic program in matrix form with inequality constraint

Is there a closed form solution for the following quadratic program with inequality constraint? Let $P \in \mathbb{S}^n_{++}$ be a symmetric positive definite matrix, and $B$, $F \in \mathbb{R}^{k \...
user avatar
  • 710
0 votes
0 answers
37 views

What does "rank one" in "rank one constraint system" mean?

Rank one constraint system (r1cs) is heavily used in zk proof, but I didn't find anywhere detailing where the rank comes from.
user avatar
  • 147
4 votes
1 answer
43 views

Why are constraints distinct from cost functions in nonlinear programming?

In virtually all handling of optimization, constraints are distinct from cost functions. In optimisation problems like linear programming, this is a necessity, as the linear cost functions cannot ...
user avatar
  • 3,081
1 vote
0 answers
30 views

I encountered a Knapsack-like problem on maximizing the weight of polynomial combinations. Is this problem NP-complete?

Let $n$ be a natural number $\geq 2$ and for each $i = 1 \ldots k$ let $P_i(x)$ be a polymomial modulo $x^n - 1$ with non-negative integer coefficients. The weight $w(P(x))$ of a polynomial $P(x)$ is ...
user avatar
2 votes
1 answer
52 views

Should I Express Optimization Goals via Objective or via Constraints?

I have $k$ reasonably smooth functions $f_i : \mathbb{R}^n \to \mathbb{R}$ and corresponding targets $t_i \in \mathbb{R}$ as well as a regularization term $r : \mathbb{R}^n \to \mathbb{R}$. I want to ...
user avatar
  • 145
0 votes
0 answers
12 views

Regularizing Jacobian by altering the differentiated function?

I have a function $f$ such that I want to solve for a linear system with its Jacobian: $$ \left[\frac{\partial f}{\partial x}\right] a = b $$ I want to impose constraints to $x$ so that the space ...
user avatar
0 votes
1 answer
18 views

Why does the solution of a problem with an equality constraint would remain at least a local solution if that constraint were removed?

To perform constrained maximization, we can construct the generalized Lagrange function of $-f(x)$, which leads to this optimization problem: $$ \min _{x} \max _{\lambda} \max _{\alpha, \alpha \geq 0}-...
user avatar
3 votes
2 answers
103 views

Maximize parameter $a$ such that inequality is still satisfied

Consider the following inequality $$ax^5 -bx^2 +2x -1 \leq 0$$ with the following constraints on the parameters $a,b$ $$a>0\\ b\in \left(0,\tfrac{1}{2}\right)\\$$ and the constraint on the variable ...
user avatar
  • 419
0 votes
0 answers
76 views

Risk constraints in Portfolio Selection Linear Programming problem

Stock1 Stock2 Stock3 Interest 0.01 0.02 0.03 Risk 0.04 0.05 0.06 Knowns: Amount to invest: 200 Amount to invest/stock: <= 100 Expected min ROI: 0.05 Expected risk: min Expected ROI: >= 0.05 ...
user avatar
  • 101
0 votes
1 answer
30 views

when applying lagrangian multiplier, why is the influence of constraints always assumed to be "linear" and independent

This might seem to be dumb, but when I was taught to apply Lagrangian multiplier in class, the first step is always set up the Lagrangian function for single & multiple constraints $${\...
user avatar
1 vote
1 answer
38 views

Euler-Lagrange equation for a constant generalized coordinate

I have an action integral that I want to optimize of the form $$ S = \int_0^T \left( a(t)q^2 -2b(t)q + \gamma \dot{q}^2 \right) dt \,. $$ I know that in fact $\dot{q} = 0$, in which case the critical ...
user avatar
  • 65
0 votes
0 answers
33 views

Do Modern Optimization Algorithms "Ignore" Duality?

In traditional optimization problems, the idea of "duality" was of great importance - from a Linear Programming perspective, "duality" allows us to potentially simplify solving ...
user avatar
  • 1,692
1 vote
2 answers
107 views

$a + b + c + d = 1$ and $a^2 + b^2 + c^2 + d^2 = \frac{1}{3}$, where $-1 \le a,b,c,d \le 1$. Which value of $a$ is the largest possible?

I'm a complete novice who honestly has no clue about how to solve these types of problems. This question was originally multiple choice, and I was able to get the answer $\frac12$ simply through ...
user avatar
1 vote
0 answers
50 views

minimization of a functional using lagrange multipliers

I have some trouble in understanding the origin of lagrange multipliers for minimization of a functional with some constraints. I would appreciate if anyone could clarify this in detail. The ...
user avatar
1 vote
3 answers
152 views

How do I solve $\sin{a} + \sin{b} + \sin{c} = 2 \land \cos{a} + \cos{b} + \cos{c} = 2 $?

How do I solve $\sin{a} + \sin{b} + \sin{c} = 2 \land \cos{a} + \cos{b} + \cos{c} = 2 $? I tried the following in Mathematica, but it did not give any solutions. I would appreciate an analytical ...
user avatar
  • 121
3 votes
0 answers
53 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 ...
user avatar
  • 1,692
2 votes
0 answers
36 views

How to choose the penalty coefficient when solving constrained optimization problem?

I was wondering why don't we select a very large number to a penalty function $c$ of the augmented function $f(x) + cP(x)$ instead of doing algorithms to increase c slowly? I know that as $c$ is large ...
user avatar
1 vote
0 answers
43 views

Minimum of an inequality-constrained quadratic program

Let $A$ be an $n \times n$ strictly positive definite matrix with strictly positive entries. Let $c \in \mathbb{R}^n$ be an arbitrary vector. $$\begin{array}{ll} \underset{x \in \mathbb{R}^n}{\text{...
user avatar
  • 41
0 votes
0 answers
15 views

Specifying Relations with Binary Constraint Networks

I was reading Constraint Processing (2003) by Rina Dechter. In Chapter 2, it discusses representing relations with binary constraint networks and it says the following: In fact, most relations cannot ...
user avatar
9 votes
1 answer
153 views

Maximizing $\int_0^\infty (1+xy')^2e^y dx$ subject to $\int_0^\infty e^ydx = 1$

I'm trying to solve a calculus of variations-type problem, which requires finding the extrema of: $$\int_0^\infty (1+xy')^2e^y dx, $$ subject to the constraint that $\int_0^\infty e^ydx = 1$. ...
user avatar
  • 323

1
2 3 4 5
18