Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
297
questions
0
votes
0
answers
35
views
Methods for delaying the "break" in non-linear least squares optimisation when the step size gets too small?
I am using the Levenberg-Marquardt method for calibration purposes. Typically, the RMSE of my calibration looks like:
I want to break the algorithm when the algorithm step-updates start to slow down, ...
1
vote
0
answers
27
views
Constraints involving max in ILP
Consider $n$ apps and $m$ transactions. $x_{ij}$ is a binary variable, it takes 0 or 1. $x_{ij}$ takes 1 if $i$th app is used for $j$th transaction, else 0.
min $\sum_{i=1}^{n}\sum_{j=1}^{m} x_{ij}$
...
- 11
5
votes
1
answer
363
views
The nitty-gritty details of augmented Lagrangian methods
I am trying to implement (constrained) minimization of a certain function with the augmented Lagrangian method. Where can I find a reference that discusses in detail the good practices for the various ...
- 11.2k
1
vote
1
answer
40
views
Name this optimum-within-convex-hull algorithm: State is a convex combination of hull vertices; Nonnegativity ensured by reparameterization
I'm looking for the "official" name(s) for a procedure for optimizing a convex loss function over a convex subset. This seems to be a default/naïve algorithm that folks come up with before ...
- 153
1
vote
0
answers
39
views
Find a minium value of a function with discrete parameters, but some combinations are invalid
I'm not a mathematician, so sorry if I miss some obvious stuff. I'm trying to develop a bot for StarCraft 2, in particular the army control for it. For every army of the enemy, I want to find the ...
- 111
1
vote
0
answers
50
views
Beyond the LP relaxation of binary least squares
I have a binary quadratic program with a convex objective function, of the form,
\begin{align}
\text{minimize}\;\;& x^tAx+b^tx\\
\text{subject to}\;\;& x_i\in\{0,1\}
\end{align}
where $A$ is ...
- 471
3
votes
0
answers
98
views
Implementation of the roller constraint
What could be the best way to implement the roller constraint in finite element code, i.e. constraint of the type
$$\mathbf{u} \cdot \mathbf{n} = 0$$
I plan to enforce it in the weak sense by ...
- 229
1
vote
2
answers
164
views
Optimization Problem with Array Index as decision variable
I am trying to formulate an optimization problem where the decision variable is an index of the input array as part of the formulation.
For example, I have the following term (this is simplified):
$A[...
- 131
2
votes
1
answer
150
views
Numerical Simulation of a Quadratic MIP with a highly rational term
I am interested in solving the following minimization problem:
$$
\begin{array}{cl}
\displaystyle\min_{x,y}&\displaystyle\frac{1}{K}\sum_{i=1}^{K}\left(\frac{x_{i}}{y_{i}}-\frac{X}{Y}\right)^{2} \\...
- 169
1
vote
1
answer
91
views
Possible bug with scipy.optimize SHGO sobol: TypeError: <lambda>() takes 1 positional argument but 3 were given
I have been trying to perform some global optimization with SciPy optimizer SHGO
and I've had issues with the sampling method 'sobol'. Specifically, I get an error ...
- 31
2
votes
0
answers
98
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at MathOverflow
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
where $D$ is a $...
- 21
2
votes
2
answers
706
views
Why does `scipy.optimize.minimize(...)` fail with this toy constrained minimisation case?
I'm learning scipy.optimize.minimize. I thought of a simple function to see how it works:
$$f(x) = x$$
With the goal to minimise $f(x)$, subject to the constraint ...
- 123
0
votes
0
answers
18
views
Toggling Constraints in Mixed Integer Programming
Are there MIP solvers that allow certain constraints to be toggled based on the value of a binary variable? My current situation is that I'm approximating the desired behavior by using constraints of ...
- 1
1
vote
0
answers
47
views
Vehicle passenger assignment with capacity constraint
Problem Background
I'm trying to find a solution to the following passenger matching problem:
The network is represented by graph $G=(V,E)$. $V$ is the set of nodes/stations. $p_{ij}$ is the profit of ...
- 11
3
votes
1
answer
275
views
What problems does softmax() solve and when should I think of using it - in simple terms
I just for the first time saw the function softmax() in this SO answer to How do I use a minimization function in scipy with constraints and was intrigued.
Another way of weighting variables where ...
- 1,026
0
votes
1
answer
58
views
KKT conditions calculation for bound constrained steepest descent topology optimization
How could one calculate the KKT conditions in the case of bound-constrained optimization?
In the general sense, given an objective function $J$ and design variables $x \in \mathcal{R}^n$, we consider ...
0
votes
2
answers
164
views
Minimize ||AX - Y|| for a matrix A that lies in a special orthogonal group
Let $X$ and $Y$ be two given $k\times n$ real matrices. If $A$ is a $k\times k$ real matrix then $AX - Y$ is a $k\times n$ real matrix. Applying the Frobenius norm $\| AX - Y \|$, we get a non-...
- 109
0
votes
0
answers
27
views
How to obtain the unitary operator to get specific partial trace using searching methods?
Is there a unitary $U_{AB}$ such that, for any density operator $\rho$, we have
$${\rm {Tr}}_A \left[U_{AB} \left(\frac{I_A}{2} \otimes \rho_B\right)U_{AB}^{\dagger}\right]= \frac{\rho_B}{2}+\frac{I_B}...
- 101
-1
votes
1
answer
86
views
what is this general form of an optimization problem (Structural) representing?
I am currently reading this article by Sigmund.
Sigmund, O., Maute, K. Topology optimization approaches. Struct Multidisc Optim 48, 1031–1055 (2013). https://doi.org/10.1007/s00158-013-0978-6
I ...
6
votes
1
answer
205
views
Minimum distance from point to surface
I’m looking for code that is well-suited to solving a fairly simple minimization problem:
I have a reference point $\mathbf p$ in 3D space, and I want to minimize $\|\mathbf x - \mathbf p\|^2$ subject ...
- 119
3
votes
2
answers
728
views
Why slack variables for inequality constraints?
When solving constraint optimization problems with (primal dual) interior points methods, I often read (e.g. on slide 17) that one should not use the inequality constraints $g(x)\leq 0$ directly, but ...
- 241
2
votes
1
answer
112
views
Objective function for PDE-constrained boundary control problem in cylindrical coordinates
I'm interested in solving a boundary control problem for an axisymmetric diffusion problem where diffusive fluxes only appear radially. The corresponding problem for a uni-dimensional slab can be ...
- 544
1
vote
0
answers
195
views
SLSQP solver scipy with linear subset constraints
I have been trying to solve a least squares problem of the following form:
$$
\begin{equation}
\min_{\vec{x}} \frac{1}{2} \lVert f(\vec{x}) - f_{\text{target}} \rVert_{2}^2 + \alpha\Big( \frac{1-\rho}{...
- 11
0
votes
1
answer
89
views
How are topology optimizations validated?
How are topology optimizations validated?
I've been confused. Doesn't this mean that each of such design (e.g. N=100) would still need to be validated empirically or is there something that allows one ...
- 427
1
vote
0
answers
92
views
Using absolute error as the cost function
This is related to my previous post Minimize distance between curves.
I have a dataset with values of multiple curves. An example plot is shown below.
I want to scale the curves (move up/down) so that ...
- 421
5
votes
1
answer
91
views
Software for Feasibility Problems
I face a feasibility problem of type
$$ c_i(\boldsymbol x) \leq 0, i = 1, \dots, \mathcal{I} \\ c_e(\boldsymbol x) = 0, e = 1, \dots, \mathcal{E} $$
where $\mathcal{I} + \mathcal{E} \gg \text{dim}(\...
- 904
1
vote
1
answer
74
views
Optimization software for real-valued functions of complex arguments
I am interested in an optimization problem of the form
$$\min_{\boldsymbol z} \max_j \vert f_j(\boldsymbol z) \vert = \min_{\boldsymbol z} \Vert f_j(\boldsymbol z) \Vert_\infty. $$
Here, the ...
- 904
-1
votes
1
answer
78
views
RobOptim for real-time computation
Do you think that the RobOptim optimization library (which I read about in C++ library for nonlinear constrained minimization) could be used for real-time optimization for the velocity control of a ...
0
votes
0
answers
42
views
Reformulate a problem with concave objective function into a QP
I would like to convert this problem into a QP (Quadratic program).
$$\text{Maximize } \sum_{k=1}^{K}\sum_{n=1}^{N}log2(1+p_{kn}b_{kn})\\
\text{subject to } \sum_{k=1}^{K}\sum_{n=1}^{N}p_{kn}\leq P_{0}...
- 1
0
votes
1
answer
129
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 ...
- 471
0
votes
0
answers
714
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
45
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
134
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
99
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
381
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
98
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
1k
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
75
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
114
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
1
answer
68
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
239
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
123
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
88
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
38
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
79
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
104
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
137
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
4
votes
0
answers
198
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 ...
- 225
1
vote
1
answer
93
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
164
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