Questions tagged [constrained-optimization]
Questions about optimization problems subject to additional constraints.
214
questions
2
votes
1answer
60 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
40 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
62 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 ...
6
votes
2answers
128 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
57 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\...
1
vote
0answers
63 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
108 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
39 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
11 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
34 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
143 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
48 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
62 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
119 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
106 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
110 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
70 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
176 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
40 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
51 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
50 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
62 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
76 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
52 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
76 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
2answers
160 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
45 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
194 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
151 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
59 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
207 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
40 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
147 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
1k 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
217 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
92 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
269 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 ...
6
votes
1answer
349 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
202 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
527 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
44 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
169 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 ...
