Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

2
votes
2answers
89 views

Maximizing a linear function over an ellipsoid

Let $A \in \mathbb{R}^{n\times n}$ be a positive definite matrix, $x \in \mathbb{R}^n$ and $c \in \mathbb{R} \setminus \{0\}$. I got to determine the maximum $$\max\{c^Ty:y\in \mathcal{E} (A,x)\}$$ ...
3
votes
3answers
62 views

Find minimum and maximum on range

$f(x,y)=x^{4}-x^{2}+y^{2}$ $B={(x,y)\in \mathbb R, x^{2}+y^{2}\leq 1 }$ I should find minimum and maximum of this function on the range B. I tried it with Lagrange Multiplier and I got these points ...
3
votes
1answer
58 views

Expected number of times a set of 10 integers (selected from 1-100) is selected before all 100 are seen

Suppose I have a set of 100 integers. I randomly choose 10 of those, make a note of which ones I selected, and repeat the process. What is the expected number of times this process must be repeated ...
2
votes
1answer
29 views

Least Squares Sensitivity to data

Let ($x_1$,$y_1$),...,($x_n$,$y_n$) be my data set. I have a function $f(x,{\bf c})$ where ${\bf c}=(c_1,...,c_m)$ is a vector of $m$ parameters. I want to fit to the data using non-linear least ...
3
votes
0answers
14 views

Skew-Symmetric Parts of Stochastic Matrices

It's easy to see that the set $\{W - W^T : W \in \mathbb{R}^{n \times n}\}$ is precisely the set of real skew-symmetric matrices. This continues to be the case if we restrict to (entry-wise) non-...
0
votes
0answers
29 views

Multiplying quaternions vs multiplying rotation matrices

It's a trivial question, but one I'm not 100% clear about. Given two matrices $$P_{\{1,2\}} = \left[ \begin{array}{cc}R & t \\ \textbf{0} & 1 \end{array}\right]$$ where $R$ is a 3x3 ...
3
votes
1answer
717 views

Maximum likelihood estimators, hypergeometric and binomial

I'm trying to solve a two part problem. The set up is as follows: consider a bag with $\theta$ red marbles and $7-\theta$ blue marbles, with $\theta$ being unknown. Let $x$ denote the number of red ...
3
votes
3answers
85 views

A convex optimisation problem involving the Euclidean norm

Any ideas on how to approach the following optimisation problem? $$\begin{array}{ll} \text{maximize} & \|Ax\|_2^2+\|Bx\|_2^2+\|Cx\|_2^2 \\ \text{subject to} & \|x\|_2 = 1\end{array}$$
2
votes
2answers
58 views

Let $Ax$ and $Ay$ minimize distance to $b \in \mathbb{R^m}.$ Show $x-y \in \ker(A).$

Let $A$ be an $m \times n$ real matrix and $b \in \mathbb{R^m}.$ Suppose $Ax$ and $Ay$ both minimize distance to $b,$ i.e. $||Ax-b|| = ||Ay-b||.$ Prove that $x-y \in \ker(A).$ Seems like there ...
0
votes
0answers
12 views

Orient edges in a mixed graph to minimize the critical path

3 down vote favorite A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way ...
0
votes
1answer
424 views

Maximization with the Dual using the Simplex Method.

I have an exam in a few hours. I need to understand the solution to the following question Find the Maximal to the the following $2 x_1 + 3 x_2$ is the objective function. The constraints are $...
1
vote
1answer
116 views

Largest rotated ellipse inscribed in a rectangle

Let's say I have a parametrized ellipse $$x (t) = a \cos(t) \cos(r) - b \sin(t) \sin(r)$$ $$y (t) = a \cos(t) \sin(r) + b \sin(t) \cos(r)$$ Where $r$ is the rotation around the axis and $t \in [0,2\...
0
votes
1answer
32 views

Optimize wrt a partial matrix?

I have a common optimization problem $$\arg\min_A \text{tr}( A^TWA),$$ where $W$ is a positive semi-definite matrix, and $A$ is the matrix to be optimized. If $A$ is completely unknown, with some ...
0
votes
0answers
6 views

Invariance of weighted matrix norms in relation to Quasi-Newton methods

In Fletcher's book page 60, he talks about the invariance property of BFGS-type methods. "To get an invariant formula out of this process it is necessary to use a measure with an invariance property. ...
1
vote
0answers
15 views

Confused about solution to the piecewise constant regression model

