Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
209
questions
1
vote
0answers
58 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)...
4
votes
3answers
91 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. ...
0
votes
0answers
35 views
Least square approximation of a polynomial with a constraint on the derivative in Python
I'm trying to fit a polynomial of the third degree through a number of points. This could be a very simple problem when not constraining the derivative. I found some promising solutions using CVXPY to ...
1
vote
0answers
9 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
33 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
27 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
20 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
124 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.
...
3
votes
0answers
46 views
Constraint solver vs Bayesian optimizer for fast discontinuous processes
I have a complex domain-specific process that accepts inputs:
10-500 inputs, where each input is of type:
enum: choice between multiple string or numeric values
int: integers
float: floating point ...
0
votes
0answers
42 views
Optimization (best input variables search) for a non-smooth non-linear unknown function
I am trying to optimize a system that monitors and advises a user multiple times over a certain period of time depending on changing outside factors. The systems behavior can be altered by 5 ...
5
votes
0answers
94 views
How to solve a 4th order nonnegative LASSO problem?
I need to solve the following 4th order nonnegative LASSO problem:
$$
\min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1
$$
where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e....
4
votes
0answers
60 views
Fast approximate solver for vehicle routing problem
I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
2
votes
1answer
79 views
How to add extra constraints to a linear system for probabilities？
Background：
I have an equation which looks like as follows:
$W \times P = R$
$$\left[\begin{array} &{1}&{0}&{0}&-\frac{w_{1}}{w_{o1}} &\dots &{0} &-\frac{w_{1}}{w_{0} } \...
0
votes
0answers
83 views
Solving a non-convex optimization problem using fmincon
I am trying to solve a non-convex optimization problem using fmincon().
At each iteration, I am iteratively looking for the optimum value and when the termination ...
3
votes
1answer
93 views
Why would BFGS converge to a local minima of a non-convex function but maintain a large gradient?
I'm using BFGS to optimize a smooth but non-convex function $f$ that is computed by a simulation. The simulation also gives me a semi-analytical gradient $g$, which is verified by the numerical ...
0
votes
0answers
73 views
Augmented Lagrangian Techniques Frank-Wolfe Algorithm [python]
I'm trying to solve the convex quadratic problem (quadratic min cost flow problem) using the Frank-Wolfe algorithm.
$$ \min\{x^TQx+qx: Ex=b,\quad 0\leq x \leq u\} $$
The standard algorithm is okay ...
3
votes
0answers
64 views
Solve ODE with non-negative and maximization constraints
My task is to solve $$\eta_k\frac{d^2C_k}{dz}(z)=-e_k, k = 1,2,3$$
$$C_k\ge0$$
$$C_1(0)=0, C_2(0)=A, C_3(0)=0$$
$$C_1(L)=B, \frac{dC_2}{dz}(L)=0, \frac{dC_3}{dz}(L)=0$$
with $$e_1 = -\beta_1-\beta_3$...
1
vote
1answer
141 views
How do I solve the matrix equality constrained optimization problem using Lagrangian multipliers?
Solve the following minimization problem in $\mathbf{X} \in \mathbb{R}^{m \times n}$
$$\begin{array}{ll} \text{minimize} & \frac 12 \| \mathbf{X}\mathbf{X}^T -\mathbf{A} \|^2_\mathcal{F}\\ \text{...
2
votes
0answers
38 views
Biconvex problem whose objective function depends on only one variable
I am solving the following biconvex problem:
$$\min_{x,y} f(y)$$
$$s.t. ~~ g(x) \leq 0$$
$$~~~~~h(x,y) = 0$$
$$x \in X, y \in Y$$
where $X$ and $Y$ are compact convex sets, $g(x)$ and $f(y)$ are ...
1
vote
1answer
49 views
Vehicle Route assignment with capacity constraint
Problem Background
I'm trying to find a solution/model to the following problem:
Let's consider a cellular network (mobile network, ie., hexagonal cells) denoted $N$ composed of $|N|$ cells. Each ...
1
vote
1answer
45 views
Research articles on MultiObjective Non-Linear Programming (MONLP)
I'm looking for papers dealing with multi-objective non-linear programming which could help me implement an algorithm to solve my problem.
My problem is :
Maximize $f(x) = c \cdot x$, while ...
0
votes
1answer
55 views
Formulate and solve a simple conic programs in cvxpy language [closed]
Let $r,\epsilon > 0$ and $a, b \in \mathbb R^n$ with $\|a\|_2 \le r$. Define $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$, and assume it is non-empty.
Question
(A)...
2
votes
1answer
63 views
Question about strange outputs from the CVXPY solver
I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem:
...
2
votes
0answers
51 views
How to find two points within defined region in this constrained optimization problem?
I am doing a project related to robotics where I am using fmincon function from matlab to minimize the distance between the points ...
4
votes
0answers
72 views
Solution of constrained system of ODEs
Can someone point me in a direction to solve this kind of integral constrained system of ODEs.
\begin{align}
&\int_0^{1/2}\dot{y}^2(t)=p\\
&2\lambda_1\ddot{y}(t)+\pi cos(\pi y(t))=0\\
&y(...
0
votes
1answer
36 views
Can LINCS algorithm be used for colliding molecules?
Supposing that one molecule is static and one is dynamic,
can the dynamic one be solved with LINCS for its shape (angle, bond length) constraints and also keep collisions with static molecule off, ...
0
votes
1answer
101 views
Is this a knapsack problem?
I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
3
votes
1answer
43 views
Improve optimization speed for a set of similar problems: Quadratic programming with a warm start
I am repeatedly solving quadratic program,
$x^T Q x$ with time dependent linear constraints $Ax=b_t$.
Dimension of $x$ is around 10000 and there are around 50 constraints. I want to solve the ...
1
vote
1answer
132 views
sum of absolute difference constraint in optimization problem
I am writing a model for an optimization problem. I need to write the following constraint:
$$\sum^{N - 1}_i \lvert (a_i - a_{i+1}) \rvert \leq 2\, .$$
How to write this constraint (or linearize)?
...
1
vote
1answer
109 views
Nature of stationary points of a Lagrangian fuction
I would like to extremize a certain function $f$ with respect to a parameter $x$, under constraints $g_1(x) = 0, ..., g_m(x)=0$. In order to achieve this, I consider the Lagrangian function $L(x, \...
2
votes
1answer
53 views
Techniques to remove a function from Levenberg-Marquardt when it is against box constraints
I have a somewhat large (20+ dimensional) root finding problem that I'm solving with Levenberg-Marquardt. One of the functions has box constraints on [0, 2]. When it is against those bounds it will ...
1
vote
1answer
155 views
Why does Newton's method with Linear Equality Constraints use KKT condition?
Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint.
The problem only has equality constraint. Why ...
1
vote
0answers
34 views
Logging vs outputs in iterative optimisation
I'm coding an iterative algorithm of constrained continuous optimisation. An augmented Lagrangian algorithm (outer) calls a bound-constrained L-BFGS-B algorithm (inner), which calls a line search ...
2
votes
0answers
36 views
Sensitivity Lagrangian solution general case
I have asked this question already on maths and mathoverflow.
Just a question about a literature reference. I am writing a paper for engineers.
Usually for the Lagrange multiplier problem
$$
\...
1
vote
0answers
35 views
Efficient numerical optimization of an “almost separable” function
I have come across an optimization problem with the following objective function:
$$f(x_0,y_0,z_0,x_1,y_1,z_1,...,x_N,y_N,z_N) = \sum_{i=0}^N f_i(x_i,y_i,z_i, \alpha(x_{i+1}-x_i) + \beta(y_{i+1}-y_i))...
6
votes
0answers
139 views
An invertible matrix that minimizes the norm of the product with a given matrix
Given a fat matrix $B \in \mathbb{C}^{n \times m}$ (where $m > n$) with full row rank, I would like to find (numerically) a full-rank matrix $A$ that minimizes the Frobenius norm of the product $A ...
4
votes
1answer
859 views
How does fmincon in MATLAB calculate gradients?
I am trying to solve numerically a constrained optimisation problem in MATLAB, and I am wondering how the fmincon function calculates gradients when one isn't ...
1
vote
1answer
192 views
Piecewise-Linear Quadratic Optimization for an “Almost Convex” Problem
I have a 7-14 dimensional piecewise linear cost function I'd like to minimize with two quadratic terms of the form:
$$
f(X) = X^tCX + d \sum_i |x_i-x^*_i|^2 + \sum_i P_i(x_i-x^0_i)
$$
$$ \sum_i x_i ...
0
votes
1answer
89 views
Simulation-based Optimization vs PDE-constrained Optimization
What is the difference between Simulation-based Optimization and PDE-constrained Optimization?
Would studying a text on Simulation-based optimization be sufficient to understand and apply both?
2
votes
0answers
266 views
Convergence of a very large non-linear least squares optimization
(note: I also posted this question on stackoverflow before finding this community here, which seems a better place for it)
I'm trying to solve the following problem: I have a lot (~80000) surface ...
5
votes
1answer
281 views
Solvers for Quadratically Constrained Quadratic Programs (QCQP) with complex variables
I'd like to know whether there are any publicly available tools for solving QCQP with complex variables (and constraints therefore expressed through Hermitian matrices). What I have found so far is ...
1
vote
1answer
199 views
How to use CSDP to express a semidefinite program?
I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program
$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
1
vote
1answer
442 views
FMINCON Step Size Tolerance
I get following error after implementing the attached code.
Error Message
"fmincon stopped because the size of the current step is less than
the default value of the step size tolerance but ...
1
vote
0answers
43 views
Space covering optimization
I have the following problem:
In the space $E=\{1, 2, \dots, N_x\} \times \{1, 2, \dots, N_y\}$, I want to define $N_R$ rectangles $R_k=\{x_k^0, \dots, x_k^1\}\times\{y_k^0, \dots, y_k^1\}$ which ...
3
votes
2answers
158 views
How do I check if a loss function can achieve its minimum?
For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its ...
2
votes
1answer
30 views
Constraints 'exactly/at most one non-zero element' without binary variables
In a much larger MINLP problem, I have set of variables $\{a_{ij}\}_{m,n}$, such that $0 \leq a_{ij} \leq 1 $ for all $i$, $j$, which I could think of as a matrix, for which I have two requirements:
...
6
votes
1answer
238 views
What is required of the objective function in order to use Gauss Newton method?
From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.
In addition to that, are the following ...
1
vote
1answer
801 views
How to Solve Optimisation Problems using Penalty Functions in Python
I am working on a implementing a simple quadratic optimisation problem:
$$\min _x \; {\underline{x}}^T Q {\underline{x}}$$
$$s.t. \,\quad {\underline{\mu}}^T{\underline{x}} = R^*$$
$$ \quad \quad \...
0
votes
1answer
504 views
Defining a soft constraint in cvxpy
I am using cvxpy to do a simple portfolio optimization.
I implemented the following dummy code
...
2
votes
1answer
105 views
What is the fastest way to solve Ax=b (subject to constraints and an absolute term)
I am trying to solve/optimize $Ax=b$ in the least squares sense subject to
box constraints;
a few (less than 5) equality/inequality constraints; and
an absolute function penalty (or some other ...
