Questions tagged [constrained-optimization]

Questions about optimization problems subject to additional constraints.

Filter by
Sorted by
Tagged with
12
votes
2answers
341 views

Efficient preconditioner for Augmented Lagrangian

I want to solve a non-linear problem with non-linear equality constrains and I'm using a augmented Lagrangian with a penalty regularization term that, as well known, spoils the condition number of my ...
10
votes
1answer
3k views

Why are interior point methods difficult to warm start?

I often encounter the general adage that interior point methods are difficult to warm start. Is there an intuitive explanation behind this advice? Are there situations in which one can expect benefits ...
8
votes
1answer
622 views

Linear system solution with inequality constraints - methods?

First of all, I hope I am posting this in the correct place. If not, I'm sorry and could you please direct me to where I should post this? Problem: You are given a set of vectors, $\{\mathbf{a}^i\}_{...
7
votes
2answers
211 views

Enforcing non-negative constraint in fourier-spectral method

I have a PDE optimization problem, and a scalar field (which I am optimizing over) is supposed to be nonnegative everywhere in the domain. Since I am working in Fourier space for solving this problem ...
7
votes
1answer
243 views

Algorithm for dealing with medium-size non-convex QCQP

I have the following problem in $x \in \mathbb C^{205}$ $$\displaystyle\min_{x}x^HAx$$ subject to the following constraints $$x^HBx = 1$$ $$x^HC_ix = 0$$ for $i \in \{0,1,\dots,203\}$, where $A$ ...
6
votes
1answer
318 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 ...
6
votes
2answers
224 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]$,...
6
votes
1answer
503 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 ...
6
votes
1answer
94 views

Intersections of supports constraint

Let $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ and $\text{supp}(\mathbf{x}) \subset \{1,2,...,n\}$ denote the set of indices such that $\mathbf{x}$ is non-zero. What type of optimization problem can ...
6
votes
1answer
754 views

Ways to speed up solving an LP with Google's ortools

I'm having an issue solving an LP of the form: $$\min z = c^Tx$$ $$\text{s.t.}$$ $$Ax \geq b$$ $$x\geq p$$ $1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$ The specific problems I'm running into ...
6
votes
3answers
575 views

Finding optimal velocity profile using Dynamic Programming

While continuously reading about Dynamic Programming I have a problem, implementing it in a practical application. Let's assume we want to optimize our way to school which we go daily by bicycle. ...
6
votes
0answers
165 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 ...
5
votes
2answers
1k views

Interpolation by Solving a Minimization Problem (Optimization)

I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - $M \times N$ Matrix). Someone marks some pixels as anchors. Now, you need to ...
5
votes
3answers
152 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. ...
5
votes
2answers
2k views

How to determine whether two cylinders intersect or not?

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
5
votes
1answer
62 views

Projection on Stiefel manifold after integration step

A few days ago, I asked how constraints like $A^T A = I$ can be implemented if one wishes to integrate differential equations of the form $\dot{A}=f(A,t)$. Kirill was so kind to point out that a ...
5
votes
1answer
134 views

Can Variational Inequalities handle non-symmetric matrices?

