Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
304
questions
5
votes
0
answers
78
views
Compelling demonstrations/examples on ill conditioning of penalty methods
It's known that penalty methods in optimization suffer from ill conditioning. But is there simple yet compelling demonstrations/examples to teach this concept to convince and visualize for learners?
- 317
1
vote
1
answer
61
views
Regular constraints
I am going through some exercises in a presentation I found treating the basics of math for machine learning, and they talk about regular constraints.
For example, this set $K = \{(x,y) \in R^2 / x+y =...
- 113
0
votes
1
answer
40
views
Estimating the rate of convergence of Projected Gradient Descent on constrained polynomial objectives
I am estimating the order of convergence of Projected Gradient Descent (GD) on quadratic polynomials with random coefficients independently drawn from Uniform(-1,1) and bounded by a unit hypercube. I'...
- 23
0
votes
1
answer
110
views
Is the NLP formalism sub-optimal for real-world problems
My home-brew optimization studies have raised yet another fundamental question. The Nonlinear Programming formalism, "minimize f(x) subject to inequality and equality constraints, and x ...
- 329
3
votes
0
answers
68
views
Iterative Solvers for Linear Least Squares with Integer Constraints
The classical linear least squares problem reads $\min_{x\in\mathbb{R}^n}\|Ax-b\|^2_2$ and its solutions satisfy the normal equations $A^{\top}Ax = A^{\top}b$. A standard approach to solve the latter ...
- 2,352
0
votes
2
answers
153
views
BFGS Constrained Optimization Failure Due to Precision Loss
I am trying to optimize the following objective function according to some constraints. However, the optimization fails at the first iteration with the message that the desired error was not ...
0
votes
0
answers
35
views
How conservation of momentum is ensured in (Projected) Gauss-Seidel constrain solver
I'm developing molecular dynamics where my time-step is limited by stiffness of the bonds. I trying to get inspiration from game-engines, where they solve similar problem (hard bond constrains). These ...
- 937
0
votes
0
answers
39
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
33
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}$
...
- 111
5
votes
1
answer
443
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 ...
- 12k
1
vote
1
answer
49
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
40
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
60
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 ...
- 503
3
votes
0
answers
109
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 ...
- 289
1
vote
2
answers
250
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
154
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
146
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
102
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
1k
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
20
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
48
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
360
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,078
0
votes
1
answer
66
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
192
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
28
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
113
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
243
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
987
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
116
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 ...
- 637
1
vote
0
answers
323
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
93
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
105
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 ...
- 433
5
votes
1
answer
96
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}(\...
- 1,093
1
vote
1
answer
81
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 ...
- 1,093
-1
votes
1
answer
87
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
45
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
158
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 ...
- 503
0
votes
0
answers
967
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
49
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
171
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
158
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
493
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
109
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
2k
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
89
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
119
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
70
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
244
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
135
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
109
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