Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
223
questions
0
votes
0answers
28 views
Discretizing a Non-Linear Continuous Adjoint Equation
I am trying to follow the derivation of the tangent linear / adjoint matrix for the following equation:
$$ \frac{\partial u}{\partial t} = \frac{\partial u}{\partial x} \frac{\partial u}{\partial y} $...
1
vote
0answers
41 views
Setting up optimization problem in GEKKO
I have the following dynamical system,
$\frac{d \phi}{dt} = -M^TDM\phi \tag{1}\label{1}$
$\frac{d \hat\phi}{dt} = -M^T\tilde{D}M\hat \phi \tag{2} \label{2}$
$\eqref{1}$ represents the exact ...
-1
votes
0answers
18 views
One to Many Assignment Problem where agents can't be assigned the same task if they share a trait
In the one to many assignment problem, many agents can be assigned to a task. In my problem, I want to assign many agents to a task, but for all of the agents assigned to that task, they must share a ...
-1
votes
0answers
48 views
What is going wrong in the way I set up constraints for optimization solver?
I have the following dynamical system,
Equation 1:
$\frac{d \phi}{dt} = -M^TDM\phi$
Equation 2:
$\frac{d \hat\phi}{dt} = -M^T\tilde{D}M\hat \phi$
Equation 1 represents the exact dynamics of a ...
2
votes
0answers
33 views
Lexicographically order matrix into a vector
I am trying to implement the algorithm contained in this article here. It is about solving a 2 and 2.5D Fredholm integral, focused on bidimensional NMR experiments. I've made significant progress, ...
3
votes
0answers
107 views
Automatically generate constraints for trajectory optimization
This is a follow up to my previous post here
I'm interested in performing trajectory optimization from the problem mentioned in abov link.
I want to supply the following as dynamical constraints to ...
1
vote
2answers
96 views
Solving a parameter estimation problem using trajectory optimization
This is a follow-up to my previous question here
I've the following system of equations for studying information flow in the below graph,
$$ \frac{d \phi}{dt} = -M^TDM\phi + \text{noise ...
1
vote
0answers
43 views
Optimization of centers and radii of circles under the non-collision constraint
I want to optimize a function w.r.t. $n$ circles parametrized by centers and radii:
$$\min_{C, R} f(C,R)$$
where $C\in\mathbb R^{n \times 2}$ and $R\in\mathbb R^n$. For example,
...
4
votes
1answer
175 views
Underdetermined Minimum Volume Enclosing Ellipsoid
Given three vectors in $\mathbb{R}^{512}$, my task is to compute a Minimum Volume Enclosing Ellipsoid (MVEE). I have tried Kachiyan's algorithm, but it requires at least as many vectors as there are ...
2
votes
1answer
64 views
Optimization with the constraint of rank=1
I have the following matrix
$$ A = [x_1, x_2, ..., x_n], $$
where $x_i \in \mathbb R^n$. But I know the relationship that
\begin{align}
x_2 = s_2 x_1 \\
x_3 = s_3 x_3 \\
...
\end{align}
where $s_i$...
2
votes
1answer
50 views
Could the convex problem be tackled by CVX?
I want to solve the convex optimization as follows:
\begin{align}
\underset{X_1,X_2}{\min} &\ -\frac{1}{N}\sum_{i=1}^N\log\det\left(I+H_i^HX_2H_i\right)-\log\left[1+h^H(X_1+X_2)h\right]\\
&\...
2
votes
1answer
84 views
Gradient descent in constrained optimization of barrier function
This question may be too basic, but I was wondering if it is possible to implement simple methods such as gradient descent or its variations to find the minimum of barrier functions in constrained ...
6
votes
2answers
136 views
How to solve calculus of variations problems numerically?
For example, how to solve the well-known isoperimetric problem (i.e., to enclose the largest area with a fixed-length curve)?
We can simplify things a bit and fix the two ends of the curve at $[a,0]$,...
0
votes
1answer
58 views
Analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^T A z$, where $A=uu^T+vv^T$
Let $u$ and $v$ be column vectors of size $n \gg 1$ (not both zero), and consider the matrix $A:=uu^T+vv^T$
Question
What is an analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^TAz=\arg\max_{\|z\...
1
vote
0answers
66 views
Ramp least squares estimation
With some given $s$ value, let
\begin{equation}
\begin{aligned}
h(\beta)&=\min(\sum_{i=1}^n(Y_i - X_i\beta)^2, s)\\
&=\sum_{i=1}^n(Y_i - X_i\beta)^2-\max(0, \sum_{i=1}^n(Y_i - X_i\beta)...
4
votes
3answers
130 views
Maximize a function of an orthogonal matrix
I'm trying to write up a small code that, given a set of normal vibrational modes for a molecule, will convert them to localized vibrational modes. To do this I'm following the procedure from J. Chem. ...
0
votes
0answers
46 views
Least square approximation of a polynomial with a constraint on the derivative in Python
I'm trying to fit a polynomial of the third degree through a number of points. This could be a very simple problem when not constraining the derivative. I found some promising solutions using CVXPY to ...
1
vote
0answers
14 views
Long AMPL model preparation time
We deal with a large-scale linear optimization problem (~50000 variables and ~4000000 constraints). We use AMPL Studio modeling environment for problem modeling and then calling linear solver (CPLEX, ...
1
vote
0answers
35 views
Minimizing a polynomial with millions of monomials
I need to minimize a single polynomial $P(x_1,x_2,...,x_n)$ with the constraint that for each $i$, $0\leq x_i \leq 1$. The number of variables in my practical problem is at most $50$. The degree is at ...
3
votes
0answers
27 views
How to set up and solve acceleration-limited trajectory optimization problems?
I've been trying to learn how to solve simple acceleration-limited trajectory planning problems. I'm working in C++ and I've been using the Eigen library to do linear systems solving. I'm doing the ...
3
votes
0answers
21 views
Sequence planning with 3 machines
together!
First of all, I have to mention that because of my background as an Industrial Engineer, I have limited abilities in mathematics, but am disciplined enough to expand myself from ...
2
votes
1answer
189 views
Simultaneously maximize and minimize
I am virtually new to optimization (saw it years ago in a very shallow course) and now I came across a problem that I believe would require from it. The problem is I don't know exactly how to proceed.
...
3
votes
0answers
48 views
Constraint solver vs Bayesian optimizer for fast discontinuous processes
I have a complex domain-specific process that accepts inputs:
10-500 inputs, where each input is of type:
enum: choice between multiple string or numeric values
int: integers
float: floating point ...
0
votes
0answers
42 views
Optimization (best input variables search) for a non-smooth non-linear unknown function
I am trying to optimize a system that monitors and advises a user multiple times over a certain period of time depending on changing outside factors. The systems behavior can be altered by 5 ...
5
votes
0answers
95 views
How to solve a 4th order nonnegative LASSO problem?
I need to solve the following 4th order nonnegative LASSO problem:
$$
\min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1
$$
where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e....
4
votes
0answers
65 views
Fast approximate solver for vehicle routing problem
I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
2
votes
1answer
79 views
How to add extra constraints to a linear system for probabilitiesļ¼
Backgroundļ¼
I have an equation which looks like as follows:
$W \times P = R$
$$\left[\begin{array} &{1}&{0}&{0}&-\frac{w_{1}}{w_{o1}} &\dots &{0} &-\frac{w_{1}}{w_{0} } \...
0
votes
0answers
144 views
Solving a non-convex optimization problem using fmincon
I am trying to solve a non-convex optimization problem using fmincon().
At each iteration, I am iteratively looking for the optimum value and when the termination ...
3
votes
1answer
122 views
Why would BFGS converge to a local minima of a non-convex function but maintain a large gradient?
I'm using BFGS to optimize a smooth but non-convex function $f$ that is computed by a simulation. The simulation also gives me a semi-analytical gradient $g$, which is verified by the numerical ...
0
votes
0answers
137 views
Augmented Lagrangian Techniques Frank-Wolfe Algorithm [python]
I'm trying to solve the convex quadratic problem (quadratic min cost flow problem) using the Frank-Wolfe algorithm.
$$ \min\{x^TQx+qx: Ex=b,\quad 0\leq x \leq u\} $$
The standard algorithm is okay ...
3
votes
0answers
74 views
Solve ODE with non-negative and maximization constraints
My task is to solve $$\eta_k\frac{d^2C_k}{dz}(z)=-e_k, k = 1,2,3$$
$$C_k\ge0$$
$$C_1(0)=0, C_2(0)=A, C_3(0)=0$$
$$C_1(L)=B, \frac{dC_2}{dz}(L)=0, \frac{dC_3}{dz}(L)=0$$
with $$e_1 = -\beta_1-\beta_3$...
1
vote
1answer
210 views
How do I solve the matrix equality constrained optimization problem using Lagrangian multipliers?
Solve the following minimization problem in $\mathbf{X} \in \mathbb{R}^{m \times n}$
$$\begin{array}{ll} \text{minimize} & \frac 12 \| \mathbf{X}\mathbf{X}^T -\mathbf{A} \|^2_\mathcal{F}\\ \text{...
2
votes
0answers
41 views
Biconvex problem whose objective function depends on only one variable
I am solving the following biconvex problem:
$$\min_{x,y} f(y)$$
$$s.t. ~~ g(x) \leq 0$$
$$~~~~~h(x,y) = 0$$
$$x \in X, y \in Y$$
where $X$ and $Y$ are compact convex sets, $g(x)$ and $f(y)$ are ...
1
vote
1answer
51 views
Vehicle Route assignment with capacity constraint
Problem Background
I'm trying to find a solution/model to the following problem:
Let's consider a cellular network (mobile network, ie., hexagonal cells) denoted $N$ composed of $|N|$ cells. Each ...
1
vote
1answer
55 views
Research articles on MultiObjective Non-Linear Programming (MONLP)
I'm looking for papers dealing with multi-objective non-linear programming which could help me implement an algorithm to solve my problem.
My problem is :
Maximize $f(x) = c \cdot x$, while ...
0
votes
1answer
63 views
Formulate and solve a simple conic programs in cvxpy language [closed]
Let $r,\epsilon > 0$ and $a, b \in \mathbb R^n$ with $\|a\|_2 \le r$. Define $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$, and assume it is non-empty.
Question
(A)...
2
votes
1answer
87 views
Question about strange outputs from the CVXPY solver
I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem:
...
2
votes
0answers
53 views
How to find two points within defined region in this constrained optimization problem?
I am doing a project related to robotics where I am using fmincon function from matlab to minimize the distance between the points ...
4
votes
0answers
76 views
Solution of constrained system of ODEs
Can someone point me in a direction to solve this kind of integral constrained system of ODEs.
\begin{align}
&\int_0^{1/2}\dot{y}^2(t)=p\\
&2\lambda_1\ddot{y}(t)+\pi cos(\pi y(t))=0\\
&y(...
0
votes
1answer
36 views
Can LINCS algorithm be used for colliding molecules?
Supposing that one molecule is static and one is dynamic,
can the dynamic one be solved with LINCS for its shape (angle, bond length) constraints and also keep collisions with static molecule off, ...
0
votes
2answers
169 views
Is this a knapsack problem?
I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
3
votes
1answer
46 views
Improve optimization speed for a set of similar problems: Quadratic programming with a warm start
I am repeatedly solving quadratic program,
$x^T Q x$ with time dependent linear constraints $Ax=b_t$.
Dimension of $x$ is around 10000 and there are around 50 constraints. I want to solve the ...
1
vote
1answer
213 views
sum of absolute difference constraint in optimization problem
I am writing a model for an optimization problem. I need to write the following constraint:
$$\sum^{N - 1}_i \lvert (a_i - a_{i+1}) \rvert \leq 2\, .$$
How to write this constraint (or linearize)?
...
1
vote
1answer
183 views
Nature of stationary points of a Lagrangian fuction
I would like to extremize a certain function $f$ with respect to a parameter $x$, under constraints $g_1(x) = 0, ..., g_m(x)=0$. In order to achieve this, I consider the Lagrangian function $L(x, \...
2
votes
1answer
64 views
Techniques to remove a function from Levenberg-Marquardt when it is against box constraints
I have a somewhat large (20+ dimensional) root finding problem that I'm solving with Levenberg-Marquardt. One of the functions has box constraints on [0, 2]. When it is against those bounds it will ...
1
vote
1answer
239 views
Why does Newton's method with Linear Equality Constraints use KKT condition?
Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint.
The problem only has equality constraint. Why ...
1
vote
0answers
34 views
Logging vs outputs in iterative optimisation
I'm coding an iterative algorithm of constrained continuous optimisation. An augmented Lagrangian algorithm (outer) calls a bound-constrained L-BFGS-B algorithm (inner), which calls a line search ...
2
votes
0answers
41 views
Sensitivity Lagrangian solution general case
I have asked this question already on maths and mathoverflow.
Just a question about a literature reference. I am writing a paper for engineers.
Usually for the Lagrange multiplier problem
$$
\...
1
vote
0answers
35 views
Efficient numerical optimization of an “almost separable” function
I have come across an optimization problem with the following objective function:
$$f(x_0,y_0,z_0,x_1,y_1,z_1,...,x_N,y_N,z_N) = \sum_{i=0}^N f_i(x_i,y_i,z_i, \alpha(x_{i+1}-x_i) + \beta(y_{i+1}-y_i))...
6
votes
0answers
153 views
An invertible matrix that minimizes the norm of the product with a given matrix
Given a fat matrix $B \in \mathbb{C}^{n \times m}$ (where $m > n$) with full row rank, I would like to find (numerically) a full-rank matrix $A$ that minimizes the Frobenius norm of the product $A ...