I am confused about the solution to the following solution to fitting piecewise constants: Specifically, are we minimising the sum of squares, that is, finding the vector $\beta = (\beta_1,\beta_2, ...
2
votes
1answer
550 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
26 views

The gas cloud covering problem

I'm faced with problem described below. My goal in posting this here is having you guys lead me in the right direction. Maybe there is a scientific article that treats a similar problem? Maybe a ...
0
votes
2answers
47 views

Lagrange multipliers with trigonometric functions. Stucked figuring out x and y values.

I want to find the maximum of the function $f(x,y) = \cos^2(x) + \cos^2(y)$ with the constraint $x-y = \pi/4$. Here are my partial derivatives: $$f_x = -2\cos(x)\cdot\sin(x)$$ $$f_y = -2\cos(y)\cdot\...
0
votes
0answers
15 views

Genetic algorithm optimize and minimize

I'm using a Genetic Algorithm to increase a certain value and decrease another. I'm trying to find the best parameters for a trading strategy. There are 2 values important for me. The netto profit ...
0
votes
1answer
64 views

McCormick Envelopes with more then 2 variables

I'm trying to solve a bilinear optimization problem by linearizing the problem using the McCormick Envelope method. It's quite a simple method when you are only using the product of two variables, ...
-2
votes
1answer
22 views

Distance between a point and a conic curve

I have a point $r=(100,0)$ and want to find the closest point to it from this set: $$k = \{(a,b) : b^2=1+a/4\}$$ where $a$ belongs to $[-4,0]$. I thought about defining function $h(x)=|r-x|$, and ...
3
votes
2answers
799 views

Optimization: maximum area of a triangle under a parabola

Optimization: maximum area of a triangle in a parabola Inside a curve ($x^2-25$ - Parabola) a triangle is drawn with A as the vertex at the origin and the line joining points B and C lie on the ...
1
vote
2answers
43 views

Logistic regression for football results - Estimating coefficient through maximum likelihood

Consider two football teams $V$ and $L$ with strengths $W_V$ and $W_L$, respectively. Let's assume that the draw probability $\mathbb{P}(Draw)$ is known. Then this model is supposed to give estimates ...
2
votes
3answers
49 views

Can't find minimum using Lagrange multipliers

I want to find the minimum of the function $f(x,y) = x + y^2$ with the constraint $2x^2 +y^2 = 1$. Here are my partial derivatives: $$f_x = 1$$ $$f_y = 2y$$ $$g_x = 4x$$ $$g_y = 2y$$ I have the ...
0
votes
0answers
16 views

How write one optimization formula.

In this game I start with a Galleon with capacity 400. I can upgrade the harbor to get more Galleons, or upgrade the technolgy to increase the Galleon base cargo size by 10%. Right now have 8 ...
0
votes
1answer
35 views

What are spurious local optima?

I keep seeing that word "spurious" (when used in the context of optimization), but I'm having trouble finding a good reference on what the definition of the term is.
0
votes
1answer
18 views

floor/ceiling/round functions in the constraints of an optimization?

I have a constrained optimization problem in which I have to impose a "floor" or "ceiling" constraint to the solution. In fact I decided to use these nonlinear rounding functions because I needed to ...
2
votes
0answers
28 views

Lasso with non-linear objective

I have a non-linear objective function that I want to minimize considering some constraints in order to obtain a sparse solution (lasso type). min f($\theta$) s.t. $\sum_i|\theta_i|\leq t$ $\theta_i ...
1
vote
1answer
44 views

Why does the “printing neatly” algorithm use cubes rather than squares?

In Introduction to Algorithms, 2nd ed. (Cormen, Leiserson, Rivest, and Stein), ch. 15, Dynamic Programming, problem 15-2 Printing neatly (a copy of which is here), the official solution given in ...
0
votes
1answer
15 views

Maximum (edge)weight connected subgraph of an undirected graph.

Let G be a undirected graph with weighted edges. I want to find a connected subgraph which has at most L nodes(vertices) whose sum of edges is maximum. It sounds similar to MWCS or PCST but here only ...
2
votes
0answers
23 views

Convergence of the minima of functionals

Let $\mathcal{H} \subset \mathbb{R}^3$ denote a compact subspace. Suppose we have a sequence of functionals $(Q_n)_{n\geq 1}$ and a functional $Q$ from $C(\mathcal{H},\mathbb{R}^3)$ (which is the ...
0
votes
0answers
14 views

Multi-objective optimization or single objective optimization?

I have this function: A(x)= P(x) / B(x) Firstly I thought about doing an multi-objective optimization, maximizing A(x) and minimizing B(x) because this two values are very important. But if I just ...
0
votes
1answer
12 views

Does projected gradint descent(pgd) results in the same minimizer as the one given by unconstrained gd and projected back on the constrained set?

For $f: \mathbb{R}^n \mapsto \mathbb{R}$ with $f(x) < \infty,\;\forall x \in \mathbb{R}^n$ and for convenience let's assume $f$ is continuously differentiable. Suppose we are trying to solve the ...
0
votes
1answer
45 views

Minimizing a strictly convex function with inequality constraint

So we've been learning about the Kuhn Tucker conditions in my non-linear optimization course and I've been having trouble with this problem: QUestion: description here Question: a strictly convex ...
0
votes
4answers
82 views

Minimize the function $f(y_1,y_2)=3 y_1^2+8y_2^2$ [closed]

I would like to minimize $f(y_1,y_2)=3 y_1^2+8y_2^2$ with the constraints $g(y_1,y_2)=y_1^2+y_2^2=1$. I thought I could use the Lagrange multipliers, but it is not work. Is there anyone could show me ...
3
votes
1answer
93 views

Least squares problem with constraint on the unit sphere

It is easy to find the minimum of $\|Ax-b\|_2$, when $A$ has full column rank. But how is the case when we add the constraint $\|x\|_2=1$? Or, to be explicit, $$\min_{\|x\|_2=1}\|Ax-b\|_2=?$$ My ...
0
votes
0answers
23 views

Optimal number of operations in the given scenario?

Suppose $$A_1=\{x_1+x_2+x_3,\quad x_2+x_3+x_4,\quad x_3+x_4+x_5\} \\ A_2=\{x_0+x_1+x_2, \quad x_0+x_1+x_8, \quad x_0+x_7+x_8\} \\ A_3=\{x_{10}+x_{11}+x_{12}, \quad x_{11}+x_{12}+x_7, \quad x_7+x_8+x_{...
0
votes
2answers
26 views

deriving Newton's method for optimization

I thought I understood the derivation of Newton's method for finding a minimum, but just realized I was not being at all careful! Here are three alternate "derivations". I think the first two are ...
3
votes
2answers
95 views

Basic Question about Newton's Method for Optimization

This is a very basic question about Newton's method for optimization, but I cannot seem to find the answer in any of my searches. If we are using Newton's method (or gradient descent), how do we find ...
2
votes
1answer
671 views

How to solve a quadratically constrained linear program (QCLP)?

Can anybody suggest some techniques to solve a quadratically constrained linear program (QCLP)? Any references on standard techniques would be helpful.
1
vote
2answers
33 views

Change of variables in minimization

I have the following non linear programming to solve: $$\left\{\begin{matrix} \min & (x-y)^2 +e^z+e^{-z} \\ \text{s.t.} & xz=0 \\ & yz=0 \end{matrix}\right.$$ The book suggests to ...
1
vote
3answers
103 views

Minimizing $\cot^2 A +\cot^2 B + \cot^2 C$ for $A+B+C=\pi$

If $A + B + C = \pi$, then find the minimum value of $\cot^2 A +\cot^2 B + \cot^2 C$. I don't know how to solve it. And can you please mention the used formulas first. What I can see is that if one ...
1
vote
1answer
323 views

What happens if we remove the non-negativity constraints in a linear programming problem?

As we know, a standard way to represent linear programs is $$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ with the associated dual ...
2
votes
0answers
161 views

Least-squares problem with quadratic equality constraint

I want to find the solution of a Lagrange equation whose inputs are matrices. First I have the equation Ax=0. By decomposing $A$ into $A_3$ (columns 9 to 11 of A), $A_9$ (the rest of the columns), ...
1
vote
1answer
45 views

A question about Lagrange multiplier in optimization

I read @amoeba 's answer in this post, PCA optimization problem is $$ \underset{\mathbf w}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw} \\ \text{s.t.}~~~~~~ \|\mathbf w\|_2=1 $$ where $\mathbf C$ ...
1
vote
0answers
12 views

KKT conditions for different inputs.

So I have the following problem: I'm trying to get a demand function for a nonlinear 2 variable optimisation problem. There are 3 inequality constraints. Doing the usual thing I get the following ...
0
votes
0answers
20 views

Book Recommendation for Infinite Dimensional Stochastic Optimization Problem in Discrete Time

Let $X(k)$ be i.i.d. discrete random variables and for all $k=0,1,2,...,N-1$, let $X:=(X(0),X(1)...,X(k))$ and $f := (f(0), f(1),...,f(k))$ with $f(k)$ be the decision function at time $k$, I want to ...
1
vote
0answers
41 views

Why the original MINLP and Linearized MILP are giving mismatched results?

I have an MINLP and its linearized formulation problem given below where the objective (nonconvex) and constraint C4 are nonlinear. We linearized them by applying some known techniques. However, when ...
2
votes
2answers
243 views

using the kronecker product and vec operators to write the following least squares problem in standard matrix form

I have a least squares problem with the following form: $$ \min_\mathbf{X} ~ \left\| \sum_{i=1}^n \mathbf{u}_i^\top \mathbf{X} \mathbf{v}_i - b_i \right\|^2 $$ where $\{\mathbf{u}_i\}_{i=1}^n$ and $\...
1
vote
3answers
58 views

Distance from a set to a point

There is this exercise I cannot understand well. It asks me for the distance between this set in $\mathbb{R}^3$ $$U = \{(x, y, z)\ |\ ax + y - 2z = 0, z = 0 \}$$ and the point $(0, b, 1)$. Also it ...