Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
257
questions
0
votes
1answer
58 views
Expressing a Constraint in an optimization problem
If I have a vector of M "continuous" decision variables (say it is called x) , and if I want a constraint to express that only one of them is allowed to have a nonzero value (i.e. no more ...
4
votes
0answers
113 views
Optimization problem
In the expression:
${\underset{\Omega}{\min}\left\|\beta A\Omega^{-1}B+C\right\|_{F}^{2}+tr(W\Omega^{-1}W^T)},$ s.t. ${tr(\Omega)=1, \Omega \ge 0}$, where any element of ${\Omega}$ is nonnegative.
...
2
votes
0answers
69 views
Efficient solver of a Integer programming
I am solving an Integer programming using MATLAB, yet the efficiency is low.
Here is the problem:
Suppose $v$ is a $N \times 1$ vector. For $v_i \in v$, $v_i \in \{0,1\}$.
$D$ is a 0-1 matrix, which ...
1
vote
1answer
51 views
Overconstraining in SQP
In Sequential Quadratic Programming we use an active set of the inequality constraints and handle them as equality constraints in the quadratic subproblem.
SQP is said to be able to deal with ...
1
vote
0answers
55 views
Constrained optimization for non-linear equations in octaveGNU
I have installed Optim1.6.1 package. I would like to solve a system of equations in non linear finite element analysis using constraints as u=1 at certain nodes. u=0 at certain nodes. Typically I find ...
0
votes
1answer
46 views
Variable equality constraints in SDP Problem
I'm quite new to SDP programming, hence I might not have been able to use the right search terms to find a solution.
I try to reformulate an SDP problem to the original form. However a side constraint ...
0
votes
1answer
51 views
Maximum Constraints Satisfaction of Linear Programming
The question I need to solve is to maximize the satisfied constraints in linear programming.
To be more specific, Suppose I have an infeasible LP problem, my goal now, is to find the maximum number of ...
3
votes
0answers
59 views
High quality constrained optimization C++ library with matrix free second order solver?
I'm working with large scale constrained optimization problem. Some of my constraints can be non linear. Currently i'm using IPOPT. Quality is good by my Hessian computation too slow. It seems that i ...
1
vote
1answer
36 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
1answer
50 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
67 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
64 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
82 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
140 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
50 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
132 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
136 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
60 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
95 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 ...
3
votes
1answer
191 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
75 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
38 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
56 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
90 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
271 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
41 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
85 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
36 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
155 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
108 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
231 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
53 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
108 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
100 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
102 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
73 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
169 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
490 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
47 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
153 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
134 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
44 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
194 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
76 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
96 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
235 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
792 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
65 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\...
