Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
269
questions
0
votes
1
answer
46
views
Efficiently solving SDP relaxation of an integer quadratic program
I have an integer quadratic program of the form,
\begin{align}
\underset{x}{\max}&\;\;\|Ax-b\|_2^2\\
\text{subject to}&\;\;x\in{\bf Z}\geq0
\end{align}
I'm currently using the (admittedly ...
- 443
0
votes
0
answers
72
views
optimization problem with L2-norm constraint
I am currently trying to solve a regression problem, which leads me to an optimization problem. Say that we have measured data ($\hat{S}(\omega)\in \mathbb{C}^{N\times N}$), and each entry of this ...
- 1
0
votes
0
answers
43
views
The condtion for Augmented Langrangian Multiplier
I am currently learning the usage of Augmented Lagrangian Multiplier to achieve my equality constraint. I have learnt from the https://en.wikipedia.org/wiki/Augmented_Lagrangian_method that I have two ...
2
votes
0
answers
70
views
How is ADMM Separable?
I'm learning about ADMM by reading Boyd's paper Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers.
The paper says that ADMM is an improvement over ...
- 21
2
votes
1
answer
56
views
Linearize problem with absolute value
Is there any method to linearize the following optimization problem?
\begin{align}
min_{x,y} &~~ c~[x; y] \\
st &~~ \sum x\leq \alpha_1 \\
&~~ \sum |y|\leq \alpha_2 \\
&~~ \sum y= 0 \\
...
- 121
0
votes
1
answer
62
views
Why is a elementwise max not DCP?
I am trying to formulate a convex optimization problem using CVXPY. Everything works, except a constraint that does not seem to follow DCP rules.
Let $D \in \Bbb R^n$ be a decision variable and let $Q$...
- 43
2
votes
0
answers
56
views
Cyipopt fails to converge for NLP problem which fmincon() can solve
I'm currently trying to implement a python script for solving a constrained nonlinear optimization problem with ~800 variables and 2 constraints, one linear and one nonlinear. There already exists a ...
2
votes
1
answer
187
views
Python solvers for MINLP in Pyomo in Google Colab
I am looking for a MINLP solver that works with Pyomo models which can be used in the Google Colab environment. I have already found MindtPy but it doesn't work in google colab.
3
votes
0
answers
41
views
Sufficient condition for real roots of a polynomial of order $n>5$ with arbitrary real coefficients
I ask for help in solving the problem. I am developing an optimization program that selects the coefficients of a polynomial of order $n> 5$ so that all its zeros are just real numbers. And I ...
- 131
1
vote
0
answers
100
views
How to constrain the every optimized vector component to be nonnegative?
I am building a gradient descent model based on portfolio optimization. Currently, I have finished the model and am able to run it smoothly without any problem. However, there's one issue that I ...
0
votes
0
answers
31
views
Can line search solve linear objective with nonlinear constraints?
Consider an optimization problem of the form:
$$\max_{f(x)\le K,\\0\le x\le M} c^\top x,$$
where $f(x)$ is nonlinear. Can a line search of the following form be used to solve this problem?
$$ \max_{\...
0
votes
1
answer
62
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 ...
- 11
6
votes
1
answer
231
views
Optimization problem
In the expression:
$${\underset{\Omega}{\min}\left\|\beta A\Omega^{-1}B+C\right\|_{F}^{2}}\, ,$$
$$\text{subject to tr}(\Omega)=1, \Omega \ge 0\, ,$$
where ${\Omega}$ is nonnegative and symmetric ...
- 81
2
votes
0
answers
81
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 ...
- 21
1
vote
1
answer
57
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 ...
- 111
1
vote
0
answers
31
views
constrained zero-sum two person game
Finding the saddle point of a constrained zero-sum two-person game is equivalent to a resolution of primal-dual programs (with bi-linear objective function).
I am looking for a free solver to compute ...
- 11
1
vote
0
answers
59
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
1
answer
58
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 ...
- 13
0
votes
1
answer
67
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 ...
- 11
3
votes
0
answers
83
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 ...
- 215
1
vote
1
answer
56
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 ...
- 13
-1
votes
1
answer
92
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 ...
- 1
0
votes
0
answers
101
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 $\...
- 121
0
votes
0
answers
84
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 ...
- 1
2
votes
0
answers
85
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
1
answer
287
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. \...
- 143
2
votes
0
answers
54
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 ...
- 191
2
votes
0
answers
134
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 ...
- 21
1
vote
1
answer
228
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}...
- 141
1
vote
0
answers
70
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 ...
- 119
0
votes
2
answers
99
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 ...
- 159
3
votes
1
answer
298
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 ...
- 143
0
votes
1
answer
81
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$ ...
- 101
1
vote
0
answers
34
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 ...
- 329
0
votes
0
answers
45
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 ...
- 193
1
vote
1
answer
71
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 ...
- 13
1
vote
1
answer
155
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 ...
- 193
8
votes
1
answer
293
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
0
answers
43
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 ...
- 31
1
vote
0
answers
111
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/...
- 111
1
vote
0
answers
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 ...
- 11
4
votes
2
answers
184
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+\...
- 350
1
vote
1
answer
155
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{...
- 143
5
votes
1
answer
270
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 ...
- 51
3
votes
0
answers
55
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 ...
- 255
0
votes
1
answer
23
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:
...
- 133
2
votes
2
answers
119
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 ...
- 443
4
votes
1
answer
103
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 ...
- 41
0
votes
2
answers
125
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 ...
- 119
0
votes
1
answer
109
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 ...
- 581