I am trying to enforce the discrete maximum principle (i.e., ensuring non-negative concentrations) for diffusion-type problems that have an anisotropic diffusivity tensor (e.g., tensor dispersion from ...
5
votes
1answer
2k views

Line search for constrained optimization

I have a nonlinear inequality constrained optimization problem of the form $$\begin{array}{cc} \min & f(x) \\ \textrm{s.t.} & g(x) \ge 0 \end{array}$$ where $x \in \mathbb{R}^n$, $f : \mathbb{...
5
votes
1answer
393 views

Constrained simulated annealing

Simulated annealing is a useful technique for finding near-optimal solutions to combinatorial problems. I have found a lot of tutorials on implementing the basic algorithm, but miss a general guide as ...
5
votes
1answer
508 views

Optimization of a blackbox function with an equality constraint?

I believe this would be an interesting problem. I have a blackbox function which can take 2-60 input variables $(X_1,X_2,...X_n)$ which are to be optimized. I'm calling this objective function as a ...
5
votes
2answers
2k views

How to solve a Rayleigh-quotient-like minimization with inequality constraints

What I am trying to solve is the following Rayleigh-quotient-like minimization: \begin{eqnarray} \begin{split} (P_0)\quad\min_x \frac{\left( Ax - b\right)^\top \left( Ax - b\right)}{x^\top x}\\ s.t. \...
5
votes
0answers
95 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....
5
votes
0answers
344 views

Optimization on the manifold of stochastic matrices

So I have an optimization problem of the form $$\text{maximize}\hspace{3mm}f(A):{\bf R}^{K\times K}\rightarrow{\bf R}$$ $$\text{subject to}\hspace{19mm}A^T{\bf 1}=\bf{1}$$ $$\hspace{33mm}A\geq 0$$ ...
5
votes
0answers
496 views

Best way to add a positivity constraint to Newton's Method

So given an objective function $f({\bf x})$, I would like to include a positivity constraint when I perform the fixed point iteration: $${\bf x}^{(t+1)}={\bf x}^{(t)} - \text{H}_f^{-1}\nabla f({\bf x}^...
4
votes
2answers
219 views

Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$

I'm sorry for this silly question. Several times I faced with optimization problems which can be expressed as $$\begin{array}{ll} \text{minimize} & \mathrm x^T \mathrm A \mathrm x\\ \text{subject ...
4
votes
1answer
154 views

Rank constrained SDP

I would like to optimize a function of the following form: \begin{equation} \sum_{i,j=1}^N c_{i,j} \mathbf{x}_i \cdot \mathbf{x}_j, \end{equation} where $\mathbf{x}_i \in \mathbf{R}^d$. Is it possible ...
4
votes
1answer
1k views

Converting convex quadratic constraint to linear matrix inequality (LMI)

I have the quadratic programming problem in $x$ $$\text{Minimize}\;\; x^T\Sigma x$$ $$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ $$\hspace{25mm}\boldsymbol{1}^Tx=1$$ ...
4
votes
2answers
460 views

Derivative-free nonlinear optimization of discrete objective function with linear constraints (simplex)

I am trying to optimize a constrained-problem with a discrete, non-linear objective function. Evaluating this function is also fairly expensive. Nevertheless, despite the above two factors, I hope, ...
4
votes
1answer
285 views

adjoint method for reaction-diffusion problem

I'm trying to code a parameter estimation for a reaction-diffusion problem. Namely, knowing the distribution of tumor density $u$ at time $0$ and $T_f$ ($u^0$ and $u^f$), what are the best ...
4
votes
3answers
311 views

How can I use Projected Gradient Descent for this optimization problem with constraint?

Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that $$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
4
votes
1answer
233 views

constrained minimization in N dimensions

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ f\...
4
votes
1answer
96 views

What's the right choice of variable settings for setting up my optimal control problem?

This is a followup to my previous question here I have the following dynamical system, $\frac{d \phi}{dt} = -M^TDM\phi \tag{1}\label{1}$ $\frac{d \hat\phi}{dt} = -M^T\tilde{D}M\hat \phi \tag{2} \...
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 ...
4
votes
1answer
368 views

Best platform for complex SDPs with n and m around 5-15K?

I am looking to solve a class of SDPs with complex entries, with the semi-definite cone $S^n$, $n$ around 5000 to 15000. Also, $m$, the number of equality/inequality constraints is close to $n$. I ...
4
votes
1answer
129 views

optimization subject to disjunction of inequality constraints

I want to solve $$\min_x f(x)\qquad \textrm{s.t.}\qquad g_i(x) \geq 0\ \ \textrm{or}\ \ h_i(x) \geq 0$$ for $i=1,\ldots,m$. Clearly if the inequality constraints split the feasible set into $2^m$ ...
4
votes
2answers
594 views

Finding a global minimum of non-convex quasi-smooth function that is costly to evaluate

I have a bounded non-convex function in 10-dimensional space. The function is quasi-smooth, you can imagine a histogram, here is an illustration, it just shows the idea and not related to my ...
4
votes
1answer
133 views

State-of-the-art for active set optimization algorithms?

Given a problem like this: $$ \text{min } ||Ex-f|| \text{ s.t.}$$ $$ Gx \ge 0$$ $$ Cx = d $$ And assuming that the matrices are medium sized (dimensions in the low thousands) and dense, what's the ...
4
votes
1answer
175 views

Underdetermined Minimum Volume Enclosing Ellipsoid

Given three vectors in $\mathbb{R}^{512}$, my task is to compute a Minimum Volume Enclosing Ellipsoid (MVEE). I have tried Kachiyan's algorithm, but it requires at least as many vectors as there are ...
4
votes
1answer
239 views

Methods for Constrained Optimization Problems with Box Constraints

Consider this problem: \begin{equation} \begin{array}{ll} \text{minimize } & f(x) \\ \text{subject to } & a \leq x \leq b \end{array} \end{equation} where $a,b,x \in \mathbb{...
4
votes
1answer
92 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 ...
4
votes
0answers
69 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 ...
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(...
4
votes
0answers
54 views

Obtainting KKT for QSDP for the trace inequality constraint

I am working on developing my own solver(for implementation on hardware), based on IPM for following problem: \begin{equation} \begin{split} \min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\ \text{...
4
votes
0answers
162 views

How to apply an integrated constrain condition in FEM?

I'm running some simulation using FEM. In my model I need to apply a constraint condition to the governing equation. My governing equation similar to the diffusion equation as below: $$\frac{\...
4
votes
0answers
639 views

Precision of ratio constraint in a linear program [closed]

I am trying to solve a LP in which one of my constraints is of the form $$\frac{A(x)}{B(x)} = 1$$ I transform this constraint into a linear one $$A(x) - B(x) = 0$$ However when CPLEX solves the ...
4
votes
0answers
158 views

Eigenvalue-style optimization with quadratic constraints

Suppose $A\in\mathbb{R}^{n\times n}$ is symmetric and positive definite and that we have several symmetric matrices $B_i\in\mathbb{R}^{n\times n}$ that are low-rank and indefinite. I need an ...
4
votes
0answers
76 views

numerical solver for stochastic optimal control problems

can any one recommend numerical solver (c/c++ library preferred) for stochastic optimal control problems? For deterministic optimal control I found something like that: http://abs-5.me.washington.edu/...
4
votes
1answer
410 views

Transform from constrained to unconstrained optimization

In a constrained optimization problem, I found in a paper a way to define new variables such that the constraints disappear. They only give the new variable definitions, and I would like to understand ...
3
votes
3answers
269 views

How to debug a constrained optimization algorithm?

I have implemented a saddle point optimization problem based on the algorithm by Prof. Nesterov, primal-dual[1]. Unfortunately, it doesn't work. It seems it is converging. But unfortunately, not to ...
3
votes
2answers
194 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 ...

1
2 3 4 5