Questions tagged [quadratic-programming]
Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.
1
vote
1answer
20 views
quadratic programming /symmetric matrix
I have a quadratic program with $ F: \mathbb{R^n} \rightarrow \mathbb{R}, F(x)=x^TQx$ I want to find a symmetric matrix M for Q, such that $F(x)=x^TMx$ holds for all x.
I can write Q as sum of ...
0
votes
2answers
71 views
Determining the coefficients of $y = a x^2 + b x + c$ so that the graph contains three given points
Determine coefficients of the equation for a second order polynomial in the format: $y = a x^2 + b x + c$
Here are the $x$-$y$ coordinates of three points:
$(0.8143,0.3500)$
$(0.2435,0.1966)$
$(0....
0
votes
1answer
46 views
Unconstrained convex quadratic integer programing
Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I have a minimization problem of the form
$$
\min_{n\in N} \sum_i A_i n_i +\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^2
$$
...
0
votes
1answer
37 views
Approximate function by stacking building blocks
I need some help with a 'generalised Lego problem':
Given a function $f(x)\geq 0$ on an interval $[a,b]$, and a 'building block' function $p(x)\geq 0$ with compact support. The maximum of f shall be ...
0
votes
1answer
34 views
Linearly constrained quadratic program
I have the following quadratic program
$$\min_x x^TAx \qquad \text{s.t} \quad Ax \in [a,b]^m$$
where matrix $A$ is positive semidefinite, and is similar both the objective function and in the ...
0
votes
0answers
19 views
Is there a time polynomial algorithm to solve a box-constrained quadratic convex program?
I am working on the following quadratic convex problem
$min_{x}x^{T}Qx+f^{T}x$
subject to
$a\leq x\leq b$
where $x,a,b,f\in\mathbb{R}^{n}$ and $Q$ is positive definite. Is there any
algorithm that ...
0
votes
1answer
40 views
Measuring infeasibility in convex optimization, relations with dual problem
A question regarding convex optimization and (maybe) duality.
I have a problem in the form
\begin{align}
x^* = \mathrm{arg} \min_x f(x) \quad \text{s.t.} \quad A x \leq b, C x = d,
\end{align}
where $...
0
votes
0answers
22 views
Derive LCP from KKT conditions of a QP
I'm working through this tutorial on LCPs and interior point methods. In it, the authors claim that the following quadratic program
$$
\begin{aligned}
\min \quad& \frac{1}{2}u^TQu - c^Tu\\
\text{...
0
votes
1answer
20 views
Is there only one unique minimizer for this scalar complex quadratic form?
Consider $c,b \in \mathbb{C}$ and $f: \mathbb{C} \mapsto \mathbb{R}$,
$$f(c) = bc' + b'c + cc'$$
is there only one extrema of $f$ corresponds to $$c^* = -b$$?
where, $'$ means complex conjugate.
...
0
votes
1answer
35 views
Local optimality of non-convex quadratic minimization with linear constraints
We are interested in minimizing a quadratic function, which is not convex. The feasible set is a polyhedron. We know that the global minimum is at a vertex when the function is concave.
Also, there ...
0
votes
0answers
39 views
Quadratic program reformulation maximum to minimum
I am newbie in optimization problem, I have the following optimization problem:
$$\max \quad \frac{1}{2}x^THx - q^THx$$
$$\text{s.t.} \;\;l\leq x \leq u$$
where $H, q$ are known constants, and H is ...
1
vote
2answers
47 views
Quadratic optimization problem with quadratic constraint
Given $A = A^T \in \mathbb{R}^{n \times n}, X = \begin{bmatrix}x & \eta\end{bmatrix} \text{with} \ x, \eta \in \mathbb{R}^n$ and $||x|| = ||\eta|| = 1$ (vectors in $\mathbb{R}^n$ are treated as ...
1
vote
0answers
42 views
Karmarkar's canonical form for convex quadratic programs??
I'm working through this paper A Simple Polynomial-Time Algorithm for Convex Quadratic Programming which gives an interior point algorithm for convex quadratic programming. I've reached the end of the ...
0
votes
1answer
21 views
confusion in proof of lemma for LCP
I'm looking at the proof of lemma 2 on page 6 of https://cowles.yale.edu/sites/default/files/files/pub/d05/d0549.pdf
Which claims that the LCP
$$
Mx+q \geq 0 \\
x \geq 0 \\
x^{T}(Mx+q) = 0
$$
has a ...
0
votes
1answer
53 views
minimum of $\frac{1}{2}x^tQx-c^tx$ subject to $Ax=b$ is local $\iff$ is global
$$\min \frac{1}{2}x^tQx-c^tx\\ Ax=b$$ where $Q\in \mathbb{R}^{n\times
n}$ is symmetric, $c\in \mathbb{R}^n$, $A\in \mathbb{R}^{m\times n}$
and $b\in\mathbb{R}^m$. Prove that if ${x}^*$ is a local
...
3
votes
2answers
168 views
How to minimize $\Vert Ax \Vert$ subject to $\hat{b}^Tx=0$ and $\Vert x \Vert = 1$?
Given $n\times 3$ matrix $A$ and unit vector $\hat{b}\in R^3$, is there a closed-form solution for $x\in R^3$ that minimizes the Euclidean norm $\Vert Ax \Vert$ subject to $\hat{b}^Tx=0$ and $\Vert x \...
0
votes
0answers
10 views
Two dimensional sorting: finding $\max_\sigma \langle M^\sigma,C\rangle$ for permutation function $\sigma$
Suppose that we have a non-negative matrices $C,M\in \mathbb{R}^{m\times m}_{\ge0}$. Also suppose $\sigma:[m] \rightarrow [m]$ is a permutation of $\{1,2,...,m\}$. We want to find the permutation that ...
0
votes
0answers
48 views
Large scale mixed integer (quadratic) programming
Here we have this optimization problem:
Given positive semi-definite matrix $A \in \mathbb{R}^{n \times n }$, and matrix $B \in \mathbb{R}^{n \times m} \text{ and vectors } d \in \mathbb{R}^n,e \in ...
5
votes
2answers
140 views
Transform an optimisation problem into a linearly-constrained quadratic program?
I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
0
votes
1answer
21 views
How to find uppper bound for the hyper parameters in linear model?
I have loss function of the following form:
$$argmin_w= ||Y-w^TX||_2^2 + \lambda||w||_1 + \gamma \sum_{g=1}^G||w_g||_1$$
where $w_g$ is group of coefficents.
Given $Y$ and $X$, I would like to find ...
0
votes
2answers
65 views
Minimise $||Ax - b||_2$ given $x \geq 0$ and $\textbf{1}^Tx = 1$
$$
\min_x ||Ax - b||_2\; \;\text{given }x \geq 0\;\;\text{and}\;\;\textbf{1}^Tx = 1
$$
I am trying to do the above optimization, I was using common Quadratic programming libraries but their speed is ...
0
votes
1answer
54 views
Silly Quadratic programming
Suppose that I want to minimize the function $x^2$ subject to the contraint
$$
ax\leq b,
$$
for some $b> 0$. I solved the problem if the contraint is an equality but I'm not sure how to go about ...
0
votes
1answer
33 views
binary quadratic mixed integer nonlinear programming to inequalities
I have this unconstrained z=x.y where x,y are 0-1 integers. How to reformulate that into set of mixed integer linear inequalities with exactly the same feasible region?
0
votes
0answers
69 views
Non-positive-definite quadratic program minimum simplification
I was finding the minimum of a simple quadratic program with equality constraints:
$$
m = \min_x x^TQx\qquad\mathrm{s.t.}\quad Ax=b.
$$
Using a formulation with Lagrange multipliers from Wikipedia I ...
0
votes
0answers
23 views
Constraint breaking in constrained least squares
In a constrained least squares problem $\boldsymbol{y} = \boldsymbol{X}\boldsymbol{\beta},\ \boldsymbol{\beta} = \{\beta_1, \ldots, \beta_n\}$ solved with quadratic programming, suppose that I have ...
0
votes
1answer
120 views
How to map quadratic programming formulation to dual soft margin SVM
I am trying to use quadratic programming for SVM and I am confused about how to map SVM formulation to quadratic programming formulation given in CVXOPT (Python package).
This is what CVXOPT gives us
...
1
vote
0answers
25 views
different block size in Block Matrix
I am following a book and having trouble understanding.
so from Section 6.6.2 page 496, i have
A = NxN matrix
b = Nx1 vector
c = Nx1 vector
from Section 14.3.2 ...
1
vote
1answer
29 views
How to Reformulate an Image Constraint in the Dual of a Quadratic Program with Nonconvex Constraints?
I have the following nonconvex optimization problem, for which I want to formulate the dual:
$\mathcal{P}:\underset{x}{\text{min}} \quad x^\top A x + b^\top x \\
\quad \ \ \text{s.t.} \quad x\in\{0,1\...
2
votes
0answers
29 views
On approximation of maximization of quadratic function over a convex set
Given a convex function $f : \mathbb{R}^n \to [0,\infty)$. Let $L = \left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1 \right\rbrace$ be it's sub-level set and suppose that $L$ is not empty as well as ...
0
votes
0answers
40 views
If the relative value of the most negative eigenvalue is small, can we view the quadratic program as convex?
Consider symmetric matrix $A \in \mathbb{R}^{n \times n}$ with $n-1$ negative eigenvalues and a positive one such that $\lambda_1 > \lambda_2> \dots > \lambda_n$, where $\lambda_n$ is the ...
0
votes
0answers
27 views
Quadratic Matrix programming
I would like to find a numerical solution to the following quadratic matrix programming problem. Square matrix A has thousands of rows, so I need a algorithm which works fast. I looked into Python but ...
1
vote
1answer
121 views
What is the fastest algorithm to solve an equality-constrained convex quadratic program?
I am trying to solve the following convex problem
$$\begin{array}{ll} \text{minimize} & x^T Q x + px\\ \text{subject to} & Ax + b = 0\end{array}$$
which arises in the active set method for ...
2
votes
1answer
103 views
Is the optimal solution of a convex problem continuous with respect to parameters?
Given the convex problem
$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{i=1}^{N} f(x_i)\\ \text{subject to} & Ax = B\\ & 0\leq x_{\min} \leq x_i \leq x_{\max}\end{array}$$
...
0
votes
0answers
44 views
Support Vector Machines: question about the underlying math
I'm new to Support Vector Machines and I've been trying to get into the underlying math (instead of just using Scikit Learn or something like that).
I understand the math behind it up to the point ...
1
vote
1answer
81 views
Solving inequality-constrained least-norm problem non-iteratively
I am looking into the following constrained quadratic program in $x \in \mathcal{R}^4$
$$\begin{array}{ll} \text{minimize} & \| x \|_2^2\\ \text{subject to} & A x = b\\ & x_{\min} \le x_i ...
2
votes
0answers
65 views
Checking inequality
Let $\pi$ be a given permutation of the integers $\{1,\ldots,n\}$ and let
$$\mathcal{X}=\{x\in\mathbb{R}_{+}^{n} \mid x_{\pi(1)}\geq\cdots\geq x_{\pi(n)},\mathbb{1}^\top x\geq \alpha\},$$
for some $\...
0
votes
0answers
117 views
Solving underdetermined linear system using least squares
As in case of linear overdetermined system of equations, we can prove that the cost function i.e. the least square function is convex.
But in linear underdetermined system, we know that there exist ...
0
votes
1answer
111 views
How to increase the accuracy of optimal point obtained by ADMM?
What is the best algorithm to polish the optimal point obtained by the ADMM method for a constrained quadratic program?
I've already studied the primal-dual method. Although it can obtain a solution ...
0
votes
0answers
38 views
Solving/minimizing $Fw=b$ with $F$ and $w$ unknown and $b$ known
I have a system $Fw=b$ that can be underdetermined, square or overdetermined. The matrix $F$ contains known scalar functions $f_i(t)$ evaluated at unknown values $t_j$. The vector $w$ contains unknown ...
0
votes
1answer
175 views
Solve Matrix Least Squares (Frobenius Norm) Problem with Lower Triangular Matrix Constraint
Let $\mathbf{A} \in \mathbb{R}^{N \times N}$, $\mathbf{X} \in \mathbb{R}^{N \times M}$, and $\mathbf{B} \in \mathbb{R}^{M \times N}$. We intend to solve for $\mathbf{X}$ by solving the following ...
0
votes
0answers
63 views
Primal Dual Interior Point convergence.
I have developed a Primal Dual Interior point algorithm to solve linear inequality constrained Quadratic problems. But sometimes it cannot reduce the residual so as to satisfy the stop criteria. I ...
4
votes
0answers
69 views
Equivalent forms Optimization
We were told to assume in class that the below optimization formulations are equivalent-
$$\min_w\max_{\delta:||\delta||_F\leq\epsilon}||(X+\delta)w-y||_2^2$$
$$\min_{w}||Xw-y||_2^2+\lambda||w||_2^2 ...
4
votes
1answer
56 views
Convex quadratic program with linear equality constraint and bounds on variables
$$\begin{array}{ll} \text{minimize} & \sum \limits_{i=1}^n x_{i}^{2}\\ \text{subject to} & \sum \limits_{i=1}^n x_{i} = m\\ & 0 \leq x_i \leq a_i\end{array}$$
I know that if the $a_i$ are ...
0
votes
0answers
15 views
Linear optimization under a binary linear classifier constraint with unknown weights
Let $c(x), x\in\mathbb{R}^N$ be a binary linear classifier, i.e. $c(x) = w^\top x + b > 0$, and suppose we have no access to $w\in\mathbb{R}^N$ and $b$ (we can only query the output of the ...
0
votes
1answer
48 views
Computing the Lagrange multiplier in constrained optimization problem
As I know the value of the Lagrange multiplier does not have a valuable meaning in most cases. Our goal is to compute the values of the parameters.
Here is an example for constrained optimization: ...
1
vote
0answers
22 views
How can we transform the objective function of LQG problem as function of the estimation error?
Consider an infinite-horizon classical Linear-Quadratic-Gaussian (LQG)
problem
\begin{eqnarray*}
\underset{x,u}{\min} & & \underset{\eta\rightarrow\infty}{\lim}\mathbb{\mathbb{E}}\left[\frac{...
0
votes
0answers
25 views
Minimizing quadratic over region
Let $x_1, ..., x_n\ge 0$ with $x_1+...+x_n=1$. Minimize $$\sum_{j=1}^na_j\left(\sum_{i=1}^nw_{i,j}x_i-y_j\right)^2$$ where $a_j$ and $w_{i,j}$ are some weights.
Use $x_n=1-x_1-...-x_{n-1}$. Without ...
0
votes
1answer
74 views
Strong duality strictly convex quadratic problem
Assume we have this strictly convex quadratic programming:
$$f(x) = x^\top A x + b^\top x,$$
$$Ax \leq b$$
$$ 0 \leq x \leq 1$$
Where $A$ is symmetric and positive definite, and the feasible set is ...
0
votes
0answers
63 views
Dual of a convex SOCP
I'm reading up on convex optimization this summer and wanted to check my understanding of an example problem.
$$\begin{array}{ll} \text{minimize} & \| x \|_2\\ \text{subject to} & \...
0
votes
0answers
32 views
Concave quadratic function unbounded below
$$f(x) = y^\top x - \frac{1}{2} x^\top Q x$$
where $Q$ is both symmetric and positive definite is shown here to be bounded above. However, is the following proof correct for $f(x)$ being unbounded ...
