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)

1
vote
1answer
46 views

Constrained Minimization Problem derived from a Directed Graph

I'm looking for a solution the following graph problem for data analysis purposes. Basically, I have a directed graph of $N$ nodes where I know the following: The sum of the weights of the ...
1
vote
0answers
31 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
2
votes
1answer
71 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
2
votes
0answers
49 views

Local extremes for quartic multivariable function

I have the function :$\ f(x,y)= x^4 +y^4-8xy $, and I have to find it's local extreme points. I computed the partial derivatives : $\ f_x= 4x^3-8y$ $\ f_y= 4y^3-8x $ $\ f_{xx}= 12x^2 $ $\ f_{yy}= ...
1
vote
3answers
5k views

How to plot a phase portrait for this system of differential equations?

I beg your help.. I'd like the phase portrait for this system. I don't know how to use Mathematica/Matlab ... :( If anyone can make this portrait and post a print screen here, I would thank you ...
4
votes
1answer
745 views

Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
1
vote
1answer
95 views

A System of differential Equations

How can I analyze the phase diagram for this system of differential eqs? This field is not my area of my expertise, so please be generous with the answers. I appreciate quick references as well. ...
2
votes
2answers
2k views

Shortest distance between two curves

Let $C_1= \{ (x, y) \in \mathrm{R}^2 : y = x^2 +1 \}$ and $C_2= \{ (x, y) \in \mathrm{R}^2 : x = y^2 +1 \}$, find the points which minimize distance between $C_1$ and $C_2$. What I tried is: we know ...
2
votes
1answer
74 views

How to minimally move circles so that they don't overlap?

You're given a set of circles, all the same radius, residing at different locations in a 2d space. Some circles are in fixed positions. How do you make sure none of them overlap, minimizing the ...
0
votes
1answer
47 views

Size of square formed by soap in a cube frame

So through the work of Plateau (as I understand it), we know that soap tries to find the shortest connection between points. At least, that's what I was taught. With this in mind, I had to solve the ...
1
vote
0answers
74 views

analytic solution to structured algebraic Riccati equation

In solving a model I have written down for a research paper, I am left with two Algebraic Riccati Equations, that is I need to solve for $X$ in the equation \begin{align*} X = A^\top (X + XB(R + ...
0
votes
2answers
42 views

Finding local minimum under constraint

How to find the minimum of $f(x) = ||x-\mu||^2$, where $\mu = (1, 1)$ and $< x, \mu > = 0$ (the inner product is $0$)?
2
votes
1answer
73 views

Linear Programming - Handling $\max(x,0)$ in the objective function

Hello I have to solve the following problem $\min_P (\max (K_1+P,0)+ K_2 P)$, s.t. $P \in \mathcal{P}$. Is there a any trick to convert the $\max(\bullet,0)$ and convert it into a linear programming ...
3
votes
1answer
171 views

Positive semidefinite cone is generated by all rank one matrices.

The positive semidefinite cone is generated by all rank one matrices $xx^T$ . They form the extreme raysof the cone. The positive definite matrices lie in the interior of the cone. The positive ...
0
votes
0answers
76 views

3D Space Covering-Problem

Given a finite amount of "slots" in 3D space, e.g. $$S = [(1,2,3),(1,3,3),(1,4,3),(1,3,4)] \in \mathbb{N}^3.$$ I'm trying to find an efficient algorithm to determine a minimal set of (rectangular) ...
2
votes
1answer
131 views

Extremum of functional of a complex function

consider functional $E$ defined by $$E[z]=\int F(x,z(x))dx$$ where $F$ is a complex-valued nonlinear function. How can we find the function $z(x)$ so that $$G=|E|^2=EE^*=\iint ...
2
votes
2answers
195 views

Multivariable optimization books

I have some economic data in hand, and I would like to make forecasting out of it (e.g., consumer demand, price elasticity and so on). As far as I understand, these characteristics can be (to some ...
0
votes
1answer
28 views

Continuous and binary variable question

For $y_1$ and $y_2$ as continuous variables how can this statement be reformed in binary and continuous variables with linear constraints Either $|y_1 - y_2| = 2$ or $|y_1 - y_2| = 4$
0
votes
1answer
18 views

Optimizing a value appearing in the Cheriton-Tarjan MST algorithm?

In the analysis of the Cheriton-Tarjan MST algortihm, there is a step that asks to optimize a quantity subject to a nonlinear constraint. Specifically, it's as follows: Let $c_1, c_2, ..., c_p$ be ...
1
vote
1answer
52 views

The most optimal way to solve this set of non-linear equations in high dimensions

So I have a series of non-linear equations which I wish to solve as fast as possible, to illustrate for the case of $n = 4$, I have the following equations: \begin{gather*} ...
4
votes
1answer
3k views

Finding the max flow of an undirected graph with Ford-Fulkerson

Given the following undirected graph, how would I find the max-flow/min-cut? Now, I know that in order to solve this, I need to redraw the graph so that it is directed as shown below. However, ...
0
votes
1answer
95 views

find integral values k such that sum of expression is minimized

Given n values $X_1 , X_2 , ...., X_n$ , where $X_i$ can be positive or negative. The absolute values of $X_i$ will be less than $100000$ , also $n<=100000$ . What should be the possible value(s) ...
2
votes
1answer
173 views

least squares minimization problem

It's easy to show that the solution to a least squares problem such as minimizing $||Ax+b||$ is $(A^tA)^{-1}A^tb$. But how can one minimize $\sum_{i}||A_ix+b_i||$? In one of the passages of the ...
1
vote
1answer
91 views

Relation between softmax and max

For two vectors $X$ and $Y$ in $\mathbf{R}^n$, does the inequality below hold? $\left| \text{softmax} X - \text{softmax} Y \right| \leq \text{max} | X - Y |$ Softmax is the same as log-sum-exp: ...
1
vote
0answers
39 views

Minimum number of operations

We have a sequence $A$ of size $n$, where each element $A_i \in \{-1,0,1\}$. In each operation we can increase $A_{i+1}$ by $A_i$. The goal is to make the sequence non-decreasing i.e. $A_1 \leq A_2 ...
0
votes
1answer
35 views

Can we find an $n$ that minimizes this function?

If we suppose that we have positive integers $k$, $c$, and $v$, can we find the $n$ that minimizes: $$k^n \frac{\log{2^v}}{\log{v}}v^{\log_2{(k \cdot v \cdot c/n)}}$$
1
vote
1answer
166 views

How to show this algorithm on positive semidefinite matrices converges to a global maximum determinant

I'm dealing with an algorithm which is supposed to converge to the maximum determinant of certain positive semidefinite matrices. The problem is that we have such a matrix, and we vary certain ...
1
vote
1answer
216 views

Solution to a Hadamard product least squares

Given two full-rank matrices $A \in \mathbb{R}^{n \times p}, B \in \mathbb{R}^{n \times k}$ and vectors $y \in \mathbb{R}^n, u \in \mathbb{R}^p, v \in \mathbb{R}^k$ I'd like to solve an optimization ...
3
votes
1answer
148 views

Maximal total-weight matching in bipartite graph problem

Given a $G(A,B,E)$ bipartite graph and a $w: E \to R$ weight function. Problem 1: We are looking for a $M$ matching where the sum of the weights of edges in the M matching is maximal. This problem ...
4
votes
0answers
49 views

Is there a name for systems of equations with min and max functions included?

In a big project I'm working on, I'm running into systems of equations that look like the following: $$a = \min(b, c)$$ $$b = d^2 + a$$ $$c = \max(a + b, d)$$ Basically, nonlinear systems of ...
0
votes
1answer
22 views

Find the values of $c_1,c_2$ so that $(-0.5, 0, 0)$ is a point of a local maximum.

Given the problem $$ \max [-(x_1+x_2+x_3)]$$ subject to the contraints $$x_1^2+x_2^2=2c_1$$ $$x_1+5x_2+x_3^2=2c_2$$ I am asked to find the values of $c_1,c_2$ so that $(-0.5, 0, 0)$ is a point of a ...
0
votes
1answer
107 views

How do I optimize a function subject to a two-part constraint?

I would like to maximize the following function $$\max\; U= log(xT_o + (1-x)T_s) + log(Y)$$ by choosing levels of $T_o$, $T_s$, and $Y$, and where $x\in[0:1]$ subject to $$N = \binom{P_sT_s+Y ...
1
vote
1answer
97 views

Optimization of cake pan volume from area of pan

It was difficult to accurately word this question, so hopefully a bit of context will clear that up. Context: I have a cake dish that is made by cutting out squares from the corners of a 25cm by 40 ...
0
votes
1answer
55 views

Implement ideal line search algorithm

I have the function $f(x)=\frac {1}{2} \mathbf x^T Q \mathbf x$. I want to use the steepest descent algorithm where $Q$ is the diagonal matrix $\begin{bmatrix}1 & 0\\0 & 20\end{bmatrix}$ and ...
1
vote
2answers
41 views

What is the Minimal cost?

A power house, $P$, is on one bank of a straight river $W$ meters (m) wide, and a factory, $F$, is on the opposite bank $L$ meters downstream from $P$. The cable has to be taken across the river, ...
1
vote
0answers
33 views

Prove that the partial derivatives of $(y-g_i+a\sum^n_{j=1} g_j)$ are positive

I have a function: $$\pi_i^1=y-g_i+a\sum^n_{j=1}g_j,$$ where 0 < a<1< na, and I need to prove this: $$\frac{\partial(\sum^n_{i=1}\pi^1_i)}{\partial g_i}=-1+na>0.$$ I am not very ...
4
votes
1answer
33 views

Optimization in $L_1$, does this make sense?

I'd like to find a probability distribution $f(x)$ on the unit interval $[0,1]$ that obeys a given set of moment constraints, e.g. $\int_0^1 xf(x) dx = \mu_0$ for some given $\mu_0$, and so forth. ...
0
votes
1answer
40 views

Determine Number of Simplex Iterations

I have an assignment, which asks me to determine the least number of simplex iterations necessary to solve different optimization problems. One problem is: a model with 1150 constraints and 2340 ...
1
vote
2answers
154 views

formulating the dual for an instance of a SOCP with linear constraints

I have an optimization problem with second-order cone constraints and linear inequalities and inequalities (shown below). I want to formulate the dual, but have been having trouble. ...
2
votes
0answers
43 views

Optimization/Jensens Inequality

A community has a fixed stock $X$ of oil that it has to consume over an infinite horizon. The utility function to be maximized is $$U=∑_t \delta^t \ln (C_t)$$ where $C_t$ represents consumption of the ...
0
votes
1answer
144 views

How to define positive definite matrix?

why first matrix in fig is not positive definte, but second is a positive definite matrix. As Eigen values of both the matrix are non negative. and also real(A)-transpose(real(A)) is zero in both ...
0
votes
1answer
37 views

Lagrangian Multiplier Question

I can do question 2 easily but I'm running into some problems proving 1 rigorously. No idea how to go about doing it at all.
0
votes
1answer
64 views

How to ensure extreme? — using Extreme Value Theorem

I think it's a simple question. How can I ensure the existence of an extreme (maximum or minimum) using the Extreme Value Theorem / Weierstrass theorem? For example, this multivariate case: $$ ...
0
votes
2answers
125 views

Symmetric Positive Definite and Gradient Proof

I have the function $f(x)=\frac {1}{2} \mathbf x^T Q \mathbf x - \mathbf b^T \mathbf x$ where $Q$ is symmetric. I'm trying to show that solving $\nabla f(\mathbf x) = 0$ is equivalent to solving $Q ...
2
votes
1answer
63 views

A stupid question about constrained optimization

This is taken from an example in Boas, Mathematical Methods for Physicists. The problem is to minimize the distance, $d=\sqrt{x^2+y^2}$, from the origin to the curve $y=1-x^2$. That is minimize $d$ to ...
0
votes
2answers
45 views

Solving lagrange multiplies

The problem is: $$ \begin{align} \operatorname{max} & \quad ax+by \\ \text{subject to} & \quad x+y=m. \end{align} $$ The Lagrangian is: $$L(x,y) = ax+by−λ(x+y−m).$$ And so far I have: $$ ...
0
votes
1answer
38 views

Minima of the function $\ f(x) =\frac{150\times 1.15^x}{x}$

Let f(x) be the function $$f(x) = \frac{150\times 1.15^x}{x}$$ How can I find the minimum value of that function in the Natural Numbers Domain? If the derivative of a function is the equation of a ...
0
votes
1answer
86 views

Maximizing the length of a right-triangle hypotenuse

Given different continuous ranges of values for the legs, how can I find the values that maximize the length pf the hypotenuse of the right triangle? In other words, given that A lies between X and Y ...
0
votes
0answers
54 views

How can I maximize the area of a rectangle given a continuous range of values for the length and width?

All the examples I have for rectangle area maximization problems start by having one of the sides fixed. But suppose I have a continuous range such that length is between A and B and height is between ...
3
votes
4answers
102 views

Differentiability of $\mathrm{max}(x, y)$ at $x=y$

I am trying to figure out differentiability of $\mathrm{max}(x, y)$. Intuitively, it should not be differentiable at $x=y$, since it changes direction "non-smoothly" at those points. I can not, ...