Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
250
questions
1
vote
1answer
29 views
Difference between LP optimization and GLPK optimization
I've seen two different optimizers being used, but both with a different solver. One uses PULP_CBC_CMD and the other uses ...
-1
votes
0answers
28 views
QP solver which achieves very low primal infeasibility
Background: My applications is a self-written trajectory optimization tool which is actually based on IPOPT, but some nasty problems, which I use as benchmarks, prohibit IPOPT from converging. In ...
-1
votes
1answer
34 views
Is there an overview of the runtime speed up of LP/MIP solvers throughout the years?
whenever I read papers on OR that use an LP/MIP approach, they include the time solver used, as well as the version and the year. I would like to know how much faster the same experiment would be ...
0
votes
0answers
52 views
CVXOPT intermediate step valuation stepping out of function domain of defintion
I am using CVXOPT, particularly to solve a nonlinear convex optimization problem. Either the objective function or the constraints involve some functions that are only defined in a strict subset of $\...
0
votes
0answers
50 views
L2 norm optimization problem
I have an optimization problem where i need to find an image x, that is very close to x' such that:
monitor(x') is valid but monitor(x) is invalid. (output is valid
when the neural network output is ...
2
votes
0answers
79 views
Finding the extrema of a transition probability function for a quantum walker on a graph
The goal
Implement some Python code to find the extrema points of a function that is strongly oscillating.
The background
Let $G$ be a connected graph with $n$ points with Laplacian matrix $L(G)$. We ...
4
votes
1answer
67 views
SCP (Sequential Convex Programming) vs SQP (Sequential Quadratic Programming)
Can someone explain me at a high level the difference between an SCP and an SQP to solve a nonlinear (nonconvex) program?
Assume my problem is something like
$$\min\limits_x. \quad f(x)$$
$$s.t. \...
2
votes
0answers
48 views
Model and solve nutrition optimization problem: how to?
How to solve/assess the following problem?
Given: $N$ ingredients like apples, bread etc. Mass of an ingredient $j$ is in this simplified model a sum of macro nutrients carbohydrates, proteins and ...
2
votes
0answers
131 views
Parametric nonlinear programming
I believe, I have a parametric nonlinear optimization problem.
The non-convex constraints depend on some parameters, and I seek a solution that satisfies these constraints for all parameters in a ...
1
vote
1answer
84 views
How to best code a problem with scipy, cvxpy or Convex.jl with given generated data
I have a curve fitting problem of the form:
$$
\textbf{y} = f(\textbf{x}, a,b,c,d) + \varepsilon
$$
$$
f(x, a,b,c,d) = \frac{b}{e^{x\cdot a}+c}+d
$$
with the constraint
\begin{equation}
\begin{aligned}...
1
vote
0answers
59 views
How applying the gradient descent method for solving a least square problem can remove the blur from an image?
I got an assignment where it asked to implement (in MATLAB) the gradient descent algorithm in order to resolve an ill posed least square problem:
$$
\min_u \Vert Gu - f \Vert
$$
where $u$ is the ...
0
votes
2answers
93 views
How to determine guitar tones played as early as possible?
I want to detect chords on a guitar as early as possible, but my approach with a sliding window and a filter bank seems to introduce too much lag.
Would required observation time decrease by using a ...
2
votes
1answer
103 views
Good languages/packages for interior point optimization with non-linear constraints?
I'm currently using Python's scipy.optimize package to perform parameter estimation for a system of 10 ODEs. I have some observed data, and I'm trying to find the set of parameters which makes the ODE ...
0
votes
1answer
73 views
How can I deal with optimization problems that have a sum of functions of Z as a constraint when Z is the quantity to be minimized?
I have a problem where I have to minimize a certain quantity $Z$ subject to the following constraints:-
$w_1 + w_2 + w_3 = 1$
$\frac{f_1(w_1*Z) + f_2(w_2 * Z) + f_3(w_3 * Z)}{Z} >= k$
where $k$ ...
1
vote
0answers
29 views
Bipartite Euclidean Matching simple to implement approximate algorithm
I am looking for a simple to implement algorithm for the bipartite euclidean matching problem (or an implementation of any practical algorithm). I am aware of Agarwal's paper, but I would like to ...
0
votes
0answers
36 views
Implementation method selection for sparse constrained linear least squares or quadratic programming
I need to slove one optimization problem of quadratic programming. The number of optimization variables is about 16,000. The constraints include equality constraints and inequality constraints.
I have ...
1
vote
1answer
53 views
Constraint programming problem with conditional constraints and some unknown indicator variables
I have an interesting little problem that I believe can be formulated in terms of optimization or constraint programming. I have a few dozen variables $a$, $b$, $c$ ... and a set of constraints that ...
1
vote
1answer
45 views
Why is quadratic penalty method used for equaltiy-constrained optimization?
When one equality-constrained optimization is formulated, the method of Lagrange multiplier will be the choice for me. In Chapter 17 from the book Numerical Optimization, quadratic penalty method can ...
8
votes
1answer
245 views
Can this simple quadratic optimization problem be turned into a simple eigenvalue problem?
I'm interested in a type of problem on this form
$$\min_{x} x^{T}Ax+x^{T}b \quad \text{s.t} \quad x^{T}x=1 $$
where $A$ is positive definite. As you can see, if it weren't for the $x^{T}b$ term in the ...
0
votes
0answers
39 views
Balanced constraint
In several optimization problems, we found what we called the balanced constraint(c^T • x = z )
For exp: C^T • 1 = 0 (C is a binary Matrix)
Can I have an intuitive explanation about the concept and ...
1
vote
0answers
62 views
How to speed up the Mixed-Integer Quadratic Program process?
Currently, I am solving a problem in the format:
M is an integer as well. The problem that troubles me is that X is a vector in {0,1} with a size of 7000. I use the solver in https://github.com/...
1
vote
0answers
35 views
What is the generalization of the resource allocation problem I'm dealing with here?
I'm dealing with a problem as follows:
I have a finite set of money 𝑚 to spend over 𝑟 different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
4
votes
2answers
151 views
Solve two-player game - minimize the l-infinity norm of a matrix-vector product
I have a matrix $M$ with non-negative real entries, and I would like to minimize the objective function
$$\Phi(v) = \|Mv\|_\infty,$$
where $v$ is constrained to be a probability vector, i.e., $v_1+\...
1
vote
1answer
73 views
Linear system with an l1-norm constraint
I have a saddle-point system of the form
\begin{equation}
\begin{bmatrix}
A & B \\
B^T & O
\end{bmatrix}\begin{bmatrix}
x\\
y
\end{bmatrix} = \begin{bmatrix}
f \\ \vec{0}
\end{bmatrix},
\end{...
5
votes
1answer
165 views
Non-negative least squares with very small numbers
(I have asked this question on StackOverflow previously but it has been pointed to me that CSSE or MSE could be more appropriate)
I have to solve a constrained optimization problem of the following ...
3
votes
0answers
51 views
Least-squares fit of explicit parabolic sheet to data points
For a given set of data points
$$\{(x_i, y_i, z_i)\}$$
there exists some
$$f_{ABC}(x,y)=Ax^2+Bxy+Cy^2$$
that minimizes
$$\sum_i(f_{ABC}(x_i,y_i)-z_i)^2$$
$A$, $B$, and $C$ can be found quickly ...
0
votes
1answer
22 views
Python: Getting second output variable from minimizing a computationally intensive function on first outputs
I have a function in python that is quite computationally expensive to evaluate, of the form:
...
2
votes
2answers
105 views
Using MILP to place a set of primers along a genome
Define variables $p_i,u_i\in\{0,1\}^G$, for $i=1,\ldots,8$ and $G=30000$.
Let $v$ be a constant vector also in $\{0,1\}^G$, with approximately 25% of its entries equal to $1$ (randomly located).
Let ...
4
votes
1answer
88 views
Plotting optimum as a function of parameter in the objective
I am trying to minimize a 2d function using scipy.optimize. Specifically I want to plot the minimum value of the function fun as a function of the parameter wjk. The problem is that I cannot pass wjk ...
0
votes
2answers
94 views
How to minimize $(x-a)^2+(y-b)^2$ subject to $ \sqrt{a}+\sqrt{b}=\sqrt{2}$?
I am not sure if this is on-topic here, but I am trying.
Let $x,y$ be positive real numbers. I am trying to find
$$ \min_{\sqrt{a}+\sqrt{b}=\sqrt{2}}(x-a)^2+(y-b)^2$$
I tried using Mathematica for ...
0
votes
1answer
53 views
Avalability of SNOPT optimization solver
I'd like to know if SNOPT solver is available free of cost for academic research in any of the optimization software packages.
I came across a few softwares that have SNOPT, but those require a ...
4
votes
1answer
132 views
What's the right choice of variable settings for setting up my optimal control problem?
This is a followup to my previous question here
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} \...
3
votes
1answer
322 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 ...
2
votes
0answers
41 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
141 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
119 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
180 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
67 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
85 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
179 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 ...
7
votes
2answers
611 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
64 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
70 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)...
5
votes
3answers
273 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. ...
1
vote
0answers
17 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
36 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
28 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
22 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
656 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.
...
