Questions tagged [quadratic-programming]

Questions on quadratic programming, the optimization of a quadratic objective function subject to affine constraints.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
28 views

How to find two vectors with a linear constrain to maxmize the angle between them? [closed]

I want to find two vectors in a linear constrained region. How can I find two vectors in the region that have the maximal angles? It can be written as: $$\begin{aligned} \min & \frac{w_1^Tw_2}{\|...
user avatar
  • 2,541
2 votes
1 answer
38 views

Decision variable limit condition in constrained linear and quadratic programing

We are given a quadratic (or linear) program as$$\min \limits _xx^TPx+q^Tx\qquad \text{s.t.}\quad a_i^tx\leq b_i,\quad \forall i\in \{1,\ldots ,N\}.$$In the above problem, we do not have any limit on ...
user avatar
  • 58
1 vote
0 answers
75 views

Why linear programming is called 'programming' instead of 'optimization'?

In numerical optimization (a mathematics branch), a standard optimization problem is formulated as min f(x), subject to c(x) = 0 or c(x) >= 0. But when these ...
user avatar
  • 71
2 votes
0 answers
27 views

Showing existence of a solution to a quadratic system of equations implies existence of a solution to another

Given a system of quadratic equations: $$\forall i\>\>\>x^{\dagger}M_ix = y_i$$ I want to show that if there exists a solution $x\in \mathbb{C}^n$, there must also exist a solution $\hat{x}$ ...
user avatar
  • 290
0 votes
0 answers
73 views

Quadratic optimization problem where the variable is a binary matrix.

I have the following optimization problem that I want to solve (note that the $X$ variable consists of a binary matrix subject to a single constraint). First, some definitions: My $X$ variable: $$ X = ...
user avatar
0 votes
0 answers
45 views

What is the fastest way to solve a large-scale quadratic programming problem with inequality constraint?

I am trying to solve problem as follows: \begin{equation} \begin{split} &\mathop{min} \limits_{\textbf{x}_1...\textbf{x}_k} \ \frac{1}{2}\textbf{x}_1^T\textbf{Q}_1\textbf{x}_1+\textbf{q}_1^T\...
user avatar
  • 21
1 vote
1 answer
33 views

Second Order Cone Program with Quadratic Objective Function

The standard form for a Second Order Cone Program (SOCP) is \begin{equation} \begin{array}{c} \min _{x} f^{T} x \\ \left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, i=1, \ldots, m \end{array} \...
user avatar
1 vote
0 answers
37 views

Rewriting quadratic optimization problem with negative definite matrix

Consider the following problem: Minimize $x(1-x) + y(1-y) + z(1-z)$ subject to: $$ a. 0\leq x, y, z \leq 1$$ $$ b. x+y+z = 1$$ If I plug in this problem in a standard quadratic optimizer, which ...
user avatar
2 votes
1 answer
39 views

Explicit Solution of Quadratic Opt. Problem

I have the following optimization problem I am unsure whether I've got it correct: $$ \text{min } x^Tx \\ \text{so that } a + c^Tx <= 0 $$ I have introduced a slack variable $s$ to make it ...
user avatar
  • 157
1 vote
0 answers
44 views

Objective function and constraints are matrix form in an optimization problem, can Lagrange multipliers method be applied to solve?

I would like to solve the following optimization problem: given $\mathbf{K} \in \mathbb{R}^{n \times n}$, $\mathbf{P_{0}} \in \mathbb{R}^{n \times 3}$, $\mathbf{M} \in \mathbb{R}^{m \times n}$, $\...
user avatar
  • 35
0 votes
0 answers
37 views

Frobenius inner product, Frobenius norm objective function with quadratic equality constraints.

I would like to solve the following optimization problem: given $\mathbf{K} \in \mathbb{R}^{n \times n}$, $\mathbf{P_{0}} \in \mathbb{R}^{n \times 3}$, $\mathbf{M} \in \mathbb{R}^{m \times n}$, $\...
user avatar
  • 35
1 vote
1 answer
66 views

Quadratic Minimization Problem with positivity constraint

Let $A \in\mathbb{R}^{m\times n}$, $b,c\in\mathbb{R}^m$, $x\in \mathbb{R}^n$. Consider the following minimization problem: $$ \min_{x\succeq 0} f(x):= \frac{1}{2}\|Ax-c\|^2 + b^\top Ax. $$ For the ...
user avatar
2 votes
2 answers
98 views

Simple Quadratic Minimization Problem

Let $A \in\mathbb{R}^{m\times n}$, $b,c\in\mathbb{R}^m$, $x\in \mathbb{R}^n$. Consider the following minimization problem: $$ \min_{x} f(x):= \frac{1}{2}\|Ax-c\|^2 + b^\top Ax. $$ Since the function ...
user avatar
0 votes
0 answers
41 views

Recast maximization as minimization

I hope you can help me. I would like to know which are the conditions to transform a maximization problem into a minimization one. I have the following problem $ Q: \max_{x,y} ~ f(y) / g(x) ~~ s.t. ~ (...
user avatar
  • 694
1 vote
0 answers
32 views

How is the Wilson-Han-Powell SQP algorithm applied?

Say for example we need to minimize $x_2$ subject to $x_1^2+x_2^2-1=0$ starting at $x_1=x_2=1/2$ and using $B=\nabla^2[x_2+\lambda(x_1^2+x_2^2-1)]$ with $\lambda=1$. Now, the WHP-SQP algorithm goes ...
user avatar
0 votes
0 answers
29 views

Parametrically enlarge one ellipsoid to fit another one

I'm trying to figure out the smallest enlargement factor which I need to apply to one ellipsoid $E_1$ in order to fit another one $E_2$. Precisely, let $E(c, S) := \{x | (x-c)^T S (x-c) \leq 1\}$ be ...
user avatar
2 votes
1 answer
43 views

Unconstrained minimizer as a linear combination

I'm given the following function: $$f : R^n \rightarrow R$$ $$f(x)=\frac{||Ax-b||^2}{c^Tx+d}$$ where x $\in R^n$ and $dom(f) = \{x|c^Tx+d > 0\}$ Also it's given that $rank(A)=n$ and vector b is ...
user avatar
  • 147
0 votes
0 answers
24 views

Solutions of Two Similar Quadratic Programs

I am solving a very large number of quadratic programs with the same objective function, and very similar constraints. Given a positive definite matrix $\Sigma$ and constraints $A,B,a,b$, let $$ x = \...
user avatar
0 votes
0 answers
14 views

Closed form solution of linear least square with penalty term and inequality constraint

I want to find a closed form solution of the following problem $$ \min_B \|V^T B- E \|^2 + \lambda \| B\|^2$$ $$s.t. V + B \geq 0, $$ where $B \in \mathbb{R}^{k \times n }$, $E \in \mathbb{S}^n$, and $...
user avatar
  • 710
0 votes
0 answers
21 views

Solution to quadratic problem in least square optimization

$ \begin{array}{rrclcl} \displaystyle \min_{\dot{\boldsymbol{x}}} & (\boldsymbol{G}_a^T\dot{\boldsymbol{x}}-\dot{\boldsymbol{\theta}}_a)^T(\boldsymbol{G}_a^T\dot{\boldsymbol{x}}-\dot{\boldsymbol{\...
user avatar
  • 1
1 vote
1 answer
97 views

Norm $\|x\|$ defined as the sum of largest $r$ absolute values, how to write $\min \|A x-b\|_{2}^{2}+\|x\|$ as QP?

This is a question from Boyd Convex Optimization, Additional Exercise 5.31 In this problem, $r$ is an integer between 1 and $n$, and $\|x\|$ denotes the norm $$ \|x\|=\max _{1 \leq i_{1}<\cdots<...
user avatar
  • 25
0 votes
0 answers
23 views

Projection mapping as quadratic programming problem.

I am studying Variational inequalities in Hilbert space. To define this, let $C$ be a closed, convex subset of a Hilbert space $H$. The Variational inequality problem is to find $x \in C$ such that $\...
user avatar
0 votes
1 answer
69 views

Solving a constrained optimization problem using Lagrange Multiplier

I am trying to solve a relatively simple single variable constrained quadratic programming but having hard time. The problem is as follows: $$ \min_x ax^2-b(1+x) $$ subject to $$ 0\leq x \leq1 $$ $$ b(...
user avatar
0 votes
1 answer
99 views

How to solve non-negativity-constrained quadratic programs?

$$\min_{x_1,x_2,x_3 \geq 0} \quad 2x^2_1+3x^2_2+4x^2_3+2x_1x_2 -2x_1x_3 -8x_1-4x_2-2x_3 $$ I tried to re range the problem to matrix form and got $$ \min_{x \geq 0_3} \quad x^T Ax + 2b^Tx$$ where $$...
user avatar
0 votes
0 answers
37 views

The dual function of non-convex QP

I am trying to find the dual function of the follwoing non-convex QP \begin{equation*} \min \frac{1}{2}x^T Q x \\ Ax = b, 0\leq x \leq e \end{equation*} The Lagrangian function is given by \begin{...
user avatar
  • 31
1 vote
0 answers
37 views

Minimizing $b^Tb$ subject to $Ax=b, x\geq 0, x\leq 1$

I have the following quadratic program: Minimize $b^Tb$ subject to $Ax=b$ where $A$ is a $n\times m$ matrix ($n\leq m$) of rank $n-1$. I also want $0\leq x\leq 1$. For my choice of $A$, I can prove ...
user avatar
  • 1,756
1 vote
1 answer
39 views

Hessian of quadratic objective function

I have the quadratic function $$f(\boldsymbol{x}) = \frac{3}{2} \left (x_{1}^{2}+x_{2}^{2} \right) + (1+a) x_{1} x_{2} - \left(x_{1} + x_{2} \right) + b$$ where $a, b \in \Bbb R$ are unknown ...
user avatar
  • 177
1 vote
1 answer
51 views

Solving Quadratic Optimization problems without using Lagrange Multipliers

I am having trouble understanding min/max problems in Linear Algebra. I am normally used to solving these types of problems using some form of calculus. The question I am stuck on is minimizing: $$b^{...
user avatar
0 votes
0 answers
20 views

Constrained Least Squares - Analytical solution

Given a matrix $A \in \mathbb{R}^{d \times d}$, and a pair of vectors $b,x_0 \in \mathbb{R}^d$, and some positive scalar $\alpha > 0$, is there an analytical solution to the following optimization ...
user avatar
0 votes
1 answer
50 views

Minimizer of a convex quadratic function

Suppose that there is a positive definite matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$, and a vector $\mathbf{b} \in \mathbb{R}^{n}$, then minimization of quadratic functions with linear terms can ...
user avatar
0 votes
1 answer
110 views

How can I form this second-order conic constraint?

I am trying to show that if we have a real symmetric matrix $Q$ with one negative eigenvalue within a quadratic constraint: $x^\top Qx+a^\top x +b \leq 0$ That this constraint can be formulated as a ...
user avatar
0 votes
0 answers
18 views

Affine Scaling Interior Point algorithm for linear programming.

Can someone explain, or provide sources for, why the affine scaling interior point method (by Dikin) projects the gradient of the objective function onto the null space of the constraint matrix to ...
user avatar
  • 1
1 vote
0 answers
77 views

Model Predictive Control with Linear Programming VS Quadratic Programming

Model Predrictive Control is often used with Quadratic Programming. But I have tried Model Predictive Control with Linear Programming and it works very well. Let's begin with the discrete SISO state ...
user avatar
  • 2,560
1 vote
0 answers
71 views

Minimizing $\|A−XB\|^2_F$

Find a closed form solution for $$\underset{X}{\operatorname{argmin}} \|A−XB\|^2_F$$ where $\| \cdot \|_F$ denotes the Frobenius norm. I have found this thread. Not sure if it helps here though. Any ...
user avatar
1 vote
1 answer
63 views

Indefinite generalized Tikhonov regularization

Suppose we want to choose $x$ to minimise the following (generalized) Tikhonov regularized least squares objective: $$(Ax-b)^\top (Ax-b) + \lambda [(x-c)^\top W (x-c)],$$ where $W$ is symmetric, but ...
user avatar
  • 671
1 vote
0 answers
7 views

Show that $\vec{a}_j$ is linear independent with respect to $\{\vec{a}_i:i\in W_k\}$.

Suppose that $\quad \vec{a}^T\vec{d}>0\quad$ for a $j\in I-W_k\quad$ and $\quad \vec{d}\neq 0$ is the optimum solution of the system $$\text{min}_{\vec{d}} (\frac{1}{2}d^TGd+d^T\vec{g}_k)$$ $$\vec{...
user avatar
1 vote
0 answers
55 views

How to solve a linear optimization problem with two arrays variables?

I have two sets of $n$ 3 dimensional vectors independent from eachother ; $$A = (f_1, f_2, ..., f_n)$$ $$C = (m_1, m_2, ..., m_n)$$ I am looking for the set of $n$ real factors, $X = (X_1, X_2, ..., ...
user avatar
1 vote
1 answer
32 views

Solving an optimization problem in QCP form

I am reading a paper in which authors said quadratic-constrained optimization is used for the following problem: \begin{align} &\underset{\mathbf{P},\,\,\epsilon}{\min}\:\epsilon\\ &\mathrm{s....
user avatar
  • 43
0 votes
0 answers
33 views

How is Mathematica minimizing correlation exactly with linear constraints?

I made a random data matrix as data = Table[Random[], {i, 5}, {j, 5}]; In my case it was $$ \left( \begin{array}{ccccc} 0.951203 & 0.546669 & 0.86928 &...
user avatar
  • 23.5k
3 votes
0 answers
143 views

Closed form solution for a quadratic program in matrix form with inequality constraint

Is there a closed form solution for the following quadratic program with inequality constraint? Let $P \in \mathbb{S}^n_{++}$ be a symmetric positive definite matrix, and $B$, $F \in \mathbb{R}^{k \...
user avatar
  • 710
1 vote
0 answers
53 views

Show that the function $f(\vec{x})=\frac{1}{2}\vec{x}^TG\vec{x}+\vec{x}\vec{c}$ is convex if and only if $G$ is semidefinited positive. [duplicate]

Show that the function $f(\vec{x})=\frac{1}{2}\vec{x}^TG\vec{x}+\vec{x}\vec{c}$ is convex if and only if $G$ is semidefinited positive. My approach: $\Rightarrow]$ I want to show that $\vec{x}^TG\vec{...
user avatar
1 vote
0 answers
86 views

How to solve this non-convex quadratic program?

Consider the following quadratic program $$\begin{array}{ll} \underset{x,y}{\text{minimize}} & a x^2 - b x y - c y\\ \text{subject to} & x \geq 1\\ & y \geq 5\end{array}$$ where $a$, $b$ ...
user avatar
  • 352
0 votes
0 answers
44 views

Convert a formula to a quadratic formula.

I've just started to learn Quantum annealing and I have found that I have to convert my problem into its quadratic form. I have to use something named QUBO. To start with, I have tried to find a ...
user avatar
2 votes
1 answer
129 views

For a given function $f: \mathbb{R}^n \rightarrow \mathbb{R}$, find the direction of least change

As written in the title, I have a function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ and I want to find the direction of least change. However, I encountered an inconsistency between two different ...
user avatar
  • 161
1 vote
0 answers
56 views

Linear Objective with quadratic constraint

Suppose $H$ is a symmetric positive definite matrix, and $h$ a vector. I want to solve the following optimization problem with linear objective and quadratic equality constraint: $$\underset{v^THv = 1}...
user avatar
  • 710
0 votes
1 answer
85 views

Prove the existence and uniqueness of a global minimum for a quadratic function $q(x)$ with positive definite Hessian

How do I prove the existence and uniqueness of a global minimum for a quadratic function $q(x)$ with positive definite Hessian?
user avatar
1 vote
1 answer
57 views

Is $q(x) = \frac{1}{2} x^T H x - g^T x$ strongly convex?

Let $$q(x) := \frac{1}{2} x^T H x - g^T x$$ where matrix $H$ is symmetric positive definite and $g \in \mathbb{R}^n$. Clearly, the function is strictly convex, but why is it strongly convex?
user avatar
1 vote
0 answers
46 views

Showing no stationary point of the function $f(x)=\frac12\langle Ax,x\rangle+\langle b,x\rangle+c$ is a point of local extremum

Not recalling the theorem about the sufficient conditions for local extrema, show that no stationary point of the function $f:\Bbb R^2\to\Bbb R$ $$f(x)=\frac12\langle Ax,x\rangle+\langle b,x\rangle+c$$...
user avatar
  • 4,357
0 votes
2 answers
296 views

How to find the minimum value of $f(x)=x^TAx+b^Tx+c$?

A scalar valued function is defined as $f(x)=x^TAx+b^Tx+c$ , where $A$ is a symmetric positive definite matrix with dimension $n\times n$ ; $b$ and $x$ are vectors of dimension $n\times 1$. Show that ...
user avatar
  • 8,750
0 votes
1 answer
90 views

Dual problem of a quadratic problem

the primal problem is: minimize: $\frac{1}{2}y\cdot Py+e\cdot z $ over $(y,z)\in \mathbb{R}^{k}\times\mathbb{R}^{l}$ subject to $Dy+Ez=w$ where $P\in\mathbb{R}^{k\times k}$ is positive definite, $w\...
user avatar
  • 337

1
2 3 4 5
14